Metraipolis › archive › dc_715006ba0876
Asymptotic Lower Bounds for Continuous Optimization — arXiv:2609.34303
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34303
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T23:06:43.466Z
- SHA-256 of the archived text
2730c497670e05c1c2ba939b5f4bb32b57d17bf815049ce542fec6389a37bb14- Stable URL of this page
https://metraipolis.com/documento/dc_715006ba0876
How to cite
Asymptotic Lower Bounds for Continuous Optimization — arXiv:2609.34303 — arXiv (en), https://arxiv.org/abs/2609.34303 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_715006ba0876 (Metraipolis archive dc_715006ba0876, sha256 2730c497670e05c1c2ba939b5f4bb32b57d17bf815049ce542fec6389a37bb14)
BibTeX
@misc{dc715006ba0876,
title = {Asymptotic Lower Bounds for Continuous Optimization — arXiv:2609.34303},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34303},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_715006ba0876; sha256 2730c497670e05c1c2ba939b5f4bb32b57d17bf815049ce542fec6389a37bb14},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34303. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Nonasymptotic convergence rates for optimization problems have been extensively studied across a wide range of settings, with carefully constructed worst-case instances establishing matching lower bounds for many algorithm classes. Recent work has shown, however, that these rates can often be improved in the asymptotic regime, while the corresponding asymptotic lower bounds remain largely unknown. We propose a general technique for converting existing nonasymptotic lower bound constructions into asymptotic lower bounds on Hilbert spaces. This allows us to show that several known asymptotic convergence upper bounds in Hilbert spaces are tight. In particular, we recover tightness of the $o(n^{-2})$ suboptimality guarantee for accelerated gradient descent on smooth convex functions \cite{attouch2016rate}, as well as the $o(n^{-1/2})$ suboptimality guarantee for gradient descent on smooth nonconvex functions \cite{gratton2025refining}. For stochastic convex optimization, we also develop a method that achieves an $o(n^{-1/2})$ suboptimality guarantee in finite dimensions, and prove a matching one-dimensional lower bound.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.34303 — 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-07T22:42:39.256Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).