# Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problems

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 25 references that are in the map.
- First posted on arXiv 12 Jun 2021.

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

- [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)
- [Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is False](https://mlsanity.com/paper/2006.01510/) (2020)
- [Stochastic Learning under Random Reshuffling with Constant Step-sizes](https://mlsanity.com/paper/1803.07964/) (2018)
- [Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?](https://mlsanity.com/paper/2103.07079/) (2021)

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

- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [Benign Underfitting of Stochastic Gradient Descent](https://mlsanity.com/paper/2202.13361/) (2022)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (2022)
- [Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptation](https://mlsanity.com/paper/2410.08305/) (2024)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization](https://mlsanity.com/paper/2206.02953/) (2022)
- [Mini-Batch Optimization of Contrastive Loss](https://mlsanity.com/paper/2307.05906/) (2023)
- [On Convergence of Incremental Gradient for Non-Convex Smooth Functions](https://mlsanity.com/paper/2305.19259/) (2023)
- [Asynchronous Federated Learning: A Scalable Approach for Decentralized Machine Learning](https://mlsanity.com/paper/2412.17723/) (2024)
- [Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimization](https://mlsanity.com/paper/2505.08306/) (2025)
- [Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/2310.15976/) (2023)
- [Demystifying SGD with Doubly Stochastic Gradients](https://mlsanity.com/paper/2406.00920/) (2024)
- [Random Reshuffling Dominates Stochastic Gradient Descent](https://mlsanity.com/paper/2606.32005/) (2026)
- [Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Condition](https://mlsanity.com/paper/2304.00459/) (2023)
- [First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptions](https://mlsanity.com/paper/2512.21521/) (2025)
- [Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent](https://mlsanity.com/paper/2610.19444/) (2026)

## Abstract (arXiv)

Recently, there has been much interest in studying the convergence rates of without-replacement SGD, and proving that it is faster than with-replacement SGD in the worst case. However, known lower bounds ignore the problem's geometry, including its condition number, whereas the upper bounds explicitly depend on it. Perhaps surprisingly, we prove that when the condition number is taken into account, without-replacement SGD does not significantly improve on with-replacement SGD in terms of worst-case bounds, unless the number of epochs (passes over the data) is larger than the condition number. Since many problems in machine learning and other areas are both ill-conditioned and involve large datasets, this indicates that without-replacement does not necessarily improve over with-replacement sampling for realistic iteration budgets. We show this by providing new lower and upper bounds which are tight (up to log factors), for quadratic problems with commuting quadratic terms, precisely quantifying the dependence on the problem parameters.