Near-Optimal Complexity of Finding Approximate Local Minima of Nonconvex Finite Sums
Source: arxiv.org/abs/2611.05807
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.05807
curl -X POST /api/v1/records/arxiv/2611.05807/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05807/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'