Gradient-type algorithms have a long history, going back at least to Cauchy (1847), and also a wealth of applications. Solving linear systems, Cauchy’s original motivation, is maybe the most obvious application, but many of today’s hot topics in machine learning or image processing also deal with optimization problems from an algorithmic perspective and rely on gradient-type algorithms.

The original gradient descent algorithm

which is precisely an explicit Euler method applied to the gradient flow

does not achieve very good convergence rates and much research has been dedicated to accelerating convergence.

Based on the analogy to mechanical systems, e.g., to the movement, with friction, of a heavy ball in a potential well defined by the smooth convex objective function $g$, with $L_{g}$-Lipschitz continuous gradient, Polyak [26] was able to provide the seminal idea for achieving acceleration namely the addition of inertial (momentum) terms to the gradient algorithm. His two-step iterative method, the so-called heavy ball method, takes the following form: For the initial values $x_{0}=x_{-1}\in\mathbb{R}^{m}$ and $n\in\mathbb{N}$ let:

where $\alpha_{n}\in[0,1)$ and $\beta_{n}>0$ is a step-size parameter. Recently, in [29], the convergence rate of order $\mathcal{O}\left(\frac{1}{n}\right)$ has been obtained for the heavy ball algorithm, provided $g$ is coercive, the inertial parameter $\left(\alpha_{n}\right)_{n\in\mathbb{N}}$ is a nonincreasing sequence, and the stepsize parameter satisfies $\beta_{n}=\frac{2\left(1-\alpha_{n}\right)c}{L_{g}}$, for some fixed $c\in(0,1)$ (see also [18] for an ergodic rate). More precisely, in [29], it is shown that under the previous assumption one has:

It is worthwhile mentioning that the forward-backward algorithm studied in [12] in a full nonconvex setting reduces to Polyak’s heavy ball method if the nonsmooth term vanishes; hence, it can be viewed as an extension of the heavy ball method to the case when the objective function $g$ is possible nonconvex, but still has Lipschitz continuous gradient with Lipschitz contant $L_{g}$. Indeed, Algorithm 1 from [12], in case $f\equiv 0$ and $F=\frac{1}{2}\|\cdot\|^{2}$ has the form: For the initial values $x_{0}=x_{-1}\in\mathbb{R}^{m}$ and $n\in\mathbb{N}$, let:

where $0<\underline{\beta}\leq\beta_{n}\leq\bar{\beta}<+\infty$ and $\alpha_{n}\in[0,\alpha],\alpha>0$ for all $n\geq 1$. In this particular case, convergence of the generated sequence $\left(x_{n}\right)_{n\in\mathbb{N}}$ to a critical point of the objective function $g$ can be shown under the assumption that a regularization of
the objective function satisfies the Kurdyka-Łojasiewicz property, further $\underline{\beta},\bar{\beta}$ and $\alpha>0$ satisfy:

Note that (3) implies $\alpha<\frac{1}{2}$; hence, $\alpha_{n}\in\left[0,\frac{1}{2}\right)$ for all $n\geq 1$. If $\underline{\beta}$ and $\alpha$ are positive numbers such that $1>\underline{\beta}L_{g}+2\alpha$, then by choosing $\bar{\beta}\in\left[\underline{\beta},\frac{\underline{\beta}}{\underline{\beta}L_{g}+2\alpha}\right)$, relation (3) is satisfied.

Probably the most acclaimed inertial algorithm is Nesterov’s accelerated gradient method, which in its particular form: For the initial values $x_{0}=x_{-1}\in\mathbb{R}^{m}$ and $n\in\mathbb{N}$ let:

for a convex $g$ with Lipschitz continuous gradient $L_{g}$ and step size $s\leq\frac{1}{L_{g}}$, exhibits an improved convergence rate of $\mathcal{O}\left(1/n^{2}\right)$ (see [15, 23]), and which, as highlighted by Su, Boyd, and Candès [28], (see also [5]), can be seen as the discrete counterpart of the second-order differential equation:

In this respect, it may be useful to recall that until recently little was known about the efficiency of Nesterov’s accelerated gradient method outside a convex setting. However, in [20], a Nesterov-like method, differing from the original only by a multiplicative coefficient, has been studied and convergence rates have been provided for the very general case when a regularization of the objective function $g$ has the KL property. More precisely, in [20], the following algorithm was considered.

For the initial values $x_{0}=x_{-1}\in\mathbb{R}^{m}$ and $n\in\mathbb{N}$ let:

where $\alpha>0,\beta\in(0,1)$ and $0<s<\frac{2(1-\beta)}{L_{g}}$. Unfortunately, for technical reasons, one can not allow $\beta=1$ therefore one does not have full equivalence between Algorithm (5) and Algorithm (4). However, what is lost at the inertial parameter is gained at the step size, since for $0<\beta\leq\frac{1}{2}$ one may have $s\in\left[\frac{1}{L_{g}},\frac{2}{L_{g}}\right)$. Convergence of the sequences generated by Algorithm (5) was obtained under the assumption that the regularization of the objective function $g$, namely $H(x,y)=g(x)+\frac{1}{2}\|y-x\|^{2}$, is a KL function.

In this paper, we deal with the optimization problem:

where $g:\mathbb{R}^{m}\longrightarrow\mathbb{R}$ is a Fréchet differentiable function with $L_{g}$-Lipschitz continuous gradient, i.e., there exists $L_{g}\geq 0$ such that $\|\nabla g(x)-\nabla g(y)\|\leq L_{g}\|x-y\|$ for all $x,y\in\mathbb{R}^{m}$, and we associate to (P) the following inertial algorithm of gradient type.

Consider the starting points $x_{0}=x_{-1}\in\mathbb{R}^{m}$, and for every $n\in\mathbb{N}$ let:

where we assume that

Remark 1 Observe that the inertial parameter $\alpha_{n}$ becomes negative after a number of iterations and this can be viewed as taking a backward inertial step in our algorithm. Of course, this also shows that after a number of iteration $y_{n}$ is a convex combination of $x_{n-1}$ and $x_{n}$, (see [16] for similar constructions), that is:

Another novelty of Algorithm (6) is that it allows variable step size. Moreover, it can easily be verified that whenever $\alpha>-\frac{1}{6}$ one may take $\beta>\frac{1}{L_{g}}$.

We emphasize that the analysis of the proposed algorithm (6) is intimately related to the properties of the following regularization of the objective function $g$ (see also $[11-13,20,21]$ ), that is:

In the remainder of this section, we introduce the necessary apparatus of notions and results that we will need in our forthcoming analysis.

For a differentiable function $f:\mathbb{R}^{m}\longrightarrow\mathbb{R}$, we denote by $\operatorname{crit}(f)=\left\{x\in\mathbb{R}^{m}\right.$ : $\nabla f(x)=0\}$ the set of critical points of $f$. The following so-called descent lemma (see [24]) will play an essential role in our forthcoming analysis.

Lemma 2 Let $f:\mathbb{R}^{m}\longrightarrow\mathbb{R}$ be Frèchet differentiable with $L$ Lipschitz continuous gradient. Then:

Furthermore, the set of cluster points of a given sequence $\left(x_{n}\right)_{n\in\mathbb{N}}$ will be denoted by $\omega\left(\left(x_{n}\right)_{n\in\mathbb{N}}\right)$. At the same time, the distance function to a set is defined for $A\subseteq\mathbb{R}^{m}$ as

Our convergence result relies on the concept of a KL function. For $\eta\in(0,+\infty]$, we denote by $\Theta_{\eta}$ the class of concave and continuous functions $\varphi:[0,\eta)\rightarrow$
$[0,+\infty)$ such that $\varphi(0)=0,\varphi$ is continuously differentiable on ( $0,\eta$ ), continuous at 0 and $\varphi^{\prime}(s)>0$ for all $s\in(0,\eta)$.

Definition 1 (Kurdyka-Lojasiewicz property) Let $f:\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a differentiable function. We say that $f$ satisfies the Kurdyka-Lojasiewicz (KL) property at $\bar{x}\in\mathbb{R}^{m}$ if there exists $\eta\in(0,+\infty]$, a neighborhood $U$ of $\bar{x}$ and a function $\varphi\in\Theta_{\eta}$ such that for all $x$ in the intersection:

the following inequality holds:

If $f$ satisfies the KL property at each point in $\mathbb{R}^{m}$, then $f$ is called a $KL$ function.
The function $\varphi$ is called a desingularizing function (see for instance [6]). The origins of this notion go back to the pioneering work of Łojasiewicz [22], where it is proved that for a real-analytic function $f:\mathbb{R}^{m}\rightarrow\mathbb{R}$ and a critical point $\bar{x}\in\mathbb{R}^{m}$ (that is $\nabla f(\bar{x})=0$ ), there exists $\theta\in[1/2,1)$ such that the function $|f-f(\bar{x})|^{\theta}\|\nabla f\|^{-1}$ is bounded around $\bar{x}$. This corresponds to the situation when $\varphi(s)=C(1-\theta)^{-1}s^{1-\theta}$, where $C>0$ is a given constant, and leads to the following definition.

Definition 2 (for which we refer to [2,8,22]) A differentiable function $f:\mathbb{R}^{m}\longrightarrow\mathbb{R}$ has the Łojasiewicz property with exponent $\theta\in[0,1)$ at $\bar{x}\in\operatorname{crit}(f)$ if there exists $K,\varepsilon>0$ such that:

for every $x\in\mathbb{R}^{m}$, with $\|x-\bar{x}\|<\varepsilon$.
In the above definition, for $\theta=0$, we adopt the convention $0^{0}=0$, such that if $|f(x)-f(\bar{x})|^{0}=0$, then $f(x)=f(\bar{x})$ (see [2]).

The result of Łojasiewicz allows the interpretation of the KL property as a reparametrization of the function values in order to avoid flatness around the critical points. Kurdyka [19] extended this property to differentiable functions definable in an o-minimal structure. Further extensions to the nonsmooth setting can be found in [3, 8-10].

To the class of KL functions belong semi-algebraic, real sub-analytic, semiconvex, uniformly convex, and convex functions satisfying a growth condition. We refer the reader to $[2-4,7-10]$ and the references therein for more details regarding all the classes mentioned above and illustrating examples.

Finally, an important role in our convergence analysis will be played by the following uniformized KL property given in [7, Lemma 6].

Lemma 3 Let $\Omega\subseteq\mathbb{R}^{m}$ be a compact set and let $f:\mathbb{R}^{m}\rightarrow\mathbb{R}$ be a differentiable function. Assume that $f$ is constant on $\Omega$ and $f$ satisfies the KL property at each
point of $\Omega$. Then, there exist $\varepsilon,\eta>0$ and $\varphi\in\Theta_{\eta}$ such that for all $\bar{x}\in\Omega$ and for all $x$ in the intersection:

the following inequality holds:

The outline of the paper is the following. In Section 2, we give a sufficient condition that ensures the decrease property of the regularization $H$ in the iterates, and which also ensures that the iterates gap belongs to $l^{2}$. Further, using these results, we show that the set of cluster points of the iterates is included in the set of critical points of the objective function. Finally, by means of the the KL property of $H$, we obtain that the iterates gap belongs to $l^{1}$. This implies the convergence of the iterates (see also [4, 7, 12, 20]). In Section 3, we obtain several convergence rates both for the sequences $\left(x_{n}\right)_{n\in\mathbb{N}},\left(y_{n}\right)_{n\in\mathbb{N}}$ generated by the numerical scheme (6), as well as for the function values $g\left(x_{n}\right),g\left(y_{n}\right)$ in the terms of the Łojasiewicz exponent of $g$ and $H$, respectively (see [14, 17, 20] and also [1] for convergence rates under geometrical conditions). Finally, in Section 4, we present some numerical experiments that show that our algorithm, in many cases, has better properties than the algorithms used in the literature.

We start to investigate the convergence of the proposed algorithm by showing that $H$ is decreasing along certain sequences built upon the iterates generated by (6).

Theorem 4 Let $\left(x_{n}\right)_{n\in\mathbb{N}}$ and $\left(y_{n}\right)_{n\in\mathbb{N}}$ be the sequences generated by the numerical scheme (6) and for all $n\in\mathbb{N},n\geq 1$ consider the sequences:

and

Then, there exists $N\in\mathbb{N}$ such that:
(i) The sequence $\left(g\left(y_{n}\right)+\delta_{n}\left\|x_{n}-x_{n-1}\right\|^{2}\right)_{n\geq N}$ is decreasing and $\delta_{n}>0$ for all $n\geq N$.

Assume further that $g$ is bounded from below. Then,
(ii) The sequence $\left(g\left(y_{n}\right)+\delta_{n}\left\|x_{n}-x_{n-1}\right\|^{2}\right)_{n\geq N}$ is convergent;
(iii) $\quad\sum_{n\geq 1}\left\|x_{n}-x_{n-1}\right\|^{2}<+\infty$.

Proof By applying the descent Lemma 2 to $g$, we have:

However, after rewriting the first equation in (6) as $\nabla g\left(y_{n}\right)=\frac{1}{\beta_{n}}\left(y_{n}-x_{n+1}\right)$ and taking the inner product with $y_{n+1}-y_{n}$ to obtain:

the descent inequality becomes:

Further,

and

hence:

Thus, we have:

and

Replacing the above equalities in (12) gives:

The above inequality motivates the introduction of the following notations:

and

for all $n\in\mathbb{N},n\geq 1$.

In terms of these notations, after using the equality:

we can write:

Consequently, we have:

Now, since $\alpha_{n}\longrightarrow\alpha,\beta_{n}\longrightarrow\beta$ as $n\longrightarrow+\infty$ and $\alpha\in\left(\frac{-10+\sqrt{68}}{8},0\right),0<\beta<\frac{4\alpha^{2}+10\alpha+2}{L_{g}(2\alpha+1)^{2}}$ we have:

Hence, there exists $N\in\mathbb{N}$ and $C>0,D>0$ such that for all $n\geq N$ one has:

which, in the view of (15), shows (i); that is, the sequence $g\left(y_{n}\right)+\delta_{n}\left\|x_{n}-x_{n-1}\right\|^{2}$ is decreasing for $n\geq N$.

By using (15) again, we obtain:

for all $n\geq N$, or, more convenient, that:

for all $n\geq N$. Let $r>N$. Summing up the latter relations gives:

which leads to:

Now, taking into account that $g$ is bounded from below, after letting $r\longrightarrow+\infty$ we obtain:

which proves (iii).
This also shows that:

hence

But then, using again the fact that $g$ is bounded from below, we have that the sequence $g\left(y_{n}\right)+\delta_{n}\left\|x_{n}-x_{n-1}\right\|^{2}$ is bounded from below and also decreasing (see (i)) for $n\geq N$; hence, there exists:

Remark 5 By introducing the sequence:

one can easily observe that the statements of Theorem 4 can be expressed in terms of the regularization of the objective function since $H\left(y_{n},u_{n}\right)=g\left(y_{n}\right)+\delta_{n}\left\|x_{n}-x_{n-1}\right\|^{2}$ for all $n\in\mathbb{N},n\geq 1$.

An interesting fact is that for the sequence $\left(H\left(y_{n},u_{n}\right)\right)_{n\geq N}$ to be decreasing one does not need the boundedness of the objective function $g$, but only its regularity, as can be seen in the proof of Theorem 4. The energy decay is thus a structural property of the algorithm (6) and only the existence of the limit requires the boundedness of the objective function.

Remark 6 Observe that conclusion (iii) in the hypotheses of Theorem 4 assures that the sequence $\left(x_{n}-x_{n-1}\right)_{n\in\mathbb{N}}\in l^{2}$, in particular that:

Lemma 7 In the framework of the optimization problem (P), assume that the objective function $g$ is bounded from below and consider the sequences $\left(x_{n}\right)_{n\in\mathbb{N}}$ and $\left(y_{n}\right)_{n\in\mathbb{N}}$ generated by the numerical algorithm (6) and let $\left(u_{n}\right)_{n\in\mathbb{N}}$ be defined by (18). Then, the following statements are valid:
(i) The sets of cluster points of $\left(x_{n}\right)_{n\in\mathbb{N}},\left(y_{n}\right)_{n\in\mathbb{N}}$ and $\left(u_{n}\right)_{n\in\mathbb{N}}$ coincide and are contained in the set o critical points of g, i.e.:

Proof (i) We start by proving $\omega\left(\left(x_{n}\right)_{n\in\mathbb{N}}\right)\subseteq\omega\left(\left(u_{n}\right)_{n\in\mathbb{N}}\right)$ and $\omega\left(\left(x_{n}\right)_{n\in\mathbb{N}}\right)\subseteq\omega\left(\left(y_{n}\right)_{n\in\mathbb{N}}\right)$. Bearing in mind that $\lim_{n\longrightarrow\infty}\left(x_{n}-x_{n-1}\right)=0$ and that the sequences $\left(\delta_{n}\right)_{n\in\mathbb{N}},\left(\alpha_{n}\right)_{n\in\mathbb{N}}$, and $\left(\beta_{n}\right)_{n\in\mathbb{N}}$ are convergent, the conclusion is quite straightforward. Indeed, if $\bar{x}\in\omega\left(\left(x_{n}\right)_{n\in\mathbb{N}}\right)$ and $\left(x_{n_{k}}\right)_{k\in\mathbb{N}}$ is a subsequence such that $\lim_{k\longrightarrow\infty}x_{n_{k}}=\bar{x}$, then:

and

imply that the sequences $\left(x_{n_{k}}\right)_{k\in\mathbb{N}},\left(y_{n_{k}}\right)_{k\in\mathbb{N}}$ and $\left(u_{n_{k}}\right)_{k\in\mathbb{N}}$ all converge to the same element $\bar{x}\in\mathbb{R}^{m}$. The reverse inclusions follow in a very similar manner from the definitions of $u_{n}$ and $y_{n}$.
In order to prove that $\omega\left(\left(x_{n}\right)_{n\in\mathbb{N}}\right)\subseteq\operatorname{crit}(g)$, we use the fact that $\nabla g$ is a continuous operator. So, passing to the limit in $\nabla g\left(y_{n_{k}}\right)=\frac{1}{\beta_{n_{k}}}\cdot\left(y_{n_{k}}-x_{n_{k}+1}\right)$ and taking into account that $\lim_{k\rightarrow+\infty}\beta_{n_{k}}=\beta>0$, we have:

and finally, as $y_{n_{k}}-x_{n_{k}+1}=\left(x_{n_{k}}-x_{n_{k}+1}\right)+\alpha_{n_{k}}\cdot\left(x_{n_{k}}-x_{n_{k}-1}\right)$, we obtain:

For proving the statement (ii), we rely on a direct computation yielding:

which, in turn, gives

and allows us to apply (i) to obtain the desired conclusion.
Some direct consequences of Theorem 4 (ii) and Lemma 7 are the following.
Fact 8 In the setting of Lemma 7, let $(\bar{x},\bar{x})\in\omega\left(\left(y_{n},u_{n}\right)_{n\in\mathbb{N}}\right)$. It follows that $\bar{x}\in$ crit $(\mathrm{g})$ and:

$H$ is finite and constant on the set $\omega\left(\left(y_{n},u_{n}\right)_{n\in\mathbb{N}}\right)$.

Report issue for preceding element