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

arXiv:2611.05807 · math.OC, cs.DS · Submitted 2026-11-04 · Read on arXiv

math.OC, cs.DS

Submitted: 2026-11-04

Updated: 2026-11-04

Comments: 30 pages, 2 tables

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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.

Abstract

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 epsilon at most c 0L 2/(nρ) is Θ(n 3/4L 1/2ρ 1/4Δ epsilon-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 n 1/4 remains for epsilon at most cL 2/(n 2ρ), up to logarithmic factors. In the complementary low-accuracy regime, we propose PathVR, which uses O(n+ sqrt n LΔ epsilon-2) queries and matches a lower bound from dense weak hiding.

Sources

Related papers