Fast inertial dynamics and FISTA algorithms in convex optimization. Perturbation aspects

Introduction

and consider similar questions for the corresponding algorithms. Let us give some $t_{0}>0$. The second-member $g:[t_{0},+\infty[\rightarrow\mathcal{H}$ is a perturbation term (integrable source term), such that $g(t)$ is small for large $t$. Precisely, in our main result, Theorem 2.1, assuming that $\alpha\geq 3$, and $\int_{t_{0}}^{+\infty}t\|g(t)\|dt<+\infty$, we show that any trajectory of (1) satisfies the fast convergence property

This extends the fast convergence of the values obtained by Su, Boyd and Candès in in the unperturbed case $g=0$. In Theorem 3.1, when $\alpha>3$, we show that any trajectory of (1) converges weakly to a minimizer of $\Phi$, which extends the convergence result obtained by Attouch, Peypouquet, and Redont in in the case $g=0$.

This inertial system involves a viscous damping which is attached to the term $\frac{\alpha}{t}\dot{x}(t)$. It is an isotropic linear damping with a viscous parameter $\frac{\alpha}{t}$ which vanishes asymptotically, but not too rapidly. The asymptotic behaviour of the inertial gradient-like system

with Asymptotic Vanishing Damping ((AVD) for short), has been studied by Cabot, Engler and Gaddat in -. As a main result, they proved that, under moderate decrease of $a(\cdot)$ to zero, i.e., $a(t)\to 0$ as $t\to+\infty$ with $\int_{0}^{\infty}a(t)dt=+\infty$, then for any trajectory $x(\cdot)$ of (3)

As a striking property, for the specific choice $a(t)=\frac{\alpha}{t}$, with $\alpha\geq 3$ , for example when considering

it has been proved by Su, Boyd, and Candès in that the fast convergence property of the values (2) is satisfied by the trajectories of (5). In the same article , the authors show that (5) can be seen as a continuous version of the fast convergent method of Nesterov, see ---. For the continuous dynamic, a related study concerning the case $a(t)=\frac{1}{t^{\theta}}$, $0<\theta<1$ has been developed by Jendoubi and May in , with roughly speaking $\mathcal{O}(\frac{1}{t^{1+\theta}})$ convergence. The analysis developped in does not contain the case $a(t)=\frac{\alpha}{t}$, where the introduction of an additional scaling, due to the coefficient $\alpha$, requires a specific analysis. That’s our main concern in this paper.

Our results provide new insight on the effect of perturbations or errors in the associated algorithms. They provide a guideline for the study of the preservation, under small perturbations, of the fast convergence property of the corresponding Nesterov type algorithms. Specifically we consider a perturbed version of the variant of FISTA recentely considered by Chambolle and Dossal , and Su, Boyd and Candès . We obtain fast convergence of the values in the case $\alpha\geq 3$, and convergence of the trajectories in the case $\alpha>3$. Convergence of the trajectories in the case $\alpha=3$, which corresponds to Nesterov algorithm, is still an open question.

Fast Convergence of the values

From Cauchy-Lipschitz theorem, for any Cauchy data $x(t_{0})=x_{0}\in\mathcal{H},\ \dot{x}(t_{0})=x_{1}\in\mathcal{H}$ we immediately infer the existence and uniqueness of a local solution to (6). The global existence follows from the energy estimate proved in Proposition 2.1, in the next paragraph. Throughout this paper we will use the following Gronwall-Bellman lemma, see [20, Lemme A.5] for a proof.

The following estimates are obtained by considering the global energy of the system, and showing that it is a strict Lyapunov function.

Suppose $\alpha>0$, and $\displaystyle{\int_{t_{0}}^{+\infty}\|g(t)\|dt<+\infty}$ . Then, for any orbit $x:[t_{0},+\infty[\rightarrow\mathcal{H}$ of $\mbox{{\rm(AVD)}}_{\alpha,g}$

Let us give some $T>t_{0}$. For $t_{0}\leq t\leq T$, let us define the energy function

Because of $\dot{x}$ continuous, and $g$ integrable, the energy function $W_{T}$ is well defined. After time derivation of $W_{T}$, and by using $\mbox{{\rm(AVD)}}_{\alpha,g}$, we obtain

Hence $W_{T}(\cdot)$ is a decreasing function. In particular, $W_{T}(t)\leq W_{T}(t_{0})$, i.e.,

Applying Gronwall-Bellman lemma 2.1, we obtain

This being true for arbitrary $T>t_{0}$, and $t_{0}\leq t\leq T$, we deduce that

which gives (7) and (9). As a consequence, the function $W$ (corresponding to $T=+\infty$)

Integrating (16) from $t_{0}$ to $t$, and using (13), (15), we obtain

2. The main result

Suppose that $\alpha\geq 3$, and $\displaystyle{\int_{t_{0}}^{+\infty}\tau\|g(\tau)\|d\tau<+\infty}$. Then, for any orbit $x:[t_{0},+\infty[\rightarrow\mathcal{H}$ of $\mbox{{\rm(AVD)}}_{\alpha,g}$, we have the following fast convergence of the values:

The proof is an adaptation to our setting (with an integrable source term $g$) of the argument developed by Su-Boyd-Candès in . Let us give some $T>t_{0}$, and $x^{*}\in S=\mbox{\rm{argmin}}\Phi$. For $t_{0}\leq t\leq T$, let us define the energy function

Derivation of $\mathcal{E}_{\alpha,g,T}(\cdot)$ gives

Then use $\mbox{{\rm(AVD)}}_{\alpha,g}$ in this last expression to obtain

As a consequence, for $\alpha\geq 3$, the function ${\mathcal{E}}_{\alpha,g}$ is nonincreasing. In particular, ${\mathcal{E}}_{\alpha,g}(t)\leq{\mathcal{E}}_{\alpha,g}(t_{0})$, which gives

Applying once more Gronwall-Bellman lemma 2.1, we obtain

Since $\displaystyle{\int_{t_{0}}^{+\infty}t\|g(t)\|dt<+\infty}$, it follows that

is well defined, and is a Lyapunov function for the dynamical system $\mbox{{\rm(AVD)}}_{\alpha,g}$.

Convergence of trajectories

In the case $\alpha>3$, provided that the second member $g(t)$ is sufficiently small for large $t$, we are going to show the convergence of the trajectories of the system

The following convergence result is an extension to the perturbed case (with a source term $g$) of the convergence result obtained by Attouch-Peypouquet-Redont in .

a) (weak convergence) There exists some $x^{*}\in{\rm argmin}\kern 1.19995pt\Phi$ such that

b) (fast convergence) There exists a positive constant $C$ such that

In order to analyze the convergence properties of the trajectories of system (1), we will use the Opial’s lemma that we recall in its continuous form; see also , who initiated the use of this argument to analyze the asymptotic convergence of nonlinear contraction semigroups in Hilbert spaces.

Let $S$ be a non empty subset of $\mathcal{H}$ and $x:[0,+\infty[\to\mathcal{H}$ a map. Assume that

We also need the following result concerning the integration of a first-order nonautonomous differential inequation, see .

2. Proof of the convergence results

Step 1. Let us return to the decrease property (23) which is satisfied by the Lyapunov function ${\mathcal{E}}_{\alpha,g}$:

By integration of this inequality, we obtain

By definition of ${\mathcal{E}}_{\alpha,g}$, and neglecting its nonnegative terms, we infer

To that end, we use the energy estimate which is obtained by taking the scalar product of (1) by $t^{2}\dot{x}(t)$:

By the classical derivation chain rule, and Cauchy-Schwarz inequality, we obtain

As a consequence, for some constant $C\geq 0$, depending only on the Cauchy data,

By (38) we have $\int_{t_{0}}^{\infty}s(\Phi(x(s))-\inf_{\mathcal{H}}\Phi)ds<+\infty$. Moreover $\alpha>1$. As a consequence, from (41) we deduce that, for some other constant $C$

Applying Gronwall-Bellman lemma 2.1, we obtain

Since $\displaystyle{\int_{t_{0}}^{+\infty}t\|g(t)\|dt<+\infty}$, we infer

Combining these two equations, and using (1) we obtain

By monotonicity of $\nabla\Phi$ and $\nabla\Phi(x^{*})=0$

By (45) the orbit is bounded. Hence, for some constant $C\geq 0$

By assumption $\int_{t_{0}}^{+\infty}t\|g(t)\|dt<+\infty$, and by (33) $\int_{t_{0}}^{\infty}t\|\dot{x}(t)\|^{2}dt<+\infty$. Hence $t\mapsto tk(t)\in L^{1}(t_{0},+\infty)$. Applying Lemma 3.2, with $w(t)=\dot{h}(t)$, we deduce that $w^{+}\in L^{1}(t_{0},+\infty)$. Equivalently $\dot{h}^{+}(t)\in L^{1}(t_{0},+\infty)$, which implies that the limit of $h(t)$ exists, as $t\to+\infty$. This proves item $i)$ of the Opial’s lemma. We complete the proof by observing that item $ii)$ is satisfied too. Indeed, since $\Phi(x(t))$ converges to $\inf\Phi$, we have that every weak sequential cluster point of $x(\cdot)$ is a minimizer of $\Phi$. ∎

3. Strong convergence results

Since the work of J.B. Baillon, we know that without additional assumptions, the trajectories of the gradient systems may not converge strongly. Let’s examine some practical interest situations where strong convergence of the trajectories of $\mbox{{\rm(AVD)}}_{\alpha,g}$ is satisfied.

Strong convergence under $int({\rm argmin}\kern 1.19995pt\Phi)\neq\emptyset$. We will need the following result, see (, Lemma 5.4).

Suppose that $\delta>0$, and let $f:[\delta;+\infty[\to\mathcal{H}$ be a continuous function that satisfies $f\in L^{1}(\delta;+\infty;\mathcal{H})$. Suppose that $\alpha>1$ and $x:[\delta;+\infty[\to\mathcal{H}$ is a classical solution of

Then, $x(t)$ converges strongly in $\mathcal{H}$ as $t\to\infty$.

Suppose that $\alpha>3$, $\displaystyle{\int_{t_{0}}^{+\infty}}tg(t)dt<+\infty$, and $\Phi$ satisfises $int({\rm argmin}\kern 1.19995pt\Phi)\neq\emptyset$. Let $x(\cdot)$ be a classical global solution of equation (1). Then, there exists some $x^{*}\in{\rm argmin}\kern 1.19995pt\,\Phi$ such that $x(t)\to x^{*}$ strongly as $t\to+\infty$.

We follow the same approach as that proposed in [15, Theorem 3.1]. We first observe that the assumption $int({\rm argmin}\kern 1.19995pt\Phi)\neq\emptyset$ implies the existence of some $\bar{z}\in\mathcal{H}$ and $\rho>0$ such that, for all $x\in\mathcal{H}$, $\langle\nabla\Phi(x),x-\bar{z}\rangle\geq\rho\|\nabla\Phi(x)\|$. In particular, for all $t\geq t_{0}$

Combining this inequality with (22) (that we recall below)

Let us return to (23), which after integration, and using $\alpha>3$, gives

As a consequence, by integrating (54), we deduce that

By setting $f(t)=tg(t)-t\nabla\Phi(x(t))$, we can rewrite equation (1) as

Since all assumptions of Lemma 3.3 are satisfied, we can affirm that $x(t)$ converges strongly to some $x^{*}\in\mathcal{H}$. Recalling that $\Phi(x(t))\rightarrow\inf_{\mathcal{H}}\Phi$ and that $\Phi$ is continuous, we obtain $x^{*}\in{\rm argmin}\kern 1.19995pt\,\Phi$. ∎

Suppose that $\alpha>3$, $\displaystyle{\int_{t_{0}}^{+\infty}}tg(t)dt<+\infty$, and $\Phi$ is an even function. Let $x(\cdot)$ be a classical global solution of equation (1). Then, there exists some $\bar{x}\in{\rm argmin}\kern 1.19995pt_{\mathcal{H}}\Phi$ such that $x(t)$ converges strongly to $\bar{x}$ as $t\to+\infty$.

From these two equations and (1), we deduce that

Let us now consider the energy function, $W(\tau)=\frac{1}{2}\|\dot{x}(\tau)\|^{2}+\Phi(x(\tau))+\int_{\tau}^{\infty}\langle\dot{x}(t),g(t)dt\rangle$. We have $\frac{d}{d\tau}W(\tau)=-\frac{\alpha}{\tau}\|\dot{x}(\tau)\|^{2}$, and therefore $W$ is a nonincreasing function. As a consequence, $W(\tau)\geq W(r)$, which equivalently gives

Using the convex differential inequality $\Phi(-x(r))\geq\Phi(x(\tau))-\langle\nabla\Phi(x(\tau)),x(\tau)+x(r)\rangle$, and the even property of $\Phi$, $\Phi(x(r))=\Phi(-x(r))$, we deduce that

Let us recall that, by Theorem 3.1, the trajectory $x(\cdot)$ is converging weakly, and hence bounded. Moreover, by (34), we have $\|\dot{x}(t)\|\leq\frac{C}{t}$. Hence, for some constant $C$

Let us observe that the function $k$ does not depend on $r$. Let us verify that $\tau\mapsto\tau k(\tau)\in L^{1}(t_{0},+\infty)$. By Theorem 3.1, we have $\int_{t_{0}}^{\infty}t\|\dot{x}(t)\|^{2}dt<+\infty$. By assumption, $\int_{t_{0}}^{+\infty}tg(t)dt<+\infty$. Moreover, by Fubini theorem

By integration of (56), by a similar argument as in Lemma 3.2, we obtain

where $C={t_{0}}^{\alpha}\|\dot{x}(t_{0})\|\,\|x\|_{\infty}$. Set

By using Fubini theorem once more, and the fact that $\tau\mapsto\tau k(\tau)\in L^{1}(t_{0},+\infty)$, we deduce that $K\in L^{1}(t_{0},+\infty)$. Integrating $\dot{y}(\tau)\leq K(\tau)$ from $t$ to $r$, we obtain

Since $\Phi$ is even, we have $0\in{\rm argmin}\kern 1.19995pt\Phi$. Hence $\lim_{t\to+\infty}\|x(t)\|^{2}$ exists (see the proof of Theorem 3.1). As a consequence, $x(t)$ has the Cauchy property as $t\to+\infty$, and hence converges.

The case argmin​Φ=∅.argminΦ{\rm argmin}\kern 1.19995pt\Phi=\emptyset.

Suppose $\alpha>0$, $\displaystyle{\int_{t_{0}}^{+\infty}\|g(t)\|dt<+\infty}$, and $\inf\Phi>-\infty$. Then, for any orbit $x:[t_{0},+\infty[\rightarrow\mathcal{H}$ of $\mbox{{\rm(AVD)}}_{\alpha,g}$, the following minimizing property holds

Take $\delta>0$, and let $f\in L^{1}(\delta,+\infty)$ be nonnegative. Consider a nondecreasing continuous function $\psi:(\delta,+\infty)\to(0,+\infty)$ such that $\lim\limits_{t\to+\infty}\psi(t)=+\infty$. Then,

Proof of Theorem 4.1. Let us first return to the proof of the energy estimates in Proposition 2.1. Replacing $\inf\Phi$ by $\min\Phi$ in the expression of the energy function, we obtain by the same argument

Consider the function $h(t)=\frac{1}{2}\|x(t)-z\|^{2}$, where this time, $z$ is an arbitrary element of $\mathcal{H}$. We can easily verify that

For every $t>0$, $W(t)\geq W_{\infty}$. Setting $B_{\infty}=W_{\infty}+\inf\Phi-\Phi(z)$, we obtain

Multiplying this last equation by $\frac{1}{t}$, and integrating between two reals $0<t_{0}<\theta$, we get

Let us estimate the integrals in the second member of (62):

By (58), $\int_{t_{0}}^{+\infty}\frac{1}{t}\|\dot{x}(t)\|^{2}dt<+\infty$.

Exploiting the relation $\|x(t)-z\|\leq\|x(t_{0})-z\|+\int_{t_{0}}^{t}\|\dot{x}(s)\|ds$, we obtain

Set $I=\int_{t_{0}}^{\theta}\frac{1}{t^{\alpha+1}}\frac{d}{dt}(t^{\alpha}\dot{h}(t))dt.$ By integrating by parts twice

Since $h\geq 0$, we have $-I\leq-C-\frac{1}{\theta}\dot{h}(\theta).$ Then notice that $|\dot{h}(\theta)|=|\langle\dot{x}(\theta),x(\theta)-z\rangle|\leq\|\dot{x}\|_{L^{\infty}}(\|x(0)-z\|+\theta\|\dot{x}\|_{L^{\infty}})$.

Collecting the above results, we deduce from (62) that

Dividing by $\ln(\frac{\theta}{t_{0}})$, and letting $\theta\rightarrow+\infty$, thanks to Lemma 4.1 with $\psi(t)=\ln t$, we conclude that $B_{\infty}\leq 0.$ Equivalently, for every $z\in\mathcal{H}$, $W_{\infty}\leq\Phi(z)-\inf\Phi$, which leads to $W_{\infty}\leq 0.$

On the other hand, it is easy to see that $W(t)\geq\Phi(x(t))-\inf\Phi-\|\dot{x}\|_{L^{\infty}}\int_{t}^{+\infty}g(s)ds$. Passing to the limit, as $t\rightarrow+\infty$, we deduce that

Since we always have $\inf\Phi\leq\liminf\Phi(x(t))$, we conclude that $\lim_{t\rightarrow+\infty}\Phi(x(t))=\inf\Phi.$ $\square$

In , in the unperturbed case $g=0$, it has been observed that, when ${\rm argmin}\kern 1.19995pt\Phi=\emptyset$, the fast convergence property of the values, as given in Theorem 2.1, may fail to be satisfied. A fortiori, without making additional assumption on the perturbation term, we also loose the fast convergence property in the perturbed case (take $g=0$!).

From continuous to discrete dynamics and algorithms

Time discretization of dissipative gradient-based dynamical systems leads naturally to algorithms, which, under appropriate assumptions, have similar convergence properties. This approach has been followed successfully in a variety of situations. For a general abstract discussion see , , and in the case or dynamics with inertial features see , , , , . To cover practical situations involving constraints and/or nonsmooth data, we need to broaden our scope. This leads us to consider the non-smooth structured convex minimization problem

where $\partial\Phi$ is the subdifferential of $\Phi$ in the sense of convex analysis. In order to adapt our dynamic to this non-smooth situation, we will consider the corresponding differential inclusion

This dynamic is within the following framework

The detailed study of this differential inclusion goes far beyond the scope of the present article, see for some results in the case of a fixed positive damping parameter, i.e., $a(t)=\gamma>0$ fixed, and $g=0$. A formal analysis of this sytem shows that the Lyapunov analysis, which has been developed in the previous sections, still holds, as long as one does not use the Lipschitz continuity property of the gradient (cocoercivity property). This is based on the fact that the convexity (subdifferential) inequalites are still valid, as well as the (generalized) derivation chain rule, see . Thus, setting $\Theta(x)=\Phi(x)+\Psi(x)$, we can reasonably assume that, for $\alpha>3$, and $\int_{t_{0}}^{+\infty}t\|g(t)\|dt<+\infty$, for each trajectory of (65), there is rapid convergence of the values,

and weak convergence of the trajectory to an optimal solution.

Indeed, we are going to use these ideas as a guideline, and so introduce corresponding fast converging algorithms, making the link with Nesterov -, Beck-Teboulle , and so extending the recent works of Chambolle-Dossal , Su-Boyd-Candès , Attouch-Peypouquet-Redont to the perturbed case. As a basic ingredient of the discretization procedure, in order to preserve the fast convergence properties of the dynamical system (65), we are going to discretize it implicitely with respect to the nonsmooth function $\Phi$, and explicitely with respect to the smooth function $\Psi$.

Taking a fixed time step size $h>0$, and setting $t_{k}=kh$, $x_{k}=x(t_{k})$ the implicit/explicit finite difference scheme for (65) gives

where $y_{k}$ is a linear combination of $x_{k}$ and $x_{k-1}$, that will be made precise further. After developing (67), we obtain

A natural choice for $y_{k}$ leading to a simple formulation of the algorithm (other choices are possible, offering new directions of research for the future) is

Using the classical proximal operator (equivalently, the resolvent operator of the maximal monotone operator $\partial\Phi$)

and setting $s=h^{2}$, the algorithm can be written as

For practical purpose, and in order to fit with the existing litterature on the subject, it is convenient to work with the following equivalent formulation

Indeed, we have $\frac{k-1}{k+\alpha-1}=1-\frac{\alpha}{k+\alpha-1}$. When $\alpha$ is an integer, up to the reindexation $k\mapsto k+\alpha-1$, we obtain the same sequences $(x_{k})$ and $(y_{k})$. For general $\alpha>0$, we can easily verify that the algorithm ${\rm\mbox{(AVD)}_{\alpha,g}-algo}$ is still associated with the dynamical system (65).

This algorithm is within the scope of the proximal-based inertial algorithms , , , and forward-backward methods. In the unperturbed case, $g_{k}=0$, it has been recently considered by Chambolle-Dossal , Su-Boyd-Candès , and Attouch-Peypouquet-Redont . It enjoys fast convergence properties which are very similar to that of the continuous dynamic.

For $\alpha=3$, $g_{k}=0$, we recover the classical algorithm based on Nesterov and Güler ideas, and developed by Beck-Teboulle (FISTA)

An important question regarding the (FISTA) method, as described in (73), is the convergence of sequences $(x_{k})$ and $(y_{k})$. Indeed, it is still an open question. A major interest to consider the broader context of ${\rm\mbox{(AVD)}_{\alpha,g}-algo}$ algorithms is that, for $\alpha>3$, these sequences converge, and they allow errors/perturbations, and using approximation methods. We will see that the proof of the convergence properties of ${\rm\mbox{(AVD)}_{\alpha,g}-algo}$ algorithms can be obtained in a parallel way with the convergence analysis in the continuous case in Theorem 3.1.

To simplify notations, we set $\Theta=\Phi+\Psi$, and take $x^{*}\in{\rm argmin}\kern 1.19995pt\Theta$, i.e., $\Theta(x^{*})=\inf\Theta$. In a parallel way to the continuous case, our proof is based on proving that $(\mathcal{E}(k))$ is a non-increasing sequence, where $\mathcal{E}(k)$ is the discrete version of the Lyapunov function ${\mathcal{E}}_{\alpha,g}(t)$ (we shall justify further that it is well defined), and which is given by

We have $\nabla\Psi_{k}(y)=\nabla\Psi(y)-g_{k}$, and hence $\nabla\Psi_{k}$ is still $L$-Lipschitz continuous. We can reformulate our algorithm with the help of $\Psi_{k}$ as follows

In order to analyze the convergence properties of the above algorithm, it is convenient to introduce the operator $G_{s,k}:\mathcal{H}\rightarrow\mathcal{H}$ which is defined by, for all $y\in\mathcal{H}$,

and the algorithm (77) can be formulated as

The variable $z_{k}$, which is defined in (76) by $z_{k}=\frac{k+\alpha-1}{\alpha-1}y_{k}-\frac{k}{\alpha-1}x_{k}$, will play an important role. It comes naturally into play as a discrete version of the term $\frac{t}{\alpha-1}\dot{x}(t)+x(t)-x^{*}$ which enters ${\mathcal{E}}_{\alpha,g}(t)$. Indeed,

where the last equality comes from (80) below. Let us examine the recursive relation satisfied by $z_{k}$. We have

We now use the classical formula in the proximal gradient (also called forward-backward) analysis (see , , , ): for any $x,y\in\mathcal{H}$

Note that this formula is valid since $s\leq\frac{1}{L}$, and $\nabla\Psi_{k}$ is $L$-lipschitz continuous. Let us write successively this formula at $y=y_{k}$ and $x=x_{k}$, then at $y=y_{k}$ and $x=x^{*}$. We obtain

Multiplying the first equation by $\frac{k}{k+\alpha-1}$, and the second by $\frac{\alpha-1}{k+\alpha-1}$, then adding the two resulting equations, and using $x_{k+1}=y_{k}-sG_{s,k}(y_{k})$, we obtain

Let us rewrite the scalar product in (84) as follows:

In order to write (86) in a recursive form, we use the relation (81) satisfied by $z_{k}$, which gives

and multiplying the above expression by $\frac{(\alpha-1)^{2}}{2s\left(k+\alpha-1\right)^{2}}$, we obtain

Replacing this expression in (86), we obtain

Returning to $\Theta(y)=\Theta_{k}(y)+\left\langle g_{k},y\right\rangle$, we obtain

Multiplying by $\frac{2s}{\alpha-1}\left(k+\alpha-1\right)^{2}$, we obtain

For $\alpha\geq 3$ one can easily verify that

As a consequence, from (91) we deduce that

We now develop a similar analysis as in the continuous case. Given some integer $K$, set

Hence, the sequence $(\mathcal{E}_{K}(k))$ is nonincreasing. In particular $\mathcal{E}_{K}(k)\leq\mathcal{E}_{K}(0)$, which gives

By definition of $\mathcal{G}(k)$, neglecting some positive terms, and by Cauchy-Schwarz inequality, we infer

We then use the following result, a discrete version of Gronwall’s lemma.

Let $(a_{k})$ be a sequence of positive real numbers such that

where $(\beta_{j})$ is a sequence of positive real numbers such that $\sum_{j}\beta_{j}<+\infty$, and $c$ is a positive real number. Then

Set $A_{k}:=\sup_{1\leq j\leq k}a_{j}$. Then, for $1\leq l\leq k$

Passing to the supremum with respect to $l$, with $1\leq l\leq k$, we obtain

By elementary algebraic computation, it follows that

Following the proof of Theorem 5.1. From (99), applying Lemma 5.1 with $a_{k}=\|z_{k}-x^{*}\|$, we deduce that

By definition of $\mathcal{G}(k)$, and the positivity of its constitutive elements we finally obtain

In the particular case $\alpha=3$, for a perturbed version of the classical FISTA algorithm, Schmidt, Le Roux, and Bach proved in a result similar to Theorem 5.1 concerning the fast convergence of the values.

Let us now study the convergence of the sequence $(x_{k})$.

i) \sum_{k}k\Big{(}(\Phi+\Psi)(x_{k})-\inf(\Phi+\Psi)\Big{)}<+\infty;

ii) $\sum k\|x_{k+1}-x_{k}\|^{2}<+\infty$ ;

iii) $(x_{k})\ \mbox{converges weakly, as}\ k\to+\infty,\ \mbox{to some}\ x^{*}\in{\rm argmin}\kern 1.19995pt\Phi$.

The demonstration is parallel to that of Theorem 3.1.

By (100), we know that the sequence $(z_{k})$ is bounded. Summing the above inequalities, and using $\alpha>3$, we obtain

Step 2. Now apply the fundamental inequality (82), which can be equivalently written as follows

Take $y=y_{k}$, and $x=x_{k}$. Since $x_{k+1}=y_{k}-sG_{s,k}(y_{k})$, and $y_{k}-x_{k}=\frac{k-1}{k+\alpha-1}(x_{k}-x_{k-1})$, we obtain

Equivalently, by definition of $\Theta_{k}$,

To shorten notations, set $\theta_{k}=\Theta(x_{k})-\Theta(x^{*})$, $d_{k}=\frac{1}{2}\|x_{k}-x_{k-1}\|^{2}$, $a=\alpha-1$. By Cauchy-Schwarz inequality, and with these notations, (105) gives

After multiplication by $(k+a)^{2}$, we obtain

By a similar computation as in Chambolle-Dossal [26, Corollary 2], we equivalently obtain

We now proceed to a parallel argument to that used in the proof of Theorem 3.1. Let us write (110) as follows, with $r_{k}:=(k+a)\|x_{k+1}-x_{k}\|$

We make appeal to the following discrete version of the Gronwall-Bellman lemma.

Let $(r_{k})$ be sequence of positive real numbers such that, for all $k\geq 1$

where $C$ is a positive constant, and $\sum_{k}\omega_{j}<+\infty$, with $\omega_{j}\geq 0$. Then the sequence $(r_{k})$ is bounded with

For simplicity, let us assume $\omega_{j}>0$ (one can always reduce to this situation by adding some positive constant, arbitrarily small, see Brezis for the proof of this lemma in the continuous case). Set $A_{k}:=C+\sum_{j=1}^{k}\omega_{j}r_{j}$, $A_{0}=C$. We have $r_{k}^{2}\leq A_{k}$, and $A_{k+1}-A_{k}=\omega_{k+1}r_{k+1}$. Equivalently $r_{k+1}=\frac{A_{k+1}-A_{k}}{\omega_{k+1}}$, which gives

From this, and using that the sequence $(A_{k})$ is increasing, we deduce that

Summing this inequality, and using $r_{k}\leq\sqrt{A_{k}}$ gives the claim. ∎

Following the proof of Theorem 5.2. Let us apply lemma 5.2 to inequality (111) with $r_{j}=(j+a)\|x_{j+1}-x_{j}\|$, and $\omega_{j}=(j+a)\|g_{j}\|$. By using the assumption on the perturbation term $\sum_{k}k\|g_{k}\|<+\infty$, we deduce that

Injecting this information in (109), we obtain

From $a=\alpha-1\geq 2$, (102), and the definition of $d_{k}$, we deduce that

Step 3. The last step consists in applying Opial’s lemma, whose discrete version is stated below.

Let $S$ be a non empty subset of $\mathcal{H}$, and $(x_{k})$ a sequence of elements of $\mathcal{H}$. Assume that

We are going to apply Opial’s lemma with $S={\rm argmin}\kern 1.19995pt(\Phi+\Psi)$. By Theorem 5.1, we have $(\Phi+\Psi)(x_{k})\to\min(\Phi+\Psi)$ (indeed, we have proved fast convergence). By the lower semicontinuity property of $\Phi+\Psi$ for the weak convergence of $\mathcal{H}$, we immediately obtain that item $(ii)$ of Opial’s lemma is satisfied. Thus the only point to verify is that $\lim\|x_{k}-x^{*}\|$ exists for any $x^{*}\in{\rm argmin}\kern 1.19995pt(\Phi+\Psi)$. Equivalently, we are going to show that $\lim h_{k}$ exists, with $h_{k}:=\frac{1}{2}\|x_{k}-x^{*}\|^{2}$.

The beginning of the proof is similar to , . It consists in establishing a discrete version of the second-order differential inequality (52)

We use the parallelogram identity, which in an equivalent form can be written as follows: for any $a,b,c\in\mathcal{H}$

Taking $b=x^{*}$, $a=x_{k+1}$, $c=x_{k}$, we obtain

Let us now use the monotonicity property of $\partial\Phi$. Since $-s\nabla\Psi(x^{*})\in s\partial\Phi(x^{*})$, and $y_{k}-x_{k+1}-s\nabla\Psi(y_{k})+sg_{k}\in s\partial\Phi(x_{k+1})$, we have

We now use the co-coercivity of $\nabla\Psi$

Let us use again (114) with $b=x^{*}$, $a=x_{k}$, $c=x_{k-1}$. We obtain

By definition of $y_{k}=x_{k}+\frac{k-1}{k+\alpha-1}(x_{k}-x_{k-1})$, we have $x_{k+1}-y_{k}=x_{k+1}-x_{k}-\frac{k-1}{k+\alpha-1}(x_{k}-x_{k-1})$. Hence

where $\gamma_{k}=\frac{k-1}{k+\alpha-1}$. Since $0<s<\frac{1}{L}$, we have $(1-\frac{sL}{2})>0$. On the other hand, since $\gamma_{k}<1$, we have $\gamma_{k}+{\gamma_{k}}^{2}<2\gamma_{k}$. Hence

By (100), we know that the sequence $(z_{k})$ is bounded. By (112), we know that $\sup_{k}k\|x_{k+1}-x_{k}\|<+\infty$ . Since $x_{k}=z_{k}-\frac{k+\alpha-1}{\alpha-1}(x_{k+1}-x_{k})$, we deduce that the sequence $(x_{k})$ is bounded. Returning to (123), we have, for some constant $C$

We now use the estimation that we obtained in step 2, namely $\sum_{k}k\|x_{k+1}-x_{k}\|^{2}<+\infty$. Combined with the assumption $\sum_{k}k\|g_{k}\|<+\infty$, we deduce that

We are now using the following lemma, which is a discrete version of lemma 3.2.

Let $(a_{k})$ be sequence of nonnegative real numbers such that, for all $k\geq 1$

where $\alpha\geq 3$, and $\sum_{k}k\omega_{k}<+\infty$, with $\omega_{k}\geq 0$. Then the sequence $(a_{k})$ is summable, i.e.,

Since $\alpha\geq 3$ we have $\alpha-1\geq 2$, and hence

Multiplying this expression by $(k+1)^{2}$, we obtain

Summing this inequality with respect to $j=1,2,...,k$, we obtain

Dividing by $k^{2}$, and summing with respect to $k$, we obtain

Applying Fubini theorem to this last sum, we obtain

which by $\frac{(j+1)^{2}}{j}\leq 4j$ for $j\geq 1$ gives the claim. ∎

End of the proof of Theorem 5.2. Let us apply lemma 5.4 with $a_{k}=\left(h_{k}-h_{k-1}\right)^{+}$. We obtain

which, combined with $h_{k}$ nonnegative, gives the convergence of the sequence $(h_{k})$, and ends the proof. ∎

References