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\"older-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.