mlsanityData to 14 Oct 2026

On the Last-Iterate Convergence of Shuffling Gradient Methods

arXiv 2403.07723 ↗First posted 12 Mar 2024cs.LG math.OC stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

Shuffling gradient methods are widely used in modern machine learning tasks and include three popular implementations: Random Reshuffle (RR), Shuffle Once (SO), and Incremental Gradient (IG). Compared to the empirical success, the theoretical guarantee of shuffling gradient methods was not well-understood for a long time. Until recently, the convergence rates had just been established for the average iterate for convex functions and the last iterate for strongly convex problems (using squared distance as the metric). However, when using the function value gap as the convergence criterion, existing theories cannot interpret the good performance of the last iterate in different settings (e.g., constrained optimization). To bridge this gap between practice and theory, we prove the first last-iterate convergence rates for shuffling gradient methods with respect to the objective value even without strong convexity. Our new results either (nearly) match the existing last-iterate lower bounds or are as fast as the previous best upper bounds for the average iterate.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 31 of its 53 references that are in the map. First posted on arXiv 12 Mar 2024.

Builds on

31 of 53 references.

References · 31

  1. 2020Random Reshuffling: Simple Analysis with Vast Improvementscited by 115
  2. 2018Tight Analyses for Non-Smooth Stochastic Gradient Descentcited by 97
  3. 2018SGD and Hogwild! Convergence Without the Bounded Gradients Assumptioncited by 95
  4. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  5. 2019How Good is SGD with Random Shuffling?cited by 64
  6. 2019SGD without Replacement: Sharper Rates for General Smooth Convex Functionscited by 61
  7. 2020A Unified Convergence Analysis for Shuffling-Type Gradient Methodscited by 58
  8. 2020SGD with shuffling: optimal rates without component convexity and large epoch requirementscited by 58
  9. 2020Closing the convergence gap of SGD without replacementcited by 57
  10. 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 45
  11. 2023Revisiting the Last-Iterate Convergence of Stochastic Gradient Methodscited by 38
  12. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 36
19 more
  1. 2021Proximal and Federated Random Reshufflingcited by 33
  2. 2015Convergence Rate of Incremental Gradient and Newton Methodscited by 27
  3. 2023Exact convergence rate of the last iterate in subgradient methodscited by 25
  4. 2017Convergence Analysis of Distributed Stochastic Gradient Descent with Shufflingcited by 23
  5. 2023Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyondcited 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. 2021Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequalitycited by 16
  10. 2022Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methodscited by 16
  11. 2018Stochastic Learning under Random Reshuffling with Constant Step-sizescited by 15
  12. 2022Federated Random Reshuffling with Compression and Variance Reductioncited by 12
  13. 2022Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimizationcited by 10
  14. 2024Last Iterate Convergence of Incremental Methods and Applications in Continual Learningcited by 10
  15. 2022SGDA with shuffling: faster convergence for nonconvex-PL minimax optimizationcited by 8
  16. 2019Incremental Methods for Weakly Convex Optimizationcited by 7
  17. 2023Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Boundscited by 6
  18. 2023High Probability Guarantees for Random Reshufflingcited by 5
  19. 2020Incremental Without Replacement Sampling in Nonconvex Optimizationcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 6.

11 papers.

  1. 2025From Continual Learning to SGD and Back: Better Rates for Continual Linear Modelscited by 12
  2. 2025Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regimecited by 12
  3. 2024Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite lossescited by 6
  4. 2026Gradient Descent's Last Iterate is Often (slightly) Suboptimalcited by 4
  5. 2026Random Reshuffling Dominates Stochastic Gradient Descentcited by 2
  6. 2025Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weightingcited by 0
  7. 2025On the Limits of Momentum in Decentralized and Federated Optimizationcited by 0
  8. 2026New Hybrid Fine-Tuning Paradigm for LLMs: Algorithm Design and Convergence Analysis Frameworkcited by 0
  9. 2026Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensionscited by 0
  10. 2026Last-Iterate Convergence Rate of Normalized Gradient Descent under H"older Smoothnesscited by 0
  11. 2026Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descentcited by 0