mlsanityData to 14 Oct 2026

Accelerated SGD for Non-Strongly-Convex Least Squares

arXiv 2203.01744 ↗First posted 3 Mar 2022cs.LG math.OC stat.MLcited by 9

Not on the map. Why?

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.

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

20 of 53 references.

References · 20

  1. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  2. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  3. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  4. 2016Katyusha: The First Direct Acceleration of Stochastic Gradient Methodscited by 135
  5. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  6. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  7. 2014Linear Coupling: An Ultimate Unification of Gradient and Mirror Descentcited by 58
  8. 2016Stochastic Heavy Ballcited by 42
  9. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 42
  10. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  11. 2015From Averaging to Acceleration, There is Only a Step-sizecited by 24
  12. 2016On the Influence of Momentum Acceleration on Online Learningcited by 24
8 more
  1. 2019Memory-Sample Tradeoffs for Linear Regression with Small Errorcited by 22
  2. 2015Un-regularizing: approximate proximal point and faster stochastic algorithms for empirical risk minimizationcited by 21
  3. 2016Optimal Black-Box Reductions Between Optimization Objectivescited by 21
  4. 2021Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Modelscited by 16
  5. 2019Space lower bounds for linear prediction in the streaming modelcited by 14
  6. 2017Accelerating Stochastic Gradient Descent For Least Squares Regressioncited by 13
  7. 2013An Accelerated Randomized Kaczmarz Algorithmcited by 12
  8. 2017Stochastic Composite Least-Squares Regression with convergence rate O(1/n)cited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 1; 2023: 0; 2024: 2; 2025: 4; 2026: 2.

9 papers.

  1. 2026A Defense of the Quadratic Modelcited by 14
  2. 2022A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momentacited by 11
  3. 2024The Optimality of (Accelerated) SGD for High-Dimensional Quadratic Optimizationcited by 8
  4. 2026Power-Law Spectrum of the Random Feature Modelcited by 4
  5. 2025On the Effectiveness of the z-Transform Method in Quadratic Optimizationcited by 3
  6. 2024SGD with memory: fundamental properties and stochastic accelerationcited by 2
  7. 2025Increasing Batch Size Improves Convergence of Stochastic Gradient Descent with Momentumcited by 2
  8. 2025Understanding SGD with Exponential Moving Average: A Case Study in Linear Regressioncited by 1
  9. 2025Corner Gradient Descentcited by 1