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 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 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Δ/epsilon squared 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 Ω(d T, sqrt ET) calls, and adaptive subspace search attains O(d 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/(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 Ω(dT) calls, as without any trace budget. Our lower bounds hold for C infinity functions with the matrix bound on all of R d, even when each call also returns gradient projections priced by rank.