mlsanityData to 14 Oct 2026

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition

arXiv 1608.04636 ↗First posted 16 Aug 2016cs.LG math.OC stat.COcited by 539

Not on the map. Why?

Cited by 30 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

In 1963, Polyak proposed a simple condition that is sufficient to show a global linear convergence rate for gradient descent. This condition is a special case of the Lojasiewicz inequality proposed in the same year, and it does not require strong convexity (or even convexity). In this work, we show that this much-older Polyak-Lojasiewicz (PL) inequality is actually weaker than the main conditions that have been explored to show linear convergence rates without strong convexity over the last 25 years. We also use the PL inequality to give new analyses of randomized and greedy coordinate descent methods, sign-based gradient descent methods, and stochastic gradient methods in the classic setting (with decreasing or constant step-sizes) as well as the variance-reduced setting. We further propose a generalization that applies to proximal-gradient methods for non-smooth optimization, leading to simple proofs of linear convergence of these methods. Along the way, we give simple convergence results for a wide variety of problems in machine learning: least squares, logistic regression, boosting, resilient backpropagation, L1-regularization, support vector machines, stochastic dual coordinate ascent, and stochastic variance-reduced gradient methods.

Key facts. Cited by 539 papers in the map (data through 14 Oct 2026). First posted on arXiv 16 Aug 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 76; 2022: 87; 2023: 95; 2024: 98; 2025: 87; 2026: 96.

539 papers.

Sort:

By area:

  1. 2023Fine-Tuning Language Models with Just Forward Passescited by 345
  2. 2021Dash: Semi-Supervised Learning with Dynamic Thresholdingcited by 148
  3. 2022Towards Understanding Sharpness-Aware Minimizationcited by 146
  4. 2023Controlled Decoding from Language Modelscited by 135
  5. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
  6. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  7. 2022On the Convergence Rates of Policy Gradient Methodscited by 119
  8. 2021Decentralized Federated Averagingcited by 114
  9. 2024Challenges in Training PINNs: A Loss Landscape Perspectivecited by 113
  10. 2022BOME! Bilevel Optimization Made Easy: A Simple First-Order Approachcited by 105
  11. 2021Distributionally Robust Federated Averagingcited by 104
  12. 2024Lisa: Lazy Safety Alignment for Large Language Models against Harmful Fine-tuning Attackcited by 92
38 more
  1. 2023On Penalty-based Bilevel Gradient Descent Methodcited by 87
  2. 2022Understanding the Generalization Benefit of Normalization Layers: Sharpness Reductioncited by 86
  3. 2023DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedulecited by 85
  4. 2022Improved analysis for a proximal algorithm for samplingcited by 73
  5. 2025Gluon: Making Muon & Scion Great Again! (Bridging Theory and Practice of LMO-based Optimizers for LLMs)cited by 72
  6. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  7. 2022Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlocited by 63
  8. 2021AC/DC: Alternating Compressed/DeCompressed Training of Deep Neural Networkscited by 59
  9. 2021Blockchain Assisted Decentralized Federated Learning (BLADE-FL): Performance Analysis and Resource Allocationcited by 56
  10. 2024Active-Dormant Attention Heads: Mechanistically Demystifying Extreme-Token Phenomena in LLMscited by 56
  11. 2021Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problemcited by 53
  12. 2021Who Leads and Who Follows in Strategic Classification?cited by 53
  13. 2022Statistical Learning Theory for Control: A Finite Sample Perspectivecited by 53
  14. 2024Friendly Sharpness-Aware Minimizationcited by 53
  15. 2023On Penalty Methods for Nonconvex Bilevel Optimization and First-Order Stochastic Approximationcited by 51
  16. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 49
  17. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  18. 2021Leveraging Non-uniformity in First-order Non-convex Optimizationcited by 44
  19. 2021Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivitycited by 43
  20. 2021On Tilted Losses in Machine Learning: Theory and Applicationscited by 43
  21. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  22. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 42
  23. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  24. 2023A Guide Through the Zoo of Biased SGDcited by 40
  25. 2021Stochastic gradient descent with noise of machine learning type. Part I: Discrete time analysiscited by 39
  26. 2023On Finding Small Hyper-Gradients in Bilevel Optimization: Hardness Results and Improved Analysiscited by 39
  27. 2024In-Context Learning with Representations: Contextual Generalization of Trained Transformerscited by 38
  28. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  29. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  30. 2021Improved Fine-Tuning by Better Leveraging Pre-Training Datacited by 36
  31. 2021On the Theory of Implicit Deep Learning: Global Convergence with Implicit Layerscited by 35
  32. 2021Fast and accurate optimization on the orthogonal manifold without retractioncited by 35
  33. 2021Proximal and Federated Random Reshufflingcited by 33
  34. 2021Averaging on the Bures-Wasserstein manifold: dimension-free convergence of gradient descentcited by 32
  35. 2024Understanding and Improving Training-free Loss-based Diffusion Guidancecited by 32
  36. 2023On the Convergence of Federated Averaging with Cyclic Client Participationcited by 31
  37. 2025On the Convergence of Muon and Beyondcited by 31
  38. 2021Convergence of stochastic gradient descent schemes for Lojasiewicz-landscapescited by 28

50 most cited of 539 All 539 (JSON)