# Accelerated SGD for Non-Strongly-Convex Least Squares

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 53 references that are in the map.
- First posted on arXiv 3 Mar 2022.

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

- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning](https://mlsanity.com/paper/1712.06559/) (2017)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Benign Overfitting of Constant-Stepsize SGD for Linear Regression](https://mlsanity.com/paper/2103.12692/) (2021)
- [Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent](https://mlsanity.com/paper/1407.1537/) (2014)
- [Stochastic Heavy Ball](https://mlsanity.com/paper/1609.04228/) (2016)
- [Last iterate convergence of SGD for Least-Squares in the Interpolation regime](https://mlsanity.com/paper/2102.03183/) (2021)
- [Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model](https://mlsanity.com/paper/2006.08212/) (2020)
- [From Averaging to Acceleration, There is Only a Step-size](https://mlsanity.com/paper/1504.01577/) (2015)
- [On the Influence of Momentum Acceleration on Online Learning](https://mlsanity.com/paper/1603.04136/) (2016)
- [Memory-Sample Tradeoffs for Linear Regression with Small Error](https://mlsanity.com/paper/1904.08544/) (2019)
- [Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimization](https://mlsanity.com/paper/1506.07512/) (2015)
- [Optimal Black-Box Reductions Between Optimization Objectives](https://mlsanity.com/paper/1603.05642/) (2016)
- [Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models](https://mlsanity.com/paper/2106.03696/) (2021)
- [Space lower bounds for linear prediction in the streaming model](https://mlsanity.com/paper/1902.03498/) (2019)
- [Accelerating Stochastic Gradient Descent For Least Squares Regression](https://mlsanity.com/paper/1704.08227/) (2017)
- [An Accelerated Randomized Kaczmarz Algorithm](https://mlsanity.com/paper/1310.2887/) (2013)
- [Stochastic Composite Least-Squares Regression with convergence rate O(1/n)](https://mlsanity.com/paper/1702.06429/) (2017)

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

- [A Defense of the Quadratic Model](https://mlsanity.com/paper/2607.21716/) (2026)
- [A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momenta](https://mlsanity.com/paper/2206.11124/) (2022)
- [The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimization](https://mlsanity.com/paper/2409.09745/) (2024)
- [Power-Law Spectrum of the Random Feature Model](https://mlsanity.com/paper/2603.14578/) (2026)
- [On the Effectiveness of the z-Transform Method in Quadratic Optimization](https://mlsanity.com/paper/2507.03404/) (2025)
- [SGD with memory: fundamental properties and stochastic acceleration](https://mlsanity.com/paper/2410.04228/) (2024)
- [Increasing Batch Size Improves Convergence of Stochastic Gradient Descent with Momentum](https://mlsanity.com/paper/2501.08883/) (2025)
- [Understanding SGD with Exponential Moving Average: A Case Study in Linear Regression](https://mlsanity.com/paper/2502.14123/) (2025)
- [Corner Gradient Descent](https://mlsanity.com/paper/2504.12519/) (2025)

## Abstract (arXiv)

We consider stochastic approximation for the least squares regression problem in the non-strongly convex setting. We present the first practical algorithm that achieves the optimal prediction error rates in terms of dependence on the noise of the problem, as O(d/t) while accelerating the forgetting of the initial conditions to O(d/t2). Our new algorithm is based on a simple modification of the accelerated gradient descent. We provide convergence results for both the averaged and the last iterate of the algorithm. In order to describe the tightness of these new bounds, we present a matching lower bound in the noiseless setting and thus show the optimality of our algorithm.