Minimax Call Complexity, Rounds and Admissible Noise in Zeroth-Order Optimization of Highly Smooth Functions

Abstract

We study zeroth-order optimization of convex and strongly convex functions with H\"older smoothness of order $\beta>2$ from values corrupted by random noise with bias independent of the method's random directions, a Lipschitz systematic error and a bounded adversarial error. We measure the number of function evaluations (calls), of sequential rounds of parallel calls, and the largest tolerable systematic and adversarial errors. For strongly convex functions with a bounded Hessian, we prove a lower bound of order $d^2\varepsilon^{-\beta/(\beta-1)}$ on the number of calls, where $d$ is the dimension and $\varepsilon$ the accuracy, and find the sharp power of $d$ under the stronger Hilbert--Schmidt smoothness for all $\beta>2$. An accelerated finite-difference method attains them in $O(\sqrt{\kappa}\log(1/\varepsilon))$ rounds for condition number $\kappa$, like Nesterov's method with exact gradients, and tolerates the optimal systematic and, up to logarithms, adversarial errors; rate-optimal methods need $\Omega(\log d)$ rounds. The same number of calls is attained when the Hessian grows at most linearly with the gradient and, for centered noise, without an upper bound on the Hessian, also in logarithmically many rounds. For convex functions, our lower bound improves the known one polynomially in $d$ and is tight at the curvature of the hard instances; the systematic level is again optimal. These bounds extend to general norms and constraints; on the $\ell_1$ ball, mirror descent needs calls nearly linear in $d$. Experiments confirm the theory.