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

Abstract

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 a fixed-matrix form of 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 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^\infty$ functions with the matrix bound on all of $\mathbb{R}^d$, even when each call also returns gradient projections priced by rank.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning

• arXiv preprint · 20 October 2026

  Learning the Geometry of Materials Space with Trained Neural Tangent Kernels

  Daniel Kaplan, Gabriel Kotliar and Anirvan M Sengupta
• arXiv preprint · 21 October 2026

  A Jump-Modified Wasserstein Gradient Flow for Maximum Mean Discrepancy with Energy Kernels

  Ansh Desai, Jason Liu, Srujan Roplekar and 1 other
• arXiv preprint · 20 October 2026

  The Router Already Knows

  Andrew Bistras and Marty Johnson
• arXiv preprint · 21 October 2026

  Local and Sparse Kernel Operator Learning for Incompressible Flows: An Operator Lagrange Formulation

  Ramansh Sharma, Matthew Lowery, Houman Owhadi and 1 other
• arXiv preprint · 20 October 2026

  Baseline and Incremental: User, Item, and Request Debiasing in Instagram Feed Ranking

  Hsin-Chiang Chen, Hao Wang, Gedi Zhou and 23 others

All new papers in Machine Learning