# SGD with shuffling: optimal rates without component convexity and large epoch requirements

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

## Key facts

- Cited by 58 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2020.

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

- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [On the Convergence of Federated Averaging with Cyclic Client Participation](https://mlsanity.com/paper/2302.03109/) (2023)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [On the Convergence of Black-Box Variational Inference](https://mlsanity.com/paper/2305.15349/) (2023)
- [Federated Optimization Algorithms with Random Reshuffling and Gradient Compression](https://mlsanity.com/paper/2206.07021/) (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)
- [Adaptive Compression for Communication-Efficient Distributed Training](https://mlsanity.com/paper/2211.00188/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [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)
- [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)
- [SGDA with shuffling: faster convergence for nonconvex-PL minimax optimization](https://mlsanity.com/paper/2210.05995/) (2022)
- [Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!](https://mlsanity.com/paper/2306.05862/) (2023)
- [Mini-Batch Optimization of Contrastive Loss](https://mlsanity.com/paper/2307.05906/) (2023)
- [Stochastic Reweighted Gradient Descent](https://mlsanity.com/paper/2103.12293/) (2021)
- [Random-reshuffled SARAH does not need a full gradient computations](https://mlsanity.com/paper/2111.13322/) (2021)
- [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)
- [Optimizer Memory Makes Shuffle Order a First-Order Source of Fine-Tuning Noise](https://mlsanity.com/paper/2606.29554/) (2026)
- [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)

## Abstract (arXiv)

We study without-replacement SGD for solving finite-sum optimization problems. Specifically, depending on how the indices of the finite-sum are shuffled, we consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) algorithms. First, we establish minimax optimal convergence rates of these algorithms up to poly-log factors. Notably, our analysis is general enough to cover gradient dominated nonconvex costs, and does not rely on the convexity of individual component functions unlike existing optimal convergence results. Secondly, assuming convexity of the individual components, we further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts: large number of epochs required for the results to hold, and extra poly-log factor gaps to the lower bound.