Metraipolis › archive › dc_85be67231b47
On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization — arXiv:2610.19652
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.19652
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T14:17:42.709Z
- SHA-256 of the archived text
134d71d4637d840729d1eadb7b1d828bd02bf2f26493d6f6f00164aed3fead81- Stable URL of this page
https://metraipolis.com/documento/dc_85be67231b47
How to cite
On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization — arXiv:2610.19652 — arXiv (en), https://arxiv.org/abs/2610.19652 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_85be67231b47 (Metraipolis archive dc_85be67231b47, sha256 134d71d4637d840729d1eadb7b1d828bd02bf2f26493d6f6f00164aed3fead81)
BibTeX
@misc{dc85be67231b47,
title = {On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization — arXiv:2610.19652},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.19652},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_85be67231b47; sha256 134d71d4637d840729d1eadb7b1d828bd02bf2f26493d6f6f00164aed3fead81},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19652. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Recent work has sought to transfer first-order nonconvex optimization guarantees to zeroth-order methods through gradient estimators, typically incurring a factor linear in $d$. \citet{kornowski2024} obtained an $\mathcal{O}(d\delta^{-1}\epsilon^{-3})$ oracle complexity for nonsmooth nonconvex optimization and asked whether its dependence on all three parameters is jointly optimal. Although the dimension dependence and the first-order dependence on $(\delta,\epsilon)$ are separately known to be unavoidable, a matching zeroth-order lower bound has remained open. We answer this question in the unrestricted full-space setting. For smooth stochastic nonconvex optimization, we establish a scalar-oracle lower bound of $\Omega\!\left(dL_0^2\min\{\Delta H,L_0^2\}/\epsilon^4\right)$ assuming a smooth, globally lower-bounded population objective and a second-moment bound on sample Lipschitz constants. A smooth reduction then yields a lower bound for Goldstein stationarity, proving the joint minimax optimality of the dependence on $(d,\delta,\epsilon)$ under explicit high-dimensional and small-accuracy conditions. Crucially, our results allow algorithms to query arbitrary points in $\mathbb{R}^d$, adaptively select sample-function labels, reuse the same sampled function at any number of locations, and output points without spatial restrictions. Thus, unlike lower bounds based on bounded query regions or fresh evaluation noise, our guarantees apply to a fully adaptive, reusable-sample scalar oracle. We also establish a separate noiseless exact-value lower bound against randomized algorithms, and hence also against deterministic methods. Our proof combines a globally defined sequential nonconvex construction with an exact Gaussian scalar channel, multistage random-field estimates, and an antithetic finite-sample realization that preserves information hardness under adaptive reuse.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.19652 — 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-15T13:53:35.626Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).