[Submitted on 14 Oct 2026 (v1), last revised 3 Nov 2026 (this version, v2)]
Abstract:Must the dimension and accuracy costs of zeroth-order optimization multiply? Global upper bounds for smooth stochastic nonconvex optimization scale as $O(depsilon^{-4})$, with both factors separately necessary. We show that their product is unavoidable. We establish an $Omega(depsilon^{-4})$ lower bound for smooth stochastic nonconvex optimization, yielding an $Omega(ddelta^{-1}epsilon^{-3})$ bound for nonsmooth Goldstein stationarity. Both match the best-known full-space upper bounds, establishing joint minimax optimality in dimension and accuracy. These bounds hold against fully adaptive randomized algorithms with unrestricted queries and outputs, even under arbitrary sample reuse. As a byproduct, we establish noiseless exact-value lower bounds for both smooth and Goldstein stationarity, even against randomized algorithms.
Submission history
From: Xiao-Tong Yuan [view email]
[v1] Wed, 14 Oct 2026 06:20:12 UTC (76 KB)
[v2] Tue, 3 Nov 2026 15:38:41 UTC (113 KB)
