Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace

Low curvature trace, an effective rank condition, is a common explanation for why randomized zeroth-order methods scale to high-dimensional tasks such as language model fine-tuning. Can deterministic methods achieve the same savings? We show that they cannot. We study finding $\epsilon$-stationary points of $L$-smooth nonconvex functions on ${\mathbb{R}}^d$ from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most $LE$; this is the effective rank condition used to explain zeroth-order fine-tuning. When $ET\le d$, the Gaussian two-point method that such fine-tuning uses needs only $O(ET)$ calls if it rejects steps that raise $f$, where $T=L\mathrm{\Delta }\mathrm{/}{\epsilon }^2$ is the iteration count of gradient descent from initial gap $\mathrm{\Delta }$, and we prove that every randomized method needs $\mathrm{\Omega }(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $\tilde{\mathrm{\Omega }}(d\min \{T,\sqrt{ET}\})$ calls, and adaptive subspace search attains $O(d\min \{T,\sqrt{ET}\})$: a deterministic method pays about $d$ calls per discovered direction, and the trace budget allows about $\sqrt{ET}$ directions. Determinism thus multiplies the cost by a factor of order $d\mathrm{/}(E+\sqrt{ET})$ up to logarithmic factors, which grows linearly with $d$ for fixed $E$ and $T$; once $E$ exceeds $T$ by a logarithmic factor, deterministic methods need $\mathrm{\Omega }(dT)$ calls, as without any trace budget. Our lower bounds hold for $C^{\mathrm{\infty }}$ functions with the matrix bound on all of ${\mathbb{R}}^d$, even when each call also returns gradient projections priced by rank.