pipette
ENEnglish

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

Yuxing Peng, Zhiqing Tang, Weijia Jia

Preprint

En palabras de los autores

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 -smooth nonconvex functions on from exact function values, assuming that below the starting value the Hessian is dominated by a fixed matrix with trace at most ; this is the effective rank condition used to explain zeroth-order fine-tuning. When , the Gaussian two-point method that such fine-tuning uses needs only calls if it rejects steps that raise , where is the iteration count of gradient descent from initial gap , and we prove that every randomized method needs calls, so this cost is optimal up to constants. In contrast, every deterministic method needs calls, and adaptive subspace search attains : a deterministic method pays about calls per discovered direction, and the trace budget allows about directions. Determinism thus multiplies the cost by a factor of order up to logarithmic factors, which grows linearly with for fixed and ; once exceeds by a logarithmic factor, deterministic methods need calls, as without any trace budget. Our lower bounds hold for functions with the matrix bound on all of , even when each call also returns gradient projections priced by rank.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 21 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 59 pages, 2 figures, 1 table; Lean 4 formalization of the deterministic bounds in the ancillary files