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

We study deterministic adaptive optimization of globally $β$-smooth, $μ$-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 $κ=β/μ$, $Q=βR^2/ε$, and $D_d=(d/\log(ed))^{1/3}$. For sufficiently large $d$ and