Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
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<η≲ 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.
Related
- Last-Iterate Convergence Rate of Normalized Gradient Descent under Hölder Smoothness
- Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent
- Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems
- A Rate Transfer Method: Convergence Rates in Stochastic Gradient Descent via Stochastic Calculus
- A Shadow Sequence Technique for Last-Iterate Convergence Analysis of the Random Reshuffling Method: Relaxed Stepsize Conditions and Beyond
BibTeX
@misc{chen2026largestep,
title = {{Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent}},
author = {Zijun Chen and Zihan Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19444},
eprint = {2610.19444},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19444},
}
RIS
TY - UNPB
TI - Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
AU - Zijun Chen
AU - Zihan Zhang
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19444
UR - https://arxiv.org/abs/2610.19444
AB - 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<η≲ 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.
ER -