Research map / Learning theory and algorithms / Sample complexity
Active Classification with Few Queries under Misspecification
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.
Proposes threshold statistical queries (TSQ) for pool-based active learning of halfspaces, achieving polylog(1/ε) queries under Massart noise and showing Ω̃(1/ε) lower bound under agnostic noise.
Problem
Pool-based active learning of halfspaces under label noise (Massart and agnostic), where mistake-based and region queries lose their query efficiency and standard active learning needs poly(1/ε) labels.
Approach
A new query language, threshold statistical queries, which asks whether a sum over pool examples of a bounded function of (example, label) exceeds a threshold; combined with Forster's transform and Vaidya's cutting-plane method, it enables noise-tolerant query-efficient halfspace learning under Massart noise, and a reduction from agnostic distributed learning gives a lower bound for singletons.
Key results
- Algorithm uses poly-log(1/ε) TSQs (Õ(d^3 log^3(1/ε))) to label a pool under Massart noise with error η+ε in polynomial time.
- Under agnostic noise, any algorithm using fewer than Õ(1/ε) TSQs fails to achieve opt+ε for singleton classes, implying Ω̃(1/ε) for halfspaces.
- Agnostic labeling with error O(opt)+ε is achievable with Õ(d log(1/ε)) TSQs, though with exponential running time.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use threshold statistical queries for halfspace learning under Massart noise | Halfspace learning · Halfspaces under Massart noise | TSQ query complexity: ˜O(d3 log3(1/ϵ)) | Helped |
| Use threshold statistical queries for halfspace learning under Massart noise | Halfspace learning · Halfspaces under Massart noise | labeling error: η + ϵ | Helped |
| Use threshold statistical queries for agnostic learning of singletons | Singleton functions · Singletons under adversarial label noise | TSQ query complexity: ˜O(1/ϵ) | Hurt |
| Use the approximate agnostic learner for a finite-VC class | Hypothesis classes with finite VC dimension · Finite-VC hypothesis classes under adversarial label noise | TSQ query complexity: ˜O(d log(1/ϵ)) | Helped |
| Use the approximate agnostic learner for a finite-VC class | Hypothesis classes with finite VC dimension · Finite-VC hypothesis classes under adversarial label noise | labeling error: O(opt) + ϵ | Mixed |
Surprising findings
- Mistake-based region queries become useless under even tiny random classification noise, as they return yes with high probability.
Limitations
- Agnostic noise requires Ω̃(1/ε) TSQs for exact opt+ε guarantee, so the efficient result is limited to Massart/random noise.
- Massart/RCN guarantees assume the pool is large (poly(d,1/ε)) and the labeling noise is persistent.
- Agnostic O(opt)+ε algorithm is computationally exponential.
Experimental setup
Metrics: query complexity classification error
Baselines: region queries seed queries label queries
Builds on: region queries seed queries Vaidya's cutting plane method Forster's transform Massart noise model
Closest papers by meaning
- Active Learning of General Halfspaces: Label Queries vs Membership Queries (NeurIPS 2024 · similarity 0.94)
- Active Learning from Imperfect Labelers (NeurIPS 2016 · similarity 0.88)
- Active Covering (ICML 2021 · similarity 0.88)
- Improved Algorithms for Agnostic Pool-based Active Classification (ICML 2021 · similarity 0.88)
- Robust Regression of General ReLUs with Queries (NeurIPS 2025 · similarity 0.87)
- Universal Rates for Active Learning (NeurIPS 2024 · similarity 0.86)
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.