# Efficient Active Learning with Abstention

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 62 references that are in the map.
- First posted on arXiv 31 Mar 2022.

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

- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Practical Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/1803.01088/) (2018)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Active Learning for Cost-Sensitive Classification](https://mlsanity.com/paper/1703.01014/) (2017)
- [Exponential Savings in Agnostic Active Learning through Abstention](https://mlsanity.com/paper/2102.00451/) (2021)
- [Beyond Disagreement-based Agnostic Active Learning](https://mlsanity.com/paper/1407.2657/) (2014)
- [Efficient and Parsimonious Agnostic Active Learning](https://mlsanity.com/paper/1506.08669/) (2015)
- [Fast classification rates without standard margin assumptions](https://mlsanity.com/paper/1910.12756/) (2019)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [Adaptivity to Noise Parameters in Nonparametric Active Learning](https://mlsanity.com/paper/1703.05841/) (2017)
- [Nuances in Margin Conditions Determine Gains in Active Learning](https://mlsanity.com/paper/2110.08418/) (2021)

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

- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Predictor-Rejector Multi-Class Abstention: Theoretical Analysis and Algorithms](https://mlsanity.com/paper/2310.14772/) (2023)
- [Active Learning with Neural Networks: Insights from Nonparametric Statistics](https://mlsanity.com/paper/2210.08367/) (2022)
- [Selective Sampling and Imitation Learning via Online Regression](https://mlsanity.com/paper/2307.04998/) (2023)
- [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)
- [Bayesian Active Learning for Semantic Segmentation](https://mlsanity.com/paper/2408.01694/) (2024)
- [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)
- [System-Aware Unlearning Algorithms: Use Lesser, Forget Faster](https://mlsanity.com/paper/2506.06073/) (2025)
- [Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits](https://mlsanity.com/paper/2602.09456/) (2026)
- [Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design](https://mlsanity.com/paper/2506.09508/) (2025)
- [Towards Multimodal Active Learning: Efficient Learning with Limited Paired Data](https://mlsanity.com/paper/2510.03247/) (2025)
- [Closing the Reflection Gap: A Free Calibration Bonus for Agentic RL](https://mlsanity.com/paper/2606.14211/) (2026)
- [Learning to Help in Multi-Class Settings](https://mlsanity.com/paper/2501.13810/) (2025)
- [Towards Fundamental Limits for Active Multi-distribution Learning](https://mlsanity.com/paper/2506.17607/) (2025)
- [Online Finetuning Decision Transformers with Pure RL Gradients](https://mlsanity.com/paper/2601.00167/) (2026)
- [Thompson Sampling in Online RLHF with General Function Approximation](https://mlsanity.com/paper/2505.23927/) (2025)
- [Active Learning via Regression Beyond Realizability](https://mlsanity.com/paper/2506.00316/) (2025)
- [AbstainGNN: Teaching Graph Neural Networks to Abstain for Graph Classification](https://mlsanity.com/paper/2605.30786/) (2026)
- [Active Learning with Foundation Model Priors: Efficient Learning under Class Imbalance](https://mlsanity.com/paper/2606.07630/) (2026)
- [Information Design Against Gaming and Learning Adversaries](https://mlsanity.com/paper/2609.31643/) (2026)

## Abstract (arXiv)

The goal of active learning is to achieve the same accuracy achievable by passive learning, while using much fewer labels. Exponential savings in terms of label complexity have been proved in very special cases, but fundamental lower bounds show that such improvements are impossible in general. This suggests a need to explore alternative goals for active learning. Learning with abstention is one such alternative. In this setting, the active learning algorithm may abstain from prediction and incur an error that is marginally smaller than random guessing. We develop the first computationally efficient active learning algorithm with abstention. Our algorithm provably achieves mathsfpolylog(frac1varepsilon) label complexity, without any low noise conditions. Such performance guarantee reduces the label complexity by an exponential factor, relative to passive learning and active learning that is not allowed to abstain. Furthermore, our algorithm is guaranteed to only abstain on hard examples (where the true label distribution is close to a fair coin), a novel property we term proper abstention that also leads to a host of other desirable characteristics (e.g., recovering minimax guarantees in the standard setting, and avoiding the undesirable "noise-seeking" behavior often seen in active learning). We also provide novel extensions of our algorithm that achieve constant label complexity and deal with model misspecification.