# A Competitive Algorithm for Agnostic Active Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 29 references that are in the map.
- First posted on arXiv 28 Oct 2023.

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

- [Minimax Analysis of Active Learning](https://mlsanity.com/paper/1410.0996/) (2014)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [Noisy (Binary) Searching: Simple, Fast and Correct](https://mlsanity.com/paper/2107.05753/) (2021)

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

- [Towards Fundamental Limits for Active Multi-distribution Learning](https://mlsanity.com/paper/2506.17607/) (2025)
- [Near-Polynomially Competitive Active Logistic Regression](https://mlsanity.com/paper/2503.05981/) (2025)

## Abstract (arXiv)

For some hypothesis classes and input distributions, active agnostic learning needs exponentially fewer samples than passive learning; for other classes and distributions, it offers little to no improvement. The most popular algorithms for agnostic active learning express their performance in terms of a parameter called the disagreement coefficient, but it is known that these algorithms are inefficient on some inputs. We take a different approach to agnostic active learning, getting an algorithm that is competitive with the optimal algorithm for any binary hypothesis class H and distribution DX over X. In particular, if any algorithm can use m^* queries to get O(η) error, then our algorithm uses O(m^* log |H|) queries to get O(η) error. Our algorithm lies in the vein of the splitting-based approach of Dasgupta [2004], which gets a similar result for the realizable (η = 0) setting. We also show that it is NP-hard to do better than our algorithm's O(log |H|) overhead in general.