Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions
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 $μ$-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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.04578
curl -X POST /api/v1/records/arxiv/2609.04578/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.04578/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'