Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls

Abstract

We prove a joint stochastic zeroth-order lower bound for Goldstein stationarity on a Euclidean query ball, even when the ball is guaranteed to contain a stationary point. In dimension $d$, let $f=\mathbb{E}[F(\cdot;\xi)]$, assume $\mathbb{E}[\operatorname{Lip}(F(\cdot;\xi))^2]\le L_0^2$, and bound the initial objective gap over the ball by $\Delta$. For neighborhood radius $\delta>0$ and residual tolerance $\varepsilon>0$, our smooth hard family requires $\Omega(dL_0^2\Delta/(\delta\varepsilon^3))$ scalar evaluations for success probability $1/2$, against randomized adaptive algorithms that may retain and repeatedly query each sampled function. The result holds for $\varepsilon\le cL_0$, $\Delta\ge C\delta\varepsilon$, and $d\ge C[1+\log(2+\Delta L_0^2/(\delta\varepsilon^3))]$, on a constructed ball of radius $\Theta(\Delta/\varepsilon)$. A sequence of localized regions forces repeated direction estimation, and an adaptive Gaussian posterior argument controls sample reuse. The result establishes a joint dimension and accuracy obstruction on solvable bounded-domain instances. The gap is local to the query ball; a matching minimax characterization at a common radius and the corresponding unrestricted global-gap lower bound remain open here.