# Stochastic Learning under Random Reshuffling with Constant Step-sizes

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2018.

## Built on by (most cited first, 15 of 15)

- [Effective Model Sparsification by Scheduled Grow-and-Prune Methods](https://mlsanity.com/paper/2106.09857/) (2021)
- [Discovering Symmetry Breaking in Physical Systems with Relaxed Group Convolution](https://mlsanity.com/paper/2310.02299/) (2023)
- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems](https://mlsanity.com/paper/2106.06880/) (2021)
- [Improved Analysis and Rates for Variance Reduction under Without-replacement Sampling Orders](https://mlsanity.com/paper/2104.12112/) (2021)
- [Federated Random Reshuffling with Compression and Variance Reduction](https://mlsanity.com/paper/2205.03914/) (2022)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [Distributed Random Reshuffling over Networks](https://mlsanity.com/paper/2112.15287/) (2021)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [Stochastic Gradient Descent without Full Data Shuffle](https://mlsanity.com/paper/2206.05830/) (2022)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [Random Reshuffling Dominates Stochastic Gradient Descent](https://mlsanity.com/paper/2606.32005/) (2026)
- [Painless step size adaptation for SGD](https://mlsanity.com/paper/2102.00853/) (2021)
- [Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent](https://mlsanity.com/paper/2610.19444/) (2026)

## Abstract (arXiv)

In empirical risk optimization, it has been observed that stochastic gradient implementations that rely on random reshuffling of the data achieve better performance than implementations that rely on sampling the data uniformly. Recent works have pursued justifications for this behavior by examining the convergence rate of the learning process under diminishing step-sizes. This work focuses on the constant step-size case and strongly convex loss function. In this case, convergence is guaranteed to a small neighborhood of the optimizer albeit at a linear rate. The analysis establishes analytically that random reshuffling outperforms uniform sampling by showing explicitly that iterates approach a smaller neighborhood of size O(μ2) around the minimizer rather than O(μ). Furthermore, we derive an analytical expression for the steady-state mean-square-error performance of the algorithm, which helps clarify in greater detail the differences between sampling with and without replacement. We also explain the periodic behavior that is observed in random reshuffling implementations.