A Shadow Sequence Technique for Last-Iterate Convergence Analysis of the Random Reshuffling Method: Relaxed Stepsize Conditions and Beyond
Abstract
We prove two last-iterate convergence bounds of the random reshuffling (RR) method in the smooth general convex finite-sum optimization. In the proved results, the stepsize sequence {ηk}k of RR is an arbitrary positive non-increasing sequence with η1≲ 1/(polylog(n)L), where n is the number of components of the finite-sum objective and L is the smoothness parameter. Specifically, a last-iterate convergence rate 𝒪̃((‖ x11−x*‖2)/n∑k=1Kηk+σ*2∑k=1Kηk2/∑l=kKηl) of RR is proved, where x* is a solution of the optimization problem and σ*2 is the variance at the solution x*. This rate is novel to the last-iterate of RR. Also, a last-iterate convergence rate 𝒪̃((‖ x11−x*‖2)/n∑k=1Kηk+nσ*2∑k=1Kηk3/∑l=kKηl ) of RR is proved. A similar rate exists in the literature, but only under a restrictive stepsize condition η≲ 1/(n L) and does not allow varying stepsizes. At the heart of our proof for the latter rate is an auxiliary sequence named the shadow sequence, which has the same epoch endpoints with the iterate sequence generated by RR. The shadow sequence can be regarded as an iterate sequence generated by performing an inexact RR on an auxiliary interpolated problem or performing a novel variant of random reshuffled SVRG on the original problem. The shadow sequence technique sheds light on deeper understanding of RR and may be useful in the analysis of other shuffling methods.
Related
- Convergence of Large-Stepsize SGD for the Cross-entropy Loss via Stochastic Lyapunov Stability
- Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
- Domains of Monomial Convergence in Banach Sequence Spaces
- Quasi-convergence of stability conditions
- Whole-Sequence Convergence of Variable-Smoothing Full-Splitting Methods via a Lifted Kurdyka-Łojasiewicz Framework
BibTeX
@misc{liu2026shadow,
title = {{A Shadow Sequence Technique for Last-Iterate Convergence Analysis of the Random Reshuffling Method: Relaxed Stepsize Conditions and Beyond}},
author = {Hai Liu and Tiande Guo and Congying Han},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.29166},
eprint = {2610.29166},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.29166},
}
RIS
TY - UNPB
TI - A Shadow Sequence Technique for Last-Iterate Convergence Analysis of the Random Reshuffling Method: Relaxed Stepsize Conditions and Beyond
AU - Hai Liu
AU - Tiande Guo
AU - Congying Han
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2610.29166
UR - https://arxiv.org/abs/2610.29166
AB - We prove two last-iterate convergence bounds of the random reshuffling (RR) method in the smooth general convex finite-sum optimization. In the proved results, the stepsize sequence {η_k}_k of RR is an arbitrary positive non-increasing sequence with η_1≲ 1/(polylog(n)L), where n is the number of components of the finite-sum objective and L is the smoothness parameter. Specifically, a last-iterate convergence rate 𝒪̃((‖ x_1^1−x_*‖^2)/n∑_k=1^Kη_k+σ_*^2∑_k=1^Kη_k^2/∑_l=k^Kη_l) of RR is proved, where x_* is a solution of the optimization problem and σ_*^2 is the variance at the solution x_*. This rate is novel to the last-iterate of RR. Also, a last-iterate convergence rate 𝒪̃((‖ x_1^1−x_*‖^2)/n∑_k=1^Kη_k+nσ_*^2∑_k=1^Kη_k^3/∑_l=k^Kη_l ) of RR is proved. A similar rate exists in the literature, but only under a restrictive stepsize condition η≲ 1/(n L) and does not allow varying stepsizes. At the heart of our proof for the latter rate is an auxiliary sequence named the shadow sequence, which has the same epoch endpoints with the iterate sequence generated by RR. The shadow sequence can be regarded as an iterate sequence generated by performing an inexact RR on an auxiliary interpolated problem or performing a novel variant of random reshuffled SVRG on the original problem. The shadow sequence technique sheds light on deeper understanding of RR and may be useful in the analysis of other shuffling methods.
ER -