Research
Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
arXiv:2604.09909v1 Announce Type: new Abstract: We study last-iterate convergence of SGD with greedy step size over smooth quadratics in the interpolation regime, a setting which captures the classica
arXiv:2604.09909v1 Announce Type: new 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.
Related
- Optimal L2 Regularization in High-dimensional Continual Linear Regression
- Smoothing the Edges: Smooth Optimization for Sparse Regularization using Hadamard Overparametrization
- On the Convergence of Gradient Descent on Learning Transformers with Residual Connections
Source: arXiv cs.LG | 2026-04-14