# Active Learning of General Halfspaces: Label Queries vs Membership Queries

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 36 references that are in the map.
- First posted on arXiv 31 Dec 2024.

## Builds on (most cited first, 11 of 11)

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals](https://mlsanity.com/paper/2006.16200/) (2020)
- [The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals](https://mlsanity.com/paper/2102.04401/) (2021)
- [Learning Geometric Concepts with Nasty Noise](https://mlsanity.com/paper/1707.01242/) (2017)
- [Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginals](https://mlsanity.com/paper/2302.06512/) (2023)
- [The Power of Comparisons for Actively Learning Linear Classifiers](https://mlsanity.com/paper/1907.03816/) (2019)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [Point Location and Active Learning: Learning Halfspaces Almost Optimally](https://mlsanity.com/paper/2004.11380/) (2020)
- [On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise](https://mlsanity.com/paper/2012.10793/) (2020)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Active Learning of Classifiers with Label and Seed Queries](https://mlsanity.com/paper/2209.03996/) (2022)

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

- [Actively Learning Halfspaces without Synthetic Data](https://mlsanity.com/paper/2509.20848/) (2025)
- [Learning Half-Spaces from Perturbed Contrastive Examples](https://mlsanity.com/paper/2602.02080/) (2026)
- [Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals](https://mlsanity.com/paper/2605.21428/) (2026)
- [Robust Regression of General ReLUs with Queries](https://mlsanity.com/paper/2606.11130/) (2026)
- [Efficiently Learning Drifting Halfspaces with Massart Noise](https://mlsanity.com/paper/2606.11149/) (2026)
- [On the Sample Complexity of Active Learning with Membership Queries](https://mlsanity.com/paper/2609.27241/) (2026)

## Abstract (arXiv)

We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces under the Gaussian distribution on Rd in the presence of some form of query access. In the classical pool-based active learning model, where the algorithm is allowed to make adaptive label queries to previously sampled points, we establish a strong information-theoretic lower bound ruling out non-trivial improvements over the passive setting. Specifically, we show that any active learner requires label complexity of tildeOmega(d/(log(m)ε)), where m is the number of unlabeled examples. Specifically, to beat the passive label complexity of tildeO (d/ε), an active learner requires a pool of 2poly(d) unlabeled samples. On the positive side, we show that this lower bound can be circumvented with membership query access, even in the agnostic model. Specifically, we give a computationally efficient learner with query complexity of tildeO(min1/p, 1/ε + d· polylog(1/ε)) achieving error guarantee of O(opt)+ε. Here p ∈ [0, 1/2] is the bias and opt is the 0-1 loss of the optimal halfspace. As a corollary, we obtain a strong separation between the active and membership query models. Taken together, our results characterize the complexity of learning general halfspaces under Gaussian marginals in these models.