Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums

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 ε≤ c₀L²/(nρ) is Θ(n3/4L1/2ρ1/4Δε-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 bound assigns the bridge edges of a nested chain to random components; a replicated spectral construction gives the same bound for unrestricted randomized algorithms. Under individual smoothness, a factor of n1/4 remains for ε≤ cL²/(n²ρ), up to logarithmic factors. In the complementary low-accuracy regime, we propose PathVR, which uses O(n+√nLΔε⁻²) queries and matches a lower bound from dense weak hiding.