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

By Hamed Karimi, Julie Nutini, Mark W. Schmidt. 2016

1,544 citations recorded by the source corpus.

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 \L{}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-\L{}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.

Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Mathematical Physics

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “We say that a function f : R d → R is µ –strongly quasi-convex [Karimi et al., 2016, Necoara et al., 2018] if there is µ > 0 such that: for all x ∈ d .”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “However, if the function is μ−quasi strongly convex then it satisfies the PL condition with the same μ (Karimi et al., 2016).”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, methodology): “To the best of our knowledge this is the first result for the convergence of SGD for PL functions without assuming bounded gradient or bounded variance or interpolation (for more details see results in Karimi et al. (2016) and discussion in Gower et al. (2019)).”
Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “[28] Hamed Karimi, Julie Nutini, and Mark Schmidt.”
Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates (2019, background): “In Appendix A, we also give upper bounds on η k if the function f i k satisﬁes the Polyak-Lojasiewicz (PL) inequality [67, 38] with constant µ ik .”
Advances and Open Problems in Federated Learning (2019, background): “[191] improves the bounds in Wang and Joshi [399] for functions satisfying the Polyak-Lojasiewicz (PL) condition [226], a generalization of strong convexity.”
Mime: Mimicking Centralized Stochastic Algorithms in Federated Learning (2020, background): “[14] Hamed Karimi, Julie Nutini, and Mark Schmidt.”
Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization (2019, methodology): “Furthermore, as μ-strong convexity implies μ-PL condition [18], Theorem 1 holds for μ-strongly convex cost functions as well.”
CoCoA: A General Framework for Communication-Efficient Distributed Optimization (2016, background): “…like the hinge-loss support vector machine that could be applied, e.g., by us-ing error bound conditions (Necoara and Nedelcu, 2014; Wang and Lin, 2014), weak strong convexity conditions (Ma et al., 2015c; Necoara, 2015) or by considering Polyak-Łojasiewicz conditions (Karimi et al., 2016).”
DeltaGrad: Rapid retraining of machine learning models (2020, neutral): “See e.g., (Gladyshev, 1965; Amari, 1967; Kul’chitskiy & Mozgovoy, 1992; Bert-sekas & Tsitsiklis, 1996; Moulines & Bach, 2011; Karimi et al., 2016; Bottou et al., 2018; Gorbunov et al., 2019; Gower et al., 2019), etc, and references therein.”
signSGD: compressed optimisation for non-convex problems (2018, background): “The convergence of steepest descent is well-known (see Karimi et al., 2016, Appendix C, for an analysis of signed gradient updates under the PolyakŁojasiewicz condition).”
ATOMO: Communication-efficient Learning via Atomic Sparsification (2018, background): “This is a well-known fact in optimization, and most convergence bounds for stochastic-gradient based methods, including minibatch, involve upper bounds on E[‖ĝ(wk)‖](2)2, in a multiplicative form, for both convex and nonconvex setups [39, 40, 41, 42, 42, 43, 44, 45, 46, 47].”
Identity Matters in Deep Learning (2016, background): “3) says that the gradient has fairly large norm compared to the error, which guarantees convergence of the gradient descent to a global minimum ([11]) if the iterates stay inside the domain Bτ , which is not guaranteed by Theorem 2.”
SGD: General Analysis and Improved Rates (2019, background): “Further, we assume that f has a unique1 global minimizer x∗ and is μ–strongly quasi-convex (Karimi et al., 2016; Necoara et al., 2018):”
YellowFin and the Art of Momentum Tuning (2017, methodology): “the PL condition (Karimi et al., 2016), have been used in the analysis of gradient descent.”
LAG: Lazily Aggregated Gradient for Communication-Efficient Distributed Learning (2018, background): “Note that the PL condition in Assumption 3 is strictly weaker than the strongly convexity (or even convexity), and it is satisfied by a wider range of machine learning problems such as least squares for underdetermined linear systems and logistic regression; see details in (Karimi et al., 2016).”
On exponential convergence of SGD in non-convex over-parametrized learning (2018, background): “In [5, Appendix B], it was shown that if g : R k → R is α -strongly convex and A ∈ R k × d is matrix whose least non-zero singular value is σ , then f : R d → R deﬁned as f ( www ) , g ( Awww ) , www ∈ R d is α σ 2 -PL function.”