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

arXiv:2609.04578v1 Announce Type: cross Abstract: We study stochastic gradient descent with random reshuffling for finite sums [ F(x)=frac1nsum_{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-Holder-continuous average Hessian adds only widetilde O(n^{1+nu}T^{-2-2nu}), so every nuge 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^agger for the composite minimizer and eta_star=|nabla F(x^agger)|, we prove [ mathbb E|y_K-x^agger|^2 =widetilde O!left( frac{eta_star^2}{K^2} +T^{-2}+n^2T^{-3} +n^{1+nu}T^{-2-2nu} right). ] For nuge 1/2, we show that the eta_star^2/K^2 splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.

Source: arXiv cs.LG | 2026-09-07