Hedy Attouch
email: hedy.attouch@umontpellier.fr

Zaki Chbani
email: chbaniz@uca.ac.ma

Hassan Riahi
email: h-riahi@uca.ac.ma

CONVERGENCE RATE OF INERTIAL PROXIMAL ALGORITHMS WITH GENERAL EXTRAPOLATION AND PROXIMAL COEFFICIENTS

Keywords: Inertial proximal algorithms, general extrapolation coefficient, Lyapunov analysis, Nesterov accelerated gradient method, nonsmooth convex optimization, time rescaling AMS subject classification. 37N40, 46N10, 49M30, 65B99, 65K05, 65K10, 90B50, 90C25

In a Hilbert space setting, with the aim of developing rapid methods for nonsmooth convex optimization, we analyze the convergence rate of the inertial proximal algorithms. These algorithms involve both extrapolation coefficients (including Nesterov acceleration method) and proximal coefficients in a general form. They can be interpreted as the discrete time version of inertial continuous gradient systems with general damping and time scale coefficients. Based on the proper setting of these parameters, we show the fast convergence of values and the convergence of iterates. In doing so, we provide an overview of this class of algorithms. Our study complements the previous Attouch-Cabot paper (SIOPT, 2018) by introducing into the algorithm time scaling aspects, and sheds new light on the Güler seminal papers on the convergence rate of the accelerated proximal methods for convex optimization.

Introduction

Throughout the paper, H is a real Hilbert space endowed with the scalar product •, • and the corresponding norm • . The function Φ : H → R∪{+∞}, which is to minimize, is supposed to be convex lower semicontinuous and proper, and such that argmin H Φ = ∅. We will analyze the convergence properties of the Inertial Proximal algorithm [START_REF] Adly | Finite time stabilization of nonlinear oscillators subject to dry friction, Nonsmooth Mechanics and Analysis[END_REF] (IP) α k ,β k y k = x k + α k (x k -x k-1 )

x k+1 = prox β k Φ (y k ),
where the sequences (α k ) and (β k ) play the role of parameters. As a standing assumption, we assume that, for every k ≥ 1, α k is non-negative and β k is positive. For a judicious choice of α k and β k , we will obtain fast convergence of the values and convergence of the iterates. In doing so, we will extend previous studies to the case of inertial proximal methods with general coefficients, including large proximal steps β k . We recall that, for β > 0, the proximal mapping prox βΦ : H → H is defined by: for every x ∈ H,

prox βΦ (x) = argmin ξ∈H βΦ(ξ) + 1 2 x -ξ 2 .
One can consult [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert spaces[END_REF][START_REF] Parikh | Proximal algorithms[END_REF][START_REF] Peypouquet | Convex optimization in normed spaces: theory, methods and examples[END_REF][START_REF] Polyak | Introduction to optimization[END_REF], for a recent account on the proximal methods, that play a central role in nonsmooth optimization as a basic block of many splitting algorithms. Proximal methods have a close relationship with gradient-type continuous evolution systems, from which they can be derived by implicit discretization. As such, their retain their convergence properties (see [START_REF] Peypouquet | Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time[END_REF] for first-order evolution systems). Precisely, to guide our study, when Φ is continuously differentiable, we will use the link between the (IP) α k ,β k proximal algorithm and the continuous second-order evolution equation (IGS) γ,β ẍ(t) + γ(t) ẋ(t) + β(t)∇Φ(x(t)) = 0.

In (IGS) γ,β , γ(t) is a positive damping coefficient, and β(t) is a time scale coefficient. The inertial proximal algorithm (IP) α k ,β k can be interpreted as an implicit discretization of (IGS) γ,β , which gives the following dynamic interpretation of the parameters (α k ) and (β k ):

• The sequence (α k ) of non-negative extrapolation coefficients captures the inertial effect. The property α k → 1, which plays a central role in the Nesterov acceleration method, is associated with the vanishing damping property γ(t) → 0, as t → +∞.

Date: February 14, 2019.

• The sequence (β k ) of positive proximal coefficients takes into account the temporal scale effects. The coefficient β k in (IP) α k ,β k is the discrete temporal version of β(t). The fast time parametrization of the orbits (respectively iterates) results from the property β(t) → +∞ as t → +∞ (respectively β k → +∞ as k → +∞). It plays a key role in obtaining fast optimization properties.

1.1. Presentation of the results. Historical aspects. Recall two important instances of (IP) α k ,β k already studied, and which constitute special cases of our study:

1. The case β k ≡ β > 0 where the proximal parameter is fixed, and α k is general, is written as follows

(2) (IP) α k ,β y k = x k + α k (x k -x k-1 )
x k+1 = prox βΦ (y k ).

It was analyzed by Attouch-Cabot [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], then by Attouch-Cabot-Chbani-Riahi [START_REF] Attouch | Accelerated forward-backward algorithms with perturbations. Application to Tikhonov regularization[END_REF] in the presence of perturbations, errors. The following result gives the convergence rate of values in this case. It is expressed with the help of the sequence (t k ) that is related to (α k ) by the formula t k := 1 + +∞ i=k i j=k α j . The inverse mapping takes the simpler form α k = t k -1 t k+1 .

Theorem 1.1 (Attouch-Cabot [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF]). Suppose that the sequence (α k ) satisfies the following properties (K 0 ) and (K 1 ).

(K 0 ) ∀k ≥ 1, +∞ i=k i j=k α j < +∞, (K 1 ) ∀k ≥ 1, t 2 k+1 -t 2 k ≤ t k+1 . Then, for any sequence (x k ) generated by the algorithm (IP)

α k ,β Φ(x k ) -min H Φ = O 1 t 2 k as k → +∞.
This result comes as a result of a rich history. In a seminal paper [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate O(1/k2)[END_REF], Nesterov proposed the extrapolation

coefficient α k = t k -1 t k+1
with t 1 = 1 and

t k+1 = √ 4t 2 k +1+1 2
. This choice corresponds to taking equality in (K 1 ), and leads to an increasing sequence (α k ) which behaves like 1 -3 k as k → +∞. Then t k is of order k, and the corresponding convergence rate for values is O( 1 k 2 ). This result has been extended by Beck-Teboulle to structured convex minimization problems in [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF], that's the FISTA inertial proximal-gradient algorithm. Since the introduction of Nesterov's scheme, much progress has been made in the development of first-order accelerated methods, to name a few [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert spaces[END_REF][START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF][START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm[END_REF][START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF][START_REF] Kim | Optimized first-order methods for smooth convex minimization[END_REF][START_REF] Liang | Local linear convergence of forward-backward under partial smoothness[END_REF][START_REF] Lorenz | An inertial forward-backward algorithm for monotone inclusions[END_REF][START_REF] Parikh | Proximal algorithms[END_REF][START_REF] Polyak | Introduction to optimization[END_REF][START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF][START_REF] Villa | Accelerated and inexact forward-backward[END_REF]. Recently, a special attention has been devoted to the case α k = 1 -α k , where α > 0 (or an equivalent expression), see [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF][START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k 2[END_REF][START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm[END_REF][START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF]. Given x 0 , x 1 ∈ H, for k ≥ 1 the algorithm writes (3)

y k = x k + 1 -α k (x k -x k-1 ) x k+1 = prox βΦ (y k ) .
For α = 3 we recover a first-order approximation of the original choice of Nesterov. The great novelty of the algorithm (3) is that, while keeping the same computational complexity as in the case α = 3, taking α > 3 offers many advantages. First, it ensures the convergence of the sequences (x k ), as proved by Chambolle-Dossal [START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm[END_REF], see [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF] for complementary results. Let us recall that the convergence of the sequences generated by FISTA has not been established so far. This is a puzzling question in the study of numerical optimization methods. Second, as proved by Attouch-Peypouquet in [START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k 2[END_REF], it provides the better convergence rate of values

Φ(x k ) -min H Φ = o 1 k 2 as k → +∞.
When taking α k = 1 -α k , α = 3 appears as a critical value. The subcritical case α < 3 has been recently considered by Apidopoulos-Aujol-Dossal [START_REF] Apidopoulos | Convergence rate of inertial Forward-Backward algorithm beyond Nesterov's rule[END_REF] and Attouch-Chbani-Riahi [START_REF] Attouch | Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3[END_REF] with the convergence rate of values

O 1 k 2α 3
. Theorem 1.1 allows to cover all these situations (except the subcritical case), and many others including the case α k = 1 -c k r with 0 ≤ r ≤ 1. 2. The case β k general, and

α k = 1 -α k , is written as follows (4) (IP) α,β k y k = x k + 1 -α k (x k -x k-1 ) x k+1 = prox β k Φ (y k ).
The following result gives the convergence rate of values for the algorithm (4). It was obtained by the authors in [7, Theorem 7.1].

Theorem 1.2 (Attouch-Chbani-Riahi [START_REF] Attouch | Fast proximal methods via time scaling of damped inertial dynamics[END_REF]). Take α ≥ 1. Suppose that the sequence (β k ) satisfies the growth condition: there exists k 1 ∈ N such that for all k ≥ k 1

(H β ) β k+1 ≤ k 2 (k + 1)(k + 2 -α) β k .
Then, for any sequence (x k ) generated by the algorithm (IP) α,β k , we have

Φ(x k ) -min H Φ = O 1 k 2 β k as k → +∞.
In this result, the introduction of the scaling factor β k permits to pass from the convergence rate

O 1 k 2 to O 1 k 2 β k . When taking β k = k δ , condition (H β ) is satisfied for δ < α -3.
In this case, for a given δ > 0, by taking α large enough, namely α > 3 + δ, we can improve the convergence rate of values from

O 1 k 2 to O 1
k 2+δ This is a clear acceleration effect. In Theorem 2.3 we will prove the following result, which includes the two studies above (it is formulated below in a condensed form).

Theorem 1.3. Suppose that the sequence (α k ) satisfies (K 0 ). Let (t k ) be the sequence defined by α k = t k -1 t k+1 . Suppose that the sequences (α k ) and (β k ) satisfy jointly

(K 1,α k ,β k ) t 2 k+1 β k -t 2 k β k-1 -t k+1 β k ≤ 0 for every k ≥ 1. Let (x k ) be a sequence generated by algorithm (IP) α k ,β k . Then, Φ(x k ) -min H Φ = O 1 t 2 k β k-1 as k → +∞.
This result permits to better understand the joint tuning of the extrapolation parameter α k and the scaling parameter β k in (IP) α k ,β k which provides fast convergence of the values. Our study includes Güler's accelerated proximal algorithm, and provides new insight on this result. In Güler's algorithm, the damping coefficient is written α k = g k 1 g k-1 -1 , which allows to formulate the condition (K 1,α k ,β k ) in a simpler form, directly on the data. Based on this appraoch, and considering various temporal discretizations, our dynamic approach with general damping and scaling coefficients provides a family of inertial proximal algorithms with fast convergence properties.

1.2. Link with inertial gradient systems and time scaling.

1.2.1. Link with inertial gradient systems. First verify that the inertial proximal algorithm (IP) α k ,β k can be interpreted as a discretized version in time of the damped inertial dynamic

(IGS) γ,β ẍ(t) + γ(t) ẋ(t) + β(t)∇Φ(x(t)) = 0.
Take a fixed time step h > 0, and set τ k = kh, x k = x(τ k ). Implicit discretization of (IGS) γ,β with centered second-order variation, gives

(5) 1 h 2 (x k+1 -2x k + x k-1 ) + γ(kh) h (x k -x k-1 ) + β(kh)∇Φ(x k+1 ) = 0. Hence, x k+1 + h 2 β(kh)∇Φ(x k+1 ) = x k + (1 -hγ(kh)) (x k -x k-1 ), which gives the algorithm (IP) α k ,β k y k = x k + (1 -hγ(kh)) (x k -x k-1 ) x k+1 = prox h 2 β(kh)Φ (y k ),
with extrapolation coefficient α k = 1 -hγ(kh), and prox. parameter h 2 β(kh).

1.2.2. From Polyak heavy ball to vanishing damping. Take β(•) ≡ 1 and discuss the role of the time-dependent parameter γ(t) in the continuous dynamic (IGS) γ,1 . In the context of mechanics, γ(t) is a viscous friction coefficient. Taking γ(t) positive causes the dissipation of the global energy of the system. This plays a central role in its stabilization and optimization properties. The introduction of inertial dynamics (second-order in time) in optimization comes with B. Polyak [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] who, in 1964, introduced the so-called heavy ball with friction method, which corresponds to a constant friction coefficient γ(t) ≡ γ 0 > 0 in (IGS) γ,1 . It turns out that in this model, the friction is important and neutralizes the inertial effect, which prevents obtaining fast optimization methods. Indeed, taking the damping parameter γ(t) which tends to zero as t → +∞ (vanishing damping) is a key property for obtaining fast optimization methods. A decisive step in this direction was obtained by Su, Boyd, and Candès [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF], who showed that the Nesterov acceleration method can be obtained as a discretization of the dynamical system (IGS) γ,1 with γ(t) = 3 t . Recently, Attouch-Chbani-Peypouquet-Redont [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF] and May [START_REF] May | Asymptotic for a second-order evolution equation with convex potential and vanishing damping term[END_REF] showed convergence of the trajectories of the (IGS) γ system with γ(t) = α t and α > 3

(6) (AVD) α ẍ(t) + α t ẋ(t) + ∇Φ(x(t)) = 0.
They also obtained the improved convergence rate Φ(x(t)) -min H Φ = o( 1 t 2 ) as t → +∞. On the basis of the correspondence α k = 1 -hγ k (where h is the discrete time step, and γ k = γ(kh)), the discrete version of the vanishing damping property is that the sequence (α k ) tends to one from below as k → +∞. This makes the link with the historical aspects and the recent developments based on Nesterov acceleration method described in the previous section. For recent developments concerning the rich relations between inertial gradient systems with time-dependent friction and the inertial proximal-based algorithms, one can consult [START_REF] Álvarez | A second-order gradient-like dissipative dynamical system with Hessiandriven damping. Application to optimization and mechanics[END_REF], [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], [START_REF] Attouch | Fast proximal methods via time scaling of damped inertial dynamics[END_REF], [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF], [START_REF] Aujol | Optimal rate of convergence of an ODE associated to the Fast Gradient Descent schemes for b > 0[END_REF], [START_REF] Bot | A second order dynamical approach with variable damping to nonconvex smooth minimization[END_REF], [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF], [START_REF] Shi | Understanding the acceleration phenomenon via high-resolution differential equations[END_REF].

1.2.3. Link with time scaling. The time-dependent parameter β(t) comes from the time scaling of the dynamic. Let's illustrate it in the following model situation. Start from the (AVD) α system with γ(t) = α t and α ≥ 3. Given a trajectory x(•) of (AVD) α , we know that (see [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF], [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF], [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF]) [START_REF] Attouch | Fast proximal methods via time scaling of damped inertial dynamics[END_REF] Φ(x(t)) -min

H Φ = O 1 t 2 .
Let's make the following change of time variable in (AVD) α : t = s p , where p is a positive parameter. Set y(s) := x(s p ). By the derivation chain rule, we have For p > 1, we have α p > α, so the damping parameters for (8) are similar to those of (AVD) α . The only major difference is the coefficient s 2(p-1) in front of ∇Φ(y(s)), which explodes when s → +∞. From [START_REF] Attouch | Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3[END_REF] we observe that the convergence rate of values can be made arbitrarily fast (in the scale of powers of 1 s ) with p large. The physical intuition is clear. Fast optimization is associated with the fast parameterization of the trajectories of the (AVD) α system. Our goal is to transpose these results to the discrete case, taking advantage of the fact that proximal algorithms usually inherit the properties of the continuous dynamics from which they come. 1.2.4. Geometrical damping. The optimization properties of the continuous dynamic (IGS) γ,β come from its viscous damping term, which makes the system stabilize asymptotically. According to this mechanical and control point of view, it is natural to consider other types of damping. An important case is the damping driven by the Hessian which contains a rich geometric information, as considered in [START_REF] Álvarez | A second-order gradient-like dissipative dynamical system with Hessiandriven damping. Application to optimization and mechanics[END_REF], [START_REF] Attouch | A second-order differential system with Hessian-driven damping; Application to non-elastic shock laws[END_REF], [START_REF] Attouch | Fast convex minimization via inertial dynamics with Hessian driven damping[END_REF]. The temporal discretization of this dynamic gives the Ravine method initially introduced by Gelfand, Tsetlin 1961, then developed by B. Polyak. The exact link was obtained in [START_REF] Shi | Understanding the acceleration phenomenon via high-resolution differential equations[END_REF] using high-resolution. Another interesting damping is the dry friction, taken account in an optimization framework in [START_REF] Adly | Finite time stabilization of nonlinear oscillators subject to dry friction, Nonsmooth Mechanics and Analysis[END_REF], and which gives finite time stabilization. Developing our Lyapunov analysis in these situations is an interesting subject for further studies. 1.3. Organization of the paper. Based on Lyapunov analysis, our main convergence result is established in Section 2. Depending on the behavior of the sequences (α k ) and (β k ), we give the convergence rate of the values of the sequences (x k ) generated by algorithm (IP) α k ,β k . In Section 3, we analyze the convergence rate of the velocities. In Section 4, we show how to pass from O to o estimates. In Section 5, we give general conditions on the sequences (α k ) and (β k ) which guarantee the weak convergence of the iterates. In Section 6, we study the link with the accelerated proximal algorithm of Güler. In Section 7 we study a parametrized family of rescaled proximal algorithms which extends the previous study. In Section 8, we study the stability with respect to perturbations. The paper is completed by some auxiliary technical lemmas contained in the Appendix.

Convergence rate of the values

The algorithm (IP)

α k ,β k (10) (IP) α k ,β k y k = x k + α k (x k -x k-1 ) x k+1 = prox β k Φ (y k ),
can be equivalently formulated as

(11) x k+1 -2x k + x k-1 + (1 -α k )(x k -x k-1 ) + β k ∂Φ(x k+1 ) 0.
This formulation can also be obtained from the implicit discretization of the inertial dynamic (IGS) γ,β , see [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF]. Following [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF]

t k = +∞ i=k-1 i j=k α j .
If the series defining t k+1 is convergent, the series defining t k is also convergent, and we have

1 + α k t k+1 = 1 + α k   +∞ i=k i j=k+1 α j   = 1 + +∞ i=k i j=k α j = t k .
Conversely, if α k = 0 and if t k is well-defined, then the series defining t k+1 is convergent and the above equalities hold true. From now on, we assume that

(K 0 ) +∞ i=k i j=k α j < +∞ for every k ≥ 1.
Let us summarize the above results.

Lemma 2.1. Assume that the non-negative sequence (α k ) satisfies (K 0 ). Then the sequence (t k ) is well defined and satisfies for every k ≥ 1

(13) 1 + α k t k+1 = t k .
The sequence (t k ) allows us to formulate the conditions on the sequence (α k ) in a dense form. Although the direct formulation ( 12) of (t k ) in terms of (α k ) is complicated, the inverse formulation is simple:

α k = t k -1 t k+1 .
2.2. Convergence rates of the values: Lyapunov analysis. Let us introduce the ingredients that will serve for the Lyapunov analysis. For k ≥ 1, the global energy W k is defined by ( 14)

W k := β k-1 Φ(x k ) -min H Φ + 1 2 x k -x k-1 2 .
Its importance is due to the fact that, for damped inertial gradient systems, it is the global energy that decreases. Given x * ∈ argmin Φ, the anchor sequence (h k ) is defined by: for k ≥ 1 (15)

h k := 1 2 x k -x * 2 .
Let us define the sequence (E k ) by: for every k ≥ 1 ( 16)

E k := t 2 k β k-1 (Φ(x k ) -min H Φ) + 1 2 x k-1 + t k (x k -x k-1 ) -x * 2 .
Note that

E k = t 2 k W k + 1 2 x k-1 -x * 2 + t k x k -x k-1 , x k-1 -x * .
This formulation shows E k as a weighted sum of the global energy, the anchor function, and the discrete time derivative of the anchor function. For our next calculation, we will use the formulation [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF], which, as a main advantage, involves only non-negative terms. The following result shows that the sequence (E k ) is non-increasing, under the condition (K 1,α k ,β k ), that involves the two sequences (α k ), and (β k ) together.

Proposition 2.2. Assume that the non-negative sequence (α k ) satisfies (K 0 ). Let (x k ) be a sequence generated by algorithm (IP) α k ,β k , and let (E k ) be the sequence defined by ( 16). Then we have: for every k ≥ 1

(17) E k+1 -E k ≤ (t 2 k+1 β k -t 2 k β k-1 -t k+1 β k )(Φ(x k ) -min H Φ).
Under the assumption

(K 1,α k ,β k ) t 2 k+1 β k -t 2 k β k-1 -t k+1 β k ≤ 0 for every k ≥ 1, then the sequence (E k ) is non-increasing.
Proof. By definition of the proximal operator, the iteration at step k of the algorithm (IP)

α k ,β k writes 1 β k (y k -x k+1 ) ∈ ∂Φ(x k+1 ).
Equivalently, we have the following subdifferential inequalities: for any x ∈ H

(18) Φ(x) ≥ Φ(x k+1 ) + 1 β k x -x k+1 , y k -x k+1 .
Let us write successively inequality (18) at x = x k and x = x * ∈ argmin Φ. We obtain the two inequalities

Φ(x k ) ≥ Φ(x k+1 ) + 1 β k x k -x k+1 , y k -x k+1 , (19)
Φ(x * ) ≥ Φ(x k+1 ) + 1 β k x * -x k+1 , y k -x k+1 . (20) Using x k -x k+1 = x k -y k + y k -x k+1 in (19) and x * -x k+1 = x * -y k + y k -x k+1 in (20) we obtain Φ(x k ) ≥ Φ(x k+1 ) + 1 β k x k -y k , y k -x k+1 + 1 β k y k -x k+1 2 , (21) Φ(x * ) ≥ Φ(x k+1 ) + 1 β k x * -y k , y k -x k+1 + 1 β k y k -x k+1 2 . ( 22
)
Multiplying ( 21) by t k+1 -1 ≥ 0, then adding [START_REF] Kim | Optimized first-order methods for smooth convex minimization[END_REF], we derive that

(t k+1 -1)(Φ(x k ) -Φ(x * )) ≥ t k+1 (Φ(x k+1 ) -Φ(x * )) + 1 β k x k+1 -y k , (t k+1 -1)(y k -x k ) + y k -x * + t k+1 β k y k -x k+1 2 .
Observe that

(t k+1 -1)(y k -x k ) + y k = t k+1 y k -(t k+1 -1)x k = x k + t k+1 α k (x k -x k-1 ) = x k-1 + (1 + t k+1 α k )(x k -x k-1 ) = x k-1 + t k (x k -x k-1
) in view of [START_REF] Aujol | Stability of over-relaxations for the Forward-Backward algorithm, application to FISTA[END_REF].

Setting

z k = x k-1 + t k (x k -x k-1
), we then deduce from ( 23) that

(t k+1 -1)(Φ(x k ) -Φ(x * )) ≥ t k+1 (Φ(x k+1 ) -Φ(x * )) (23) + 1 β k x k+1 -y k , z k -x * + t k+1 β k y k -x k+1 2 .
Equivalently, after multiplication by

β k β k (t k+1 -1)(Φ(x k ) -Φ(x * )) ≥ β k t k+1 (Φ(x k+1 ) -Φ(x * )) (24) + x k+1 -y k , z k -x * + t k+1 y k -x k+1 2 .
To write [START_REF] Lorenz | An inertial forward-backward algorithm for monotone inclusions[END_REF] in a recursive form, observe that

z k+1 -z k = x k + t k+1 (x k+1 -x k ) -x k-1 -t k (x k -x k-1 ) = t k+1 (x k+1 -x k ) -(t k -1)(x k -x k-1 ) = t k+1 (x k+1 -x k -α k (x k -x k-1 )) in view of (13) = t k+1 (x k+1 -y k ).
It ensues that

z k+1 -x * 2 = z k -x * 2 + 2t k+1 x k+1 -y k , z k -x * + t 2 k+1 x k+1 -y k 2 ,
which gives

x k+1 -y k , z k -x * = 1 2t k+1 z k+1 -x * 2 -z k -x * 2 - t k+1 2 x k+1 -y k 2 .
Using this equality in [START_REF] Lorenz | An inertial forward-backward algorithm for monotone inclusions[END_REF], we find

β k (t k+1 -1)(Φ(x k ) -Φ(x * )) ≥ β k t k+1 (Φ(x k+1 ) -Φ(x * )) + t k+1 2 y k -x k+1 2 + 1 2t k+1 z k+1 -x * 2 -z k -x * 2 .
After multiplication by t k+1 , and neglecting the non-negative term t k+1 2 y k -x k+1 2 , we obtain

β k (t 2 k+1 -t k+1 )(Φ(x k ) -Φ(x * )) + 1 2 z k -x * 2 . ≥ β k t 2 k+1 (Φ(x k+1 ) -Φ(x * )) + 1 2 z k+1 -x * 2 .
Note that the sequence (E k ) writes equivalently

E k = t 2 k β k-1 (Φ(x k ) -min H Φ) + 1 2 z k -x * 2
. Thus, we have obtained the following inequality

E k ≥ E k+1 + (t 2 k β k-1 -β k (t 2 k+1 -t k+1 ))(Φ(x k ) -min H Φ). Under condition (K 1,β k ) we have t 2 k β k-1 -β k (t 2 k+1 -t k+1 ) ≥ 0. As a consequence E k ≥ E k+1 , and the sequence (E k ) is non-increasing.
As a result of Proposition 2.2, we obtain the convergence rate of values as shown below.

Theorem 2.3. Suppose that the sequence (α k ) satisfies (K 0 ). Suppose that (α k ) and (β k ) satisfy (K 1,α k ,β k ). Let (x k ) be a sequence generated by algorithm (IP) α k ,β k . Then we have

(i) For every k ≥ 1, Φ(x k ) -min H Φ ≤ C t 2 k β k-1 , with C = t 2 1 β 0 (Φ(x 1 ) -min H Φ) + 1 2 (d(x 0 , argmin H Φ) 2 + t 2 1 x 1 -x 0 2 ).
(ii) Assume moreover that there exists m < 1 such that

(K + 1,α k ,β k ) t 2 k+1 β k -t 2 k β k-1 ≤ m t k+1 β k for every k ≥ 1.
Then we have

+∞ k=1 t k+1 β k (Φ(x k ) -min H Φ) < +∞. Proof. (i) From Proposition 2.2, the sequence (E k ) is non-increasing. It ensues that E k ≤ E 1 for every k ≥ 1.
Recalling the expression of E k , we deduce that

t 2 k β k-1 (Φ(x k ) -min H Φ) ≤ t 2 1 β 0 [Φ(x 1 ) -min H Φ] + 1 2 x 0 -x * + t 1 (x 1 -x 0 ) 2 ≤ t 2 1 β 0 [Φ(x 1 ) -min H Φ] + 1 2 x 0 -x * 2 + t 2 1 2 x 1 -x 0 2
Since x * can be taken arbitrarily in argmin H Φ, we finally obtain

t 2 k β k-1 (Φ(x k ) -min H Φ) ≤ C, with C = t 2 1 β 0 (Φ(x 1 ) -min H Φ) + 1 2 (d(x 0 , argmin H Φ) 2 + t 2 1 x 1 -x 0 2 ).
(ii) By summing inequality [START_REF] Bot | A second order dynamical approach with variable damping to nonconvex smooth minimization[END_REF] from k = 1 to n, we find

E n+1 + n k=1 (t k+1 β k -t 2 k+1 β k + t 2 k β k-1 )(Φ(x k ) -min H Φ) ≤ E 1 . Since E n+1 ≥ 0 and since t 2 k+1 β k -t 2 k β k-1 ≤ m t k+1 β k , this implies that (1 -m) n k=1 t k+1 β k (Φ(x k ) -min H Φ) ≤ E 1 .
By letting n tend to infinity, we obtain

∞ k=1 t k+1 β k (Φ(x k ) -min H Φ) ≤ E 1 1 -m ,
which gives the claim.

2.3. Particular cases.

2.3.1.

Case β k ≡ s > 0, α k general. This is the case without scaling. The algorithm (IP) α k ,β k writes (25)

y k = x k + α k (x k -x k-1 ) x k+1 = prox sΦ (y k ), Condition (K 1,α k ,β k ) becomes t 2 k+1 -t 2 k -t k+1 ≤ 0 for every k ≥ 1.
Under this condition, we obtain the convergence rate of values

Φ(x k ) -min H Φ ≤ C t 2 k .
Thus, we recover the convergence rate of values of Attouch-Cabot [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF].

2.3.2. Case α k = 1 -α k , β k general. The algorithm (IP) α k ,β k writes (26) y k = x k + 1 -α k (x k -x k-1 ) x k+1 = prox β k Φ (y k ), Then, t k = k-1
α-1 (see [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF]), and condition (K 1,β k ) becomes

β k+1 ≤ β k k 2 (k + 1)(k + 2 -α) .
Under this condition, we obtain the convergence rate of values

Φ(x k ) -min H Φ ≤ C k 2 β k .
Thus, we recover the result of Attouch-Chbani-Riahi [7, section 7].

Convergence rate of the velocities

Let (x k ) be a sequence generated by the algorithm (IP) α k ,β k . We will analyze the convergence rate to zero of the velocity x k -x k-1 . Our analysis is based on the global energy decay. Recall that the friction effect, and thus the dissipation of energy, is related to α k ≤ 1. Proposition 3.1. Let (x k ) be a sequence generated by algorithm (IP) α k ,β k . Then, for every k ≥ 1,

β k (Φ(x k ) -min H Φ) + 1 2 x k -x k-1 2 ≥ β k (Φ(x k+1 ) -HΦ) + 1 2 x k+1 -x k 2 + 1 -α 2 k 2 x k -x k-1 2 . ( 27
)
Proof. The iteration at step k of the algorithm (IP) α k ,β k writes 1 β k (y k -x k+1 ) ∈ ∂Φ(x k+1 ), which gives:

(28) Φ(x k ) -min H Φ ≥ Φ(x k+1 ) -min H Φ + 1 β k y k -x k+1 , x k -x k+1 .
According to the extrapolation formula,

y k = x k + α k (x k -x k-1
), and after multiplication by β k we get

β k (Φ(x k ) -min H Φ) ≥ β k (Φ(x k+1 ) -min H Φ) + x k -x k+1 + α k (x k -x k-1 ), x k -x k+1 = β k (Φ(x k+1 ) -min H Φ) + x k -x k+1 2 + α k (x k -x k-1 ), x k -x k+1 .
By using the algebraic inequality

| α k (x k -x k-1 ), x k -x k+1 | ≤ 1 2 x k -x k+1 2 + α 2 k 2 x k -x k-1 2 ,
we deduce that

β k (Φ(x k ) -min H Φ) ≥ β k (Φ(x k+1 ) -min H Φ) + x k -x k+1 2 - 1 2 x k -x k+1 2 - α 2 k 2 x k -x k-1 2 .
Equivalently

β k (Φ(x k ) -min H Φ) + 1 2 x k -x k-1 2 ≥ β k (Φ(x k+1 ) -min H Φ) + 1 2 x k+1 -x k 2 + 1 -α 2 k 2 x k -x k-1 2 ,
which gives the claim.

Theorem 3.2. Suppose that (α k ) and (β k ) satisfy (K + 1,α k ,β k ). Then, we have

+∞ k=1 t k x k -x k-1 2 < +∞.
Proof. Consider, for k ≥ 1, the global energy W k , where we set m = min H Φ:

W k := β k-1 (Φ(x k ) -m) + 1 2 x k -x k-1 2 .
Let us multiply the inequality [START_REF]Weak convergence of the sequence of successive approximations for nonexpansive mappings[END_REF] obtained in Proposition 3.1 by

t 2 k+1 t 2 k+1 β k (Φ(x k ) -m) + 1 2 x k -x k-1 2 ≥ t 2 k+1 β k (Φ(x k+1 ) -m) + t 2 k+1 2 x k+1 -x k 2 + t 2 k+1 (1 -α 2 k ) 2 x k -x k-1 2 .
Let us reformulate this inequality in terms of the sequence (W k ). We have

t 2 k+1 β k-1 (Φ(x k ) -m) + (β k -β k-1 )(Φ(x k ) -m) + 1 2 x k -x k-1 2 ≥ t 2 k+1 W k+1 + t 2 k+1 (1 -α 2 k ) 2 x k -x k-1 2 ,
which gives

t 2 k+1 W k + t 2 k+1 (β k -β k-1 )(Φ(x k ) -m) ≥ t 2 k+1 W k+1 + t 2 k+1 (1 -α 2 k ) 2 x k -x k-1 2 .
Equivalently

t 2 k+1 (W k+1 -W k ) + t 2 k+1 (1 -α 2 k ) 2 x k -x k-1 2 ≤ t 2 k+1 (β k -β k-1 ) (Φ(x k ) -m).
Let us rewrite the above expression as

t 2 k+1 W k+1 -t 2 k W k + (t 2 k -t 2 k+1 )W k + t 2 k+1 (1 -α 2 k ) 2 x k -x k-1 2 ≤ t 2 k+1 (β k -β k-1 ) (Φ(x k ) -m).
Recalling the expression of W k , we deduce that

t 2 k+1 W k+1 -t 2 k W k + 1 2 [t 2 k -t 2 k+1 + t 2 k+1 (1 -α 2 k )] x k -x k-1 2 ≤ [(t 2 k+1 -t 2 k )β k-1 + t 2 k+1 (β k -β k-1 )](Φ(x k ) -m
). On the one hand, by [START_REF] Aujol | Stability of over-relaxations for the Forward-Backward algorithm, application to FISTA[END_REF], and since t k ≥ 1 we have

t 2 k -t 2 k+1 + t 2 k+1 (1 -α 2 k ) = t 2 k -t 2 k+1 α 2 k = t 2 k -(t k -1) 2 = 2t k -1 ≥ t k .
On the other hand, by using condition

(K + 1,α k ,β k ) we have (t 2 k+1 -t 2 k )β k-1 + t 2 k+1 (β k -β k-1 ) = t 2 k+1 β k -t 2 k β k-1 ≤ t k+1 β k .
Combining the above results we obtain (29)

t 2 k+1 W k+1 -t 2 k W k + 1 2 t k x k -x k-1 2 ≤ t k+1 β k (Φ(x k ) -m).
By Theorem 2.3, under the assumption

(K + 1,α k ,β k ) we have ∞ k=1 t k+1 β k (Φ(x k ) -m) < +∞.
As a consequence, by summing the above inequalities, we obtain 1 2

∞ k=1 t k x k -x k-1 2 ≤ t 2 1 W 1 + ∞ k=1 t k+1 β k (Φ(x k ) -m) < +∞,
which gives the claim.

Corollary 3.3. Suppose that the sequences (α k ) and (β k ) satisfy (K + 1,α k ,β k ). Suppose that 0 ≤ α k ≤ 1 for every k ≥ 1, and that the sequence (β k ) satisfies: there exists some positive constant C such that, for all k ≥ 1 (30)

β k ≤ Cβ k+1 .
Then, for any sequence (x k ) generated by the algorithm (IP) α k ,β k , we have

+∞ k=1 t k W k < +∞, where W k := β k-1 (Φ(x k ) -min H Φ) + 1 2 x k -x k-1 2 .
Proof. By Theorem 2.3 (ii), under the assumption (K + 1,α k ,β k ) we have ( 31)

+∞ k=1 t k+1 β k (Φ(x k ) -min H Φ) < +∞.
By assumption [START_REF] Peypouquet | Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time[END_REF] we have t k β k-1 ≤ Ct k β k . By Lemma 2.1, we have t k = 1 + α k t k+1 . Since 0 ≤ α k ≤ 1, and according to 1 ≤ t k+1 , this implies

t k ≤ 1 + t k+1 ≤ 2t k+1 .
Combining the two above inequalities, we obtain t k β k-1 ≤ 2Ct k+1 β k . According to [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] this implies (32)

+∞ k=1 t k β k-1 (Φ(x k ) -min H Φ) ≤ 2C +∞ k=1 t k+1 β k (Φ(x k ) -min H Φ) < +∞.
Combining this inequality with the estimate of the velocities

+∞ k=1 t k x k -x k-1 2 < +∞, obtained in Theorem 3.2, we obtain +∞ k=1 t k W k < +∞.
Remark 3.4. In Corollary 3.3, the assumption on the sequence (β k ) is satisfied in almost all practical situations. Clearly, it is satisfied if the sequence (β k ) is non-decreasing. It may be also decreasing like 1 k r for any r ≥ 0, or exp(-k). A limiting case in which it is not satisfied is 1 k! . Moreover, the assumption on the sequence (α k ) can be weakened, just assuming that it is bounded from above.

From O to o estimates

In line with Attouch-Peypouquet [START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k 2[END_REF] and Attouch-Cabot [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], we have the following convergence rate of values, where O is replaced by o.

Theorem 4.1. Let us assume that the non-negative sequence (α k ) is bounded from above, (α k ) and (β k ) satisfy the condition (K + 1,α k ,β k ), and there exists some positive constant C such that β k ≤ Cβ k+1 for all k ≥ 1. Then, for any sequence (x k ) generated by the algorithm (IP) α k ,β k , we have:

i) If 1 t k = +∞, then Φ(x k ) -min H Φ = o 1 t 2 k β k and x k -x k-1 2 = o 1 t 2 k . ii) If t k β k-1 = +∞, 0 ≤ α k ≤ 1, and (β k ) is non-decreasing, then Φ(x k ) -min H Φ = o 1 k i=1 t i β i-1 and x k -x k-1 2 = o β k-1 k i=1 t i β i-1
.

In particular, Φ(x k ) → min H Φ as k → +∞.

Proof. Let's consider the sequence of global energies (W k ) introduced in the proof of Theorem 3.2

W k := β k-1 (Φ(x k ) -m) + 1 2 x k -x k-1 2
.

By Corollary 3.3 it satisfies

∞ k=1 t k W k < +∞.
i) Returning to (29) we have

t 2 k+1 W k+1 -t 2 k W k + 1 2 t k x k -x k-1 2 ≤ t k+1 β k (Φ(x k ) -m).
The non-negative sequence (a k ) with

a k := t 2 k W k satisfies the relation a k+1 -a k ≤ ω k with ω k = t k+1 β k (Φ(x k ) -m). According to k≥1 t k+1 β k (Φ(x k ) -m) < +∞ (see Theorem 2.3 (ii)) we have (w k ) ∈ l 1 (N)
. By a standard argument, we deduce that the limit of the sequence (a k ) exists, that is

lim k→+∞ t 2 k W k exists. Let c := lim k→+∞ t 2 k W k .
Let's show that c = 0. Let's argue by contradiction, and suppose that c > 0. As a result,

t k W k ∼ c t k . According to ∞ k=1 t k W k < +∞, this implies c 1 t k < +∞, a clear contradiction with the hypothesis 1 t k = +∞. Hence, c = 0. So, lim k→+∞ t 2 k W k = 0, which gives the claim.
ii) The argument is based on the non-increasing property of the sequence ( 1

β k-1 W k ).
Let us return to Proposition 3.1. After dividing [START_REF]Weak convergence of the sequence of successive approximations for nonexpansive mappings[END_REF] by β k , we get

(Φ(x k ) -min H Φ) + 1 2β k x k -x k-1 2 ≥ (Φ(x k+1 ) -min H Φ) + 1 2β k x k+1 -x k 2 + 1 -α 2 k 2β k x k -x k-1 2 . (33)
Let's formulate the above inequality in terms of the sequence (W k ). We obtain [START_REF] Schmidt | Convergence rates of inexact proximal-gradient methods for convex optimization[END_REF] 1

β k-1 W k + ( 1 2β k - 1 2β k-1 ) x k -x k-1 2 ≥ 1 β k W k+1 + 1 -α 2 k 2β k x k -x k-1 2 .
Since 0 ≤ α k ≤ 1, and the sequence (β k ) is non-decreasing, we deduce that

(35) 1 β k-1 W k ≥ 1 β k W k+1 .
Hence, the sequence (

1 β k-1 W k ) is non-increasing. Let us rewrite the estimate ∞ k=1 t k W k < +∞. as ∞ k=1 t k β k-1 1 β k-1 W k < +∞.
We are now in position to apply Lemma A.2 in the appendix, with the sequences (t k β k-1 ) and ( 1 β k-1 W k ), respectively in place of (τ k ) and (ε k ). We obtain that

1 β k-1 W k = o 1 k i=1 t i β i-1
as k → +∞.

Hence

W k = o β k-1 k i=1 t i β i-1
as k → +∞, which gives the claim.

As a direct consequence of Theorem 4.1, in the case without inertia, i.e. α k ≡ 0 (which gives t k ≡ 1) we obtain the following result.

Corollary 4.2. Suppose that the sequence (β k ) is non-decreasing. Then for any sequence (x k ) generated by the proximal algorithm x k+1 = prox β k Φ (x k ) we have the following estimates:

Φ(x k ) -min H Φ = o 1 k i=1 β i-1 and x k -x k-1 2 = o β k-1 k i=1 β i-1
.

When (β k ) is non-decreasing, this notably improves the results obtained by Güler in [20, Theorem 3.1].

Convergence of the iterates

Let us now fix x * ∈ argmin Φ, and define h k := 1 2 x k -x * 2 . The sequence (h k ) takes account of the anchoring of the sequence of iterates (x k ) to the solution set. The next result will be useful for establishing the convergence of the iterates of the algorithm (IP) α k ,β k . Proposition 5.1. For any k ≥ 1, the following inequality holds

(36) h k+1 -h k -α k (h k -h k-1 ) ≤ 1 2 (α 2 k + α k ) x k -x k-1 2 -β k (Φ(x k+1 ) -min H Φ).
Proof. Observe that

y k -x * 2 = x k + α k (x k -x k-1 ) -x * 2 = x k -x * 2 + α 2 k x k -x k-1 2 + 2α k x k -x * , x k -x k-1 = x k -x * 2 + α 2 k x k -x k-1 2 + α k x k -x * 2 + α k x k -x k-1 2 -α k x k-1 -x * 2 = x k -x * 2 + α k ( x k -x * 2 -x k-1 -x * 2 ) + (α 2 k + α k ) x k -x k-1 2 = 2[h k + α k (h k -h k-1 )] + (α 2 k + α k ) x k -x k-1 2 .
Set briefly

A k = h k+1 -h k -α k (h k -h k-1 ) = 1 2 x k+1 -x * 2 -[h k + α k (h k -h k-1 )
]. According to the above inequality, we get

A k = 1 2 x k+1 -x * 2 - 1 2 y k -x * 2 + 1 2 (α 2 k + α k ) x k -x k-1 2 = x k+1 -y k , 1 2 (x k+1 + y k ) -x * + 1 2 (α 2 k + α k ) x k -x k-1 2 = x k+1 -y k , y k -x * + 1 2 x k+1 -y k 2 + 1 2 (α 2 k + α k ) x k -x k-1 2 .
So, we obtain the equality

h k+1 -h k -α k (h k -h k-1 ) = 1 2 (α 2 k + α k ) x k -x k-1 2 + y k -x k+1 , x * -y k + 1 2 y k -x k+1 2 . ( 37
)
Now use that x * ∈ argmin Φ. By definition of the proximal operator, x k+1 = prox β k Φ (y k ) equivalently gives

1 β k (y k -x k+1 ) ∈ ∂Φ(x k+1 ). The convex subdifferential inequality applied at x k+1 gives Φ(x * ) ≥ Φ(x k+1 ) + 1 β k (y k -x k+1 ), x * -x k+1 .
Since Φ(x * ) = min H Φ, we infer that

y k -x k+1 , x * -x k+1 ≤ -β k (Φ(x k+1 ) -min H Φ). Hence y k -x k+1 2 + y k -x k+1 , x * -y k ≤ -β k (Φ(x k+1 ) -min H Φ).
Combining this inequality with [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF] gives

h k+1 -h k -α k (h k -h k-1 ) ≤ 1 2 (α 2 k + α k ) x k -x k-1 2 -β k (Φ(x k+1 ) -min H Φ),
which completes the proof of Proposition 5.1.

We will also need the following estimate for the velocities which completes Theorem 3.2.

Proposition 5.2. Suppose that the sequences (α k ) and (β k ) satisfy the condition (K + 1,α k ,β k ) and that the sequence (β k ) is non-decreasing. Then, we have

+∞ k=1 t k+1 x k -x k-1 2 < +∞.
Proof. Condition (K + 1,α k ,β k ) can be equivalently written as

(t 2 k+1 -t 2 k )β k + t 2 k (β k -β k-1 ) ≤ t k+1 β k Since the sequence (β k ) is non-decreasing, we infer t 2 k+1 -t 2 k ≤ t k+1 . Hence t k+1 -t k ≤ t k+1 t k+1 + t k ≤ 1. Since 1 ≤ t k , we immediately obtain t k+1 ≤ 2t k . So +∞ k=1 t k+1 x k -x k-1 2 ≤ 2 +∞ k=1 t k x k -x k-1 2 < +∞,
where the last inequality comes from Theorem 3.2.

Theorem 5.3. Assume that i) the sequences (α k ) and (β k ) satisfy the condition

(K + 1,α k ,β k ); ii) α k ∈ [0, 1] for every k ≥ 1; iii) the sequence (β k ) is non-decreasing; iv) ∞ k=1 t k β k-1 = +∞.
Then, any sequence (x k ) generated by the algorithm (IP) α k ,β k converges weakly, and its limit belongs to argmin Φ.

Proof. We apply the Opial lemma, see Lemma A.1. Assume that there exist x ∈ H and a sequence (k n ) such that k n → +∞, and x kn

x weakly as n → +∞. Since the convex function Φ is lower semicontinuous, it is lower semicontinuous for the weak topology, hence satisfies

Φ(x) ≤ lim inf n→+∞ Φ(x kn ) = lim k→+∞ Φ(x k ) = min H Φ,
where the last equality comes from Theorem 4.1. It ensues that x ∈ argmin Φ, which shows the first point. Let us now fix x * ∈ argmin Φ, and show that lim k→+∞ x k -x * exists. Set h k = 1 2 x k -x * 2 . From Proposition 5.1, (h k ) satisfies the following inequalities

h k+1 -h k -α k (h k -h k-1 ) ≤ 1 2 (α 2 k + α k ) x k -x k-1 2 ≤ x k -x k-1 2 since α k ∈ [0, 1].
Taking the positive part, we find

(h k+1 -h k ) + ≤ α k (h k -h k-1 ) + + x k -x k-1 2 .
By Proposition 5.2 we have

+∞ k=1 t k+1 x k -x k-1 2 < +∞. By applying Lemma A.3 (appendix) with a k = (h k -h k-1 ) + and ω k = x k -x k-1 2 , we obtain +∞ k=1 (h k -h k-1 ) + < +∞. Since (h k
) is nonnegative, this implies that lim k→+∞ h k exists. The second point of the Opial lemma is shown, which ends the proof.

Link with Güler's accelerated proximal algorithm

Let's recall Güler's accelerated proximal algorithm, see [START_REF] Güler | New proximal point algorithms for convex minimization[END_REF]. We modify the notations to adapt them to our framework. The proximal parameter noted λ k in Güler's article is noted here β k , and the inertial parameter is denoted by g k in place of γ k . a) Initialization of ν 0 and A 0 .

b)

Step k :

• Choose β k > 0, and calculate g k > 0 by solving

g 2 k + g k A k β k -A k β k = 0. • Define i) y k = (1 -g k )x k + g k ν k ; ii) x k+1 = prox β k Φ (y k ); iii) ν k+1 = ν k + 1 g k (x k+1 -y k ); iv) A k+1 = (1 -g k )A k .
(38) 6.1. Güler's accelerated proximal algorithm as (IP) α k ,β k . Let us show that Güler's proximal algorithm can be written as an inertial proximal algorithm (IP) α k ,β k . First verify that, for all k ≥ 1 (39)

ν k = x k-1 + 1 g k-1 (x k -x k-1 ) .
For this, we use an induction argument. Suppose (39) is satisfied at step k. Using successively (38) iii), (39), (38) i), and (39) again, we obtain

ν k+1 = ν k + 1 g k (x k+1 -y k ) = x k-1 + 1 g k-1 (x k -x k-1 ) + 1 g k (x k+1 -y k ) = 1 g k x k+1 + x k-1 + 1 g k-1 (x k -x k-1 ) - 1 g k ((1 -g k )x k + g k ν k ) = 1 g k x k+1 - 1 -g k g k x k = x k + 1 g k (x k+1 -x k ) ,
which shows that (39) is satisfied at step k + 1. Then, combining (38) i) with (39), we obtain

y k = (1 -g k )x k + g k ν k = (1 -g k )x k + g k x k-1 + 1 g k-1 (x k -x k-1 ) = x k + g k g k-1 -g k (x k -x k-1 ) .
Hence, Güler's proximal algorithm can be written as (40)

y k = x k + α k (x k -x k-1 ) x k+1 = prox β k Φ (y k ), with (41) α k = g k 1 g k-1 -1 .
By construction of g k , we have

g k = 1 2 -A k β k + (A k β k ) 2 + 4A k β k , which gives 0 ≤ g k < 1.
According to (41), we deduce that α k > 0. As a result, the first formula of (40) defines an extrapolation operation. This makes Güler's algorithm an inertial proximal algorithm, within the framework of the algorithm (IP) α k ,β k . From item iv) in Güler's algorithm, we immediately get:

(42) A k = A 0 k-1 j=0
(1 -g j ).

From the second-order algebraic equation that defines g k and (38) iv), we have 42) with (43), we obtain the following relation:

(43) g 2 k = A k β k (1 -g k ) = β k A k+1 . Combining (
(44) β k = g 2 k A 0 k j=0 (1 -g j )
.

According to (41)-( 42)-( 44), we have obtained that all the parameters entering into Güler's algorithm can be expressed according to the single parameter g k .

6.2. Convergence rate of Güler's accelerated proximal algorithm. Let us show that the convergence rate of Güler's accelerated proximal algorithm falls within the framework of Theorem 2.3. For this, we must make the link between the parameters used in Güler's algorithm and the parameter t k used in Theorem 2.3. We start from (45)

α k = g k 1 g k-1 -1 .
Let us show how to invert this relation. Set γ k = 1 -α k . According to (45)

γ k = 1 -g k 1 g k-1 -1 = g k 1 + 1 g k - 1 g k-1
.

Set

w k := 1 g k . The sequence (w k ) safisfies the finite-difference equation 1 + w k -w k-1 = γ k w k ,
which gives, for all k ≥ 1, w k-1 = 1 + α k w k . Comparing with the relation ( 13) that defines the sequence (t k ) in Lemma 2.1, we obtain w k = t k+1 . Hence, for all k ≥ 1 (46)

g k = 1 t k+1 .
We have now all the ingredients to verify that the condition

(K 1,α k ,β k ) t 2 k+1 β k -t 2 k β k-1 -t k+1 β k ≤ 0 for every k ≥ 1
, is satisfied by Güler's algorithm. We have

t 2 k+1 β k -t 2 k β k-1 -t k+1 β k = t k+1 β k (t k+1 -1) -t 2 k β k-1 = β k g k 1 -g k g k - β k-1 g 2 k-1 = g 2 k A 0 k j=0 (1 -g j ) 1 g k 1 -g k g k - 1 g 2 k-1 g 2 k-1 A 0 k-1 j=0 (1 -g j ) = 1 A 0 k-1 j=0 (1 -g j ) - 1 A 0 k-1 j=0 (1 -g j ) = 0.
So, Güler's accelerated proximal algorithm corresponds to taking equality in the condition (K 1,α k ,β k ). Let us summarize the above results.

Proposition 6.1. Güler's accelerated proximal algorithm is within the framework of algorithm (IP) α k ,β k with

α k = g k 1 g k-1 -1 . It satisfies the condition (K 1,α k ,β k )
with equality instead of inequality, i.e., for all k ≥ 1

t 2 k+1 β k -t 2 k β k-1 -t k+1 β k = 0. The following rate of convergence is satisfied: For every k ≥ 1, (47) Φ(x k ) -min H Φ ≤ C t 2 k β k-1 , with C = t 2 1 β 0 (Φ(x 1 ) -min H Φ) + 1 2 (d(x 0 , argmin H Φ) 2 + t 2 1 x 1 -x 0 2 ). Moreover, for every k ≥ 1, (48) Φ(x k ) -min H Φ = O 1 k j=1 t j β j-1
.

The above formulas can be expressed equivalently in terms of Güler's parameters thanks to the relation t k = 1 g k-1 :

Φ(x k ) -min H Φ = O g 2 k-1 β k-1 Φ(x k ) -min H Φ = O   1 k j=1 βj-1 gj-1   Proof.
The convergence rate given in (47) results from Theorem 2.3. Let us now exploit the fact that in the case of Güler's algorithm, the condition (K 1,α k ,β k ) is satisfied, with equality. By adding the equalities

t 2 j β j-1 -t 2 j-1 β j-2 = t j β j-1 from j = 1 to k, we get t 2 k β k-1 = k j=1 t j β j-1 + t 1 β 0 .
This gives (48), by just assuming that theses quantities are infinite. This is a minimal assumption to insure convergence of the algorithm.

Let's now compare the convergence rate given as above, which results from Theorem 2.3, with the convergence rate obtained by Güler in [START_REF] Güler | New proximal point algorithms for convex minimization[END_REF] (49) Φ(x k ) -min

H Φ = O    1 k-1 j=1 β j 2    .
The two above formulas give the same rate of convergence in most practical situations. Let's give a simple result where we can deduce the convergence rate obtained by Güler from the Proposition 6.1. Suppose that (β k ) is a non-decreasing sequence, and that t k ≥ Ck for some positive constant C, and k large enough. This last assumption is satisfied for the Nesterov type acceleration formula with α k = 1 -α k and α ≥ 3, see [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF]. Since (

β k ) is non-decreasing   k-1 j=1 β j   2 ≤ (k -1) 2 β k-1 .
Since t k ≥ Ck for k large enough, we deduce that (for some other constant C)

1 k-1 j=1 β j 2 ≥ C t 2 k β k-1
, which gives the claim. Remark 6.2. Güler's accelerated proximal algorithm corresponds to taking equality in (K 1,α k ,β k ). As such, it fits into the critical case, introduced historically by Nesterov, and for which the convergence of the iterates is still an open question. By contrast, as shown in Theorem 5.3, taking strict inequality (precisely assuming the condition (K + 1,α k ,β k )) gives the convergence of iterates, and makes it possible to pass from the capital O to small o convergence rates. See [START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm[END_REF] and [START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k 2[END_REF] who initiated this type of result. 6.3. Dynamic interpretation of Güler's algorithm. Let's come with the dynamic interpretation of Güler's algorithm, as formulated in (40-41). According to the formulation (41) of α k we get

x k+1 + β k ∂Φ(x k+1 ) y k = x k + g k 1 g k-1 -1 (x k -x k-1 ).
Equivalently, (50)

x k+1 -2x k + x k-1 + g k - g k -g k-1 g k-1 (x k -x k-1 ) + β k ∂Φ(x k+1 ) = 0.
This can be interpreted as a time discretization of the second-order evolution equation (when Φ is smooth)

(51) ẍ(t) + g(t) - ġ(t) g(t) ẋ(t) + β(t)∇Φ(x(t)) = 0.
So, Güler's proximal algorithm is based on the damped inertial dynamic (IGS) γ,β where the damping coefficient is expressed as

γ(t) = g(t) - ġ(t) g(t) = g(t) 1 + d dt 1 g (t) .
This makes the link with the next section, where we show that, in this context, the corresponding dynamic and proximal algorithms can be studied more directly: the conditions ensuring the rapid convergence of the algorithm can be expressed directly on the parameters g k and β k . This avoids the use of the coefficients t k whose study requires additional analysis, see [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF] for more details.

A class of inertial proximal algorithms

Motivated by the results above, we consider the proximal algorithms that can be obtained (when Φ is smooth) by various temporal discretizations of the second-order evolution equation ( 52)

ẍ(t) + g(t) 1 + d dt 1 g (t) ẋ(t) + λ(t)∇Φ(x(t)) = 0.
We will see that, without loss of generality, the convergence analysis for the Inertial Proximal algorithm (IP) α k ,β k can be developed within this setting. In doing so, we will introduce a class of inertial proximal algorithms, including the one studied in the previous sections, and which share similar convergence properties. Moreover, the convergence results can now be expressed directly on the parameters describing the algorithms.

7.1. Link between the two descriptions.

7.1.1. Continuous case. Let's show that taking g(t) 1 + d dt 1 g (t) as the damping coefficient γ(t) is not a restrictive assumption. To see this, given a continuous function γ(•), we have to integrate the differential equation ( 53)

g(t) 1 + d dt 1 g (t) = γ(t).
Take as a new unknown function w := 1 g . Then (53) is equivalent to solve the non-autonomous linear differential equation ẇ(t) -γ(t)w(t) = -1.

Set p(t) := exp t t0 γ(τ )dτ for t ≥ t 0 , then, following [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF] and assuming that +∞ t0 ds p(s) < +∞, we obtain as a solution

w(t) = p(t) ∞ t 1 p(s) ds.
This is the function Γ(•) introduced in [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF]. Hence g(t) = 1 Γ(t) is solution of (53). The general solution is g(t) = 1 Cp(t)+Γ(t) with 1 C = lim t→+∞ p(t)g(t). Let's summarize the above results in the following lemma. (54)

g(t) 1 + d dt 1 g (t) = γ(t).
Then, the following non-negative continuously differentiable function g(•) is solution of (54):

(55)

g(t) = 1 Γ(t)
where

Γ(t) = p(t) ∞ t 1 p(s) ds.
Precisely, it is the solution of (54) that satisfies lim t→+∞ 1 p(t)g(t) = 0. Note that the above definition of Γ does not depend on the initial time t 0 . When β(t) ≡ β > 0 is fixed, fast convergence of the values is obtained in [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF] under the condition γ(t)Γ(t) ≤ 3 2 . According to (54) and (55), in terms of g(t), this condition takes the equivalent form

g(t) 1 + d dt 1 g (t) 1 g(t) = 1 + d dt 1 g (t) ≤ 3 2 .
So, the condition γ(t)Γ(t) ≤ 3 2 becomes (56) d dt

1 g (t) ≤ 1 2 ,
with the corresponding convergence rate of the values (57) Φ(x(t)) -min

H Φ = O g(t) 2 .
This shows the obvious interest in formulating the damping coefficient in the form g(t) 1 + d dt 1 g (t) . There is no loss of generality, and the conditions for obtaining rapid convergence results can be formulated directly on the data g. For example, let's start with g(t) = α-1 t . From (54), we immediately obtain γ(t) = α t . Then, (56)-(57) shows that the well-known condition α ≥ 3 provides the O 1 t 2 convergence rate of values (see [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF], [START_REF] Aujol | Optimal rate of convergence of an ODE associated to the Fast Gradient Descent schemes for b > 0[END_REF], [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF]). 7.1.2. Discrete case. Similar results occur in the discrete case. Recall that the implicit temporal discretization of (52) gives (58)

x k+1 -2x k + x k-1 + g k 1 + 1 g k - 1 g k-1 (x k -x k-1 ) + λ k ∂Φ(x k+1 ) 0.
Equivalently (59)

y k = x k + α k (x k -x k-1 ) x k+1 = prox λ k Φ (y k ),
where (60)

α k = g k 1 g k-1 -1 . Set γ k = 1 -α k . This gives γ k = g k 1 + 1 g k -1 g k-1 .
As shown in the previous section, inverting this relation gives, for all k ≥ 1, g k = 1 t k+1 . Let's summarize the above results in the following lemma. Lemma 7.2. Let (γ k ) be a sequence of non-negative numbers. Consider the following finite-difference equation, where the unknown sequence is (g k ) (61)

g k 1 + 1 g k - 1 g k-1 = γ k .
Then, the following sequence of non-negative numbers is solution of (61):

(62)

g k = 1 t k+1
where

t k = 1 + +∞ i=k i j=k α j .
Following Theorem 1.1 recalled in the introduction, when β k ≡ β > 0 is fixed, we obtain a fast convergence of the values (see [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF]) under the condition (K 1 ) ∀k ≥ 1, t 2 k+1 -t 2 k ≤ t k+1 . According to the above lemma this condition can be equivalently formulated in terms of g k as (63)

g k ≥ 1 - g k g k-1 2 ,
with the corresponding convergence rate of the values

(64) Φ(x k ) -min H Φ = O g 2 k .
Starting from g k = α-1 k , (61) immediately gives γ k = α k . Then (63)-(64) shows that the well-known condition α ≥ 3 provides the O 1 k 2 convergence rate of values, a classical result (see [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF], [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF], [START_REF] Attouch | The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than 1/k 2[END_REF], [START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm[END_REF], [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF]). 7.2. A parametrized family of proximal inertial algorithms. Let us start from the second-order evolution equation ( 52) and introduce various temporal discretizations. When considering the implicit discretization for the potential term, which gives proximal algorithms, we can take a general convex lower semicontinuous proper function Φ. As novelty, we introduce a parameter θ ∈ [0, 1] which takes into account different discretizations of the damping term: for k ≥ 1,

(x k+1 -2x k + x k-1 ) + g k (1 -θ) 1 + 1 g k+1 - 1 g k (x k+1 -x k ) + g k θ 1 + 1 g k - 1 g k-1 (x k -x k-1 ) + λ k ∂Φ(x k+1 ) 0.
For θ = 1, we recover the algorithm considered in the previous sections. After dividing by g k , we obtain

1 g k + (1 -θ) 1 + 1 g k+1 - 1 g k (x k+1 -x k ) - 1 g k + θ 1 g k-1 - 1 g k -1 (x k -x k-1 ) + λ k g k ∂Φ(x k+1 ) 0. Set, for k ≥ 1, θ k := 1 g k + θ 1 g k-1 -1 g k -1 . Note that 1 g k + (1 -θ) 1 + 1 g k+1 - 1 g k = 1 + θ k+1 .
So, we can reformulate the above algorithm in the condensed form (65)

x k+1 + λ k g k (1 + θ k+1 ) ∂Φ(x k+1 ) x k + θ k 1 + θ k+1 (x k -x k-1 ).
This gives the Inertial Proximal algorithm with parameter θ:

Inertial Proximal algorithm with parameter θ.

(IP) α k ,β k ,θ y k = x k + α k (x k -x k-1 )
x k+1 = prox β k Φ (y k ),

α k := θ k 1+θ k+1 ; β k := λ k g k (1+θ k+1 ) ; θ k := 1 g k + θ 1 g k-1 -1 g k -1 . (66)
(IP) α k ,β k ,θ fits into the general framework of (IP) α k ,β k , with extrapolation parameters and proximal parameters written in a specific form.

7.3. Convergence rates. An analysis parallel to that developed in the previous sections can be developed.

We only detail the study of the rapid convergence of values.

Theorem 7.3. Consider the inertial proximal algorithm (IP) α k ,β k ,θ where α k := θ k 1+θ k+1 , β k := λ k g k (1+θ k+1 ) , and

θ k := 1 g k + θ 1 g k-1 -1 g k -1 . Suppose that 0 < g k ≤ 1, 0 ≤ θ ≤ 1
, and the parameters (g k ), (λ k ) and θ satisfy the growth condition: there exists k 1 ∈ N such that for all k ≥ k 1

(K 1,g k ,λ k ,θ ) λ k+1 ≤ g k+1 g k θ k+1 + 1 θ k+2 λ k .
Then, for any sequence (x k ) generated by the algorithm (IP) α k ,β k ,θ , we have

             (i) Φ(x k ) -min H Φ = O g k-1 λ k-1 (1 + θ k ) , as k → +∞; (ii) k≥1 β k,θ (Φ(x k ) -min H Φ) < +∞ where β k,θ := λ k-1 g k-1 (1 + θ k ) -λ k g k θ k+1 is non-negative by (K 1,g k ,λ k ,θ ).
The proof is similar to that of the more general perturbed case (Theorem 8.1).

7.4. Some examples. Depending on the choice of the parameter θ, we obtain a specific algorithm, with its convergence rate. The classical situation (considered below) corresponds to the explicit discretization (θ = 1) of the damping term. Let's consider the following cases of particular interest: a) Case θ = 1: it corresponds to the explicit discretization of the damping term

(67) (x k+1 -2x k + x k-1 ) + g k 1 + 1 g k - 1 g k-1 (x k -x k-1 ) + β k ∂Φ(x k+1 ) 0.
This is precisely the algorithm studied in the previous section with

α k = g k 1 g k-1 -1 .
Let us compare the result obtained by applying respectively Theorem 2.3 (using the t k ) and Theorem 7.3 (using the g k in an explicit form). On the one hand, according to g k = 1 t k+1 , the growth condition (K 1,α k ,β k ) of Theorem 2.3 can be written

β k+1 ≤ g k+1 g 2 k ( 1 g k+1 -1) β k .
Making θ = 1 in the formula giving the parameters, we have

θ k := 1 g k + 1 g k-1 - 1 g k -1 = 1 g k-1 -1. Hence θ k+1 + 1 = 1 g k , which gives β k = λ k . The formula (K 1,g k ,λ k ,θ ) in Theorem 7.3 becomes (68) β k+1 ≤ g k+1 g k 1 g k 1 g k+1 -1 β k = g k+1 g 2 k ( 1 g k+1 -1) β k .
So we recover the same growth condition. Let us now compare the convergence rates. Theorem 2.3 gives

Φ(x k ) -min H Φ = O 1 t 2 k β k-1 . Theorem 7.3 gives Φ(x k ) -min H Φ = O g k-1 λ k-1 (1 + θ k ) . From θ k + 1 = 1 g k-1 we get g k-1 λ k-1 (1 + θ k ) = g 2 k-1 λ k-1 = 1 t 2 k β k-1 .
So, we recover the same convergence rate. b) Case θ = 0: it corresponds to the implicit discretization of the damping term

(69) (x k+1 -2x k + x k-1 ) + g k 1 + 1 g k+1 - 1 α k (x k+1 -x k ) + β k ∂Φ(x k+1 ) 0.
We have θ k = 1 g k , which gives algorithm (IP) α k ,β k ,θ with α k = g k+1 g k (1 + g k+1 ) and β k = λ k g k+1 g k (1 + g k+1 ) . Theorem 7.3 gives that, under the condition (K 1,g k ,λ k ,θ )

λ k+1 ≤ (1 + g k+1 )g k+2 g k λ k , we have Φ(x k ) -min H Φ = O g k g k-1 λ k-1 (1 + g k )
, as k → +∞;

Consider the particular case g k = α-1 k-1 . This gives α k = k-1 k+α-1 , which corresponds to a variant of the Nesterov acceleration scheme considered in [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF], [START_REF] Chambolle | On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm[END_REF], [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF]. An elementary calculation shows that the growth condition above and the corresponding convergence rate give results comparable to those of the explicit case.

Stability with respect to perturbations, errors

Consider the perturbed version of the evolution equation (52

) (70) ẍ(t) + g(t) 1 + d dt 1 g (t) ẋ(t) + λ(t)∇Φ(x(t)) = e(t)
where the second member of (70), denoted by e(•), can be interpreted as an external action on the system, a perturbation, or a control term. By following a parallel approach to the time discretization procedure described in section 7.2, we obtain : for k ≥ 1,

(x k+1 -2x k + x k-1 ) + g k (1 -θ) 1 + 1 g k+1 - 1 g k (x k+1 -x k ) + g k θ 1 + 1 g k - 1 g k-1 (x k -x k-1 ) + λ k ∂Φ(x k+1 ) e k
From the algorithmic point of view, the sequence (e k ) of elements of H takes into account the presence of perturbations, approximations, or errors. After dividing by g k , we obtain

1 g k + (1 -θ) 1 + 1 g k+1 - 1 g k (x k+1 -x k ) - 1 g k + θ 1 g k-1 - 1 g k -1 (x k -x k-1 ) + λ k g k ∂Φ(x k+1 ) 1 g k e k .
Set, for k ≥ 1

θ k := 1 g k + θ 1 g k-1 - 1 g k -1 . Note that 1 g k + (1 -θ) 1 + 1 g k+1 - 1 g k = 1 + θ k+1 .
So, we can reformulate the above algorithm in the condensed form

(71) (1 + θ k+1 )(x k+1 -x k ) + λ k g k ∂Φ(x k+1 ) θ k (x k -x k-1 ) + 1 g k e k .
Equivalently, (72)

x k+1 + λ k g k (1 + θ k+1 ) ∂Φ(x k+1 ) x k + θ k 1 + θ k+1 (x k -x k-1 ) + 1 g k (1 + θ k+1 ) e k .
This gives the Inertial Proximal algorithm with parameter θ and error r k , (IP) α k ,β k ,r k ,θ for short Inertial Proximal Algorithm with parameter θ and error r k .

(IP) α k ,β k ,r k ,θ y k = x k + α k (x k -x k-1 ) x k+1 = prox β k Φ (y k -r k ), α k := θ k 1+θ k+1 ; β k := λ k g k (1+θ k+1 ) ; r k = - 1 g k (1+θ k+1 ) e k θ k := 1 g k + θ 1 g k-1 -1 g k -1 . (73)
The following result extends Theorem 2.3 to the perturbed case.

Theorem 8.1. Consider the inertial proximal algorithm (IP) α k ,β k ,r k ,θ . Suppose that 0 < g k ≤ 1, 0 ≤ θ ≤ 1, and the parameters (g k ), (λ k ) and θ satisfy the growth condition: there exists

k 1 ∈ N such that for all k ≥ k 1 (K 1,g k ,λ k ,θ ) λ k+1 ≤ g k+1 g k θ k+1 + 1 θ k+2 λ k .
Suppose that the sequence (r k ) satisfies the summability property

(74) k≥1 (1 + θ k+1 ) r k < +∞.
Then, for any sequence (x k ) generated by the algorithm (IP) α k ,β k ,r k ,θ , we have

             (i) Φ(x k ) -min H Φ = O g k-1 λ k-1 (1 + θ k )
, as k → +∞;

(ii) k≥1 β k,θ (Φ(x k ) -min H Φ) < +∞ where β k,θ := λ k-1 g k-1 (1 + θ k ) -λ k g k θ k+1 is non-negative by (K 1,g k ,λ k ,θ ).

Proof. To make the presentation simpler, without loss of generality, we take k 1 = 1. By definition of the proximal operator, the iteration at step k of the algorithm (IP) α k ,β k ,θ is written

1 β k (y k -x k+1 -r k ) ∈ ∂Φ(x k+1 ).
Equivalently, we have the following subdifferential inequalities: for any x ∈ H

θ k α k -1 (Φ(x k ) -Φ(x * )) ≥ θ k α k (Φ(x k+1 ) -Φ(x * )) + θ k α k β k y k -x k+1 2 + 1 β k x k+1 -y k , θ k α k -1 (y k -x k ) + y k -x * (80) + 1 β k θ k α k -1 (x k+1 -x k ) + x k+1 -x * , r k .
By definition of y k we have

θ k α k -1 (y k -x k ) + y k = θ k α k -1 α k (x k -x k-1 ) + x k + α k (x k -x k-1 ) = x k + θ k (x k -x k-1 ) = z k
where z k := x k + θ k (x k -x k-1 ). Moreover θ k α k -1 (x k+1 -x k ) + x k+1 = θ k+1 (x k+1 -x k ) + x k+1 = z k+1 .

We then deduce from (80) that

θ k α k -1 (Φ(x k ) -Φ(x * )) ≥ θ k α k (Φ(x k+1 ) -Φ(x * )) + 1 β k x k+1 -y k , z k -x * + 1 β k r k , z k+1 -x * + θ k α k β k y k -x k+1 2 .
Equivalently, after multiplication by β k

β k θ k α k -1 (Φ(x k ) -Φ(x * )) ≥ β k θ k α k (Φ(x k+1 ) -Φ(x * )) + x k+1 -y k , z k -x * + r k , z k+1 -x * + θ k α k y k -x k+1 2 . ( 81
)
To write (81) in a recursive form, we use z k+1 -z k = (1 + θ k+1 ) (x k+1 -y k ) . It ensues that

z k+1 -x * 2 = z k -x * 2 + 2(1 + θ k+1 ) x k+1 -y k , z k -x * + (1 + θ k+1 ) 2 x k+1 -y k 2 ,
which gives

x k+1 -y k , z k -x * = 1 2(1 + θ k+1 ) z k+1 -x * 2 -z k -x * 2 - (1 + θ k+1 ) 2 x k+1 -y k 2 .
Using this equality in (81), we find

β k θ k α k -1 (Φ(x k ) -Φ(x * )) ≥ β k θ k α k (Φ(x k+1 ) -Φ(x * )) + r k , z k+1 -x * + 1 2(1 + θ k+1 ) z k+1 -x * 2 -z k -x * 2 + (1 + θ k+1 ) 2 x k+1 -y k 2 ,
where we have used

θ k α k -(1+θ k+1 ) 2 = (1+θ k+1 ) 2
(a consequence of the definition of α k ). After multiplication by

(1 + θ k+1 ), and neglecting the non-negative term (1+θ k+1 ) 2

x k+1 -y k 2 , we obtain

β k (1 + θ k+1 ) θ k α k -1 (Φ(x k ) -Φ(x * )) + 1 2 z k -x * 2 ≥ β k (1 + θ k+1 )θ k α k (Φ(x k+1 ) -Φ(x * )) + 1 2 z k+1 -x * 2 + (1 + θ k+1 ) r k , z k+1 -x * . (82)
According to β k (1 + θ k+1 ) = λ k g k , and θ k α k -1 = θ k+1 we have

β k (1 + θ k+1 ) θ k α k -1 = λ k g k θ k+1 .
Hence, (82) can be equivalently written as

λ k g k θ k+1 (Φ(x k ) -Φ(x * )) + 1 2 z k -x * 2 ≥ λ k g k (1 + θ k+1 )(Φ(x k+1 ) -Φ(x * )) + 1 2 z k+1 -x * 2 + (1 + θ k+1 ) r k , z k+1 -x * .
This naturally leads us to introduce the sequence (E k ) (83)

E k = λ k-1 g k-1 (1 + θ k )(Φ(x k ) -Φ(x * )) + 1 2 z k -x * 2 .
Thus, we have obtained the following inequality

E k ≥ E k+1 + λ k-1 g k-1 (1 + θ k ) - λ k g k θ k+1 (Φ(x k ) -min H Φ) + (1 + θ k+1 ) r k , z k+1 -x * . (84) Under condition K 1,g k ,λ k ,θ we have λ k-1 g k-1 (1 + θ k ) -λ k g k θ k+1 ≥ 0. Hence, (85) (1 + θ k+1 ) r k × z k+1 -x * + E k ≥ E k+1 .
By summing inequalities (85) from j = 1 to k -1, we obtain (86)

E k ≤ E 1 + k j=2
(1 + θ j ) r j-1 × z j -x * .

Since E k ≥ 1 2 z k -x * 2 , we deduce that (87)

z k -x * 2 ≤ 2E 1 + k j=1 2(1 + θ j ) r j-1 × z j -x * .
Let us apply the Gronwall lemma A.4 with a j = z j -x * , b j = 2(1 + θ j ) r j-1 , and c = √ 2E 1 . We obtain

z k -x * ≤ 2E 1 + ∞ j=1 2(1 + θ j ) r j-1 .
By assumption (74), √ 2E 1 + ∞ j=1 2(1 + θ j ) r j-1 is a positive finite real number. Returning to (86) we obtain (88)

E k ≤ C := E 1 + k j=2 (1 + θ j ) r j-1   2E 1 + ∞ j=1 2(1 + θ j ) r j-1   .
By definition of E k , we obtain, for all k ≥ k 1

λ k-1 g k-1 (1 + θ k )(Φ(x k ) -Φ(x * )) ≤ E k ≤ C,
which gives the claim. The last item follows directly by summing (84).

Remark 8.2. According to the relations between the parameters, the summability assumption on the errors can be equivalently formulated in terms of e k as k≥1 1 g k e k < +∞.

When θ = 1 and α k = 1 -α k , using 1 g k = t k+1 , we recover the condition k≥1 k e k < +∞ considered in [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF].

  ) + p 2 s 2(p-1) ∇Φ(y(s)) = 0, where α p = 1 + (α -1)p. The convergence rate of values becomes

Lemma 7 . 1 .

 71 Let γ : [t 0 , +∞[→ R be a positive continuous function. Set p(t) = exp t t0 γ(τ )dτ and assume +∞ t0 ds p(s) < +∞. Consider the following differential equation, where the unknown function is g(•):

β k y k -x k+1 2 ,β k y k -x k+1 2 .θ k α k - 1 ≥

 221 ) ≥ Φ(x k+1 ) + 1 β k x -x k+1 , y k -x k+1 -1 β k x -x k+1 , r k .Let us write successively inequality (75) at x = x k and x = x * ∈ argmin Φ. We obtain the two inequalitiesΦ(x k ) ≥ Φ(x k+1 ) + 1 β k x k -x k+1 , y k -x k+1 -1 β k x k -x k+1 , r k , (76) Φ(x * ) ≥ Φ(x k+1 ) + 1 β k x * -x k+1 , y k -x k+1 -1 β k x * -x k+1 , r k . (77) Using x k -x k+1 = x k -y k + y k -x k+1 in (76) and x * -x k+1 = x * -y k + y k -x k+1 in (77) we obtain Φ(x k ) ≥ Φ(x k+1 ) + 1 β k x k -y k , y k -x k+1 -1 β k x k -x k+1 , r k + 1 (78) Φ(x * ) ≥ Φ(x k+1 ) + 1 β k x * -y k , y k -x k+1 -1 β kx * -x k+1 , r k + 1 0, then adding (79), we derive that

  , let us introduce the sequence (t k ) that plays a central role in the analysis of algorithm (IP) α k ,β k .2.1. The sequence (t k ). Given k ≥ 1, assume that

		+∞	i
			α j < +∞ and set t k = 1 +	+∞ i=k	i j=k α j . We use
		i=k	j=k
	the convention	k-1 j=k α j = 1, which gives the compact form of t k
	(12)

Appendix A. Some auxiliary results

The following auxiliary lemmas are used throughout the paper. To establish the weak convergence of the iterates of (IP) α k ,β k , we apply Opial's Lemma [START_REF]Weak convergence of the sequence of successive approximations for nonexpansive mappings[END_REF], that we recall in its discrete form.

Lemma A.1. Let S be a nonempty subset of H, and (x k ) a sequence in H. Assume that (i) every sequential weak cluster point of (x k ), as k → +∞, belongs to S;

(ii) for every z ∈ S, lim k→+∞ x k -z exists. Then (x k ) converges weakly as k → +∞ to a point in S.

Owing to the next lemma, we are able to estimate the rate of convergence of a sequence (ε k ) supposed to be non-increasing and summable with respect to weight coefficients, see [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF]Lemma 21] for the proof.

Lemma A.2. Let (τ k ) be a nonnegative sequence such that +∞ k=1 τ k = +∞. Assume that (ε k ) is a non-negative and non-increasing sequence satisfying +∞ k=1 τ k ε k < +∞. Then we have

The following result shows the summability of a sequence (a k ) satisfying some suitable inequality.

Lemma A.3. Given a non-negative sequence (α k ) satisfying (K 0 ), let (t k ) be the sequence defined by t k = 1 + +∞ i=k i j=k α j . Let (a k ) and (ω k ) be two sequences of nonnegative numbers such that (89)

or equivalently a k ≤ (t k a k -t k+1 a k+1 ) + t k+1 ω k . By summing from k = 0 to n, we obtain