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

arXiv: https://arxiv.org/abs/2610.19444 · HTML: https://mlsanity.com/paper/2610.19444/

## 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 (most cited first, 18 of 18)

- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [How Good is SGD with Random Shuffling?](https://mlsanity.com/paper/1908.00045/) (2019)
- [SGD without Replacement: Sharper Rates for General Smooth Convex Functions](https://mlsanity.com/paper/1903.01463/) (2019)
- [A Unified Convergence Analysis for Shuffling-Type Gradient Methods](https://mlsanity.com/paper/2002.08246/) (2020)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Closing the convergence gap of SGD without replacement](https://mlsanity.com/paper/2002.10400/) (2020)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems](https://mlsanity.com/paper/2106.06880/) (2021)
- [Stochastic Learning under Random Reshuffling with Constant Step-sizes](https://mlsanity.com/paper/1803.07964/) (2018)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization](https://mlsanity.com/paper/2505.23056/) (2025)
- [Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems](https://mlsanity.com/paper/2506.04126/) (2025)
- [Random Reshuffling Dominates Stochastic Gradient Descent](https://mlsanity.com/paper/2606.32005/) (2026)

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