# Permutation-Based SGD: Is Random Optimal?

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 19 Feb 2021.

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

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [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)
- [Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey](https://mlsanity.com/paper/1507.01030/) (2015)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [SMG: A Shuffling Gradient-Based Method with Momentum](https://mlsanity.com/paper/2011.11884/) (2020)
- [Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is False](https://mlsanity.com/paper/2006.01510/) (2020)

## 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 Impact of Machine Learning Randomness on Group Fairness](https://mlsanity.com/paper/2307.04138/) (2023)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods](https://mlsanity.com/paper/2202.01838/) (2022)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Mini-Batch Optimization of Contrastive Loss](https://mlsanity.com/paper/2307.05906/) (2023)
- [Coordinating Distributed Example Orders for Provably Accelerated Training](https://mlsanity.com/paper/2302.00845/) (2023)
- [RINAS: Training with Dataset Shuffling Can Be General and Fast](https://mlsanity.com/paper/2312.02368/) (2023)
- [Randomised Splitting Methods and Stochastic Gradient Descent](https://mlsanity.com/paper/2504.04274/) (2025)
- [Random Reshuffling Dominates Stochastic Gradient Descent](https://mlsanity.com/paper/2606.32005/) (2026)
- [Computing the Variance of Shuffling Stochastic Gradient Algorithms via Power Spectral Density Analysis](https://mlsanity.com/paper/2206.00632/) (2022)
- [Ordering for Non-Replacement SGD](https://mlsanity.com/paper/2306.15848/) (2023)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Towards Continuous-Time Approximations for Stochastic Gradient Descent without Replacement](https://mlsanity.com/paper/2512.04703/) (2025)
- [Stochastic Optimization Under Power-Law Spectra: Tight Bounds and Shuffling Analysis](https://mlsanity.com/paper/2609.36271/) (2026)
- [When Is Deletion Ordering Tractable? From Update Dynamics to Permutation Structure](https://mlsanity.com/paper/2610.01149/) (2026)

## Abstract (arXiv)

A recent line of ground-breaking results for permutation-based SGD has corroborated a widely observed phenomenon: random permutations offer faster convergence than with-replacement sampling. However, is random optimal? We show that this depends heavily on what functions we are optimizing, and the convergence gap between optimal and random permutations can vary from exponential to nonexistent. We first show that for 1-dimensional strongly convex functions, with smooth second derivatives, there exist permutations that offer exponentially faster convergence compared to random. However, for general strongly convex functions, random permutations are optimal. Finally, we show that for quadratic, strongly-convex functions, there are easy-to-construct permutations that lead to accelerated convergence compared to random. Our results suggest that a general convergence characterization of optimal permutations cannot capture the nuances of individual function classes, and can mistakenly indicate that one cannot do much better than random.