Research map / Optimization / Optimizers
On the Convergence of Loss and Uncertainty-based Active Learning Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives convergence rates for SGD with loss- or uncertainty-based sampling (active learning / data subset selection) and proposes Adaptive-Weight Sampling (AWS), which combines sampling with a stochastic Polyak step size in expectation.
Problem
Convergence rates and expected sample sizes for SGD when training samples are selected by their loss or uncertainty, as used in active learning and data subset selection, where existing guarantees are limited.
Approach
Treat Bernoulli-sampled SGD as SGD on an equivalent loss (integral of the sampling probability of the loss), yielding convergence rates for loss-based sampling; and propose AWS, which reweights updates by 1/pi so the step size matches the stochastic Polyak step size in expectation, giving O(1/n) rates for smooth convex losses.
Key results
- AWS-PA (Polyak step size with absolute-error loss sampling) converges faster than constant-step loss-based sampling across the tested datasets.
- Loss-based sampling converges faster than random sampling on five of the six datasets.
- Sampling based on a Random Forest estimate of absolute error loss performs similarly to sampling with the true loss on all datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AWS-PA instead of constant-step loss-based sampling | Logistic regression · Mushroom, MNIST 3 vs 5, Parkinsons, Splice, Tictactoe, and Credit | average progressive loss | Helped |
| Use constant-step loss-based sampling instead of random sampling | Logistic regression · Five of the six evaluated datasets | average progressive loss | Helped |
| Use estimated rather than true absolute error loss for AWS-PA sampling | AWS-PA · Mushroom, MNIST 3 vs 5, Parkinsons, Splice, Tictactoe, and Credit | average progressive loss | No clear effect |
Limitations
- Theoretical loss estimator is assumed unbiased and noiseless; bias and noise not analyzed theoretically.
- Experiments limited to logistic regression with single-epoch training; no neural networks.
- Tightness of convergence rates for constant-weight sampling is an open problem.
Experimental setup
Datasets: mushrooms (RBF-kernel modified) MNIST 3 vs 5 parkinsons splice tictactoe credit
Benchmarks: mushrooms MNIST 3 vs 5 parkinsons splice tictactoe credit
Metrics: progressive validation average cross-entropy loss data sampling rate
Baselines: random sampling loss-based sampling with constant step size loss-based sampling with absolute error loss
Builds on: stochastic Polyak step size equivalent loss framework perceptron algorithm margin-based uncertainty sampling
Closest papers by meaning
- Starting Small - Learning with Adaptive Sample Sizes (ICML 2016 · similarity 0.89)
- Adaptive Sampling for SGD by Exploiting Side Information (ICML 2016 · similarity 0.89)
- Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss (NeurIPS 2024 · similarity 0.86)
- Gradient Descent Converges Arbitrarily Fast for Logistic Regression via Large and Adaptive Stepsizes (ICML 2025 · similarity 0.86)
- Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.86)
- Generalization Analysis of Stochastic Weight Averaging with General Sampling (ICML 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.