arXiv · Oct 20, 2026
Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace
By 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 ε-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 a fixed-matrix form of 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Δ/ε² 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Ω(dmin{T,√ET}) calls, and adaptive subspace search attains O(dmin{T,√ET}): a deterministic method pays about d calls per discovered direction, and the trace budget allows about √ET directions. Determinism thus multiplies the cost by a factor of order d/(E+√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^(∞) functions with the matrix bound on all of R^d, even when each call also returns gradient projections priced by rank.