mlsanityData to 14 Oct 2026

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

arXiv 2610.19444 ↗First posted 14 Oct 2026math.OC cs.LG stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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<η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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 18 of its 27 references that are in the map. First posted on arXiv 14 Oct 2026.

Builds on

18 of 27 references.

References · 18

  1. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  2. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  3. 2015Why Random Reshuffling Beats Stochastic Gradient Descentcited by 79
  4. 2018Random Shuffling Beats SGD after Finite Epochscited by 67
  5. 2019How Good is SGD with Random Shuffling?cited by 64
  6. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
  7. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  8. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  9. 2020Closing the convergence gap of SGD without replacementcited by 57
  10. 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 27
  11. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 22
  12. 2021Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problemscited by 17
6 more
  1. 2018Stochastic Learning under Random Reshuffling with Constant Step-sizescited by 15
  2. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 12
  3. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 11
  4. 2025Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimizationcited by 4
  5. 2025Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problemscited by 2
  6. 2026Random Reshuffling Dominates Stochastic Gradient Descentcited by 2

Built on by

Not cited yet.