Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions
Abstract
We study stochastic gradient descent with random reshuffling for finite sums F(x)=1/n∑i=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 𝔼[F(yK)−F(x⋆)] =Õ (T−2+n2T−3), 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 ν-Hölder-continuous average Hessian adds only Õ(n1+νT−2−2ν), so every ν≥ 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 𝒫=F+ψ. Writing x† for the composite minimizer and β⋆=|∇ F(x†)|, we prove 𝔼|yK−x†|2 =Õ ( β⋆2/K2 +T−2+n2T−3 +n1+νT−2−2ν ). For ν≥ 1/2, we show that the β⋆2/K2 splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.
Related
- Prefixes of Coxeter elements are Coxeter elements of the reflection subgroups they generate
- A lower bound on the density of prefixes with maximal palindromic length
- Conformal Certification of Reasoning Trace Prefixes
- Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
- Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent
BibTeX
@misc{li2026centered,
title = {{Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions}},
author = {Jiaxiang Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04578},
eprint = {2609.04578},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04578},
}
RIS
TY - UNPB
TI - Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions
AU - Jiaxiang Li
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.04578
UR - https://arxiv.org/abs/2609.04578
AB - We study stochastic gradient descent with random reshuffling for finite sums F(x)=1/n∑_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 μ-strongly convex with a Lipschitz-continuous Hessian, we prove the last-epoch rate 𝔼[F(y_K)−F(x_⋆)] =Õ (T^−2+n^2T^−3), 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 ν-Hölder-continuous average Hessian adds only Õ(n^1+νT^−2−2ν), so every ν≥ 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 𝒫=F+ψ. Writing x^† for the composite minimizer and β_⋆=|∇ F(x^†)|, we prove 𝔼|y_K−x^†|^2 =Õ ( β_⋆^2/K^2 +T^−2+n^2T^−3 +n^1+νT^−2−2ν ). For ν≥ 1/2, we show that the β_⋆^2/K^2 splitting term is unavoidable and obtain a matching lower bound up to logarithms in the stated constant-stepsize regime.
ER -