Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization

Abstract

We establish a randomized first-order lower bound for finding an $\epsilon$-stationary point, $\|\nabla f(x)\|\le \epsilon$, of a nonconvex function with initial gap at most $\Delta$, $L_1$-Lipschitz gradient, and $L_2$-Lipschitz Hessian. Each oracle call returns the exact function value and gradient. Let $Q_{\mathrm{rand},\mathrm{FO}}^{\infty}(\epsilon;\Delta,L_1,L_2)$ denote the minimax number of calls, maximized over finite dimensions, for arbitrary adaptive randomized algorithms with per-instance success probability at least $2/3$. In the regime $\epsilon\lesssim L_1^2/L_2$ and $\Delta L_2^{1/2}\epsilon^{-3/2}\gtrsim 1$, we prove $ Q_{\mathrm{rand},\mathrm{FO}}^{\infty}(\epsilon;\Delta,L_1,L_2) \ge c\,\Delta L_1^{1/2}L_2^{1/4}\epsilon^{-7/4}, $ where $c>0$ is an absolute constant. This matches the deterministic restarted accelerated-gradient upper bound of Li and Lin (2023) and extends the sharp deterministic lower bound of Zhou (2026) to unrestricted randomized algorithms. Thus, randomization does not improve the high-dimensional worst-case query rate. The construction keeps quadratic curvature visible while revealing the forcing directions sequentially. Large eigenspaces limit preprocessing, and a scheduled-disclosure coupling makes each fresh direction incur a separate cost.