# Efficient active learning of sparse halfspaces with arbitrary bounded noise

arXiv: https://arxiv.org/abs/2002.04840 · HTML: https://mlsanity.com/paper/2002.04840/

## Key facts

- Cited by 29 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 12 Feb 2020.

## Built on by (most cited first, 29 of 29)

- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Tester-Learners for Halfspaces: Universal Algorithms](https://mlsanity.com/paper/2305.11765/) (2023)
- [Forster Decomposition and Learning Halfspaces with Noise](https://mlsanity.com/paper/2107.05582/) (2021)
- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [List-Decodable Sparse Mean Estimation](https://mlsanity.com/paper/2205.14337/) (2022)
- [Improved Algorithms for Neural Active Learning](https://mlsanity.com/paper/2210.00423/) (2022)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Boosting in the Presence of Massart Noise](https://mlsanity.com/paper/2106.07779/) (2021)
- [ReLU Regression with Massart Noise](https://mlsanity.com/paper/2109.04623/) (2021)
- [Neural Active Learning Beyond Bandits](https://mlsanity.com/paper/2404.12522/) (2024)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Efficient PAC Learning of Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2410.01186/) (2024)
- [Semi-verified PAC Learning from the Crowd](https://mlsanity.com/paper/2106.07080/) (2021)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)
- [Attribute-Efficient PAC Learning of Low-Degree Polynomial Threshold Functions with Nasty Noise](https://mlsanity.com/paper/2306.00673/) (2023)
- [AdaBoost and robust one-bit compressed sensing](https://mlsanity.com/paper/2105.02083/) (2021)
- [Agnostic Learnability of Halfspaces via Logistic Loss](https://mlsanity.com/paper/2201.13419/) (2022)
- [Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2505.21430/) (2025)
- [Feedback Coding for Active Learning](https://mlsanity.com/paper/2103.00654/) (2021)
- [Self-Directed Linear Classification](https://mlsanity.com/paper/2308.03142/) (2023)
- [Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach](https://mlsanity.com/paper/2310.15411/) (2023)
- [Reliable Learning of Halfspaces under Gaussian Marginals](https://mlsanity.com/paper/2411.11238/) (2024)
- [Towards Efficient Contrastive PAC Learning](https://mlsanity.com/paper/2502.15962/) (2025)
- [Learning Guarantee of Reward Modeling Using Deep Neural Networks](https://mlsanity.com/paper/2505.06601/) (2025)
- [Testable Learning of General Halfspaces under Massart Noise](https://mlsanity.com/paper/2602.22300/) (2026)
- [Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization](https://mlsanity.com/paper/2606.17215/) (2026)
- [Optimal Learning Under Tsybakov Noise](https://mlsanity.com/paper/2608.08416/) (2026)

## Abstract (arXiv)

We study active learning of homogeneous s-sparse halfspaces in ℝd under the setting where the unlabeled data distribution is isotropic log-concave and each label is flipped with probability at most η for a parameter η ∈ big[0, frac12big), known as the bounded noise. Even in the presence of mild label noise, i.e. η is a small constant, this is a challenging problem and only recently have label complexity bounds of the form tildeObig(s · polylog(d, frac1ε)big) 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 tildeObig((fracs ln dε)^2poly(1/(1-2η)) big), which is label-efficient only when the noise rate η 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 tildeObig(fracs(1-2η)4 polylog (d, frac 1 ε) big). This is the first efficient algorithm with label complexity polynomial in frac11-2η in this setting, which is label-efficient even for η arbitrarily close to frac12. 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.