J-F Aujol

Ch Dossal
email: charles.dossal@insa-toulouse.fr

A Rondepierre
email: aude.rondepierre@insa-toulouse.fr

Convergence rates of the Heavy-Ball method with Lojasiewicz property

Keywords: Lyapunov function, rate of convergence, ODEs, optimization, Lojasiewicz property, Heavy Ball method

. Convergence results with much weaker assumptions are given in the present paper: namely, linear convergence rates when assuming a growth condition (which amounts to a Lojasiewicz property in the convex case). This analysis is firstly performed in continuous time for the ODE, and then transposed for discrete optimization schemes. In particular, a variant of the Heavy Ball algorithm is proposed, which converges geometrically whatever the parameters choice, and which has the best state of the art convergence rate for first order methods to minimize composite non smooth convex functions satisfying a Lojasiewicz property.

Introduction

Let us consider the following unconstrained minimization problem

min x∈R n F (x) (1)
where F : R n → R is a convex function having a non-empty set of minimizers X * . Depending on the assumptions on F , there exist plenty of algorithms to solve this problem. The convergence of these algorithms and their rate of convergence may highly depend on the properties of F . If F is differentiable with a L-Lipschitz continuous gradient, a classical algorithm is the explicit Gradient Descent (GD) which ensures the convergence to a minimizer x * of F . The convergence rate of (GD) i.e. the decay of F (x n ) -F (x * ), may be quite slow for some convex functions but it is actually exponential when F is strongly convex. Most algorithms such as inertial algorithms (Heavy Ball or Nesterov acceleration schemes), ensure a better convergence rate if F is known to be strongly convex. Most of the time the parameter µ of strong convexity is a parameter of the algorithm. Nevertheless, the strong convexity assumption may not be satisfied in many numerical problems. Strong convexity is indeed a strong hypothesis. It turns out that many functions are not strongly convex but still have good properties for optimization. A weaker property ensuring an exponential convergence of the Gradient Descent is actually the Lojasiewicz property with an exponent θ = 1 2 . This property is equivalent for convex functions to a quadratic growth condition around the set of minimizers. Roughly speaking a function F satisfies the Lojasiewicz property with parameter θ ∈ [0, 1) if around its set of minimizers we have:

F (x) -F * µ 2 d(x, X * ) 1 θ . ( 2
)
that is, if θ = 1 2 , F grows at most quadratically around the set of minimizers. In the present work we focus on the class of convex functions satisfying a Lojasiewicz property with a special interest to the subclass of functions satisfying a Lojasiewicz property with an exponent 1 2 , which gathers a large set of functions used in image processing and statistics. A well-known example of such a function is the LASSO function:

F (x) = 1 2 Ax -y 2 + λ x 1 (3)
If Ker(A) = {0}, the function F is not strongly convex and it may not be quasi-strongly convex [31, Definition 1] but it belongs to the class of convex functions having the Lojasiewicz property with an exponent θ = 1 2 [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF]. Following Polyak [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] a joint study of the dynamical system (4) ẍ(t) + α ẋ(t) + ∇F (x(t)) = 0 [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF] and of an associated algorithm that is a suitable discretization of the ODE (4), is proposed.

The study of the continuous dynamic to have of a better understanding of algorithms is actually a cornerstone of many recent works in optimization, see e.g. [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF][START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF][START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF][START_REF] Apidopoulos | On a second order differential inclusion modeling the FISTA algorithm[END_REF][START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF][START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF][START_REF] Cabot | On the long time behavior of second order differential equations with asymptotically small dissipation[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] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF].

The analysis of Polyak [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] rests on a C 2 hypothesis on F and most following studies by Nesterov [START_REF] Nesterov | Gradient methods for minimizing composite functions[END_REF], Ghadimi [START_REF] Ghadimi | Global convergence of the heavyball method for convex optimization[END_REF], Siegel [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF] or by the authors of the present work [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] necessitate a strong or at least weak strong convexity assumption. These previous results do not apply under a sole growth condition. Moreover the value of the parameter α in (4) must be chosen accordingly to strong convexity parameter of F to ensure the convergence and the rate of the algorithm.

The main contributions of this work can be summarized as follows.

1. Linear convergence rates for the ODE (4) associated to the Heavy ball in the case of a growth condition and uniqueness of a minimizer (which are the best known rates under these hypotheses), see Theorems 1 and 2.

2. New convergence rates for an algorithm inspired from ODE (4) in the case of a convex function with a L-Lipschitz gradient (or in the composite case) in the case when F satisfies any Lojasiewicz property, whatever the parameters choice, see Theorems 6 and 8.

3. Linear convergence rates for an algorithm inspired from ODE (4) under the additional assumption of uniqueness of the minimizer (which are the best known rates under these hypotheses), see Theorems 7 and 9.

More precisely, we extend the analysis of the first point with a non vanishing perturbation term and to the associated monotone inclusion. A conclusion of this first study is that the value of the friction parameter α in (4) ensuring the best decay rate of F (x(t)) -F (x * ) is different from the one obtained by Polyak [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] for C 2 strongly convex functions and obtained in [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] for weak strong convex functions.

The second contribution is algorithmic since we propose an inertial algorithm which is different from the classical Heavy Ball algorithm of Polyak and which convergence is ensured for a large set of parameters. No lower bounds on the growth parameters are needed to ensure the convergence of the iterates or a fast decay rate of F (x n ) -F (x * ) under Lojasiewicz properties. This is a main difference with most previous works in which the parameter α must be chosen small enough with respect to the strong convexity parameter of F . The given decay rate of F (x n ) -F (x * ) are polynomials and are the one we expect according to the continuous analysis of Bolte et al. [START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF] when the Lojasiewicz parameter θ is smaller than 1 2 and is linear when θ = 1 2 . To understand the third contribution, the reader must be aware of a key point : all exponential decay rates of various algorithms are not equivalent. We refer the reader to Definitions 5 and 6 in Section 3 for the exact definition of decay rate in the case of exponential convergence. In many practical problems, the value of the parameter µ in the growth condition ( 2) is very small. When F is continuously differentiable with a L-Lipschitz gradient, the condition number κ = µ L may be very small. This number drives the actual rate of many algorithms minimizing F . For the gradient descent we can expect that F (x n ) -F * = O(q n ) with q = 1 -κ. This rate is actually achieved for quadratic functions and we cannot expect a better rate for the gradient descent in general. If κ is really small, this decay may be really slow and not visible on numerical experiments. It is one of the reasons why the Forward Backward algorithm that can be seen as a extension of Gradient descent to composite functions F = f + g, is numerically slow on the LASSO problem even if the decay is exponential.

The main advantage of inertial methods is that they are able to provide rates such that 1 -q ≈ C √ κ which is much better when κ is close to 0. We will say that the exponential decay is slow if 1 -q ≈ Cκ and is fast if 1 -q ≈ C √ κ. In Theorems 7 and 9, we achieve a fast exponential decay for a suitable choice of parameters depending on the growth parameter µ. Hence, these last theorems ensure better decay rates under stronger assumptions than Theorems 6 and 8 and complete the analysis under growth conditions.

The paper is structured as follows: in Section 2 , the definitions and the links between all the classical geometrical hypotheses on functions F are presented. In Section 3, we present the state of the art and extensive results for the dynamical system [START_REF] Attouch | On the convergence of the proximal algorithm for nonsmooth functions involving analytic features[END_REF]. These results are extended to the associated differential inclusion. Section 4 is dedicated to the discrete scheme, and we propose here a new scheme that has the best convergence rate for minimizing non smooth convex functions satisfying a Lojasiewicz property. Section 5 presents some numerical experiments. Most of the proofs are postponed to Section 6.

Preliminaries: local geometry of convex functions

Let us first recall some basic notations and definitions. We assume that R n is equipped with the Euclidean scalar product •, • and the associated norm • . As usual B(x * , r) denotes the open Euclidean ball with center x * ∈ R n and radius r > 0. For any real subset X ⊂ R n , the Euclidean distance d is defined as:

∀x ∈ R n , d(x, X) = inf y∈X x -y .
If the function F : R n → R is differentiable, its gradient is denoted by ∇F (x). When F is assumed only convex, its (convex) subdifferential denoted by ∂F (x), is defined by:

∂F (x) = {s ∈ R n | ∀y ∈ R n , F (y) F (x) + s, y -x }.
We remind here that ∂F (x) is a closed convex set at any x ∈ int(dom(F )). If F is additionally proper lower semicontinuous then for all x ∈ int(dom(F )), its subdifferential ∂F (x) is also nonempty and bounded.

In this paper we consider the general class of convex functions having a Lojasiewicz property [START_REF] Lojasiewicz | Une propriété topologique des sous-ensembles analytiques réels[END_REF][START_REF] Lojasiewicz | Sur la géométrie semi-et sous-analytique[END_REF], a key tool in the mathematical analysis of continuous and discrete dynamical systems. Initially introduced to prove the convergence of the trajectories for the gradient flow of analytic functions, an extension to nonsmooth functions has been proposed by Bolte et al. in [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF][START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF]:

Definition 1 (The Lojasiewicz property for convex functions). Let F : R n → R ∪ {+∞} be a proper lower semicontinuous convex function with X * = argmin F = ∅. The function F has a Lojasiewicz property if for any minimizer x * , there exist θ ∈ [0, 1), c > 0, ε > 0 such that:

∀x ∈ B(x * , ε), c (F (x) -F (x * )) θ d(0, ∂F (x)), (5)
or equivalently if F satisfies a local growth condition i.e. if for any minimizer x * ∈ X * , there exist r 1 and µ > 0 such that

∃ε > 0, ∀x ∈ B(x * , ε), F (x) -F (x * ) µ 2 d(x, X * ) r . (6)
The equivalence between the Lojasiewicz property ( 5) and the local growth condition (6) has been proved in [START_REF] Bolte | Clarke subgradients of stratifiable functions[END_REF]Theorem 5]. More generally, for convex functions, a growth condition on an arbitrary set Ω ⊂ R n implies a Lojasiewicz property on Ω, but the equivalence is guaranteed only on ∂F -invariant sets, see [START_REF] Garrigos | Convergence of the forward-backward algorithm: Beyond the worst case with the help of geometry[END_REF]Proposition 3.2] for more details.

In this paper we consider a slightly stronger growth condition, namely a growth condition defined in the neighborhood of the set of minimizers as follows:

Definition 2 (Growth condition G r µ ). Let F : R n → R∪{+∞} be a proper lower semicontinuous convex function such that X * = argmin F = ∅. The function F satisfies the growth condition G r µ for some exponent r 1 and some real constant µ > 0 if there exists ε > 0 such that for all x ∈ R n , we have:

d(x, X * ) ε ⇒ µ 2 d(x, X * ) r F (x) -F * .
The condition G r µ is said to be global if for all x ∈ R n , we have:

F (x) -F * µ 2 d(x, X * ) r .
The growth condition G r µ can be seen as a sharpness assumption on the function F characterizing functions behaving at least as • r in the neighborhood of their minimizers. Note that G r µ implies the growth condition G r µ for all r > r 1. If F admits a unique minimizer, the growth condition G r µ is nothing more than the local growth condition [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF]. More generally, when the set X * of the minimizers is a compact set (which is guaranteed assuming for example F coercive), a straightforward extension of [4, Lemma 1] ensures that the local growth condition [START_REF] Attouch | Convergence rates of inertial forward-backward algorithms[END_REF] and the condition G r µ are actually equivalent. More precisely combining [START_REF] Garrigos | Convergence of the forward-backward algorithm: Beyond the worst case with the help of geometry[END_REF]Proposition 3.2] and [4, Lemma 1], we have: Lemma 1. Let F : R n → R ∪ {+∞} be a proper lower semicontinuous and coercive convex function satisfying a Lojasiewicz property, or equivalently some local growth condition. Then there exist r 1 and µ > 0 such that F satisfies the growth condition G r µ for some ε > 0 and has the Lojasiewicz property with the exponent θ = 1 -1 r on the set {x ∈ R n | d(x, X * ) ε} i.e.:

∀x ∈ R n , d(x, X * ) ε ⇒ c (F (x) -F (x * )) θ d(0, ∂F (x))
where c = r 2

∀x ∈ R n , d(0, ∂F (x)) 2 2µ (F (x) -F * ) .
Note that convex functions having a strong minimizer in the sense of [START_REF] Attouch | Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity[END_REF]Section 3.3], satisfy the PL µ property.

Let us now recall some state-of-the-art functional classes in the analysis of the Heavy Ball system: the set Q µ of quadratic functions, the classes S p,1 µ,L for p ∈ {1, 2}, of µ-strongly convex functions of class C p having a L-Lipschitz gradient and the class of just µ-strongly convex S µ . We will also refer to the class qS µ of µ-quasi-strongly convex functions introduced by I. Necoara et al. in [START_REF] Necoara | Linear convergence of first order methods for non-strongly convex optimization[END_REF]:

Definition 4 (Quasi-strong convexity [31, Definition 1]). A continuously differentiable function F : R n → R is µ-quasi-strongly convex if for any x ∈ R n : ∇F (x), x -x * F (x) -F (x * ) + µ 2 x -x * 2
where x * denotes the projection of x onto the set X * = argmin F = ∅.

The quasi-strong convexity is a relaxation of the strong convexity, but it does not imply the convexity of F or the uniqueness of the minimizer. However observe that the quasi-strong convexity of F implies that F satisfies the Polyak-Lojasiewicz property PL µ [START_REF] Necoara | Linear convergence of first order methods for non-strongly convex optimization[END_REF]:

Lemma 2. Let F : R n → R be a continuously differentiable function with X * = argmin F = ∅. If F is µ-strongly quasi-convex then F satisfies the Polyak-Lojasiewicz property PL µ .
All these sets of functions are sub-classes of functions satisfying a quadratic growth condition G 2 µ . The relations between them are extensively detailed in [START_REF] Necoara | Linear convergence of first order methods for non-strongly convex optimization[END_REF]Section 3] and can be summarized as follows: if F is a differentiable convex function admitting a unique minimizer then:

Q µ =⇒ S 2,1 µ,L =⇒ S 1,1 µ,L =⇒ S µ =⇒ qS µ =⇒ PL µ =⇒ G 2 µ . (7)
Note that the quadratic growth condition alone is not equivalent to the quasi-strong convexity. More information on the geometry of the function F to minimize, such as a global quadratic growth condition, is needed. For example we can prove that functions satisfying both a "flatness" assumption and a global quadratic growth condition G 2 µ (i.e. functions at least as flat as • γ with γ > 1, and as sharp as • 2 ) as in [START_REF] Sebbouh | Nesterov's acceleration and Polyak's heavy ball method in continuous time: convergence rate analysis under geometric conditions and perturbations[END_REF], are quasi-strongly convex: Lemma 3. Let F : R n → R be a convex continuously differentiable function with X * = argmin F = ∅ and F * = inf F . If F satisfies a flatness assumption:

∀x ∈ R n , F (x) -F * 1 γ ∇F (x), x -x * (8)
for some γ > 1 and the Polyak-Lojasiewicz property PL µ for some real constant µ > 0 then necessarily γ 2 and F is (γ -1)µ-quasi-strongly convex.

Proof. The proof is straightforward. Observe that combining the flatness assumption [START_REF] Attouch | Fast inertial dynamics and FISTA algorithms in convex optimization[END_REF] with the quadratic growth condition, we get:

∀x ∈ R n , ∇F (x), x -x * F (x) -F * + (γ -1) (F (x) -F * ) F (x) -F * + (γ -1) µ 2 d(x, X * ) 2 .
Finally we introduce the class G 2 µ,L of functions satisfying the growth condition G 2 µ and having a L-Lipschitz continuous gradient that will considered in the analysis of the discrete scheme in Section 4. Without further assumptions, G 2 µ,L is not a sub-class of quasi-strongly convex functions that are extensively considered in [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] for the analysis of the Heavy ball system. However assuming a little more, namely that F satisfies a global quadratic growth condition, we have: Lemma 2] Let F : R n → R be a convex continuously differentiable function with X * = argmin F = ∅. If F has a L-Lipschitz continuous gradient for some L > 0 and has the Polyak-Lojasiewicz property PL µ for some µ > 0 then F is µ 2 L -quasi-strongly convex.

Lemma 4. [12,

The Heavy Ball dynamical system

In his seminal work [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] B.T. Polyak studies the Heavy Ball dynamical system (4), the properties of its solutions and the rates of convergence of F (x(t)) -F * for functions belonging to the class S 2,1 µ,L of µ-strongly convex functions of class C 2 having a L-Lipschitz gradient. This first analysis is the key to analyze the convergence of the optimization scheme described in the same paper. More recently Su et al. [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF] show that the Nesterov acceleration scheme can be seen as a discretization of another ODE:

ẍ(t) + α t ẋ(t) + ∇F (x(t)) = 0. (9)
Following this approach a large amount of papers have proposed to study ODEs in different settings to provide some new properties or convergence rates of the existing algorithms, or even to provide new algorithms. An important point to keep in mind is that it is easy to find an ODE ensuring a fast decay of F (x(t)) -F * for any set of functions using time scaling for example. The difficulty in this joint study of ODE and algorithm is to be able to find a discrete and explicit scheme ensuring the same decay rate that the one reached in the continuous setting. To set some definitions we would say that: Definition 5. A dynamical system provides a fast exponential decay on a functional set F µ if there exists δ > 0 such that for any F ∈ F µ and any solution x of the associated ODE

F (x(t)) -F * = O(e -δ √ µt ). Set F µ References Optimal values Exponential rate of α of F (x(t)) -F * S 2,1 µ Polyak [38] 2 √ µ 2 √ µ S 1,
F (x(t)) -F * = O(e -δµt ).
It turns out that a good discretization of a dynamical system with a fast decay may provide a fast optimization algorithm. Table 1 summarizes the decays that are achieved for the Heavy ball system on various sets of functions. We can observe that on the classes S 2,1 µ , S 1,1 µ and qS µ with uniqueness of the minimizer, the given decays are fast exponential decays. In Polyak [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] and ADR [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] the exponential decays are also given for any α respectively on the classes S 2,1 µ and S 1,1 µ and the decays are proved to be optimal: [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] exhibits some functions for which these rates are reached.

Let us now consider the class of convex functions having a Lojasiewicz property. We first recall that the exponential decay of solutions of the Gradient Descend flow: ẋ(t) + ∇F (x(t)) = 0 [START_REF] Aujol | Optimal rate of convergence of an ODE associated to the fast gradient descent schemes for b > 0[END_REF] for convex functions in PL µ (i.e. having the Polyak-Lojasiewicz property) is straightforward.

Indeed defining E(t) = F (x(t)) -F * , we get E (t) = -∇F (x(t))

2

-2µ(F (x(t)) -F * ) ensuring that:

F (x(t)) -F * (F (x(t 0 )) -F * ) e -2µ(t-t0)
which is a slow exponential decay rate. These rates are actually exact for quadratic functions.

In Section 4 we will see that the associated discrete algorithms inherit of these fast or low rates and this difference partially explains the good behavior of inertial algorithms with respect to the steepest descent in large dimension problems for which µ is really small. For the Nesterov ODE (9), in [START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF] the authors prove that the decay rate for convex functions admitting a unique minimizer and satisfying a growth condition G 2 µ provides only a polynomial rate. For the Heavy Ball system, there are few results. For flat geometries i.e. for convex functions satisfying any local growth condition G r µ with r > 2, Bégout et al. in [START_REF] Bégout | On damped second order gradients systems[END_REF] prove the convergence of the trajectory to a minimizer x * of F at a polynomial rate provided that F is of class

C 2 : x(t) -x * = O t -1 r-2 . ( 11
)
Without further information on the local geometry of F around its set of minimizers, applying [START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF]Lemma 2.2] to γ = 1 (which corresponds to the sole convexity assumption), this implies the same polynomial decay on the values F (x(t)) -F * . If F behaves like x r , with r > 2 around its set of minimizers, the convergence rate provided by [START_REF] Bégout | On damped second order gradients systems[END_REF] is more accurately in O t -r r-2 . For sharp geometries i.e. for convex functions satisfying some quadratic growth condition G 2 µ , or equivalently having a Lojasiewicz property with an exponent 1 2 , Bégout et al. in [START_REF] Bégout | On damped second order gradients systems[END_REF] and Polyak et al. [START_REF] Polyak | Lyapunov functions: An optimization theory perspective[END_REF] respectively prove that the decay is exponential when F is of class C 2 . In [START_REF] Polyak | Lyapunov functions: An optimization theory perspective[END_REF] the exact decay is not given but our computations indicate slow exponential rates in these two approaches. However note that these two approaches do not assume the uniqueness of the minimizer of F . The main contribution of this part is Theorem 1 stating that the Heavy Ball ODE ensures a fast decay rate on the set of differentiable convex functions satisfying a quadratic growth condition G 2 µ and having a unique minimizer. We also prove that these decays are preserved for the perturbed Heavy Ball ODE assuming sufficient integrability conditions on the perturbation. Moreover, it should be noticed that the optimal value of α is still different from the previous ones. One can observe in the Figure 1 that the optimal value of parameter α in the Heavy Ball Figure 1: Decay rates that can be achieved depending on the geometrical hypotheses made on F for µ = 1 the parameter of the growth condition. The stronger the regularity assumption, the better the rate. The optimal value of α depends on the regularity assumption. ODE [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] depends on the exact hypothesis made of F . The exponential rate is lower under growth conditions than under strong convexity or quasi-strong convexity assumptions, which is not surprising since this hypothesis is weaker than the other ones.

The differentiable case

Let F : R n → R be a continuously differentiable convex function having a unique minimizer x * and F * = inf F . We consider the Heavy Ball dynamical system:

ẍ(t) + α ẋ(t) + ∇F (x(t)) = 0 ( 12
)
for any t t 0 , where t 0 > 0. Throughout the paper, we assume that, for any given initial conditions (x 0 , v 0 ) ∈ R n × R n , the Cauchy problem associated with the ODE [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF], admits a unique global solution satisfying (x(0), ẋ(0)) = (x 0 , v 0 ). This is guaranteed in particular when the gradient of F is Lipschitz on bounded subsets of R n [START_REF] Cabot | On the long time behavior of second order differential equations with asymptotically small dissipation[END_REF].

We can now state the main theorem for the Heavy Ball ODE [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] whose proof is detailed in Section 6.1. Note that to analyze the asymptotic behavior of F (x(t)) -F * , we only need local geometric assumptions on F since the trajectory x converges to some minimizer of F provided that F is a convex function of class C 1 admitting at least one minimizer and that the ODE [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] has a unique global solution, see [START_REF] Alvarez | On the minimizing property of a second order dissipative system in hilbert spaces[END_REF]Theorem 2.1] for more details: Theorem 1. Let α > 0 and t 0 > 0. Let F : R n → R be a differentiable convex function such that: X * = argmin F = ∅ and F * = inf F . Let x be the solution of the ODE [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] for given initial conditions (x(t 0 ), ẋ(t 0 )) = (x 0 , v 0 ).

If F satisfies a quadratic growth condition G 2 µ for some real constant µ > 0 and admits a unique minimizer then

F (x(t)) -F * = O e -δα,µt
where δ α,µ is the (unique) real root of the polynomial:

P α,µ (δ) = δ 3 -3αδ 2 + (3µ + 2α 2 )δ -2µα on the interval [0, 2α 3 [. In particular: δ α,µ (2 - √ 2)
√ µ and the best rate

δ α,µ = (2 - √ 2) √ µ is achieved for α = (2 - √ 2
2 ) √ µ.

Now assuming that the quadratic growth condition is global, we also get non-asymptotic convergence rates for this class of functions: Corollary 1. Under the assumptions of Theorem 1, if F satisfies a global quadratic growth condition G 2 µ and admits a unique minimizer then for any δ δ α,µ , we have:

∀t t 0 , F (x(t)) -F * 4µ + (2α -δ + 2 √ µ) 2 µ(4 -αδ + δ 2 ) M 0 e -δ(t-t0)
where:

M 0 = F (x 0 ) -F * + 1 2 v 0 2 . If α = (2 - √ 2
2 ) √ µ, the best rate is given by:

F (x(t)) -F * ( 11 2 -2 √ 2)M 0 e -(2- √ 2) √ µ(t-t0) . (13)
Remark 1. Using the open-source Python library Sympy for symbolic mathematics, we are able to provide some explicit equivalents of the real root δ α,µ . For a fixed µ > 0, we have:

δ α,µ ∼ 2α 3 , α → 0 + , δ α,µ ∼ µ α , α → +∞.
Moreover studying the variations of the polynomial P α,µ we deduce a criterion to easily compare a given exponent δ ∈ [0, 2α 3 [ with the best possible rate δ α,µ :

δ δ α,µ ⇐⇒ P α,µ (δ) 0. ( 14
)
Remark 2. Using the Python library Sympy, we actually have an explicit (but barely readable) expression of δ α,µ . For α large enough (numerically larger than 0.15µ 2 ), we have:

δ α,µ = µ - 18
1 3 3 µ 2 -3α d(α, µ) - 12
1 3 6 d(α, µ)
where:

d(α, µ) = 9αµ + √ 3 108α 3 -81α 2 µ 2 + 36µ 4 α -4µ 6 1 3 .
Otherwise for small values of α, we have:

δ α,µ = α - 18
1 3 3 α 2 -3µ d(µ, α) - 12
1 3 6 d(µ, α).
To our best knowledge the only other result in the literature providing a fast exponential decay for the values F (x(t)) -F * can be found in [START_REF] Sebbouh | Nesterov's acceleration and Polyak's heavy ball method in continuous time: convergence rate analysis under geometric conditions and perturbations[END_REF]. Indeed, applying [START_REF] Sebbouh | Nesterov's acceleration and Polyak's heavy ball method in continuous time: convergence rate analysis under geometric conditions and perturbations[END_REF]Theorem 3.2] with K 2 = 2µ and γ = 1 (corresponding to the sole convexity assumption), we get an exponential

decay in O e -µ 2α provided that α 3 2
√ µ, which can be seen as a fast exponential decay when α is chosen proportional to √ µ as in Theorem 1. Since P α,µ ( µ 2α ) 0, we easily show that this rate is always worse than the one provided by Theorem 1.

Consider now the subclass G r µ with r ∈ (1, 2) of differentiable convex functions being sharper than quadratic in the neighborhood of its minimizers. Since G r µ is a sub-class of G 2 µ , Theorem 1 applies and we deduce that the exponent in the exponential decay is at least in δ α,µ . A natural question is then: can this convergence rate be improved for this class of functions ? In [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF], the authors prove that the exponent 2α 3 is optimal on the sub-class S µ of strongly convex functions when α < 3 µ 2 . In fact, we can prove that the exponential decay is at least in 2α 3 for any α > 0 on the sub-class G r µ with r ∈ (1, 2), providing thus an upper bound for the convergence rate: Proposition 1. Let F : R n → R be a continuously differentiable convex function with X * = argmin F = ∅ and F * = inf F . Let α > 0 and t 0 > 0. Let x be the solution of the ODE (12) for given initial conditions (x(t 0 ), ẋ(t 0 )) = (x 0 , v 0 ).

Let r ∈ (1, 2). If F admits a unique minimizer and satisfies a local growth condition G r µ for some µ > 0 then:

∀λ < 2α 3 , F (x(t)) -F * = O e -λt .
Proof. Let us consider the Lyapunov energy:

E(t) = (F (x(t)) -F * ) + 1 2 λ(x(t) -x * ) + ẋ(t) 2 + ξ 2 x(t) -x * 2 . ( 15
)
Differentiating the energy (15) and using the ODE ( 12), we have:

E (t) = ∇F (x(t)) + ẍ(t), ẋ(t) + (λ 2 + ξ) x(t) -x * , ẋ(t) + λ x(t) -x * , ẍ(t) + λ ẋ(t) 2 = -λ ∇F (x(t)), x(t) -x * + (λ -α) ẋ(t) 2 + (ξ + λ(λ -α)) ẋ(t), x(t) -x *
Using the parameters λ = 2α 3 and ξ = -2α 2 9 we have the following equality (the careful reader will have noticed that the parameters of the Lyapunov function are not the same as the ones used in Theorem 1):

∀t t 0 , E (t) + 2α 3 E(t) = 2α 3 27 x(t) -x * 2 + 2α 3 [F (x(t)) -F * -∇F (x(t)), x(t) -x * ] (16) It follows that if F is convex we get ∀t t 0 , E (t) + 2α 3 E(t) 2α 3 27 x(t) -x * 2 .
Observe that using the growth condition G r µ with r ∈ (1, 2), there exists t 1 t 0 such that:

∀t t 1 , E(t) F (x(t)) -F * + ξ 2 x(t) -x * 2 µ 2 x(t) -x * r - α 2 9 x(t) -x * 2 .
Let ∈ (0, 2α 3 ). Then:

∀t t 1 , E (t) + ( 2α 3 -)E(t) 2α 3 27 + α 2 9 x(t) -x * 2 - µ 2 x(t) -x * r ( 2α 3 27 + α 2 9 ) x(t) -x * 2-r - µ 2 x(t) -x * r .
We can then conclude that there exists t 2 > t 1 such that for all t t 2 , we have:

∀ ∈ (0, 2α 3 ), E (t) + ( 2α 3 -)E(t) 0, hence: ∀λ < 2α 3 , E(t) = O e -λt .
To deduce the control on the values F (x(t)) -F * we use the growth condition G r µ :

∀t t 2 , E(t) F (x(t)) -F * + ξ 2 x(t) -x * 2 = F (x(t)) -F * - 2α 2 9 x(t) -x * 2 1 - 4α 2 9µ x(t) -x * 2-r (F (x(t)) -F * ) 1 2 (F (x(t)) -F * ) ( 17
)
for t large enough, and we finally obtain the expected convergence rate.

Remark 3. Consider the particular case of convex functions behaving like F (x) = µ 2 x r with r ∈ (1, 2) in the neighborhood of their minimizers. Then F naturally satisfies the growth condition G r µ , or equivalently a Lojasiewicz property with an exponent θ = 1 -1 r . By a strategy similar to the one used in Proposition 1 with the set of parameters of Theorem 1, and replacing the convexity inequality by the equality: ∇F (x), x -x * = r(F (x) -F * ), we can prove that the decay is even better than 2α 3 , namely:

∀λ < 2rα r + 2 , F (x(t)) -F * = O e -λt . (18)
Let us conclude this section by a stability study of the Heavy Ball dynamical system. We consider the perturbed version of the Heavy Ball ODE:

∀t t 0 , ẍ(t) + α ẋ(t) + ∇F (x(t)) = g(t) (19)
where t 0 > 0 and g : [t 0 , +∞[ is an integrable source term that can be interpreted as an external perturbation exerted on the system. We assume that the Cauchy problem associated with the ODE [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF], admits a unique global solution satisfying (x(0), ẋ(0)) = (x 0 , v 0 ) for any given initial conditions (x 0 , v 0 ) ∈ R n ×R n . This is guaranteed in particular when the gradient of F is Lipschitz on bounded subsets of R n [START_REF] Haraux | On a second order dissipative ODE in Hilbert space with an integrable source term[END_REF][START_REF] Jendoubi | Asymptotics for a second-order differential equation with nonautonomous damping and an integrable source term[END_REF].

Theorem 2 provides sufficient integrability conditions on the perturbation g in order to guarantee that the convergence rate established in Theorem 1 is preserved. Note that as in the unperturbed case, the trajectory x(t) solution of the perturbed ODE [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF] converges (weakly in a Hilbert space) to a minimizer of F , see [START_REF] Haraux | On a second order dissipative ODE in Hilbert space with an integrable source term[END_REF]Theorem 3.3], so that we only need local geometric assumptions on F to analyze the asymptotic behavior of F (x(t)) -F * : Theorem 2. Let F : R n → R be a continuously differentiable convex function with X * = argmin F = ∅ and F * = inf F . Let α > 0 and t 0 > 0. Let x be the solution of the ODE (19) for given initial conditions (x(t 0 ), ẋ(t 0 )) = (x 0 , v 0 ).

Assume that F satisfies a quadratic growth condition G 2 µ for some real constant µ > 0 and admits a unique minimizer. Let δ α,µ be defined as in Theorem 1 and δ δ α,µ . If:

J 0 = +∞ t0 e δt g(t) dt < +∞, then: F (x(t)) -F * = O e -δ(t-t0) .
As in the unperturbed case, assuming that F additionally satisfies a global quadratic condition G 2 µ , we can provide non-asymptotic bounds on the values F (x(t)) -F * :

Corollary 2. Under the hypotheses of Theorem 2, if F additionally satisfies a global quadratic condition G 2 µ then for any δ δ α,µ , we have:

∀t t 0 , F (x(t)) -F * 4 E 0 (δ) + ( 2E 0 (δ) + I 0 )J 0 e -δt0 4 -αδ + δ 2 M 0 e -δ(t-t0)
where:

M 0 = F (x 0 ) -F * + 1 2 v 0 2 , I 0 = +∞ t0 g(s) ds, E 0 (δ) = M 0 + ( √ 2M 0 + I 0 )I 0 + √ M 0 + I0 √ 2 + 2α-δ 2 √ µ M 0 + ( √ 2M 0 + I 0 )I 0 2 .

The non-differentiable case

Assume now that F is a convex but non differentiable function. In that case, the Heavy Ball ODE [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] has no meaning anymore but we can consider the following differential inclusion:

0 ∈ ẍ(t) + α ẋ(t) + ∂F (x(t)). ( 20
)
To study some optimization algorithms dedicated to non smooth functions, it may be useful to understand the behavior of solutions of [START_REF] Brezis | Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert[END_REF]. This is the case for instance for the LASSO problem (3), for which proximal algorithms such as the Forward Backward (or its accelerated version FISTA) can be used. It was shown in [START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF] that the behavior of FISTA is linked with the behavior of solutions of 0 ∈ ẍ(t) + α t ẋ(t) + ∂F (x(t)).

It turns out that FISTA is not the only inertial algorithm that can be used to minimize the LASSO problem or any non smooth optimization problem. It is shown in [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] that a variant of the Heavy Ball algorithm can be used in the case when F is strongly convex or quasi-strongly convex, and the optimal value of the friction parameter α is given.

If F is less regular, but if it still satisfies a growth condition (i.e. if F is in G 2 µ ), it may be interesting to understand how the Heavy Ball algorithm can be used, and how to choose the parameter α. Actually, we will see in the part dedicated to the optimization scheme that the previous analysis applies to this case.

Solutions of the differential inclusion

The differential inclusion problem (20) admits a shock solution [START_REF] Paoli | An existence result for vibrations with unilateral constraints: case of a nonsmooth set of constraints[END_REF][START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF] and it is known [START_REF] Attouch | The dynamics of elastic shocks via epigraphical regularization of a differential inclusion. Barrier and penalty approximations[END_REF][START_REF] Cabot | Asymptotics for some vibro-impact problems with a linear dissipation term[END_REF] that for any solution x of (20), F (x(t)) -F * converges to 0 for any α > 0. Most of known convergence rates of F (x(t)) -F * are consequences of a Lyapunov analysis. An energy E is defined and it is shown to be a non increasing function of t. To prove that E is non increasing, the simplest way is to compute the derivative E of E. To study solutions of (20), we use exactly the same energy defined to study the Heavy Ball ODE:

E λ,ξ (t) = F (x(t)) -F * + 1 2 λ(x(t) -x * ) + ẋ(t) 2 + ξ 2 2 x(t) -x * 2 . ( 22
)
This time these Lyapunov energies may not be differentiable. Fortunately, the shock solutions [START_REF] Paoli | An existence result for vibrations with unilateral constraints: case of a nonsmooth set of constraints[END_REF][START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF] of the differential inclusion (20) are obtained as limit of C 2 functions, where the subdifferential ∂F is replaced by its Moreau Yosida approximation [START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF].

Let us recall the definition of shock solution for the differential inclusion (20):

Definition 7 (Shock solution [START_REF] Paoli | An existence result for vibrations with unilateral constraints: case of a nonsmooth set of constraints[END_REF][START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF]). A function x : [t 0 , +∞) -→ R n is an energy-conserving shock solution of the differential inclusion (20) if:

1. x ∈ C 0,1 ([t 0 , T ]; R n ) for all T > t 0 , i.e.
x is a Lipschitz continuous function.

2. ẋ ∈ BV ([t 0 , T ]; R n ) for all T > t 0 . 3. x(t) ∈ dom(F ) for all t ≥ t 0 . 4. For all φ ∈ C 1 c ([t 0 , +∞), R + ) and v ∈ C([t 0 , +∞), dom(F )), it holds: T t0 (F (x(t)) -F (v(t)))φ(t)dt ≤ ẍ + α ẋ, (v -x)φ M×C .

5.

x satisfies the following energy equation for a.e. t ≥ t 0

F (x(t)) -F (x 0 ) + 1 2 ẋ(t) 2 - 1 2 v 0 2 + t t0 α ẋ(s) 2 ds = 0.
We then consider the Moreau-Yosida approximations {F γ } γ>0 of F defined by:

F γ (x) = min y F (y) + 1 2γ x -y 2 (23)
and the following approximating ODE:

ẍγ (t) + α ẋγ (t) + ∇F γ (x γ (t)) = 0 x γ (t 0 ) = x 0 ẋγ (t 0 ) = v 0 . ( 24
)
The differential equation ( 24) falls into the classical theory of differential equations and admits a unique solution x γ of class C 2 on [t 0 , +∞) for all γ > 0. More precisely, using [3, Theorems 3.2 and 3.3], we have the following result:

Theorem 3. Assume F to be a lower semi continuous convex function. Let {F γ } γ>0 the Moreau-Yosida approximations of F . There exists a subsequence {x γ } γ>0 of solutions of (24) that converges to a shock solution of (20) according to the following scheme:

• x γ -→ γ→0 x uniformly on [t 0 , T ] for all T > t 0 . • ẋγ -→ γ→0 ẋ in L p ([t 0 , T ]; R n ) , for all p ∈ [1, +∞) and T > t 0 . • F γ (x γ ) -→ γ→0 F (x) in L p ([t 0 , T ]; R n ), for all ∀p ∈ [1, +∞) and T > t 0 . (25)
From Corollary 3.6 of [START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF], we also have:

Corollary 3. If dom(F ) = R n
, then the differential inclusion (20) admits a shock solution x , such that:

x ∈ W 2,∞ ((t 0 , T ); R n ) ∩ C 1 ([t 0 , +∞); R n ), for all T > t 0 .
It turns out that all the results shown for the Heavy ball ODE remain valid for the differential inclusion [START_REF] Brezis | Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert[END_REF]. Indeed, the approximated solutions x γ of Theorem 3 are solutions of the Heavy ball ODE and they thus satisfy all the previous properties. By passing to the limit γ → 0 + , the shock solutions of (20) also satisfies these properties (see e.g. [START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF] for more details).

We do not restate all the Theorems of the previous section for the differential inclusion case. However, we state a result for a particular case of interest, the LASSO problem recalled here:

min x∈R n 1 2 Ax -b 2 + β x 1 (26)
Let

F (x) = 1 2 Ax -b 2 + β x 1 .
As shown in [19, Lemma 10], the function F satisfies a quadratic growth condition, or equivalently has the Lojasiewicz property with an exponent θ = 1 2 , on some 1 ball. Corollary 4. If the LASSO problem (26) admits a unique minimizer, even if Ker(A) = {0}, there is a solution of the differential inclusion [START_REF] Brezis | Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert[END_REF] such that the conclusions of Theorem 1 hold.

Optimality of the decays

In Proposition 1, we have shown that if F is at least as sharp as • r for some r ∈ (1, 2), then

∀λ < 2α 3 , F (x(t)) -F * = O e -λt .
In Theorem 4 whose proof is detailed in Subsection 6.3, it is proven that a better exponential decay than 2α 3 is unreachable for the solution of ( 20) under the quadratic growth condition G 2 µ , proving that in some sense this decay is reached for the function F (x) = |x| for any α > 0.

Theorem 4. If F (x) = |x| then for all α > 0 then all solutions of (20) satisfy:

F (x(t)) -F * = O e -2α 3 t
and this decay is optimal: lim sup t t0 e 2α 3 t (F (x(t)) -F * ) > 0.

Optimization scheme

In this section we introduce an inertial scheme to minimize a convex differentiable function F whose gradient is L-Lipschitz continuous, and satisfying any Lojasiewicz property. In a second time, this scheme is extended to a sum of two convex functions F = f + h using an inertial proximal gradient algorithm. Both schemes can be seen as discretizations of the Heavy Ball ODE and they are variations of the schemes proposed by B.T. Polyak [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF], Y. Nesterov [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o( 1 k 2 )[END_REF] and J.W. Siegel [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF].

If F is a convex differentiable function satisfying G 2 µ and whose gradient is L-Lipschitz, then the steepest descent algorithm defined by

x n+1 = x n - β L ∇F (x n ), with β ∈ (1, 2) (27)
ensures an exponential decay:

F (x n ) -F (x * ) = O(q n ) (28) Hyp. on F References Values of q Remarks S 2,1 µ,L Polyak [38] 1- √ κ 1+ √ k 2
Local convergence and optimal rate on S 2,1 µ,L , may diverge on S 1,1 where q = 1 -κ and κ := µ L the conditioning number. If F = f + h, where f is a convex differentiable function whose gradient is L-Lipschitz, and h is convex, the Forward-Backward algorithm uses the proximal operator of h prox sh (z) = argmin

µ,L S 1,1 µ,L Nesterov [32] 1 - √ κ + O(κ) Global convergence S 1,1 µ,L GFJ [24] 1 -κ Global convergence S 2,1 µ,L SFL [44] 1 -2 √ κ + O(κ) Global convergence, three points method S 1,1 µ,L Siegel [41] 1 - √ κ Global convergence, can be extended to non differentiable functions qS 1,1 µ,L ADR[12] 1 -(2 -ε)κ + O(κ) Global convergence,
x∈R n h(x) + 1 2s x -z 2 ( 29
)
and it is defined by the following operator T

T (x) := prox 1 L h (x - 1 L ∇f (x)), x n+1 = T x n . (30)
If F satisfies G 2 µ , the sequence generated by the Forward Backward algorithm ensures an exponential decay with 1 -q = κ. If κ << 1 this exponential decay may be slow. In [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF] Bolte et al. proved that for the LASSO problem [START_REF] Hiriart-Urruty | Fundamentals of convex analysis[END_REF] the function F satisfies the PL µ property and thus the growth condition G 2 µ . It turns out that the decay is so slow that FISTA [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] which only ensures a O( 1 n 2 ) decay, is better in practice for many large scale problems. The question arising is then: can we provide a fast exponential decay that is

F (x n ) -F * = O(q n ) with 1 -q ≈ C
√ κ for such functions ? Namely, for a single differentiable function F belonging to G 2 µ or a composite function F = f + h where only f is differentiable ? If F is µ-strongly convex, it has been proved that such rates can be achieved as summarized in Table 2. But all these results do not apply directly to the set G 2 µ since we do not have the strong convexity assumption. Nevertheless observe that from Lemma 4, if F ∈ G 2 µ is differentiable with L-Lipschitz gradient, then F is also µ 2 L -quasi strongly convex. Hence applying the rates from the Table 2, we do not reach any fast exponential decay that is with 1 -q = C √ κ where κ = µ L with µ the parameter of growth. Moreover, only Siegel [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF] and ADR [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] proposed an extension to the non differentiable case and both approaches necessitate the strong convexity of the differentiable part which is a real bottleneck. Indeed the strong convexity hypothesis of the differentiable part is a really strong hypothesis, much more than the G 2 µ property and the uniqueness of the minimizer.

Consider now the LASSO problem [START_REF] Hiriart-Urruty | Fundamentals of convex analysis[END_REF]. The strong convexity of the differentiable part implies that Ker(A) = {0}. If Ker(A) = {0} the LASSO problem may have an infinite set of solutions but it is not the generic case. Indeed for a generic linear operator A, the LASSO problem (26) admits a unique minimizer (see for example Lemma 3 in [START_REF] Tibshirani | The lasso problem and uniqueness[END_REF] for the exact definition of genericity and more detailed results). This means that except for a very specific choice of A, the LASSO problem (26) admits a unique minimizer.

To summarize, none of the previous analysis applies to the LASSO problem (26) for a generic matrix A and none of them ensures an exponential decay such that q = 1 -C µ L where µ is the growth parameter for any function F ∈ G 2 µ . In [START_REF] O'donoghue | Adaptive restart for accelerated gradient schemes[END_REF], the authors observe that a restarted FISTA algorithm provides a fast exponential decay if S 1,1 µ,L . Actually this result is also available for functions satisfying a growth condition, as remarked in [START_REF] Necoara | Linear convergence of first order methods for non-strongly convex optimization[END_REF]:

Theorem 5. If F is a convex differentiable function whose gradient is L-Lipschitz and if F ∈ G 2 µ then the sequence (x n ) n∈N generated by FISTA with a restart each k * = E 2e √ κ satisfies F (x n ) -F * = O 1 - √ κ e n . (31)
One can notice that FISTA applies to composite functions and that there is no need of uniqueness of the minimizer of F to get this fast rate. Restarted FISTA is thus a relevant algorithm to minimize such functions. One can also notice that even if the inertial parameter does not depend on µ, the starting rule depends on κ. If µ is overestimated, then the proof of convergence does not hold any more.

Another natural question with respect to the Table 2 is the behavior of each algorithm when the growth constant µ is not known. Indeed, the rates given in Table 2 are related to the choice of parameters in the algorithm that depends on µ. It is always possible to underestimate µ but at the cost of a loss of speed (the more µ is underestimated, the slower the algorithm). With non adequate parameters, some of the algorithms mentioned in Table 2 may even diverge.

In this section we propose a new algorithm (41) with a better exponential decay based on the previous analysis of the Heavy Ball ODE (4). Firstly on differentiable functions and in a second time on composite functions, see Theorems 7 and 9. This last algorithm allows to solve the LASSO problem with a fast exponential rate for generic matrix A.

It turns out that the algorithm (41) can be seen as a specific case of a more general algorithm [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] whose parameters do not depend on µ. We can show (see Theorems 6 and 8) that in fact such a scheme converges under very weak assumptions: it suffices that the function F to minimize belongs to G r µ and has a L-Lipschitz gradient. And a (slow) geometrical decay is reached as soon as F satisfies any Lojasiewicz property.

The Differentiable case

Several algorithms to minimize strongly convex functions of S 1,1 µ,L or S 2,1 µ,L are inspired by the Heavy Ball ODE in the unperturbed continuous case:

ẍ(t) + α ẋ(t) + ∇F (x(t)) = 0. ( 32
)
rewritten as the following first order differential system:

ẋ(t) = v(t) v(t) = -αv(t) -∇F (x(t)). ( 33
)
The first one was proposed by Polyak in [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] for functions in S 2,1 µ,L :

     x n+ 1 2 = x n + 1 - √ κ 1 + √ κ 2 (x n -x n-1 ) x n+1 = x n+ 1 2 -s 2 ∇F (x n ) ( 34
)
with s = 2 √ L+ √ µ , which can be seen as a discretization of the Heavy Ball ODE for α = 2 √ µ.

This algorithm is efficient for functions in S 2,1 µ,L but it may diverge for some functions in S 1,1 µ,L , see Ghadimi et al. [START_REF] Ghadimi | Global convergence of the heavyball method for convex optimization[END_REF] for example. It is worth mentioning that Ghadimi et al. in [START_REF] Ghadimi | Global convergence of the heavyball method for convex optimization[END_REF]Theorem 4] proved the linear convergence of such a scheme for functions F in S 1,1 µ,L changing the step and the inertia, but the rate in this case is

F (x n ) -F * = O((1 -κ) n ) ( 35
)
that is the best rate that can be achieved of the gradient descent on S 1,1 µ,L . As we will see further, this decay is much worse than the ones that can be achieved using other schemes for small κ since for small κ, κ << √ κ. In his book [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF], Nesterov proposes a scheme which is quite similar:

     x n+ 1 2 = x n + 1 - √ κ 1 + √ κ (x n -x n-1 ) x n+1 = x n+ 1 2 -s 2 ∇F (x n+ 1 2 ) (36)
with s = 1 √ L . This scheme can also be seen as a discretization of the Heavy Ball ODE with α = 2 √ µ, but the descent step s 2 is about four times lower. Nesterov proves the convergence of the scheme [START_REF] O'donoghue | Adaptive restart for accelerated gradient schemes[END_REF] for functions in S 1,1 µ,L and he gives a convergence rate:

F (x n ) -F * = O((1 - √ κ) n ). ( 37
)
Notice that another variant of this algorithm with the same asymptotic decrease rate was also introduced by Y. Nesterov in [START_REF] Nesterov | Gradient methods for minimizing composite objective function. core discussion papers 2007076[END_REF] with an extension to non differentiable functions (but still strongly convex). An application of this last scheme to image processing can be found in [START_REF] Aujol | Some first-order algorithms for total variation based image restoration[END_REF].

Convergence of the scheme

In this paper, we consider the following general scheme:

         x n+ 1 2 = x n + sv n v n+ 1 2 = (1 + γλs) -1 (v n -s∇F (x n+ 1 2 )) x n+1 = x n+ 1 2 -s 2 ∇F (x n+ 1 2 ) v n+1 = v n+ 1 2 + (1 + λs) -1 λs 2 ∇F (x n+ 1 2 ) ( 38
)
with γ > 0 and s = 1 √ L . Theorem 6. Let F be a convex differentiable function having a L-Lipschitz gradient. Let s = 1 √ L . If γλ 2 < L then the following assertions hold:

1. The sequences (∇F (x n )) n∈N and (v n ) n∈N generated by the scheme [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF], converge to 0 when n → +∞.

2. If F is coercive then the sequences (F (x n ) -F * ) n∈N and (d(x n , X * )) n∈N converge to 0.

3. Assume that F is coercive and has some Lojasiewicz property with an exponent θ ∈ (0, 1).

(a) If θ = 1 2 i.e if F satisfies some local quadratic growth condition G 2 µ , then the values (F (x n ) -F * ) n∈N decay exponentially to 0 and the iterates (x n ) n∈N converge to a minimizer x * of F . More precisely for any ε ∈ (0, 1), if γ = (1 -ε) L 2 λ 2 , there exists λ ε > 0 such that for all λ ∈ (0, λ ε ) then:

F (x n ) -F * = O 1 + µ L -ε µ L + λ √ L -n . ( 39
) (b) If θ ∈ ( 1 2 , 1) then F (x n ) -F (x * ) = O 1 n 1 2θ-1 . ( 40
)
Moreover, if θ < 3 4 , then the sequence (x n ) n∈N converges to a minimizer x * of F and the length of the trajectory is finite.

The proof of the Theorem is detailed in Subsection 6.4.

Improved rates of convergence

In this paper, we promote the use of the following particular scheme (where the product γλ is now fixed to be the friction parameter α):

         x n+ 1 2 = x n + sv n v n+ 1 2 = (1 + αs) -1 (v n -s∇F (x n+ 1 2 )) x n+1 = x n+ 1 2 -s 2 ∇F (x n+ 1 2 ) v n+1 = v n+ 1 2 + (1 + λs) -1 λs 2 ∇F (x n+ 1 2 ) (41)
with s = 1 √ L . Notice that it has the same general form as the one that we introduced in [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF]. The difference with respect to the scheme of [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] will be in the choice of the parameters α and λ of the scheme. This comes from the fact that the analysis in the continuous setting has led us to different parameters in the Lyapunov function, and we now use these values in the discrete scheme. Since the parameters are different, the proof of of convergence of the new scheme here is different from the one of [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF]. In [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF], we used α = 2λ 3 to get a new optimal scheme for strongly convex functions. In this paper, inspired by the analysis in the continuous case detailed in Section 3, we use:

α = 2 - √ 2 2 √ µ, λ = √ µ and ξ = √ 2 2 -1 µ. ( 42
) Let β = 2 - √ 2
2 . We will use the following discrete Lyapunov function:

L(x n , v n ) := F (x n ) -F * + 1 2 λ(x n -x * ) + (1 + λs)v n 2 -(β -1) λ 2 2 x n -x * 2 . ( 43
)
The careful reader can check that the sequence (v n ) n∈N is a discretization of the variable v = ẋ in [START_REF] Nesterov | Gradient methods for minimizing composite objective function. core discussion papers 2007076[END_REF]. Indeed, if using explicit Euler schemes to discretize [START_REF] Nesterov | Gradient methods for minimizing composite objective function. core discussion papers 2007076[END_REF], one gets the two first lines of [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF]. The third line corresponds to a classical contraction step on x n that makes the objective function F decrease by a factor 1 2L ∇F (x n+ 1 2 ) 2 (this is the same argument that is used to prove the convergence of the explicit gradient descent scheme to minimize a differentiable function with L-Lipschitz gradient), and the fourth line keeps the middle term of the Lyapunov function [START_REF] Tibshirani | The lasso problem and uniqueness[END_REF] constant.

From [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF], we can write v n+1 as a function of v n :

v n+1 -v n s = - α 1 + αs v n - 1 -αλs 2 (1 + αs)(1 + λs) ∇F (x n+ 1 2 ). ( 44
)
We then see that ( 41) is indeed a discretization of [START_REF] Nesterov | Gradient methods for minimizing composite objective function. core discussion papers 2007076[END_REF].

The interest of the new scheme [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF] is that it allows to provide a better decay rate of F (x n ) -F * that is asymptotically better than the previous ones under similar assumptions: Theorem 7. Assume that F is convex differentiable function with a L-Lipschitz gradient, admitting a unique minimizer and satisfying some quadratic growth condition

G 2 µ . If we choose α = 2 -2 √ 2
√ µ and λ = √ µ in (41), then there exist t > 0 and K > 0 such that if µ L ∈ [0, t], then the sequence (x n ) n∈N provided by [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF]

with s = 1 √ L satisfies: F (x n ) -F * K 0 1 + 2 - √ 2 µ L -K µ L -n
.

More precisely, remembering that κ = µ L , the new scheme [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF] allows to get the following rate:

F (x n ) -F * = O (1 + (2 - √ 2) √ κ -Kκ) -n . (45)
Notice that we have

(1 + (2 - √ 2) √ κ -Kκ) -1 = 1 -(2 - √ 2) √ κ + o( √ κ). (46)
The only other result under similar assumptions (quadratic growth) is the Nesterov restart algorithm of [START_REF] Necoara | Linear convergence of first order methods for non-strongly convex optimization[END_REF] (see Theorem 5), but we can see that we have a better convergence rate with Theorem 7 since 2 -√ 2 > 1 e . As far as we know, Theorem 7 gives the best convergence rate in the literature when the function F to minimize satisfies G 2 µ , has a L-Lipschitz gradient, and has a unique minimizer.

Discrete scheme in the non differentiable case

In many practical problems especially coming from statistics or image processing the function F to minimize is not differentiable. A classical case is the LASSO problem

F (x) = 1 2 Ax -y 2 + λ x 1 ( 47
)
where A is a linear operator. To study the minimisation of such functions, convex but not differentiable, we cannot consider a differential equation involving F . Nevertheless we can consider the following monotone inclusion:

0 ∈ ẍ(t) + α ẋ(t) + ∂F (x(t)). ( 48
)
This inclusion problem admits a shock solution (see [START_REF] Apidopoulos | The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b 3[END_REF] and [START_REF] Paoli | An existence result for vibrations with unilateral constraints: case of a nonsmooth set of constraints[END_REF]) and F (x(t)) -F * tends to 0.

When F = f + h, with f differentiable, ∇f is L-Lipschitz and h is convex proper and lower semi continuous, Siegel in [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF] proposed an extension of the discrete scheme built for differentiable functions. In the same spirit we can prove that our scheme can be directly extended to such composite functions using the Forward-Backward algorithm, also called Proximal Gradient Operator.

Let us first recall the definition of the proximal operator for the convex semicontinuous function h:

prox h (x) = argmin y∈R n h(y) + 1 2 y -x 2 . ( 49
)
Using the optimality condition, we have the equivalence:

y = prox h (x) ⇔ x ∈ ∂h(y) + y ⇔ y = (Id + ∂h) -1 (x). ( 50
)
The proximal operator is widely used in convex and non differentiable optimization. It is a generalization of the implicit gradient descent to convex and non differentiable function.

Let F = f + h, where f is convex differentiable function having a L-Lipschitz gradient and h is convex proper and lower semi continuous. A classical algorithm to minimize F is the Forward-Backward algorithm defined in the following way:

x n+1 = T (x n ), where T (x) := prox s 2 h x -s 2 ∇f (x) (51) If s 2 1
L , it can be shown that (F (x n ) -F * ) n∈N tends to 0 and (x n ) n∈N converges (weakly in an infinite dimension Hilbert space) to a minimizer of F .

The operator T shares many properties with the gradient descent. The algorithm FISTA of Beck and Teboulle can be seen as a Nesterov acceleration to this operator T . Following Siegel [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF] we modify the previous scheme [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF] so that it can be used with F = f + h that is a possibly non smooth convex function: we replace the vector ∇F (x n+ 1 2 ) in ( 41) by

g n+ 1 2 = 1 s 2 x n+ 1 2 -prox s 2 h (x n+ 1 2 -s 2 ∇f (x n+ 1 2 )) (52)
Note that:

g n+ 1 2 / ∈ ∂F (x n+ 1
2 ) as we might expect. The vector g n+ 1 2 as defined by (52) has been chosen such that the following decrease condition is satisfied:

∀y ∈ R n , F (x n+1 ) -F (y) ≤ g n+ 1 2 , x n+ 1 2 -y - s 2 2 g n+ 1 2 2 (53)
which is the only property of g n+ 1 2 we need to establish our convergence results. With that choice the new scheme can be written in the nonsmooth case as:

         x n+ 1 2 = x n + sv n v := v n+ 1 2 = (1 + γλs) -1 (v n -sg n+ 1 2 ) x n+1 = x n+ 1 2 -s 2 g n+ 1 2 v n+1 = v + (1 + λs) -1 λs 2 g n+ 1 2 (54)
that is exactly the original scheme (41) replacing ∇F (x n+ 1 2 ) by g n+ 1 2 . Notice that the same strategy is used in [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF] and [START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] to extend the convergence results of the numerical scheme in the differential case to the composite case. This new scheme shares the same properties as the previous one: Theorem 8. Let F = f + h where f is a convex differentiable function having a L-Lipschitz gradient and h a convex proper lower semicontinuous function. Let s = 1 √ L , γ > 0 and λ > 0. If γλ 2 < L then the following assertions hold:

1. The sequences (d(0, ∂F (x n )) n∈N and (v n ) n∈N converge to 0 when n → +∞.

2. If F is coercive then the sequences (F (x n ) -F * ) n∈N and (d(x n , X * )) n∈ converge to 0.

3. Assume that F is coercive and satisfies a Lojasiewicz property with an exponent θ ∈ (0, 1).

(a) If θ = 1 2 i.e if F satisfies some local quadratic growth condition G 2 µ , then the values (F (x n ) -F * ) n∈N decay exponentially to 0 and the iterates (x n ) n∈N converge to a minimizer x * of F . More precisely for any ε ∈ (0, 1), if γ = (1 -ε) L 2 λ 2 , there exists λ ε > 0 such that for all λ ∈ (0, λ ε ) then:

F (x n ) -F * = O 1 + µ L -ε µ L + λ √ L -n . ( 55
) (b) If θ ∈ ( 1 2 , 1) then F (x n ) -F (x * ) = O 1 n 1 2θ-1 . ( 56
)
Moreover, if θ < 3 4 , then the sequence (x n ) n∈N converges to a minimizer x * of F and the length of the trajectory is finite.

As in the differentiable case these rates of convergence can be improved assuming that α = γλ and that the objective function has a unique minimizer. Theorem 9. Let F = f + h where f is a convex differentiable function having a L-Lipschitz gradient and h a convex proper lower semicontinuous function. Assume that F satisfies the growth condition G 2 µ with parameter µ and has a unique minimizer.

If γ = α λ , α = 2 -2 √ 2
√ µ and λ = √ µ in (54), then there exist t > 0 and K > 0 such that if µ L ∈ [0, t], then the sequence (x n ) n∈N provided by (54) with s = 1 √ L satisfies:

F (x n ) -F * K 0 1 + 2 - √ 2 µ L -K 3 µ L -n
.

This Theorem applies then to the LASSO problem [START_REF] Hiriart-Urruty | Fundamentals of convex analysis[END_REF] when it admits a unique solution: it ensures that in this setting we can expect an exponential decay

O 1 + (2 - √ 2)κ -n
for κ sufficiently small. As far as we know, this is the best rate that can be found in the literature.

Numerical experiments

In the previous sections several convergence properties of the Heavy ball discrete scheme are proved, they are illustrated here. More precisely the exponential convergence is ensured for most parameters λ and α. The key to get a fast exponential decay is the knowledge of the best parameter µ defining the growth condition of F . In many practical problems, µ is not known. In many theoretical results, see e.g. [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF], [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o( 1 k 2 )[END_REF] or [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF], it is crucial to have a lower bound of µ to get a value of α ensuring an exponential decay. The actual decay of the algorithm depends on this lower bound estimation. The tuning of the parameter α is a problem of most Heavy Ball methods. An advantage of the proposed scheme is that even if µ is overestimated, an exponential decay is ensured: however, this decay can be quite slow. The optimal choice of α is an open and tough problem. Indeed, the estimation of the optimal α on a given problem is an ill-posed problem that may depend on the starting point of the algorithm. The relevant growth parameter is actually the one available between x and x * ∈ X * for any x on the trajectory of the algorithm. In many practical problems with sparsity constraints, the points (x n ) n∈N are nearly sparse on the trajectory of the algorithm: thus the relevant growth parameter μ, that is the highest parameter such that for all n ∈ N

μ 2 d(x n , X * ) 2 F (x n ) -F (x * )
may highly depend on x 0 . Notice that choosing α and λ in our algorithm depending on the real global µ parameter may be irrelevant in some situations since the real µ may be much lower than μ.

Liang et al [START_REF] Peyré | Activity identification and local linear convergence of forward-backward-type methods[END_REF] proved that, on a large family of optimisation problems with sparsity constraints, the trajectory of the Forward-Backward algorithm after a finite number of iterations belongs to a subspace of small dimension G depending on the set X * of solutions. Moreover, the asymptotic exponential decay of the Forward-Backward algorithm depends on the geometrical properties of the function F to minimize on this subspace G, and not on the whole space. Even if the convergence of the trajectory of Heavy Ball schemes on such a subspace is unclear due to the inertia, numerical experiments show that the iterates are really close to sparse vectors. In the inpainting experiment, most iterates have a small number of non zero wavelet coefficients.

For all these reasons, it is today an open problem to choose the parameter of these inertial algorithms. Moreover, a choice of parameter providing a fast asymptotically decay may not be the best for a given precision and numerical experiments will show that depending on the precision, the best set of parameters may not be the same, see Figure 3.

To test these new schemes we consider two classical image processing problems. The first one is the inpainting problem and the second one is the Total Variation (TV) denoising.

Inpainting

Let x 0 be a numerical image and M a masking operator setting randomly half of the pixel to 0. We want to estimate x from y 0 = M x 0 . Using the assumption that natural images are sparse in a suitable wavelet basis we estimate x solving the following optimization problem.

min x∈R n F (x) := 1 2 M x -y 2 + λ T x 1 ( 57
)
where T is the orthogonal Daubechies (db2) wavelet transform. A numerical example of image inpainting with this model is shown in Figure 2. Figure 3 compares the decay of log(F (x n ) -F (x * )) for various choices of parameters. We can observe that these new schemes can be compared to FISTA [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] for various precisions on this specific problem.

TV denoising

Let x 0 be a numerical image and n a realisation of a white Gaussian noise. We consider y = x+n a noisy image and we want to estimate x from y. Using the assumption that the Total Variation of x, that is the 1 norm of the discrete gradient of x is small, we can estimate x by solving This second problem (59) can be easily solved using any composite inertial algorithm. An example of image denoising with this approach is shown in Figure 4. Figure 5 compares the decay of log(F (x n ) -F (x * )) for various choices of parameters. We can observe that these new schemes can be compared to FISTA [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] for various precisions on this specific problem.

min x∈R n F (x) := 1 2 x -y 2 + λ ∇x 1 (58)

Proofs

Proofs of Theorem 1 and Corollary 1

The proof of Theorem 1 and Corollary 1 relies on the following Lyapunov energy:

E(t) = F (x(t)) -F * + 1 2 λ(x(t) -x * ) + ẋ(t) 2 + ξ 2 x(t) -x * 2 (60)
and is build in two steps: the first step consists in choosing the parameters λ and ξ such that the energy E satisfies some differential equation:

E (t) + δE(t) 0
for some suitable parameter δ > 0, which implies that: E(t) = O(e -δt ). The second step will be to get the control on the values F (x(t)) -F * from the energy E(t). In the third step we will prove the Corollary 1: assuming that the quadratic growth condition is global, we provide an uniform bound on the energy E and thus non-asymptotic decay rates for the values F (x(t)) -F * .

Step 1. Differentiating the energy E and using the ODE ( 12), we have:

E (t) = -λ ∇F (x(t)), x(t) -x * + (λ -α) ẋ(t) 2 + (ξ + λ(λ -α)) x(t) -x * , ẋ(t) -λ(F (x(t)) -F * ) + (λ -α) ẋ(t) 2 + (ξ + λ(λ -α)) x(t) -x * , ẋ(t)
using the convexity of F . Let us set δ < λ:

E (t) + δE(t) (δ -λ)(F (x(t) -F * ) + δ 2 (ξ + λ 2 ) x(t) -x * 2 + (λ -α + δ 2 ) ẋ(t) 2 +(ξ + λ(λ -α) + δλ) x(t) -x * , ẋ(t)
We now choose ξ := -λ(λ -α) -δλ = λ(α -λ -δ) so that the inner product term disappears.

E (t) + δE(t) (δ -λ)(F (x(t) -F * ) + δ 2 λ(α -δ) x(t) -x * 2 + (λ -α + δ 2 ) ẋ(t) 2 (61)
Using the quadratic growth assumption G 2 µ on F and assuming that δ < λ, there exists t 1 t 0 such that:

∀t t 1 , E (t) + δE(t) ( δ 2 λ(α -δ) + (δ -λ) µ 2 ) x(t) -x * 2 + (λ -α + δ 2 ) ẋ(t) 2 . (62)
Note that we can choose t 1 = t 0 if the quadratic growth condition is assumed to be global. Let us fix µ > 0. Since we want E (t) + δE(t) 0, we need to choose λ and δ such that:

δ 2 λ(α -δ) + (δ -λ) µ 2 0, λ -α + δ 2 0, δ < λ. (63)
Let us choose λ := α -δ 2 . We then have two constraints left:

α 2 - 3δ 2 + µ δ α + 3µ 2 + δ 2 2 0 (64) δ < 2α 3 (65)
The constraint (64) can be seen as a polynomial of degree 3 in δ or as a polynomial of degree 2 en α. Let us first consider (64) as a polynomial inequality of degree 3 in δ. Let α > 0 and:

P α (δ) = δ 3 -3αδ 2 + (3µ + 2α 2 )δ -2µα.
Noticing that: P α (δ) = 6(δ -α) < 0 for all δ < 2α 3 , we easily check that P α is non-increasing on the interval [0, 2α 3 [. First case: α < 3 µ 2 . In that case, a straightforward computation shows that: P α ( 2α 3 ) 0. We thus deduce that P α is non-decreasing on the interval [0, 2α 3 [.

Second case: α > 3 µ 2 .
In that case, a straightforward computation shows that: P α ( 2α 3 ) < 0. We thus deduce that P α is first non-decreasing and then non-increasing on [0, 2α 3 [. Observe now that:

P α (0) = -2αµ < 0, P α ( 2α 3 ) = α 3 27 > 0.
This implies that in any case there exists a unique δ α,µ ∈ [0, 2α 3 [ such that P α (δ α,µ ) = 0 and:

∀δ δ α,µ , P α (δ) 0. ( 66
)
Let us now consider the polynomial inequality (64) as a polynomial of degree 2 in α to obtain more information on the admissible values for δ α,µ . If δ is fixed then the polynomial inequality (64) admits a solution in α if and only if its discriminant is positive i.e. if:

∆ = 3δ 2 + µ δ 2 -4 3µ 2 + δ 2 2 0,
or equivalently if: δ 4 -12δ 2 µ + 4µ 2 0, i.e. if and only if:

δ (2 - √ 2) √ µ or δ (2 + √ 2) √ µ. (67)
Coming back to the definition (66) of δ α,µ , remember that the constraint P α (δ) 0 has to be satisfied by any δ ∈ [0, δ α,µ ] which excludes (2 + √ 2) √ µ (or any larger value) from the admissible values of δ α,µ . We can thus conclude that for a given α > 0:

δ α,µ (2 - √ 2) √ µ.
Finally, observe that for the critical value (2 -√ 2) √ µ, the discriminant ∆ is equal to 0 so that the polynomial P α ((2 -√ 2) √ µ) admits a double root in α given by:

α = 2 - √ 2 2 √ µ. (68)
For this particular value of α, we have:

δ α,µ = (2 - √ 2) √ µ, λ = √ µ, and ξ = √ 2 2 -1 µ. (69)
In any case, we have proved that with our choice of parameters, for all δ δ α,µ , we have: ∀t t 1 , E (t) + δE(t) 0, hence for δ δ α,µ :

∀t t 1 , E(t) E(t 1 )e -δ(t-t1) . ( 70
)
in order to cancel all the terms depending on the perturbation g after derivation. Indeed differentiating the energy G and using the convexity of F as in Theorem 1, we get:

G (t) = E (t) -λ(x(t) -x * ) + ẋ(t), g(t) = -λ ∇F (x(t)), x(t) -x * + (λ -α) ẋ(t) 2 + (ξ + λ(λ -α)) x(t) -x * , ẋ(t) -λ(F (x(t)) -F * ) + (λ -α) ẋ(t) 2 + (ξ + λ(λ -α)) x(t) -x * , ẋ (t)
Choosing now the same parameters λ, ξ and δ as in the unperturbed case, we obtain:

∀t t 0 , G (t) + δE(t) 0. (74)
Moreover observe that even if the energy E is not a sum of non-negative terms, according to (71) and (72), we have the following control:

E(t) = F (x(t)) -F * + 1 2 λ(x(t) -x * ) + ẋ(t) 2 + ξ 2 x(t) -x * 2 (75) 1 2 λ(x(t) -x * ) + ẋ(t) 2 (76)
so that: ∀t t 0 , G (t) -λE(t) 0. The energy G is so non-increasing, and: ∀t t 0 , G(t) ≤ G(t 0 ), i.e.:

∀t t 0 , E(t) E(t 0 ) + t t0 g(s), ẋ(s) + λ(x(s) -x * ) ds E(t 0 ) + t t0 g(s) (1 + β) ẋ(s) + λ(x(s) -x * ) ds
Combining the last inequality with (76), we get:

∀t t 0 , 1 2 λ(x(t) -x * ) + ẋ(t) 2 E(t 0 ) + t t0 g(s) λ(x(s) -x * ) + ẋ(s) ds
Applying the Grönwall-Bellman Lemma [20, Lemma A.5], we obtain:

∀t t 0 , λ(x(t) -x * ) + ẋ(t) 2E(t 0 ) + t t0
g(s) ds.

Assuming +∞ t0 g(s) ds < +∞, we can conclude that:

sup t t0 λ(x(t) -x * ) + ẋ(t) 2E(t 0 ) + +∞ t0 g(s) ds < +∞.
We set: A = 2E(t 0 ) + I 0 where I 0 = +∞ t0 g(s) ds. The differential inequality ∀t t 0 , G (t) -δE(t) 0 can be rewritten as:

∀t t 0 , E (t) -δE(t) + λ(x(t) -x * ) + (1 + β) ẋ(t), g(t) .
-δE(t) + A g(t) .

Integrating between t 0 and t, we finally obtain:

∀t t 0 , e δt E(t) e δt0 E(t 0 ) + A t t0
e δs g(s) ds,

e δt0 E(t 0 ) + A +∞ t0
e δs g(s) ds < +∞.

Hence:

∀t t 0 , E(t) E(t 0 ) + ( 2E(t 0 ) + I 0 )J 0 e -δt0 e -δ(t-t0) .
Let us define:

M 0 = F (x 0 ) -F * + 1 2 v 0 2 , I 0 = +∞ t0 g(s) ds, E 0 (λ) = M 0 + ( √ 2M 0 + I 0 )I 0 + √ M 0 + I0 √ 2 + λ √ µ M 0 + ( √ 2M 0 + I 0 )I 0 2 .
Applying [12, Lemma 4] with our choice of parameters (for which ξ < 0), we have again an uniform bound on the energy E for the class of differentiable convex functions satisfying a quadratic growth condition for some constant µ > 0, given by:

∀t t 0 , E(t) M 0 + ( 2M 0 + I 0 )I 0 + M 0 + I 0 √ 2 + 2α -δ 2 √ µ M 0 + ( 2M 0 + I 0 )I 0 2
which concludes the proof.

Proof of Theorem 4

Using the definition of the Lyapunov function E and the convexity of F , a standard computation (as in the beginning of step 1 of the proof of Theorem 1) leads to

E (t) + λE(t) λ 2 (ξ + λ 2 ) x(t) -x * 2 + 3 2 λ -α ẋ(t) 2 + (ξ + λ(2λ -α)) ẋ(t), x(t) -x * .
Observe that if F (x) = |x|, this inequality is actually an equality:

E (t) + λE(t) = λ 2 (ξ + λ 2 ) x(t) -x * 2 + 3 2 λ -α ẋ(t) 2 + (ξ + λ(2λ -α)) ẋ(t), x(t) -x * (77)
since for this function, we actually have for all u ∈ ∂F (x), u, x -x * = F (x) -F * . If we choose λ = 2α 3 and ξ = -λ 2 we get

E (t) + λE(t) = λ 3 4 |x(t)| 2 . ( 78
)
Hence for any δ > 0:

E (t) + δE(t) = λ 3 4 |x(t)| 2 + (δ -λ)E(t). (79)
Since x(t) → 0 when t → +∞, it follows that for δ = 2λ 3 < λ, it exists t 1 > t 0 such that E(x(t 1 )) > 0 and such that for any t > t 1 , E (t) + 2λ 3 E(t) 0. We deduce that for any t > t 1 ,

E(t) E(t 1 )e -2λ(t-t 1 )
3 with E(t 1 ) 0. It follows that it exists A 1 0 such that

|x(t)| - λ 2 4 |x(t)| 2 E(t) A 1 e -2λt 3
and thus it exists t 3 and A 2 such that for all t t 3

|x(t)| A 2 e -2λt 3 . (80)
Moreover from ( 78) and ( 80) we deduce that it exists t 3 and A 3 such that for any t t 3 ,

E (t) + δE(t) A 3 e -4λt 3
and thus if we define: H 1 (t) := e 2αt 3 E(t) we get for all t t 3 , H 1 (t) A 3 e -λt 3 . It follows that it exists B such that for all t > t 0 , H(t) B and thus

|x(t)| - λ 2 4 |x(t)| 2 E(t) Be -2αt 3 which implies that it exists B 1 > 0 such that: |x(t)| B 1 e -2αt 3 .
To prove the second point of the Theorem, we observe that (78) implies that H 1 is a non decreasing function. If H(t 0 ) > 0, it follows that for all t t 0 , H(t) H(t 0 ). Hence, ∀t t 0

e 2αt 3 |x(t)| + 1 2 |λx(t) + ẋ(t)| H(t 0 ) > 0.
Defining y(t) = e 2αt 3 x(t) we have for all t t 0

|y(t)| + 1 2 | ẏ(t)| 2 e -2αt 3
H(t 0 ) > 0.
Hence, if it exists t 4 such that for all t t 4 , |y(t)|

1 2 H(t 0 ), then ∀t t 4 , | ẏ(t)| 2 H(t 0 )e 2αt 3 . Since y ∈ C 1 (thanks to Corollary 3), y is a continuous function of time. It follows that the sign of ẏ(t) is constant on [t 4 , +∞[. If ẏ(t 4 ) > 0 then: ∀t t 4 , y(t) y t4 + t t4 H(t 0 )e αu 3 du
which is impossible. If ẏ(t 4 ) < 0 then for all t t 4 , y(t) y t4 -t t4 H(t 0 )e αu 3 du, which is also impossible. It follows that y(t) cannot tend to 0 when t → ∞ which concludes the proof.

Proofs of Theorems 6 and 8

In this section we propose a detailed proof of the convergence of the iterates generated by the discrete scheme [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] in the differentiable case, and by the scheme (54) in the nonsmooth case. These two proofs being very similar we will present each results of the two theorems, detailing all the calculations in the differentiable case and then explaining how to adapt them in the non-differentiable case.

Let us remind here the general scheme in the differentiable case: let γ > 0.

       λx n+ 1 2 = λx n + tv n v := v n+ 1 2 = (1 + γt) -1 (v n -tg) λx n+1 = λx n+ 1 2 -t 2 g v n+1 = v + (1 + t) -1 t 2 g.
(81) using the reduced notations:

t = λs, v = v n+ 1 2 and g = 1 λ ∇F (x n+ 1 2 ). ( 82
)
The scheme in the nonsmooth case is obtained from (81) by replacing g by the vector g defined by:

g = λ t 2 x n+ 1 2 -prox t 2 λ 2 h (x n+ 1 2 - t 2 λ 2 ∇f (x n+ 1 2 )) . (83)
Keep in mind that to adapt the proof from the differentiable to the non-differentiable case, a key element will be to be able to compute a subgradient of F at some iterate. More precisely, exploiting the definition of g, we easily prove that:

λg + ∇f (x n+1 ) -∇f (x n+ 1 2 ) ∈ ∂F (x n+1 ) (84)
Moreover using the L-Lipschitz continuity and the co-coercivity of ∇f , observe that:

λ g, ∇f (x n+1 ) -∇f (x n+ 1 2 ) - λ 2 t 2 ∇f (x n+1 ) -∇f (x n+ 1 2 ), x n+1 -x n+ 1 2 - λ 2 Lt 2 ∇f (x n+1 ) -∇f (x n+ 1 2 ) 2 -∇f (x n+1 ) -∇f (x n+ 1 2 ) 2
since: t = λs and s = 1 √ L . It follows that:

λg + ∇f (x n+1 ) -∇f (x n+ 1 2 ) 2 = λ 2 g 2 + ∇f (x n+1 ) -∇f (x n+ 1 2 ) 2 +2λ g, ∇f (x n+1 ) -∇f (x n+ 1 2 ) λ 2 g 2 -∇f (x n+1 ) -∇f (x n+ 1 2 ) 2 . Hence: λg + ∇f (x n+1 ) -∇f (x n+ 1 2 ) λ g . (85)

Proof of Point 1. Global convergence of the discrete scheme

Following the line of Alvarez in [START_REF] Alvarez | On the minimizing property of a second order dissipative system in hilbert spaces[END_REF], we introduce the following Lyapunov energy:

L n = F (x n ) -F (x * ) + ρ 2 v n 2 (86)
where ρ > 0 will be defined later.

The differentiable case. Remembering that v n+1 = v + t 2 1+t g, note that:

v n = (1 + γt)v + tg = (1 + γt)v n+1 + t(1 - (1 + γt)t 1 + t )g = (1 + γt)v n+1 + tAg
where:

A = 1 - (1 + γt)t 1 + t (87)
Observe that the quantity A always satisfies A < 1 for any t > 0 and that A > 0 if and only if:

γt 2 < 1.
Let us now prove that for a suitable choice of ρ, the sequence L n is non increasing. A key element to prove this result is the following decrease inequality:

F (x n+1 ) -F (x n ) -t g, v n - t 2 2 g 2 (88)
whose proof is detailed at (134). This inequality is a combination of the convexity and the Lipschitz continuity of F . We thus have:

L n+1 -L n = F (x n+1 ) -F (x n ) + ρ 2 v n+1 2 -(1 + γt)v n+1 + tAg 2 - t 2 2 g 2 + t g, (1 + γt)v n+1 + tAg + ρ 2 v n+1 2 -(1 + γt)v n+1 + tAg 2 (- 1 2 + A)t 2 g 2 + t(1 + γt) g, v n+1 + ρ 2 v n+1 2 -(1 + γt)v n+1 + tAg 2
Let us focus on the last part of the right member of the above inequality:

v n+1 2 -(1 + γt)v n+1 + tAg 2 = (-2γt -γ 2 t 2 ) v n+1 2 -2(1 + γt)At v n+1 , g -t 2 A 2 g 2 .
It follows that

L n+1 -L n - 1 2 + A - ρA 2 2 t 2 g 2 +(t(1 + γt) -ρ(1 + γt)At) g, v n+1 - ρ 2 (2γt+γ 2 t 2 ) v n+1 2 .
Choosing ρ = A -1 where A is given by (87), the scalar product term vanishes and we get

L n+1 -L n - t 3 2 1 + γt 1 + t g 2 - ρ 2 (2γt + γ 2 t 2 ) v n+1 2 . (89)
If follows that (L n ) n∈N is non increasing, and thus it converges in R + . Let us now rewrite inequality (89) as:

L n+1 -L n -a g 2 -b v n+1 2 ( 90
)
where a and b are two positive constants. Hence:

∀N 1, a N n=0 g 2 + b N n=0 v n+1 2 L 0 -L N +1 L 0 .
Since L n is a positive sequence, we deduce that g 2 and v n+1 2 are converging sums.

Hence both sequences ( g 2 ) n∈N and ( v n+1 2 ) n∈N tend to 0. Using the L-Lipschitz continuity of the gradient, we also deduce the convergence of the sequence (∇F (x n )) n∈N to 0.

The non differentiable case Consider now the non differentiable case. The calculations of this first step are unchanged replacing the vector g = 1 λ ∇F (x n+ 1 2 ) by g since we only need the decrease condition:

F (x n+1 ) -F (x n ) ≤ λ g, x n+ 1 2 -x n - t 2 2 g 2 . ( 91
)
which is actually satisfied by g applying Lemma 8 to x = x n+1 and y = x n . We thus have:

L n+1 -L n - t 3 2 1 + γt 1 + t g 2 - ρ 2 (2γt + γ 2 t 2 ) v n+1 2 (92)
and it follows that the sequence (L n ) n∈N is still non increasing, and converges in R + . Hence g 2 and v n+1 2 are converging sums, and ( g 2 ) n∈N and ( v n+1 2 ) n∈N tend to 0. To prove the global convergence of our discrete scheme (i.e. that d(0, ∂F (x n )) converges to 0), remember that:

λg + ∇f (x n+1 ) -∇f (x n+ 1 2 ) ∈ ∂F (x n+1 ). ( 93
)
Thus using (85) we have:

d(0, ∂F (x n+1 )) λg + ∇f (x n+1 ) -∇f (x n+ 1 2 ) λ g .
Since g converges to 0, d(0, ∂F (x n+1 )) also converges to 0. Observe first that in the differentiable and non-differentiable cases we have:

∀n ∈ N, F (x n ) -F * = L n - ρ 2 v n 2 .
We prove in Step 1 that the sequence (L n ) n∈N converges in R + and that (v n ) n∈N converges to 0, hence (F (x n ) -F * ) n∈N also converges in R + and is thus bounded. Assume now that F is additionally coercive. Using the coercivity assumption combined with the boundedness of (F (x n ) -F * ) n∈N , we deduce that the sequence (x n ) n∈N is bounded (as well as the sequence (x n+ 1 2 ) n∈N ). Thus there exists a compact set C containing X * and such that:

{x n ; n ∈ N} ∪ {x n+ 1 2 ; n ∈ N} ⊂ C. (94)
Convergence of F (x n )-F * to 0 in the differentiable case. Since the sequence (∇F (x n )) n∈N converges to 0 as shown in Step 1, we deduce that any accumulation point of the sequence (x n ) n∈N of iterates is a critical point, and thus a minimizer of F . By continuity of F and remembering that (F (x n ) -F * ) n∈N converges, necessarily (F (x n ) -F * ) n∈N converges to 0.

Convergence of F (x n ) -F * to 0 in the non-differentiable case. Since F is assumed convex and lower semicontinuous, its sub-differential is a non empty compact convex set and:

∀n ∈ N, ∃s n ∈ ∂F (x n ), d(0, ∂F (x n )) = s n . (95)
Since d(0, ∂F (x n )) converges to 0 according to Step 1, the sequence (s n ) n∈N also converges to 0.

Let us now introduce the set:

C = {(x, s) ∈ R n × R n ; x ∈ C, s ∈ ∂F (x)} ⊂ C × ∂F (C) ( 96
)
where C is the compact set defined by (94). Since F is a proper lower semicontinuous convex function, C is a compact subset of R n × R n , see [26, Propositions 6.2.1 and 6.2.2]. Observe now that by construction, (x n , s n ) ∈ C for all n ∈ N. There so exist a non-decreasing function ϕ : N → N and (x, s) ∈ C such that the sub-sequence (x ϕ(n) , s ϕ(n) ) converges to (x, s) when n tends to +∞. Remember now that (s n ) n∈N converges to 0 and (x, s) ∈ C, hence necessarily: s = 0 and:

0 ∈ ∂F (x). ( 97
)
We so proved that the sub-sequence (x ϕ(n) ) n∈N converges to a minimizer of F . By local Lipschitz continuity of F on the relative interior of its domain, we then deduce that (F (x ϕ(n) )) n∈N converges to F (x) = F * . Since the sequence (F (x n ) -F * ) n∈N converges, we deduce that (F (x n ) -F * ) n∈N converges to 0 when n → 0.

Convergence of d(x n , X * ) to 0 in the differentiable and non-differentiable cases. Assume on the contrary that the sequence d(x n , X * ) does not converge to 0: there thus exist ε > 0 and a non-increasing function ϕ : N → N such that the sub-sequence (x ϕ(n) ) n∈N satisfies:

∀n ∈ N, d(x ϕ(n) , X * ) ε. ( 98
) Let K ε = C ∩ {x ∈ R n ; d(x, X * ) ε}. By construction, K ε is a compact subset of R n and K ε ∩ X * = ∅.
Moreover for all n ∈ N, we have: x ϕ(n) ∈ K ε so that there exists a convergent subsequence (x ψ•ϕ(n) ) n∈N whose limit denoted by x belongs to K ε , and thus: x / ∈ X * . To conclude, note that in the differentiable case as in the non-differentiable case, we can deduce that F (x ψ•ϕ(n) ) -F * then converges to F (x) -F * . Since the whole sequence (F (x n ) -F * ) n∈N converges to 0 when n → 0, necessarily: F (x) -F * = 0 which is impossible since x / ∈ X * .

6.4.3 Proof of Point 3. Convergence of the iterates to a minimizer of F .

Assume now that F is coercive and additionally satisfies any Lojasiewicz property with an exponent θ ∈ [0, 1). Under these assumptions, the set X * of the minimizers is compact and according to Lemma 1 there exists µ > 0 and ε > 0 such that:

d(x, X * ) ε ⇒ 2µ (F (x) -F * ) θ d(0, ∂F (x)). ( 99
)
Proof of Point 3(a). Assume that θ = 1 2 i.e. that F satisfies the PL µ property. We now prove that the values F (x n ) -F * converge exponentially to 0.

Consider first the differentiable case. Observe that: x n+1 = x n+ 1 2 -t 2 λ g and:

λg + ∇F (x n+1 ) -∇F (x n+ 1 2 ) = ∇F (x n+1
). Following exactly the same steps as those which led to inequality (85), we can prove that: 1 2 , X * ) tends to 0 when n → +∞, we now write the PL µ property satisfied by F at x n+1 i.e. there exists n 0 ∈ N such that:

∇F (x n+1 ) 2 λ 2 g 2 -∇F (x n+1 ) -∇F (x n+ 1 2 ) 2 λ 2 g 2 Since d(x n+
∀n n 0 , 2µ (F (x n+1 ) -F (x * )) ∇F (x n+1 ) 2 λ 2 g 2 . ( 100
) that is: -g 2 - 2µ λ 2 (F (x n+1 ) -F (x * )) . (101)
Combined with (89), this inequality ensures that

L n+1 -L n -t 3 1 + γt 1 + t µ λ 2 (F (x n+1 ) -F (x * )) - ρ 2 (2γt + γ 2 t 2 ) v n+1 2 -t 1 + γt 1 + t µ L (F (x n+1 ) -F (x * )) + ρ 2 (2γ + γ 2 t) v n+1 2
Let us define:

K = min µ(1 + γt) L(1 + t) , γ(2 + γt) (102)
We can remark that we have K > 0 for any t > 0 so that:

L n+1 -L n -tKL n+1 . (103)
This ensures that for any n n 0

L n+1 (1 + tK) -1 L n . (104)
Note that in the non differentiable case, the very last inequality on the energy L n is unchanged: the proof is exactly the same by replacing g by g and ∇F (x n+1 ) by λg + ∇f (x n+1 ) -∇f (x n+ 1 2 ). In both cases, the inequality (104) ensures that (L n ) n∈N and thus (F (x n ) -F (x * )) n∈N and (v n ) n∈N decay exponentially. It follows in particular that the series n v n converges. Moreover, combining the second and the fourth lines of (81) in the differentiable case, we get:

t γt 2 -1 1 + t g = (1 + γt)v n+1 -v n .
Since v n converges, the series n g also converges. Noticing that λ(x n+1 -x n ) = tv n -t 2 g, we finally deduce the convergence of the sequence (x n ) n∈N . Since X * is a closed convex set and since d(x n , X * ) tends to 0 when n → +∞, necessarily (x n ) n∈N converges to a minimizer of F .

In the non-differentiable case, the conclusions are the same since we similarly have:

t γt 2 -1 1 + t g = (1 + γt)v n+1 -v n , λ(x n+1 -x n ) = tv n -t 2 g
and thus the convergence of the series g, and the convergence of (x n ) n∈N to a minimizer of F .

Optimizing the constant tK. We now focus on optimizing the constant tK, where K is given by (102). We can see that the two functions inside the minimum of the definition of K are increasing functions of γ. Hence the larger γ, then the larger K.

Remembering the constraint γt 2 < 1, i.e.: γ < 1 t 2 , the best choice is γ = 1- t 2 (with → 0 + ). For this choice of γ, we have:

tK = min µ L 1 - 1 + t , ( 1
-) 1 + 2t - t 2 . ( 105
)
Since t → (1 -) 1+2t t 2 -is a decreasing function on R * + and goes to +∞ when t → 0 + , we see that the best possible constant tK is thus µ L 1 -1+t . Thus for a given > 0, there exists t > 0 such that:

tK = µ L 1 - 1 + t .
Proof of Point 3(b). Assume now that F satisfies a Lojasiewicz property with an exponent θ ∈ ( 1 2 , 1) i.e. that there exists µ > 0 and ε > 0 such that:

d(x, X * ) ε ⇒ 2µ (F (x) -F * ) θ d(0, ∂F (x)). ( 106
)
We eventually prove that the decay of the values F (x n ) -F * is now polynomial both in the differentiable and non-differentiable cases.

The differentiable case. To lighten the notations, let us rewrite the inequality (89) as:

L n+1 -L n -A 1 g 2 -A 2 ρ 2 v n+1 2 . ( 107
)
where A 1 and A 2 are two positive constants. Using the Lojasiewicz property applied at

x n+ 1 2 with g = 1 λ ∇F (x n+ 1 2 ): 2µ λ (F (x n+ 1 2 ) -F * ) θ g .
and the decrease inequality (88) that implies:

F (x n+1 ) -F * F (x n+ 1
2 ) -F * , we get:

L n+1 -L n -A 1 4µ 2 λ 2 (F (x n+1 ) -F (x * )) 2θ -A 2 ρ 2 v n+1 2-4θ+4θ . (108)
In the first step of the proof we prove that v n+1 tends to 0. It follows that v n+1 is bounded. Since 2 -4θ < 0 we can then find A 3 > 0 such that for any n ∈ N,

L n+1 -L n -A 3 1 2 (F (x n+1 ) -F (x * )) 2θ + 1 2 ρ 2 2θ v n+1 4θ . (109)
Using the convexity of the function x → x 2θ observe that:

1 2 (F (x n+1 ) -F (x * )) + 1 2 ρ 2 v n+1 2 2θ 1 2 (F (x n+1 )-F (x * )) 2θ + 1 2 ρ 2 2θ v n+1 4θ (110) It follows that L n+1 -L n - A 3 4 θ L 2θ n+1 . (111)
We now apply Lemma 5 to the sequence (L n ) n∈N to deduce that there exists K > 0 such that for all n ∈ N,

F (x n ) -F (x * ) L n K n 1 2θ-1 . Moreover we have v n 2 2K ρn 1 2θ-1 . (112)
If 1 2θ-1 > 2, i.e. if θ < 3 4 , it follows that the sequence n 1 v n is finite. Using the fact that

x n+1 -x n = tv n -t 2 g (113)
and

g = t 1 - (1 + γt)t 1 + t -1 (v n -(1 + γt)v n+1 ) (114)
we deduce that the sequence n 1 x n+1 -x n is finite and thus that the sequence (x n ) n∈N converges to a minimizer x * of F .

The non-differentiable case. In the non-differentiable case, the proof remains unchanged by replacing one more time g by g. The only difference is the way to obtain the inequality (108). Let us prove that the inequality (108) is still valid by replacing g by g in the nonsmooth case. First we apply the Lojasiewicz property at x n+1 choosing λg + ∇f (x n+1 ) -∇f (x n+ 1 2 ) as a subgradient of F at x n+1 : for n large enough, we have:

2µ(F (x n+1 ) -F * ) θ λg + ∇f (x n+1 ) -∇f (x n+ 1
2 ) . Using now the inequality (85): λg + ∇f (x n+1 ) -∇f (x n+ 1 2 ) λ g , we then obtain:

2µ λ (F (x n+1 ) -F (x * )) θ g as expected.
Let us recall the discrete scheme we consider:

         x n+ 1 2 = x n + sv n v n+ 1 2 = (1 + αs) -1 (v n -s∇F (x n+ 1 2 )) x n+1 = x n+ 1 2 -s 2 ∇F (x n+ 1 2 ) v n+1 = v n+ 1 2 + (1 + λs) -1 λs 2 ∇F (x n+ 1 2 ) (124)
To simplify the writing of the proof, we introduce the following reduced notations:

t = λs, u = λ(x n+ 1 2 -x * ), v = v n+ 1 2 and g = 1 λ ∇F (x n+ 1 2 ). (125)
With these reduced notations, the scheme may be rewritten as:

       λx n+ 1 2 = λx n + tv n v := v n+ 1 2 = (1 + βt) -1 (v n -tg) λx n+1 = λx n+ 1 2 -t 2 g v n+1 = v + (1 + t) -1 t 2 g. (126)
Remember that the value of v n+1 is actually chosen such that

λ(x n+1 -x * ) + (1 + t)v n+1 2 = u + (1 + t)v 2 . ( 127
)
To study the properties of the scheme (124), we define the sequence L n :

L n := L(x n , v n ) := F (x n ) -F * + 1 2 λ(x n -x * ) + (1 + λs)v n 2 -(β -1) λ 2 2 x n -x * 2
which can be seen as particular discretization of the energy E. Let us first compute L n+ 1 2 and L n using the reduced notations:

L n+ 1 2 := L(x n+ 1 2 , v n+ 1 2 ) := F (x n+ 1 2 ) -F * + 1 2 u + (1 + t)v 2 - β -1 2 u 2 (128)
and L n can be written in the following way as:

L n = F (x n ) -F * + 1 2 u + λ(x n -x n+ 1 2 ) + (1 + t)v n 2 - β -1 2 u + λ(x n -x n+ 1 2 ) 2 = F (x n ) -F * + 1 2 u + v n 2 - β -1 2 u -tv n 2 .
Now, noticing that:

-(β -1)λ 2 2 x n+1 -x * 2 = -(β -1)λ 2 2 x n+1 -x n+ 1 2 + x n+ 1 2 -x * 2 = - β -1 2 u 2 - (β -1)t 4 2 g 2 + (β -1)t 2 u, g
the energy L n+1 can be expressed as a variation of L n+ 1 2 :

L n+1 = L n+ 1 2 + F (x n+1 ) -F (x n+ 1 2 ) -(β -1)
t 4 2 g 2 + (β -1)t 2 u, g . (129)
To prove Theorem 1 we demonstrated that the Lyapunov Energy defined by (121) satisfies

E (t) + δE(t) 0. ( 130
)
To prove Theorem 7 we will use the following Lemma whose proof is left to Subsection 6.5.1: Lemma 6. There exist t 1 > 0 and K 3 > 0 such that for any t ∈ [0, t 1 ], it holds:

∀n ∈ N, 1 + δ λ t -t 2 K 3 L n+1 -L n 0. ( 131
)
Moreover, we then have for any t ∈ [0, t 1 ],

∀n ∈ N, L n 1 + δ λ t -K 3 t 2 -n L 0 . (132)
To get the control on the values F (x n ) -F * from the control on the energy L n provided by Lemma 6, note that:

L n = F (x n ) -F * + 1 2 λ(x n -x * ) + (1 + λs)v n 2 -(β -1) λ 2 2 x n -x * 2 F (x n ) -F * -(β -1) µ 2 x n -x * 2 . ( 133
)
since λ = √ µ. Observe now that assuming the uniqueness of the minimizer x * of F , Theorem 6

ensures that the sequence of iterates (x n ) n∈N converges to x * . Thus using the quadratic growth condition G 2 µ satisfied by F , there exists N ∈ N such that:

∀n N, µ 2 x n -x * 2 F (x n ) -F * .
Combining this last inequality with (133), we finally get: (2 -β) (F (x n ) -F * ) L n for any n N , and thus the expected control on F (x n ) -F * .

Proof of Lemma 6

Sketch of proof: The proof of Lemma 6 is technical. This is the reason why we first give a structure of it:

1. A key descent inequality (134) used previously by Siegel is proven.

2. We give an upper bound of L n+ 1 2 -L n . 3. From this bound and (134) we give an upper bound of L n+1 -L n .

4. We deduce a bound on (1 + tδ/λ)L n+1 -L n as a polynomial in t whose coefficients depend on u and v.

5. We conclude by bounding this polynomial by L n+1 .

Proof of Lemma 6: Step 1. We first prove the inequality (134)

F (x n+1 ) -F (y) ≤ λ g, x n+ 1 2 -y - t 2 2 g 2 (134)
which is a key inequality used by Siegel in [START_REF] Siegel | Accelerated first-order methods: Differential equations and Lyapunov functions[END_REF]. Since ∇F is L = 1 s 2 -Lipschitz and g :=

1 λ ∇F (x n+ 1
2 ) := λ t 2 (x n+1 -x n+ 1 2 ) we get

F (x n+1 ) -F (x n+ 1 2 ) - t 2 2 g 2 . ( 135
)
Step 3. Using (129), we get:

L n+1 -L n = L n+1 -L n+ 1 2 + L n+ 1 2 -L n = F (x n+1 ) -F (x n ) -
Then, we apply (134) with y = x n and tv n = λ(x n+ 1 2 -x n ) to get:

F (x n+1 ) -F (x n ) -t g, v n ≤ - t 2 2 g 2 (140)
and ( 134) with y = x * to get:

g, u ≥ F (x n+1 ) -F * + t 2 2 g 2 . ( 141
)
Combining ( 139), ( 140) and (141) we deduce:

L n+1 -L n ≤ -t(F (x n+1 ) -F * ) -t(β -1) (2 + βt) v, u + (β -1)(1 + βt)t 3 v, g - t 3 2 g 2 - β -1 2 t 2 + (β + 1)t -t(1 + βt) 2 v 2 .
Step 4. Using the following expression of F (x n+1 ) -F * :

F (x n+1 ) -F * = L n+1 - 1 2 λ(x n+1 -x * ) + (1 + t)v n+1 2 + (β -1)λ 2 2 x n+1 -x * 2 = L n+1 - 1 2 u + (1 + t)v 2 + β -1 2 u -t 2 g 2 = L n+1 - 1

Proof of Theorem 9

The proof is essentially similar to the one of Theorem 7. The careful reader may have remarked that the only property of g that is used in the proof of Theorem 7 is the inequality (134) we recall here ∀y ∈ R n , F (x n+1 ) -F (y) ≤ λ g, x n+ 1 2 -y -

t 2 2 g 2 .
It is used twice, once with y = x n and once with y = x * . Actually, any vector g satisfying this descent property will ensure the decay described in both theorems. It turns out that the vector g defined in (52) satisfies this inequality under the hypothesis of the Theorem 9, see also [ L then for all (x, y) ∈ R n × R n :

F (T x) -F (y) ≤ 1 s 2 x -T x, x -y - 1 2s 2 T x -x 2 . ( 155
)
Proof. Since T x = prox s 2 h x -s 2 ∇f (x) , we have x -s 2 ∇f (x) -T x ∈ s 2 ∂h(T x) that is for any y ∈ R n : h(T x) -h(y)

x -T x s 2 -∇f (x), T x -y (156)

Since ∇f is 1 s 2 -Lipschitz

f (T x) -f (x) ∇f (x), T x -x + 1 2s 2 T x -x 2 . ( 157
)
Since f is convex, for all y ∈ R n f (x) -f (y) ∇f (x), x -y .

Adding the three last inequalities we get:

F (T x) -F (y) 1 s 2 x -T x, T x -y + 1 2s 2 T x -x 2 . ( 159
)
Using T x -y = T x -x + x -y we get

F (T x) -F (y) 1 s 2 x -T x, x -y - 1 2s 2 T x -x 2 . ( 160
)
Applying this Lemma to x = x n+ 1 2 we have T x = x n+1 and using g := λ t 2 (x -T x) we get exactly the inequality needed to complete the proof of Theorem 9: ∀y ∈ R n , F (x n+1 ) -F (y) ≤ λ g, x n+ 1 2 -y -

t 2 2 g 2 .
(161)

2 :

 2 Throughout the paper, we have a special interest in the class G 2 µ of convex functions satisfying a quadratic growth condition G 2 µ and the sub-class PL µ of functions satisfying a global version of G 2 µ , or equivalently the Lojasiewicz property with an exponent θ = 1 Definition 3 (The Polyak-Lojasiewicz property PL µ ). Let F : R n → R ∪ {+∞} be a proper lower semicontinuous convex function with X * = argmin F = ∅. Let F * = inf F . The function F has the Polyak-Lojasiewicz property PL µ for some µ > 0 if and only if:

Figure 2 :Figure 3 :

 23 Figure 2: Example of image inpainting with model (57)

Figure 4 :Figure 5 :

 45 Figure 4: Example of TV Denoising with model (58)

6. 4 . 2

 42 Proof of Point 2. Convergence of F (x n ) -F * and d(x n , X * ) to 0.

Table 1 :

 1 Rate of convergence for the Heavy Ball ODE Definition 6. A numerical scheme provides a low exponential decay on a functional set F µ if there exists δ > 0 such that for any F ∈ F µ and any solution x of the associated ODE

	1 qS µ and uniqueness of minimizer µ C 2 and G 2 µ	Siegel [41] ADR[12] Bégout et al. [15]	2 √ µ 3 µ 2 -	√ µ √ 2µ µ

Table 2 :

 2 Rates of convergence of inertial algorithms depending on the regularity of the function to minimize

	can be extended

  -t(1 + βt) 2 v 2 + (β -1)(1 + βt)t 3 v, g +(β -1) 2 (2 -β)t u 2 + (β -1)t(1 + t) 2 v 2 -(β -1) 2 t 5 g 2 -2(β -1)t(1 + t) u, v + 2(β -1) 2 t 3 u, g n+1 -L n ≤ -(3 -2β)t(F (x n+1 ) -F * ) + (β -1)(2 -β)t u 2 +(β -1)(2 -β)t 2 v, u + β -1 2 t 2 4 -β + 2(β + 1)t + β 2 t 2 v 2 +(β -1)(1 + βt)t 3 v, g + 2(β -1) 2 t 3 u, g -t 3 2 (1 + 2(β -1) 2 t 2 ) g 2 . -t 2 g 2 + (β -1)(2 -β)t u 2 +(β -1)(2 -β)t 2 v, u + β -1 2 t 2 4 -β + 2(β + 1)t + β 2 t 2 v 2 +(β -1)(1 + βt)t 3 v, g + 2(β -1) 2 t 3 u, g -t 3 2 (1 + 2(β -1) 2 t 2 ) g 2 . n+1 -L n ≤ (β -1)(2 -β)t 2 v, u + β -1 2 t 2 5 -β + (3β + 2)t + β 2 t 2 v 2 +2(β -1)t 3 u, g -t 3 2 (1 -(β -1)t -(2 -3β + β 2 )t 2 ) g 2 .From the previous inequality, we therefore know that there exists two positive real numbers K 1 and K 2 and two polynomials P 1 and P 2 such that n+1 -L n t 2 K 1 u, v + P 1 (t) v 2 + K 2 t u, g + tP 2 (t) g P 3 (t) + 1 2 |2tP 3 (t) + K 2 | . We can conclude that for any t ∈ [0, t 1 ] and any n 0,

	2 2 -β u + (1 + t)v 2 + 2 u 2 -(1 + t) 2 β -1 2 2 v 2 + t 4 g 2 + u 2 -2t 2 u, g (β -1)t 4 2 g 2 -(1 + t) u, v -(β -1)t 2 u, g we eventually get, remembering that δ = L n+1 -λ = 2(β -1) and thus 1 -δ λ = 3 -2β, so that t = 2(β -1)t + (3 -2β)t: 1 + δ λ t L -2(β -1)t -(2 -β)t 2 u 2 -(1 + t) 2 2 v 2 + (β -1)t 4 2 g 2 -(1 + t) u, v -(β -1)t 2 u, g ≤ -(3 -2β)t(F (x n+1 ) -F * ) -t 3 2 g 2 -t(β -1) (2 + βt) v, u -β -1 2 F (x n+1 ) -F (x * ) ≥ µ 2 x n+1 -x 2 = µ 2λ 2 u -t 2 g 2 = 1 2 u -t 2 g 2 (142) we get: 1 + δ λ t L n+1 -L n ≤ -3 -2β 2 t u ≤ -3 -2β 2 t u -t We thus have: 1 + δ λ t L We now use the inequality: | tg, v | ≤ t 2 2 g 2 + 1 2 v 2 (144) so that: t 3 | v, g | ≤ 1 2 t 4 g 2 + 1 2 t 2 v 2 and: 1 + δ λ δ λ t L 2 (145) t L 1 + We deduce that for all t ∈ [0, t 1 ], t 2 + (β + 1)t So that: 1 + δ λ 1 + δ λ t L n+1 -L n t 2 K 3 L n+1 (153) t L Using the growth condition and remembering that λ 2 = µ: with K 3 = max t∈[0,t1] max 2P 3 (t), 2 2-β L n 1 + -n δ λ t -K 3 t 2 L 0 . (154)

n+1 -L n ≤ -(3 -2β)t(F (x n+1 ) -F * ) -t 3 2 g 2 -t(β -1) (2 + βt) v, u β -1 2 t 2 + (β + 1)t -t(1 + βt) 2 v 2 + (β -1)(1 + βt)t 3 v, g 2 g 2 + (β -1)(2 -β)t u -t 2 g 2 +(β -1)(2 -β)t 2 v, u + β -1 2 t 2 4 -β + 2(β + 1)t + β 2 t 2 v 2 +(β -1)(1 + βt)t 3 v, g + 2(β -1)t 3 u, g -t 3 2 (1 + 2(β -1)t 2 ) g 2 . n+1 -L n ≤ (β -1)(2 -β)t 2 v, u + β -1 2 t 2 4 -β + 2(β + 1)t + β 2 t 2 v 2 (143) +(β -1)(1 + βt)t 3 v, g + 2(β -1)t 3 u, g -t 3 2 (1 + 2(β -1)t 2 ) g 2 .

Acknowledgments

J.-F. Aujol acknowledges the support of the European Union's Horizon 2020 research and innovation program under the Marie Sk lodowska-Curie grant agreement No777826.

The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR) under reference ANR-PRC-CE23 Masdol and the support of FMJH Program PGMO 2019-0024 and from the support to this program from EDF-Thales-Orange.

Step 2. The point now is to get the control on the values F (x(t)) -F * from the inequality (70). To do this, remember the definition of the energy with ξ = -δλ 2 = -δ 4 (2α -δ) < 0:

Using the quadratic growth condition satisfied by F , we then get the control:

Moreover we can easily check that:

Indeed, observe that if α < 2 √ µ then the discriminant of the polynomial Q α (δ) = δ 2 -2αδ +4µ is non positive so that the inequality (72) is satisfied for any δ δ α,µ . If α 2 √ µ, the polynomial Q α has two real roots given by δ ± = α ± α 2 -4µ. Noticing that P α (α -α 2 -4µ) = µ(α + α 2 -4µ) > 0, the variations of the polynomial P α imply that necessarily: δ α,µ < α-α 2 -4µ.

Combining the control (70) with the inequality (71), we get:

which concludes the proof of Theorem 1.

Step 3. Assume now that the quadratic growth condition is global. In that case, we have: t 1 = t 0 and: Lemma 3] with our choice of parameters (for which ξ < 0), we have an uniform bound on the energy E for the class of differentiable convex functions satisfying a quadratic growth condition for some constant µ > 0, given by:

which concludes the proof of Corollary 1.

Proofs of Theorem 2 and Corollary 2

The proof of Theorem 2 is quite standard, see [START_REF] Attouch | Fast inertial dynamics and FISTA algorithms in convex optimization[END_REF][START_REF] Balti | Asymptotic for the perturbed heavy ball system with vanishing damping term[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] Sebbouh | Nesterov's acceleration and Polyak's heavy ball method in continuous time: convergence rate analysis under geometric conditions and perturbations[END_REF][START_REF] Aujol | Convergence rates of the Heavy-Ball method for quasi-strongly convex optimization[END_REF] and the references therein. Let T > 0. We consider the same Lyapunov energy as in the unperturbed case:

To deal with the perturbation term, the idea is to add an integral term to the energy E by considering the energy:

Technical result

To derive the polynomial rates stated in the point 3(b) of Theorems 6 and 8, we have used the following technical result:

Lemma 5. Let (u n ) n∈N be a non negative sequence. Assume that there exist θ > 1 2 and a > 0 such that:

Then it exists K > 0 such that ∀n 1,

Proof. Let us define w n :=

and it is thus bounded i.e. it exists A > 0 such that for all n ∈ N, w n A and we can observe that

Let us define f (x) = x + ax 2θ . This function is non decreasing on (0, +∞). Moreover for any K > 0 we have:

It turns out that for K

A a 1 2θ-1 we get using (117):

we get using (115):

since f is non increasing it follows that u n+1 K (n+1)

, we conclude by induction on n.

Proof of Theorem 7

The proof of Theorem 7 is based on a Lyapunov analysis inspired by the one proposed for the ODE. To study the ODE we used to following Lyapunov energy:

where

2 . Moreover, we have

Since F is convex, for any y ∈ R n we have

Inequality (134) holds summing the two previous inequalities.

Step 2.

We use the identity (with the condition A -B = a + b):

We thus get with this identity:

Moreover observe that:

Hence:

Using the expression of v n = (1 + βt)v + tg , we get:

More precisely, we have:

and

Step 5. This last step relies on the following technical lemma whose proof is straightforward:

, we have:

Applying Lemma 8 or 11 with x = √ 1 + tv and y = u √ 1+t and using the fact that for all t 0, P1(t) K1(1+t) 1 4 we deduce

Defining P 3 (t) := 2K1P1(t) (1+t) , we get for all t 0:

Moreover