Research map / Learning theory and algorithms / Sample complexity
Active Learning of General Halfspaces: Label Queries vs Membership Queries
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows an information-theoretic label-complexity lower bound for active learning of general Gaussian halfspaces, and gives a computationally efficient agnostic membership-query learner with near-optimal query complexity, separating MQ from label-query active learning.
Problem
Learning general (non-homogeneous, possibly biased) halfspaces under Gaussian marginals in active (label query) and membership query models, where the 1/p bias term makes passive-style active learning costly.
Approach
A lower bound showing pool-based active learners need ~d/(p log m) label queries unless the pool is exponentially large, plus an agnostic MQ learner using label smoothing to estimate a warm start from random negative examples and localization-based gradient refinement with binary search on the threshold, achieving Õ(min{1/p,1/ε}+d polylog(1/ε)) queries.
Key results
- Pool-based active learners need Ω̃(d/(p log m)) label queries for general Gaussian halfspaces unless the pool has size 2^poly(d), ruling out improvement over passive Õ(d/ε) for p=Θ(ε log(1/ε)).
- An agnostic membership-query learner achieves error O(opt)+ε with Õ(min{1/p,1/ε} + d polylog(1/ε)) queries in poly(d,M) time.
- The MQ upper bound and the active lower bound together give a strong separation between active (label query) and membership query models.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive label queries from a pool of m unlabeled examples | Learning general halfspaces under the Gaussian distribution · Gaussian general halfspaces | label complexity: \Tilde{\Omega}(d/(p\log(m))) | Hurt |
| Use membership queries instead of pool-based label queries | Agnostic learning of general halfspaces · Gaussian general halfspaces | query complexity: \Tilde{O}(\min\{1/p, 1/\epsilon\} + d\cdot\mathrm{polylog}(1/\epsilon)) | Helped |
Surprising findings
- Active learning gives no non-trivial advantage over passive learning for general Gaussian halfspaces unless the unlabeled pool is exponentially large.
Limitations
- Some warm-start analysis for very large thresholds is only sketched (deferred to a full version), and the case eta*sqrt(log(1/eta)) > 1/t is not fully covered in the main text.
- The lower bound relies on an explicit Gaussian construction and a Yao-style argument; the MQ algorithm's guarantees depend on the 1/p exploration term, which is argued to be unavoidable in the agnostic setting.
Experimental setup
Metrics: label complexity membership query complexity 0-1 error
Baselines: passive learners with poly(d,1/epsilon) samples Balcan-Hanneke-Vaughan active learner for general halfspaces
Builds on: Balcan-Hanneke-Vaughan active learning bounds localization technique of Awasthi-Balcan-Long Chow parameter estimation Yao's minimax principle
Closest papers by meaning
- Active Classification with Few Queries under Misspecification (NeurIPS 2024 · similarity 0.94)
- Reliable Learning of Halfspaces under Gaussian Marginals (NeurIPS 2024 · similarity 0.89)
- Robust Regression of General ReLUs with Queries (NeurIPS 2025 · similarity 0.88)
- An Efficient Tester-Learner for Halfspaces (ICLR 2024 · similarity 0.88)
- Smoothed Agnostic Learning of Halfspaces over the Hypercube (NeurIPS 2025 · similarity 0.87)
- Learning Noisy Halfspaces with a Margin: Massart is No Harder than Random (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.