# Low-Regret Active learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 56 references that are in the map.
- First posted on arXiv 6 Apr 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [A Survey of Deep Active Learning](https://mlsanity.com/paper/2009.00236/) (2020)
- [BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning](https://mlsanity.com/paper/1906.08158/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Variational Adversarial Active Learning](https://mlsanity.com/paper/1904.00370/) (2019)
- [Adversarial Active Learning for Deep Networks: a Margin Based Approach](https://mlsanity.com/paper/1802.09841/) (2018)
- [Discriminative Active Learning](https://mlsanity.com/paper/1907.06347/) (2019)
- [Provable Filter Pruning for Efficient Neural Networks](https://mlsanity.com/paper/1911.07412/) (2019)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [End-to-end Training for Whole Image Breast Cancer Diagnosis using An All Convolutional Design](https://mlsanity.com/paper/1711.05775/) (2017)
- [Deep Active Learning over the Long Tail](https://mlsanity.com/paper/1711.00941/) (2017)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds](https://mlsanity.com/paper/1804.05345/) (2018)
- [Optimal learning with Bernstein Online Aggregation](https://mlsanity.com/paper/1404.1356/) (2014)
- [Tracking the Best Expert in Non-stationary Stochastic Environments](https://mlsanity.com/paper/1712.00578/) (2017)
- [The Many Faces of Exponential Weights in Online Learning](https://mlsanity.com/paper/1802.07543/) (2018)
- [Minimax Active Learning](https://mlsanity.com/paper/2012.10467/) (2020)
- [Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewards](https://mlsanity.com/paper/2004.06248/) (2020)
- [Accelerating Optimization via Adaptive Prediction](https://mlsanity.com/paper/1509.05760/) (2015)
- [Dying Experts: Efficient Algorithms with Optimal Regret Bounds](https://mlsanity.com/paper/1910.13521/) (2019)

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

- [Stochastic Batch Acquisition: A Simple Baseline for Deep Active Learning](https://mlsanity.com/paper/2106.12059/) (2021)
- [Your Data, My Model: Learning Who Really Helps in Federated Learning](https://mlsanity.com/paper/2409.02064/) (2024)
- [Efficient Data Selection for Training Genomic Perturbation Models](https://mlsanity.com/paper/2503.14571/) (2025)

## Abstract (arXiv)

We develop an online learning algorithm for identifying unlabeled data points that are most informative for training (i.e., active learning). By formulating the active learning problem as the prediction with sleeping experts problem, we provide a regret minimization framework for identifying relevant data with respect to any given definition of informativeness. Motivated by the successes of ensembles in active learning, we define regret with respect to an omnipotent algorithm that has access to an infinity large ensemble. At the core of our work is an efficient algorithm for sleeping experts that is tailored to achieve low regret on easy instances while remaining resilient to adversarial ones. Low regret implies that we can be provably competitive with an ensemble method without the computational burden of having to train an ensemble. This stands in contrast to state-of-the-art active learning methods that are overwhelmingly based on greedy selection, and hence cannot ensure good performance across problem instances with high amounts of noise. We present empirical results demonstrating that our method (i) instantiated with an informativeness measure consistently outperforms its greedy counterpart and (ii) reliably outperforms uniform sampling on real-world scenarios.