mlsanityData to 7 Oct 2026

Active Learning of General Halfspaces: Label Queries vs Membership Queries

arXiv 2501.00508 ↗First posted 31 Dec 2024cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

11 of 36 references.

References · 11

  1. 2014Minimax Analysis of Active Learningcited by 61
  2. 2020Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginalscited by 57
  3. 2021The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginalscited by 52
  4. 2017Learning Geometric Concepts with Nasty Noisecited by 46
  5. 2023Near-Optimal Cryptographic Hardness of Agnostically Learning Halfspaces and ReLU Regression under Gaussian Marginalscited by 31
  6. 2019The Power of Comparisons for Actively Learning Linear Classifierscited by 20
  7. 2023Efficient Testable Learning of Halfspaces with Adversarial Label Noisecited by 19
  8. 2020Point Location and Active Learning: Learning Halfspaces Almost Optimallycited by 13
  9. 2020On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noisecited by 11
  10. 2024Active Learning with Simple Questionscited by 4
  11. 2022Active Learning of Classifiers with Label and Seed Queriescited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 5.

6 papers.

  1. 2025Actively Learning Halfspaces without Synthetic Datacited by 0
  2. 2026Learning Half-Spaces from Perturbed Contrastive Examplescited by 0
  3. 2026Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginalscited by 0
  4. 2026Robust Regression of General ReLUs with Queriescited by 0
  5. 2026Efficiently Learning Drifting Halfspaces with Massart Noisecited by 0
  6. 2026On the Sample Complexity of Active Learning with Membership Queriescited by 0