Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition
Using the Polyak-Lojasiewicz (PL) inequality, this paper proves linear convergence of gradient and proximal gradient methods for non-strong convex problems.
Key Findings
Methodology
This work systematically analyzes the application of the PL inequality in non-strong convex optimization, establishing linear convergence for gradient, coordinate, stochastic, and proximal gradient algorithms under PL conditions. It introduces a generalized proximal-PL condition, simplifying convergence proofs for nonsmooth problems like SVMs and L1-regularized least squares. The analysis leverages specific algorithms such as randomized coordinate descent, stochastic gradient descent (SGD), and variance-reduced methods (SVRG), deriving explicit convergence rates. The framework broadens the theoretical understanding of non-convex and non-strong convex problems, providing unified guarantees across diverse machine learning models.
Key Results
- Gradient descent with step size 1/L achieves linear convergence rate (1 - μ/L)^k in non-strong convex settings, applicable to various models including logistic regression and least squares.
- Expected convergence rate for randomized coordinate descent is (1 - μ/dL)^k, outperforming classical bounds, especially in high-dimensional sparse problems.
- Proximal gradient methods under the proximal-PL inequality attain linear convergence, simplifying analysis for support vector machines and L1 regularization, with explicit rate formulas.
Significance
This research extends the classical convergence theory beyond strong convexity, offering a versatile framework applicable to a wide range of machine learning tasks. It addresses longstanding challenges in analyzing non-convex and nonsmooth problems, providing rigorous guarantees for algorithms widely used in practice. The unified approach and simplified proofs enhance both theoretical understanding and practical algorithm design, facilitating efficient large-scale optimization in deep learning, sparse modeling, and beyond.
Technical Contribution
The paper introduces the proximal-PL inequality as a unifying condition for linear convergence in non-smooth and non-strong convex problems. It derives explicit convergence rates for various algorithms, including coordinate descent, stochastic methods, and proximal gradient algorithms, under this condition. The analysis simplifies existing proofs, broadens applicability, and connects the PL framework with established conditions like Kurdyka-Łojasiewicz (KL) and error bounds, creating a comprehensive theoretical foundation.
Novelty
This is the first comprehensive application of the PL inequality to multiple classes of optimization algorithms in non-strong convex contexts. The introduction of the proximal-PL condition and its equivalence to KL inequality provides a novel, simplified analytical framework. The work bridges gaps between classical convex analysis and modern non-convex optimization, offering new insights into convergence guarantees without relying on strong convexity.
Limitations
- While broadly applicable, verifying the PL condition in complex neural networks remains challenging, limiting immediate practical deployment.
- Convergence rates depend on the parameter μ, which is often difficult to estimate accurately in real-world scenarios.
- The analysis primarily addresses global convergence, with less emphasis on local convergence behaviors in highly non-convex landscapes.
Future Work
Future research will focus on validating PL conditions in deep neural networks, developing adaptive algorithms that estimate μ dynamically, and extending the framework to broader classes of non-convex problems. Exploring local convergence properties and integrating stochastic variance reduction techniques more deeply will further enhance practical performance.
AI Executive Summary
Since Polyak's seminal 1963 work, the PL inequality has served as a cornerstone for understanding linear convergence in optimization. This paper advances the field by demonstrating that the PL condition, a weaker assumption than strong convexity, suffices to guarantee linear convergence for a wide array of algorithms, including gradient descent, coordinate descent, stochastic gradient, and proximal gradient methods. The authors establish that under the PL inequality, these methods achieve explicit convergence rates, such as (1 - μ/L)^k, without requiring the objective to be convex or strongly convex.
A key innovation lies in the generalization of the PL condition to the proximal setting, where it becomes equivalent to the Kurdyka-Łojasiewicz (KL) inequality. This unification simplifies the analysis of non-smooth problems like support vector machines and L1-regularized least squares, providing clear linear convergence guarantees. The work also explores the relationships between PL and other conditions like error bounds, restricted strong convexity, and quadratic growth, positioning PL as a central, versatile criterion.
Experimental results demonstrate the broad applicability of the theory, with convergence rates derived for high-dimensional sparse problems, logistic regression, and neural network training. Notably, the analysis reveals that coordinate descent with greedy or randomized selection achieves faster expected convergence under PL, outperforming classical bounds. The results have significant implications for large-scale machine learning, enabling more efficient algorithms with rigorous guarantees.
Looking ahead, the challenge remains to verify the PL condition in complex models like deep neural networks and to develop adaptive methods that estimate μ during training. Extending the framework to address local convergence phenomena and non-convex landscapes will be crucial for future breakthroughs. Overall, this work provides a unified, simplified, and powerful theoretical foundation for the convergence analysis of a broad class of optimization algorithms, promising to influence both theory and practice in machine learning and beyond.
Deep Dive
Abstract
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 Łojasiewicz 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-Łojasiewicz (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.