mlsanityData to 14 Oct 2026

Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

arXiv 2507.11274 ↗First posted 15 Jul 2025cs.LG math.OC stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

We study population convergence guarantees of stochastic gradient descent (SGD) for smooth convex objectives in the interpolation regime, where the noise at optimum is zero or near zero. The behavior of the last iterate of SGD in this setting -- particularly with large (constant) stepsizes -- has received growing attention in recent years due to implications for the training of over-parameterized models, as well as to analyzing forgetting in continual learning and to understanding the convergence of the randomized Kaczmarz method for solving linear systems. We establish that after T steps of SGD on β-smooth convex loss functions with stepsize 0 < η < 2/β, the last iterate exhibits expected excess risk widetildeO(frac1η (2-β η) T1-βη/2 + fracη(2-βη)2 Tβη/2 σ_star2), where σ_star2 denotes the variance of the stochastic gradients at the optimum. In particular, for a well-tuned stepsize we obtain a near optimal widetildeO(1/T + σ_star/√T) rate for the last iterate, extending the results of Varre et al. (2021) beyond least squares regression; and when σ_star=0 we obtain a rate of smashO(1/√ T) with η=1/β, improving upon the best-known smashO(T-1/4) rate recently established by Evron et al. (2025) in the special case of realizable linear regression.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 37 of its 63 references that are in the map. First posted on arXiv 15 Jul 2025.

Builds on

37 of 63 references.

References · 37

  1. 2017The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learningcited by 150
  2. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  3. 2013Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithmcited by 133
  4. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  5. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  6. 2020A Theoretical Analysis of Catastrophic Forgetting through the NTK Overlap Matrixcited by 103
  7. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  8. 2022How catastrophic can catastrophic forgetting be in linear regression?cited by 81
  9. 2023Theory on Forgetting and Generalization of Continual Learningcited by 72
  10. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 68
  11. 2019How Good is SGD with Random Shuffling?cited by 64
  12. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
25 more
  1. 2020Closing the convergence gap of SGD without replacementcited by 57
  2. 2021Last iterate convergence of SGD for Least-Squares in the Interpolation regimecited by 42
  3. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  4. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 38
  5. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
  6. 2023The Ideal Continual Learner: An Agent That Never Forgetscited by 35
  7. 2023Continual Learning in Linear Classification on Separable Datacited by 34
  8. 2022Analysis of Catastrophic Forgetting for Random Orthogonal Transformation Tasks in the Overparameterized Regimecited by 29
  9. 2024The Joint Effect of Task Similarity and Overparameterization on Catastrophic Forgetting -- An Analytical Modelcited by 26
  10. 2023Exact convergence rate of the last iterate in subgradient methodscited by 25
  11. 2023Fixed Design Analysis of Regularization-Based Continual Learningcited by 24
  12. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 22
  13. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  14. 2022Challenging Common Assumptions about Catastrophic Forgettingcited by 20
  15. 2024Disentangling and Mitigating the Impact of Task Similarity for Continual Learningcited by 19
  16. 2020Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is Falsecited by 16
  17. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 12
  18. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 11
  19. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  20. 2024Continual Learning in the Presence of Repetitioncited by 10
  21. 2025Convergence and Implicit Bias of Gradient Descent on Continual Linear Classificationcited by 9
  22. 2025Optimal Rates in Continual Linear Regression via Increasing Regularizationcited by 8
  23. 2023Lower Generalization Bounds for GD and SGD in Smooth Stochastic Convex Optimizationcited by 6
  24. 2023Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Boundscited by 6
  25. 2025Bias-Optimal Bounds for SGD: A Computer-Aided Lyapunov Analysiscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 11.

12 papers.

  1. 2025Flat Minima and Generalization: Insights from Stochastic Convex Optimizationcited by 4
  2. 2026Gradient Descent's Last Iterate is Often (slightly) Suboptimalcited by 4
  3. 2026Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Sizecited by 2
  4. 2026Small Gradient Norm Regret for Online Convex Optimizationcited by 0
  5. 2026Convergence Rate of the Last Iterate of Stochastic Proximal Algorithmscited by 0
  6. 2026Perfect Parallelization in Mini-Batch SGD with Classical Momentum Accelerationcited by 0
  7. 2026Dangerous Liaisons of Convex Learning and Non-Affine Aggregationcited by 0
  8. 2026How AI settled the complexity of the oldest SGD algorithmcited by 0
  9. 2026Convergence of Continual Learning in Homogeneous Deep Networkscited by 0
  10. 2026Stochastic gradient descent with initial regularizationcited by 0
  11. 2026Probabilistic Multi-Source Data Selection via Learnable Categorical Priors: Variance Reduction and Guaranteed Derandomizationcited by 0
  12. 2026Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descentcited by 0