Calculus of the Exponent of Kurdyka–Łojasiewicz Inequality and Its Applications to Linear Convergence of First-Order Methods

By Guoyin Li, Ting Kei Pong. 2016

366 citations recorded by the source corpus.

In this paper, we study the Kurdyka–Łojasiewicz (KL) exponent, an important quantity for analyzing the convergence rate of first-order methods. Specifically, we develop various calculus rules to deduce the KL exponent of new (possibly nonconvex and nonsmooth) functions formed from functions with known KL exponents. In addition, we show that the well-studied Luo–Tseng error bound together with a mild assumption on the separation of stationary values implies that the KL exponent is 12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{2}$$\end{document}. The Luo–Tseng error bound is known to hold for a large class of concrete structured optimization problems, and thus we deduce the KL exponent of a large class of functions whose exponents were previously unknown. Building upon this and the calculus rules, we are then able to show that for many convex or nonconvex optimization models for applications such as sparse recovery, their objective function’s KL exponent is 12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{2}$$\end{document}. This includes the least squares problem with smoothly clipped absolute deviation regularization or minimax concave penalty regularization and the logistic regression problem with ℓ1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _1$$\end{document} regularization. Since many existing local convergence rate analysis for first-order methods in the nonconvex scenario relies on the KL exponent, our results enable us to obtain explicit convergence rate for various first-order methods when they are applied to a large variety of practical optimization models. Finally, we further illustrate how our results can be applied to establishing local linear convergence of the proximal gradient algorithm and the inertial proximal algorithm with constant step sizes for some specific models that arise in sparse recovery.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, methodology): “While the KL inequality has been used to show local linear convergence of proximal-gradient methods [Bolte et al., 2015], [Li and Pong, 2016], in this section we propose a different generalization of the PL inequality that yields a simple global linear convergence analysis.”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, neutral): “This topic has been studied in [18][27][26][24][22].”
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods (2016, background): “1 While finalizing a first version of this work, the authors became aware of a concurrent, independent and nicely complementary approach [30], based on a related calculus of KurdykaLojasiewicz exponents.”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, neutral): “Due to λ ∗ > 0, g ( v ∗ ) is also a constant (Li and Pong, 2017).”
SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation (2020, background): “, 2014), quasi strong convexity (Necoara et al., 2018; Gower et al., 2019), the restricted secant inequality (Zhang and Yin, 2013), and the quadratic growth (QG) condition (Anitescu, 2000; Loizou, 2019).”
Convergence Analysis of a Momentum Algorithm with Adaptive Step Size for Non Convex Optimization (2019, background): “1. α := 1 − θ is also defined as the K L exponent in other papers (Li and Pong, 2018).”