# Exponential Savings in Agnostic Active Learning through Abstention

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

## Key facts

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

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

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Beyond Disagreement-based Agnostic Active Learning](https://mlsanity.com/paper/1407.2657/) (2014)
- [Fast Rates for Online Prediction with Abstention](https://mlsanity.com/paper/2001.10623/) (2020)
- [Fast classification rates without standard margin assumptions](https://mlsanity.com/paper/1910.12756/) (2019)
- [Active Learning from Imperfect Labelers](https://mlsanity.com/paper/1610.09730/) (2016)
- [Adaptivity to Noise Parameters in Nonparametric Active Learning](https://mlsanity.com/paper/1703.05841/) (2017)
- [The Relationship Between Agnostic Selective Classification Active Learning and the Disagreement Coefficient](https://mlsanity.com/paper/1703.06536/) (2017)
- [An Adaptive Strategy for Active Learning with Smooth Decision Boundary](https://mlsanity.com/paper/1711.09294/) (2017)

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

- [Machine Learning with a Reject Option: A survey](https://mlsanity.com/paper/2107.11277/) (2021)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [Theoretically Grounded Loss Functions and Algorithms for Score-Based Multi-Class Abstention](https://mlsanity.com/paper/2310.14770/) (2023)
- [Classification with abstention but without disparities](https://mlsanity.com/paper/2102.12258/) (2021)
- [Efficient Active Learning with Abstention](https://mlsanity.com/paper/2204.00043/) (2022)
- [Active Learning in Bayesian Neural Networks with Balanced Entropy Learning Principle](https://mlsanity.com/paper/2105.14559/) (2021)
- [Active Learning with Neural Networks: Insights from Nonparametric Statistics](https://mlsanity.com/paper/2210.08367/) (2022)
- [Revisiting Agnostic PAC Learning](https://mlsanity.com/paper/2407.19777/) (2024)
- [Reliable learning in challenging environments](https://mlsanity.com/paper/2304.03370/) (2023)
- [High-Probability Risk Bounds via Sequential Predictors](https://mlsanity.com/paper/2308.07588/) (2023)
- [Exponential Tail Local Rademacher Complexity Risk Bounds Without the Bernstein Condition](https://mlsanity.com/paper/2202.11461/) (2022)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Promises and Pitfalls of Threshold-based Auto-labeling](https://mlsanity.com/paper/2211.12620/) (2022)
- [Test-Time Matching: Unlocking Compositional Reasoning in Multimodal Models](https://mlsanity.com/paper/2510.07632/) (2025)
- [Active Testing of Large Language Models via Approximate Neyman Allocation](https://mlsanity.com/paper/2605.10075/) (2026)
- [Online Decision Mediation](https://mlsanity.com/paper/2310.18601/) (2023)
- [Towards Multimodal Active Learning: Efficient Learning with Limited Paired Data](https://mlsanity.com/paper/2510.03247/) (2025)
- [Reweighting Improves Conditional Risk Bounds](https://mlsanity.com/paper/2501.02353/) (2025)
- [Online Finetuning Decision Transformers with Pure RL Gradients](https://mlsanity.com/paper/2601.00167/) (2026)
- [Selective Nonparametric Regression via Testing](https://mlsanity.com/paper/2309.16412/) (2023)
- [Near-Exponential Savings for Mean Estimation with Active Learning](https://mlsanity.com/paper/2511.05736/) (2025)
- [Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysis](https://mlsanity.com/paper/2602.05333/) (2026)
- [Optimal Learning Under Tsybakov Noise](https://mlsanity.com/paper/2608.08416/) (2026)

## 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.