Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent

arXiv:2610.19444v1 Announce Type: cross Abstract: Random reshuffling stochastic gradient descent (RR-SGD) is widely used for finite-sum optimization in machine learning. For convex L-smooth components, recent work establishes convergence guarantees for an averaged iterate with component stepsizes as large as order 1/L. However, the final iterate is a natural output in practice, and existing last-iterate guarantees in this setting require stepsizes that scale inversely with the number of components n. We establish an expected objective-gap bound for the last iterate of standard RR-SGD on unconstrained problems with a constant component stepsize satisfying 0<etalesssim 1/(L(1 + log(nK))), where K is the number of epochs. By retaining the sampling bias at random comparison points, we remove the explicit 1/n factor from the stepsize restriction. Combined with existing small-step bounds, our result matches the corresponding averaged-iterate convergence rate up to logarithmic factors.

Source: arXiv cs.LG | 2026-10-15