{"id":"arxiv/2604.09909","url":"https://arxiv.org/abs/2604.09909","tags":["cs.LG","math.NA","math.OC","stat.ML"],"score":0,"title":"Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size","domain":"cs.LG","source":"arxiv","authors":["Michał Dereziński","Xiaoyu Dong"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-10","reactions":{}}