# Improved Algorithms for Agnostic Pool-based Active Classification

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 38 references that are in the map.
- First posted on arXiv 13 May 2021.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [An Empirical Process Approach to the Union Bound: Practical Algorithms for Combinatorial and Linear Bandits](https://mlsanity.com/paper/2006.11685/) (2020)
- [Beyond Disagreement-based Agnostic Active Learning](https://mlsanity.com/paper/1407.2657/) (2014)
- [Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration](https://mlsanity.com/paper/1706.01081/) (2017)
- [Efficient and Parsimonious Agnostic Active Learning](https://mlsanity.com/paper/1506.08669/) (2015)
- [Uncertainty Sampling is Preconditioned Stochastic Gradient Descent on Zero-One Loss](https://mlsanity.com/paper/1812.01815/) (2018)
- [A New Perspective on Pool-Based Active Classification and False-Discovery Control](https://mlsanity.com/paper/2008.06555/) (2020)

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

- [GALAXY: Graph-based Active Learning at the Extreme](https://mlsanity.com/paper/2202.01402/) (2022)
- [Efficient Active Learning with Abstention](https://mlsanity.com/paper/2204.00043/) (2022)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [Active Learning with Safety Constraints](https://mlsanity.com/paper/2206.11183/) (2022)
- [Fast Rates in Pool-Based Batch Active Learning](https://mlsanity.com/paper/2202.05448/) (2022)
- [Improved Algorithm for Deep Active Learning under Imbalance via Optimal Separation](https://mlsanity.com/paper/2312.09196/) (2023)
- [AHA: Human-Assisted Out-of-Distribution Generalization and Detection](https://mlsanity.com/paper/2410.08000/) (2024)
- [Selective Sampling for Online Best-arm Identification](https://mlsanity.com/paper/2110.14864/) (2021)
- [Promises and Pitfalls of Threshold-based Auto-labeling](https://mlsanity.com/paper/2211.12620/) (2022)
- [SPEED: Experimental Design for Policy Evaluation in Linear Heteroscedastic Bandits](https://mlsanity.com/paper/2301.12357/) (2023)
- [A Competitive Algorithm for Agnostic Active Learning](https://mlsanity.com/paper/2310.18786/) (2023)
- [Fair Active Learning in Low-Data Regimes](https://mlsanity.com/paper/2312.08559/) (2023)
- [Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers](https://mlsanity.com/paper/2111.04915/) (2021)
- [Experimental Design for Active Transductive Inference in Large Language Models](https://mlsanity.com/paper/2404.08846/) (2024)
- [Near-Polynomially Competitive Active Logistic Regression](https://mlsanity.com/paper/2503.05981/) (2025)

## Abstract (arXiv)

We consider active learning for binary classification in the agnostic pool-based setting. The vast majority of works in active learning in the agnostic setting are inspired by the CAL algorithm where each query is uniformly sampled from the disagreement region of the current version space. The sample complexity of such algorithms is described by a quantity known as the disagreement coefficient which captures both the geometry of the hypothesis space as well as the underlying probability space. To date, the disagreement coefficient has been justified by minimax lower bounds only, leaving the door open for superior instance dependent sample complexities. In this work we propose an algorithm that, in contrast to uniform sampling over the disagreement region, solves an experimental design problem to determine a distribution over examples from which to request labels. We show that the new approach achieves sample complexity bounds that are never worse than the best disagreement coefficient-based bounds, but in specific cases can be dramatically smaller. From a practical perspective, the proposed algorithm requires no hyperparameters to tune (e.g., to control the aggressiveness of sampling), and is computationally efficient by means of assuming access to an empirical risk minimization oracle (without any constraints). Empirically, we demonstrate that our algorithm is superior to state of the art agnostic active learning algorithms on image classification datasets.