# On the Convergence of Loss and Uncertainty-based Active Learning Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 21 Dec 2023.

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

- [An Empirical Study of Example Forgetting during Deep Neural Network Learning](https://mlsanity.com/paper/1812.05159/) (2018)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Deep Learning on a Data Diet: Finding Important Examples Early in Training](https://mlsanity.com/paper/2107.07075/) (2021)
- [Beyond neural scaling laws: beating power law scaling via data pruning](https://mlsanity.com/paper/2206.14486/) (2022)
- [BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning](https://mlsanity.com/paper/1906.08158/) (2019)
- [Selection via Proxy: Efficient Data Selection for Deep Learning](https://mlsanity.com/paper/1906.11829/) (2019)
- [Learning Loss for Active Learning](https://mlsanity.com/paper/1905.03677/) (2019)
- [Prioritized Training on Points that are Learnable, Worth Learning, and Not Yet Learnt](https://mlsanity.com/paper/2206.07137/) (2022)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [DEUP: Direct Epistemic Uncertainty Prediction](https://mlsanity.com/paper/2102.08501/) (2021)
- [A Benchmark and Comparison of Active Learning for Logistic Regression](https://mlsanity.com/paper/1611.08618/) (2016)
- [Active Learning Using Uncertainty Information](https://mlsanity.com/paper/1702.08540/) (2017)
- [Unifying Approaches in Active Learning and Active Sampling via Fisher Information and Information-Theoretic Quantities](https://mlsanity.com/paper/2208.00549/) (2022)
- [Convergence of Uncertainty Sampling for Active Learning](https://mlsanity.com/paper/2110.15784/) (2021)
- [On the Power of Localized Perceptron for Label-Optimal Learning of Halfspaces with Adversarial Noise](https://mlsanity.com/paper/2012.10793/) (2020)
- [Uncertainty Sampling is Preconditioned Stochastic Gradient Descent on Zero-One Loss](https://mlsanity.com/paper/1812.01815/) (2018)
- [Loss Prediction: End-to-End Active Learning Approach For Speech Recognition](https://mlsanity.com/paper/2107.04289/) (2021)

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

- [PICore: Physics-Informed Unsupervised Coreset Selection for Data Efficient Neural Operator Training](https://mlsanity.com/paper/2507.17151/) (2025)

## Abstract (arXiv)

We investigate the convergence rates and data sample sizes required for training a machine learning model using a stochastic gradient descent (SGD) algorithm, where data points are sampled based on either their loss value or uncertainty value. These training methods are particularly relevant for active learning and data subset selection problems. For SGD with a constant step size update, we present convergence results for linear classifiers and linearly separable datasets using squared hinge loss and similar training loss functions. Additionally, we extend our analysis to more general classifiers and datasets, considering a wide range of loss-based sampling strategies and smooth convex training loss functions. We propose a novel algorithm called Adaptive-Weight Sampling (AWS) that utilizes SGD with an adaptive step size that achieves stochastic Polyak's step size in expectation. We establish convergence rate results for AWS for smooth convex training loss functions. Our numerical experiments demonstrate the efficiency of AWS on various datasets by using either exact or estimated loss values.