mlsanityData to 7 Oct 2026

Last iterate convergence of SGD for Least-Squares in the Interpolation regime

arXiv 2102.03183 ↗First posted 5 Feb 2021cs.LG math.OC stat.MLcited by 41

Not on the map. Why?

Abstract (arXiv)

Motivated by the recent successes of neural networks that have the ability to fit the data perfectly and generalize well, we study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs langle θ_* , φ(X) rangle = Y, where φ(X) stands for a possibly infinite dimensional non-linear feature map. To solve this problem, we consider the estimator given by the last iterate of stochastic gradient descent (SGD) with constant step-size. In this context, our contribution is two fold: (i) from a (stochastic) optimization perspective, we exhibit an archetypal problem where we can show explicitly the convergence of SGD final iterate for a non-strongly convex problem with constant step-size whereas usual results use some form of average and (ii) from a statistical perspective, we give explicit non-asymptotic convergence rates in the over-parameterized setting and leverage a fine-grained parameterization of the problem to exhibit polynomial rates that can be faster than O(1/T). The link with reproducing kernel Hilbert spaces is established.

Key facts. Cited by 41 papers in the map (data through 7 Oct 2026). Builds on 17 of its 36 references that are in the map. First posted on arXiv 5 Feb 2021.

Builds on

17 of 36 references.

References · 17

  1. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  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. 2019Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Ratescited by 119
  5. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 110
  6. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 94
  7. 2018Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passescited by 69
  8. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 67
  9. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  10. 2013Fast Convergence of Stochastic Gradient Descent under a Strong Growth Conditioncited by 54
  11. 2020Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Modelcited by 39
  12. 2018On exponential convergence of SGD in non-convex over-parametrized learningcited by 33
5 more
  1. 2019Fast and Furious Convergence: Stochastic Second Order Methods under Interpolationcited by 18
  2. 2017Accelerating Stochastic Gradient Descent For Least Squares Regressioncited by 13
  3. 2019Kernel Truncated Randomized Ridge Regression: Optimal Rates and Low Noise Accelerationcited by 12
  4. 2017Stochastic Composite Least-Squares Regression with convergence rate O(1/n)cited by 7
  5. 2020Stochastic Gradient Descent in Hilbert Scales: Smoothness, Preconditioning and Earlier Stoppingcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 9; 2023: 5; 2024: 7; 2025: 9; 2026: 6.

41 papers.

Sort:

  1. 2021Implicit Bias of SGD for Diagonal Linear Networks: a Provable Benefit of Stochasticitycited by 107
  2. 2024A Dynamical Model of Neural Scaling Lawscited by 105
  3. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 95
  4. 2022How catastrophic can catastrophic forgetting be in linear regression?cited by 80
  5. 2024Scaling Laws in Linear Regression: Compute, Parameters, and Datacited by 54
  6. 2023From high-dimensional & mean-field dynamics to dimensionless ODEs: A unifying approach to SGD in two-layers networkscited by 42
  7. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 37
  8. 2022The Power and Limitation of Pretraining-Finetuning for Linear Regression under Covariate Shiftcited by 25
  9. 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
  10. 2022Error Scaling Laws for Kernel Classification under Source and Capacity Conditionscited by 17
  11. 2023Stochastic Gradient Descent for Gaussian Processes Done Rightcited by 16
  12. 2022A view of mini-batch SGD via generating functions: conditions of convergence, phase transitions, benefit from negative momentacited by 11
29 more
  1. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 10
  2. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 10
  3. 2022Tight Convergence Rate Bounds for Optimization Under Power Law Spectral Conditionscited by 9
  4. 2022Accelerated SGD for Non-Strongly-Convex Least Squarescited by 9
  5. 2025Optimal Rates in Continual Linear Regression via Increasing Regularizationcited by 8
  6. 2025Improved Scaling Laws in Linear Regression via Data Reusecited by 7
  7. 2026A Defense of the Quadratic Modelcited by 6
  8. 2021On the Double Descent of Random Features Models Trained with SGDcited by 5
  9. 2022Vector-Valued Least-Squares Regression under Output Regularity Assumptionscited by 5
  10. 2023Kernelized Diffusion mapscited by 5
  11. 2026Theory of Optimal Learning Rate Schedules and Scaling Laws for a Random Feature Modelcited by 4
  12. 2024The High Line: Exact Risk and Learning Rate Curves of Stochastic Adaptive Learning Rate Algorithmscited by 3
  13. 2024Stochastic Differential Equations models for Least-Squares Stochastic Gradient Descentcited by 3
  14. 2026Gradient Descent's Last Iterate is Often (slightly) Suboptimalcited by 3
  15. 2024SGD with memory: fundamental properties and stochastic accelerationcited by 2
  16. 2025On the Effectiveness of the z-Transform Method in Quadratic Optimizationcited by 2
  17. 2025Green Federated Learning via Carbon-Aware Client and Time Slot Schedulingcited by 2
  18. 2026Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Sizecited by 2
  19. 2023Statistical Inference for Linear Functionals of Online SGD in High-dimensional Linear Regressioncited by 1
  20. 2025Corner Gradient Descentcited by 1
  21. 2025Breaking the curse of dimensionality for linear rules: optimal predictors over the ellipsoidcited by 1
  22. 2025Statistical Inference for Linear Functionals of Online Least-squares SGD when t gtrsim d1+δcited by 1
  23. 2021Learning Curves for SGD on Structured Featurescited by 0
  24. 2022Local SGD in Overparameterized Linear Regressioncited by 0
  25. 2023Loss Dynamics of Temporal Difference Reinforcement Learningcited by 0
  26. 2024Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolationcited by 0
  27. 2024Derivatives of Stochastic Gradient Descent in parametric optimizationcited by 0
  28. 2026How AI settled the complexity of the oldest SGD algorithmcited by 0
  29. 2026Stochastic gradient descent with initial regularizationcited by 0