# Accelerating Stochastic Gradient Descent For Least Squares Regression

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Apr 2017.

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

- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize](https://mlsanity.com/paper/2106.01257/) (2021)
- [On the Last Iterate Convergence of Momentum Methods](https://mlsanity.com/paper/2102.07002/) (2021)
- [Accelerated SGD for Non-Strongly-Convex Least Squares](https://mlsanity.com/paper/2203.01744/) (2022)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Flatter, faster: scaling momentum for optimal speedup of SGD](https://mlsanity.com/paper/2210.16400/) (2022)
- [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)
- [COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization](https://mlsanity.com/paper/2109.03207/) (2021)
- [Policy Search using Dynamic Mirror Descent MPC for Model Free Off Policy RL](https://mlsanity.com/paper/2110.12239/) (2021)
- [Joint Sampling and Optimisation for Inverse Rendering](https://mlsanity.com/paper/2309.15676/) (2023)
- [Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration](https://mlsanity.com/paper/2605.18609/) (2026)

## Abstract (arXiv)

There is widespread sentiment that it is not possible to effectively utilize fast gradient methods (e.g. Nesterov's acceleration, conjugate gradient, heavy ball) for the purposes of stochastic optimization due to their instability and error accumulation, a notion made precise in d'Aspremont 2008 and Devolder, Glineur, and Nesterov 2014. This work considers these issues for the special case of stochastic approximation for the least squares regression problem, and our main result refutes the conventional wisdom by showing that acceleration can be made robust to statistical errors. In particular, this work introduces an accelerated stochastic gradient method that provably achieves the minimax optimal statistical risk faster than stochastic gradient descent. Critical to the analysis is a sharp characterization of accelerated stochastic gradient descent as a stochastic process. We hope this characterization gives insights towards the broader question of designing simple and effective accelerated stochastic methods for more general convex and non-convex optimization problems.