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

Yuxing Peng, Zhiqing Tang, Weijia Jia

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 $\varepsilon$-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Δ/\varepsilon^2$ is the iteration count of gradient descent from initial gap $Δ$, and we prove that every randomized method needs $Ω(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $\widetildeΩ(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…