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

Abstract

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/2)$. Set $\kappa=\beta/\mu$, $Q=\beta R^2/\epsilon$, and $D_d=(d/\log(ed))^{1/3}$. For sufficiently large $d$ and $0<\epsilon\le c_\epsilon\beta R^2$, the minimax value complexity $N_\epsilon$ satisfies \[ \begin{aligned} N_\epsilon&\ge c d\min\{\sqrt Q,\sqrt\kappa,D_d\},\\ N_\epsilon&\le C d\min\left\{ \sqrt Q,\sqrt\kappa[1+\log_+(Q/\kappa)] \right\}, \end{aligned} \] 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=\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/\epsilon)$; the optimal accuracy dependence remains unresolved in general.