Pith. sign in

REVIEW 1 major objections 1 minor 1 cited by

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

T0 review · 1 major / 1 minor · reviewed 2026-05-10 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read The last iterate of randomized Kaczmarz and greedy-step SGD converges at rate O(1/t^{3/4}) on smooth quadratic objectives in the interpolation regime.

desk verdict The paper gets a 3/4 last-iterate rate for greedy SGD and Kaczmarz by modeling iterates as stochastic contraction processes and reducing to an eigenvalue equation, but the approximation errors in that reduction need checking. read the letter →

arxiv 2604.09909 v1 submitted 2026-04-10 cs.LG cs.NAmath.NAmath.OCstat.ML

Micha{l} Dereziński , Xiaoyu Dong This is my paper · ORCID
classification cs.LGcs.NAmath.NAmath.OCstat.ML
keywords last-iterateconvergencerandomizedKaczmarzSGDgreedystepsizeinterpolationregimestochasticcontractionprocessesrates
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper shows that the last iterate of stochastic gradient descent with a greedy step size converges at a rate of order 1 over t to the power 3/4 when applied to smooth quadratic objectives in the interpolation regime. This setting includes the classical randomized Kaczmarz algorithm for solving linear systems, and the new bound improves on a previous guarantee of order 1 over square root of t. The proof models the iterates using a family of stochastic contraction processes whose dynamics reduce to those of a deterministic eigenvalue equation, which is then analyzed by passing from discrete steps to a continuous limit. A sympathetic reader would care because these iterative methods are widely used in practice, and last-iterate convergence without averaging is often what matters for implementation.

What carries the argument

The family of stochastic contraction processes whose behavior reduces to the evolution of a deterministic eigenvalue equation analyzed via discrete-to-continuous reduction.

What would settle it

Measure the error of the final iterate versus iteration count t when running randomized Kaczmarz on a random consistent linear system and check whether the decay follows t to the power -3/4 or falls back to a slower rate.

Watch

Extended reading notes

Core claim

The authors prove an O(1/t^{3/4}) last-iterate convergence rate for SGD with greedy step sizes and randomized Kaczmarz on smooth quadratics in the interpolation regime. This is achieved by introducing stochastic contraction processes and reducing their analysis to the evolution of a deterministic eigenvalue equation via discrete-to-continuous techniques.

Load-bearing premise

The objective must be a smooth quadratic function satisfying the interpolation condition where the minimum is attained.

Editorial extensions

If this is right

  • The O(1/t^{3/4}) rate applies directly to randomized Kaczmarz on consistent linear systems.
  • Greedy step sizes yield faster last-iterate convergence for SGD without needing iterate averaging.
  • The stochastic contraction process model extends the analysis technique to similar iterative linear solvers.
  • The 3/4 exponent arises specifically from the eigenvalue dynamics in the discrete-to-continuous limit.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same modeling approach might produce improved last-iterate rates for non-quadratic smooth convex functions.
  • Step-size selection rules derived from the eigenvalue equation could be tested on other stochastic first-order methods.
  • In high-dimensional linear systems the faster rate would reduce the number of iterations needed to reach a target accuracy.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 1 minor

Summary. The manuscript analyzes the last-iterate convergence of SGD with greedy step sizes and the Randomized Kaczmarz method for solving linear systems, which correspond to smooth quadratic objectives in the interpolation regime. The central result is an O(1/t^{3/4}) convergence rate for the t-th iterate, improving on the O(1/t^{1/2}) rate from prior work by Attia et al. The proof introduces a new family of stochastic contraction processes whose evolution is captured by a deterministic eigenvalue equation obtained through a discrete-to-continuous reduction.

Significance. If the analysis holds, this provides a tighter last-iterate rate for a class of important iterative solvers, directly addressing an open question. The introduction of stochastic contraction processes and the discrete-to-continuous technique represent a novel approach that could be applied to other stochastic optimization problems. The result is notable for achieving a rate better than 1/2 without additional assumptions beyond smoothness and interpolation.

major comments (1)
  1. [§4 (Discrete-to-Continuous Reduction)] The key step reduces the stochastic recurrence for the contraction process to a deterministic eigenvalue equation. However, the error analysis for this reduction does not explicitly bound the discrepancy between the stochastic process and its deterministic approximation by o(1/t^{3/4}). If this error is only O(1/t^{1/2}), as might occur from standard concentration or discretization errors, the claimed rate would not hold. A more precise quantification of the approximation error, perhaps in Lemma 4.3 or similar, is needed to confirm the 3/4 exponent.
minor comments (1)
  1. [§3] The notation for the family of stochastic contraction processes could be summarized in a table or definition box to improve readability across the proof.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive assessment of the significance of the stochastic contraction processes framework and the improved last-iterate rate. We address the single major comment below.

read point-by-point responses

  1. Referee: [§4 (Discrete-to-Continuous Reduction)] The key step reduces the stochastic recurrence for the contraction process to a deterministic eigenvalue equation. However, the error analysis for this reduction does not explicitly bound the discrepancy between the stochastic process and its deterministic approximation by o(1/t^{3/4}). If this error is only O(1/t^{1/2}), as might occur from standard concentration or discretization errors, the claimed rate would not hold. A more precise quantification of the approximation error, perhaps in Lemma 4.3 or similar, is needed to confirm the 3/4 exponent.

    Authors: We appreciate the referee highlighting the need for an explicit error bound in the discrete-to-continuous reduction. In the current proof of Lemma 4.3, the discrepancy between the stochastic contraction process and the deterministic eigenvalue equation is controlled via a martingale argument that exploits the greedy step-size choice and the contraction property; this yields a total accumulated approximation error of O(1/t) (via a telescoping sum and variance decay). Since O(1/t) = o(1/t^{3/4}), the claimed rate is preserved. We agree, however, that this order is not stated as a standalone claim. In the revised version we will insert a short corollary immediately after Lemma 4.3 that explicitly records the O(1/t) bound on the approximation error together with the key steps of its derivation, thereby making the justification for the 3/4 exponent fully transparent. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity in the derivation; auxiliary process and reduction are independent modeling steps

full rationale

The paper introduces the family of stochastic contraction processes as an auxiliary modeling device and reduces its evolution to a deterministic eigenvalue equation via discrete-to-continuous analysis. This is an original analytical construction whose output (the O(1/t^{3/4}) rate) is not equivalent to any fitted input or prior quantity by definition. No self-citation is invoked as a load-bearing uniqueness theorem, no parameter is fitted on a subset and renamed as a prediction, and the central claim addresses an open question from independent prior work. The derivation chain remains self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 1 assumptions · 1 invented entities

The claim rests on the domain assumption that the problem is a smooth quadratic in the interpolation regime together with the modeling choice of stochastic contraction processes whose analysis reduces to a deterministic eigenvalue equation.

assumptions (1)
  • domain assumption The objective function is a smooth quadratic in the interpolation regime.
    Explicitly stated as the setting that captures Randomized Kaczmarz and other linear solvers.
invented entities (1)
  • stochastic contraction processes
    purpose: To model the evolution of the iterates so that their behavior reduces to a deterministic eigenvalue equation.
    New family introduced in the proof to enable the discrete-to-continuous analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size." pith.science (2026). https://pith.science/paper/2604.09909

@misc{pith2026260409909,
  author       = {Pith},
  title        = {Pith review of: Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.09909}},
  note         = {Machine review of arXiv:2604.09909}
}
abstract

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/t^{3/4})$ convergence rate, addressing a question posed by Attia, Schliserman, Sherman, and Koren, who gave an $O(1/t^{1/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.

Figures

Figures reproduced from arXiv: 2604.09909 by the authors.

Figure 1
Figure 1. Two simulations of the eigenvalue recursion (4). On the left is a small example (n = 6) illustrating the two regimes that distinguish the behavior of eigenvalues below and above the 1/2 threshold. On the right is a larger example consisting of n = 50 eigenvalues spread evenly in the log-scale between 1 and 10−20. Here, the dotted line is a best linear fit on the log-log plot for the evolution of maxk λk,t (the expon… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Perfect Parallelization in Mini-Batch SGD with Classical Momentum Acceleration

    cs.LG 2026-05 unverdicted novelty 6.0 of 10

    Classical momentum acceleration in mini-batch SGD for quadratics is proportional to batch size up to saturation, enabling perfect parallelization under minimal noise assumptions.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · cited by 1 Pith paper

  1. [1]

    The fast J ohnson-- L indenstrauss transform and approximate nearest neighbors

    Nir Ailon and Bernard Chazelle. The fast J ohnson-- L indenstrauss transform and approximate nearest neighbors. SIAM Journal on computing, 39 0 (1): 0 302--322, 2009

    work page 2009

  2. [2]

    Fast last-iterate convergenceofsgdinthesmoothinterpolationregime.arXiv preprint arXiv:2507.11274, 2025

    Amit Attia, Matan Schliserman, Uri Sherman, and Tomer Koren. Fast last-iterate convergence of sgd in the smooth interpolation regime. arXiv preprint arXiv:2507.11274, 2025

    work page arXiv 2025

  3. [3]

    Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)

    Francis Bach and Eric Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n). Advances in neural information processing systems, 26, 2013

    work page 2013

  4. [4]

    Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model

    Rapha \"e l Berthier, Francis Bach, and Pierre Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances in Neural Information Processing Systems, 33: 0 2576--2586, 2020

    work page 2020

  5. [5]

    Bertsekas

    Dimitri P. Bertsekas. Nonlinear Programming . Athena Scientific, 3rd edition, 2016. ISBN 978-1-886529-05-2. URL http://www.athenasc.com/nonlinbook.html

    work page 2016

  6. [6]

    arXiv preprint arXiv:2403.06873 , year=

    Xufeng Cai and Jelena Diakonikolas. Last iterate convergence of incremental methods and applications in continual learning. arXiv preprint arXiv:2403.06873, 2024

    work page arXiv 2024

  7. [7]

    Recent and upcoming developments in randomized numerical linear algebra for machine learning

    Micha Derezi \'n ski and Michael W Mahoney. Recent and upcoming developments in randomized numerical linear algebra for machine learning. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 6470--6479, 2024

    work page 2024

  8. [8]

    Sharp analysis of sketch-and-project methods via a connection to randomized singular value decomposition

    Micha Derezi \'n ski and Elizaveta Rebrova. Sharp analysis of sketch-and-project methods via a connection to randomized singular value decomposition. SIAM Journal on Mathematics of Data Science, 6 0 (1): 0 127--153, 2024

    work page 2024

Show all 37 references
  1. [9]

    Solving dense linear systems faster than via preconditioning

    Micha Derezi \'n ski and Jiaming Yang. Solving dense linear systems faster than via preconditioning. In 56th Annual ACM Symposium on Theory of Computing, 2024

    2024

  2. [10]

    Fine-grained analysis and faster algorithms for iteratively solving linear systems

    Micha Derezi \'n ski, Daniel LeJeune, Deanna Needell, and Elizaveta Rebrova. Fine-grained analysis and faster algorithms for iteratively solving linear systems. Journal of Machine Learning Research, 26 0 (144): 0 1--49, 2025 a

    2025

  3. [11]

    Randomized kaczmarz methods with beyond-krylov convergence

    Micha Derezi \'n ski, Deanna Needell, Elizaveta Rebrova, and Jiaming Yang. Randomized kaczmarz methods with beyond-krylov convergence. SIAM Journal on Matrix Analysis and Applications, 46 0 (4): 0 2558--2588, 2025 b

    2025

  4. [12]

    Block-iterative methods for consistent and inconsistent linear equations

    Tommy Elfving. Block-iterative methods for consistent and inconsistent linear equations. Numerische Mathematik, 35 0 (1): 0 1--12, 1980

    1980

  5. [13]

    How catastrophic can catastrophic forgetting be in linear regression? In Conference on Learning Theory, pages 4028--4079

    Itay Evron, Edward Moroshko, Rachel Ward, Nathan Srebro, and Daniel Soudry. How catastrophic can catastrophic forgetting be in linear regression? In Conference on Learning Theory, pages 4028--4079. PMLR, 2022

    2022

  6. [14]

    From continual learning to sgd and back: Better rates for continual linear models

    Itay Evron, Ran Levinstein, Matan Schliserman, Uri Sherman, Tomer Koren, Daniel Soudry, and Nathan Srebro. From continual learning to sgd and back: Better rates for continual linear models. In Fourth Conference on Lifelong Learning Agents-Workshop Track, 2025

    2025

  7. [15]

    The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares

    Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. Advances in neural information processing systems, 32, 2019

    2019

  8. [16]

    Randomized iterative methods for linear systems

    Robert M Gower and Peter Richt \'a rik. Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications, 36 0 (4): 0 1660--1690, 2015

    2015

  9. [17]

    Tight analyses for non-smooth stochastic gradient descent

    Nicholas JA Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579--1613. PMLR, 2019

    2019

  10. [18]

    Making the last iterate of sgd information theoretically optimal

    Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory, pages 1752--1755. PMLR, 2019

    2019

  11. [19]

    M. S. Kaczmarz. Angenaherte auflosung von systemen linearer gleichungen. Bulletin International de l’Academie Polonaise des Sciences et des Lettres, 35: 0 355–357, 1937

    1937

  12. [20]

    Randomized methods for linear constraints: convergence rates and conditioning

    Dennis Leventhal and Adrian S Lewis. Randomized methods for linear constraints: convergence rates and conditioning. Mathematics of Operations Research, 35 0 (3): 0 641--654, 2010

    2010

  13. [21]

    Optimal rates in continual linear regression via increasing regularization

    Ran Levinstein, Amit Attia, Matan Schliserman, Uri Sherman, Tomer Koren, Daniel Soudry, and Itay Evron. Optimal rates in continual linear regression via increasing regularization. arXiv preprint arXiv:2506.06501, 2025

    2025

  14. [22]

    Aiming towards the minimizers: fast convergence of sgd for overparametrized problems

    Chaoyue Liu, Dmitriy Drusvyatskiy, Misha Belkin, Damek Davis, and Yian Ma. Aiming towards the minimizers: fast convergence of sgd for overparametrized problems. Advances in neural information processing systems, 36: 0 60748--60767, 2023

    2023

  15. [23]

    Revisiting the last-iterate convergence of stochastic gradient methods

    Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. The Twelfth International Conference on Learning Representations, 2023

    2023

  16. [24]

    The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning

    Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. In International Conference on Machine Learning, pages 3325--3334. PMLR, 2018

    2018

  17. [25]

    The stability-plasticity dilemma: Investigating the continuum from catastrophic forgetting to age-limited learning effects, 2013

    Martial Mermillod, Aur \'e lia Bugaiska, and Patrick Bonin. The stability-plasticity dilemma: Investigating the continuum from catastrophic forgetting to age-limited learning effects, 2013

    2013

  18. [26]

    Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm

    Deanna Needell, Nathan Srebro, and Rachel Ward. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Advances in neural information processing systems, 27, 2014

    2014

  19. [27]

    Have askotch: A neat solution for large-scale kernel ridge regression

    Pratik Rathore, Zachary Frangella, Jiaming Yang, Micha Derezi\'nski, and Madeleine Udell. Have askotch: A neat solution for large-scale kernel ridge regression. arXiv preprint arXiv:2407.10070, 2025

    2025

  20. [28]

    A stochastic approximation method

    Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400--407, 1951

    1951

  21. [29]

    Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes

    Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International conference on machine learning, pages 71--79. PMLR, 2013

    2013

  22. [30]

    Approximate solutions of linear systems at a universal rate

    Stefan Steinerberger. Approximate solutions of linear systems at a universal rate. SIAM Journal on Matrix Analysis and Applications, 44 0 (3): 0 1436--1446, 2023

    2023

  23. [31]

    A randomized kaczmarz algorithm with exponential convergence

    Thomas Strohmer and Roman Vershynin. A randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15 0 (2): 0 262--278, 2009

    2009

  24. [32]

    Nearly optimal bounds for cyclic forgetting

    William Swartworth, Deanna Needell, Rachel Ward, Mark Kong, and Halyun Jeong. Nearly optimal bounds for cyclic forgetting. Advances in neural information processing systems, 36: 0 68197--68206, 2023

    2023

  25. [33]

    Last iterate convergence of sgd for least-squares in the interpolation regime

    Aditya Vardhan Varre, Loucas Pillaud-Vivien, and Nicolas Flammarion. Last iterate convergence of sgd for least-squares in the interpolation regime. Advances in Neural Information Processing Systems, 34: 0 21581--21591, 2021

    2021

  26. [34]

    Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron

    Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron. In The 22nd international conference on artificial intelligence and statistics, pages 1195--1204. PMLR, 2019

    2019

  27. [35]

    Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression

    Jingfeng Wu, Difan Zou, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. In International conference on machine learning, pages 24280--24314. PMLR, 2022

    2022

  28. [36]

    Exact convergence rate of the last iterate in subgradient methods

    Moslem Zamani and Francois Glineur. Exact convergence rate of the last iterate in subgradient methods. SIAM Journal on Optimization, 35 0 (3): 0 2182--2201, 2025

    2025

  29. [37]

    Benign overfitting of constant-stepsize sgd for linear regression

    Difan Zou, Jingfeng Wu, Vladimir Braverman, Quanquan Gu, and Sham Kakade. Benign overfitting of constant-stepsize sgd for linear regression. In Conference on learning theory, pages 4633--4635. PMLR, 2021

    2021

Pith tools

Reviewed May 10, 2026 · model on record in the stance chip above.