Deterministic optimization costs scale poorly under low curvature trace
Lower Bounds for Smooth Nonconvex Zeroth-Order Optimization: The Price of Determinism under Low Curvature Trace
Machine Learning
Summary
Finding points where smooth but complex functions don't change much (called stationary points) can be done using random guesses more efficiently than using fixed, predictable steps. The authors show that when the function has a special low-rank structure, randomized methods can find these points much faster, while deterministic methods require many more function calls. This means that if you want to avoid randomness, you’ll have to spend a lot more effort, especially in high dimensions. Their work proves that this large difference in cost is unavoidable.
What this means in practice
- •For machine learning engineers: Choose randomized zeroth-order methods when tuning large language models for better efficiency due to inherent cost gaps with deterministic approaches.
- •For optimization algorithm developers: Design deterministic optimization routines knowing they inherently require scaling costs in high dimensions under low curvature trace conditions.
A theory result. No direct application yet.
Authors
Yuxing Peng, Zhiqing Tang, Weijia Jia
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 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.