Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization

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

arXivarxiv/2609.28202Sep 23, 2026math.OCscore 0

We establish tight randomized higher-order oracle complexity for finding first-order stationary points of nonconvex finite sums. Let $n$ be the number of components, $Δ>0$ the initial objective-gap bound, $L_p>0$ an individual $p$-th derivative Lipschitz bound, and $ε>0$ the target gradient norm. For every fixed integer $p\ge 2$, the minimax number of exact component queries returning the value and all derivatives through order $p$, with success probability at least $2/3$, is \[ Θ_p\!\left( n+ΔL_p^{1/p}n^{1-1/(2p)} ε^{-(p+1)/p} \right), \] where the constants depend only on $p$ and the worst…

SourceJSON

Comments and reviews

No comments yet.

API

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