# On the Last-Iterate Convergence of Shuffling Gradient Methods

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

## 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 (most cited first, 30 of 31)

- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Tight Analyses for Non-Smooth Stochastic Gradient Descent](https://mlsanity.com/paper/1812.05217/) (2018)
- [SGD and Hogwild! Convergence Without the Bounded Gradients Assumption](https://mlsanity.com/paper/1802.03801/) (2018)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [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)
- [Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods](https://mlsanity.com/paper/2312.08531/) (2023)
- [Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond](https://mlsanity.com/paper/2110.10342/) (2021)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Convergence Rate of Incremental Gradient and Newton Methods](https://mlsanity.com/paper/1510.08562/) (2015)
- [Exact convergence rate of the last iterate in subgradient methods](https://mlsanity.com/paper/2307.11134/) (2023)
- [Convergence Analysis of Distributed Stochastic Gradient Descent with Shuffling](https://mlsanity.com/paper/1709.10432/) (2017)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (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)
- [Convergence of Random Reshuffling Under The Kurdyka-Lojasiewicz Inequality](https://mlsanity.com/paper/2110.04926/) (2021)
- [Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods](https://mlsanity.com/paper/2202.01838/) (2022)
- [Stochastic Learning under Random Reshuffling with Constant Step-sizes](https://mlsanity.com/paper/1803.07964/) (2018)
- [Federated Random Reshuffling with Compression and Variance Reduction](https://mlsanity.com/paper/2205.03914/) (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)
- [SGDA with shuffling: faster convergence for nonconvex-PL minimax optimization](https://mlsanity.com/paper/2210.05995/) (2022)
- [Incremental Methods for Weakly Convex Optimization](https://mlsanity.com/paper/1907.11687/) (2019)
- [Empirical Risk Minimization with Shuffled SGD: A Primal-Dual Perspective and Improved Bounds](https://mlsanity.com/paper/2306.12498/) (2023)
- [High Probability Guarantees for Random Reshuffling](https://mlsanity.com/paper/2311.11841/) (2023)

## Built on by (most cited first, 11 of 11)

- [From Continual Learning to SGD and Back: Better Rates for Continual Linear Models](https://mlsanity.com/paper/2504.04579/) (2025)
- [Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime](https://mlsanity.com/paper/2507.11274/) (2025)
- [Privacy of the last iterate in cyclically-sampled DP-SGD on nonconvex composite losses](https://mlsanity.com/paper/2407.05237/) (2024)
- [Gradient Descent's Last Iterate is Often (slightly) Suboptimal](https://mlsanity.com/paper/2604.13870/) (2026)
- [Random Reshuffling Dominates Stochastic Gradient Descent](https://mlsanity.com/paper/2606.32005/) (2026)
- [Adjusted Shuffling SARAH: Advancing Complexity Analysis via Dynamic Gradient Weighting](https://mlsanity.com/paper/2506.12444/) (2025)
- [On the Limits of Momentum in Decentralized and Federated Optimization](https://mlsanity.com/paper/2511.20168/) (2025)
- [New Hybrid Fine-Tuning Paradigm for LLMs: Algorithm Design and Convergence Analysis Framework](https://mlsanity.com/paper/2604.09940/) (2026)
- [Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensions](https://mlsanity.com/paper/2609.04578/) (2026)
- [Last-Iterate Convergence Rate of Normalized Gradient Descent under H"older Smoothness](https://mlsanity.com/paper/2610.06070/) (2026)
- [Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent](https://mlsanity.com/paper/2610.19444/) (2026)

## 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.