Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
This addresses an open question about the convergence rate of randomized Kaczmarz and SGD with greedy step size, providing a tighter bound for iterative linear system solvers.
The paper proves that SGD with greedy step size over smooth quadratics in the interpolation regime achieves an O(1/t^{3/4}) last-iterate convergence rate, improving upon the previous O(1/t^{1/2}) guarantee.
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.