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

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.