Complexity bounds improve finding local minima in nonconvex sums
Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
Data Structures and Algorithms
Summary
Finding approximate local minima in complex functions made of many parts is important but challenging. This paper studies the minimum number of queries needed to reliably find such minima for functions that are not simple curves but sums of many smooth components. The authors give tight upper and lower bounds on this complexity depending on how accurate the solution needs to be and the problem's smoothness. They also propose an efficient method called PathVR for cases where high accuracy is not required. Their results sharpen previous understanding of how quickly such problems can be solved.
What this means in practice
- •For machine learning engineers: Optimize large-scale nonconvex models more efficiently by understanding query limits for finding local minima with finite-sum structures.
- •For numerical optimization developers: Design improved optimization algorithms leveraging new complexity bounds and proposed methods for problems with component-wise smoothness criteria.
A theory result. No direct application yet.
Authors
Qihao Zhou
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 $\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 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 $\varepsilon\le cL^2/(n^2ρ)$, up to logarithmic factors. In the complementary low-accuracy regime, we propose PathVR, which uses $\tilde O(n+\sqrt{n}LΔ\varepsilon^{-2})$ queries and matches a lower bound from dense weak hiding.