arXiv preprint ·
Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Optimization & Control
Last-Iterate Convergence of Stochastic Gradient Methods for Unbounded Problems
Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning
From What Is Used to What Is Missing: Rethinking Dynamic Rank in LoRA
On Convergence of Gradient Temporal-Difference Learning with Regularized Corrections and Eligibility Traces
Truncated backpropagation through time induces a two-sided gradient turnpike property
Get the few papers worth your time in Optimization & Control every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.