arXiv：cs.LG· Yuxuan Xia, Xiao-Tong Yuan·· 4 小时前
零阶非凸优化中全局联合下界研究：arXiv 论文给出 (d,δ,ε) 联合最优性证明
On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization
AI 导读
一篇 arXiv 论文在无限制全空间设定下回答了零阶非凸优化的开放问题，证明在显式高维与小精度条件下，对 (d, δ, ε) 的依赖具有联合极小极大最优性。针对光滑随机非凸优化，作者给出标量 oracle 下界 Ω(dL₀²min{ΔH, L₀²}/ε⁴)；经光滑归约后得到 Goldstein 平稳性下界，适用于可自适应、可复用样本的标量 oracle。论文还建立了针对随机算法的无噪声精确值下界。
正文
Abstract: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.
| Subjects: | Machine Learning (cs.LG); Machine Learning (stat.ML) |
| Cite as: | arXiv:2610.19652 [cs.LG] |
| (or arXiv:2610.19652v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.19652 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Xiao-Tong Yuan [view email]
[v1]
Wed, 14 Oct 2026 06:20:12 UTC (76 KB)
来源：arXiv：cs.LG · arxiv.org