# Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, H"older Geometry, and Composite Proximal Extensions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 22 references that are in the map.
- First posted on arXiv 4 Sep 2026.

## Builds on (most cited first, 20 of 20)

- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Random Shuffling Beats SGD after Finite Epochs](https://mlsanity.com/paper/1806.10077/) (2018)
- [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)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond](https://mlsanity.com/paper/2303.07160/) (2023)
- [GraB: Finding Provably Better Data Permutations than Random Reshuffling](https://mlsanity.com/paper/2205.10733/) (2022)
- [On the Last-Iterate Convergence of Shuffling Gradient Methods](https://mlsanity.com/paper/2403.07723/) (2024)
- [Stochastic Extragradient with Random Reshuffling: Improved Convergence for Variational Inequalities](https://mlsanity.com/paper/2403.07148/) (2024)
- [A New Random Reshuffling Method for Nonsmooth Nonconvex Finite-sum Optimization](https://mlsanity.com/paper/2312.01047/) (2023)
- [Proximal random reshuffling under local Lipschitz continuity](https://mlsanity.com/paper/2408.07182/) (2024)
- [Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization](https://mlsanity.com/paper/2505.23056/) (2025)
- [Distributed Random Reshuffling Methods with Improved Convergence](https://mlsanity.com/paper/2306.12037/) (2023)
- [Stochastic Extragradient with Flip-Flop Shuffling & Anchoring: Provable Improvements](https://mlsanity.com/paper/2501.00511/) (2024)
- [Learning to Shuffle: Block Reshuffling and Reversal Schemes for Stochastic Optimization](https://mlsanity.com/paper/2604.00260/) (2026)
- [Random Reshuffling Dominates Stochastic Gradient Descent](https://mlsanity.com/paper/2606.32005/) (2026)

## Abstract (arXiv)

We study stochastic gradient descent with random reshuffling for finite sums [ F(x)=frac1nsumi=1n fi(x). ] For fresh reshuffling with a constant component stepsize, if each fi has an L-Lipschitz gradient and the average F is μ-strongly convex with a Lipschitz-continuous Hessian, we prove the last-epoch rate [ mathbb E[F(yK)-F(x_star)] =widetilde O!left(T-2+n2T-3right), qquad T=nK, ] matching the known quadratic lower bound in its (n,K)-dependence. The components may be nonconvex, and no componentwise Hessian continuity or separate bounded-iterate assumption is required. More generally, a nu-H"older-continuous average Hessian adds only widetilde O(n1+nuT-2-2nu), so every nu≥ 1/2 preserves the quadratic rate. Under convex components, a decreasing-stepsize result removes the large-epoch requirement and recovers the same two-term scale once nK exceeds the condition-number scale. We also analyze epoch-wise ProxRR for mathcal P=F+psi. Writing x^dagger for the composite minimizer and β_star=|nabla F(x^dagger)|, we prove [ mathbb E|yK-x^dagger|2 =widetilde O!left( fracβ_star2K2 +T-2+n2T-3 +n1+nuT-2-2nu right). ] For nu≥ 1/2, we show that the β_star2/K2 splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.