Metraipolis › archive › dc_498c30748edb

Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions — arXiv:2609.04578

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.04578
License (as archived)
CC0-1.0
Archived
2026-10-16T22:59:35.968Z
SHA-256 of the archived text
0ca9e120b6040117d11671f6d5f63c74dcd6918d325a51a900fb78fa5c832631
Stable URL of this page
https://metraipolis.com/documento/dc_498c30748edb

How to cite

Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions — arXiv:2609.04578 — arXiv (en), https://arxiv.org/abs/2609.04578 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_498c30748edb (Metraipolis archive dc_498c30748edb, sha256 0ca9e120b6040117d11671f6d5f63c74dcd6918d325a51a900fb78fa5c832631)
BibTeX
@misc{dc498c30748edb,
  title = {Centered Permutation Prefixes for SGD with Random Reshuffling: Sharp Rates, Hölder Geometry, and Composite Proximal Extensions — arXiv:2609.04578},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.04578},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_498c30748edb; sha256 0ca9e120b6040117d11671f6d5f63c74dcd6918d325a51a900fb78fa5c832631},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04578. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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ölder-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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-07 in cs.LG).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.04578 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T22:31:32.234Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).