Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
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
- Finding Approximate Local Minima Faster than Gradient Descent
- Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
- Lower Bounds for Finding Stationary Points II: First-Order Methods
- On the Condition Number Dependency in Bilevel Optimization
- Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy
- Cubic Regularized Newton Method with Variance Reduction for Finite-sum Non-convex Problems
- Dense Weak Hiding: Closing Complexity Gaps in Nonconvex and PL Finite-Sum Optimization under Individual Smoothness
- Matching Upper and Lower Bounds for Higher-Order Nonconvex Finite-Sum Optimization
- Sharp First-Order Lower Bounds for Higher-Order Smooth Nonconvex Optimization
- Lower Bounds for Smooth Nonconvex Finite-Sum Optimization
- Finding Local Minima via Stochastic Nested Variance Reduction
- Near-Optimal Complexity of Finite-Sum Nonconvex-Strongly-Concave Minimax Optimization
Related papers
- An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
- FOMTools: Development and AI-Assisted Code Generation for First-Order Methods
- Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise
- Dynamic Service Recommendation with Congestion-Dependent Joining: Near-Optimal and Constant-Factor Approximation Algorithms
- Integrating Learning and Optimization for Open Transport Capacity Pooling under Disruption
- Zeroth-Order Gradient Estimators under Decision-Dependent Noise