On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization
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 𝒪(dδ−1ε−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 (δ,ε) 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 Ω (dL02min{ΔH,L02}/ε4) 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,δ,ε) under explicit high-dimensional and small-accuracy conditions. Crucially, our results allow algorithms to query arbitrary points in ℝ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.
Related
- Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls
- Langevin for Nonconvex Optimization: Exact, Inexact and Zeroth-Order
- Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
- Tight Lower Bounds for Stochastic Nonconvex-Strongly-Concave Minimax Optimization
- Lower Bounds for Nonconvex-Concave Minimax Optimization
BibTeX
@misc{xia2026global,
title = {{On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization}},
author = {Yuxuan Xia and Xiao-Tong Yuan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19652},
eprint = {2610.19652},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19652},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization
AU - Yuxuan Xia
AU - Xiao-Tong Yuan
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19652
UR - https://arxiv.org/abs/2610.19652
AB - 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 𝒪(dδ^−1ε^−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 (δ,ε) 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 Ω (dL_0^2min{ΔH,L_0^2}/ε^4) 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,δ,ε) under explicit high-dimensional and small-accuracy conditions. Crucially, our results allow algorithms to query arbitrary points in ℝ^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.
ER -