{"id":"arxiv/2609.28202","url":"https://arxiv.org/abs/2609.28202","tags":["math.OC"],"score":0,"title":"Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization","domain":"math.OC","source":"arxiv","authors":["Wendao Wu","Haihan Zhang","Chenheng Zhang","Yanyi Li","Chunyuan Zheng","Cong Fang","Haoxuan Li","Zhouchen Lin"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{}}