# On the weak convergence of the iterates of “FISTA”.

A. Chambolle and Ch. Dossal

September 2014

## Abstract

We discuss here the convergence of the “FISTA” algorithm, which is an accelerated algorithm proposed by Beck and Teboulle, to minimize the sum $F = f + g$ of two convex, l.s.c. and proper functions, such that one, say $f$, is differentiable with Lipschitz gradient, and the proximity operator of the second is easy to compute. It builds a sequence of iterates $(x_n)_{n \in \mathbb{N}}$ for which $F(x_n) - F(x^*) \le O(1/n^2)$. However the convergence of these iterates $(x_n)_{n \in \mathbb{N}}$ is not clear. We show here that with a small modification, we can ensure the same decay of the energy as well as the weak convergence of the iterates to a minimizer.

## Introduction

Let $\mathcal{H}$ be a Hilbert space and $f$ and $g$ two convex, l.s.c functions from $\mathcal{H}$ to $\mathbb{R} \cup \{+\infty\}$ such that $f$ is differentiable with $L$-Lipschitz continuous gradient, and $g$ is “simple”, meaning that its “proximal map”

$$x \mapsto \arg \min_{y \in \mathcal{H}} g(y) + \frac{\|x - y\|^2}{2\tau}$$

can be easily computed. We consider the following minimization problem

$$\min_{x \in \mathcal{H}} F(x) := f(x) + g(x) \qquad (1)$$

and we assume that this problem has at least a solution (and possibly an infinite set of solutions).

Among the many algorithms which exist to tackle such problems, the proximal splitting algorithms, which perform alternating descents in $f$ and in $g$, are frequently used, because of their simplicity and relatively small per-iteration complexity. One can mention the Forward-Backward (FB)
# On the convergence of the iterates of "FISTA"

Antonin Chambolle, Charles H Dossal

► To cite this version:

Antonin Chambolle, Charles H Dossal. On the convergence of the iterates of "FISTA". Journal of Optimization Theory and Applications, 2015, Volume 166 ( Issue 3), pp.25. hal-01060130v3

HAL Id: hal-01060130

https://inria.hal.science/hal-01060130v3

Submitted on 20 Oct 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
splitting, the Douglas-Rachford splitting, the ADMM (alternating direction method of multipliers),<fnref n="1" /> which all have been proved to be efficient in many imaging problem such as denoising, inpainting, deconvolution, color trans- fert and many others.

This work focuses on the so-called “Fast Iterative Soft Thresholding Al- gorithm” (FISTA) which is an accelerated variant of the Forward-Backward algorithm proposed by Beck and Teboulle [3], built upon ideas of Nes- terov [12] and Güler [8].

The FB is a descent algorithm which defines a sequence $(x_n)_{n \in \mathbb{N}}$ by performing an explicit descent in $f$ and implicit in $g$. It is then shown that there exist $C > 0$, such that for all $n \in \mathbb{N}$ $F(x_n) - F(x^*) \le \frac{C}{n}$ where $x^*$ is a minimizer of $F$. Moreover the sequence $(x_n)_{n \in \mathbb{N}}$ weakly converges in $\mathcal{H}$. See for instance [14] or [3] for a simple derivation of this rate.

The sequence $(x_n)_{n \in \mathbb{N}}$ defined by the accelerated variant “FISTA” [3] satisfies, on the other hand, $F(x_n) - F(x^*) \le \frac{C'}{n^2}$ for a suitable real number $C'$, however no convergence of $(x_n)_{n \in \mathbb{N}}$ has been proved so far.

The FISTA algorithm is based on a simple over-relaxation step with varying parameter, and several choices of parameters yield roughly the same rate of convergence. This paper provides complementary results on the convergence of $F(x_n) - F(x^*)$ for some “good” choices of these parameters, for which the weak convergence of the iterates can also be proved.

In the next section, we introduce a few definitions and our main notation. In a second part, the main result on the convergence of FISTA is recalled, and we give new results on the convergence of the values of $F(x_n)$, for other over-relaxation sequences. In the third part we show the convergence of the iterates. This part is strongly inspired from a recent paper of Pock and Lorenz [10], inspired by works of Alvarez and Attouch [1] and Moufadi and Oliny [2]. The last part is focused on numerical experiments.

# 1 Notation and definitions

In the following $x^*$ denotes a solution of (1), even if this solution is not unique the value $F(x^*)$ is uniquely defined.

A key tool of FISTA is the proximal map. To any proper, convex and l.s.c function $h$ is associated the proximal map $\text{Prox}_h$ which is a function from $\mathcal{H}$ to $\mathcal{H}$ defined by

$$ \text{Prox}_h(x) = \arg \min_{y \in \mathcal{H}} h(y) + \frac{1}{2} \|x - y\|^2. $$

This function is uniquely defined and generalizes the projection on a closed convex set to convex functions.

<footnote n="1">¹See for instance [5, 9, 6, 7, 4].</footnote>
On the convergence of the iterates of “FISTA”.

A. Chambolle and Ch. Dossal

September 2014

Abstract

We discuss here the convergence of the iterates of the “FISTA” algo-
rithm, which is an accelerated algorithm proposed by Beck and Teboulle for
minimizing the sum $F = f + g$ of two convex, l.s.c. and proper functions,
such that one is differentiable with Lipschitz gradient, and the proximity
operator of the second is easy to compute. It builds a sequence of iterates
$(x_n)_{n \in \mathbb{N}}$ for which $F(x_n) - F(x^*) \le O(1/n^2)$. However the convergence of
these iterates $(x_n)_{n \in \mathbb{N}}$ is not obvious. We show here that with a small mod-
ification, we can ensure the same decay of the energy as well as the (weak)
convergence of the iterates to a minimizer.

Introduction

Let $\mathcal{H}$ be a Hilbert space and $f$ and $g$ two convex, l.s.c functions from $\mathcal{H}$ to $\mathbb{R} \cup \{+\infty\}$ such that $f$ is differentiable with $L$-Lipschitz continuous gradient, and $g$ is “simple”, meaning that its “proximal map”

$$
x \mapsto \arg \min_{y \in \mathcal{H}} g(y) + \frac{\|x - y\|^2}{2\tau}
$$

can be easily computed. We consider the following minimization problem

$$
\min_{x \in \mathcal{H}} F(x) := f(x) + g(x) \tag{1}
$$

and we assume that this problem has at least a solution (and possibly an
infinite set of solutions).

Among the many algorithms which exist to tackle such problems, the
proximal splitting algorithms, which perform alternating descents in f and
in g, are frequently used, because of their simplicity and relatively small
per-iteration complexity. One can mention the Forward-Backward (FB)
splitting, the Douglas-Rachford splitting, the ADMM (alternating direction
In the sequel, $\gamma$ denotes a non negative real number such that $\gamma \le \frac{1}{L}$ where $L$ is the Lipschitz constant of $\nabla f$ and $T$ the mapping from $\mathcal{H}$ to $\mathcal{H}$ defined by

$$T(x) := \operatorname{Prox}_{\gamma g}(x - \gamma \nabla f(x)),$$

The idea of FB is to apply this mapping from any $x_0 \in \mathcal{H}$ using Krasnosel'ski Mann iterations to get a weak convergence to a minimizer $x^*$ of $F$. The idea of FISTA is to apply this mapping using a suitable extragruadient rule to accelerate the convergence.

FISTA is defined by a sequence $(t_n)_{n \in \mathbb{N}}$ of real numbers greater than 1 and a point $x_0 \in \mathcal{H}$. Let $(t_n)_{n \in \mathbb{N}^*}$ be a sequence of non negative real numbers and $x_0 \in \mathcal{H}$, the sequences $(x_n)_{n \in \mathbb{N}}$, $(y_n)_{n \in \mathbb{N}}$ and $(u_n)_{n \in \mathbb{N}}$ and $(y_n)_{n \in \mathbb{N}}$ are defined by $y_0 = u_0 = x_0$ and for all $n \ge 1$,

$$x_n = T(y_{n-1}) \qquad (2)$$

$$y_n = \left(1 - \frac{1}{t_{n+1}}\right) x_n + \frac{1}{t_{n+1}} u_n \qquad (3)$$

$$u_n = x_{n-1} + t_n(x_n - x_{n-1}). \qquad (4)$$

The point $y_n$ may also be defined from points $x_n$ and $x_{n-1}$ by

$$y_n = x_n + \alpha_n(x_n - x_{n-1}) \quad \text{with} \quad \alpha_n := \frac{t_n - 1}{t_{n+1}} \qquad (5)$$

For suitable choices of $(t_n)_{n \in \mathbb{N}^*}$ the sequence $(F(x_n))_{n \in \mathbb{N}}$ converge to $F(x^*)$, i.e the sequence $(w_n)_{n \in \mathbb{N}}$, defined as follows,

$$w_n := F(x_n) - F(x^*) \qquad (6)$$

tends to 0 when $n$ goes to infinity.

Several proofs use bounds on the local variation of the sequence $(x_n)_{n \in \mathbb{N}}$, which we will denote $(\delta_n)_{n \in \mathbb{N}}$: variation :

$$\delta_n := \frac{1}{2} \|x_n - x_{n-1}\|_2^2 \qquad (7)$$

The sequence $(v_n)_{n \in \mathbb{N}}$ denoting the distance between $u_n$ and a fixed minimizer $x^*$ of $F$ will also be useful:

$$v_n := \frac{1}{2} \|u_n - x^*\|_2^2. \qquad (8)$$

To complete this part devoted to our notation, we define a sequence $(\rho_n)_{n \in \mathbb{N}}$, associated to $(t_n)_{n \in \mathbb{N}^*}$, whose positivity will ensure the convergence of the FISTA iterations:

$$\rho_n := t_{n-1}^2 - t_n^2 + t_n. \qquad (9)$$
method of multipliers),<fnref n="1" /> which all have been proved to be efficient in many imaging problem such as denoising, inpainting, deconvolution, color trans- fert and many others.

This work focuses on the so-called “Fast Iterative Soft Thresholding Al- gorithm” (FISTA) which is an accelerated variant of the Forward-Backward algorithm proposed by Beck and Teboulle [2], built upon ideas of Nes- terov [12] and Güler [7].

The FB is a descent algorithm which defines a sequence $(x_n)_{n \in \mathbb{N}}$ by performing an explicit descent in $f$ and implicit in $g$. It is then shown that there exist $C > 0$, such that for all $n \in \mathbb{N}$ $F(x_n) - F(x^*) \le \frac{C}{n}$ where $x^*$ is a minimizer of $F$. Moreover the sequence $(x_n)_{n \in \mathbb{N}}$ weakly converges in $\mathcal{H}$. See for instance [14] or [2] for a simple derivation of this rate.

The sequence $(x_n)_{n \in \mathbb{N}}$ defined by the accelerated variant “FISTA” [2] satisfies, on the other hand, $F(x_n) - F(x^*) \le \frac{C'}{n^2}$ for a suitable real number $C'$, however no convergence of $(x_n)_{n \in \mathbb{N}}$ has been proved so far.

The FISTA algorithm is based on a simple over-relaxation step with varying parameter, and several choices of parameters yield roughly the same rate of convergence. This paper provides complementary results on the convergence of $F(x_n) - F(x^*)$ for some “good” choices of these parameters, for which the weak convergence of the iterates can also be proved.

In the next section, we introduce a few definitions and our main notation. In a second part, the main result on the convergence of FISTA is recalled, and we give new results on the convergence of the values of $F(x_n)$, for other over-relaxation sequences. In the third part we show the convergence of the iterates. This part is strongly inspired from a recent paper of Pock and Lorenz [9], inspired by works of Alvarez and Attouch [1] and Moufadi and Oliny [10]. The last part is focused on numerical experiments.

# 1 Notation and definitions

In the following $x^*$ denotes a solution of (1), even if this solution is not unique the value $F(x^*)$ is uniquely defined.

A key tool of FISTA is the proximal map. To any proper, convex and l.s.c function $h$ is associated the proximal map $\text{Prox}_h$ which is a function from $\mathcal{H}$ to $\mathcal{H}$ defined by

$$ \text{Prox}_h(x) = \arg \min_{y \in \mathcal{H}} h(y) + \frac{1}{2} \|x - y\|^2. $$

This function is uniquely defined and generalizes the projection on a closed convex set to convex functions.

<footnote n="1">¹See for instance [4, 8, 5, 6, 3].</footnote>
## 2 Some results on the FISTA method

The main result of [3] is the following Theorem:

**Theorem 1** ([3, Thm. 4.1]). For any $x_0 \in \mathcal{H}$, if the sequence $(t_n)_{n \in \mathbb{N}^*}$ satisfies

$$ \forall n \ge 2 \quad t_n^2 - t_n \le t_{n-1}^2 \quad (10) $$

and $t_1 = 1$, if $\gamma \le \frac{1}{L}$ then the sequence $(x_n)_{n \in \mathbb{N}}$ satisfies for all $n \in \mathbb{N}$

$$ w_n \le \frac{1}{2\gamma t_n^2} \|x_0 - x^*\|_2^2 \quad (11) $$

for any minimizer $x^*$ of F.

Condition (10) can also be stated using the sequence $(\rho_n)_{n \in \mathbb{N}}$: $\forall n \ge 2$, $\rho_n \ge 0$.

The sequence defined by $t_1 = 1$ and

$$ \forall n \in \mathbb{N}^* \quad t_{n+1} = \sqrt{t_n^2 + \frac{1}{4} + \frac{1}{2}} \quad (12) $$

achieves the equality in (10). Also, it turns out that the sequence $(t_n)_{n \in \mathbb{N}}$ defined by $t_n = \frac{n+1}{2}$ satisfies condition (10). But more generally, for any $a \ge 2$ the sequence $(t_n)_{n \in \mathbb{N}}$ defined by $t_n = \frac{n+a-1}{a}$ satisfies (10). Indeed,

$$ \rho_n = \frac{1}{a^2}((n+a-2)^2-(n+a-1)^2+a(n+a-1)) = \frac{1}{a^2}((a-2)n+a^2-3a+3) \ge 0. \quad (13) $$

An induction proves that any sequence satisfying (10) (hence an inequality in (12)) and $t_1 = 1$ satisfies $t_n \le n$. Hence for any sequence defined above, Theorem 1 ensures that

$$ \forall n \in \mathbb{N} \quad w_n \le \frac{C}{n^2} \quad (14) $$

where C depends on the exact choice of the sequence $(t_n)_{n \in \mathbb{N}}$.

A priori, the best constant “C” in this bound $\frac{C}{n^2}$ will be reached if the sequence $(t_n)_{n \in \mathbb{N}}$ is the one achieving the equality in (10), given by (12), ensuring the highest value of $t_n$. This is the choice in [3], and it turns out that it is nearly optimal (since for any n there exists a problem which has lower bound of the same order, see [11, 13]). We will soon see, however, that not achieving this equality may have some advantages.

This first Theorem can easily be made more precise, as follows:

**Theorem 2.** If the sequence $(t_n)_{n \in \mathbb{N}}$ satisfies (10) and $t_1 = 1$, if $\gamma \le \frac{1}{L}$ then for any $N \ge 2$,

$$ t_{N+1}^2 w_{N+1} + \sum_{n=1}^{N} \rho_{n+1} w_n \le \frac{v_0 - v_{N+1}}{\gamma}. \quad (15) $$
In the sequel, $\gamma$ denotes a non negative real number such that $\gamma \le \frac{1}{L}$ where $L$ is the Lipschitz constant of $\nabla f$ and $T$ the mapping from $\mathcal{H}$ to $\mathcal{H}$ defined by

$$T(x) := \operatorname{Prox}_{\gamma g}(x - \gamma \nabla f(x)),$$

The idea of FB is to apply this mapping from any $x_0 \in \mathcal{H}$ using Krasnosel'ski Mann iterations to get a weak convergence to a minimizer $x^*$ of $F$. The idea of FISTA is to apply this mapping using a suitable extragruadient rule to accelerate the convergence.

FISTA is defined by a sequence $(t_n)_{n \in \mathbb{N}}$ of real numbers greater than 1 and a point $x_0 \in \mathcal{H}$. Let $(t_n)_{n \in \mathbb{N}^*}$ be a sequence of non negative real numbers and $x_0 \in \mathcal{H}$, the sequences $(x_n)_{n \in \mathbb{N}}$, $(y_n)_{n \in \mathbb{N}}$ and $(u_n)_{n \in \mathbb{N}}$ and $(y_n)_{n \in \mathbb{N}}$ are defined by $y_0 = u_0 = x_0$ and for all $n \ge 1$,

$$x_n = T(y_{n-1}) \qquad (2)$$

$$y_n = \left(1 - \frac{1}{t_{n+1}}\right) x_n + \frac{1}{t_{n+1}} u_n \qquad (3)$$

$$u_n = x_{n-1} + t_n(x_n - x_{n-1}). \qquad (4)$$

The point $y_n$ may also be defined from points $x_n$ and $x_{n-1}$ by

$$y_n = x_n + \alpha_n(x_n - x_{n-1}) \quad \text{with} \quad \alpha_n := \frac{t_n - 1}{t_{n+1}} \qquad (5)$$

For suitable choices of $(t_n)_{n \in \mathbb{N}^*}$ the sequence $(F(x_n))_{n \in \mathbb{N}}$ converge to $F(x^*)$, i.e the sequence $(w_n)_{n \in \mathbb{N}}$, defined as follows,

$$w_n := F(x_n) - F(x^*) \qquad (6)$$

tends to 0 when $n$ goes to infinity.

Several proofs use bounds on the local variation of the sequence $(x_n)_{n \in \mathbb{N}}$, which we will denote $(\delta_n)_{n \in \mathbb{N}}$: variation :

$$\delta_n := \frac{1}{2} \|x_n - x_{n-1}\|_2^2 \qquad (7)$$

The sequence $(v_n)_{n \in \mathbb{N}}$ denoting the distance between $u_n$ and a fixed minimizer $x^*$ of $F$ will also be useful:

$$v_n := \frac{1}{2} \|u_n - x^*\|_2^2. \qquad (8)$$

To complete this part devoted to our notation, we define a sequence $(\rho_n)_{n \in \mathbb{N}}$, associated to $(t_n)_{n \in \mathbb{N}^*}$, whose positivity will ensure the convergence of the FISTA iterations:

$$\rho_n := t_{n-1}^2 - t_n^2 + t_n. \qquad (9)$$
Using the several choices of sequence $(t_n)_{n \in \mathbb{N}}$ described above, Theorem 2 ensures the same decay for $w_n$ ($w_n \le \frac{C}{n^2}$) as the previous. But using (13), we readily see that for a “good” choice of the sequence $(t_n)_{n \in \mathbb{N}^*}$, one obtains the following corollary:

**Corollary 1.** Let $a > 2$ and for $n \ge 1$, $t_n = \frac{n+a-1}{a}$. Then the sequence $(nw_n)_{n \in \mathbb{N}}$ belongs to $\ell_1(\mathbb{N})$. In particular, $\liminf_{n \to \infty} n^2 \log nw_n = 0$.

The classical choice (12) for the sequence $(t_n)_{n \in \mathbb{N}^*}$ may yield the best rate of convergence for the objective, but other sequences can give better global properties of the sequence $(nw_n)_{n \in \mathbb{N}}$. (also notice that the other classical choice corresponding to $a = 2$ will not ensure this summability.) An important remark, here, is that this result is not in contradiction with the lower bounds of Nemirovski and Yudin (see [11, 13]). Indeed, they show that for any integer $n_0$ one can build a specific problem for which one will have, after $n_0$ iterations, $n_0 w_{n_0} \ge C/n_0$, however this does not mean that the sequence $(nw_n)_n$ is not eventually summable.

**Proof of Theorem 2** The proof is similar to the one of Theorem 1 in [3], however for the ease of the reader we will sketch it here. A first (standard) technical descent Lemma is useful:

**Lemma 1.** Let $\gamma \in ]0, \frac{1}{L}]$, where $L$ is the Lipschitz constant of $\nabla f$, $\bar{x} \in \mathcal{H}$ and $\hat{x} = T\bar{x}$. Then

$$ \forall x \in \mathcal{H} \quad F(\hat{x}) + \frac{\|\hat{x} - x\|^2}{2\gamma} \le F(x) + \frac{\|x - \bar{x}\|^2}{2\gamma} \quad (16) $$

*Proof.* Many proofs exist of this result, we give an elementary one which is inspired from [16]. By definition of the proximal map, $\hat{x}$ is the minimizer of the $\frac{1}{\gamma}$-strongly convex function

$$ z \mapsto g(z) + f(\bar{x}) + \langle \nabla f(\bar{x}), z - \bar{x} \rangle + \frac{1}{2\gamma} \|z - \bar{x}\|^2 $$

hence for all $z \in \mathcal{H}$

$$ g(\hat{x}) + f(\bar{x}) + \langle \nabla f(\bar{x}), \hat{x} - \bar{x} \rangle + \frac{\|\bar{x} - \hat{x}\|^2}{2\gamma} + \frac{\|z - \hat{x}\|^2}{2\gamma} \\ \le g(z) + f(\bar{x}) + \langle \nabla f(\bar{x}), z - \bar{x} \rangle + \frac{\|z - \bar{x}\|^2}{2\gamma}. $$

Since $\gamma \le 1/L$, it follows

$$ g(\hat{x}) + f(\bar{x}) + \frac{1}{2\gamma} \|z - \hat{x}\|^2 \le g(z) + f(\bar{x}) + \langle \nabla f(\bar{x}), z - \bar{x} \rangle + \frac{1}{2\gamma} \|z - \bar{x}\|^2. $$

By convexity, $f(\bar{x}) + \langle \nabla f(\bar{x}), z - \bar{x} \rangle \le f(z)$. We deduce that (16) holds and the Lemma is proved. $\square$
## 2 Some results on the FISTA method

The main result of [2] is the following Theorem:

**Theorem 1** ([2, Thm. 4.1]). For any $x_0 \in \mathcal{H}$, if the sequence $(t_n)_{n \in \mathbb{N}^*}$ satisfies

$$ \forall n \ge 2 \quad t_n^2 - t_n \le t_{n-1}^2 \quad (10) $$

and $t_1 = 1$, if $\gamma \le \frac{1}{L}$ then the sequence $(x_n)_{n \in \mathbb{N}}$ satisfies for all $n \in \mathbb{N}$

$$ w_n \le \frac{1}{2\gamma t_n^2} \|x_0 - x^*\|_2^2 \quad (11) $$

for any minimizer $x^*$ of F.

Condition (10) can also be stated using the sequence $(\rho_n)_{n \in \mathbb{N}}$: $\forall n \ge 2$, $\rho_n \ge 0$.

The sequence defined by $t_1 = 1$ and

$$ \forall n \in \mathbb{N}^* \quad t_{n+1} = \sqrt{t_n^2 + \frac{1}{4} + \frac{1}{2}} \quad (12) $$

achieves the equality in (10). Also, it turns out that the sequence $(t_n)_{n \in \mathbb{N}}$ defined by $t_n = \frac{n+1}{2}$ satisfies condition (10). But more generally, for any $a \ge 2$ the sequence $(t_n)_{n \in \mathbb{N}}$ defined by $t_n = \frac{n+a-1}{a}$ satisfies (10). Indeed,

$$ \rho_n = \frac{1}{a^2}((n+a-2)^2-(n+a-1)^2+a(n+a-1)) = \frac{1}{a^2}((a-2)n+a^2-3a+3) \ge 0. \quad (13) $$

An induction proves that any sequence satisfying (10) (hence an inequality in (12)) and $t_1 = 1$ satisfies $t_n \ge n$. Hence for any sequence defined above, Theorem 1 ensures that

$$ \forall n \in \mathbb{N} \quad w_n \le \frac{C}{n^2} \quad (14) $$

where C depends on the exact choice of the sequence $(t_n)_{n \in \mathbb{N}}$.

A priori, the best constant “C” in this bound $\frac{C}{n^2}$ will be reached if the sequence $(t_n)_{n \in \mathbb{N}}$ is the one achieving the equality in (10), given by (12), ensuring the highest value of $t_n$. This is the choice in [2], and it turns out that it is nearly optimal (since for any n there exists a problem which has lower bound of the same order, see [11, 13]). We will soon see, however, that not achieving this equality may have some advantages.

This first Theorem can easily be made more precise, as follows:

**Theorem 2.** If the sequence $(t_n)_{n \in \mathbb{N}}$ satisfies (10) and $t_1 = 1$, if $\gamma \le \frac{1}{L}$ then for any $N \ge 2$,

$$ t_{N+1}^2 w_{N+1} + \sum_{n=1}^{N} \rho_{n+1} w_n \le \frac{v_0 - v_{N+1}}{\gamma}. \quad (15) $$
*Proof of Theorem 2.* Applying this Lemma to $\bar{x} = y_n$, $\hat{x} = x_{n+1}$ and $x = (1 - \frac{1}{t_{n+1}})x_n + \frac{1}{t_{n+1}}x^*$, we find

$$F(x_{n+1}) + \frac{\left\| \frac{1}{t_{n+1}} u_{n+1} - \frac{1}{t_{n+1}} x^* \right\|_2^2}{2\gamma} \\ \le F\left(\left(1 - \frac{1}{t_{n+1}}\right)x_n + \frac{1}{t_{n+1}}x^*\right) + \frac{\left\| \frac{1}{t_{n+1}} x^* - \frac{1}{t_{n+1}} u_n \right\|_2^2}{2\gamma}$$

Using the convexity of $F$ it follows

$$F(x_{n+1}) - F(x^*) - \left(1 - \frac{1}{t_{n+1}}\right) (F(x_n) - F(x^*)) \\ \le \frac{\|u_n - x^*\|_2^2}{2\gamma t_{n+1}^2} - \frac{\|u_{n+1} - x^*\|_2^2}{2\gamma t_{n+1}^2}$$

Using definitions of $w_n$ and $v_n$ this inequality can be stated

$$t_{n+1}^2 w_{n+1} - (t_{n+1}^2 - t_{n+1}) w_n \le \frac{v_n - v_{n+1}}{\gamma} \quad (17)$$

Summing these inequalities from $n=1$ to $n=N$ leads to

$$t_{N+1}^2 w_{N+1} + \sum_{n=1}^{N} \rho_{n+1} w_n \le \frac{v_0 - v_{N+1}}{\gamma}. \quad (18)$$

which ends the proof of Theorem 2. □

We can deduce another useful corollary:

**Corollary 2.** Let $a > 2$ and for $n \ge 1$, $t_n = \frac{n+a-1}{a}$. Then the sequence $(n\delta_n)_{n \in \mathbb{N}}$ belongs to $\ell_1(\mathbb{N})$, in particular $\liminf_{n \to \infty} n^2 \log n\delta_n = 0$. In addition, there exists $C > 0$ such that for all $n \in \mathbb{N}^*$, $\delta_n \le \frac{C}{n^2}$.

This results which is a consequence of Corollary 1 is the key to prove the convergence of the sequence $(x_n)_{n \in \mathbb{N}}$.

*Proof.* Applying Lemma 1 to $\bar{x} = y_n = x_n + \alpha_n(x_n - x_{n-1})$, and $x = x_n$ leads to

$$F(x_{n+1}) + \frac{\|x_n - x_{n+1}\|^2}{2\gamma} \le F(x_n) + \frac{\alpha_n^2 \|x_n - x_{n-1}\|^2}{2\gamma}$$

which can be written with definitions of $w_n$ and $\delta_n$

$$\delta_{n+1} - \alpha_n^2 \delta_n \le \gamma(w_n - w_{n+1})$$
Using the several choices of sequence $(t_n)_{n \in \mathbb{N}}$ described above, Theorem 2 ensures the same decay for $w_n$ ($w_n \le \frac{C}{n^2}$) as the previous. But using (13), we readily see that for a “good” choice of the sequence $(t_n)_{n \in \mathbb{N}^*}$, one obtains the following corollary:

**Corollary 1.** Let $a > 2$ and for $n \ge 1$, $t_n = \frac{n+a-1}{a}$. Then the sequence $(nw_n)_{n \in \mathbb{N}}$ belongs to $\ell_1(\mathbb{N})$. In particular, $\liminf_{n \to \infty} n^2 \log nw_n = 0$.

The classical choice (12) for the sequence $(t_n)_{n \in \mathbb{N}^*}$ may yield the best rate of convergence for the objective, but other sequences can give better global properties of the sequence $(nw_n)_{n \in \mathbb{N}}$. (also notice that the other classical choice corresponding to $a = 2$ will not ensure this summability.) An important remark, here, is that this result is not in contradiction with the lower bounds of Nemirovski and Yudin (see [11, 13]). Indeed, they show that for any integer $n_0$ one can build a specific problem for which one will have, after $n_0$ iterations, $n_0 w_{n_0} \ge C/n_0$, however this does not mean that the sequence $(nw_n)_n$ is not eventually summable.

**Proof of Theorem 2** The proof is similar to the one of Theorem 1 in [2], however for the ease of the reader we will sketch it here. A first (standard) technical descent Lemma is useful:

**Lemma 1.** Let $\gamma \in ]0, \frac{1}{L}]$, where $L$ is the Lipschitz constant of $\nabla f$, $\bar{x} \in \mathcal{H}$ and $\hat{x} = T\bar{x}$. Then

$$ \forall x \in \mathcal{H} \quad F(\hat{x}) + \frac{\|\hat{x} - x\|^2}{2\gamma} \le F(x) + \frac{\|x - \bar{x}\|^2}{2\gamma} \quad (16) $$

*Proof.* Many proofs exist of this result, we give an elementary one which is inspired from [16]. By definition of the proximal map, $\hat{x}$ is the minimizer of the $\frac{1}{\gamma}$-strongly convex function

$$ z \mapsto g(z) + f(\bar{x}) + \langle \nabla f(\bar{x}), z - \bar{x} \rangle + \frac{1}{2\gamma} \|z - \bar{x}\|^2 $$

hence for all $z \in \mathcal{H}$

$$ \begin{aligned} & g(\hat{x}) + f(\bar{x}) + \langle \nabla f(\bar{x}), \hat{x} - \bar{x} \rangle + \frac{\|\bar{x} - \hat{x}\|^2}{2\gamma} + \frac{\|z - \hat{x}\|^2}{2\gamma} \\ & \le g(z) + f(\bar{x}) + \langle \nabla f(\bar{x}), z - \bar{x} \rangle + \frac{\|z - \bar{x}\|^2}{2\gamma}. \end{aligned} $$

Since $\gamma \le 1/L$, it follows

$$ g(\hat{x}) + f(\hat{x}) + \frac{1}{2\gamma} \|z - \hat{x}\|^2 \le g(z) + f(\bar{x}) + \langle \nabla f(\bar{x}), z - \bar{x} \rangle + \frac{1}{2\gamma} \|z - \bar{x}\|^2. $$

By convexity, $f(\bar{x}) + \langle \nabla f(\bar{x}), z - \bar{x} \rangle \le f(z)$. We deduce that (16) holds and the Lemma is proved. $\square$
If $t_n = \frac{n+a-1}{a}$, $\alpha_n = \frac{t_n-1}{t_{n+1}} = \frac{n-1}{n+a}$.

Multiplying this inequality by $(n+a)^2$ and summing from $n=1$ to $n=N$ leads to

$$ \sum_{n=1}^{N} (n+a)^2 (\delta_{n+1} - \alpha_n^2 \delta_n) \leq \gamma \sum_{n=1}^{N} (n+a)^2 (w_n - w_{n+1}), $$

which gives

$$ (N+a)^2 \delta_{N+1} + \sum_{n=2}^{N} ((n+a-1)^2 - (n+a)^2 \alpha_n^2) \delta_n \leq \gamma \left( (a+1)^2 w_1 - (N+a)^2 w_{N+1} + \sum_{n=2}^{N} ((n+a)^2 - (n+a-1)^2) w_n \right) $$

that is

$$ (N+a)^2 \delta_{N+1} + \sum_{n=2}^{N} a(2n-2+a)\delta_n \leq \gamma \left( (a+1)^2 w_1 - (N+a)^2 w_{N+1} + \sum_{n=2}^{N} (2n+2a-1)w_n \right) $$

By Corollary 1 and since we have assumed $a > 2$, the right part of the inequality is uniformly bounded independently of $N$, which ensures that the sequence $(n\delta_n)_{n \in \mathbb{N}}$ belongs to $\ell_1(\mathbb{N})$. It also follows that $N^2\delta_{N+1}$ is globally bounded. $\square$

# 3 Convergence of the iterates of FISTA

In this section, we show the following Theorem

**Theorem 3.** Let $a > 2$ be a positive real number, and for all $n \in \mathbb{N}$ let $t_n = \frac{n+a-1}{a}$. Then the sequence $(x_n)_{n \in \mathbb{N}}$ given by FISTA weakly converges to a minimizer of $F$.

The proof of the theorem follows the ideas of Pock and Lorenz, in the proof of Theorem 1 in [10]—see also [1]. The two main differences between our setting and the setting of [10] are:

1. We do not assume the existence of $\alpha < 1$ such that $\forall n \geq 1$, $\alpha_n \leq \alpha$;

2. The sequence $(\delta_n)_{n \in \mathbb{N}}$ produced by FISTA, with a good choice of the sequence $(t_n)$, has stronger properties than in [10].
Proof of Theorem 2. Applying this Lemma to $\bar{x} = y_n$, $\hat{x} = x_{n+1}$ and $x = (1 - \frac{1}{t_{n+1}})x_n + \frac{1}{t_{n+1}}x^*$, we find

$$F(x_{n+1}) + \frac{\left\| \frac{1}{t_{n+1}} u_{n+1} - \frac{1}{t_{n+1}} x^* \right\|_2^2}{2\gamma} \\ \le F\left(\left(1 - \frac{1}{t_{n+1}}\right)x_n + \frac{1}{t_{n+1}}x^*\right) + \frac{\left\| \frac{1}{t_{n+1}} x^* - \frac{1}{t_{n+1}} u_n \right\|_2^2}{2\gamma}$$

Using the convexity of $F$ it follows

$$F(x_{n+1}) - F(x^*) - \left(1 - \frac{1}{t_{n+1}}\right) (F(x_n) - F(x^*)) \\ \le \frac{\|u_n - x^*\|_2^2}{2\gamma t_{n+1}^2} - \frac{\|u_{n+1} - x^*\|_2^2}{2\gamma t_{n+1}^2}$$

Using definitions of $w_n$ and $v_n$ this inequality can be stated

$$t_{n+1}^2 w_{n+1} - (t_{n+1}^2 - t_{n+1}) w_n \le \frac{v_n - v_{n+1}}{\gamma} \quad (17)$$

Summing these inequalities from $n=1$ to $n=N$ leads to

$$t_{N+1}^2 w_{N+1} + \sum_{n=1}^{N} \rho_{n+1} w_n \le \frac{v_0 - v_{N+1}}{\gamma}. \quad (18)$$

which ends the proof of Theorem 2. □

We can deduce another useful corollary:

**Corollary 2.** Let $a > 2$ and for $n \ge 1$, $t_n = \frac{n+a-1}{a}$. Then the sequence $(n\delta_n)_{n \in \mathbb{N}}$ belongs to $\ell_1(\mathbb{N})$, in particular $\liminf_{n \to \infty} n^2 \log n\delta_n = 0$. In addition, there exists $C > 0$ such that for all $n \in \mathbb{N}^*$, $\delta_n \le \frac{C}{n^2}$.

This results which is a consequence of Corollary 1 is the key to prove the convergence of the sequence $(x_n)_{n \in \mathbb{N}}$.

*Proof.* Applying Lemma 1 to $\bar{x} = y_n = x_n + \alpha_n(x_n - x_{n-1})$, and $x = x_n$ leads to

$$F(x_{n+1}) + \frac{\|x_n - x_{n+1}\|^2}{2\gamma} \le F(x_n) + \frac{\alpha_n^2 \|x_n - x_{n-1}\|^2}{2\gamma}$$

which can be written with definitions of $w_n$ and $\delta_n$

$$\delta_{n+1} - \alpha_n^2 \delta_n \le \gamma(w_n - w_{n+1})$$
It turns out that Corollary 2 is crucial, while classical bounds on $\delta_n$ which only show the existence of a constant $C > 0$ such that $\delta_n \le \frac{C}{n^2}$ are not sufficient.

Before giving the complete proof of this result, several remarks can be done.

1. From Corollary 2 it follows that the sequence $(n(x_{n+1} - x_n))_{n \in \mathbb{N}}$ is bounded, moreover from (18) it follows that the sequence $(v_n)_{n \in \mathbb{N}}$ defined in (8) is also bounded (hence $(u_n)_{n \in \mathbb{N}}$). These two facts imply that the sequence $((x_n)_{n \in \mathbb{N}})$ is bounded, hence weakly sequentially compact.

2. Assume we have a subsequence which weakly converges to a $\tilde{x} \in \mathcal{H}$, $x_\nu \to \tilde{x}$: then since the sequence $(\delta_n)_{n \in \mathbb{N}}$ tends to 0, $y_\nu \to \tilde{x}$ which shows that $\tilde{x}$ is a fixed point of the nonexpansive operator $T$. Hence it is a minimizer of $F$.

If we are able to prove that the sequence $\|x_n - x^*\|$ has a limit for any minimizer $x^*$ of $F$, Theorem 3 will follow, from points 1. and 2. above and the observation that if $x_\nu \to \tilde{x}$ and $x_{\nu'} \to \tilde{x}'$, then using $\lim_\nu \|x_\nu - \tilde{x}\|^2 = \lim_{\nu'} \|x_{\nu'} - \tilde{x}'\|^2$ and the same equality with $\tilde{x}'$, it follows $\|\tilde{x} - \tilde{x}'\|^2 = 0$ (this is Opial's Theorem [15]).

*Proof of Theorem 3.* Let us define for all $j \ge 1$ and for all $k \ge j$

$$ \beta_{j,k} = \prod_{l=j}^{k} \alpha_l = \prod_{l=j}^{k} \frac{l-1}{l+a} $$

and $\beta_{j,k} = 1$ if $j > k$.

Since $\alpha_1 = 0, \forall k > 1, \beta_{1,k} = 0$. Moreover since $a > 2$,

$$ \beta_{j,k} \le \prod_{l=j}^{k} \frac{l-1}{l+2} $$

Hence, for all $j \ge 2$ and for all $k \ge 1$, $\beta_{j,k} \le 1$, while if $k - j \ge 2$,

$$ \beta_{j,k} \le \left( \frac{j+1}{k} \right)^3 $$

It follows that for all $j \ge 2$,

$$ \begin{aligned} \sum_{k=j}^{+\infty} \beta_{j,k} &\le 2 + \sum_{k=j+2}^{+\infty} \beta_{j,k} \le 2 + \sum_{k=j+2}^{+\infty} \left(\frac{j+1}{k}\right)^3 \le 2 + (j+1)^3 \sum_{k=j+2}^{+\infty} \frac{1}{k^3} \\ &\le 2 + (j+1)^3 \int_{t=j+1}^{+\infty} \frac{dt}{t^3} \le 2 + (j+1)^3 \frac{1}{2(j+1)^2} \end{aligned} $$
If $t_n = \frac{n+a-1}{a}$, $\alpha_n = \frac{t_n-1}{t_{n+1}} = \frac{n-1}{n+a}$.

Multiplying this inequality by $(n+a)^2$ and summing from $n=1$ to $n=N$ leads to

$$ \sum_{n=1}^{N} (n+a)^2 (\delta_{n+1} - \alpha_n^2 \delta_n) \le \gamma \sum_{n=1}^{N} (n+a)^2 (w_n - w_{n+1}), $$

which gives

$$ (N+a)^2 \delta_{N+1} + \sum_{n=2}^{N} ((n+a-1)^2 - (n+a)^2 \alpha_n^2) \delta_n \le \gamma \left( (a+1)^2 w_1 - (N+a)^2 w_{N+1} + \sum_{n=2}^{N} ((n+a)^2 - (n+a-1)^2) w_n \right) $$

that is

$$ (N+a)^2 \delta_{N+1} + \sum_{n=2}^{N} a(2n-2+a)\delta_n \le \gamma \left( (a+1)^2 w_1 - (N+a)^2 w_{N+1} + \sum_{n=2}^{N} (2n+2a-1)w_n \right) $$

By Corollary 1 and since we have assumed $a > 2$, the right part of the inequality is uniformly bounded independently of $N$, which ensures that the sequence $(n\delta_n)_{n \in \mathbb{N}}$ belongs to $\ell_1(\mathbb{N})$. It also follows that $N^2\delta_{N+1}$ is globally bounded. $\square$

# 3 Convergence of the iterates of FISTA

In this section, we show the following Theorem

**Theorem 3.** Let $a > 2$ be a positive real number, and for all $n \in \mathbb{N}$ let $t_n = \frac{n+a-1}{a}$. Then the sequence $(x_n)_{n \in \mathbb{N}}$ given by FISTA weakly converges to a minimizer of $F$.

The proof of the theorem follows the ideas of Pock and Lorenz, in the proof of Theorem 1 in [9]—see also [1]. The two main differences between our setting and the setting of [9] are:

1. We do not assume the existence of $\alpha < 1$ such that $\forall n \ge 1$, $\alpha_n \le \alpha$;

2. The sequence $(\delta_n)_{n \in \mathbb{N}}$ produced by FISTA, with a good choice of the sequence $(t_n)$, has stronger properties than in [9].
and then

$$ \sum_{k=j}^{+\infty} \beta_{j,k} \le \frac{j+5}{2}. \qquad (19) $$

Let us define

$$ \Phi_n = \frac{1}{2} \|x_n - x^*\|_2^2 \quad \text{and} \quad \Gamma_n = \frac{1}{2} \|x_{n+1} - y_n\|_2^2 $$

From the identity

$$ \langle a-b, a-c \rangle = \frac{1}{2} \|a-b\|_2^2 + \frac{1}{2} \|a-c\|_2^2 - \frac{1}{2} \|b-c\|_2^2 \quad (20) $$

we have by using the definition of $y_n$

$$ \Phi_n - \Phi_{n+1} = \delta_{n+1} + \langle y_n - x_{n+1}, x_{n+1} - x^* \rangle - \alpha_n \langle x_n - x_{n-1}, x_{n+1} - x^* \rangle \quad (21) $$

Then, using the monoticity of $\partial g$, we deduce that for any $z_{n+1} \in \partial g(x_{n+1})$ and for any $z^* \in \partial g(x^*)$

$$ \langle \gamma z_{n+1} - \gamma z^*, x_{n+1} - x^* \rangle \ge 0 $$

By definition of $x^*$, $-\nabla(f(x^*)) \in \partial g(x^*)$ and $y_n - x_{n+1} - \gamma \nabla f(y_n) \in \gamma \partial g(x_{n+1})$.

It follows

$$ \begin{aligned} \langle y_n - x_{n+1} - \gamma \nabla f(y_n) + \gamma \nabla f(x^*), x_{n+1} - x^* \rangle &\ge 0 \\ \langle y_n - x_{n+1}, x_{n+1} - x^* \rangle + \gamma \langle \nabla f(x^*) - \nabla f(y_n), x_{n+1} - x^* \rangle &\ge 0 \end{aligned} $$

Combining with (21) we obtain

$$ \Phi_n - \Phi_{n+1} \ge \delta_{n+1} + \gamma \langle \nabla f(y_n) - \nabla f(x^*), x_{n+1} - x^* \rangle - \alpha_n \langle x_n - x_{n-1}, x_{n+1} - x^* \rangle. \quad (22) $$

From the co-coercivity of $\nabla f$, we have

$$ \begin{aligned} \langle \nabla f(y_n) - \nabla f(x^*), x_{n+1} - x^* \rangle &= \langle \nabla f(y_n) - \nabla f(x^*), x_{n+1} - y_n + y_n - x^* \rangle \\ &\ge \frac{1}{L} \| \nabla f(y_n) - \nabla f(x^*) \|_2^2 + \langle \nabla f(y_n) - \nabla f(x^*), x_{n+1} - y_n \rangle \\ &\ge \frac{1}{L} \| \nabla f(y_n) - \nabla f(x^*) \|_2^2 - \frac{1}{L} \| \nabla f(y_n) - \nabla f(x^*) \|_2^2 - \frac{L}{2} \Gamma_n \\ &\ge -\frac{L}{2} \Gamma_n. \end{aligned} $$

Substituting back into (22), we get

$$ \Phi_n - \Phi_{n+1} \ge \delta_{n+1} - \frac{\gamma L}{2} \Gamma_n - \alpha_n \langle x_n - x_{n-1}, x_{n+1} - x^* \rangle, $$
It turns out that Corollary 2 is crucial, while classical bounds on $\delta_n$ which only show the existence of a constant $C > 0$ such that $\delta_n \le \frac{C}{n^2}$ are not sufficient.

Before giving the complete proof of this result, several remarks can be done.

1. From Corollary 2 it follows that the sequence $(n(x_{n+1} - x_n))_{n \in \mathbb{N}}$ is bounded, moreover from (18) it follows that the sequence $(v_n)_{n \in \mathbb{N}}$ defined in (8) is also bounded (hence $(u_n)_{n \in \mathbb{N}}$). These two facts imply that the sequence $((x_n)_{n \in \mathbb{N}})$ is bounded, hence weakly sequentially compact.

2. Assume we have a subsequence which weakly converges to a $\tilde{x} \in \mathcal{H}$, $x_\nu \to \tilde{x}$: then since the sequence $(\delta_n)_{n \in \mathbb{N}}$ tends to 0, $y_\nu \to \tilde{x}$ which shows that $\tilde{x}$ is a fixed point of the nonexpansive operator $T$. Hence it is a minimizer of $F$.

If we are able to prove that the sequence $\|x_n - x^*\|$ has a limit for any minimizer $x^*$ of $F$, Theorem 3 will follow, from points 1. and 2. above and the observation that if $x_\nu \to \tilde{x}$ and $x_{\nu'} \to \tilde{x}'$, then using $\lim_{\nu'} \|x_\nu - \tilde{x}'\|^2 = \lim_{\nu'} \|x_{\nu'} - \tilde{x}'\|^2$ and the same equality with $\tilde{x}'$, it follows $\|\tilde{x} - \tilde{x}'\|^2 = 0$ (this is Opial's Theorem [15]). Before proving Theorem 3, let us establish the following estimate.

**Lemma 2.** For all $j \ge 1$, let us define

$$ \beta_{j,k} = \prod_{l=j}^{k} \alpha_l = \prod_{l=j}^{k} \frac{l-1}{l+a}, $$

for all $k \ge j$, and $\beta_{j,k} = 1$ for $k < j$. (Observe that since $\alpha_1 = 0$, $\forall k > 1, \beta_{1,k} = 0$.) Then, we have for all $j$

$$ \sum_{k=j}^{+\infty} \beta_{j,k} \le \frac{j+5}{2}. \qquad (19) $$

*Proof.* Since $a \ge 2$,

$$ \beta_{j,k} \le \prod_{l=j}^{k} \frac{l-1}{l+2}. $$

Hence, for all $j \ge 2$ and for all $k \ge 1$, $\beta_{j,k} \le 1$, while if $k - j \ge 2$,

$$ \beta_{j,k} \le \left( \frac{j+1}{k} \right)^3. $$
and invoking (20) it follows that

$$
\begin{align*}
\Phi_{n+1} - \Phi_n - \alpha_n (\Phi_n - \Phi_{n-1}) &\le -\delta_{n+1} + \frac{\gamma L}{2} \Gamma_n \\
&\quad + \alpha_n (\delta_n + \langle x_n - x_{n-1}, x_{n+1} - x_n \rangle) \\
&= -\Gamma_n + \frac{\gamma L}{2} \Gamma_n + (\alpha_n + \alpha_n^2) \delta_n,
\end{align*}
$$

where we have used the fact that

$$
\delta_{n+1} - \alpha_n \langle x_n - x_{n-1}, x_{n+1} - x_n \rangle = \alpha_n^2 \frac{\|x_n - x_{n-1}\|^2}{2} - \frac{\|x_{n+1} - y_n\|^2}{2}.
$$

Using $\frac{\alpha_n + \alpha_n^2}{2} \le \alpha_n$ we obtain

$$
\Phi_{n+1} - \Phi_n - \alpha_n (\Phi_n - \Phi_{n-1}) \le - \left(1 - \frac{\gamma L}{2}\right) \Gamma_n + 2\alpha_n \delta_n \quad (23)
$$

with $1 - \frac{\gamma L}{2} > 0$.

Now defining $\theta_n = \max(0, \Phi_n - \Phi_{n-1})$ we obtain

$$
\theta_{n+1} \le \alpha_n (\theta_n + 2\delta_n) \quad (24)
$$

Applying recursively (24) it follows that for all $n \ge 2$ ($\alpha_1 = 0$, and in particular $\theta_1, \theta_2 = 0$).

$$
\theta_{n+1} \le 2 \sum_{j=2}^{n} \left( \prod_{l=j}^{n} \alpha_l \right) \delta_j = 2 \sum_{j=2}^{n} \beta_{j,n} \delta_j. \quad (25)
$$

Hence (using (19)),

$$
\begin{align*}
\sum_{n=2}^{+\infty} \theta_n &\le 2 \sum_{n=1}^{+\infty} \sum_{j=2}^{n} \beta_{j,n} \delta_j \\
&\le 2 \sum_{j=2}^{\infty} \delta_j \sum_{n=j}^{\infty} \beta_{j,n} \\
&\le 2 \sum_{j=1}^{\infty} \delta_j \frac{j+5}{2}.
\end{align*}
$$

From Corollary 2 the right side of the last inequality is finite if $a > 2$,
therefore the sequence $(\theta_n)_{n \in \mathbb{N}}$ belongs to $\ell_1(\mathbb{N})$.

The end of the proof follows Lorenz and Pock [10]. We set $s_n = \Phi_n - \sum_{i=1}^n \theta_i$ and since $\Phi_n \ge 0$ and $\sum_{i=1}^n \theta_i$ is bounded independently of $n$, we see that $s_n$ is bounded from below. On the other hand

$$
s_{n+1} = \Phi_{n+1} - \theta_n - \sum_{i=1}^{n} \theta_n \le \Phi_{n+1} - \Phi_{n+1} + \Phi_n - \sum_{i=1}^{n} \theta_i = s_n
$$

and hence $(s_n)_{n \in \mathbb{N}}$ is a non-decreasing sequence and thus is convergent. This
implies that $\Phi_n$ is convergent, which concludes the proof of Theorem 3. $\square$
It follows that for all $j \ge 2$,

$$ \begin{aligned} \sum_{k=j}^{+\infty} \beta_{j,k} &\le 2 + \sum_{k=j+2}^{+\infty} \beta_{j,k} \le 2 + \sum_{k=j+2}^{+\infty} \left(\frac{j+1}{k}\right)^3 \le 2 + (j+1)^3 \sum_{k=j+2}^{+\infty} \frac{1}{k^3} \\ &\le 2 + (j+1)^3 \int_{t=j+1}^{+\infty} \frac{dt}{t^3} \le 2 + (j+1)^3 \frac{1}{2(j+1)^2}. \end{aligned} $$

Estimate (19) follows. □

Proof of Theorem 3. Let us define

$$ \Phi_n = \frac{1}{2} \|x_n - x^*\|_2^2 \quad \text{and} \quad \Gamma_n = \frac{1}{2} \|x_{n+1} - y_n\|_2^2 $$

From the identity

$$ \langle a-b, a-c \rangle = \frac{1}{2} \|a-b\|_2^2 + \frac{1}{2} \|a-c\|_2^2 - \frac{1}{2} \|b-c\|_2^2 \quad (20) $$

we have by using the definition of $y_n$

$$ \Phi_n - \Phi_{n+1} = \delta_{n+1} + \langle y_n - x_{n+1}, x_{n+1} - x^* \rangle - \alpha_n \langle x_n - x_{n-1}, x_{n+1} - x^* \rangle \quad (21) $$

Then, using the monoticity of $\partial g$, we deduce that for any $z_{n+1} \in \partial g(x_{n+1})$ and for any $z^* \in \partial g(x^*)$

$$ \langle \gamma z_{n+1} - \gamma z^*, x_{n+1} - x^* \rangle \ge 0 $$

By definition of $x^*$, $-\nabla(f(x^*)) \in \partial g(x^*)$ and $y_n - x_{n+1} - \gamma \nabla f(y_n) \in \gamma \partial g(x_{n+1})$.

It follows

$$ \begin{aligned} \langle y_n - x_{n+1} - \gamma \nabla f(y_n) + \gamma \nabla f(x^*), x_{n+1} - x^* \rangle &\ge 0 \\ \langle y_n - x_{n+1}, x_{n+1} - x^* \rangle + \gamma \langle \nabla f(x^*) - \nabla f(y_n), x_{n+1} - x^* \rangle &\ge 0 \end{aligned} $$

Combining with (21) we obtain

$$ \Phi_n - \Phi_{n+1} \ge \delta_{n+1} + \gamma \langle \nabla f(y_n) - \nabla f(x^*), x_{n+1} - x^* \rangle - \alpha_n \langle x_n - x_{n-1}, x_{n+1} - x^* \rangle. \quad (22) $$

From the co-coercivity of $\nabla f$, we have

$$ \begin{aligned} \langle \nabla f(y_n) - \nabla f(x^*), x_{n+1} - x^* \rangle &= \langle \nabla f(y_n) - \nabla f(x^*), x_{n+1} - y_n + y_n - x^* \rangle \\ &\ge \frac{1}{L} \| \nabla f(y_n) - \nabla f(x^*) \|_2^2 + \langle \nabla f(y_n) - \nabla f(x^*), x_{n+1} - y_n \rangle \\ &\ge \frac{1}{L} \| \nabla f(y_n) - \nabla f(x^*) \|_2^2 - \frac{1}{L} \| \nabla f(y_n) - \nabla f(x^*) \|_2^2 - \frac{L}{2} \Gamma_n \\ &\ge -\frac{L}{2} \Gamma_n. \end{aligned} $$
# 4 Numerical Experiments

In the previous parts, it was shown that non classical choices of the sequence $(t_n)_{n \in \mathbb{N}}$ ensure weak convergence of iterates $(x_n)_{n \in \mathbb{N}}$ and good properties for the sequence $(F(x_n)-F(x^*))_{n \in \mathbb{N}}$. On three examples, inpainting, deblurring and denoising, we compare several choices of parameters.

For each example the 4 following sequences are tested :

* $t_1 = 1$ and $\forall n \in \mathbb{N}$, $t_{n+1} = \sqrt{t_n^2 + \frac{1}{4}} + \frac{1}{2}$,

* $t_n = \frac{n+a+1}{a}$, $\forall n \in \mathbb{N}$ with $a = 2, 3$ and $4$.

For each problem, at each iteration $n$, the values $\|x_n - x_{n-1}\|_2^2$ and $F(x^n) - F(x^*)$ are computed. Since $F(x^*)$ can not be exactly computed, the value $F(x^*)$ is estimated by the the minimum of the values computed on 2000 iterations for the four methods. The graph of the logarithm of these two quantities is thus given from $n = 1$ to $n = 1800$.

**Inpainting** Let us consider here a degraded image $y^0 = Mx^0$ where $x^0$ is an unknown source image and $M$ a mask operator. In our example 50% of the pixels are removed. We estimate the image $x^0$ from $y^0$ by minimizing

$$F(x) = \frac{1}{2} \|y^0 - Mx\|_2^2 + \lambda \|Tx\|_1 \quad (26)$$

where $\lambda$ is a small positive parameter and $T$ an orthogonal (Daubechies) wavelet transform.

Considering $f(x) = \frac{1}{2} \|y^0 - Mx\|_2^2$ and $g(x) = \lambda \|Tx\|_1$, FISTA may be applied to minimize $F$.

<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /><figcaption>Left: the masked image $y^0$. Right: an image $\hat{x}$ estimated minimizing $F$ with FISTA.<fnref n="2" /></figcaption></figure>

<footnote n="2">²The images provided by the 4 versions of FISTA look very similar, the difference appears in the values of the variation of functional $F$ through the iterations.</footnote>
Substituting back into (22), we get

$$ \Phi_n - \Phi_{n+1} \ge \delta_{n+1} - \frac{\gamma L}{2} \Gamma_n - \alpha_n \langle x_n - x_{n-1}, x_{n+1} - x^* \rangle, $$

and invoking (20) it follows that

$$ \begin{aligned} \Phi_{n+1} - \Phi_n - \alpha_n(\Phi_n - \Phi_{n-1}) &\le -\delta_{n+1} + \frac{\gamma L}{2}\Gamma_n \\ &\quad + \alpha_n(\delta_n + \langle x_n - x_{n-1}, x_{n+1} - x_n \rangle) \\ &= -\Gamma_n + \frac{\gamma L}{2}\Gamma_n + (\alpha_n + \alpha_n^2)\delta_n, \end{aligned} $$

where we have used the fact that

$$ \delta_{n+1} - \alpha_n \langle x_n - x_{n-1}, x_{n+1} - x_n \rangle = \alpha_n^2 \frac{\|x_n - x_{n-1}\|^2}{2} - \frac{\|x_{n+1} - y_n\|^2}{2}. $$

Using $\frac{\alpha_n + \alpha_n^2}{2} \le \alpha_n$ we obtain

$$ \Phi_{n+1} - \Phi_n - \alpha_n(\Phi_n - \Phi_{n-1}) \le -\left(1 - \frac{\gamma L}{2}\right) \Gamma_n + 2\alpha_n \delta_n \quad (23) $$

with $1 - \frac{\gamma L}{2} > 0$.

Now defining $\theta_n = \max(0, \Phi_n - \Phi_{n-1})$ we obtain

$$ \theta_{n+1} \le \alpha_n (\theta_n + 2\delta_n) \quad (24) $$

Applying recursively (24) it follows that for all $n \ge 2$ ($\alpha_1 = 0$, and in particular $\theta_1, \theta_2 = 0$).

$$ \theta_{n+1} \le 2 \sum_{j=2}^{n} \left( \prod_{l=j}^{n} \alpha_l \right) \delta_j = 2 \sum_{j=2}^{n} \beta_{j,n} \delta_j. \quad (25) $$

Hence (using (19)),

$$ \begin{aligned} \sum_{n=2}^{+\infty} \theta_n &\le 2 \sum_{n=1}^{+\infty} \sum_{j=2}^{n} \beta_{j,n} \delta_j \\ &\le 2 \sum_{j=2}^{\infty} \delta_j \sum_{n=j}^{\infty} \beta_{j,n} \\ &\le 2 \sum_{j=1}^{\infty} \delta_j \frac{j+5}{2}. \end{aligned} $$

From Corollary 2 the right side of the last inequality is finite if $a > 2$, therefore the sequence $(\theta_n)_{n \in \mathbb{N}}$ belongs to $\ell_1(\mathbb{N})$.
<figure><img src="image_3.png" /><figcaption>Left: values of $\log(F(x_n) - F(x^*))$. Right: values of $\log(\|x_n - x_{n-1}\|_2^2)$. Blue dot line classical FISTA, red dashed-dot line $a = 2$, black solid line $a = 3$ and magenta dashed line $a = 4$.</figcaption></figure>

On this example, the choices $a = 3$ or $a = 4$ seems better than classical choices after 100 iterations. One can notice that classical FISTA is better for a small number of iterations.

**Deblurring** In this second example $y^0 = h \star x^0 + n$ is the noisy image of a blurred images $x^0$, where $h$ is a gaussian filter and $n$ is a random gaussian noise. The image $x^0$ can be estimated minimizing

$$F(x) = \frac{1}{2} \|y^0 - h \star x\|_2^2 + \lambda \|Tx\|_1 \quad (27)$$

where $\lambda$ is a small positive real number whose value depends on the noise level and $T$ is an orthogonal (Daubechies) wavelet transform.

Considering $f(x) = \frac{1}{2} \|y^0 - h \star x\|_2^2$ and $g(x) = \lambda \|Tx\|_1$, FISTA may be applied to minimize $F$.

<figure><img src="image_4.png" /><figcaption>Left: the blurred image $y^0$. Right: an image $\hat{x}$ estimated minimizing $F$ with FISTA.</figcaption></figure>
The end of the proof follows Lorenz and Pock [9]. We set $s_n = \Phi_n - \sum_{i=1}^n \theta_i$ and since $\Phi_n \ge 0$ and $\sum_{i=1}^n \theta_i$ is bounded independently of $n$, we see that $s_n$ is bounded from below. On the other hand

$$s_{n+1} = \Phi_{n+1} - \theta_n - \sum_{i=1}^{n} \theta_i \le \Phi_{n+1} - \Phi_{n+1} + \Phi_n - \sum_{i=1}^{n} \theta_i = s_n$$

and hence $(s_n)_{n \in \mathbb{N}}$ is a non-decreasing sequence and thus is convergent. This implies that $\Phi_n$ is convergent, which concludes the proof of Theorem 3. $\square$

# 4 Numerical Experiments

In the previous parts, it was shown that non classical choices of the sequence $(t_n)_{n \in \mathbb{N}}$ ensure weak convergence of iterates $(x_n)_{n \in \mathbb{N}}$ and good properties for the sequence $(F(x_n)-F(x^*))_{n \in \mathbb{N}}$. On three examples, inpainting, deblurring and denoising, we compare several choices of parameters.

For each example the 4 following sequences are tested :

* $t_1 = 1$ and $\forall n \in \mathbb{N}$, $t_{n+1} = \sqrt{t_n^2 + \frac{1}{4} + \frac{1}{2}}$,

* $t_n = \frac{n+a+1}{a}$, $\forall n \in \mathbb{N}$ with $a = 2, 3$ and $4$.

For each problem, at each iteration $n$, the values $\|x_n - x_{n-1}\|_2^2$ and $F(x^n) - F(x^*)$ are computed. Since $F(x^*)$ can not be exactly computed, the value $F(x^*)$ is estimated by the minimum of the values computed on 2000 iterations for the four methods. The plot of these two quantities is thus given from $n = 1$ to $n = 1800$.

**Inpainting** Let us consider here a degraded image $y^0 = Mx^0$ where $x^0$ is an unknown source image and $M$ a mask operator. In our example 50% of the pixels are removed. We estimate the image $x^0$ from $y^0$ by minimizing

$$F(x) = \frac{1}{2} \|y^0 - Mx\|_2^2 + \lambda \|Tx\|_1 \quad (26)$$

where $\lambda$ is a small positive parameter and $T$ an orthogonal (Daubechies) wavelet transform.

Considering $f(x) = \frac{1}{2} \|y^0 - Mx\|_2^2$ and $g(x) = \lambda \|Tx\|_1$, FISTA may be applied to minimize $F$.
<figure><img src="image_5.png" /><figcaption>Left: values of $\log(F(x_n) - F(x^*))$. Right: values of $\log(\|x_n - x_{n-1}\|_2^2)$. Blue dot line classical FISTA, red dashed-dot line $a = 2$, black solid line $a = 3$ and magenta dashed line $a = 4$.</figcaption></figure>

On this example, the choices of the classical FISTA seems better after 200 iterations, but the decreasing of $\delta_n$ seems still better for $a = 3$ and $a = 4$.

**TV denoising** Let us consider now a noisy image $y^0 = x^0 + n$. The image $x^0$ may be estimated from $y^0$ minimizing

$$F(x) = \frac{1}{2} \|y^0 - x\|_2^2 + \lambda \|\nabla x\|_1 \quad (28)$$

where $\nabla x$ is the gradient of the image $x$ and $\|\nabla x\|_1$ is the isotropic $\ell_1$-norm of the gradient. This regularization is also called Total Variation (TV) regularization. The proximal map of the function $x \mapsto \|\nabla x\|_1$ does not have a close form and FISTA is difficult to use directly here. Nevertheless, by duality, this minimization problem is equivalent to minimize

$$G(p) = \frac{1}{2} \|y^0 + \text{div } p\|_2^2 + i_{\|\cdot\|_{\infty} \le \lambda}(p) \quad (29)$$

where $i_C$ denotes the function such that $i_C(x) = 0$ if $x \in C$ and $i_C(x) = +\infty$ if $x \notin C$ and where $x \mapsto -\text{div } x$ is the divergence operator, conjugate of the gradient $\nabla$.

These two problems are equivalent and for any solution $p^*$ of the second minimization problem, $y^0 + \text{div } p^*$ is a solution of the first minimization problem.

This second problem can be solved using FISTA since the gradient of $p \mapsto \frac{1}{2} \|y + \text{div } p\|_2^2$ is Lipschitz and the proximal map of $p \mapsto i_{\|\cdot\|_{+\infty} \le \lambda}(p)$ is a simple projection.
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /><figcaption>Left: the masked image $y^0$. Right: an image $\hat{x}$ estimated minimizing $F$ with FISTA.<fnref n="2" /></figcaption></figure>

<figure><img src="image_4.png" /><figcaption>Left: values of $F(x_n) - F(x^*)$. Right: values of $\|x_n - x_{n-1}\|_2^2$. Blue dot line classical FISTA, red dashed-dot line $a = 2$, black solid line $a = 3$ and magenta dashed line $a = 4$.</figcaption></figure>

On this example, the choices $a = 3$ or $a = 4$ seems better than classical choices after 100 iterations. One can notice that classical FISTA is better for a small number of iterations.

**Deblurring** In this second example $y^0 = h \star x^0 + n$ is the noisy image of a blurred images $x^0$, where $h$ is a gaussian filter and $n$ is a random gaussian noise. The image $x^0$ can be estimated minimizing

$$F(x) = \frac{1}{2} \|y^0 - h \star x\|_2^2 + \lambda \|Tx\|_1 \quad (27)$$

where $\lambda$ is a small positive real number whose value depends on the noise level and $T$ is an orthogonal (Daubechies) wavelet transform.

Considering $f(x) = \frac{1}{2} \|y^0 - h \star x\|_2^2$ and $g(x) = \lambda \|Tx\|_1$, FISTA may be applied to minimize $F$.

<footnote n="2">²The images provided by the 4 versions of FISTA look very similar, the difference appears in the values of the variation of functional $F$ through the iterations.</footnote>
<figure><img src="image_6.png" /><figcaption>Left: noisy image $y^0$. Right: the image $\hat{x}$ estimated minimizing $F$ with FISTA.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Left: values of $\log(G(p_n) - G(p^*))$. Right: values of $\log(\|p_n - p_{n-1}\|_2^2)$. Blue dot line classical FISTA, red dashed-dot line $a = 2$, black solid line $a = 3$ and magenta dashed line $a = 4$.</figcaption></figure>

On this example, the different choices of parameters seem to be equivalent.

These three examples shows that choosing a priori a sequence $(t_n)_{n \in \mathbb{N}}$ for FISTA is difficult and that for a given problem, it would be useful to test various options. Sometimes the classical parameters proposed by Beck and Teboulle are better to get a faster minimization, sometimes the use of $a = 3$ or $a = 4$ is better. But on the three examples the norm of the variation $\delta_n$ is smaller for $a = 3$ or $a = 4$ than $a = 2$ or the classical FISTA, which may indicate that the convergence of the iterates is faster.

## Acknowledgements

A. Chambolle is partially supported by the joint ANR/FWF Project "Efficient Algorithms for Nonsmooth Optimization in Imaging" (EANOI) FWF n. I1148 / ANR-12-IS01-0003.

This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the
<figure><img src="image_5.png" /><figcaption>Left: the blurred image $y^0$. Right: an image $\hat{x}$ estimated minimizing $F$ with FISTA.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Left: values of $F(x_n) - F(x^*)$. Right: values of $\|x_n - x_{n-1}\|_2^2$. Blue dot line classical FISTA, red dashed-dot line $a = 2$, black solid line $a = 3$ and magenta dashed line $a = 4$.</figcaption></figure>

On this example, the choices of the classical FISTA seems better after 200 iterations, but the decreasing of $\delta_n$ seems still better for $a = 3$ and $a = 4$.

**TV denoising** Let us consider now a noisy image $y^0 = x^0 + n$. The image $x^0$ may be estimated from $y^0$ minimizing

$$F(x) = \frac{1}{2} \|y^0 - x\|_2^2 + \lambda \|\nabla x\|_1 \quad (28)$$

where $\nabla x$ is the gradient of the image $x$ and $\|\nabla x\|_1$ is the isotropic $\ell_1$-norm of the gradient. This regularization is also called Total Variation (TV) regularization. The proximal map of the function $x \mapsto \|\nabla x\|_1$ does not have a close form and FISTA is difficult to use directly here. Nevertheless, by duality, this minimization problem is equivalent to minimize

$$G(p) = \frac{1}{2} \|y^0 + \text{div } p\|_2^2 + i_{\|\cdot\|_{\infty} \le \lambda}(p) \quad (29)$$

where $i_C$ denotes the function such that $i_C(x) = 0$ if $x \in C$ and $i_C(x) = +\infty$ if $x \notin C$ and where $x \mapsto -\text{div } x$ is the divergence operator, conjugate of
frame of the Investments for the future Programme IdEx Bordeaux (ANR-10-IDEX-03-02).

## References

[1] Felipe Alvarez and Hedy Attouch. An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. *Set-Valued Anal.*, 9(1-2):3–11, 2001. Wellposedness in optimization and related topics (Gargnano, 1999).

[2] M. Oliny A.Moudafi. Convergence of a splitting inertial proximal method for monotone operators. *Journal of Computational and Applied Mathematics*, 155(2):447–454, 2003.

[3] Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. *SIAM J. Imaging Sci.*, 2(1):183–202, 2009.

[4] Patrick L. Combettes and Jean-Christophe Pesquet. Proximal splitting methods in signal processing. In *Fixed-point algorithms for inverse problems in science and engineering*, volume 49 of Springer Optim. Appl., pages 185–212. Springer, New York, 2011.

[5] Patrick L. Combettes and Valérie R. Wajs. Signal recovery by proximal forward-backward splitting. *Multiscale Model. Simul.*, 4(4):1168–1200, 2005.

[6] Jonathan Eckstein and Dimitri P. Bertsekas. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. *Math. Programming*, 55(3, Ser. A):293–318, 1992.

[7] Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. *Computers & Mathematics with Applications*, 2(1):17–40, 1976.

[8] Osman Güler. New proximal point algorithms for convex minimization. *SIAM J. Optim.*, 2(4):649–664, 1992.

[9] P.-L. Lions and B. Mercier. Splitting algorithms for the sum of two nonlinear operators. *SIAM J. Numer. Anal.*, 16(6):964–979, 1979.

[10] Dirk A. Lorenz and Thomas Pock. An accelerated forward-backward algorithm for monotone inclusions. *CoRR*, abs/1403.3522, 2014.

[11] Arkadi. S. Nemirovski and David B. Yudin. *Problem complexity and method efficiency in optimization*. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson, Wiley-Interscience Series in Discrete Mathematics.
the gradient $\nabla$.

These two problems are equivalent and for any solution $p^*$ of the second minimization problem, $y^0 + \text{div } p^*$ is a solution of the first minimization problem.

This second problem can be solved using FISTA since the gradient of $p \mapsto \frac{1}{2} \|y + \text{div } p\|_2^2$ is Lipschitz and the proximal map of $p \mapsto i_{\|\cdot\|_{+\infty}\le\lambda}(p)$ is a simple projection.

<figure><img src="image_7.png" /><figcaption>Left: noisy image $y^0$. Right: the image $\hat{x}$ estimated minimizing $F$ with FISTA.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Left: values of $G(p_n) - G(p^*)$. Right: values of $\|p_n - p_{n-1}\|_2^2$.
Blue dot line classical FISTA, red dashed-dot line $a=2$, black solid line $a=3$ and magenta dashed line $a=4$.</figcaption></figure>

On this example, the different choices of parameters seem to be equivalent.

These three examples shows that choosing a priori a sequence $(t_n)_{n\in\mathbb{N}}$ for FISTA is difficult and that for a given problem, it would be useful to test various options. Sometimes the classical parameters proposed by Beck and Teboulle are better to get a faster minimization, sometimes the use of $a=3$ or $a=4$ is better. But on the three examples the norm of the variation $\delta_n$ is smaller for $a=3$ or $a=4$ than $a=2$ or the classical FISTA, which may indicate that the convergence of the iterates is faster.
[12] Yurii Nesterov. A method for solving the convex programming problem with convergence rate $O(1/k^2)$. Dokl. Akad. Nauk SSSR, 269(3):543-547, 1983.

[13] Yurii Nesterov. *Introductory lectures on convex optimization*, volume 87 of *Applied Optimization*. Kluwer Academic Publishers, Boston, MA, 2004. A basic course.

[14] Yurii Nesterov. Smooth minimization of non-smooth functions. *Math. Program.*, 103(1, Ser. A):127-152, 2005.

[15] Zdzisław Opial. Weak convergence of the sequence of successive approximations for nonexpansive mappings. *Bull. Amer. Math. Soc.*, 73:591-597, 1967.

[16] Paul Tseng. On accelerated proximal gradient methods for convex-concave optimization, 2008. Submitted to SIAM J. Optim.
# Acknowledgements

A. Chambolle is partially supported by the joint ANR/FWF Project "Efficient Algorithms for Nonsmooth Optimization in Imaging" (EANOI) FWF n. I1148 / ANR-12-IS01-0003.

This study has been carried out with financial support from the French State, managed by the French National Research Agency (ANR) in the frame of the Investments for the future Programme IdEx Bordeaux (ANR-10-IDEX-03-02). The authors would like to thank J. Fadili and T. Pock for helpful discussions.

# References

[1] Felipe Alvarez and Hedy Attouch. An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. *Set-Valued Anal.*, 9(1-2):3–11, 2001. Wellposedness in optimization and related topics (Gargnano, 1999).

[2] Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. *SIAM J. Imaging Sci.*, 2(1):183–202, 2009.

[3] Patrick L. Combettes and Jean-Christophe Pesquet. Proximal splitting methods in signal processing. In *Fixed-point algorithms for inverse problems in science and engineering*, volume 49 of Springer Optim. Appl., pages 185–212. Springer, New York, 2011.

[4] Patrick L. Combettes and Valérie R. Wajs. Signal recovery by proximal forward-backward splitting. *Multiscale Model. Simul.*, 4(4):1168–1200, 2005.

[5] Jonathan Eckstein and Dimitri P. Bertsekas. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. *Math. Programming*, 55(3, Ser. A):293–318, 1992.

[6] Daniel Gabay and Bertrand Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. *Computers & Mathematics with Applications*, 2(1):17–40, 1976.

[7] Osman Güler. New proximal point algorithms for convex minimization. *SIAM J. Optim.*, 2(4):649–664, 1992.

[8] Pierre-Louis Lions and Bertrand Mercier. Splitting algorithms for the sum of two nonlinear operators. *SIAM J. Numer. Anal.*, 16(6):964–979, 1979.

[9] Dirk A. Lorenz and Thomas Pock. An inertial forward-backward algorithm for monotone inclusions. *J. Math. Imaging Vision*, pages 1–15, 2014. (online).
[10] A. Moudafi and M. Oliny. Convergence of a splitting inertial proximal method for monotone operators. *J. Comput. Appl. Math.*, 155(2):447–454, 2003.

[11] Arkadi. S. Nemirovski and David B. Yudin. *Problem complexity and method efficiency in optimization*. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson, Wiley-Interscience Series in Discrete Mathematics.

[12] Yurii Nesterov. A method for solving the convex programming problem with convergence rate $O(1/k^2)$. *Dokl. Akad. Nauk SSSR*, 269(3):543–547, 1983.

[13] Yurii Nesterov. *Introductory lectures on convex optimization*, volume 87 of *Applied Optimization*. Kluwer Academic Publishers, Boston, MA, 2004. A basic course.

[14] Yurii Nesterov. Smooth minimization of non-smooth functions. *Math. Program.*, 103(1, Ser. A):127–152, 2005.

[15] Zdzisław Opial. Weak convergence of the sequence of successive approximations for nonexpansive mappings. *Bull. Amer. Math. Soc.*, 73:591–597, 1967.

[16] Paul Tseng. On accelerated proximal gradient methods for convex-concave optimization, 2008. Submitted to SIAM J. Optim.