mlsanityData to 7 Oct 2026

Exponential Savings in Agnostic Active Learning through Abstention

arXiv 2102.00451 ↗First posted 31 Jan 2021cs.LG cs.IT math.ITcited by 23

Not on the map. Why?

Abstract (arXiv)

We show that in pool-based active classification without assumptions on the underlying distribution, if the learner is given the power to abstain from some predictions by paying the price marginally smaller than the average loss 1/2 of a random guess, exponential savings in the number of label requests are possible whenever they are possible in the corresponding realizable problem. We extend this result to provide a necessary and sufficient condition for exponential savings in pool-based active classification under the model misspecification.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Builds on 8 of its 61 references that are in the map. First posted on arXiv 31 Jan 2021.

Builds on

8 of 61 references.

References · 8

  1. 2014Minimax Analysis of Active Learningcited by 61
  2. 2014Beyond Disagreement-based Agnostic Active Learningcited by 21
  3. 2020Fast Rates for Online Prediction with Abstentioncited by 19
  4. 2019Fast classification rates without standard margin assumptionscited by 16
  5. 2016Active Learning from Imperfect Labelerscited by 13
  6. 2017Adaptivity to Noise Parameters in Nonparametric Active Learningcited by 12
  7. 2017The Relationship Between Agnostic Selective Classification Active Learning and the Disagreement Coefficientcited by 6
  8. 2017An Adaptive Strategy for Active Learning with Smooth Decision Boundarycited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 6; 2024: 1; 2025: 4; 2026: 4.

23 papers.

Sort:

By area:

  1. 2021Machine Learning with a Reject Option: A surveycited by 107
  2. 2023Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithmscited by 36
  3. 2023Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstentioncited by 32
  4. 2021Classification with abstention but without disparitiescited by 27
  5. 2022Efficient Active Learning with Abstentioncited by 21
  6. 2021Active Learning in Bayesian Neural Networks with Balanced Entropy Learning Principlecited by 14
  7. 2022Active Learning with Neural Networks: Insights from Nonparametric Statisticscited by 13
  8. 2024Revisiting Agnostic PAC Learningcited by 11
  9. 2022Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Conditioncited by 9
  10. 2023Reliable learning in challenging environmentscited by 9
  11. 2023High-Probability Risk Bounds via Sequential Predictorscited by 9
  12. 2022A Regret-Variance Trade-Off in Online Learningcited by 7
11 more
  1. 2022Promises and Pitfalls of Threshold-based Auto-labelingcited by 6
  2. 2025Test-Time Matching: Unlocking Compositional Reasoning in Multimodal Modelscited by 6
  3. 2023Online Decision Mediationcited by 4
  4. 2026Active Testing of Large Language Models via Approximate Neyman Allocationcited by 4
  5. 2025Towards Multimodal Active Learning: Efficient Learning with Limited Paired Datacited by 3
  6. 2025Reweighting Improves Conditional Risk Boundscited by 1
  7. 2026Online Finetuning Decision Transformers with Pure RL Gradientscited by 1
  8. 2023Selective Nonparametric Regression via Testingcited by 0
  9. 2025Near-Exponential Savings for Mean Estimation with Active Learningcited by 0
  10. 2026Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysiscited by 0
  11. 2026Optimal Learning Under Tsybakov Noisecited by 0