# Competing with the Empirical Risk Minimizer in a Single Pass

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2014.

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

- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)
- [Optimal variance-reduced stochastic approximation in Banach spaces](https://mlsanity.com/paper/2201.08518/) (2022)
- [Eigencurve: Optimal Learning Rate Schedule for SGD on Quadratic Objectives with Skewed Hessian Spectrums](https://mlsanity.com/paper/2110.14109/) (2021)
- [Anytime Pretraining: Horizon-Free Learning-Rate Schedules with Weight Averaging](https://mlsanity.com/paper/2602.03702/) (2026)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning](https://mlsanity.com/paper/2206.00796/) (2022)
- [Logits are All We Need to Adapt Closed Models](https://mlsanity.com/paper/2502.06806/) (2025)
- [Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviation](https://mlsanity.com/paper/2301.03125/) (2023)
- [Gaussian Process Inference Using Mini-batch Stochastic Gradient Descent: Convergence Guarantees and Empirical Benefits](https://mlsanity.com/paper/2111.10461/) (2021)
- [Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach](https://mlsanity.com/paper/2106.05445/) (2021)
- [Policy Learning and Evaluation with Randomized Quasi-Monte Carlo](https://mlsanity.com/paper/2202.07808/) (2022)
- [Cyclic and Randomized Stepsizes Invoke Heavier Tails in SGD than Constant Stepsize](https://mlsanity.com/paper/2302.05516/) (2023)
- [An Effective Dynamic Gradient Calibration Method for Continual Learning](https://mlsanity.com/paper/2407.20956/) (2024)
- [On Interpolation Formulas Describing Neural Network Generalization](https://mlsanity.com/paper/2603.13872/) (2026)
- [Active Learning for Stochastic Contextual Linear Bandits](https://mlsanity.com/paper/2605.24803/) (2026)
- [COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization](https://mlsanity.com/paper/2109.03207/) (2021)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [FIRAL: An Active Learning Algorithm for Multinomial Logistic Regression](https://mlsanity.com/paper/2409.07379/) (2024)
- [Convergence Analysis of alpha-SVRG under Strong Convexity](https://mlsanity.com/paper/2503.12454/) (2025)
- [Accelerating Single-Pass SGD for Generalized Linear Prediction](https://mlsanity.com/paper/2603.01951/) (2026)

## Abstract (arXiv)

In many estimation problems, e.g. linear and logistic regression, we wish to minimize an unknown objective given only unbiased samples of the objective function. Furthermore, we aim to achieve this using as few samples as possible. In the absence of computational constraints, the minimizer of a sample average of observed data -- commonly referred to as either the empirical risk minimizer (ERM) or the M-estimator -- is widely regarded as the estimation strategy of choice due to its desirable statistical convergence properties. Our goal in this work is to perform as well as the ERM, on every problem, while minimizing the use of computational resources such as running time and space usage. We provide a simple streaming algorithm which, under standard regularity assumptions on the underlying problem, enjoys the following properties: * The algorithm can be implemented in linear time with a single pass of the observed data, using space linear in the size of a single sample. * The algorithm achieves the same statistical rate of convergence as the empirical risk minimizer on every problem, even considering constant factors. * The algorithm's performance depends on the initial error at a rate that decreases super-polynomially. * The algorithm is easily parallelizable. Moreover, we quantify the (finite-sample) rate at which the algorithm becomes competitive with the ERM.