On Global Joint Lower Bounds in Zeroth-Order Nonconvex Optimization

Abstract

Must the dimension and accuracy costs of zeroth-order optimization multiply? Global upper bounds for smooth stochastic nonconvex optimization scale as $O(d{\epsilon }^{-4})$, with both factors separately necessary. We show that their product is unavoidable. We establish an $\Omega (d{\epsilon }^{-4})$ lower bound for smooth stochastic nonconvex optimization, yielding an $\Omega (d{\delta }^{-1}{\epsilon }^{-3})$ bound for nonsmooth Goldstein stationarity. Both match the best-known full-space upper bounds, establishing joint minimax optimality in dimension and accuracy. These bounds hold against fully adaptive randomized algorithms with unrestricted queries and outputs, even under arbitrary sample reuse. As a byproduct, we establish noiseless exact-value lower bounds for both smooth and Goldstein stationarity, even against randomized algorithms.