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

Abstract:We study stochastic gradient descent with random reshuffling for finite sums \[ F(x)=\frac1n\sum_{i=1}^n f_i(x). \] For fresh reshuffling with a constant component stepsize, if each $f_i$ has an $L$-Lipschitz gradient and the average $F$ is $\mu$-strongly convex with a Lipschitz-continuous Hessian, we prove the last-epoch rate \[ \mathbb E[F(y_K)-F(x_\star)] =\widetilde O\!\left(T^{-2}+n^2T^{-3}\right), \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ölder-continuous average Hessian adds only $\widetilde O(n^{1+\nu}T^{-2-2\nu})$, so every $\nu\ge 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 $\beta_\star=\|\nabla F(x^\dagger)\|$, we prove \[ \mathbb E\|y_K-x^\dagger\|^2 =\widetilde O\!\left( \frac{\beta_\star^2}{K^2} +T^{-2}+n^2T^{-3} +n^{1+\nu}T^{-2-2\nu} \right). \] For $\nu\ge 1/2$, we show that the $\beta_\star^2/K^2$ splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.

Optimization and Control (math.OC); Machine Learning (cs.LG)

arXiv:2609.04578 [math.OC]

(or arXiv:2609.04578v1 [math.OC] for this version)

https://doi.org/10.48550/arXiv.2609.04578 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.