Matching Lower Bounds for Randomized First-Order Methods in Hessian-Lipschitz Nonconvex Optimization
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 $…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.00245
curl -X POST /api/v1/records/arxiv/2610.00245/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.00245/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'