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.
