mlsanityData to 14 Oct 2026

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

arXiv 2006.06946 ↗First posted 12 Jun 2020math.OC stat.MLcited by 58

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 9; 2023: 17; 2024: 11; 2025: 3; 2026: 9.

58 papers.

Sort:

By area:

  1. 2021Proximal and Federated Random Reshufflingcited by 33
  2. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  3. 2023Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimizationcited by 22
  4. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited by 22
  5. 2023On the Convergence of Black-Box Variational Inferencecited by 22
  6. 2022Federated Optimization Algorithms with Random Reshuffling and Gradient Compressioncited by 18
  7. 2021Permutation-Based SGD: Is Random Optimal?cited by 17
  8. 2021Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned Problemscited by 17
  9. 2022Adaptive Compression for Communication-Efficient Distributed Trainingcited by 16
  10. 2023AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithmscited by 16
  11. 2023Federated Learning with Regularized Client Participationcited by 14
  12. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
38 more
  1. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 13
  2. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 11
  3. 2022Nesterov Accelerated Shuffling Gradient Method for Convex Optimizationcited by 10
  4. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  5. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  6. 2021Optimal Rates for Random Order Online Optimizationcited by 9
  7. 2021Can Single-Shuffle SGD be Better than Reshuffling SGD and GD?cited by 8
  8. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
  9. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  10. 2023Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!cited by 8
  11. 2023Mini-Batch Optimization of Contrastive Losscited by 8
  12. 2021Stochastic Reweighted Gradient Descentcited by 7
  13. 2021Random-reshuffled SARAH does not need a full gradient computationscited by 7
  14. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  15. 2024Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applicationscited by 7
  16. 2026Optimizer Memory Makes Shuffle Order a First-Order Source of Fine-Tuning Noisecited by 7
  17. 2022Efficiency Ordering of Stochastic Gradient Descentcited by 6
  18. 2023Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Boundscited by 6
  19. 2023Distributed Personalized Empirical Risk Minimizationcited by 6
  20. 2024Reawakening knowledge: Anticipatory recovery from catastrophic interference via structured trainingcited by 6
  21. 2024Stochastic Optimization Algorithms for Instrumental Variable Regression with Streaming Datacited by 4
  22. 2023On the Training Instability of Shuffling SGD with Batch Normalizationcited by 3
  23. 2023RINAS: Training with Dataset Shuffling Can Be General and Fastcited by 3
  24. 2024Asynchronous Federated Learning: A Scalable Approach for Decentralized Machine Learningcited by 3
  25. 2021Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimizationcited by 2
  26. 2022On the Convergence to a Global Solution of Shuffling-Type Gradient Algorithmscited by 2
  27. 2023Convergence of Sign-based Random Reshuffling Algorithms for Nonconvex Optimizationcited by 2
  28. 2024Demystifying SGD with Doubly Stochastic Gradientscited by 2
  29. 2024Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGDcited by 2
  30. 2026Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimizationcited by 2
  31. 2026Random Reshuffling Dominates Stochastic Gradient Descentcited by 2
  32. 2023Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Conditioncited by 1
  33. 2024Shuffling Momentum Gradient Algorithm for Convex Optimizationcited by 1
  34. 2024A Generalized Version of Chung's Lemma and its Applicationscited by 1
  35. 2026Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGDcited by 1
  36. 2026A Resolution of the SS--RS--GD Inequalitiescited by 1
  37. 2026Sparse Data Augmentation for Optimization with Provable Guaranteescited by 1
  38. 2022Convergence of ease-controlled Random Reshuffling gradient Algorithms under Lipschitz smoothnesscited by 0

50 most cited of 58 All 58 (JSON)