{"id":"arxiv/2611.05807","url":"https://arxiv.org/abs/2611.05807","tags":["math.OC","cs.DS"],"score":0,"title":"Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums","domain":"math.OC","source":"arxiv","authors":["Qihao Zhou"],"reviews":0,"subject":"math.OC","summary":"We study the component-oracle complexity of finding approximate local minima of nonconvex finite sums under mean-squared averaged smoothness with parameter $L$ and a $ρ$-Lipschitz average Hessian. Each query returns the value, gradient, and one Hessian-vector product of a component. We show that the complexity in the high-accuracy regime $\\varepsilon\\le c_0L^2/(nρ)$ is $\\tildeΘ(n^{3/4}L^{1/2}ρ^{1/4}Δ\\varepsilon^{-7/4})$ for a sufficiently large initial gap $Δ$. We attain the upper bound by adapting the inverse solver and eigenvector routine of FastCubic to averaged smoothness. Our lower…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-04","reactions":{}}