Efficient active learning of sparse halfspaces with arbitrary bounded noise

Abstract

We study active learning of homogeneous $s$-sparse halfspaces in ${\mathbb{R}}^d$ under the setting where the unlabeled data distribution is isotropic log-concave and each label is flipped with probability at most $\eta$ for a parameter $\eta \in [0,\frac{1}{2})$, known as the bounded noise. Even in the presence of mild label noise, i.e. $\eta$ is a small constant, this is a challenging problem and only recently have label complexity bounds of the form $\tilde{O}(s\cdot \mathrm{polylog}(d,\frac{1}{\epsilon }))$ been established in [Zhang, 2018] for computationally efficient algorithms. In contrast, under high levels of label noise, the label complexity bounds achieved by computationally efficient algorithms are much worse: the best known result of [Awasthi et al., 2016] provides a computationally efficient algorithm with label complexity $\tilde{O}((\frac{s\ln d}{\epsilon }{)}^{2^{\mathrm{poly}(1/(1-2\eta ))}})$, which is label-efficient only when the noise rate $\eta$ is a fixed constant. In this work, we substantially improve on it by designing a polynomial time algorithm for active learning of $s$-sparse halfspaces, with a label complexity of $\tilde{O}(\frac{s}{(1-2\eta {)}^4}\mathrm{polylog}(d,\frac{1}{\epsilon }))$. This is the first efficient algorithm with label complexity polynomial in $\frac{1}{1-2\eta }$ in this setting, which is label-efficient even for $\eta$ arbitrarily close to $\frac{1}{2}$. Our active learning algorithm and its theoretical guarantees also immediately translate to new state-of-the-art label and sample complexity results for full-dimensional active and passive halfspace learning under arbitrary bounded noise. The key insight of our algorithm and analysis is a new interpretation of online learning regret inequalities, which may be of independent interest.

33 pages, 2 figures; NeurIPS 2020

References in corpus (5)

• High-dimensional classification using features annealed independence rules
• Online Learning: A Modern Introduction Using Convex Optimization
• Adaptive Hard Thresholding for Near-optimal Consistent Robust Regression
• Efficient Learning of Linear Separators under Bounded Noise
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance

Cited by in corpus (10)

• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise
• Attribute-Efficient Learning of Halfspaces with Malicious Noise: Near-Optimal Label Complexity and Noise Tolerance
• Boosting in the Presence of Massart Noise
• On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise
• One-Bit Compressed Sensing via One-Shot Hard Thresholding
• Feedback Coding for Active Learning
• Robust Learning under Strong Noise via SQs
• Near-Optimal Statistical Query Hardness of Learning Halfspaces with Massart Noise
• ReLU Regression with Massart Noise
• Sample-Optimal PAC Learning of Halfspaces with Malicious Noise