# Efficient active learning of sparse halfspaces

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2018.

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

- [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)
- [Sample-Optimal PAC Learning of Halfspaces with Malicious Noise](https://mlsanity.com/paper/2102.06247/) (2021)
- [Improved Algorithms for Neural Active Learning](https://mlsanity.com/paper/2210.00423/) (2022)
- [Neural Active Learning Beyond Bandits](https://mlsanity.com/paper/2404.12522/) (2024)
- [Margin-based sampling in high dimensions: When being active is less efficient than staying passive](https://mlsanity.com/paper/2212.00772/) (2022)
- [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)
- [Attribute-Efficient PAC Learning of Sparse Halfspaces with Constant Malicious Noise Rate](https://mlsanity.com/paper/2505.21430/) (2025)
- [On the Sample Complexity of Rank Regression from Pairwise Comparisons](https://mlsanity.com/paper/2105.01463/) (2021)
- [Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach](https://mlsanity.com/paper/2310.15411/) (2023)
- [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)

## Abstract (arXiv)

We study the problem of efficient PAC active learning of homogeneous linear classifiers (halfspaces) in ℝd, where the goal is to learn a halfspace with low error using as few label queries as possible. Under the extra assumption that there is a t-sparse halfspace that performs well on the data (t ll d), we would like our active learning algorithm to be em attribute efficient, i.e. to have label requirements sublinear in d. In this paper, we provide a computationally efficient algorithm that achieves this goal. Under certain distributional assumptions on the data, our algorithm achieves a label complexity of O(t · polylog(d, frac 1 ε)). In contrast, existing algorithms in this setting are either computationally inefficient, or subject to label requirements polynomial in d or frac 1 ε.