[Submitted on 20 Oct 2026 (v1), last revised 3 Nov 2026 (this version, v3)]
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 $ETle 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=LDelta/varepsilon^2$ is the iteration count of gradient descent from initial gap $Delta$, and we prove that every randomized method needs $Omega(ET)$ calls, so this cost is optimal up to constants. In contrast, every deterministic method needs $widetildeOmega(dmin{T,sqrt{ET}})$ calls, and adaptive subspace search attains $O(dmin{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 $Omega(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.
Submission history
From: Yuxing Peng [view email]
[v1] Tue, 20 Oct 2026 03:05:54 UTC (316 KB)
[v2] Wed, 21 Oct 2026 02:39:27 UTC (317 KB)
[v3] Tue, 3 Nov 2026 06:32:43 UTC (318 KB)
