Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods

Introduction

Large-scale nonsmooth and nonconvex optimization problems are ubiquitous in machine learning and data analysis. Tremendous efforts have thus been directed at designing efficient algorithms for solving these problems. One popular class of algorithms is the class of first-order methods. These methods are noted for their simplicity, ease-of-implementation and relatively (often surprisingly) good performance; some notable examples include the proximal gradient algorithm, the inertial proximal algorithms and the alternating direction method of multipliers, etc. Due to the excellent performance and wide applicability of first-order methods, their convergence behaviors have been extensively studied in recent years; see, for example, and references therein. Analyzing the convergence rate of first-order methods is an important step towards a better understanding of existing algorithms, and is also crucial for developing new optimization models and numerical schemes.

As demonstrated in [2, Theorem 3.4], the convergence behavior of many first-order methods can be understood using the celebrated Kurdyka-Łojasiewicz (KL) property and its associated KL exponent; see Definitions 2.2 and 2.3. The KL property and its associated KL exponent have their roots in algebraic geometry, and they describe a qualitative relationship between the value of a suitable potential function (depending on the optimization model and the algorithm being considered) and some first-order information (gradient or subgradient) of the potential function. The KL property has been applied to analyzing local convergence rate of various first-order methods for a wide variety of problems by many researchers; see, for example, . In these studies, a proto-typical theorem on convergence rate takes the following form:

Prototypical result on convergence rate. For a certain algorithm of interest, consider a suitable potential function. Suppose that the potential function satisfies the KL property with an exponent of $\alpha\in[0,1)$, and that $\{x^{k}\}$ is a bounded sequence generated by the algorithm. Then the following results hold.

If $\alpha=0$, then $\{x^{k}\}$ converges finitely.

If $\alpha\in(0,\frac{1}{2}]$, then $\{x^{k}\}$ converges locally linearly.

If $\alpha\in(\frac{1}{2},1)$, then $\{x^{k}\}$ converges locally sublinearly.

While this kind of convergence results is prominent and theoretically powerful, for the results to be fully informative, one has to be able to estimate the KL exponent. Moreover, in order to guarantee a local linear convergence rate, it is desirable to be able to determine whether a given model has a KL exponent of at most $\frac{1}{2}$, or be able to construct a new model whose KL exponent is at most $\frac{1}{2}$ if the old one does not have the desired KL exponent.

The main contributions of this paper are the rules for computing explicitly the KL exponent of many (convex or nonconvex) optimization models that arise in applications such as statistical machine learning. We accomplish this via two different means: studying calculus rules and building connections with the concept of Luo-Tseng error bound; see Definition 2.1. The Luo-Tseng error bound was used for establishing local linear convergence for various first-order methods, and was shown to hold for a wide range of problems; see, for example, for details. This concept is different from the error bound studied in because the Luo-Tseng error bound is defined for specially structured optimization problems and involves first-order information, while the error bound studied in does not explicitly involve any first-order information. The different nature of these two concepts was also noted in [7, Section 1], in which the Luo-Tseng error bound was referred as “first-order error bound”.

Notation and preliminaries

For a proper closed convex function $P$, the proximal mapping at any $z$ is defined as

where $\mathop{\rm arg\,min}$ denotes the unique minimizer of the optimization problem $\min\limits_{x}\{P(x)+\frac{1}{2}\|x-z\|^{2}\}$.This problem has a unique minimizer because the objective is proper closed and strongly convex. For a general optimization problem $\min\limits_{x}f(x)$, we use $\mathop{\rm Arg\,min}f$ to denote the set of minimizers, which may be empty, a singleton or may contain more than one point. This mapping is nonexpansive, i.e., for any $y$ and $z$, we have

see, for example, [36, Page 340]. Moreover, it is routine to show that $x={\rm prox}_{P}(z)$ if and only if $z\in x+\partial P(x)$.

The following property is defined for proper closed functions of the form $f=h+P$, where $h$ is a proper closed function with an open domain, and is continuously differentiable with a locally Lipschitz continuous gradient on ${\rm dom}\,h$, and $P$ is proper closed convex. Recall that for this class of functions, we have $\bar{x}\in{\cal X}$ if and only if $\bar{x}={\rm prox}_{P}(\bar{x}-\nabla h(\bar{x}))$, where $\cal X$ denotes the set of stationary points of $f$. Indeed, we have

where (i) follows from [38, Exercise 8.8(c)].

(Luo-Tseng error bound)We adapt the definition from [41, Assumption 2a]. Let $\cal X$ be the set of stationary points of $f$. Suppose that ${\cal X}\neq\emptyset$. We say that the Luo-Tseng error bound This is referred as first-order error bound in [7, Section 1]. holds if for any $\zeta\geq\inf f$, there exist $c$, $\epsilon>0$ so that

whenever $\|{\rm prox}_{P}(x-\nabla h(x))-x\|<\epsilon$ and $f(x)\leq\zeta$.

It is known that this property is satisfied for many choices of $h$ and $P$, and we refer to and references therein for more detailed discussions. This property was used for establishing local linear convergence of various first-order methods applied to minimizing $f=h+P$.

Recently, the following property was also used extensively for analyzing convergence rate of first-order methods, mainly for possibly nonconvex objective functions; see, for example, .

$\psi$ is continuously differentiable on $(0,\nu)$ with $\psi^{\prime}>0$;

for all $x\in{\cal N}$ with $f(\bar{x})<f(x)<f(\bar{x})+\nu$, one has

A proper closed function $f$ satisfying the KL property at all points in ${\rm dom}\,\partial f$ is called a KL function.

In this paper, we are interested in the KL exponent, which is defined as follows.

(KL exponent) For a proper closed function $f$ satisfying the KL property at $\bar{x}\in{\rm dom}\,\partial f$, if the corresponding function $\psi$ can be chosen as $\psi(s)=c\,s^{1-\alpha}$ for some $c>0$ and $\alpha\in[0,1)$, i.e., there exist $c$, $\epsilon>0$ and $\nu\in(0,\infty]$ so that

whenever $\|x-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x)<f(\bar{x})+\nu$, then we say that $f$ has the KL property at $\bar{x}$ with an exponent of $\alpha$. If $f$ is a KL function and has the same exponent $\alpha$ at any $\bar{x}\in{\rm dom}\,\partial f$, then we say that $f$ is a KL function with an exponent of $\alpha$. In classical algebraic geometry, the exponent $\alpha$ is also referred as the Łojasiewicz exponent.

This definition encompasses broad classes of function that arise in practical optimization problems. For example, it is known that if $f$ is a proper closed semi-algebraic function , then $f$ is a KL function with a suitable exponent $\alpha\in[0,1)$. As established in [2, Theorem 3.4] and many subsequent work, KL exponent has a close relationship with the rate of convergence of many commonly used optimization methods.

Before ending this section, we state two auxiliary lemmas. The first result is an immediate consequence of the fact that the set-valued mapping $x\mapsto\partial f(x)$ is outer semicontinuous (with respect to the $f$-attentive convergence, i.e., $y\stackrel{{\scriptstyle f}}{{\to}}x$; see [38, Proposition 8.7]), and can be found in [2, Remark 4 (b)]. This result will be used repeatedly at various places in our discussion below. We include a proof for self-containedness.

Suppose that $f$ is a proper closed function, $\bar{x}\in{\rm dom}\,\partial f$ and $0\notin\partial f(\bar{x})$. Then, for any $\alpha\in[0,1)$, $f$ satisfies the KL property at $\bar{x}$ with an exponent of $\alpha$.

Fix any $\alpha\in[0,1)$. Since $0\notin\partial f(\bar{x})$ and $\partial f(\bar{x})$ is nonempty and closed, it follows that ${\rm dist}(0,\partial f(\bar{x}))$ is positive and finite. Define $\eta:=\frac{1}{2}{\rm dist}(0,\partial f(\bar{x}))>0$. We claim that there exists $\epsilon\in(0,1)$ so that ${\rm dist}(0,\partial f(x))>\eta$ whenever $\|x-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x)<f(\bar{x})+\epsilon$.

Suppose for the sake of contradiction that this is not true. Then there exists a sequence $\{x^{k}\}$ with $x^{k}\to\bar{x}$ and $f(x^{k})\to f(\bar{x})$ so that

In particular, there exists a sequence $\{\xi^{k}\}$ satisfying $\xi^{k}\in\partial f(x^{k})$ and $\|\xi^{k}\|\leq\eta$. By passing to a subsequence if necessary, we may assume without loss of generality that $\xi^{k}\to\bar{\xi}$ for some $\bar{\xi}$, and we have $\bar{\xi}\in\partial f(\bar{x})$, thanks to [38, Proposition 8.7]. But then we have $2\eta={\rm dist}(0,\partial f(\bar{x}))\leq\|\bar{\xi}\|\leq\eta$, a contradiction. Thus, there exists $\epsilon\in(0,1)$ so that ${\rm dist}(0,\partial f(x))>\eta$ whenever $\|x-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x)<f(\bar{x})+\epsilon$.

whenever $\|x-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x)<f(\bar{x})+\epsilon$, showing that $f$ satisfies the KL property at $\bar{x}$ with an exponent of $\alpha$. This completes the proof. ∎

The second result concerns the equivalence of “norms”, whose proof is simple and is omitted.

Let $t>0$. Then there exist $C_{1}\geq C_{2}>0$ so that

Calculus of the KL exponent

In this section, we discuss how the KL exponent behaves under various operations on KL functions. We briefly summarize our results below. The required assumptions will be made explicit in the respective theorems.

Exponent for $\min_{1\leq i\leq r}f_{i}$ given the exponents of $f_{i}$ for each $i$; see Theorem 3.1 and Corollary 3.1.

Exponent for $g(F(x))$ when the Jacobian of $F$ is surjective, given the exponent of $g$; see Theorem 3.2.

Exponent for $\sum_{i=1}^{m}f_{i}(x_{i})$ given the exponents of $f_{i}$ for each $i$; see Theorem 3.3.

Exponent for the Moreau envelope of a convex KL function; see Theorem 3.4.

Deducing the exponent from the Lagrangian relaxation for convex problems; see Theorem 3.5.

Exponent for a potential function used in the convergence analysis of the inertial proximal algorithm in ; see Theorem 3.6.

Deducing the exponent of a partly smooth KL function by looking at its restriction on its active manifold; see Theorem 3.7.

We shall make use of some of these calculus rules in Section 5 to deduce the KL exponent of some concrete optimization models.

We start with our first result, which concerns the minimum of finitely many KL functions. This rule will prove to be useful in Section 5. Indeed, as we shall see there, many nonconvex optimization problems that arise in applications have objectives that can be written as the minimum of finitely many KL functions whose exponents can be deduced from our results in Section 4; this includes some prominent and widely used NP-hard optimization model problems, for example, the least squares problem with cardinality constraint .

(Exponent for minimum of finitely many KL functions) Let $f_{i}$, $1\leq i\leq r$, be proper closed functions, $f:=\min_{1\leq i\leq r}f_{i}$ be continuous on ${\rm dom}\,\partial f$ and \bar{x}\in{\rm dom}\,\partial f\cap\big{(}\bigcap_{i\in I(\bar{x})}{\rm dom}\,\partial f_{i}\big{)}, where $I(\bar{x}):=\{i:f_{i}(\bar{x})=f(\bar{x})\}$. Suppose further that each $f_{i}$, $i\in I(\bar{x})$, satisfies the KL property at $\bar{x}$ with an exponent of $\alpha_{i}\in[0,1)$. Then $f$ satisfies the KL property at $\bar{x}$ with an exponent of $\alpha=\max\{\alpha_{i}:i\in I(\bar{x})\}$.

From the definition of $I(\bar{x})$, we see that $\min_{i\notin I(\bar{x})}\{f_{i}(\bar{x})\}>f(\bar{x})$. Since $x\mapsto\min_{i\notin I(\bar{x})}\{f_{i}(x)\}$ is lower semicontinuous and the function $f$ is continuous on ${\rm dom}\,\partial f$, there exists $\eta>0$ such that for all $x\in{\rm dom}\,\partial f$ with $\|x-\bar{x}\|\leq\eta$, we have

Thus, whenever $x\in{\rm dom}\,\partial f$ and $\|x-\bar{x}\|\leq\eta$, we have $I(x)\subseteq I(\bar{x})$.

Next, using $f(x)=\min_{1\leq i\leq r}\{f_{i}(x)\}$ and the subdifferential rule of the minimum of finitely many functions [32, Theorem 5.5], we obtain for all $x\in{\rm dom}\,\partial f$ that

On the other hand, by assumption, for each $i\in I(\bar{x})$, there exist $\epsilon_{i}$, $c_{i}$, $\nu_{i}>0$ such that for all $x\in{\rm dom}\,\partial f_{i}$ with $\|x-\bar{x}\|\leq\epsilon_{i}$ and $f_{i}(\bar{x})<f_{i}(x)<f_{i}(\bar{x})+\nu_{i}$, one has

Let $c=\min_{i\in I(\bar{x})}c_{i}$, $\epsilon=\min\{\eta,\min_{i\in I(\bar{x})}\epsilon_{i}\}$ and $\nu=\min_{i\in I(\bar{x})}\{1,\nu_{i}\}$. Take any $x\in{\rm dom}\,\partial f$ with $\|x-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x)<f(\bar{x})+\nu$. Then $I(x)\subseteq I(\bar{x})$ and we have

where the first inequality follows from (5), the second inequality follows from (6), the construction of $c$, $\nu$, $\epsilon$ and $\alpha$, as well as the facts that $f_{i}(x)=f(x)$ and $f_{i}(\bar{x})=f(\bar{x})$ for $i\in I(x)\subseteq I(\bar{x})$; these facts also give the last equality. This completes the proof. ∎

We have the following immediate corollary.

Let $f_{i}$, $1\leq i\leq r$, be proper closed functions with ${\rm dom}\,f_{i}={\rm dom}\,\partial f_{i}$ for all $i$, and $f:=\min_{1\leq i\leq r}f_{i}$ be continuous on ${\rm dom}\,\partial f$. Suppose further that each $f_{i}$ is a KL function with an exponent of $\alpha_{i}\in[0,1)$ for $1\leq i\leq r$. Then $f$ is a KL function with an exponent of $\alpha=\max\{\alpha_{i}:1\leq i\leq r\}$.

In view of Theorem 3.1, it suffices to show that for any $\bar{x}\in{\rm dom}\,\partial f$, we have $\bar{x}\in\bigcap_{i\in I(\bar{x})}{\rm dom}\,\partial f_{i}$. To this end, take any $\bar{x}\in{\rm dom}\,\partial f$. Note that we have ${\rm dom}\,\partial f\subseteq{\rm dom}\,f$ by the definition, and hence $f(\bar{x})<\infty$. In addition, from the definition of $I(\bar{x})$, we have $f(\bar{x})=f_{i}(\bar{x})$ for all $i\in I(\bar{x})$. Hence, $f_{i}(\bar{x})$ is finite for all $i\in I(\bar{x})$. Thus, we conclude that $\bar{x}\in{\rm dom}\,f_{i}$ for all $i\in I(\bar{x})$, which implies that $\bar{x}\in\bigcap_{i\in I(\bar{x})}{\rm dom}\,\partial f_{i}$ because ${\rm dom}\,f_{i}={\rm dom}\,\partial f_{i}$ for all $i$ by assumption. ∎

The next theorem concerns the composition of a KL function with a smooth function that has a surjective Jacobian mapping.

Note from [38, Exercise 10.7] and $\bar{x}\in{\rm dom}\,\partial f$ that $F(\bar{x})\in{\rm dom}\,\partial g$. As $g$ is a KL function, there exist $\epsilon_{0}$, $c_{0}$, $\nu_{0}>0$ such that for all $u\in{\rm dom}\,\partial g$ with $\|u-F(\bar{x})\|\leq\epsilon_{0}$ and $g(F(\bar{x}))<g(u)<g(F(\bar{x}))+\nu_{0}$, one has

On the other hand, since the linear map $JF(\bar{x})$ is surjective and $F$ is continuously differentiable, it follows from the classical Lyusternik-Graves theorem (see, for example, [33, Theorem 1.57]) that there are numbers $l>0$ and $\epsilon_{1}\in(0,\epsilon_{0})$ such that for all $x$ with $\|x-\bar{x}\|\leq\epsilon_{1}$

whenever $\|x-\bar{x}\|\leq\epsilon_{1}$. Moreover, from the chain rule of the limiting subdifferential for composite functions (see, for example, [38, Exercise 10.7]), we have for all $x$ with $\|x-\bar{x}\|\leq\epsilon_{1}$ that

because $JF(x)$ is a surjective mapping for all such $x$.

Now, let $\epsilon\in(0,\epsilon_{1}]$ be such that $\|F(x)-F(\bar{x})\|\leq\epsilon_{0}$ for all $\|x-\bar{x}\|\leq\epsilon$, $c=l\,c_{0}$ and $\nu=\nu_{0}$. Fix $x\in{\rm dom}\,\partial f$ with $\|x-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x)<f(\bar{x})+\nu$. Let $a\in\partial f(x)$ be such that $\|a\|={\rm dist}(0,\partial f(x))$. Then, we have $a=JF(x)^{*}v$ for some $v\in\partial g(F(x))$. Hence, it follows from (8) that

In addition, since $v\in\partial g(F(x))$, applying (7) with $u=F(x)$ gives us that

Our next theorem concerns separable sums.

Let $\epsilon=\min_{1\leq i\leq r}\epsilon_{i}$. Take any $x\in{\rm dom}\,\partial f$ with $\|x-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x)<f(\bar{x})+1$. We will now verify (4). To this end, let $z\in\partial f(x)$ be such that

since $0<f(x)-f(\bar{x})<1$. Thus, we consider the case where $\|z\|\leq 1$. In this case, recall from [38, Proposition 10.5] that

for $C_{0}=\max_{1\leq i\leq r}c_{i}$. Define $\alpha:=\max\{\alpha_{i}:1\leq i\leq r\}$. Since $\|z_{i}\|\leq\|z\|\leq 1$ and $0<\alpha_{i}\leq\alpha<1$, it then follows from (11) that

where the second inequality follows from Lemma 2.2 with $t=\frac{1}{\alpha}$. This completes the proof. ∎

We now discuss the operation of taking Moreau envelope. This operation is a common operation for smoothing the objective function of convex optimization problems.

(Exponent for Moreau envelope of convex KL functions) Let $f$ be a proper closed convex function that is a KL function with an exponent of $\alpha\in(0,\frac{2}{3})$. Suppose further that $f$ is continuous on ${\rm dom}\,\partial f$. Fix $\lambda>0$ and consider

Then $F_{\lambda}$ is a KL function with an exponent of $\max\{\frac{1}{2},\frac{\alpha}{2-2\alpha}\}<1$.

It suffices to consider the case $\mathop{\rm Arg\,min}F_{\lambda}\neq\emptyset$ and show that $F_{\lambda}$ has the KL property with an exponent of $\max\{\frac{1}{2},\frac{\alpha}{2-2\alpha}\}$ at any fixed $\bar{x}\in\mathop{\rm Arg\,min}F_{\lambda}$, in view of Lemma 2.1 and the convexity of $F_{\lambda}$.

and that $\nabla F_{\lambda}$ is Lipschitz continuous with a Lipschitz constant of $\frac{1}{\lambda}$. Consequently, we have for any $y$ that

where $\bar{y}$ is the projection of $y$ onto $\mathop{\rm Arg\,min}F_{\lambda}$, and the last equality holds because $\nabla F_{\lambda}(\bar{y})=0$.

whenever $\|y-\bar{x}\|\leq\epsilon$ and $y\in{\rm dom}\,\partial f$; here, the condition on the bound on function values is waived by using the continuity of $f$ on $\partial f$ and choosing a smaller $\epsilon$ if necessary. Moreover, in view of [7, Theorem 5(i)], by shrinking $\epsilon$ if necessary, we conclude that there exists $c>0$ so that

whenever $\|y-\bar{x}\|\leq\epsilon$ and $y\in{\rm dom}\,\partial f$; here, the condition on the bound on function values is waived similarly as before. Finally, since $\mathop{\rm Arg\,min}F_{\lambda}=\mathop{\rm Arg\,min}f$, we have $\|y-\bar{y}\|={\rm dist}(y,\mathop{\rm Arg\,min}f)$. Combining this with (14) and (15) implies that for some $c_{1}>0$,

whenever $\|y-\bar{x}\|\leq\epsilon$ and $y\in{\rm dom}\,\partial f$.

Now, using the definition of the proximal mapping as minimizer, we have by using the first-order optimality condition that for any $u$,

In particular, ${\rm prox}_{\lambda f}(u)\in{\rm dom}\,\partial f$. In addition, using the above relation and (12), we deduce that

Fix an arbitrary $u$ with $\|u-\bar{x}\|\leq\epsilon$. Then $\|{\rm prox}_{\lambda f}(u)-\bar{x}\|=\|{\rm prox}_{\lambda f}(u)-{\rm prox}_{\lambda f}(\bar{x})\|\leq\|u-\bar{x}\|$, where the inequality is due to (2). Let $y={\rm prox}_{\lambda f}(u)$. Then $y\in{\rm dom}\,\partial f$ and $\|y-\bar{x}\|\leq\epsilon$. Hence, the relations (16) and (17) imply that

Applying (13) with $y={\rm prox}_{\lambda f}(u)$ and combining this with the preceding relation, we obtain further that

whenever $\|u-\bar{x}\|\leq\epsilon$. Finally, from the convexity of $F_{\lambda}$, we have

Shrink $\epsilon$ further if necessary so that $\|\nabla F_{\lambda}(u)\|<1$ whenever $\|u-\bar{x}\|\leq\epsilon$; this is possible since $\nabla F_{\lambda}(\bar{x})=0$. Summing (18) and (19), we obtain further that

for some $C>0$, whenever $\|u-\bar{x}\|\leq\epsilon$. This completes the proof. ∎

Our next result concerns the Lagrangian relaxation. This result will be used later in Proposition 4.2 for a group LASSO model. In addition, the result, together with results in that give the exponent of the maximum of finitely many convex polynomials, can be used to study the KL property of a large class of convex polynomial optimization problems with multiple convex polynomial constraints.

there exists $x_{0}\in D$ with $g(x_{0})<0$;

$\inf\limits_{x\in D}h(x)<\inf\limits_{x\in C\cap D}h(x)$;

for any $\lambda>0$, the function $h(x)+\lambda g(x)+\delta_{D}(x)$ is a KL function with an exponent of $\alpha$.

Then $f(x)=h(x)+\delta_{C}(x)+\delta_{D}(x)$ has the KL property at any $\bar{x}\in C\cap D$, with an exponent of $\alpha$.

In view of Lemma 2.1 and the convexity of $f$, we only need to consider the case $\mathop{\rm Arg\,min}f\neq\emptyset$ and look at those $\bar{x}$ with $0\in\partial f(\bar{x})$ (and so, $\bar{x}\in\mathop{\rm Arg\,min}f$ by the convexity of $f$). From now on, fix any such $\bar{x}$.

First, from condition (i) and [36, Corollary 28.2.1], there exists $\lambda\geq 0$ so that

where the first inequality follows from $\bar{x}\in C\cap D$, while the second inequality follows from the fact that $\bar{x}\in C$ and hence $g(\bar{x})\leq 0$. Thus, equality holds throughout (20); in particular, we have $h(\bar{x})+\lambda g(\bar{x})=h(\bar{x})$, which gives $\lambda g(\bar{x})=0$. Also, in view of the fourth equality in (20) and condition (ii), we must have $\lambda>0$; consequently, we have $g(\bar{x})=0$. Fix any such $\lambda>0$. Then, in view of [36, Theorem 28.1], we also have

Next, since $h(x)=l(Ax)$ for some strictly convex function $l$, it must hold true that $Ax$ is constant for any $x\in\mathop{\rm Arg\,min}(h+\lambda g+\delta_{D})$. Since $\lambda>0$, we deduce that $g(x)$ is constant over $\mathop{\rm Arg\,min}(h+\lambda g+\delta_{D})$. Hence, in view of (21), we have $g(x)=g(\bar{x})=0$ for any $x\in\mathop{\rm Arg\,min}(h+\lambda g+\delta_{D})$. Then we conclude further from (21) that

Now, using condition (iii) and [7, Theorem 5(i)], and noting that $\bar{x}\in{\rm dom}\,\partial(h+\lambda g+\delta_{D})$, we see that there exist $\epsilon$, $\nu$ and $c>0$ so that

whenever $\|x-\bar{x}\|\leq\epsilon$, $x\in D$ and $h(\bar{x})\leq h(x)+\lambda g(x)<h(\bar{x})+\nu$, because $g(\bar{x})=0$. On the other hand, whenever $h(\bar{x})<h(x)<h(\bar{x})+\nu$ and $x\in C\cap D$, we have

where the equality follows from (20) and the second inequality follows from the definition of $C$. Combining this with (23), we see that whenever $x\in C\cap D$, $\|x-\bar{x}\|\leq\epsilon$ and $h(\bar{x})<h(x)<h(\bar{x})+\nu$, we have

where the first equality follows from (22) and the second inequality follows from the definition of $C$. The conclusion of the theorem now follows from this last relation and [7, Theorem 5(ii)]. ∎

In our next result, Theorem 3.6, we study the KL property of $F(x,y):=f(x)+\frac{\beta}{2}\|x-y\|^{2}$ for any $\beta>0$ when $f$ is a KL function. The function $F$ is used in the convergence analysis of various first-order methods whose iterates involve momentum terms; see, for example, for convergence analysis of some inertial proximal algorithms, and for convergence analysis of the proximal gradient algorithm with extrapolation. Theorem 3.6 will be used to analyze the convergence rate of an inertial proximal algorithm, the iPiano , with constant step-sizes, in Theorem 5.1.

We start with the following simple lemma.

Let $\gamma\in(1,2]$. Then there exist $\eta_{1}>0$ and $\eta_{2}\in(0,1)$ so that

Notice that $x\mapsto\|x\|^{\gamma}$ is convex because $\gamma\in(1,2]$. Fix any $\lambda\in(0,\frac{1}{2})$. Then we have from convexity that

Rearranging terms, we obtain further that

The proof is completed upon noting that $\frac{\lambda}{1-\lambda}\in(0,1)$, since $\lambda\in(0,\frac{1}{2})$. ∎

(Exponent for a potential function for iPiano) Suppose that $f$ is a proper closed function that has the KL property at $\bar{x}\in{\rm dom}\,\partial f$ with an exponent of $\alpha\in[\frac{1}{2},1)$ and $\beta>0$. Consider the function $F(x,y):=f(x)+\frac{\beta}{2}\|x-y\|^{2}$. Then the function $F$ has the KL property at $(\bar{x},\bar{x})$ with an exponent of $\alpha$.

Since $f$ has the KL property at $\bar{x}$ with an exponent of $\alpha\in(0,1)$, there exist $c$, $\epsilon$ and $\nu>0$ so that

whenever $x\in{\rm dom}\,\partial f$, $\|x-\bar{x}\|\leq\epsilon$ and $f(x)<f(\bar{x})+\nu$, where the condition $f(\bar{x})<f(x)$ is dropped because (24) holds trivially otherwise. By shrinking $\epsilon$ further if necessary, we assume that $\epsilon<\frac{1}{2}$.

Now, consider any $(x,y)$ satisfying $x\in{\rm dom}\,\partial f$, $\|x-\bar{x}\|\leq\epsilon$, $\|y-\bar{x}\|\leq\epsilon$ and $F(\bar{x},\bar{x})<F(x,y)<F(\bar{x},\bar{x})+\nu$. Clearly, any such $(x,y)$ satisfies

and thus (24) holds for these $x$. Then for some suitable positive constants $C_{0}$, $C_{1}$ and $C_{2}$ (to be specified below), we have for any such $(x,y)$ that

where the existence of $C_{0}>0$ in the first inequality follows from Lemma 2.2; the second inequality follows from Lemma 3.1 applied to the term $\|\xi+\beta(x-y)\|^{\frac{1}{\alpha}}$, with $\eta_{1}$ and $\eta_{2}$ given by Lemma 3.1; the third inequality follows by setting $C_{1}=C_{0}\min\{\eta_{1},1-\eta_{2}\}$; the fourth inequality follows by further shrinking $C_{1}$, and $c$ is the same number as in (24); the fifth inequality follows from (24), while the last inequality follows from the assumption on $\alpha$ and the observation that

In our last theorem in this section, we examine KL property on a subset, more precisely, a manifold $\mathfrak{M}$. Roughly speaking, we show that under partial smoothness and some additional assumptions, one only needs to verify the KL property along $\mathfrak{M}$ in order to establish the property at a point $\bar{x}$. Before stating the result, we recall some necessary definitions. First, following [38, Definition 13.27], a proper closed function $f$ is said to be prox-regular at a point ${\bar{x}}$ for a subgradient ${\bar{v}}\in\partial f({\bar{x}})$ if ${\bar{x}}\in{\rm dom}\,f$ and there exists $\rho\geq 0$ such that

whenever $x$ and $x^{\prime}$ are near ${\bar{x}}$ with $f(x)$ near $f({\bar{x}})$ and $v\in\partial f(x)$ is near ${\bar{v}}$. Furthermore, we say that $f$ is prox-regular at ${\bar{x}}$ if it is prox-regular at ${\bar{x}}$ for every ${\bar{v}}\in\partial f({\bar{x}})$.

Next, let ${\mathfrak{M}}$ be a ${\cal C}^{2}$ manifold about ${\bar{x}}\in{\mathfrak{M}}$.Following , this notion means that locally $\mathfrak{M}$ can be expressed as the solution set of a collection of ${\cal C}^{2}$ equations with linearly independent gradients. For a function $f$ that is ${\cal C}^{2}$ around ${\bar{x}}\in\mathfrak{M}$, the covariant derivative $\nabla_{\mathfrak{M}}f({\bar{x}})$ is defined as the unique vector in $T_{\bar{x}}({\mathfrak{M}})$ with

Finally, we recall the notion of partial smoothness. From [18, Definition 2.3] (see also [22, Definition 2.7]), a function $f$ is ${\cal C}^{2}$-partly smooth at ${\bar{x}}$ relative to ${\mathfrak{M}}$ if the following four properties hold:

(restricted smoothness) the restriction of $f$ on ${\mathfrak{M}}$ is a ${\cal C}^{2}$ function near ${\bar{x}}$;

(regularity) at every point in ${\mathfrak{M}}$ close to ${\bar{x}}$, the function $f$ is regular and $\partial f({\bar{x}})\neq\emptyset$;

(normal sharpness) the affine span of $\partial f({\bar{x}})$ is a translate of the limiting normal cone $N_{{\mathfrak{M}}}({\bar{x}})$;

(subgradient continuity) the subdifferential mapping $\partial f$ restricted to ${\mathfrak{M}}$ is continuous at ${\bar{x}}$.

(Exponent for partly smooth KL functions) Suppose that $f$ is a proper closed function that is prox-regular at $\bar{x}$ and ${\cal C}^{2}$-partly smooth at $\bar{x}$ relative to a manifold ${\mathfrak{M}}$. Suppose further that $0\in{\rm ri}\,\partial f(\bar{x})$ and that there exist $c$, $\nu$, $\epsilon>0$ and $\alpha\in[0,1)$ so that

whenever $x\in\mathfrak{M}$ with $\|x-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x)<f(\bar{x})+\nu$. Then $f$ has the KL property at $\bar{x}$ with an exponent of $\alpha$.

Our proof proceeds by contradiction. Suppose the contrary holds. Then there exists $\{x^{k}\}\subseteq{\rm dom}\,\partial f$ with $x^{k}\to\bar{x}$ and $f(x^{k})>f(\bar{x})$, $f(x^{k})\to f(\bar{x})$ such that

In particular, ${\rm dist}(0,\partial f(x^{k}))\to 0$. This together with the assumptions on prox-regularity, partial smoothness, $0\in{\rm ri}\,\partial f(\bar{x})$ and [18, Theorem 5.3] shows that $x^{k}\in\mathfrak{M}$ for all sufficiently large $k$. Thus, by considering even larger $k$ if necessary so that $\|x^{k}-\bar{x}\|\leq\epsilon$ and $f(\bar{x})<f(x^{k})<f(\bar{x})+\nu$, we conclude from the assumption that

for all sufficiently large $k$. Since ${\rm dist}(0,\partial f(x^{k}))=\|\nabla_{\mathfrak{M}}f(x^{k})\|$ for all sufficiently large $k$ as a consequence of [11, Proposition 23], we have obtained a contradiction to (25). This completes the proof. ∎

Structured problems: Luo-Tseng error bound and KL property

In this section, we examine structured optimization problems where the objective functions $f$ are proper closed functions taking the following form:

Here, $h$ is a proper closed (possibly nonconvex) function with an open domain, and is continuously differentiable with a locally Lipschitz continuous gradient on ${\rm dom}\,h$, and $P$ is proper closed convex. Since $f$ is proper closed, we must have ${\rm dom}\,h\cap{\rm dom}\,P\neq\emptyset$. For this class of functions, the Luo-Tseng error bound (3) is commonly used in the literature for establishing local linear convergence of various first-order methods applied to minimizing $f$; see, for example, . In this section, we study the relationship between the Luo-Tseng error bound and the KL property for the class of functions (26), under the following assumption concerning separation of stationary values. Recall that ${\cal X}$ is the set of stationary points of $f$.

For any $\bar{x}\in\cal X$, there exists $\delta>0$ so that $f(y)=f(\bar{x})$ whenever $y\in{\cal X}$ and $\|y-\bar{x}\|\leq\delta$.

This assumption is trivially satisfied if $h$ is, in addition, convex. Moreover, a global version of this assumption is commonly used together with the Luo-Tseng error bound for convergence analysis in the literature.

Before proving our main result of this section under Assumption 4.1, we first establish the following auxiliary lemma. This lemma is a generalization of [13, Proposition 1.5.14], where we have a general proper closed convex function $P$ instead of just the indicator function of a closed convex set.

Consider the function $f$ given in (26). For any $x\in{\rm dom}\,\partial f$, it holds that

For any $x\in{\rm dom}\,\partial f$, we have $\partial f(x)\neq\emptyset$. Since $\partial f(x)=\nabla h(x)+\partial P(x)$ thanks to [38, Exercise 8.8(c)], we must then have $\partial P(x)\neq\emptyset$. Consequently, the set $x+\partial P(x)$ is nonempty. Using the definition of proximal mapping, this means that there exists $z$ so that $x={\rm prox}_{P}(z)$.

Now, for any $x\in{\rm dom}\,\partial f$, let $z$ be such that $x={\rm prox}_{P}(z)$. Then

where the inequality follows from (2). Consequently, we have

where the fourth equality follows from the definition of the proximal mapping. The desired inequality (27) now follows by combining (28) and (29). ∎

Using the above lemma, we can now prove the following result, which states that if the Luo-Tseng error bound and Assumption 4.1 hold, then $f$ is a KL function with an exponent of $\frac{1}{2}$.

(Luo-Tseng error bound implies KL) Suppose that ${\cal X}\neq\emptyset$, and that Assumption 4.1 and the Luo-Tseng error bound hold. Then $f$ in (26) is a KL function with an exponent of $\frac{1}{2}$.

From Lemma 2.1, we only need to show that $f$ has the KL property at any $\bar{x}\in\cal X$ with an exponent of $\frac{1}{2}$. To see this, fix any $\bar{x}\in{\cal X}$. Let $\delta>0$ be defined as in Assumption 4.1 and take any $\epsilon\in(0,\frac{\delta}{4})$ such that $B(\bar{x},2\epsilon)\subset{\rm dom}\,h$ (this is possible as ${\rm dom}\,h$ is open and $\bar{x}\in{\rm dom}\,h$). Then for any $x$ with $\|x-\bar{x}\|\leq\epsilon$, we have

whenever $u\in{\rm Proj}_{\bar{\cal X}}(x)$. From this, one can argue that ${\rm Proj}_{\bar{\cal X}}(x)={\rm Proj}_{\cal X}(x)$ for these $x$. Indeed, if $u\in{\rm Proj}_{\bar{\cal X}}(x)\subseteq\bar{\cal X}$, then there exist $u^{k}\to u$ satisfying $0\in\nabla h(u^{k})+\partial P(u^{k})$ for all $k$. Using this, $u\in B(\bar{x},2\epsilon)\subset{\rm dom}\,h$ and the closedness of $\partial P$, we conclude that $u\in\cal X$. This proves ${\rm Proj}_{\bar{\cal X}}(x)={\rm Proj}_{\cal X}(x)$ since ${\rm Proj}_{\bar{\cal X}}(x)\supseteq{\rm Proj}_{\cal X}(x)$ holds trivially. Thus, it holds that $f(u)=f(\bar{x})$ for any $u\in{\rm Proj}_{\cal X}(x)$ whenever $\|x-\bar{x}\|\leq\epsilon$. On the other hand, notice that $B(\bar{x},2\epsilon)$ is a compact subset of ${\rm dom}\,h$ and $\nabla h$ is locally Lipschitz on ${\rm dom}\,h$. Consequently, $\nabla h$ is globally Lipschitz continuous on $B(\bar{x},2\epsilon)$; we denote its Lipschitz constant by $L>0$.

Next, from the assumption on Luo-Tseng error bound, we see that for $\zeta=f(\bar{x})+1$, there exist $c_{1}$, $\epsilon_{1}>0$ so that

whenever $\|{\rm prox}_{P}(x-\nabla h(x))-x\|<\epsilon_{1}$ and $f(x)\leq f(\bar{x})+1$. Since $\|{\rm prox}_{P}(x-\nabla h(x))-x\|<\epsilon_{1}$ is a neighborhood of ${\cal X}$ containing $\bar{x}$, by shrinking $\epsilon$ if necessary, we may assume that (30) holds whenever $\|x-\bar{x}\|\leq\epsilon$ and $f(x)\leq f(\bar{x})+1$.

From the above discussions, for any $x\in{\rm dom}\,\partial f$ with $f(\bar{x})<f(x)<f(\bar{x})+1$ and $\|x-\bar{x}\|\leq\epsilon$, we have $f(\bar{x})=f(u)$ for any $u\in{\rm Proj}_{\cal X}(x)$, and

for any $\xi\in\partial P(x)$, where the first inequality is a consequence of the subgradient inequality applied to $P$ and the fact that $\nabla h$ is Lipschitz continuous with a Lipschitz constant of $L$ on $B(\bar{x},2\epsilon)$, which contains both $x$ and $u$, the last equality follows from the definition of $u$, while the last inequality follows from (30) for some suitable $C_{0}>0$. Taking infimum over all possible $\xi\in\partial P(x)$ and invoking Lemma 4.1, we see further that

for some $C_{1}>0$. This completes the proof. ∎

(Convex problems with convex piecewise linear-quadratic regularizers) Consider a convex function $f$ given as in (31). Suppose that $\mathop{\rm Arg\,min}f$ is a nonempty compact set. Then $f$ is a KL function with an exponent of $\frac{1}{2}$.

Fix any $\bar{x}\in\mathop{\rm Arg\,min}f$. Denote $\bar{y}=A\bar{x}$ and $\bar{g}=A^{*}\nabla l(A\bar{x})$. Then $-\bar{g}\in\partial P(\bar{x})$ from the first-order optimality condition and [38, Exercise 8.8(c)]. Notice that $Ax\equiv\bar{y}$ over $\mathop{\rm Arg\,min}f$ due to the strong convexity of $l$ on compact convex sets. Consequently, we also have $A^{*}\nabla l(Ax)\equiv A^{*}\nabla l(\bar{y})=\bar{g}$ over $\mathop{\rm Arg\,min}f$. Define

as in [46, Section 3.3]. We will subsequently show that

The pair of sets $\{\Gamma_{f}(\bar{y}),\Gamma_{P}(\bar{g})\}$ is boundedly linearly regular.

The subdifferential mapping $\partial P$ is metrically sub-regular at $\bar{x}$ for $-\bar{g}$.

Granting these, since $\bar{x}\in\mathop{\rm Arg\,min}f$ is arbitrary, we conclude using [46, Theorem 2] and [46, Corollary 1] that the Luo-Tseng error bound holds. Since $f$ is convex so that Assumption 4.1 is trivially satisfied, the desired conclusion follows from Theorem 4.1.

Now it remains to prove the two claims above.

For (1), note that $P^{*}$ is convex piecewise linear-quadratic according to [38, Theorem 11.14], which implies that $\partial P^{*}(-\bar{g})$ is a polyhedral set [38, Proposition 10.21]. Consequently, it follows from [5, Corollary 5.2.6] that the pair of sets $\{\Gamma_{f}(\bar{y}),\Gamma_{P}(\bar{g})\}$ is linearly regular in the sense that there exists $c>0$ such that