Near-Optimal Lower Bounds for Exact Zeroth-Order Convex Optimization

The fundamental oracle limits of exact function value access remain poorly understood in zeroth-order optimization: even for canonical convex problems, the optimal joint dependence on dimension $d$ and accuracy $\epsilon$ has remained unresolved. We resolve this question for arbitrary adaptive randomized algorithms minimizing nonsmooth $L_0$-Lipschitz convex functions over the $d$-dimensional Euclidean unit ball, where each query returns only the exact scalar value $f(\mathbf{x})$ of a fixed objective. With universal $L_0>0$, let $T_{\epsilon }$ denote the minimum number of queries required to return an $\epsilon$-suboptimal point with probability at least $1\mathrm{/}2$, uniformly over the function class. We prove that $$T_{\epsilon }\ge c\frac{d\min \{d,{\epsilon }^{-2}\}}{\log \text{\hspace{0.17em}⁣}(e\min \{d,{\epsilon }^{-2}\})},$$ for all $d\ge d_0$ and $0<\epsilon \le {\epsilon }_0$, for universal constants $c,{\epsilon }_0>0$ and $d_0\in \mathbb{N}$. In the low-accuracy regime $\epsilon \ge d^{-1\mathrm{/}2}$, this matches the $O(d{\epsilon }^{-2})$ two-point exact value upper bound up to a logarithmic factor. In the high-accuracy regime $\epsilon \le d^{-1\mathrm{/}2}$, the lower bound saturates at $\mathrm{\Omega }(d^2\mathrm{/}\log (ed))$, independently of $\epsilon$, matching the $\tilde{O}(d^2)$ evaluation oracle upper bound up to polylogarithmic factors. The proof uses a random support function hard family and develops a posterior mean energy method for adaptive exact max observations, in place of first-order zero chain constructions and noise based transcript inequalities.