mlsanityData to 7 Oct 2026

Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond

arXiv 2303.07160 ↗First posted 13 Mar 2023cs.LG math.OC stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

We study convergence lower bounds of without-replacement stochastic gradient descent (SGD) for solving smooth (strongly-)convex finite-sum minimization problems. Unlike most existing results focusing on final iterate lower bounds in terms of the number of components n and the number of epochs K, we seek bounds for arbitrary weighted average iterates that are tight in all factors including the condition number kappa. For SGD with Random Reshuffling, we present lower bounds that have tighter kappa dependencies than existing bounds. Our results are the first to perfectly close the gap between lower and upper bounds for weighted average iterates in both strongly-convex and convex cases. We also prove weighted average iterate lower bounds for arbitrary permutation-based SGD, which apply to all variants that carefully choose the best permutation. Our bounds improve the existing bounds in factors of n and kappa and thereby match the upper bounds shown for a recently proposed algorithm called GraB.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 17 of its 39 references that are in the map. First posted on arXiv 13 Mar 2023.

Builds on

17 of 39 references.

References · 17

  1. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  2. 2014Convex Optimization: Algorithms and Complexitycited by 569
  3. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 112
  4. 2018Random Shuffling Beats SGD after Finite Epochscited by 66
  5. 2019How Good is SGD with Random Shuffling?cited by 63
  6. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 59
  7. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 57
  8. 2020Closing the convergence gap of SGD without replacementcited by 56
  9. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  10. 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 26
  11. 2020Discrepancy Minimization via a Self-Balancing Walkcited by 22
  12. 2022GraB: Finding Provably Better Data Permutations than Random Reshufflingcited by 18
5 more
  1. 2021Permutation-Based SGD: Is Random Optimal?cited by 16
  2. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 15
  3. 2022Nesterov Accelerated Shuffling Gradient Method for Convex Optimizationcited by 10
  4. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  5. 2016Algorithmic Discrepancy Beyond Partial Coloringcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 7; 2024: 5; 2025: 7; 2026: 2.

21 papers.

Sort:

By area:

  1. 2024Randomized Asymmetric Chain of LoRA: The First Meaningful Theoretical Framework for Low-Rank Adaptationcited by 12
  2. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  3. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 10
  4. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 10
  5. 2024On the Last-Iterate Convergence of Shuffling Gradient Methodscited by 9
  6. 2023Mini-Batch Optimization of Contrastive Losscited by 8
  7. 2023On Convergence of Incremental Gradient for Non-Convex Smooth Functionscited by 7
  8. 2025Low-Rank Thinningcited by 7
  9. 2023Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Boundscited by 6
  10. 2023High Probability Guarantees for Random Reshufflingcited by 5
  11. 2024Asynchronous Federated Learning: A Scalable Approach for Decentralized Machine Learningcited by 3
  12. 2025Randomised Splitting Methods and Stochastic Gradient Descentcited by 3
9 more
  1. 2023Distributed Random Reshuffling Methods with Improved Convergencecited by 2
  2. 2024Demystifying SGD with Doubly Stochastic Gradientscited by 2
  3. 2025Random Reshuffling for Stochastic Gradient Langevin Dynamicscited by 2
  4. 2025Rapid Overfitting of Multi-Pass Stochastic Gradient Descent in Stochastic Convex Optimizationcited by 2
  5. 2023Fast Convergence of Random Reshuffling under Over-Parameterization and the Polyak-L ojasiewicz Conditioncited by 1
  6. 2026Random Reshuffling Dominates Stochastic Gradient Descentcited by 1
  7. 2023GraB-sampler: Optimal Permutation-based SGD Data Sampler for PyTorchcited by 0
  8. 2025Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weightingcited by 0
  9. 2026Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensionscited by 0