Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
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 ε≤ c0L2/(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 ε≤ cL2/(n2ρ), up to logarithmic factors. In the complementary low-accuracy regime, we propose PathVR, which uses Õ(n+√nLΔε−2) queries and matches a lower bound from dense weak hiding.
Related
- The Complexity of Finding Stationary Points in Nonsmooth Nonconvex Optimization
- On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
- Optimal Deterministic First-Order Oracle Complexity for Nonconvex-Concave Minimax Optimization
- Composite Online-to-Nonconvex Conversion with Optimal Oracle Complexity
BibTeX
@misc{zhou2026nearoptimal,
title = {{Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums}},
author = {Qihao Zhou},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05807},
eprint = {2611.05807},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05807},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
AU - Qihao Zhou
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.05807
UR - https://arxiv.org/abs/2611.05807
AB - 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_0L^2/(nρ) is Θ̃(n^3/4L^1/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 n^1/4 remains for ε≤ cL^2/(n^2ρ), up to logarithmic factors. In the complementary low-accuracy regime, we propose PathVR, which uses Õ(n+√nLΔε^−2) queries and matches a lower bound from dense weak hiding.
ER -