Metraipolis › archive › dc_06b0e1a700ef

Acceleration Survives Heavy Tails and Generalized Smoothness — arXiv:2610.23301

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.23301
License (as archived)
CC0-1.0
Archived
2026-10-19T09:37:46.685Z
SHA-256 of the archived text
0eeda00eb327ba98a2491e6cbc782b05193f29b7b4aaecac918dc2ca70f9e5c8
Stable URL of this page
https://metraipolis.com/documento/dc_06b0e1a700ef

How to cite

Acceleration Survives Heavy Tails and Generalized Smoothness — arXiv:2610.23301 — arXiv (en), https://arxiv.org/abs/2610.23301 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_06b0e1a700ef (Metraipolis archive dc_06b0e1a700ef, sha256 0eeda00eb327ba98a2491e6cbc782b05193f29b7b4aaecac918dc2ca70f9e5c8)
BibTeX
@misc{dc06b0e1a700ef,
  title = {Acceleration Survives Heavy Tails and Generalized Smoothness — arXiv:2610.23301},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.23301},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_06b0e1a700ef; sha256 0eeda00eb327ba98a2491e6cbc782b05193f29b7b4aaecac918dc2ca70f9e5c8},
  year = {2026}
}

Archived text

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

We establish high-probability accelerated convergence guarantees for convex $(L_0,L_1)$-smooth optimization with unbiased stochastic gradients under heavy-tailed noise, assuming a central $\alpha$-th noise moment bounded by $\sigma^\alpha$, $\alpha\in(1,2]$. Such guarantees are known under classical $L$-smoothness, but extending them through localization over an $O(R)$-radius ball may introduce an $e^{O(L_1R)}$ factor. We avoid this dependence in two ways. First, a two-phase scheme uses \algname{Clip-SGD} to reach a low-curvature regime, after which clipped stochastic similar triangles (\algname{Clip-SSTM}) attains, with probability at least $1-\delta$, $f(y_K)-f^\star\le\widetilde{\mathcal O}\big(L_0R^2/K^2+\sigma RK^{-(\alpha-1)/\alpha}\big),$ where $R$ bounds the distance from the Phase-II starting point to a minimizer. Second, a modified deterministic weight schedule allows \algname{Clip-SSTM} to start directly from the initial point, controlling the high-curvature transient before recovering acceleration. With the prescribed initialization, both approaches recover the classical accelerated rate, with $L_1$ confined to an accuracy-independent transient, up to logarithmic factors. The two-phase analysis uses two coupled potentials to preserve the low-curvature regime despite momentum; the one-phase analysis controls the initial high-curvature regime using a modified version of the classical SSTM weight schedule.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.23301 — 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-19T09:33:44.738Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).