# Active Labeling: Streaming Stochastic Gradients

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 86 references that are in the map.
- First posted on arXiv 26 May 2022.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Snorkel: Rapid Training Data Creation with Weak Supervision](https://mlsanity.com/paper/1711.10160/) (2017)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Preference-based Online Learning with Dueling Bandits: A Survey](https://mlsanity.com/paper/1807.11398/) (2018)
- [Looking for the Devil in the Details: Learning Trilinear Attention Sampling Network for Fine-grained Image Recognition](https://mlsanity.com/paper/1903.06150/) (2019)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes](https://mlsanity.com/paper/1805.10074/) (2018)
- [The Unreasonable Effectiveness of Noisy Data for Fine-Grained Recognition](https://mlsanity.com/paper/1511.06789/) (2015)
- [A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings](https://mlsanity.com/paper/2002.05424/) (2020)
- [Structured Prediction with Partial Labelling through the Infimum Loss](https://mlsanity.com/paper/2003.00920/) (2020)
- [Dynamic Pricing with Finitely Many Unknown Valuations](https://mlsanity.com/paper/1807.03288/) (2018)
- [Efficient Algorithms for Learning from Coarse Labels](https://mlsanity.com/paper/2108.09805/) (2021)
- [Overcoming the curse of dimensionality with Laplacian regularization in semi-supervised learning](https://mlsanity.com/paper/2009.04324/) (2020)
- [Exponential convergence of testing error for stochastic gradient methods](https://mlsanity.com/paper/1712.04755/) (2017)
- [Fast rates in structured prediction](https://mlsanity.com/paper/2102.00760/) (2021)
- [Sorted Top-k in Rounds](https://mlsanity.com/paper/1906.05208/) (2019)
- [Efficient Primal-Dual Algorithms for Large-Scale Multiclass Classification](https://mlsanity.com/paper/1902.03755/) (2019)

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

- [Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Need](https://mlsanity.com/paper/2303.15256/) (2023)
- [Mode Estimation with Partial Feedback](https://mlsanity.com/paper/2402.13079/) (2024)
- [From Weakly Supervised Learning to Active Learning](https://mlsanity.com/paper/2209.11629/) (2022)

## Abstract (arXiv)

The workhorse of machine learning is stochastic gradient descent. To access stochastic gradients, it is common to consider iteratively input/output pairs of a training dataset. Interestingly, it appears that one does not need full supervision to access stochastic gradients, which is the main motivation of this paper. After formalizing the "active labeling" problem, which focuses on active learning with partial supervision, we provide a streaming technique that provably minimizes the ratio of generalization error over the number of samples. We illustrate our technique in depth for robust regression.