Asymptotic Lower Bounds for Continuous Optimization

Abstract

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⁻²) 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.

Optimal Spectral Lower Bounds and Nonradial Nonlinear Asymptotic Stability of a Family of Three-Dimensional Keller--Segel Self-Similar Blow-Up Solutions
Te Li, Yuwei Sun, Kaiqiang Zhang
arXiv6 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
Weiming Ou, Xiao Wang
arXiv26 Sep 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Quantum lower bounds for convex optimization and real matrix-vector query problems
Andrew M. Childs
arXiv28 Oct 2026PreprintarXiv licenceFull textOptimisation & control Quantum physics & quantum informationarXiv
Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
Dongruo Zhou
arXiv21 Sep 2026PreprintCC BY-SA 4.0Full textOptimisation & controlarXiv
Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
Siqi Zhang, Qilong Wu, Junchi Yang
arXiv28 Sep 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{hinder2026asymptotic,
  title = {{Asymptotic Lower Bounds for Continuous Optimization}},
  author = {Oliver Hinder and Yuntian Jiang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.34303},
  eprint = {2609.34303},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.34303},
}

RIS

TY  - UNPB
TI  - Asymptotic Lower Bounds for Continuous Optimization
AU  - Oliver Hinder
AU  - Yuntian Jiang
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.34303
UR  - https://arxiv.org/abs/2609.34303
AB  - 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.
ER  -

Abstract

Related

Cite