Near-Optimal Exact-Value Zeroth-Order Complexity for Smooth Strongly Convex Optimization

We study deterministic adaptive optimization of globally $\beta$-smooth, $\mu$-strongly convex functions using exact scalar function values. Queries and outputs lie in $B_2^d(R)$, and the minimizer lies in $B_2^d(R\mathrm{/}2)$. Set $\kappa =\beta \mathrm{/}\mu$, $Q=\beta R^2\mathrm{/}\epsilon$, and $D_d=(d\mathrm{/}\log (ed){)}^{1\mathrm{/}3}$. For sufficiently large $d$ and $0<\epsilon \le c_{\epsilon }\beta R^2$, the minimax value complexity $N_{\epsilon }$ satisfies $$\begin{array}{rl}{\displaystyle N_{\epsilon }}& {\displaystyle \ge cd\min \{\sqrt{Q},\sqrt{\kappa },D_d\},}\\ {\displaystyle N_{\epsilon }}& {\displaystyle \le Cd\min \{\sqrt{Q},\sqrt{\kappa }[1+{\log }_{+}(Q\mathrm{/}\kappa )]\},}\end{array}$$ where $c,C,c_{\epsilon }>0$ are universal constants and ${\log }_{+}(t)=\max \{0,\log t\}$. The lower bound uses an exactly shielded smooth chain and batched delayed rotations; the upper bound combines finite differences, acceleration, and restart. When $\min \{Q,\kappa \}\le D_d^2$, these bounds match up to constants in the accuracy-dominated regime $Q\le \kappa$ and at constant relative accuracy $\epsilon =\mathrm{\Theta }(\mu R^2)$. For arbitrarily higher accuracy in the range $\kappa \le D_d^2$, the bounds differ by at most $1+\log (\mu R^2\mathrm{/}\epsilon )$; the optimal accuracy dependence remains unresolved in general.