Fetching the paper…
Reading the bibliography…
Polyak-{\L}ojasiewicz (PL) [Polyak, 1963] condition is a weaker condition than the strong convexity but suffices to ensure a global convergence for the Gradient Descent algorithm.
Lower bounds for non-convex stochastic optimization
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth · 1912
Earlier work this paper cites.
A topological property of real analytic subsets
S. Lojasiewicz · 1963
Earlier work this paper cites.
Gradient methods for the minimisation of functionals
B. Polyak · 1963
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
A. S. Nemirovskij and D. B. Yudin · 1983
Earlier work this paper cites.
Some NP-complete problems in quadratic and nonlinear programming
K. G. Murty and S. N. Kabadi · 1985
Earlier work this paper cites.
Error bounds and convergence analysis of feasible descent methods: a general approach
Z.-Q. Luo and P. Tseng · 1993
Earlier work this paper cites.
Degenerate nonlinear programming with a quadratic growth condition
M. Anitescu · 2000
Earlier work this paper cites.
Introductory lectures on convex optimization: A basic course , volume 87
Y. Nesterov · 2003
Earlier work this paper cites.
Gradient methods for convex minimization: better rates under weaker conditions
H. Zhang and W. Yin · 2013
Earlier work this paper cites.
An asynchronous parallel stochastic coordinate descent algorithm
J. Liu, S. Wright, C. Ré, V. Bittorf, and S. Sridhar · 2014
Earlier work this paper cites.
Identity matters in deep learning
M. Hardt and T. Ma · 2016
Cited alongside, same era.
Proximal stochastic methods for nonsmooth nonconvex finite-sum optimization
S. J Reddi, S. Sra, B. Poczos, and A. J. Smola · 2016
Cited alongside, same era.
Linear convergence of gradient and proximal-gradient methods under the polyak-łojasiewicz condition
H. Karimi, J. Nutini, and M. Schmidt · 2016
Cited alongside, same era.
Tight complexity bounds for optimizing composite objectives
B. E. Woodworth and N. Srebro · 2016
Cited alongside, same era.
Non-convex finite-sum optimization via scsg methods
L. Lei, C. Ju, J. Chen, and M. I. Jordan · 2017
Cited alongside, same era.
Linear convergence of first order methods for non-strongly convex optimization
I. Necoara, Y. Nesterov, and F. Glineur · 2019
Later among the works it cites.
Solving a class of non-convex min-max games using iterative first order methods
M. Nouiehed, M. Sanjabi, T. Huang, J. D. Lee, and M. Razaviyayn · 2019
Later among the works it cites.
Lower bounds for smooth nonconvex finite-sum optimization
D. Zhou and Q. Gu · 2019
Later among the works it cites.
Second-order information in non-convex stochastic optimization: Power and limitations
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, A. Sekhari, and K. Sridharan · 2020
Later among the works it cites.
Lower bounds for finding stationary points I
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford · 2020
Later among the works it cites.
Non-monotone behavior of the heavy ball method
M. Danilova, A. Kulakova, and B. Polyak · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
B. Woodworth and N. Srebro · 2017
Cited alongside, same era.
On exponential convergence of SGD in non-convex over-parametrized learning
R. Bassily, M. Belkin, and S. Ma · 2018
Cited alongside, same era.
SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator
C. Fang, C. J. Li, Z. Lin, and T. Zhang · 2018
Cited alongside, same era.
Global convergence of policy gradient methods for the linear quadratic regulator
M. Fazel, R. Ge, S. Kakade, and M. Mesbahi · 2018
Cited alongside, same era.
Algorithmic regularization in over-parameterized matrix sensing and neural networks with quadratic activations
Y. Li, T. Ma, and H. Zhang · 2018
Cited alongside, same era.
Oracle complexity of second-order methods for smooth convex optimization
Y. Arjevani, O. Shamir, and R. Shiff
Cited in the paper.
Later among the works it cites.
Lower bounds for finding stationary points II: first-order methods
Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford · 2021
Later among the works it cites.
Loss landscapes and optimization in over-parameterized non-linear systems and neural networks
C. Liu, L. Zhu, and M. Belkin · 2022
Closest in time.
Provable acceleration of heavy ball beyond quadratics for a class of polyak-lojasiewicz functions when the non-convexity is averaged-out
J.-K. Wang, C.-H. Lin, A. Wibisono, and B. Hu · 2022
Closest in time.