From error bounds to the complexity of first-order descent methods for convex functions

Overview and main results

Since Hoffman’s celebrated result on error bounds for systems of linear inequalities , the study of error bounds has been successfully applied to problems in sensitivity, convergence rate estimation, and feasibility issues. In the optimization world, the first natural extensions were made to convex functions by Robinson , Mangasarian , and Auslender-Crouzeix . However, the most striking discovery came years before in the pioneering works of Łojasiewicz at the end of the fifties: under a mere compactness assumption, the existence of error bounds for arbitrary continuous semi-algebraic functions was provided. Despite their remarkable depth, these works remained unnoticed by the optimization community during a long period (see ). At the beginning of the nineties, motivated by numerous applications, many researchers started working along these lines, in quest for quantitative results that could produce more effective tools. The survey of Pang provides a comprehensive panorama of results obtained around this time. The works of Luo and Dedieu are also important milestones in the theory. The recent works provide even stronger quantitative results by using the powerful machinery of algebraic geometry or advanced techniques of convex optimization.

Let us introduce the concepts used in this work and show how they can be arranged to devise a new and systematic approach to complexity. Let $H$ be a real Hilbert space, and let $f:H\to(-\infty,+\infty]$ be a proper lower-semicontinuous convex function achieving its minimum $\min f$ so that $\operatorname{argmin}f\neq\emptyset$. In its most simple version, an error bound is an inequality of the form

where $\omega$ is an increasing function vanishing at –called here the residual function–, and where $x$ may evolve either in the whole space or in a bounded set. Hölderian error bounds, which are very common in practice, have a simple power form

Once the question of computing constants and exponents (here $\gamma$ and $p$) for a given minimization problem is settled (see the fundamental works ), it is natural to wonder whether these concepts are connected to the complexity properties of first-order methods for minimizing $f$. Despite the important success of the error bound theory in several branches of optimization, we are not aware of a solid theory connecting the error bounds we consider (as defined in (1)), with the study of the complexity of general descent methods. There are, however, several works connecting error bounds with the convergence rates results of first-order methods (see e.g., ). See also the new and interesting work that provides a wealth of error bounds and some applications to convergence rate analysis. An important fraction of these works involves “first-order error bounds”That is, involving inequalities of the type $\|\nabla f(x)\|\geq\omega(\operatorname{dist}(x,\operatorname{argmin}f))$ (see ) that are different from those we consider here.

Our answer to the connection between complexity and “zero-order error bounds” will partially come from a related notion, also discovered by Łojasiewicz and further developed by Kurdyka in the semi-algebraic world: the Łojasiewicz gradient inequality. This inequality, also called Kurdyka-Łojasiewicz (KL) inequality (see ), asserts that for any smooth semi-algebraic function $f$ there is a smooth concave function $\varphi$ such that

for all $x$ in some neighborhood of the set $\operatorname{argmin}f$. Its generalization to the nonsmooth case has opened very surprising roads in the nonconvex world and it has allowed to perform convergence rate analyses for many important algorithms in optimization . In a first stage of the present paper we show, when $f$ is convex, that error bounds are equivalent to nonsmooth KL inequalities provided the residual function has a moderate behavior close to 0 (meaning that its derivative blows up at reasonable rate). Our result includes, in particular, all power-type examples like the ones that are often met in practiceAn absolutely crucial asset of error bounds and KL inequalities in the convex world is their global nature under a mere coercivity assumption – see Section 6..

Once we know that error bounds provide a KL inequality, one still needs to make the connection with the actual complexity of first-order methods. This is probably the main contribution in this paper: to any given convex objective $f:H\to(-\infty,+\infty]$ and descent sequence of the form

$f(x_{k})+a\|x_{k}-x_{k-1}\|^{2}\leq f(x_{k-1}),$

$\|\omega_{k}\|\leq b\|x_{k}-x_{k-1}\|$ where $\omega_{k}\in\partial f(x_{k})$, $k\geq 1,$

we associate a worst case one dimensional proximal method

Similar results for the sequence are provided. These ideas are already present in and [13, Section 3.2]. The function $\varphi^{-1}$ above –the inverse of a desingularizing function for $f$ on a convenient domain– contains almost all the information our approach provides on the complexity of descent methods. As explained previously, it depends on the precise knowledge of a KL inequality and thus, in this convex setting, of an error bound. The reader familiar with second-order methods might have recognized the spirit of the majorant method of Kantorovich , where a reduction to dimension one is used to study Newton’s method.

As explained before, our paper led us to establish several theoretical results and to clarify some questions appearing in a somehow disparate manner in the literature. We first explain how to pass from error bounds to KL inequality in the general setting of Hilbert spaces and vice versa, similar questions appear in . This result is proved by considering the interplay between the contraction semigroup generated by the subdifferential function and the $L^{1}$ contraction property of this flow. These results are connected to the geometry of the residual functions $\omega$ and break down when error bounds are too flat. This is shown in Section 6 by a dimension 2 counterexample presented in for another purpose.

Our investigations also led us to consider the problem of KL inequalities for convex functions, a problem partly tackled in . We show how to extend convex KL inequalities from a level set to the whole space. We also show that compactness and semi-algebraicity ensure that real semi-algebraic or definable coercive convex functions are automatically KL on the whole space. This result has an interesting theoretical consequence in terms of complexity: abstract descent methods for coercive semi-algebraic convex problems are systematically amenable to a full complexity analysis provided that a desingularizing function –known to exist– is explicitly computable.

Preliminaries

In this section, we recall the basic concepts, notation and some well-known results to be used throughout the paper. In what follows, $H$ is a real Hilbert space and $f:H\to(-\infty,+\infty]$ is proper, lower-semicontinuous and convex. We are interested in some properties of the function $f$ around the set of its minimizers, which we suppose to be nonempty and denote by $\operatorname{argmin}f$ or $S$. We assume, without loss of generality, that $\min f=0$.

We use the standard notation from (see also and ). The subdifferential of $f$ at $x$ is defined as

Clearly, $\hat{x}$ minimizes $f$ on $H$ if, and only if, $0\in\partial f(\hat{x})$. The domain of the point-to-set operator $\partial f:H\rightrightarrows H$ is $\operatorname{dom}\partial f:=\{x\in H:\partial f(x)\neq\emptyset\}.$ For $x\in\operatorname{dom}\partial f$, we denote by $\partial^{0}f(x)$ the least-norm element of $\partial f(x)$. The vector $\partial^{0}f(x)$ exists and is unique as it is the projection of $0\in H$ onto the nonempty closed convex set $\partial f(x)$. We have $\|\partial^{0}f(x)\|=\operatorname{dist}(0,\partial f(x))$ (when $x$ is not in $\operatorname{dom}\partial f$ we set $\|\partial^{0}f(x)\|=+\infty$). We adopt the convention $s\times(+\infty)=+\infty$ for all $s>0$.

Given $x\in H$, the function $f_{x}$, defined by

for $y\in H$, has a unique minimizer, which we denote by $\operatorname{prox}_{f}(x)$. Using Fermat’s Rule and the Moreau-Rockafellar Theorem, $\operatorname{prox}_{f}(x)$ is characterized as the unique solution of the inclusion $x-\operatorname{prox}_{f}(x)\in\partial f\left(\operatorname{prox}_{f}(x)\right).$ In particular, $\operatorname{prox}_{f}(x)\in\operatorname{dom}\partial f\subset\operatorname{dom}f\subset H$. The mapping $\operatorname{prox}_{f}:H\to H$ is the proximity operator associated to $f$. It is easy to prove that $\operatorname{prox}_{f}$ is Lipschitz continuous with constant 1.

If $C\subset H$ is nonempty, closed and convex, the indicator function of $C$ is the function $i_{C}:H\to(-\infty,\infty]$, defined by

It is proper, lower-semicontinuous and convex. Moreover, for each $x\in H$, $\partial i_{C}(x)=N_{C}(x)$, the normal cone to $C$ at $x$. In turn, $\operatorname{prox}_{i_{C}}$ is the projection operator onto $C$, which we denote by $P_{C}$.

2 Subgradient curves

where $x\in\overline{\operatorname{dom}f}$ and $y(\cdot)$ is an absolutely continuous curve in $H$. The main properties of this system $-$ for the purpose of this research $-$ are summarized in the following:

For each $x\in\overline{\operatorname{dom}f}$, there is a unique absolutely continuous curve $\chi_{x}:[0,\infty)\to H$ such that $\chi_{x}(0)=x$ and

\displaystyle\hbox{\frac{d}{dt}}\chi_{x}(t^{+})=-\partial^{0}f(\chi_{x}(t)) for all $t>0$;

\displaystyle\hbox{\frac{d}{dt}}f\left(\chi_{x}(t^{+})\right)=-\|\dot{\chi}_{x}(t^{+})\|^{2} for all $t>0$;

For each $z\in S$, the function $t\mapsto\|\chi_{x}(t)-z\|$ decreases;

The function $t\mapsto f(\chi_{x}(t))$ is nonincreasing and $\lim_{t\to\infty}f(\chi_{x}(t))=\min f$;

$\chi_{x}(t)$ converges weakly to some $\hat{x}\in S$, as $t\to\infty$.

The proof of the result above is provided in , except for part ${\rm v)}$, which was proved in . The trajectory $t\mapsto\chi_{x}(t)$ is called a subgradient curve.

3 Kurdyka-Łojasiewicz inequality

In this subsection, we present the nonsmooth Kurdyka-Łojasiewicz inequality introduced in (see also , and the fundamental works ). To simplify the notation, we write $[f<\mu]=\{x\in H:f(x)<\mu\}$ (similar notation can be guessed from the context). Let $r_{0}>0$ and set

The function $f$ satisfies the Kurdyka-Łojasiewicz (KL) inequality (or has the KL property) locally at $\bar{x}\in\operatorname{dom}f$ if there exist $r_{0}>0$, $\varphi\in\mathcal{K}(0,r_{0})$ and $\varepsilon>0$ such that

for all $x\in B(\bar{x},\varepsilon)\cap[f(\bar{x})<f(x)<f(\bar{x})+r_{0}]$. We say $\varphi$ is a desingularizing function for $f$ at $\bar{x}$. This property basically expresses the fact that a function can be made sharp by a reparameterization of its values.

If $\bar{x}$ is not a minimizer of $f$, the KL inequality is obviously satisfied at $\bar{x}$. Therefore, we focus on the case when $\bar{x}\in S$. Since $f(\bar{x})=0$, the KL inequality reads

for $x\in B(\bar{x},\varepsilon)\cap[0<f<r_{0}$]. The function $f$ has the KL property on $S$ if it does so at each point of $S$.

The Łojasiewicz gradient inequality corresponds to the case when $\varphi(s)=cs^{1-\theta}$ for some $c>0$ and $\theta\in[0,1)$. Following Łojasiewicz original presentation, (2) can be reformulated as follows

where $c^{\prime}=[(1-\theta)c]^{-1}$. The number $\theta$ is the Łojasiewicz exponent. If $f$ has the KL property and admits the same desingularizing function $\varphi$ at every point, then we say that $\varphi$ is a global desingularizing function for $f$.

KL inequalities were developed within the fascinating world of real semi-algebraic sets and functions. For that subject, we refer the reader to the book by Bochnak-Coste-Roy.

We recall the following theorem on the nonsmooth KL inequality (which follows the pioneering works of Łojasiewicz and Kurdyka ). It is one of the cornerstones of the present research:

Under an additional coercivity assumption, a global result is provided in Subsection 6.3.

4 Error bounds

Consider a nondecreasing function $\omega:[0,+\infty[\to[0,+\infty[$ with $\omega(0)=0$. The function $f$ satisfies a local error bound with residual function $\omega$ if there is $r_{0}>0$ such that

for all $x\in[0\leq f\leq r_{0}]$ (recall that $\min f=0$). Of particular importance is the case when $\omega(s)=\gamma^{-1}s^{\frac{1}{p}}$ with $\gamma>0$ and $p\geq 1$, namely:

If $f$ is convex lower semicontinuous, we can extend the error bound beyond $[0\leq f\leq r_{0}]$ by linear extrapolation. More precisely, let $x\in\operatorname{dom}f$ such that $f(x)>r_{0}$. Then $f$ is continuous on the segment $[x,P_{S}(x)]$. Therefore, there is $x_{0}\in[x,P_{S}(x)]$ such that $f(x_{0})=r_{0}$. By convexity, we have

for all $x\in H$, where $\gamma_{0}=\left(1+r_{0}^{\frac{p-1}{p}}\right)\,\gamma^{\frac{1}{p}}$. This is known in the literature as a global Hölder-type error bound (see ). Observe that it can be put under the form $\omega(f(x))\geq\operatorname{dist}(x,S)$ by simply setting $\omega(s)=\frac{1}{\gamma_{0}}(s+s^{\frac{1}{p}})$. When combined with the Łojasiewicz error bound inequality , the above remark implies immediately the following result:

where $\gamma_{0}>0$ and $p\geq 1$ is a rational number.

Error bounds with moderate growth are equivalent to Łojasiewicz inequalities

In this section, we establish a general equivalence result between error bounds and KL inequalities. Our main goal is to provide a simple and natural way of explicitly computing Łojasiewicz exponents and, more generally, desingularizing functions. To avoid perturbing the flow of our general methodology on complexity, we discuss limitations and extensions of our results later, in Section 6.

As shown in Section 4, KL inequalities allow us to derive complexity bounds for first-order methods. However, KL inequalities with known constants are in general difficult to establish while error bounds are more tractable (see e.g., and references therein). The fact that these two notions are equivalent opens a wide range of possibilities when it comes to analyzing algorithm complexity.

where $c$ is a positive constant (observe that by concavity one has necessarily $c\leq 1$). A pretty direct use of the Puiseux Lemma (see ) shows:

The following theorem asserts that if $\varphi$ has a moderate behavior, $f$ has the global KL property if, and only if, $f$ has a global error bound. Besides, the desingularizing function in the KL inequality and the residual function in the error bound are essentially the same, up to a multiplicative constant. As explained through a counterexample in subsection 6.3, the equivalence breaks down if one argues in a setting where the derivative $\varphi$ can blow up faster. This result is related to results obtained in and also shares some common techniques.

Let $f:H\to(-\infty,+\infty]$ be a proper, convex and lower-semicontinuous, with $\min f=0$. Let $r_{0}>0$, $\varphi\in\mathcal{K}(0,r_{0})$, $c>0$, $\rho>0$ and $\bar{x}\in\operatorname{argmin}f$.

[KL inequality implies error bounds] If $\varphi^{\prime}\left(f(x)\right)\|\partial^{0}f(x)\|\geq 1$ for all $x\in[0<f<r_{0}]\cap B(\bar{x},\rho)$, then $\operatorname{dist}(x,S)\leq\varphi\left(f(x)\right)$ for all $x\in[0<f<r_{0}]\cap B(\bar{x},\rho)$.

[Error bounds implies KL inequality] Conversely, if $s\varphi^{\prime}(s)\geq c\varphi(s)$ for all $s\in(0,r_{0})$ ($\varphi$ has a moderate behavior), and $\varphi(f(x))\geq\operatorname{dist}(x,S)$ for all $x\in[0<f<r_{0}]\cap B(\bar{x},\rho)$, then $\varphi^{\prime}\left(f(x)\right)\|\partial^{0}f(x)\|\geq c$ for all $x\in[0<f<r_{0}]\cap B(\bar{x},\rho)$.

(i) Recall that the mapping $[0,+\infty)\times\overline{\operatorname{dom}f}\ni(t,x)\to\chi_{x}(t)$ denotes the semiflow associated to $-\partial f$ (see previous section). Since $f$ satisfies Kurdyka-Łojasiewicz inequality, we can apply Theorem 27 of Section 6, to obtain

and the conclusion follows immediately. $\square$

In a similar fashion, we can characterize the global existence of a Łojasiewicz gradient inequality.

(Characterization of Łojasiewicz inequalities for convex functions: global case) Let $f:H\to(-\infty,+\infty]$ be a proper, convex and lower-semicontinuous, with $\min f=0$. Let $\varphi\in\mathcal{K}(0,+\infty)$ and $c>0$.

If $\varphi^{\prime}\left(f(x)\right)\|\partial^{0}f(x)\|\geq 1$ for all $x\in[0<f]$, then $\operatorname{dist}(x,S)\leq\varphi\left(f(x)\right)$ for all $x\in[0<f]$.

Conversely, if $s\varphi^{\prime}(s)\geq c\varphi(s)$ for all $s\in(0,r_{0})$ ($\varphi$ has moderate behavior), and $\varphi(f(x))\geq\operatorname{dist}(x,S)$ for all $x\in[0<f]$, then $\varphi^{\prime}\left(f(x)\right)\|\partial^{0}f(x)\|\geq c$ for all $x\in[0<f]$.

(a) Observe the slight dissymmetry between the conclusions of (i) and (ii) in Theorem 5 and Corollary 6: while a desingularizing function provides directly an error bound in (i), an error bound (with moderate growth) becomes desingularizing after a rescaling, namely $c^{-1}\varphi$. (b) (Hölderian case) When in $(ii)$ one has $\varphi(s)=\gamma s^{\frac{1}{p}}$ with $p\geq 1$, $\gamma>0$, then the constant $c$ is given by

Analytical aspects linked with the above results, such as connections with subgradient curves and nonlinear bounds, are discussed in a section devoted to further theoretical aspects of the interplay between KL inequality and error bounds. We focus here on the essential consequences we expect in terms of algorithms and complexity. With this objective in mind, we first provide some concrete examples in which a KL inequality with known powers and/or constants can be provided.

2 Examples: computing Łojasiewicz exponent through error bounds

The method we use for computing Łojasiewicz exponents is quite simple: we derive an error bound for $f$ with as much information as possible on the constants, and then we use the convexity along with either Theorem 5 or Corollary 6 to compute a desingularizing function together with a domain of desingularization; this technique appears also in a paper which only came to our knowledge during the finalization of our article.

Combining Proposition 8 and Corollary 6, the above implies:

Yet, in order to derive proper complexity bounds for ISTA we need to identify a computable constant $\gamma_{r}$ in (4). For this we shall apply a recent result from Beck-Shtern .

First let us recall some basic results on error bounds (see e.g., ). In what follows, $\|M\|$ denotes the spectral or operator norm of a real matrix $M$.It is the largest singular value of $M$, which is the square root of the largest eigenvalue of the positive-semidefinite square matrix $M^{T}M$, where $M^{T}$ is the transpose matrix of $M$.

and we assume that $X\cap Y\neq\emptyset$. There exists a constant $\nu=\nu(A,E)\geq 0$, that only depends on the pair $(A,E)$ and is known as Hoffman’s constant for the pair $(A,E)$, such that

A crucial aspect of Hoffman’s error bound is the possibility of estimating the constant $\nu$ from the data $A,E$. We will not enter into these details here, we simply refer the reader to the work of Zǎlinescu and the references therein.

Therefore, we can rewrite the above inequality as follows

2.2 Distances to an intersection: convex feasibility

For $m\geq 2$, one considers closed convex subsets $C_{1},\ldots,C_{m}$ of $H$ whose intersection contains a nonempty open ball. This proposition is a quantitative version of [12, Corollary 3.1].

Suppose that there is $\bar{x}\in H$ and $R>0$ such that

We assume $m=2$ in a first stage. Put $C=C_{1}\cap C_{2}$, $d=2\max\left\{\operatorname{dist}(x,C_{1}),\operatorname{dist}(x,C_{2})\right\}$ and fix $x\in H$. The function $\operatorname{dist}(\cdot,C_{2})$ is Lipschitz continuous with constant 1. Thus,

By taking $y=\bar{x}+\frac{R}{d}(P_{C_{1}}(x)-P_{C_{2}}P_{C_{1}}(x))$, we deduce that $y\in B(\bar{x},R)\subset C_{1}\cap C_{2}$. Now, we construct a specific point $z\in C$ as follows

Obviously $z$ is in $C_{2}$, and if we replace $y$ in $z$ by \bar{x}+\frac{R}{d}\big{(}P_{C_{1}}(x)-P_{C_{2}}P_{C_{1}}(x)\big{)}, we obtain

This implies that $z\in C_{1}\cap C_{2}$. Therefore

By combining the above results, we have $\operatorname{dist}(x,C)\leq\frac{d}{2}+\frac{d}{R+d}\|x-\bar{x}\|,$ which gives

For arbitrary $m\geq 2$, applying (13) for the two sets $C_{1}$ and $\mathop{\cap}\limits_{i=2}^{m}C_{i}$, we obtain

Repeating the process $(m-1)$ times, we obtain (12). $\square$

A potential function for the barycentric projection method. Let $C:=\displaystyle\cap_{i=1}^{m}C_{i}$. If $C\neq\emptyset$, finding a point in $C$ is equivalent to minimizing the following convex function over $H$

where $\alpha_{i}>0$ for all $i=1,\ldots,m$ and $\sum_{1}^{m}\alpha_{i}=1$. As we shall see in the next section, the gradient method applied to $f$ yields the barycentric projection method (introduced in ; see also ). We now provide an error bound for $f$ under assumption (11).

It is clear that $C=\operatorname{argmin}f=\left\{x\in H:f(x)=0\right\}$. Fix any $x_{0}\in H$. From Proposition 11, we obtain that $f$ has the following local error bound:

Combining with Theorem 5, we deduce that $f$ satisfies the Łojasiewicz inequality on $B(\bar{x},\|x_{0}-\bar{x}\|)\cap[0<f]$ with desingularizing function $\varphi(s)=\sqrt{\frac{2}{M}s\,}$, where

A potential function for the alternating projection method. Assume now that $m=2$, and set $g=i_{C_{1}}+\frac{1}{2}\operatorname{dist}(\cdot,C_{2})^{2}$ – a function related to the alternating projection method, as we shall see in a Section 5. One obviously has g(x)\geq\frac{1}{2}\big{(}\operatorname{dist}^{2}(x,C_{1})+\operatorname{dist}^{2}(x,C_{2})\big{)} for all $x\in H$. From the above remarks, we deduce that

Hence, $g$ satisfies the Łojasiewicz inequality on $B(\bar{x},\|x_{0}-\bar{x}\|)\cap[0<g]$ with desingularizing function given by

Complexity for first-order methods with sufficient decrease condition

In this section, we derive complexity bounds for first-order methods with a sufficient decrease condition, under a KL inequality. In what follows, we assume, as before, that $f:H\to(-\infty,+\infty]$ is a proper lower-semicontinuous convex function such that $S=\operatorname{argmin}f\neq\emptyset$ and $\min f=0$.

(Sufficient decrease condition) For each $k\geq 1$,

(Relative error condition) For each $k\geq 1$, there is $\omega_{k}\in\partial f(x_{k})$ such that

We point out that an additional continuity condition $-$ which is not necessary here because of the convexity of $f$ $-$ was required in .

It seems that these conditions were first considered in the seminal and inspiring work of Luo-Tseng . They were used to study convergence rates from error bounds. We adopt partly their views and we provide a double improvement: on the one hand, we show how complexity can be tackled for such dynamics, and, on the other hand, we provide a general methodology that will hopefully be used for many other methods than those considered here.

The motivation behind this definition is due to the fact that such sequences are generated by many prominent methods, such as the forward-backward method (which we describe in detail below), many trust region methods , alternating methods , and, in a much more subtle manner, sequential quadratic methods and a wealth of majorization-minimization methods . In Section 5, we essentially focus on the forward-backward method because of its simplicity and its efficiency. Clearly, many other examples could be worked out.

If $f$ is smooth and its gradient is Lipschitz continuous with constant $L$, then any sequence satisfying:

also satisfies (H2). Indeed, for every $k\geq 1$,

for $k\geq 1$. By the strong convexity, lower-semicontinuity of the argument in the right-hand side and weak topology arguments, the set of minimizers has exactly one element. On the other hand, it is easily seen that (17) is equivalent to

Moreover, using the proximity operator defined in Subsection 2.1, the latter can be rewritten as

When $h=0$, we obtain the proximal point algorithm for $g$. On the other hand, if $g=0$ it reduces to the classical explicit gradient method for $h$.

We shall see that the forward-backward method generates subgradient descent sequences if the step sizes are properly chosen.

Take $k\geq 0$. For the constant $a$, we use the fundamental inequality provided in [21, Remark 3.2(iii)]:

For $b$, we proceed as in Remark 12 above. Using the Moreau-Rockafellar Theorem, the optimality condition for the forward-backward method is given by

where $\omega_{k+1}\in\partial g(x_{k+1})$. Using the Lipschitz continuity of $\nabla h$, we obtain

If $f=g+h$ has the KL property, Theorem 14 below guarantees the strong convergence of every sequence generated by the forward-backward method.

Convergence of subgradient descent sequences follows readily from and . Although this kind of result has now became standard, we provide a direct proof for estimating thoroughly the constants at stake.

Assume first that $f(x_{k})>0$ and $\|x_{k}-x_{k-1}\|>0$ for all $k\geq 1$. Combining $({\bf H1})$, $({\bf H2})$, and using the concavity of $\varphi$ we obtain

Combining the latter with $({\bf H1})$ yields

The case when $\|x_{k}-x_{k-1}\|$ or $f(x_{k})$ vanishes for some $k$ follows easily by using the argument evoked at the beginning of the proof. $\square$

When $f$ is twice continuously differentiable and definable (in particular, if it is semi-algebraic) it is proved in that $\varphi(s)\geq O(\sqrt{s})$ near the origin. This shows that, in general, the “worst” complexity is more likely to be induced by $\varphi$ rather than the square root.

2 Complexity for subgradient descent sequences

This section is devoted to the study of complexity for first-order descent methods of KL convex functions in Hilbert spaces.

Let $0<r_{0}<\bar{r}$, we shall assume that $f$ has the KL property on $[0<f<\bar{r}]$ with desingularizing function $\varphi\in\mathcal{K}(0,\bar{r})$ (recall that $\operatorname{argmin}f\neq\emptyset$ and $\min f=0$.). Whence

for all $x\in[0<f<\bar{r}]$. Set $\alpha_{0}=\varphi(r_{0})$ and consider the function $\psi=(\varphi|_{[0,r_{0}]})^{-1}:[0,\alpha_{0}]\to[0,r_{0}]$, which is increasing and convex.

The following assumption will be useful in the sequel:

Intuitively, the function $\psi$ embodies the worst-case “profile” of $f$. As explained below, the worst-case behavior of descent methods appears indeed to be measured through $\varphi$. The assumption (A) is definitely weak, since for interesting cases $\psi$ is flat near , while it can be chosen affine for large values (see Proposition 30).

We focus on algorithms that generate subgradient descent sequences, thus complying with (H1) and (H2).

A one-dimensional worst-case proximal sequence. Set

for $k\geq 0$. Using standard arguments, one sees that $\alpha_{k}$ is well defined and positive for each $k\geq 0$. Moreover, the sequence can be interpreted through the recursion

For $k\geq 1$, set $r_{k}:=f(x_{k})$. If $r_{k}=0$ the result is trivial. Assume $r_{k}>0$, then one has also $r_{j}>0$ for $j=1,\dots,k$. Set $\beta_{k}=\psi^{-1}(r_{k})>0$ and $s_{k}=\frac{\beta_{k-1}-\beta_{k}}{\psi^{\prime}(\beta_{k})}>0$ so that $\beta_{k}$ satisfies

We shall prove that $s_{k}\geq\zeta$. Combining the KL inequality and $({\bf H2})$, we obtain that

where $\omega_{k}$ is as in $({\bf H2})$. Using $({\bf H1})$ and the formula for the derivative of the inverse function, this gives

We now use the descent Lemma on $\psi$ (see, for instance, [58, Lemma 1.30]), to obtain

The above holds for every $k\geq 1$ such that $r_{k}>0$.

To conclude we need two simple results on the prox operator in one dimension. Claim 1. Take $\lambda^{0}>\lambda^{1}$ and $\gamma>0$. Then

Proof of Claim 1. It is elementary, set $\delta=(I+\lambda^{1}\psi^{\prime})^{-1}(\gamma)\in(0,\gamma)$, one indeed has $(I+\lambda^{0}\psi^{\prime})(\delta)=(I+\lambda^{1}\psi^{\prime})(\delta)+(\lambda^{0}-\lambda^{1})\psi^{\prime}(\delta)>\gamma,$ and the result follows by the monotonicity of $I+\lambda_{0}\psi^{\prime}.$

with $\beta^{0}_{0}=\beta_{0}^{1}\in(0,r_{0}]$. Then $\beta_{k}^{0}\leq\beta_{k}^{1}$ for all $k\geq 0$.

Proof of Claim 2. We proceed by induction, the first step being trivial, we assume the result holds true for $k\geq 0$. We write

where the first inequality is due to the induction assumption (and the monotonicity of $\psi^{\prime}$), while the second one follows from Claim 1.

We now conclude by observing that $\alpha_{k},\beta_{k}$ are proximal sequences,

Recalling that $s_{k}\geq\zeta$, one can apply Claim 2 to obtain that $\alpha_{k}\geq\beta_{k}$. And thus $\psi(\alpha_{k})\geq\psi(\beta_{k})=r_{k}$. The last point follows from Theorem 14. $\square$

In many cases the function $\psi$ is nonlinear near zero and is affine beyond a given threshold $t_{0}>0$ (see subsection 2.4 or Proposition 30). This geometry reflects on the convergence rate of the estimators as follows:

A fast convergence regime is observed when $\alpha_{k}>t_{0}$. The objective is cut down by a constant value at each step.

When the sequence $\alpha_{k}$ enters $[0,t_{0}]$, a slower and restrictive complexity regime appears.

We draw the attention of the reader that our complexity result on the sequence (not only on the values) holds even in the case when there is a continuum of minimizers.

It is obvious from the proof that the following result holds.

Let $X$ be a subset of $H$. If the set $[0<f<\bar{r}]$ on which $f$ has the KL property is replaced by a more general set of the form: $\bar{X}=X\cap[0<f<\bar{r}]$ with the property that $x_{k}\in\bar{X}$ for all $k\geq 0$, then the same result holds.

In that case the complexity estimates given in Theorem 16 take the form

we obtain (29). For (30), first observe that

In view of (25), by adding (32) and (33) we obtain:

and combine this last equality with (34) to obtain the result.

Applications: feasibility problems, uniformly convex problems and compressed sensing

Let \displaystyle\big{\{}C_{i}\big{\}}_{i\in\{1,\ldots,m\}} be a family of closed convex subsets of $H$, for which there exist $R>0$ and $\bar{x}\in H$ with

where $\alpha_{i}>0$ and $\sum_{i=1}^{m}\alpha_{i}=1$.

Using the function $f=\frac{1}{2}\sum\limits_{i=1}^{m}\alpha_{i}\operatorname{dist}^{2}(\cdot,C_{i})$, studied in Subsection 3.2.2, it is easy to check that

Alternating projection algorithm. We consider here the feasibility problem in the case $m=2$. The von Neuman’s alternating projection method is given by the following recursion

With no loss of generality, we assume that $x_{0}\in C_{1}$. The sequence generated by the alternating projection method converges to a point $x^{*}\in C$. Moreover, $x_{k}\in C_{1}$ for all $k\geq 1$,

2 Uniformly convex problems

Let $\sigma$ be a positive coefficient. The function $f$ is called $p$-uniformly convex, or simply uniformly convex, if there exists $p\geq 2$ such that:

for all $x,y\in H$, $x^{*}\in\partial f(x)$. It is easy to see that $f$ satisfies the KL inequality on $H$ with $\varphi(s)=p\;\sigma^{-\frac{1}{p}}\;s^{\frac{1}{p}}$ (see ). For such a function we have

The case $p=2$ can be computed in closed form (as previously), but in general only numerical estimates are available.

Proposition 8 shows that first-order descent sequences for piecewise polynomial convex functions have a similar complexity structure. This shows that error bounds or KL inequalities capture more precisely the determinant geometrical factors behind complexity than mere uniform convexity.

Here, $\operatorname{prox}_{\lambda_{k}\mu\|\cdot\|_{1}}$ is an easily computable piecewise linear object known as the soft thresholding operator (see, for instance, ). This method has been applied widely in many contexts and is known to have a complexity O\big{(}\frac{1}{k}\big{)}. We intend to prove here that this bound can be surprisingly “improved” by our techniques.

First, recall that, according to Proposition 13, sequences generated by this method comply with (H1) and (H2), provided the stepsizes satisfy $0<\lambda^{-}\leq\lambda_{k}\leq\lambda^{+}<2/L$. Recall that the constants $a$ and $b$ can be chosen as

where $\gamma_{R}$ is known to exist and is bounded from above by the constant given in (10).

If one makes the simple choice of a constant step size all throughout the process, namely $\lambda_{k}=d/L$ with $d\in(0,2)$, one obtains

Combining the above developments with Corollary 19, we obtain the following surprising result:

(a) While it was known that ISTA has a linear asymptotic convergence rate, see in which a transparent explanation is provided, best known complexity bounds were of the type $O(\frac{1}{k})$, see . Much like in the spirit of , we show here how geometry impacts complexity –through error bounds/KL inequality– providing thus complementary results to what is usually done in this field. (b) The estimate of $\gamma_{R}$ given in Section 3.2.1 is far from being optimal and more work remains to be done to obtain acceptable/tight bounds. Observe however that the role of an optimal $\gamma_{R}$ is absolutely crucial when it comes to complexity (see (36)): a good “conditioning” ($\gamma_{R}$ not too small) provides fast convergence, while a bad oneBad conditioning are produced by flat objective functions yielding thus small constants $\gamma_{R}$. comes with “bad complexity”. (c) Assuming that the forward-backward method is performed with a constant stepsize $d/L$ as in Remark 24, the value $q$ appearing in the complexity bounds given by Theorem 25 becomes

This quantity is maximized when $d=1/2$. In this case, one obtains the optimized estimate:

Error bounds and KL inequalities for convex functions: additional properties

In this concluding section we provide further theoretical perspectives that will help the reader to understand the possibilities and the limitations of our general methodology. We give, in particular, a counterexample to the full equivalence between the KL property and error bounds, and we provide a globalization result for desingularizing functions.

This subsection essentially recalls a characterization result from on the equivalence between the KL inequality and the existence of a uniform bound for the length of subgradient trajectories verifying a subgradient differential inclusion. Due to the contraction properties of the semi-flow, the result is actually stronger than the nonconvex results provided in . For the reader’s convenience, we provide a self-contained proof.

Given $x\in\overline{\operatorname{dom}\partial f}$, we denote by $\chi_{x}:[0,\infty)\to H$ the unique solution of the differential inclusion

The following result provides an estimation on the length of subgradient trajectories, when $f$ satisfies the KL inequality. Given $x\in\overline{\operatorname{dom}f}$, and $0\leq t<s$, write

Recall that $S=\operatorname{argmin}f$ and that $\min f=0$.

Let $\bar{x}\in S$, $\rho>0$ and $\varphi\in\mathcal{K}(0,r_{0})$. The following are equivalent:

For each $y\in B(\bar{x},\rho)\cap[0<f<r_{0}]$, we have

For each $x\in B(\bar{x},\rho)\cap[0<f\leq r_{0}]$ and $0\leq t<s$, we have

Moreover, under these conditions, $\chi_{x}(t)$ converges strongly to a minimizer as $t\to\infty$.

Take $x\in B(\bar{x},\rho)\cap[0<f\leq r_{0}]$ and $0\leq t<s$. First observe that

Since $\chi_{x}(\tau)\in\operatorname{dom}\partial f\cap B(\bar{x},\rho)\cap[0<f<r_{0}]$ for all $\tau>0$ (see Theorem 1) and $-\dot{\chi}_{x}(\tau)\in\partial f(\chi_{x}(\tau))$ for almost every $\tau>0$, it follows that

for all such $\tau$. Multiplying by $\|\dot{\chi}_{x}(\tau)\|$ and integrating from $t$ to $s$, we deduce that

Conversely, take $y\in\operatorname{dom}\partial f\cap B(\bar{x},\rho)\cap[0<f<r_{0}]$ (if $y$ is not in $\operatorname{dom}\partial f$ the result is obvious). For each $h>0$ we have

Finally, since $\|\chi_{x}(t)-\chi_{x}(s)\|\leq\operatorname{length}(\chi_{x},t,s)$, we deduce from ii) that the function $t\mapsto\chi_{x}(t)$ has the Cauchy property as $t\to\infty$. $\square$

2 A counterexample: error bounds do not imply KL

This function is increasing (recall that $f$ is convex) and it satisfies

Let $\hat{\psi}$ be the convex envelope of $\psi$, that is the greatest convex function lying below $\psi$. One easily verifies that $\hat{\psi}$ enjoys the same properties (38), (39), (40). The Moreau envelope of the latter:

Hölderian error bounds do not necessarily imply Łojasiewicz inequality $-$ not even the KL inequality $-$ for nonconvex functions. The reason is elementary and consists simply in considering a function with non isolated critical values. Given $r\geq 2$, consider the $C^{r-1}$ function

3 From semi-local inequalities to global inequalities

We derive here a globalization result for KL inequalities that strongly supports the Lipschitz continuity assumption for the derivative of the inverse of a desingularizing function, an assumption that was essential to derive Theorem 16. The ideas behind the proof are inspired by .

Let $f:H\to(-\infty,+\infty]$ be a proper lower semicontinuous convex function such that $\operatorname{argmin}f\neq\emptyset$ and $\min f=0$. Assume also that $f$ has the KL property on $[0<f<r_{0}]$ with desingularizing function $\varphi\in\mathcal{K}(0,r_{0})$. Then, given $r_{1}\in(0,r_{0})$, the function given by

is desingularising for $f$ on all of $H$.

Let $x$ be such that $f(x)>r_{1}$. We would like to establish that $\|\partial^{0}f(x)\|\phi^{\prime}(f(x))\geq 1$, thus we may assume, with no loss of generality, that $\|\partial^{0}f(x)\|$ is finite. If there is $y\in[f=r_{1}]$ such that $\|\partial^{0}f(y)\|\leq\|\partial^{0}f(x)\|$, then

To show that such a $y$ exists, we use the semiflow of $\partial f$. Consider the curve $t\to\chi_{x}(t)$ and observe that there exists $t_{1}>0$ such that $f(\chi_{x}(t_{1}))=r_{1}$, because $f(\chi_{x}(0))=f(x)>r_{1}$, $f(\chi_{x}(t))\to\inf f<r_{1}$ and $f(\chi_{x}(\cdot))$ is continuous. From [23, Theorem 3.1 (6)], we know also that $\|\partial f^{0}(\chi_{x}(t))\|$ is nonincreasing. As a consequence, if we set $y=\chi_{x}(t_{1})$, we obtained the desired point and the final conclusion. $\square$

One deduces easily from the above the following result, which is close to an observation already made in . For an insight into the notion of definability of functions, a prominent example being semi-algebraicity, one is referred to . Recall that coercivity of a proper lower-semicontinuous convex function defined on a finite dimensional space is equivalent to the fact that $\operatorname{argmin}f$ is nonempty and compact.

Take $r_{0}>0$ and use to obtain $\varphi\in\mathcal{K}(0,r_{0})$ so that $f$ is KL on $[\min f<f<\min f+r_{0}]$. Then use the previous proposition to extend $\varphi$ on $(0,+\infty)$. $\square$

(Complexity of descent methods for definable coercive convex function) The previous result implies that there always exists a global measure of complexity for first-order descent methods $({\bf H1}),({\bf H2})$ of definable coercive convex lower-semicontinuous functions. This complexity bound is encoded in majorizing sequences computable from a single definable function and from the initial data. These majorizing sequences are of course defined, as in Theorem 16, by

where $\zeta$ is a parameter of the chosen first-order method.

It is a very theoretical result yet conceptually important since it shows that the understanding and the research of complexity is guaranteed by the existence of a global KL inequality and our general methodology.

Conclusions

In this paper, we devised a general methodology to estimate the complexity for descent methods which are commonly used to solve convex optimization problems: error bounds can be employed to obtain desingularizing functions in the sense of Łojasiewicz, which, in turn, provide the complexity estimates. These techniques are applied to obtain new complexity results for ISTA in compressed sensing, as well as barycentric and alternating projection method for convex feasibility.

While this work was in its final phase, we discovered the prepublication in which complementary ideas are used to develop error bounds for parametric polynomial systems and to analyze the convergence rate of some first order methods. Numerous interconnections and roads must be investigated at the light of these new discoveries, and we hope to do so in our future research.

Acknowledgements The authors would like to thank Amir Beck, Patrick Combettes, Édouard Pauwels, Marc Teboulle and the anonymous referee for very useful comments.

References