# Random Reshuffling Dominates Stochastic Gradient Descent

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 30 Jun 2026.

## Builds on (most cited first, 18 of 18)

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [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)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [Benign Underfitting of Stochastic Gradient Descent](https://mlsanity.com/paper/2202.13361/) (2022)
- [Permutation-Based SGD: Is Random Optimal?](https://mlsanity.com/paper/2102.09718/) (2021)
- [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)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Optimal Rates for Random Order Online Optimization](https://mlsanity.com/paper/2106.15207/) (2021)
- [Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization](https://mlsanity.com/paper/2505.23056/) (2025)

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

- [Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensions](https://mlsanity.com/paper/2609.04578/) (2026)
- [Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent](https://mlsanity.com/paper/2610.19444/) (2026)

## Abstract (arXiv)

Stochastic Gradient Descent (textsfSGD) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of textsfSGD differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (textsfShuffling SGD). A particularly popular strategy in textsfShuffling SGD is Random Reshuffling (textsfRR), which has achieved great empirical success across numerous experiments. Despite its strong performance, textsfRR has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for textsfRR, thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of textsfRR remain to this day. More precisely, according to the current theory, textsfShuffling SGD under textsfRR converges only when the stepsize is smaller than a threshold proportional to 1/n, where n is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of textsfShuffling SGD under textsfRR is strictly worse than that of textsfSGD when the number of epochs is smaller than another threshold proportional to n. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that textsfRR dominates textsfSGD in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.