OpenAlex ·
Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.00245
- Original
- Read it at the publisher
- Topics
Abstract
We establish a randomized first-order lower bound for finding an $ε$-stationary point, $\|\nabla f(x)\|\le ε$, of a nonconvex function with initial gap at most $Δ$, $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}(ε;Δ,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 $ε\lesssim L_1^2/L_2$ and $ΔL_2^{1/2}ε^{-3/2}\gtrsim 1$, we prove $ Q_{\mathrm{rand},\mathrm{FO}}^{\infty}(ε;Δ,L_1,L_2) \ge c\,ΔL_1^{1/2}L_2^{1/4}ε^{-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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Artificial Intelligence
Vertex-Coloring Edge-Weighting: Kernelization and Generalization
Claim-Gated Source-Risk Auditing for Generative Search
Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs
A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth
Biplanar graphs with independence number two are 9-colorable
Get the few papers worth your time in Artificial Intelligence every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.