# Fast Rates in Pool-Based Batch Active Learning

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 66 references that are in the map.
- First posted on arXiv 11 Feb 2022.

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

- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning](https://mlsanity.com/paper/1906.08158/) (2019)
- [GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning](https://mlsanity.com/paper/2012.10630/) (2020)
- [Batch Active Learning at Scale](https://mlsanity.com/paper/2107.14263/) (2021)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Deep Active Learning: Unified and Principled Method for Query and Training](https://mlsanity.com/paper/1911.09162/) (2019)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Diverse mini-batch Active Learning](https://mlsanity.com/paper/1901.05954/) (2019)
- [Task-Aware Variational Adversarial Active Learning](https://mlsanity.com/paper/2002.04709/) (2020)
- [SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios](https://mlsanity.com/paper/2107.00717/) (2021)
- [Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective](https://mlsanity.com/paper/2010.03104/) (2020)
- [Relative Loss Bounds for On-line Density Estimation with the Exponential Family of Distributions](https://mlsanity.com/paper/1301.6677/) (2013)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Data Shapley Valuation for Efficient Batch Active Learning](https://mlsanity.com/paper/2104.08312/) (2021)
- [Convergence Rates of Active Learning for Maximum Likelihood Estimation](https://mlsanity.com/paper/1506.02348/) (2015)
- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Neural Active Learning with Performance Guarantees](https://mlsanity.com/paper/2106.03243/) (2021)
- [Improved Algorithms for Efficient Active Learning Halfspaces with Massart and Tsybakov noise](https://mlsanity.com/paper/2102.05312/) (2021)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [Chernoff Sampling for Active Testing and Extension to Active Regression](https://mlsanity.com/paper/2012.08073/) (2020)
- [Data Summarization via Bilevel Optimization](https://mlsanity.com/paper/2109.12534/) (2021)
- [Near-optimal Bayesian Active Learning with Correlated and Noisy Tests](https://mlsanity.com/paper/1605.07334/) (2016)
- [Diameter-Based Active Learning](https://mlsanity.com/paper/1702.08553/) (2017)
- [A Short Note on the Relationship of Information Gain and Eluder Dimension](https://mlsanity.com/paper/2107.02377/) (2021)
- [Selective Sampling for Online Best-arm Identification](https://mlsanity.com/paper/2110.14864/) (2021)

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

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Active Prompting with Chain-of-Thought for Large Language Models](https://mlsanity.com/paper/2302.12246/) (2023)
- [CoAnnotating: Uncertainty-Guided Work Allocation between Human and Large Language Models for Data Annotation](https://mlsanity.com/paper/2310.15638/) (2023)
- [Fairness-guided Few-shot Prompting for Large Language Models](https://mlsanity.com/paper/2303.13217/) (2023)
- [Online Iterative Reinforcement Learning from Human Feedback with General Preference Model](https://mlsanity.com/paper/2402.07314/) (2024)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Evolving Knowledge Distillation with Large Language Models and Active Learning](https://mlsanity.com/paper/2403.06414/) (2024)
- [Distributional Machine Unlearning via Selective Data Removal](https://mlsanity.com/paper/2507.15112/) (2025)
- [Primal Dual Continual Learning: Balancing Stability and Plasticity through Adaptive Memory Allocation](https://mlsanity.com/paper/2310.00154/) (2023)
- [System-Aware Unlearning Algorithms: Use Lesser, Forget Faster](https://mlsanity.com/paper/2506.06073/) (2025)
- [Daunce: Data Attribution through Uncertainty Estimation](https://mlsanity.com/paper/2505.23223/) (2025)
- [ActiveCQ: Active Estimation of Causal Quantities](https://mlsanity.com/paper/2509.24293/) (2025)
- [Active Learning for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2605.24803/) (2026)
- [The Power of Adaptation: Boosting In-Context Learning through Adaptive Prompting](https://mlsanity.com/paper/2412.17891/) (2024)
- [Pool-based Active Learning as Noisy Lossy Compression: Characterizing Label Complexity via Finite Blocklength Analysis](https://mlsanity.com/paper/2602.05333/) (2026)

## Abstract (arXiv)

We consider a batch active learning scenario where the learner adaptively issues batches of points to a labeling oracle. Sampling labels in batches is highly desirable in practice due to the smaller number of interactive rounds with the labeling oracle (often human beings). However, batch active learning typically pays the price of a reduced adaptivity, leading to suboptimal results. In this paper we propose a solution which requires a careful trade off between the informativeness of the queried points and their diversity. We theoretically investigate batch active learning in the practically relevant scenario where the unlabeled pool of data is available beforehand (em pool-based active learning). We analyze a novel stage-wise greedy algorithm and show that, as a function of the label complexity, the excess risk of this algorithm matches the known minimax rates in standard statistical learning settings. Our results also exhibit a mild dependence on the batch size. These are the first theoretical results that employ careful trade offs between informativeness and diversity to rigorously quantify the statistical performance of batch active learning in the pool-based scenario.