mlsanityData to 14 Oct 2026

Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size

arXiv 2604.09909 ↗First posted 10 Apr 2026cs.LG cs.NA math.NAcited by 2

Not on the map. Why?

Abstract (arXiv)

We study last-iterate convergence of SGD with greedy step size over smooth quadratics in the interpolation regime, a setting which captures the classical Randomized Kaczmarz algorithm as well as other popular iterative linear system solvers. For these methods, we show that the t-th iterate attains an O(1/t3/4) convergence rate, addressing a question posed by Attia, Schliserman, Sherman, and Koren, who gave an O(1/t1/2) guarantee for this setting. In the proof, we introduce the family of stochastic contraction processes, whose behavior can be described by the evolution of a certain deterministic eigenvalue equation, which we analyze via a careful discrete-to-continuous reduction.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 24 of its 37 references that are in the map. First posted on arXiv 10 Apr 2026.

Builds on

24 of 37 references.

References · 24

  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. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  5. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  6. 2022How catastrophic can catastrophic forgetting be in linear regression?cited by 81
  7. 2021Benign Overfitting of Constant-Stepsize SGD for Linear Regressioncited by 71
  8. 2019The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure For Least Squarescited by 68
  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. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 38
  12. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
12 more
  1. 2023Exact convergence rate of the last iterate in subgradient methodscited by 25
  2. 2023Aiming towards the minimizers: fast convergence of SGD for overparametrized problemscited by 22
  3. 2022Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decompositioncited by 19
  4. 2023Solving Dense Linear Systems Faster Than via Preconditioningcited by 12
  5. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 12
  6. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 12
  7. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  8. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  9. 2024Have ASkotch: A Neat Solution for Large-scale Kernel Ridge Regressioncited by 8
  10. 2025Optimal Rates in Continual Linear Regression via Increasing Regularizationcited by 8
  11. 2024Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systemscited by 7
  12. 2025Randomized Kaczmarz Methods with Beyond-Krylov Convergencecited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Perfect Parallelization in Mini-Batch SGD with Classical Momentum Accelerationcited by 0
  2. 2026How AI settled the complexity of the oldest SGD algorithmcited by 0