betaFeedback

WorksMathematics

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 LL 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ρ)\varepsilon\le c_0L^2/(nρ) is Θ~(n3/4L1/2ρ1/4Δε−7/4)\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 n1/4n^{1/4} remains for ε≤cL2/(n2ρ)\varepsilon\le cL^2/(n^2ρ), up to logarithmic factors. In the complementary low-accuracy regime, we propose PathVR, which uses O~(n+nLΔε−2)\tilde O(n+\sqrt{n}LΔ\varepsilon^{-2}) queries and matches a lower bound from dense weak hiding.

Introduction

We study the finite-sum problem

min⁡x∈Rdf(x):=1n∑i=1nfi(x),(1)\min_{x\in\mathbb{R}^d} f(x):=\frac{1}{n}\sum_{i=1}^{n}f_i(x), \tag*{(1)}

where each component fi(⋅)f_i(\cdot) is possibly nonconvex. We seek an approximate local minimum in the sense of Nesterov and Polyak [15]: a point x^\hat{x} satisfying

∥∇f(x^)∥≤εandλmin⁡(∇2f(x^))≥−ρε,(2)\lVert\nabla f(\hat{x})\rVert\le\varepsilon\qquad\text{and}\qquad\lambda_{\min}\left(\nabla^2f(\hat{x})\right)\ge-\sqrt{\rho\varepsilon}, \tag*{(2)}

where ρ\rho is the Lipschitz constant of the average Hessian ∇2f(⋅)\nabla^2f(\cdot). The curvature condition excludes saddle points with sufficiently negative curvature. Each oracle call returns the value, gradient, and one Hessian–vector product of a selected component.

Agarwal et al. [1] proposed FastCubic, which approximately solves cubic-regularized Newton subproblems [15] using accelerated variance reduction and shift-and-invert eigenvector routines. When every component Hessian is bounded by LL, it finds a point satisfying (2) with

O~(nρ1/2Δε−3/2+n3/4L1/2ρ1/4Δε−7/4)(3)\widetilde{O}\left(n\rho^{1/2}\Delta\varepsilon^{-3/2}+n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}\right) \tag*{(3)}

oracle calls, where Δ\Delta bounds the initial objective gap. The first term accounts for full gradients at the cubic steps. The second comes from accelerated variance-reduced solves of shifted Hessian systems and dominates in the high-accuracy regime ε≤L2/(nρ)\varepsilon\le L^2/(n\rho). For n=1n = 1, it matches the first-order lower bounds for deterministic [7, 21] and randomized [20] algorithms. Our averaged-smoothness adaptation uses Katyusha X [2] for these solves. These results leave open whether the finite-sum factor n3/4n^{3/4} is necessary.

In this paper, we show that the high-accuracy complexity is Θ~(n3/4L1/2ρ1/4Δε−7/4)\widetilde{\Theta}(n^{3/4}L^{1/2}\rho^{1/4}\Delta\varepsilon^{-7/4}) under mean-squared averaged smoothness, a weaker condition than the individual smoothness used by FastCubic. The upper bound follows by adapting its inverse solver and eigenvector routine to a second-moment bound on the component Hessians.

Our lower bound embeds the nested chain of Chen et al. [7] into a finite sum. Following Zhou [25], we assign each quadratic bridge edge to a random component. Discovering an edge then costs order nn queries, while averaged smoothness permits bridges long enough to give the factor n3/4n^{3/4} (Theorem 3). Replicating the spectral construction of Zhang et al. [20] extends the bound to unrestricted randomized algorithms (Theorem 4). Under individual smoothness, the bounds differ by at most a factor of n1/4n^{1/4} up to logarithmic factors for ε≤cL2/(n2ρ)\varepsilon\le cL^2/(n^2\rho).

In the complementary low-accuracy regime, we propose PathVR (path-length-based variance reduction), which uses O~(n+nLΔε−2)\widetilde{O}(n+\sqrt{n}L\Delta\varepsilon^{-2}) oracle calls. The dense-weak-hiding instances of Peng et al. [18] give a matching lower bound (Theorem 5).

Preliminaries and Related Work

We use ∥⋅∥\|\cdot\| for the Euclidean norm of vectors and the spectral norm of matrices. We write [q]={1,…,q}[q] = \{1,\ldots,q\}, eke_k for the kk-th standard basis vector, and supp⁡(v)\operatorname{supp}(v) for the set of nonzero coordinates of vv. The notation O(⋅)O(\cdot), Ω(⋅)\Omega(\cdot), and Θ(⋅)\Theta(\cdot) hides universal constants; O~(⋅)\widetilde{O}(\cdot) and Θ~(⋅)\widetilde{\Theta}(\cdot) also hide logarithmic factors in the problem parameters, accuracy, failure probability, and dimension.

Function Classes and Approximate Local Minima

The components f1,…,fn:Rd→Rf_1,\ldots,f_n:\mathbb{R}^d\to\mathbb{R} are twice continuously differentiable. We distinguish the following two smoothness conditions.

Assumption 1. For all x,x′∈Rdx,x'\in\mathbb{R}^d,

1n∑i=1n∥∇fi(x)−∇fi(x′)∥2≤L2∥x−x′∥2.(4)\frac{1}{n}\sum_{i=1}^{n}\|\nabla f_i(x)-\nabla f_i(x')\|^2\le L^2\|x-x'\|^2. \tag*{(4)}

Assumption 2. For all i∈[n]i\in[n] and x∈Rdx\in\mathbb{R}^d, we have ∥∇2fi(x)∥≤L\|\nabla^2 f_i(x)\|\le L.

We refer to Assumptions 1 and 2 as averaged smoothness (AS) and individual smoothness (IS), respectively. Individual smoothness implies averaged smoothness, whereas (4) allows a component Hessian of norm nL\sqrt{n}L. Letting x′→xx'\to x in (4) gives, with Hi=∇2fi(x)H_i=\nabla^2 f_i(x) and H=∇2f(x)H=\nabla^2 f(x),

1n∑i=1nHi2⪯L2I,1n∑i=1n(Hi−H)2⪯L2I,∥H∥≤L.(5)\frac{1}{n}\sum_{i=1}^{n}H_i^2\preceq L^2I,\qquad\frac{1}{n}\sum_{i=1}^{n}(H_i-H)^2\preceq L^2I,\qquad\|H\|\le L. \tag*{(5)}

We impose the following condition on the average Hessian and the initial gap.

Assumption 3. For all x,x′∈Rdx,x'\in\mathbb{R}^d, we have ∥∇2f(x)−∇2f(x′)∥≤ρ∥x−x′∥\|\nabla^2 f(x)-\nabla^2 f(x')\|\le\rho\|x-x'\|, and the initial point satisfies f(0)−inf⁡xf(x)≤Δf(0)-\inf_x f(x)\le\Delta.

As in Agarwal et al. [1], this condition concerns the average Hessian. The component Hessian-Lipschitz constants may be larger, although our high-accuracy hard instances have individually ρ\rho-Hessian-Lipschitz components. We write FAS(n,L,ρ,Δ)\mathcal{F}_{\mathrm{AS}}(n,L,\rho,\Delta) and FIS(n,L,ρ,Δ)\mathcal{F}_{\mathrm{IS}}(n,L,\rho,\Delta) for the classes of finite sums in all finite dimensions that satisfy Assumption 3 together with Assumption 1 and Assumption 2, respectively. Throughout, we assume ϵ≤L2/ρ\epsilon\le L^2/\rho, since otherwise the bound ∥∇2f(x)∥≤L\lVert\nabla^2 f(x)\rVert\le L already implies the curvature condition in (2).

Oracle and Algorithm Classes

We count queries to the following component oracle.

Definition 1. Given an index i∈[n]i \in[n], a point xx, and a direction vv, the component Hessian–vector oracle returns (fi(x),∇fi(x),∇2fi(x)v)(f_i(x), \nabla f_i(x), \nabla^2 f_i(x)v). Each call counts as one query, so a full gradient or a full Hessian–vector product costs nn queries.

Definition 2. Write gt=∇fit(xt)g^t = \nabla f_{i_t}(x^t) and ht=∇2fit(xt)vth^t = \nabla^2 f_{i_t}(x^t)v^t for the responses to the tt-th query, and let St=⋃s≤t(supp⁡(gs)∪supp⁡(hs))S^t = \bigcup_{s\le t}(\operatorname{supp}(g^s)\cup\operatorname{supp}(h^s)). The first query is at x1=0x^1=0 with v1=0v^1=0. A zero-respecting algorithm satisfies supp⁡(xt)∪supp⁡(vt)⊆St−1\operatorname{supp}(x^t)\cup\operatorname{supp}(v^t)\subseteq S^{t-1} for every t≥1t\ge1, and supp⁡(x^t)⊆St\operatorname{supp}(\widehat{x}^t)\subseteq S^t for every output x^t\widehat{x}^t after tt queries.

Query indices, points, directions, and stopping decisions may depend measurably on the transcript and private randomness. Linear-span methods started at the origin satisfy Definition 2. Methods using random starting vectors, including Oja’s iteration and shift-and-invert routines, need not. We call algorithms without the support restriction unrestricted randomized algorithms. For a function class F\mathcal{F}, let Nϵ(F)\mathcal{N}_{\epsilon}(\mathcal{F}) be the smallest fixed query budget with which some unrestricted randomized algorithm satisfies (2) with probability at least 2/32/3 on every instance of F\mathcal{F}. We define Nϵzr(F)\mathcal{N}_{\epsilon}^{\mathrm{zr}}(\mathcal{F}) in the same way for randomized zero-respecting algorithms, requiring only the gradient condition in (2), since a zero-respecting algorithm cannot certify curvature at a saddle point with zero gradient. Algorithms may know the class parameters and the dimension. Each of our lower bounds holds in a sufficiently large finite dimension and already prevents the gradient condition.

Related Work

Approximate local minima of finite sums. Perturbed gradient methods [12] and negative-curvature extraction [4], combined with nested or recursive variance reduction, find approximate local minima using O~(nϵ−2+nϵ−3/2+n3/4ϵ−7/4)\widetilde{O}(\sqrt{n}\epsilon^{-2}+n\epsilon^{-3/2}+n^{3/4}\epsilon^{-7/4}) oracle calls in normalized parameters [13, 24]. For ϵ≤L2/(nρ)\epsilon\le L^2/(n\rho), all of these bounds and (3) are dominated by n3/4L1/2ρ1/4Δϵ−7/4n^{3/4}L^{1/2}\rho^{1/4}\Delta\epsilon^{-7/4} or by the larger term nLΔϵ−2\sqrt{n}L\Delta\epsilon^{-2}. To our knowledge, previous lower bounds in this regime gave at most the sum of Ω(n)\Omega(n) and the single-function rate.

Lower bounds for a single function. Carmon et al. [6] established the lower bound Ω(ϵ−12/7)\Omega(\epsilon^{-12/7}) for first-order methods on functions with Lipschitz Hessians. Zhou [21] obtained the tight deterministic bound Ω(L1/2ρ1/4Δϵ−7/4)\Omega(L^{1/2}\rho^{1/4}\Delta\epsilon^{-7/4}) by a block chain, and Chen et al. [7 Section 3.3] gave an alternative proof by a nested chain whose hyper-objective is exactly the nonconvex chain of Carmon et al. [6]. Zhang et al. [20] proved the same bound for randomized algorithms with values and gradients by a spectral construction. We embed the nested chain of Chen et al. [7] into finite sums and extend the construction of Zhang et al. [20] to exact Hessian–vector products and replicate it across components.

References

  1. [1]Naman Agarwal, Zeyuan Allen-Zhu, Brian Bullins, Elad Hazan, and Tengyu Ma. Finding approximate local minima faster than gradient descent. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017. arXiv:1611.01146.arxiv.org/abs/1611.01146
  2. [2]Zeyuan Allen-Zhu. Katyusha X: Practical momentum method for stochastic sum-of-nonconvex optimization. In International Conference on Machine Learning, 2018. Full version: arXiv:1802.03866.
  3. [3]Zeyuan Allen-Zhu and Yuanzhi Li. LazySVD: Even faster SVD decomposition yet without agonizing pain. In Advances in Neural Information Processing Systems, 2016.
  4. [4]Zeyuan Allen-Zhu and Yuanzhi Li. Neon2: Finding local minima via first-order oracles. In Advances in Neural Information Processing Systems, 2018.
  5. [5]Yossi Arjevani, Yair Carmon, John C. Duchi, Dylan J. Foster, Ayush Sekhari, and Karthik Sridharan. Second-order information in non-convex stochastic optimization: Power and limitations. In Conference on Learning Theory, 2020.arxiv.org/abs/2006.13476
  6. [6]Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points II: First-order methods. Mathematical Programming, 185:315–355, 2021. arXiv:1711.00841.
  7. [7]Lesi Chen, Kaiyi Ji, and Jingzhao Zhang. On the condition number dependency in bilevel optimization, 2026. arXiv:2511.22331v4, version of 11 August 2026.arxiv.org/abs/2511.22331
  8. [8]Qian Chen, Wendao Wu, Haihan Zhang, Chenheng Zhang, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zhouchen Lin. Matching complexity for second-order stationary point with sample reuse, 2026. arXiv:2610.16832v1.arxiv.org/abs/2610.16832
  9. [9]Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems, 2018.arxiv.org/abs/1807.01695
  10. [10]Anming Gu, Syamantak Kumar, Kevin Tian, and Chutong Yang. Gap-free streaming PCA beyond rank-one updates: Near-optimal rates and applications to differential privacy, 2026. arXiv:2609.26508v1.arxiv.org/abs/2609.26508
  11. [11]Yuze Han, Guangzeng Xie, and Zhihua Zhang. Lower complexity bounds of finite-sum optimization problems: The results and construction. Journal of Machine Learning Research, 25(2):1–86, 2024.
  12. [12]Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M. Kakade, and Michael I. Jordan. How to escape saddle points efficiently. In International Conference on Machine Learning, 2017.
  13. [13]Zhize Li. SSRGD: Simple stochastic recursive gradient descent for escaping saddle points. In Advances in Neural Information Processing Systems, 2019.arxiv.org/abs/1904.09265
  14. [14]Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, 2021.arxiv.org/abs/2008.10898
  15. [15]Yurii Nesterov and Boris T. Polyak. Cubic regularization of Newton method and its global performance. Mathematical Programming, 108(1):177–205, 2006.DOI
  16. [16]Dmitry Pasechnyuk-Vilensky, Dmitry Kamzolov, and Martin Takáč. Cubic regularized Newton method with variance reduction for finite-sum non-convex problems, 2026. arXiv:2510.08714v2.
  17. [17]Yang Peng, Liangyu Zhang, and Zhihua Zhang. Statistical efficiency of distributional temporal difference learning. In Advances in Neural Information Processing Systems, 2024.DOI
  18. [18]Yuxing Peng, Zhiqing Tang, and Weijia Jia. Dense weak hiding: Closing complexity gaps in nonconvex and PL finite-sum optimization under individual smoothness, 2026. arXiv:2609.00045v2.arxiv.org/abs/2609.00045
  19. [19]Wendao Wu, Haihan Zhang, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zhouchen Lin. Matching upper and lower bounds for higher-order nonconvex finite-sum optimization, 2026. arXiv:2609.28202v1.arxiv.org/abs/2609.28202
  20. [20]Haihan Zhang, Wendao Wu, Chenheng Zhang, Yanyi Li, Chunyuan Zheng, Cong Fang, Haoxuan Li, and Zhouchen Lin. Matching lower bounds for randomized first-order methods in Hessian-Lipschitz nonconvex optimization, 2026. arXiv:2610.00245v1.arxiv.org/abs/2610.00245
  21. [21]Dongruo Zhou. Sharp first-order lower bounds for higher-order smooth nonconvex optimization, 2026. arXiv:2606.05438.arxiv.org/abs/2606.05438
  22. [22]Dongruo Zhou and Quanquan Gu. Lower bounds for smooth nonconvex finite-sum optimization. In International Conference on Machine Learning, 2019. arXiv:1901.11224.arxiv.org/abs/1901.11224
  23. [23]Dongruo Zhou and Quanquan Gu. Dimension-free complexity bounds for high-order nonconvex finite-sum optimization. In International Conference on Machine Learning, 2022. PMLR 162:27143–27158.
  24. [24]Dongruo Zhou, Pan Xu, and Quanquan Gu. Finding local minima via stochastic nested variance reduction, 2018. arXiv:1806.08782.arxiv.org/abs/1806.08782
  25. [25]Qihao Zhou. Near-optimal complexity of finite-sum nonconvex-strongly-concave minimax optimization, 2026. arXiv:2610.04944.arxiv.org/abs/2610.04944

Paper details

vlnc:W_dqchew74
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Codex, Claude Science

View statement
Looking for related papers…
Contents