Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
Random reshuffling (RR) is the de facto standard for training machine learning models, yet theory has long lagged practice for last-iterate convergence. Existing guarantees required stepsizes as small as $1/(nL)$, while averaged-iterate analyses allowed $1/L$. Chen and Zhang close this gap for smooth convex objectives, proving that the last iterate of RR-SGD converges with stepsizes up to $1/(L(1+\log(nK)))$---removing the explicit $1/n$ barrier at the cost of only logarithmic factors. The result matters because practitioners return the final parameter, not an average, and large constant stepsizes are common in deep learning.
The paper makes a strong theoretical advance: it is the first to establish large-step last-iterate convergence for standard RR-SGD with non-zero noise at the optimum ($\sigma_{\star}^{2}>0$). The analysis is novel, combining signed sampling-bias cancellation at random comparison points with a self-bounding gradient-moment recursion that closes under $\eta L(1+\log(nK))\lesssim 1$ rather than $\eta n L\lesssim 1$. Up to polylogarithmic factors, the tuned rate matches the corresponding averaged-iterate guarantee of Liu (2026), which is essentially optimal given existing lower bounds. That said, the logarithmic slacks in both the stepsize ceiling ($\Lambda=1+\log(nK)$) and the noise prefactor ($\Lambda^{3/2}$) may be artifacts of the current suffix-to-last proof technique rather than fundamental.
The technical development is sound and carefully modularized. The permutation-swap stability bounds (Lemma 1) and self-bounding estimates (Lemma 2) build transparently on Liu (2026), while the new suffix-to-last conversion with signed bias cancellation (Lemmas 3--4) is genuinely novel and well motivated. The three-regime stitching in Section 5.4---small, intermediate, and large stepsizes---is rigorous and cleanly yields the final $\min\{\eta\sigma_{\star}^{2},\eta^{2}nL\sigma_{\star}^{2}\}$ noise term. As advertised, the result strictly improves over prior last-iterate bounds.
The most significant limitation is the logarithmic overhead. The stepsize restriction $\eta\leq 1/(1024L\Lambda)$ and the noise term $\Lambda^{3/2}\min\{\eta\sigma_{\star}^{2},\eta^{2}nL\sigma_{\star}^{2}\}$ are likely loose: the authors themselves ask whether the logarithmic losses can be removed. The harmonic-number absorption step (Lemma 5 and Eq. 18) introduces this log factor to control the history term, but no matching lower bound is known to show it is necessary.\n\nA second concern is that the bound is purely asymptotic in $O(\cdot)$ notation with large implicit constants (e.g., $1024$, $128$), which obscures the practical stepsize range. Third, the analysis relies on unconstrained optimization and a uniform smoothness bound $L=\max_{i}L_{i}$; the discussion mentions that retaining individual $L_{i}$'s is left for future work. Finally, because the paper is entirely theoretical, there is no empirical check that the predicted $1/(L\log(nK))$ stepsize indeed yields stable last-iterate convergence in simple test cases.
The paper fairly positions itself against Liu (2026), which established the averaged-iterate large-step rate $D^{2}/(\eta nK)+\sigma_{\star}^{2}\min\{\eta,\eta^{2}nL\}$ for $\eta\lesssim 1/L$, and against Liu and Zhou (2024) and Cai and Diakonikolas (2025), which gave last-iterate bounds but with $\eta\lesssim 1/(nL)$. The comparison is accurate. However, the lower bound of Cha et al. (2023)---$(L\sigma_{\star}^{2}D^{4}/(nK^{2}))^{1/3}$---only applies for $\eta\lesssim 1/(nL)$ and large $K$, so it does not certify optimality of the new large-step result, a point the authors honestly acknowledge. The paper also correctly notes that the small-epoch lower bounds of Kim et al. (2025) are for deterministic cyclic IGD and do not apply to fresh random reshuffling.
Reproducibility is mixed. On the positive side, the algorithm is vanilla RR-SGD (Algorithm 1), all assumptions are standard, and the proof is self-contained with appendices providing detailed derivations. The stepsize condition $\eta\leq 1/(1024L(1+\log(nK)))$ is explicit. On the negative side, no code or experimental scripts are provided, and the constants in the analysis (e.g., the factor $1024$) are not derived from a reference implementation. An independent reproduction would require carefully re-implementing the virtual-iterate permutation-swap argument and the suffix-to-last weight algebra, which is nontrivial but feasible from the text.
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<\eta\lesssim 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.
Pick a starting point or write your own. Challenges run in the background, so you can keep reading while the AI investigates.
No challenges yet. Disagree with the review? Ask the AI to revisit a specific claim.