Matching Randomized First-Order Bounds for Higher-Order Smooth Nonconvex Optimization

Haihan Zhang, Wendao Wu, Fangqing Zhang, Chenheng Zhang, Chunyuan Zheng, Cong Fang, Haoxuan Li, Zhouchen Lin

arXivarxiv/2610.17074Oct 12, 2026math.OCscore 0

Does randomization improve the worst-case first-order complexity of nonconvex optimization when the objective is very smooth? We prove that, for every fixed finite integer $p\ge3$, finding an $\eps$-stationary point requires $Ω_p(\eps^{-5/3})$ exact value-and-gradient queries, even for $C^\infty$ objectives with initial gap at most one and simultaneous global Lipschitz budgets of one for derivatives of orders $1,\ldots,p$. Together with the known deterministic upper bound, this determines the accuracy exponent up to a single logarithmic factor. The lower bound holds for unrestricted adaptive…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.17074
curl -X POST /api/v1/records/arxiv/2610.17074/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.17074/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'