# On the Complexity of Finite-Sum Smooth Optimization under the Polyak-Lojasiewicz Condition

arXiv: https://arxiv.org/abs/2402.02569 · HTML: https://mlsanity.com/paper/2402.02569/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 70 references that are in the map.
- First posted on arXiv 4 Feb 2024.

## Builds on (most cited first, 30 of 45)

- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!](https://mlsanity.com/paper/2202.09357/) (2022)
- [Lower Bounds for Finding Stationary Points I](https://mlsanity.com/paper/1710.11606/) (2017)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Optimal algorithms for smooth and strongly convex distributed optimization in networks](https://mlsanity.com/paper/1702.08704/) (2017)
- [A general sample complexity analysis of vanilla policy gradient](https://mlsanity.com/paper/2107.11433/) (2021)
- [Variance Reduction for Faster Non-Convex Optimization](https://mlsanity.com/paper/1603.05643/) (2016)
- [Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop](https://mlsanity.com/paper/1901.08689/) (2019)
- [Non-convex Finite-Sum Optimization Via SCSG Methods](https://mlsanity.com/paper/1706.09156/) (2017)
- [Optimal Complexity in Decentralized Training](https://mlsanity.com/paper/2006.08085/) (2020)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization](https://mlsanity.com/paper/2006.11773/) (2020)
- [LQR through the Lens of First Order Methods: Discrete-time Case](https://mlsanity.com/paper/1907.08921/) (2019)
- [ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/1902.05679/) (2019)
- [Optimizing Static Linear Feedback: Gradient Method](https://mlsanity.com/paper/2004.09875/) (2020)
- [Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization](https://mlsanity.com/paper/2210.07863/) (2022)
- [Lower Bounds for Smooth Nonconvex Finite-Sum Optimization](https://mlsanity.com/paper/1901.11224/) (2019)

## Built on by (most cited first, 2 of 2)

- [Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization](https://mlsanity.com/paper/2509.00737/) (2025)
- [Decentralized Stochastic Nonconvex Optimization under the (L0,L1)-Smoothness](https://mlsanity.com/paper/2509.08726/) (2025)

## Abstract (arXiv)

This paper considers the optimization problem of the form min_bf x∈mathbb Rd f(bf x)triangleq frac1nsumi=1n fi(bf x), where f(·) satisfies the Polyak--Lojasiewicz (PL) condition with parameter μ and fi(·)i=1n is L-mean-squared smooth. We show that any gradient method requires at least Omega(n+kappa√nlog(1/ε)) incremental first-order oracle (IFO) calls to find an ε-suboptimal solution, where kappatriangleq L/μ is the condition number of the problem. This result nearly matches upper bounds of IFO complexity for best-known first-order methods. We also study the problem of minimizing the PL function in the distributed setting such that the individuals f1(·),dots,fn(·) are located on a connected network of n agents. We provide lower bounds of Omega(kappa/√γ,log(1/ε)), Omega((kappa+τkappa/√γ,)log(1/ε)) and Omegabig(n+kappa√nlog(1/ε)big) for communication rounds, time cost and local first-order oracle calls respectively, where γ∈(0,1] is the spectral gap of the mixing matrix associated with the network and~τ>0 is the time cost of per communication round. Furthermore, we propose a decentralized first-order method that nearly matches above lower bounds in expectation.