# Minimax Analysis of Active Learning

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

## Key facts

- Cited by 61 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2014.

## Built on by (most cited first, 30 of 61)

- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Towards a Unified Information-Theoretic Framework for Generalization](https://mlsanity.com/paper/2111.05275/) (2021)
- [Active learning for data streams: a survey](https://mlsanity.com/paper/2302.08893/) (2023)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Realizable Learning is All You Need](https://mlsanity.com/paper/2111.04746/) (2021)
- [Exponential Savings in Agnostic Active Learning through Abstention](https://mlsanity.com/paper/2102.00451/) (2021)
- [Streaming Active Learning with Deep Neural Networks](https://mlsanity.com/paper/2303.02535/) (2023)
- [Understanding the Eluder Dimension](https://mlsanity.com/paper/2104.06970/) (2021)
- [Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension](https://mlsanity.com/paper/2302.13849/) (2023)
- [Adversarially Robust Learning: A Generic Minimax Optimal Learner and Characterization](https://mlsanity.com/paper/2209.07369/) (2022)
- [Robust learning under clean-label attack](https://mlsanity.com/paper/2103.00671/) (2021)
- [Multiclass Learnability Beyond the PAC Framework: Universal Rates and Partial Concept Classes](https://mlsanity.com/paper/2210.02297/) (2022)
- [Teaching an Active Learner with Contrastive Examples](https://mlsanity.com/paper/2110.14888/) (2021)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [The One-Inclusion Graph Algorithm is not Always Optimal](https://mlsanity.com/paper/2212.09270/) (2022)
- [Adversarial Resilience in Sequential Prediction via Abstention](https://mlsanity.com/paper/2306.13119/) (2023)
- [Nuances in Margin Conditions Determine Gains in Active Learning](https://mlsanity.com/paper/2110.08418/) (2021)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back](https://mlsanity.com/paper/2511.12659/) (2025)
- [All models are wrong, some are useful: Model Selection with Limited Labels](https://mlsanity.com/paper/2410.13609/) (2024)
- [Agnostic Multi-Group Active Learning](https://mlsanity.com/paper/2306.01922/) (2023)
- [The Real Price of Bandit Information in Multiclass Classification](https://mlsanity.com/paper/2405.10027/) (2024)
- [Poisson Reweighted Laplacian Uncertainty Sampling for Graph-based Active Learning](https://mlsanity.com/paper/2210.15786/) (2022)
- [Active Learning of General Halfspaces: Label Queries vs Membership Queries](https://mlsanity.com/paper/2501.00508/) (2024)
- [Greedy Approximation Algorithms for Active Sequential Hypothesis Testing](https://mlsanity.com/paper/2103.04250/) (2021)
- [Understanding Uncertainty Sampling via Equivalent Loss](https://mlsanity.com/paper/2307.02719/) (2023)
- [Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise](https://mlsanity.com/paper/2307.08438/) (2023)
- [Active Sequential Two-Sample Testing](https://mlsanity.com/paper/2301.12616/) (2023)
- [Active Learning with Simple Questions](https://mlsanity.com/paper/2405.07937/) (2024)
- [Do PAC-Learners Learn the Marginal Distribution?](https://mlsanity.com/paper/2302.06285/) (2023)

## Abstract (arXiv)

This work establishes distribution-free upper and lower bounds on the minimax label complexity of active learning with general hypothesis classes, under various noise models. The results reveal a number of surprising facts. In particular, under the noise model of Tsybakov (2004), the minimax label complexity of active learning with a VC class is always asymptotically smaller than that of passive learning, and is typically significantly smaller than the best previously-published upper bounds in the active learning literature. In high-noise regimes, it turns out that all active learning problems of a given VC dimension have roughly the same minimax label complexity, which contrasts with well-known results for bounded noise. In low-noise regimes, we find that the label complexity is well-characterized by a simple combinatorial complexity measure we call the star number. Interestingly, we find that almost all of the complexity measures previously explored in the active learning literature have worst-case values exactly equal to the star number. We also propose new active learning strategies that nearly achieve these minimax label complexities.