# How Good is SGD with Random Shuffling?

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2019.

## Built on by (most cited first, 30 of 64)

- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning](https://mlsanity.com/paper/2305.18424/) (2023)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [Random Reshuffling with Variance Reduction: New Analysis and Better Rates](https://mlsanity.com/paper/2104.09342/) (2021)
- [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021)
- [Benign Underfitting of Stochastic Gradient Descent](https://mlsanity.com/paper/2202.13361/) (2022)
- [Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization](https://mlsanity.com/paper/2106.09082/) (2021)
- [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)
- [Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods](https://mlsanity.com/paper/2202.01838/) (2022)
- [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)
- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [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)
- [Nesterov Accelerated Shuffling Gradient Method for Convex Optimization](https://mlsanity.com/paper/2202.03525/) (2022)
- [Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization](https://mlsanity.com/paper/2206.02953/) (2022)
- [Last Iterate Convergence of Incremental Methods and Applications in Continual Learning](https://mlsanity.com/paper/2403.06873/) (2024)
- [Optimal Rates for Random Order Online Optimization](https://mlsanity.com/paper/2106.15207/) (2021)
- [Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?](https://mlsanity.com/paper/2103.07079/) (2021)
- [Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regime](https://mlsanity.com/paper/2203.03159/) (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)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [Reawakening knowledge: Anticipatory recovery from catastrophic interference via structured training](https://mlsanity.com/paper/2403.09613/) (2024)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [High Probability Guarantees for Random Reshuffling](https://mlsanity.com/paper/2311.11841/) (2023)

## Abstract (arXiv)

We study the performance of stochastic gradient descent (SGD) on smooth and strongly-convex finite-sum optimization problems. In contrast to the majority of existing theoretical works, which assume that individual functions are sampled with replacement, we focus here on popular but poorly-understood heuristics, which involve going over random permutations of the individual functions. This setting has been investigated in several recent works, but the optimal error rates remain unclear. In this paper, we provide lower bounds on the expected optimization error with these heuristics (using SGD with any constant step size), which elucidate their advantages and disadvantages. In particular, we prove that after k passes over n individual functions, if the functions are re-shuffled after every pass, the best possible optimization error for SGD is at least Omegaleft(1/(nk)2+1/nk3right), which partially corresponds to recently derived upper bounds. Moreover, if the functions are only shuffled once, then the lower bound increases to Omega(1/nk2). Since there are strictly smaller upper bounds for repeated reshuffling, this proves an inherent performance gap between SGD with single shuffling and repeated shuffling. As a more minor contribution, we also provide a non-asymptotic Omega(1/k2) lower bound (independent of n) for the incremental gradient method, when no random shuffling takes place. Finally, we provide an indication that our lower bounds are tight, by proving matching upper bounds for univariate quadratic functions.