Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910120946958336 |
|---|---|
| author | Dereziński, Michał Dong, Xiaoyu |
| author_facet | Dereziński, Michał Dong, Xiaoyu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_09909 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size Dereziński, Michał Dong, Xiaoyu Machine Learning Numerical Analysis Optimization and Control 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. |
| title | Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size |
| topic | Machine Learning Numerical Analysis Optimization and Control |
| url | https://arxiv.org/abs/2604.09909 |