Metraipolis › archive › dc_0f8d896ea7d9
A stochastic subgradient method with optimal failure exponent — arXiv:2609.37425
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.37425
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:00:11.981Z
- SHA-256 of the archived text
b71d913966ef83ef01ab1481ce9befc60bf205c7465e4721db4203bf909262c6- Stable URL of this page
https://metraipolis.com/documento/dc_0f8d896ea7d9
How to cite
A stochastic subgradient method with optimal failure exponent — arXiv:2609.37425 — arXiv (en), https://arxiv.org/abs/2609.37425 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0f8d896ea7d9 (Metraipolis archive dc_0f8d896ea7d9, sha256 b71d913966ef83ef01ab1481ce9befc60bf205c7465e4721db4203bf909262c6)
BibTeX
@misc{dc0f8d896ea7d9,
title = {A stochastic subgradient method with optimal failure exponent — arXiv:2609.37425},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.37425},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0f8d896ea7d9; sha256 b71d913966ef83ef01ab1481ce9befc60bf205c7465e4721db4203bf909262c6},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37425. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Fix a target accuracy $\varepsilon$, a gradient-noise level $s$, and a horizon $N$. We wish to design algorithms which minimize the probability of observing a suboptimality gap which exceeds the target accuracy, i.e., $\mathcal{E}_N = -\log \sup_{f,P} \mathbb{P}_P(f(x_A) - f_\star \ge \varepsilon)$, with the noise law $P$ known only to be sub-Gaussian. We single out a uniformly averaged schedule which is harmonic (of the form $h_k = R^2/(\varepsilon (N+m-k))$) and prove, via an optimized exponential supermartingale argument, that it attains the optimal exponent $\mathcal{E}_N^\star = \varepsilon^2 N (1+o(1))/(2R^2 s^2)$. Optimality is certified by a matching impossibility result: under Gaussian noise, a gradient-masking change of measure caps the exponent of every algorithm at the same leading order. In a small-noise limit, our setting degenerates into the adversarial-error model of Gösgens and van Parys (2025) for subgradient methods.
Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-30 in stat.ML).
Categorie arXiv: Optimization and Control (math.OC) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2609.37425 — 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-07T17:33:44.757Z dalla pagina https://arxiv.org/catchup/stat.ML/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).