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

Michał Dereziński, Xiaoyu Dong
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:1771-1813, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-derezinski26b, title = {Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size}, author = {Derezi{\'n}ski, Micha{\l} and Dong, Xiaoyu}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {1771--1813}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/derezinski26b/derezinski26b.pdf}, url = {https://proceedings.mlr.press/v336/derezinski26b.html}, 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. } }
Endnote
%0 Conference Paper %T Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size %A Michał Dereziński %A Xiaoyu Dong %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-derezinski26b %I PMLR %P 1771--1813 %U https://proceedings.mlr.press/v336/derezinski26b.html %V 336 %X 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.
APA
Dereziński, M. & Dong, X.. (2026). Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:1771-1813 Available from https://proceedings.mlr.press/v336/derezinski26b.html.

Related Material