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

Michał Dereziński; Xiaoyu Dong

cs.LGApr 10, 2026

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

Authors: Michał Dereziński, Xiaoyu Dong

Organizations: University of Michigan · National University of Singapore

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 & tables

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

\max_{k}\lambda_{k,t}

(the exponent

3/4+0.01

was rounded). To best accommodate the log-log plot we start indexing the recursions at

t=1

, not at 0.

Last-Iterate Convergence

Last-iterate convergence studies whether an algorithm’s final update approaches an optimizer or equilibrium, rather than only its average.

See all 41 papers

Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
Oct 18, 2026Matan Schliserman, Tomer KorenLast-Iterate Convergence Stochastic Optimization Convergence
Blavatnik School of Computer Science and AI, Tel Aviv University · Blavatnik School of Computer Science and AI, Tel Aviv University, and Google Research Tel Aviv
Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
Oct 14, 2026Zijun Chen, Zihan ZhangStochastic Optimization Last-Iterate Convergence
Department of Computer Science and Engineering, Hong Kong University of Science and Technology
Gradient Descent's Last Iterate is Often (slightly) Suboptimal
Apr 15, 2026Guy Kornowski, Ohad ShamirLast-Iterate Convergence Gradient Descent
Institute for Advanced Study · Weizmann Institute of Science · University of Toronto and the Vector Institute

Oct 18, 2026J/K move · Enter open · S save

Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

Matan Schliserman, Tomer Koren

Blavatnik School of Computer Science and AI, Tel Aviv University · Blavatnik School of Computer Science and AI, Tel Aviv University, and Google Research Tel Aviv

Last-Iterate Convergence Stochastic Optimization Convergence Stochastic Gradient Descent

Open paper AskPDF arXiv

We study the last iterate of stochastic gradient descent (SGD) with a constant stepsize on smooth convex objectives in the low-noise and interpolation regimes, where the variance

σ_\star^2

of the stochastic gradients at the optimum is small or zero. We establish that after

T

steps of SGD on

β

-smooth convex losses with any constant stepsize

0<η<2/β

, the last iterate attains expected excess risk

\widetilde O\bigl(\tfrac{1}{η(2-βη)^3T}+\tfracη{(2-βη)^4}σ_\star^2\bigr)

, which gives the rate

\smash{\widetilde O(1/T)}

for every constant stepsize in the interpolation regime (

σ_\star=0

), matching the

Ω(1/T)

lower bound up to logarithmic factors and improving upon the

O(1/\sqrt T)

rate of Attia et al. (2026) for

η=1/β

. Our analysis is based on a new technique, which compares the second moments of the stochastic gradients along the SGD trajectory across only logarithmically many time scales. For quadratic losses in the interpolation regime, an adaptation of this technique gives an

O(1/T)

rate for every constant stepsize, extending the recent optimal rate for the randomized Kaczmarz method of Derezinski and Dong (2026) to stepsizes above the greedy stepsize with an arguably simpler proof.

Abstract

Last-Iterate Convergence

Explore similar work

Near-Optimal Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

Gradient Descent's Last Iterate is Often (slightly) Suboptimal