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 $\mathcal{O}(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 $Ω\!\left(dL_0^2\min\{ΔH,L_0^2\}/ε^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,δ,ε)$ 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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper establishes a joint minimax lower bound for stochastic zeroth-order nonconvex optimization, proving that the dependence on dimension, smoothness, and accuracy is jointly optimal under a fully adaptive, reusable-sample scalar oracle model. By constructing a global zero-chain with hidden workspace directions and employing information-theoretic tools to control adaptive sample reuse, the authors demonstrate that the oracle complexity scales as $\Omega(d L_0^2 \min\{\Delta H, L_0^2\} / \epsilon^4)$, resolving a key open question in the field and providing a rigorous theoretical limit for gradient-free optimization methods.
Methodology
The paper addresses a significant gap in zeroth-order optimization theory: establishing a joint lower bound for the dependence on dimension ($d$), smoothness ($H$), and accuracy ($\epsilon$) in the stochastic nonconvex setting. The authors propose a novel construction that combines a global zero-chain geometry with a "moving well" mechanism to force sequential information acquisition. The core technical contribution is the proof that even with a fully adaptive, reusable-sample scalar oracle (where algorithms can query any point and reuse sample functions), the complexity scales as $\Omega(d L_0^2 \min\{\Delta H, L_0^2\} / \epsilon^4)$. The methodology is rigorous, utilizing Gaussian process representations, antithetic sampling to create a finite static oracle, and information-theoretic arguments (specifically spherical concentration and log-Sobolev inequalities) to bound the information gain per query. The construction is complex, involving careful management of global Lipschitz moments and spatial cutoffs to ensure the hardness persists globally rather than just locally.
Results & evaluation
As a pure theory paper, there are no empirical experiments. The "evaluation" is the mathematical proof of the lower bound. The rigor of the proof is the primary metric of quality here. The paper provides detailed appendices (referenced but not fully visible in the snippet, though the main text outlines the structure) to support the claims. The lack of empirical validation is standard for this subcategory of optimization theory.
Reproducibility
The paper is highly reproducible in the sense that the mathematical results are deterministic and verifiable by other theorists. There is no code to reproduce. The constants and conditions are explicitly stated, allowing for independent verification of the bounds.
Limitations
The lower bound holds under specific high-dimensional and small-accuracy conditions (explicitly stated as $d \ge C(B/\epsilon^2)(2+BL_0^2/\epsilon^4)$). The bound is for the smooth stochastic case, and the extension to nonsmooth Goldstein stationarity is via a reduction, which may not be tight in all regimes. The construction is quite intricate, making it difficult to generalize to other oracle models without significant modification. The constants involved are conservative (e.g., $2^{128}$), which limits immediate practical utility for tight algorithm design but is typical for lower bound constructions.
Broader impact
This paper settles an open question regarding the joint optimality of zeroth-order optimization complexities. It provides a definitive answer to whether the linear dependence on dimension $d$ is unavoidable in the stochastic nonconvex setting when using scalar oracles. This has implications for the design of gradient-free optimization algorithms, confirming that one cannot hope for sub-linear dimension dependence in the worst case under these assumptions. It strengthens the theoretical foundation for understanding the limitations of zeroth-order methods compared to first-order methods. The paper establishes a joint minimax lower bound for stochastic zeroth-order nonconvex optimization, proving that the dependence on dimension, smoothness, and accuracy is jointly optimal under a fully adaptive, reusable-sample scalar oracle model. By constructing a global zero-chain with hidden workspace directions and employing information-theoretic tools to control adaptive sample reuse, the authors demonstrate that the oracle complexity scales as $\Omega(d L_0^2 \min\{\Delta H, L_0^2\} / \epsilon^4)$, resolving a key open question in the field and providing a rigorous theoretical limit for gradient-free optimization methods.
Author of this paper? Send a correction.