Maxime Egéa
email: maxime.egea@univ-angers.fr

(Non)-penalized Multilevel methods for non-uniformly log-concave distributions

Keywords: Mathematics Subject Classification: Primary 65C05-37M25 Secondary 65C40-93E35 Multilevel, ergodic diffusion, Langevin algorithm, Euler scheme, weakly convex

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In this paper, we are interested in the sampling of probability distribution named Gibbs measure whose density is π(dx) = 1 Z e -U (x) 2σ 2 λ(dx) where λ is the Lebesgue measure, Z = R d e -2U (x) σ 2 λ(dx) and U : R d → R is a coercive function. Many applications require the computation of these measures in high dimension state space including for example machine learning, Bayesian estimation or statistical physics. Methods that are studied in this paper are based on the discretization of over-damped Langevin stochastic differential equation (SDE)

dX t = -∇U (X t )dt + σdB t , (1)
where (B t ) t≥0 is a d-dimensional Brownian motion and σ ∈ R + * . These methods received a lot of attention in the last few years, in particular when U is strongly convex (in the sense where, in the whole space, the smallest eigenvalue of its Hessian is lower bounded by a positive α). This assumption may be certainly constraining in view of applications. It is the reason why, in this paper, we suppose that U is not strongly convex but only weakly convex 1 . More precisely, we will assume that the potential U is a convex twice differentiable function with Lipschitz gradient. Under these assumptions, strong existence and uniqueness of a solution (X t ) t≥0 classically hold and the solution to (1) is an ergodic Markov process whose invariant distribution is exactly the Gibbs distribution π ∝ e -U dλ (for background, see e.g. [START_REF] Meyn | Markov chains and stochastic stability[END_REF], [KS91], [START_REF] Khasminskii | Stochastic stability of differential equations[END_REF], [START_REF] Hairer | Convergence of Markov processes[END_REF]).

We respectively denote by (P t ) t≥0 and L the related semi-group and infinitesimal generator. We recall that for a twice differentiable function f : R d → R by

Lf = -∇U, ∇f + σ 2 2 ∆f.
It is also well-known that in this log-concave setting, the distribution π satisfies the Poincaré inequality (see e.g. [START_REF] Bakry | A simple proof of the Poincaré inequality for a large class of probability measures[END_REF]) and that convergence holds to equilibrium in distribution and in "pathwise average": for any starting point x ∈ R d , the occupation measure converges to π in the following sense: for all continuous function f ∈ L 2 (π),

1 t t 0 f (X x s ) ds -→ t→+∞ π(f ) a.s. (2)
In the continuity of [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF], our multilevel methods will be based on discretized adaptations of (2). More precisely, we first choose to approximate the stochastic process (X t ) t≥0 by the classical Euler-Maruyama scheme. When the related step size γ is constant, this discretization scheme is defined by X0 = x ∈ R d and:

∀n ≥ 0, X(n+1)γ = Xnγ -γ∇U Xnγ + σ √ γZ n+1 ,
where (Z n ) n∈N is an i.i.d sequence of d-dimensional standard Gaussian random variables. In the long-time setting, these schemes and there convergence properties to equilibrium were first studied in the nineties by [START_REF] Talay | Second-order discretization schemes of stochastic differential systems for the computation of the invariant law[END_REF] and [START_REF] Gareth | Exponential convergence of Langevin distributions and their discrete approximations[END_REF]. Then, some decreasing step Euler schemes were investigated by [START_REF] Lamberton | Recursive computation of the invariant distribution of a diffusion: the case of a weakly mean reverting drift[END_REF] (see also [START_REF] Lemaire | Estimation récursive de la mesure invariante d'un processus de diffusion[END_REF]) in order to manage, in the same time, the discretization and long-time errors. Here, we choose to keep the constant step size point of view in order to avoid some additional technicalities but our ideas could be probably adapted to this setting.

We also introduced the continuous-time extension of ( Xnγ ) n≥0 given by: for all n ∈ N and for all t ∈ [nγ, (n + 1)γ), Xγ t := Xnγ -(tnγ)∇U Xnγ + σ B t -B (n+1)γ . If we denote by t γ the discretization time related to a positive number t, i.e.,

t γ = γ sup{n ≥ 1, nγ ≤ t}, (3)
we remark that ∀t ≥ 0, Xt = x -t 0 ∇U ( Xs γ )ds + σ t 0 dB s .

This "pseudo-diffusion" form is usually convenient for proofs but it is worth noting that the procedure is only based on the discrete-time Euler scheme. If no confusion arises, we will sometimes write t instead of t γ , and Xt or Xγ t instead of Xγ,x0 t to alleviate the notations. We now mimic (2) with the Euler scheme to approximate the target measure π. Thus, consider the following occupation measure (for background see [START_REF] Talay | Second-order discretization schemes of stochastic differential systems for the computation of the invariant law[END_REF]), for N ∈ N

ν γ N (f ) := 1 N N -1 i=0 f Xiγ .

Multilevel methods

Multilevel methods introduced by M. Giles in [START_REF] Michael | Multilevel Monte Carlo path simulation[END_REF]. These methods, initially used for the approximation of E[f (X T )], are now widely exploited in many settings. The rough idea is the following: assume that the target E[X] is the expectation of a random variable that cannot be sampled (with a reasonable cost) and consider a family of random variables (X j ) j approximating X, with a cost of simulation and a precision which typically increases with j. The principle of the multilevel is to stack correcting layers with a low variance to a coarse approximation X 0 of the target. More precisely, writing

E[X J ] = E[X 0 ] Coarse + J j=1 E[X j -X j-1 ] Correcting layer , (4)
the multilevel method consists in building a procedure based on the addition of Monte-Carlo approximations of E[X 0 ] and of E[X j -X j-1 ], j = 1, . . . , J. Then, if the random variables X j -X j-1 have low variance, the approximation of E[X j -X j-1 ] requires few simulations and, in view of (4), we can obtain a procedure which has the bias related to X J but with a cost which may be much less than the one generated by a standard Monte-Carlo method applied to estimate E[X J ].

In the discretization setting, the family of random variables (X j ) j is a sequence of Euler schemes ( Xγj ) j where (γ j ) j is a family of decreasing time steps2 . Following the heuristic (4), the (independent) correcting layers are built by coupling of Euler schemes with steps γ j-1 and γ j . Note that in view of the simulation of the (synchronous) coupling, we need γ j-1 to be a multiple of γ j (in this paper, we will assume that γ j = γ 0 2 -j ).

Multilevel methods have been already studied in the literature for the approximation of the invariant distribution of the Langevin diffusion. In [GMS + 20], the authors take advantage of the convergence in distribution to equilibrium. Thus, the classical Monte-Carlo point of view is adopted: the approximation of π(f ) is obtained by sampling a large number of Euler schemes for each level. In [START_REF] Pagès | Weighted multilevel Langevin simulation of invariant measures[END_REF] 3 and [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF], the point of view is to take advantage of the convergence of the occupation measure. Thus, each level is based on only one path of the Euler scheme or of the couple of Euler schemes whose length decreases (since the variance of the correcting layers decreases) and discretization step increases. All these papers show that, in the uniformly strongly convex setting, the invariant distribution can be approximated (along Lipschitz continuous functions) with a precision ε (in a L 2 -sense) using a Multilevel procedure whose complexity is of order ε -2 or ε -2 log p (ε) with p ∈ [1, 3]. Moreover, in [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF], a particular attention is paid to the dependency in the dimension. In this case, it is shown that one can build a multilevel procedure that produces an εapproximation of the target for a complexity cost proportional to dε -2 (with an explicit expression of the dependence in the Lipschitz constant L and the contraction parameter α).

The more involved weakly convex case seems to be less explored in the multilevel paradigm but, in view of applications (for instance for Bayesian Lasso), it is natural to ask about the robustness of these methods when one relaxes the contraction assumption.

Contributions and plan of the paper

The main goal of this paper is thus to extend the multilevel Langevin algorithm for the Gibbs sampling to the weakly convex setting, and if possible to obtain some quantitative bounds for the complexity related to the computation of an ε-approximation of the target (see Section 1.4 for a definition of ε-approximation).

We first investigate the penalized multilevel method: in the continuity of [START_REF] Dalalyan | User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient[END_REF] and [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF], we build a multilevel procedure based on the following observation: consider a new equation with another potential U α (x) := U (x) + α 2 |x| 2 , this new equation has an invariant distribution named π α which converges to π when α tends to 0 in Wasserstein metric. The idea is that this new invariant distribution is easiest to sample because of the uniform convexity of the potential U α . In Section 2.1, Theorem 2.1 combines the benefits of the penalized approach and of the multilevel methods. For a Lipschitz-continuous function f : R d → R and a C 2 -potential U , the multilevel procedure performs an ε-approximation of π(f ) with a complexity cost proportional to π(|.| 2 ) 3 dε -5 . As in [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF], our result depends on the generally unknown constant π(|.| 2 ) which is at least proportional to d (see Remark 2.1 for details and comparisons with [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF]).

Because of the above remarks, we chose in a second part to try to develop some tools which tackle the weakly convex setting from a dynamic point of view and which can improve the complexity in terms of ε. More precisely, in the spirit of [START_REF] Gadat | On the cost of Bayesian posterior mean strategy for log-concave models[END_REF], we study an intermediary framework (called weakly parametric convex setting in the sequel). We assume that the eigenvalues of the Hessian matrix of U vanish when |x| goes to +∞, but with a rate controlled by the function x → U -r (x) with r ∈ [0, 1) (see Assumption (H 1 r )). The parameter r characterizes the "lack of strong convexity", the case r = 1 referring to the "Laplace case"4 whereas r = 0 corresponds to the uniformly convex setting. When one assumes such an assumption, one can get some bounds for the exponential moments of the Euler scheme (at the price of technicalities). One is also able to preserve some confluence properties, i.e. two paths of the Euler scheme have a tendency to stick at infinity. Finally, in this setting, it is also possible to control the distance between diffusion paths and the related Euler schemes. These three ingredients (obtained with a lower quality than in the strongly convex setting) allow us to tackle the multilevel procedure in this framework.

The related main contribution is Theorem 2.2. In this result, we provide a series of statements under different sets of assumptions: when U is only C 2 or when U is C 3 . Under (H 1 r ) only or under (H 1 r ) and (H 2 r ), where (H 2 r ) denotes an additional assumption which requires the highest eigenvalue to be also controlled by the function x → U -r (x) (we could roughly say that under (H 1 r ) and (H 2 r ), the potential is uniformly weakly convex in the sense that "the decrease of the contraction is uniform"). In each statement, we provide a multilevel procedure adapted to the assumptions. The related complexity is exhibited in terms of d, ε but also in terms of the contraction parameter and the Lipschitz constant. Without going too much into the details, when U is only C 2 , the complexity is of the order ε -3 whereas when U is C 3 , we can obtain a rate of the order ε -2-ρ for any ρ > 0 and thus approach the "optimal" complexity ε -2 . Now, in terms of the dimension, when only (H 1 r ) holds the dependence in the dimension of the complexity is bounded by

d 3 2 +( 9 2 +δ)r 1-r
whereas when (H 1 r ) and (H 2 r ) hold, we obtain in

d 3 2 +( 9 2 +δ)r when U is C 2 and d 1+ ρ 2 +4r
for any ρ > 0 when U is C 3 . This means that when U is C 3 and (H 1 r ) and (H 2 r ) hold, the complexity is of the order ε -2-ρ d 1+ ρ 2 +4r for any ρ > 0. With respect to the paper [START_REF] Gadat | On the cost of Bayesian posterior mean strategy for log-concave models[END_REF], our multilevel procedure improves the dependence in ε and is most comparable in terms of the dimension. Note that when only (H 1 r ) holds, the dependency in the dimension dramatically increases on r. Whereas, when the potential is uniformly weakly convex, the dependence in the dimension does not explode when r → 1 (see Theorem 2.2 for more details).

Plan of the paper. As detailed in the previous paragraphs, Sections 2.1 and 2.2 are respectively devoted to the statement of the main theorems for the penalized multilevel and in the parametric weakly convex case. Then, Section 3 is dedicated to the proof of the first main theorem (Theorem 2.1). In Proposition 3.2, we obtain a Wasserstein bound related to the bias induced by the penalization on the invariant distribution. The proof of Theorem 2.1 is then an adaptation of [EP21, Theo 2.2]. From Section 4, we focus on the proof of Theorem 2.2. In Section 4, we prove some preliminary results on the diffusion and its Euler scheme under (H 1 r ): we begin with some controls of the exponential moments (Proposition 4.1 and Proposition 4.2) which in turn lead to some bounds of the polynomial moments (Proposition 4.3). In this section, we also show that the discretization error can be controlled in long time (Proposition 4.4) and finally obtain an integrable rate of convergence to equilibrium for the Euler scheme (Proposition 4.5). With the help of these fundamental bricks, in Section 5, we obtain some bounds on the bias (Proposition 4.7) and of the variance of the procedure (Proposition 5.2) which in turn allow us to finally provide the proof of Theorem 2.1 in Theorem 2.2.

Design of the algorithm

We now build the multilevel procedure. Let x ∈ R d be the initialization of the procedure, J ∈ N be a number of levels, (γ j ) 0≤j≤J be a sequence of time steps, (T j ) 0≤j≤J be a sequence of final times. Define by Y(J, (γ j ) j , τ, (T j ) j , x, .) the multilevel occupation measure : for all f : R d → R, Y(J, (γ j ) j , τ, (T j ) j , x, α, f

) := 1 T 0 -τ T0 τ f ( Xγ0,x s γ 0 )ds + J j=1 1 T j -τ Tj τ f ( Xγj,x s γ j-1 ) -f ( Xγj-1,x s γ j-1 )ds, (5)
where trajectories on each level are coupled with the same Brownian motion. To ease notation, we simplify Y(J, (γ j ) j , τ, (T j ) j , x, f ) by Y(f ). The parameter τ ≥ 0 is the time where we begin the average. Indeed, this "warm-start trick" may improve the precision of the estimation in some cases (we refer to [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF] for more details). But, it could be equal to 0 when the gain is non-efficient, for example in the second part of our main result.

Notations

The usual scalar product on R d and the induced Euclidean norm are respectively denoted by

f : R d → R is denoted by [f ] 1 . A function f : R d → R is C k , k ∈ N, if
all its partial derivatives are well-defined and continuous up to order k. The gradient and Hessian matrix of f are respectively denoted by ∇f and D 2 f . The probability space is denoted by (Ω, F , P). The Laplace operator is denoted by ∆: ∆f = d i=1 ∂ 2 i,i f . The L p -norm on (Ω, F , P) is denoted by • p . For two probability measures µ and ν, we define the Wasserstein distance of order p by

W p (µ, ν) = inf ζ∈Π(µ,ν) R d |x -y| p dζ(x, y) 1 p
, where Π(µ, ν) is the set of couplings of µ and ν.

• P and uc : For two positive real numbers a and b and a set of parameters P , one writes a P b if a ≤ C P b where C P is a positive constant which only depends on the parameters P . When a ≤ Cb where C is a universal constant, we write a uc b.

• ε-approximation: We say that Y is an ε-approximation (or more precisely an ε-approximation of a for the

L 2 -norm) if Y -a 2 = E[|Y -a| 2 ] 1 2 ≤ ε.
Equivalently, Y is said to be an ε-approximation of a if the related Mean-Squared Error (MSE) is lower than ε 2 .

• Complexity/ε-complexity: For a random variable Y built with some iterations of a standard Euler scheme, we denote by C(Y), the number of iterations of the Euler scheme which is needed to compute Y. For instance, C( Xγ nγ ) = n. We sometimes call ε-complexity of the algorithm, the complexity related to the algorithm which produces an ε-approximation.

Main results

The penalized approach

In this section, we develop a penalized multilevel method to sample a non-strongly log-concave probability distribution π. The idea is based on [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF] and [START_REF] Arnak | Penalized langevin dynamics with vanishing penalty for smooth and log-concave targets[END_REF] where the authors consider the potential U α (x) := U (x) + α 2 |x| 2 with α > 0 which is called penalized version of U . We here assume that U satisfies the following assumption:

WC L : U is a non-zero C 2 -function and there exists L > 0 such that

∀x ∈ R d , 0 D 2 U (x) LId R d , (6)
the inequalities being taken in the sense of symmetric matrices. Denote by π α the invariant measure of the diffusion process (X α t ) t≥0 solution of the stochastic differential equation

dX α t = -∇U α (X α t )dt + σdB t . (7)
It appears that π α satisfies the Bakry-Émery criterion thus we can apply our multilevel method that requires strong convexity to approximate π α . But our target is π then we have to control the distance (in a Wasserstein sense) between π and π α . To this end, the results of [START_REF] Bolley | Weighted Csiszár-Kullback-Pinsker inequalities and applications to transportation inequalities[END_REF] and [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF] ensure the convergence of π α when α goes to 0 with a bound of the Kullback-Leibler divergence. This leads to the following theorem:

Theorem 2.1. Assume that WC L hold. Let ε > 0, let f : R d → R be a Lipschitz function and x ∈ R d . For ε ≥ 0 let

J ε = ⌈2 log 2 (σ 2 dm 1/2 4 ε -2 )⌉, T j = σ 2 d log(γ -1 0 )m 4 ε -5 J 2 ε 2 -J , j ∈ {0, . . . , J ε }, γ 0 = εm -1/2 4 L -2 , ( 8
)
with m 4 = E π [| • | 4 ]. Then we have Y(f ) -π(f ) 2 2 ≤ ε, (9)
with a complexity satisfying ) and this implies that the complexity is of the order d 4 ε -5 .

C(Y) ≤ 1 3 log (γ 0 ) m 3/2 4 L 2 σ 2 dε -5 log 2 1 2 σ 2 dm 1/2 4 ε -3 3 . ( 10
)
Let us now compare with [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF]: note that in this paper, the cost is not explicitly written. As usual in the Monte-Carlo literature, the authors control the number of iterations of the Euler scheme which is necessary to draw a random variable whose distance to the target is lower than ε instead of giving the real cost. In the Langevin Monte-Carlo case, when U is C 2 , they then obtain a number of iterations which is, up to logarithmic terms, of order π(|.| 2 )dε -4 . Normalizing ε (i.e. replacing ε by ε/ π(|.| 2 )) leads to a number of iterations of order π(|.| 2 ) 3 dε -4 . But to compare with our work, we need to include the Monte-Carlo cost, i.e. to the number of simulations which is necessary to make the variance lower than ε 2 . Then, we have to multiply the previous number of iterations by Var π (f )ε -2 which can be reasonably bounded by π(|.| 2 )ε -2 (when f is Lipschitz). This means that the complexity of the penalized Langevin Monte-Carlo in [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF] is of the order π(|.| 2 ) 4 dε -6 . In consequence, the multilevel method allows us to improve the result of [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF]. Note that the authors also provide other algorithms such as the Kinetic-LMC where the bound in ε is improved (it seems that our result meets the complexity given for this algorithm).

About decreasing penalization.In the above result, we propose a Multilevel strategy based on a fixed penalization. A natural question arises: could we take advantage of the Multilevel strategy by keeping the same penalization for the highest level and progressively reducing it on the lower layers? Indeed, this is precisely what we do with the discretization bias, thus we can wonder about the effect of such a strategy for the penalization: to this end, let us introduce a decreasing sequence (α j ) 0≤j≤J of penalization levels such that the bias induced by the distance between π αJ and π is small with respect to the required precision ε.

More specifically, we want to replace (4) with the following telescoping series

π γJ αJ = π γ0 α0 + J j=1 π γj αj -π γj-1 αj-1 .
However, the above decomposition requires several longtime bounds on the underlying dynamics to be an efficient multilevel procedure. In particular, for the control of the variance generated by each level, we need to control the pathwise distance between two paths of the dynamics related to penalization levels α j and α j-1 . But, oppositely to the constant penalization case where we can obtain some confluence properties, we can observe that for two trajectories computed with two different degrees of penalization α and α, there is a "lack of confluence" quantified by the following inequality,

E X x,α t -X y, α t 2 ≤ e -2αt |x -y| 2 + (α -α)dσ 2 α ,
where the bound dramatically depends on α. In this inequality we voluntary treated the continuous case to ease the readability but a discrete analogous result can be shown. We refer to the section 3 to get the proof of this result. This inequality is certainly related to the shape of the penalization sequence (α j ) 0≤j≤J .

In fact, this result must be considered in addition of the error induced by the difference between two Euler schemes with different time steps. Up to an universal constant we have (see [EP21, Prop 5.1])

sup t≥0 E Xx,γ t - Xx,γ/2 t 2 ≤ γdσ 2 α 2 .
Then, the additional variance generated by the decrease of the penalization does not have an impact on the results, we have to impose that γdσ 2 α 2 j (α jα j-1 )dσ 2 α j-1 . In particular, the sequence (α j ) 0≤j≤J cannot be too decreasing. Going further into the computations, it seems that we cannot expect a significant gain with this approach.

Parametric weakly convex setting

The purpose of this section is to study the non-penalized multilevel procedure in the weakly convex setting. Instead of penalizing the dynamics, it is actually natural to ask about the robustness of the "standard" multilevel method in this case. To answer this question, we have to prove a series of properties in the spirit of the assumptions H i (i ∈ {1, 2, 3, 4}) in [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF]. These assumptions include the convergence to equilibrium of the Euler scheme with a quantitative rate, the long-time control of the L 2 -distance between the Euler scheme and the diffusion, the control of the Wasserstein distance between π γ and π and the control of the moments. Some of these properties (especially the long-time control of the L 2 -distance) seem hard to check in a general convex setting. We thus propose to work in the parametric weakly convex setting used in [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF] by introducing (H 1 r ) (see below) where we assume that the contraction vanishes at ∞ but with a rate controlled by U -r .

Let us now introduce our assumptions depending on a parameter r ∈ [0, 1) :

(H 1 r ) : The potential U is a positive C 2 -convex function with a unique minimum x ⋆ such that U (x ⋆ ) = 1. ∇U is L-Lipschitz with L ≥ 1 6 . The function x → λ D 2 U(x)
is positive and there exist L and c > 0 such that,

∀x ∈ R d , λ D 2 U(x) ≥ cU -r (x).
The lower-bound can be seen as the "lack of uniform strong convexity" for the potential. Indeed, if r = 0 we recover the strong convexity and r = 1 corresponds to the weakest convexity case where the gradient is flat at infinity. The fact that ∇U is L-Lipschitz implies that x → λD 2 U(x) is upper-bounded by L. In order to improve the dependence in the dimension, we also introduce an additional assumption that deals with the case where the largest eigenvalue decreases at infinity with an intensity that is of the same order as the lowest eigenvalue:

(H 2 r ) : There exists a positive c such that for all x ∈ R d , λD 2 U(x) ≤ cU -r (x).

For instance, it can be checked that the function x → (1 + |x| 2 ) p with p ∈ (1/2, 1] satisfies (H 1 r ) and (H 2 r ) with r = 1-p p , c = 2p(2p -1) and c = 2p.

Let us finally define the couple (γ ⋆ , Ψ) by:

(γ ⋆ , Ψ) =      1 4L , (1 + σ 2 ) dL + 1 + dL c 1 1-r if only (H 1 r ) holds 1-r 4(c∨L) , c r d(1+σ 2 )(c∨L) c if (H 1 r ) and (H 2 r ) hold true, (11)
where c r is a constant which only depends on r. γ ⋆ will denote the largest value for γ 0 whereas, Ψ controls the moments of U ( Xnγ ) (see Proposition 4.3 for details). It is worth noting that on the one hand, γ ⋆ does not depend on d and on the other hand, that Ψ ∝ d 1 1-r when only (H 1 r ) holds and Ψ ∝ d when (H 1 r ) and (H 2 r ) hold true. This means that in the first case, the dependence in d dramatically increases with r whereas in the second case, it does not depend on r. In the next result, the reader will have to keep in mind that the definition of these parameters depends on the assumptions. In particular, even if (H 2 r ) does not appear in the statement, it is hidden in the value of the parameters γ ⋆ and Ψ.

We are now ready to state our main theorem in this setting: Theorem 2.2. Assume (H 1 r ) and let x ∈ R d such that U (x) r Ψ, γ 0 ∈ (0, γ ⋆ ], δ ∈ (0, 1/4] and let f be a Lipschitz-continuous function. For an integer J ≥ 1, set ∀j ∈ {1, . . . , J}, γ j = γ 0 2 -j and

T j = T 0 2 -(1-ρ)j with ρ ∈ [1/2, 1). Let ε > 0. (i) Set ρ = 1/2, J = ⌈log 2 ( L c 2 1-δ ∧ c Ψ1+(3+δ)r γ 0 ε -2 )⌉, and T 0 := (c -3 4 ∨ c -5 2 -δ ) Ψ 3 2 +( 9 2 +δ)r ε -2 .
Then, for δ small enough,

Y(J, (γ j ) j , τ, (T j ) j , f ) -π(f ) 2 r,δ ε, (12)
with a complexity cost,

C(Y) ≤ √ L(c -5 4 ∧ c -7 2 -δ ) Ψ 3 2 +( 9 2 +δ)r ε -3 . ( 13
) (ii) Assume that U is a C 3 -function with sup x∈R d d i=1 |∆(∂ i U )| 2 r σ -4 L 3 Ψ. Set J = ⌈log 2 c -2 1-δ L 3 Ψ1+ 2r 1-δ γ 0 ε -1 ⌉ and T 0 = L ρ 2 c -( 5 4 -ρ)∧(3ρ)+δ ∨ c -5 2 -δ Ψ1+(4-2ρ+δ)r ε -2 .
Then, for δ small enough, Y(J, (γ j ) j , τ,

(T j ) j , f ) -π(f ) 2 r,δ,ρ ε, with C(Y) ≤ γ -ρ 0 L 2ρ c 5 4 ∧(2ρ)+δ ∨ c -5 2 -δ Ψ1+ ρ 2 +(4-ρ+δ)r ε -2-ρ .
Remark 2.2. This technical result deserves several comments:

⊲ Complexity in terms of ε. If we only consider the dependence in ε, we obtain ε -3 when U is only C 2 and ε -2-ρ for any ρ > 0 when U is C 3 and an additional (but reasonable 7 ) assumption on ∆(∇U ) is satisfied. We can thus theoretically approach the complexity in ε -2 . However, it is worth noting that the non-explicit constants depending on ρ and δ go to ∞ (independently of the other parameters) when ρ and δ go to 0. The fact that we "only" obtain a complexity in ε -3 when U is C 2 is due to the fact that in this case, our bound of the 1-Wasserstein distance between π γ and π is of the order √ γ. When U is C 3 , the bound on the 1-Wasserstein distance between π γ and π is of order δ. This allows us to clearly improve the complexity but it can be noted that we do not retrieve the ε -2 -bound of the uniformly convex case. This is due to the rate of convergence to equilibrium. Actually, our rate is polynomial and not exponential, which in turn, implies a "slight cost" on the dependence in ε. In fact, we could get some (sub)-exponential rates but without controlling the dependence in the dimension which is of first importance for applications.

⊲ Complexity in terms of the dimension. The dependence in the dimension strongly varies with the assumptions. In the "worst" case where U is only C 2 and only (H 1 r ) holds, the complexity is of the order

d 3 2 +( 9 2 +δ)r 1-r
. Unfortunately, when r is close to 1, this means that this dependence seriously worsens. We retrieve this same phenomenon when U is C 3 and only (H 1 r ) holds but with a better bound of the order d

1+ ρ 2 +(4-ρ+δ)r 1-r
for any positive ρ and δ. This bad behavior when r goes to 1 is due to the fact that when only (H 1 r ) holds, the bounds on the exponential moments of sup t≥0 E[e U( Xt) ] are of the order exp(d

1 1-r ). Introducing (H 2
r ) dramatically improves this exponential bound since in this case, we are able to prove that this is of the order e d (this implies that sup t≥0 E[U p ( Xt )] is of the order d p , see Propositions 4.3 and 4.2 for details). It is worth noting that in this case, the dependence in the dimension does not explode when r goes to 1 being of the order d 1+ ρ 2 +(4-ρ+δ)r for any ρ > 0. Remark that when r = 0, we formally approach the rate of the uniformly convex case in dε -2 obtained in [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF].

⊲ Comparison with the literature: In this setting, the only paper which we may reasonably compare with is [GPP20] since we use similar assumptions. Compared with this paper, our multilevel procedure certainly improves the dependence in ε, replacing ε -4 by ε -3 when U is C 2 and ε -3 by ε -2-ρ when U is C 3 . In terms of the dimension, our approach slightly increases the dependence on the dimension. For instance, when (H 1 r ) and (H 2 r ) hold, [START_REF] Gadat | On the cost of Bayesian posterior mean strategy for log-concave models[END_REF] obtain a bound in d 1+4r when U is C 2 or C 3 . We here retrieve a dependence which is somewhat similar when U is C 3 but when U is C 2 , our bound in d 3 2 +( 9 2 +δ)r is clearly worse.

⊲ About the parameters. In applications, the dependence in the parameters, L, c, and c may be of importance (think for instance to applications to Bayesian estimation where these parameters can strongly depend on the number of observations). This is why here, we chose to keep all these dependencies in the main result even if it sometimes adds many technicalities in the proof.

Proof of Theorem 2.1

This section is devoted to the proof of the first main result. We first quantify the bias induced by the approximation of π by π α . To this end, we use the Talagrand concentration inequality that estimates the Wasserstein distance between these two measures by their Kullback-Leibler divergence.

Proposition 3.1. Assume that WC L hold. Then for all α ≥ 0, there is a universal constant C such that

W 1 (π, π α ) ≤ C D KL (π|π α ).
7 See Remark 4.8 for details on this assumption

We refer to [BV05, Cor 2.4] to find a proof of this result. In addition, in [START_REF] Arnak S Dalalyan | Bounding the error of discretized langevin algorithms for non-strongly log-concave targets[END_REF] the authors show that C ≤ 2E π [|X| 2 ] (page 24). It remains to compute the Kullback Leibler divergence of π from π α , to bound the bias induced by the penalization. Proposition 3.2. Assume that WC L hold. Then for all α ≥ 0,

W 1 (π, π α ) ≤ α 2 √ 2 E π [|.| 4 ] 1/2 .
Proof. The Kullback-Leibler divergence is defined by

D KL (π|π α ) = R d log dπ dπ α (x) π(dx).
By definition of π and π α ,

D KL (π|π α ) = R d log Z α Z + α 2 |x| 2 π(dx) = log E π e -α 2 |.| 2 + α 2 E π |.| 2 .
Using the inequality e -x ≤ 1x + x 2 2 for x ≥ 0, this leads to,

D KL (π|π α ) ≤ log 1 -E π α 2 |.| 2 - α 2 8 |.| 4 + α 2 E π |.| 2 ,
and by the inequality log(1x) ≤ -x for x ≤ 1 we get,

D KL (π|π α ) ≤ α 2 8 E π [|.| 4 ].
Proposition 3.1 for π α implies the result. Now we switch to the proof of the main theorem. With the two previous propositions, we control the bias induced by the penalization, then it remains to compute the error and the complexity of a multilevel procedure in a uniformly convex setting. To this end, we use [EP21, Theorem 2.2] which gives parameters to perform an ε-approximation of the invariant distribution with an explicit complexity in terms of the parameters, especially in terms of the contraction parameter. Here, this is exactly our penalization parameter α and we will thus optimize its choice in the proof.

Proof. of Theorem 2.1 Let ε be a positive number and f : R d → R be a Lipschitz continuous function. By the bias/variance decomposition, triangular inequality and the Monge-Kantorovich duality, we have

Y(f ) -π(f ) 2 2 ≤ E [|Y(f ) -π(f )|] 2 + Var(Y(f )) ≤ 2|π α (f ) -π(f )| 2 + 2E[Y(f ) -π α (f )] 2 + Var(Y(f ))) uc W 2 1 (π, π α ) P1 + E[Y(f ) -π α (f )] 2 + Var(Y(f )) P2 . ( 14
)
The second term denoted by P 2 is the mean squared error of a Multilevel procedure for the approximation of π α . This penalized measure is invariant for the diffusion process defined with the potential U α . By assumption WC L , U α satisfies the following property

C α : For all x, y ∈ R d , ∇U α (x) -∇U α (y), x -y ≥ α|x -y| 2 .
[EP21, Theorem 2.2] ensures that with α/L 2 ≤ 1, σ 2 α -1 d ≥ 1, |U α (x 0 )| 2 uc σ 2 αd and the following parameters8 :

J ε = ⌈2 log 2 (σ 2 dα -1 ε -1 )⌉, T j = σ 2 d log(γ -1 0 ) α 2 ε -2 J 2 ε 2 -j , r ∈ {0, . . . , J ε }, γ 0 = α/(2L 2 ), (15)
we have

P 2 ≤ ε,
with a complexity satisfying

C(Y) ≤ 5 log 2L 2 α L 2 2α 3 σ 2 dε -2 log 2 σ 2 d α ε -2 3 . ( 16
)
It remains to calibrate the penalization parameter α. Proposition 3.2 implies

P 1 uc α 2 4 E π [|.| 4 ], so that P 1 ≤ ε 2 for α = 2ε E π [|.| 4 ] 1/2 .
Putting α in (15) and ( 16),

C(Y) ≤ 5dε -5 16 log E π [|.| 4 ] 1/2 L 2 ε -1 E π [|.| 4 ] 3/2 L 2 σ 2 log 2 1 2 E π [|.| 4 ] 1/2 σ 2 dε -3 3 .
Precisions about the "decreasing penalization":

For α > α > 0 and x, y ∈ R d consider the couple (X x,α t , X x, α t ) t≥0 defined by

X x,α t = x + t 0 ∇U α (X x,α s )ds + σB t X y, α t = y + t 0 ∇U α(X y, α s )ds + σB t . (17) Proposition 3.3. For all t > 0 we have E X x,α t -X y, α t 2 ≤ e -2αt |x -y| 2 + (α -α)dσ 2 α .
Proof. By the Itô formula we have,

e 2αt X x,α t -X y, α t 2 = |x -y| 2 + t 0 2e 2αs ∇U α (X x,α s ) -∇U α X y, α s , X y, α s -X x,α s ds + t 0 2αe 2αs X x,α s -X y, α s 2 ds,
We now use the fact that for all x ∈ R :

∇U α(x) = ∇U α (x) + ( α -α) |x| which yields e 2αt X x,α t -X y, α t 2 = |x -y| 2 + t 0 2e 2αs ∇U α (X x,α s ) -∇U α X y, α s , X y, α s -X x,α s ds + t 0 2(α -α)e 2αs X y, α s , X y, α s -X x,α s ds + t 0 2αe 2αs X x,α s -X y, α s 2 ds.
The strong convexity property of

U α : ∇U α (x) -∇U α (y), x -y ≤ α|x -y| 2 implies e 2αt E X x,α t -X y, α t 2 ≤ |x -y| 2 + t 0 2(α -α)e 2αs X y, α s , X y, α s -X x,α s ds ≤ |x -y| 2 + t 0 2(α -α)e 2αs E X y, α s 2 ds.
Up to an universal constant, the moment of order two of the diffusion process under the strong convexity hypothesis are bounded by σ 2 d α (see [EP21, Lem 5.1]), we get

E X x,α t -X y, α t 2 ≤ e -2αt |x -y| 2 + 2(α -α)dσ 2 α t 0 e 2α(s-t) ds.
The result follows.

4 Preliminary bounds under (H 1 r ) and (H 2 r ):

From now, we switch to the proof of the second part of the main results i.e. we consider the weakly convex case under the parametric assumptions (H 1 r ) and (H 2 r ). As mentioned before, these hypotheses deal with the behavior of the lowest and highest eigenvalues of the Hessian matrix of U . In some sense, (H 1 r ) quantifies the strict convexity of the potential which in turn implies the contraction of the dynamics. Note that such an assumption also appears in [START_REF] Cattiaux | Self-improvement of the Bakry-Emery criterion for Poincaré inequalities and Wasserstein contraction using variable curvature bounds[END_REF] where the authors obtain exponential rates to equilibrium under this parametric assumption.

In this preliminary section we state a series of results related to the diffusion and its Euler scheme under Assumption (H 1 r ). For the upper-bounds of the eigenvalues of D 2 U , we distinguish two cases: the first one where we assume that we have a uniform upper-bound by L (in others words that ∇U is L-Lipschitz) and the second one, we add Assumption (H 2 r ) where the largest eigenvalues also decrease at infinity with a rate which is comparable to the one of the lowest eigenvalues. In fact, in the second case, we will see that we are able to preserve a dependency of the moments in the dimension which is linear, whereas, without this assumption, the dependency is O(d

1 1-r ).
In the second part we state a result about the longtime pathwise control of the distance between the diffusion and its Euler scheme. Third, we study the convergence to equilibrium for the Euler scheme. Finally, we quantify the bias induced by the discretization with some results on the 1-Wasserstein distance between π and π γ (the invariant measure of the Euler scheme).

Bounds on the exponential moment

In order to study the confluence between the continuous time process and its Euler scheme, let us start this section by a control of the moment of the continuous time process and the discrete time when the potential U is supposed convex. We first state a result on the control of the exponential moment of the continuous time process. Proposition 4.1. For all x ∈ R d and t > 0,

sup t≥0 E x e U (X t ) σ 2 ≤ e U (x) σ 2 +    e 1 σ 2 (1+ dL 2c ) 1 1-r under (H 1 r ) dL 2c e 1 σ 2 (4 1 1-r ∨ dc c )
under (H 1 r ) and (H 2 r ). We preface the proof by a technical lemma.

Lemma 4.1. Let θ ∈ (0, 2 σ 2 ) and M > 0, then

C M := x ∈ R d ; (1 -θ) |∇U (x)| 2 - σ 2 2 θ∆U (x) ≤ M ⊂ x ∈ R d , U (x) ≤ K M ,
where,

K M =      1 + (2M+θσ 2 dL) 2c(2-θσ 2 ) 1 1-r under (H 1 r ) max M(1-r) (4-2θσ 2 )c ∨ 4 1 1-r , 2σ 2 dθc c(2-θσ 2 )
under (H 1 r ) and (H 2 r ).

In particular, C M is a compact set (since it is included in a level set of a coercive function).

Proof. Denote by y the solution of the ordinary differential equation y ′ (t) = -∇U (y(t)) starting from y(0) = x. Define the function f : t → |∇U (y(t))| 2 we have by chain rule for all t ∈ R + . By (

H 1 r ), d dt f (t) = 2 y ′′ (t), y ′ (t) = 2 D 2 U (y(t))y ′ (t), y ′ (t) ≥ 2c U -r (y(t))y ′ (t), y ′ (t) = 2c 1 -r d dt U 1-r (y(t)) ,
Since lim t→+∞ y(t) = x ⋆ , we get by integration

|∇U (x)| 2 ≥ 2c 1 -r U 1-r (x) -U 1-r (x ⋆ ) . (18)
Therefore,

1 - θσ 2 2 |∇U (x)| 2 - σ 2 θ 2 ∆U (x) ≥ 2(1 -θ)c 1 -r U 1-r (x) -U 1-r (x ⋆ ) - σ 2 θ 2 ∆U (x).
Since ∆U = Tr(D 2 U ) ≤ d λD 2 U ≤ dL (where λA stands for the largest eigenvalue of symmetric matrix A) and U (x ⋆ ) = 1, it follows that

1 - θσ 2 2 |∇U (x)| 2 - σ 2 2 θ∆U (x) ≥ 2 1 -θσ 2 2 c 1 -r (U 1-r (x) -U 1-r (x ⋆ )) - θσ 2 dL 2 ,
so that

C M ⊂ x ∈ R d ; U (x) ≤ 1 + 2M + θσ 2 dL 2c(2 -θσ 2 ) 1 1-r . ( 19
)
If we now consider the case where (H 2 r ) also holds, we use that ∆U ≤ cU -r (x) to obtain:

1 - θσ 2 2 |∇U (x)| 2 - σ 2 2 θ∆U (x) ≥ (2 -θσ 2 )c 1 -r U 1-r (x) 1 -U r-1 (x) - (1 -r)σ 2 θcd 2c(2 -θσ 2 )U (x) .
To ensure that the right-hand member is lower-bounded by M , it is enough to ensure that

(2 -θσ 2 )c 1 -r U 1-r (x) > M 2 , U r-1 (x) ≤ 1 4 and σ 2 θcd c(4 -2θσ 2 )U (x) ≤ 1 4 .
This concludes the proof.

Proof. (of Proposition 4.1) Let θ ∈ (0, 1), (to be choosen latter) and for all x ∈ R define,

f θ (x) := e θU(x) , (20)
show that f θ is a Lyapunov function for the dynamic L :

Lf θ (x) = -θf θ (x) 1 - θσ 2 2 |∇U (x)| 2 - θσ 2 2 ∆U (x) ≤ -θM f θ (x) -θf θ (x) 1 - θσ 2 2 |∇U (x)| 2 - θσ 2 2 ∆U (x) 1 CM (x),
where C M is defined in Lemma 4.1. In the proof of this lemma we showed that C M is included in a level set

L KM = {x ∈ R d | U (x) ≤ K M }. Thus, -θf θ (x) 1 - θσ 2 2 |∇U (x)| 2 - σ 2 2 θ∆U (x) 1 CM (x) ≤ θ 2 σ 2 2 f θ (x)∆U (x)1 LK M ≤ θ 2 σ 2 dL 2 e θKM 1 LK M .
Finally f θ is a Lyapunov function for the dynamics: i.e. for all x ∈ R d ,

Lf θ (x) ≤ -θM f θ (x) + θ 2 σ 2 dL 2 e θKM 1 LK M (x),
Hence by a Gronwall argument we get,

P t f θ (x) ≤ e -θMt f θ (x) + θσ 2 dL 2M e θKM . Choosing θ = 1 σ 2 , M = θσ 2 dL 2 under (H 1 r ) and M = (4-2θσ 2 )c 1-r
under (H 1 r ) and (H 2 r ) leads to the result. We now state an analogous result for the Euler scheme.

Proposition 4.2. (i) Assume (H 1 r ). Then, if γ ∈ (0, 1 4L ] and θ ∈ [0, 1 8σ 2 ],
sup n≥0 E x e θU( Xnγ ) ≤ e θU(x) + e θ(1+ 8dL c ) 1 1-r +θdL cosh(θγdL).

(ii) Assume (H 1 r ) and (H 2 r ). If γ ∈ (0, 1-r 4c∨L ] and θ ∈ [0, 1 8σ 2 ∧ 1], then for all x ∈ R d and n ∈ N we have

sup n≥0 E x e θU( Xnγ ) ≤ e θU(x) + ce cr θd(1+σ 2 )c c ,
where c denotes a constant independent of the parameters and c r a constant which only depends on r.

The proof of this proposition is postponed in Appendix A.

Remark 4.1. The reader will find more explicit (but more technical) bounds in the proof of the second case. It is worth noting that we can preserve a condition on γ does not depend on d (as in the strongly convex setting). This is of first importance in our multilevel setting where it is much more efficient if the rough layers of the method can be implemented with step sequences with large sizes. The proof is very close to [START_REF] Gadat | On the cost of Bayesian posterior mean strategy for log-concave models[END_REF] but the bounds are refined. In particular, compared to this paper, we precisely do not require that the step size decreases with d.

Thanks to the two previous results we are now able to control the moment of the continuous time and the discrete time processes.

Proposition 4.3. Assume (H 1 r ). (i) For all x ∈ R d , p ≥ 0, sup t≥0 E x [U p (X t )] p (U (x) + Ψ) p .
where

Ψ =    (1 + σ 2 ) 1 + dL c 1 1-r under (H 1 r ) only 4 1 1-r ∨ (1+σ 2 )(c∨L) c d
under (H 1 r ) and (H 2 r ),

(ii) Let γ ∈ (0, γ ⋆ ] with γ ⋆ defined by (11). Then,

sup n≥0 E x U p Xnγ p (U (x) + Ψ) p
where Ψ is defined by (11) (iii) In particular,

max sup t≥0 E x [U p (X t )] , sup t≥0,γ∈(0,γ ⋆ ] E x U p Xt r,p (U (x) + Ψ) p . ( 21
)
and

max U p (x)π(dx), sup γ∈(0,γ ⋆ ] U p (x)π γ (dx) r,p Ψp . ( 22
)
Proof. The proof similar to [GPP20, Prop B.4] is postponed in Appendix B.

Remark 4.2. In order to avoid the distinction between cases in all the proofs, we choose to adopt only one notation for Ψ and Ψ but the reader has to keep in mind that the definition of these quantities depends on the fact that (H 2 r ) is satisfied or not. Let us also recall that the notation r,p means that the constant only depends on r and p. These constants are certainly locally bounded: for any compact subset K of [0, 1) × [1, +∞), there exists a universal constant c such that for any (r, p) ∈ K, the underlying constant c r,p related to r,p is bounded by c. Finally, note that we chose to keep all the dependencies in the other parameters.

Longtime strong discretization error under (H 1 r ):

The following proposition studies the L 2 -error induced by the discretization of the SDE under (H 1 r ). The notations γ ⋆ and Ψ come from Proposition 4.3. Proposition 4.4. Assume (H 1 r ) and let x ∈ R d , γ ∈ (0, γ ⋆ ] and δ ∈ (0, 1). Then,

sup t≥0 E x |X t -Xt | 2 r Lγ cδ U (x) + Ψ 1+2r Γ 1 δ + (U (x) + Ψ) r+ 2δr 1-δ c 1+ 2δ 1-δ
where Γ is the gamma function.

Remark 4.3. The control of the L 2 -distance between the diffusion and its Euler scheme is a fundamental property for the efficiency of the multilevel method. Actually, it allows us to control the variance of each level. The fact that we are able to obtain such a property in this (semi)-weakly convex setting is new.

We start with two technical lemmas.

Lemma 4.2. Assume (H 1 r ) then for all x ∈ R d we have

|x -x ⋆ | 2 ≤ U 1+r (x) -U 1+r (x ⋆ ) c(1 + r) .
Proof. First, one can check that for all x ∈ R d and for all eigenvalue of the Hessian we have

λ D 2 U 1+r (x) ≥ (1 + r)U r (x)λ D 2 U(x) ≥ (1 + r)c, (23)
where in the last inequality we have used assumption (H 1 r ). By the Taylor formula,

U 1+r (x) -U 1+r (x ⋆ ) = ∇U 1+r (x ⋆ ), x -x ⋆ + 1 0 D 2 U 1+r (ξ θ )(x -x ⋆ ), x -x ⋆ dθ,
where ξ θ = λx + (1λ)x * . By (23) and the fact that ∇U 1+r (x ⋆ ) = 0, we get

U 1+r (x) -U 1+r (x ⋆ ) ≥ (1 + r)c 1 0 |x -x ⋆ | 2 dθ.
This concludes the proof.

The next lemma is a bound on the moments of the increment of the Euler scheme (with the notations γ ⋆ and Ψ introduced in Proposition 4.3).

Lemma 4.3. Assume (H 1 r ) with r ∈ [0, 1). Let γ ∈ (0, γ ⋆ ].
Then for all t > 0 and k ∈ N * ,

E x Xt -Xt 2k 1/k r,k L 2 (t -t) 2 U (x) + Ψ 1+r + (t -t)dσ 2 .
Proof. By the definition of the Euler scheme we have

E x Xt -Xt 2k 1/k = E x -(t -t)∇U Xt + σ(B t -B t ) 2 k 1/k ≤ E x 2(t -t) 2 ∇U Xt 2 + 2σ 2 B t -B t 2 k 1/k .
Then, by Minkowski inequality,

E x Xt -Xt 2k 1/k ≤ 2(t -t) 2 E x ∇U Xt 2k 1/k + 2σ 2 E x B t -B t 2k 1/k ≤ 2L 2 (t -t) 2 E x Xt -x ⋆ 2k 1/k + 2(t -t)σ 2 E x |Z| 2k 1/k ,
where in the last line we used the L-Lipschitz continuous property of ∇U and the fact that B t -B t ∼ √ t -tZ with Z ∼ N (0, Id). Finally, by Lemma 4.2 and Proposition 4.3, we obtain

E x Xt -Xt 2k 1/k ≤ 2L 2 (t -t) 2 1 + r sup n≥0 E[ U 1+r ( Xnγ ) 2k ] 1 2k + 2dσ 2 (2k)! 2 k k! 1/k (t -t) r,k L 2 (t -t) 2 U (x) + Ψ 1+r + (t -t)dσ 2 .
We are now ready to prove Proposition 4.4.

Proof. (of Proposition 4.4) Let x ∈ R d and consider the following process in

R d × R d , X t = x - t 0 ∇U (X s )ds + σB t Xt = Xt -(t -t)∇U ( Xt ) + σ B t -B t , with X0 = x. Denote by F x (t) := |X t -Xt | 2 . By the Lebesgue differentiability theorem, F ′ x (t) = 2 X t -Xt , ∇U ( Xt ) -∇U (X t ) = 2 X t -Xt , ∇U ( Xt ) -∇U (X t ) E1 +2 X t -Xt , ∇U ( Xt ) -∇U ( Xt ) E2 .
To control E 1 we use a Taylor expansion and obtain,

E 1 = -2 X t -Xt , 1 0 D 2 U λX t + (1 -λ) Xt (X t -Xt )dλ = -2 1 0 X t -Xt , D 2 U λX t + (1 -λ) Xt (X t -Xt ) dλ. Since D 2 U is a symmetric matrix, E 1 ≤ -2ξ t X t -Xt 2 ,
where

ξ t = 1 0 λ D 2 U(λXt+(1-λ) Xt) dλ.
For the second term E 2 , using the inequality a, b ≤ ξt 2 |a| 2 + 1 2ξt |b| 2 and the fact that ∇U is L-Lipschitz, we get

E 2 ≤ ξ t X t -Xt 2 + L 2 ξ t Xt -Xt 2 .
Thus,

F ′ x (t) ≤ -ξ t F x (t) + L 2 ξ t Xt -Xt 2 ,
and a Gronwall argument leads to

F x (t) ≤ t 0 L 2 ξ s Xs -Xs 2 e -t s ξudu ds.
Taking the expectation, the Fubini's theorem implies

E x |X t -Xt | 2 ≤ t 0 E x 1 ξ s Xs -Xs 2 e -t s ξudu
As ds.

Now let φ be a real non negative function, φ : t → φ(t)

A s ≤ E x 1 ξ s Xs -Xs 2 e -t s ξudu 1 { t s ξudu>φ(s)} + E x 1 ξ s Xs -Xs 2 e -t s ξudu 1 { t s ξudu≤φ(s)} ≤ E x 1 ξ s Xs -Xs 2 e -φ(s) A (1) s + E x 1 ξ s Xs -Xs 2 1 { t s ξudu≤φ(s)} A (2) s , (24)
Using (H 1 r ), the convexity of x → U (x) and t → t -r and the Jensen inequality, we have

ξ t = 1 0 λ D 2 U(λXt+(1-λ) Xt) dλ ≥ c 1 0 U -r λX t + (1 -λ) Xt dλ ≥ c 1 0 λU (X t ) + (1 -λ)U Xt -r dλ ≥ c 1 0 λU (X t ) + (1 -λ)U Xt dλ -r ≥ 2 r c U (X t ) + U Xt -r .
Thus by the inequality (a + b) p ≤ a p + b p for a, b ≥ 0 and p ∈ [0, 1],

ξ -1 t ≤ 1 2 r c U (X t ) + U Xt r ≤ 1 2 r c U r (X t ) + U r Xt . (25)
By Cauchy-Schwarz inequality, Proposition 4.3(iii) and Lemma 4.3 we get

A (1) s ≤ E[ξ -2 s ] 1 2 E[| Xs -Xs | 4 ] 1 2 e -φ(s) r e -φ(s) c -1 U (x) + Ψ r L 2 (s -s) 2 U (x) + Ψ 1+r + (s -s)dσ 2 r e -φ(s) Lγ c U (x) + Ψ 1+2r , (26)
where in the last line, we used that dσ 2 ≤ Ψ and γL ≤ 1.

For the second term use Cauchy-Schwarz inequality,

A (2) s ≤ E x 1 ξ s Xs -Xs 2 2 1/2 P x t s ξ u du ≤ φ(s) 1/2 ≤ E x 1 ξ 4 s 1/4 E x Xs -Xs 8 1/4 P x t s ξ u du ≤ φ(s) 1/2
.

With the help of Inequality (25) and Proposition 4.3, we have

A (2) s r c -1 U (x) + Ψ r L 2 (s -s) 2 U (x) + Ψ 1+r + (s -s)dσ 2 P x t s ξ u du ≤ φ(s) 1/2 .
For the third term of this product, let κ be a positive number and use Markov inequality:

P x t s ξ u du ≤ φ(s) 1/2 ≤ P x t s ξ u du -κ ≥ φ κ (s) 1/2 ≤ φ κ/2 (s)E t s ξ u du -κ 1/2 .
The function x → x -κ being convex on (0, +∞) it follow from Jensen inequality that

P x t s ξ u du ≤ φ(s) 1/2 ≤ φ κ/2 (s)(t -s) -κ/2 E 1 t -s t s ξ -κ u du 1/2 .
Using again inequality (25) and Proposition 4.3,

P x t s ξ u du ≤ φ(s) 1/2 r c -κ 2 φ(s) t -s κ/2 sup u∈[s,t] E U κr (X t ) + U κr Xt 1/2 r c -κ 2 φ(s) t -s κ/2 U (x) + Ψ κr 2 .
Finally, we get

A (2) s r c -1-κ 2 U (x) + Ψ r+ κr 2 L 2 (s -s) 2 U (x) + Ψ 1+r + (s -s)dσ 2 φ(s) t -s κ/2
. Now let φ(s) = t-s (t+1-s) 1-δ with a > 0, δ ∈ (0, 1) and κ = 2(1+δ) 1-δ we have

A (2) s r c -2-2δ 1-δ L 2 (s -s) 2 (U (x) + Ψ) 1+3r+ 2δr 1-δ + (s -s)dσ 2 (U (x) + Ψ) 2r+ 2δr 1-δ 1 t + 1 -s 1+δ .
As a consequence, since γL ≤ 1 and dσ 2 ≤ Ψ, we obtain

A (2) s r Lγ c 2+ 2δ 1-δ (U (x) + Ψ) 1+3r+ 2δr 1-δ 1 t + 1 -s 1+δ .
Back to (24), we deduce from (26) and from the above inequality that

E x |X t -Xt | 2 ≤ t 0 A (1) s ds + t 0 A (2) s ds r Lγ c U (x) + Ψ 1+2r t 0 e - u (u+1) 1-δ du + (U (x) + Ψ) r+ 2δr 1-δ c 1+ 2δ 1-δ t 0 1 1 + u 1+δ du r Lγ c U (x) + Ψ 1+2r t 0 e -u δ du + (U (x) + Ψ) r+ 2δr 1-δ δc 1+ 2δ 1-δ r Lγ cδ U (x) + Ψ 1+2r Γ 1 δ + (U (x) + Ψ) r+ 2δr 1-δ c 1+ 2δ 1-δ
The result follows.

Convergence to equilibrium for the Euler Scheme under (H 1 r ):

We now proceed to establish the weak error between the discrete semi group and its invariant measure denoted by π γ . The proof of this result is based on the control of the so-called tangent process T x t := ∇X x t .

Proposition 4.5. Assume (H 1 r ) and let x ∈ R d , γ ∈ (0, γ ⋆ ]. Let κ > 0 and φ : R + → R be a positive function. Assume that U (x) r Ψ. Then, for any r ∈ [0, 1), there exists a constant c r,κ (depending only on r and κ) such that for all n > 0, for all Lipschitz continuous function f : R d → R,

E x f ( Xnγ ) -π γ (f ) ≤ c r,κ [f ] 1 h φ,κ (n), where h φ,κ (n) = c -1 2 Ψ 1+r 2 e -φ(n) + c -κ+1 2 Ψ 1+r(1+κ) 2 φ(n) nγ κ 2
, with γ ⋆ and Ψ defined in Proposition 4.3.

Remark 4.4. ⊲ In order to alleviate the purpose, the result is stated under the assumption that the initial condition x satisfies U (x) r Ψ but the reader will find some bounds without this assumption in the proofs.

⊲ The function h φ,κ plays the role of convergence rate to equilibrium. In this setting where the Hessian is not lower-bounded, we adopt a strategy which consists in separating the space into two parts. In the first one, we assume that we have some good contraction properties parametrized by the function φ and in the other one, we try simply to control the probability that such a good contraction does not occur. This leads to a balance between two terms depending on φ and κ. In the following, we will choose φ and κ in order that h φ,κ is summable with the smallest impact on the dependence in the dimension.

Note that in [START_REF] Cattiaux | Self-improvement of the Bakry-Emery criterion for Poincaré inequalities and Wasserstein contraction using variable curvature bounds[END_REF], some exponential rates are exhibited under similar assumptions in the continuous case (with the help of concentration inequalities). However, this exponential rate depends on some constants whose control seems to be difficult to obtain (typically, when the starting distribution is absolutely continuous with respect to the invariant distribution, the constants involve the L 2 -moment of the related density). Probably, some ideas could be adapted to the Euler scheme (starting from a deterministic point) but with technicalities that seem to carry us too far for this paper.

We preface the proof of Proposition 4.5 by a lemma about the shape of the first variation process of the continuous time Euler scheme, T x t = ∇ x Xx t .

Lemma 4.4. For all n ∈ N, x ∈ R d and γ ∈ [0, 1),

T x (n+1)γ = n i=0 Id R d -γD 2 U Xx iγ .
Proof. (of Lemma 4.4) First, observe that for all n ∈ N,

T x (n+1)γ -T x nγ γ = ∇ x Xx (n+1)γ -Xx nγ γ ,
and by the definition of the Euler scheme and the chain rule,

T x (n+1)γ -T x nγ γ = ∇ x -∇ x U Xx nγ + σ B (n+1)γ -B (n-1)γ = -D 2 U Xx nγ T x nγ .
Then we get, T

x (n+1)γ = T x nγ Id R d -γD 2 U Xx nγ ,
and the proof follows by a simple induction.

Consider two paths defined with the same Brownian motion and different starting points: x, y ∈ R d . The following proposition shows that there is a pathwise confluence, i.e. the two trajectories get closer when n goes to infinity. Proposition 4.6. Assume (H 1 r ) and let x, y ∈ R d , γ ∈ (0, γ ⋆ ], κ > 0. Let φ : R + → R be a positive function. Then,

sup n≥0 E (x,y) Xx nγ -Xy nγ 2 r,κ |x -y| 2 h φ,κ,x,y (n),
where,

h φ,κ,x,y (n) = e -2φ(n) + φ(n) nγ κ c -κ (U (x) + U (y) + Ψ) κr ,
with γ ⋆ and Ψ given by Proposition 4.3.

Remark 4.5. In the sequel, this property is typically applied with a polynomial function φ which leads to polynomial rates to equilibrium. It is worth noting that the proof could be adapted to provide exponential rates (the idea would be to consider an exponentially decreasing convex function instead of x → x -κ in the proof below). However, with our method, such rates would lead to exponential dependence in the dimension. This is why we do not give such bounds here.

Proof. (of Proposition 4.6) For x, y ∈ R d and n ∈ N, let us start by a Taylor expansion of the function

x → Xx nγ , Xx nγ -Xy nγ 2 = 1 0 T λx+(1-λ)y nγ (x -y)dλ 2 = |x -y| 2 1 0 T λx+(1-λ)y nγ dλ x -y |x -y| 2 ≤ |x -y| 2 1 0 T λx+(1-λ)y nγ dλ 2 ,
where . is the operator norm associated with the Euclidean norm. By Jensen inequality and Lemma 4.4,

Xx nγ -Xy nγ 2 ≤ |x -y| 2 1 0 n-1 i=0 Id R d -γD 2 U Xλx+(1-λ)y iγ 2 dλ ≤ |x -y| 2 1 0 n-1 i=0 Id R d -γD 2 U Xλx+(1-λ)y iγ 2 dλ.
The operator norm associated with the Euclidean norm of a symmetric matrix is equal to its spectral radius, so we get

Xx nγ -Xy nγ 2 ≤ |x -y| 2 1 0 n-1 i=0 1 -γλ D 2 U Xλx-(1-λ)y iγ 2 dλ ≤ |x -y| 2 1 0 e -2γ n-1 i=0 λ D 2 U ( Xλx-(1-λ)y iγ ) dλ, and
E (x,y) Xx nγ -Xy nγ 2 ≤ |x -y| 2 1 0 E (x,y) e -2ξn(λ) dλ, (27)
with,

ξ n (λ) := γ n-1 i=0 λ D 2 U Xλx-(1-λ)y iγ = nγ 0 λ D 2 U Xλx-(1-λ)y u du.
For a given real non negative function φ : R → R we have

E (x,y) e -2ξn(λ) ≤ E (x,y) e -2ξn 1 {ξn>φ(n)} + E (x,y) e -2ξn 1 {ξn≤φ(n)} ≤ e -2φ(n) + E (x,y) 1 {ξn≤φ(n)} ≤ e -2φ(n) + P (x,y) nγ 0 λ D 2 U Xλx-(1-λ)y u du ≤ φ(n) .
For a positive number κ we have

E (x,y) e -2ξn(λ) ≤ e -2φ(n) + P (x,y) nγ 0 λ D 2 U Xλx-(1-λ)y u du -κ ≥ φ -κ (n) ,
and using the Markov inequality,

E (x,y) e -2ξn(λ) ≤ e -2φ(n) + φ κ (n)E (x,y) nγ 0 λ D 2 U Xλx-(1-λ)y u du -κ
.

The function x → x -κ is convex on (0, +∞) then by Jensen inequality,

E (x,y) e -2ξn(λ) ≤ e -2φ(n) + φ κ (n)(nγ) -κ E (x,y) 1 nγ nγ 0 λ -κ D 2 U Xλx-(1-λ)y u du ≤ e -2φ(n) + φ(n) nγ κ sup k∈{0,...,n-1} E λ -κ D 2 U Xλx-(1-λ)y kγ .
Observe that assumption (H 1 r ) implies,

E (x,y) e -2ξn(λ) ≤ e -2φ(n) + φ(n) nγ κ sup k∈{0,...,n-1} E c -κ U κr Xλx+(1-λ)y kγ .
By Proposition 4.3 and the convexity of U , this implies that for any γ ∈ (0, γ ⋆ ],

E (x,y) e -2ξn(λ) r,κ e -2φ(n) + φ(n) nγ κ c -κ (U (x) + U (y) + Ψ) κr .
Thanks to this confluence property we are now able to prove the convergence to equilibrium of the Euler scheme and to give the rate of this convergence.

Proof. (of Proposition 4.5) Since π γ is invariant for Xnγ n∈N we deduce from Fubini's Theorem and Jensen inequality that

E x f ( Xnγ ) -π γ (f ) 2 = R d E (x,y) f ( Xx nγ ) -f ( Xy nγ ) π γ (dy) 2 ≤ R d E (x,y) f ( Xx nγ ) -f ( Xy nγ ) 2 π γ (dy).
The Lipschitz property of f implies that

E x f ( Xnγ ) -π γ (f ) 2 ≤ [f ] 2 1 R d E (x,y) Xx nγ -Xy nγ 2 π γ (dy),
where [f ] 1 is the Lipschitz constant of f . Proposition 4.6 implies

E x f ( Xnγ ) -π γ (f ) 2 r,κ [f ] 2 1 R d |x -y| 2 h φ,κ,x,y (n)π γ (dy). (28) By Lemma 4.2, |x -y| 2 ≤ 2(|x -x ⋆ | 2 + |y -y ⋆ | 2 ) ≤ 2 c(1 + r) U 1+r (x) + U 1+r (y) .
With the help of the Young inequality, we also have

|x -y| 2 (U (x) + U (y)) rκ r,κ c -1 U 1+r(1+κ) (x) + U 1+r(1+κ) (y) .
Plugging these controls into (28) yields

E x f ( Xnγ ) -π γ (f ) 2 r,κ [f ] 2 1 c U 1+r (x) + π γ (U 1+r ) e -2φ(n) + [f ] 2 1 c -κ-1 U 1+r(1+κ) (x) + π γ (U 1+r(1+κ) ) φ(n) nγ κ . + [f ] 2 1 c -κ-1 Ψrκ U 1+r (x) + π γ (U 1+r ) φ(n) nγ κ . ( 29
)
To conclude, we now use the bound (22) of Proposition 4.3(iii) and the assumption U (x) r Ψ.

Bias induced by the discretization under (H 1 r ):

We now need to provide estimates of W 1 (π, π γ ). We provide two results: Lemma 4.5 where we directly derive from Proposition 4.4 a bound in O( √ γ) which "only" requires the potential U to be C 2 . However, such a bound has a serious impact on the dependency in ε of the complexity. Thus, we propose a second result when U is C 3 where we recover a bound in O(γ).

A first bound in O( √ γ)

As mentioned before, a first estimate can be directly deduced from Proposition 4.4. Actually, since in this result, the L 2 -error between the process and its discretization is controlled uniformly in this leads to a similar bound for W 1 (π, π γ ) by letting t go to ∞. More precisely,

Lemma 4.5. Assume (H 1 r ). Let γ ∈ (0, γ ⋆ ]. Then, W 1 (π, π γ ) 2 r,δ Lγ c 2 1-δ ∧ c Ψ1+3r+ 2δr 1-δ . ( 30
)
Proof. Owing to the stationarity of π, we have for every n ≥ 0,

W 1 (π, π γ ) ≤ W 1 (πP nγ , π Pnγ ) + W 1 (π Pnγ , π γ ), so that W 1 (π, π γ ) ≤ lim sup n→+∞ W 1 (πP nγ , π Pnγ ), since W 1 (π Pnγ , π γ )
n→+∞ -----→ 0 by Proposition 4.5 (more precisely, this property can be deduced from an integration of (29) with respect to π and from the fact that π(U p ) < +∞ for any p by Proposition 4.3). Now, integrating with respect to π the bound of Proposition 4.4 and using that π(U p ) r

Ψp by Proposition 4.3 leads to the result.

A second bound in O(γ)

Even if the above bound is quite explicit in terms of its dependency with respect to L, c, c and d, the fact that it is in O( √ γ) dramatically impacts the complexity in terms of ε (at least).

In fact, it is possible to get a 1-Wasserstein error of the order γ by using a combination of the control of the rate of convergence to equilibrium of the continuous process and of the finite-time weak error (between the process and its discretization). Such a strategy is used in several papers : in [PPar], this idea is developed in a multiplicative setting with a so-called "domino" approach for the control of the 1-Wasserstein and T V distances between the process and its discretization, uniformly in time. For the control of W 1 (π, π γ ) itself, our approach follows [START_REF] Durmus | Asymptotic bias of inexact markov chain monte carlo methods in high dimension[END_REF] which provides a series of bounds in many models and sets of assumptions which are mainly based on the following principle (see Lemma 1 of [START_REF] Durmus | Asymptotic bias of inexact markov chain monte carlo methods in high dimension[END_REF]). Taking advantage of the stationarity of π γ , for any p ≥ 1, for any t > 0,

W p (π, π γ ) ≤ W p (π, π γ P t ) + W p (π γ P t , π γ Pt ),
so that if we assume that

W p (π, π γ P t ) ≤ ε 1 (t)W p (π, π γ ) and W p (π γ P t , π γ Pt ) ≤ ε 2 (t), then, W p (π, π γ ) ≤ inf ε 2 (t) 1 -ε 1 (t) , t > 0 . ( 31
)
We thus propose to estimate ε 1 (t) and ε 2 (t) under Assumption (H 1 r ) (with or without (H 2 r )). This is the purpose of Lemmas 4.6 and 4.7 respectively. These two estimates lead to the following proposition Proposition 4.7. Assume (H 1 r ) and let δ ∈ (0, 1). Assume that U is C 3 with ∆(∇U ) 2 2,∞ r σ -4 L 3 Ψ (with ∆(∇U ) 2,∞ defined in Lemma 4.7). Then, a constant c r,δ (depending only on r and δ) exists such that for all γ ∈ (0, γ ⋆ ],

W 2 (π, π γ ) ≤ c r,δ c -1 1-δ L 3 2 Ψ 1 2 + r 1-δ γ.
Remark 4.6. ⊲ Note that this result is clearly in the spirit of [DE21, Theorem 6]. However, there are several differences. First, we need here to adapt our proof to a setting where we only have polynomial convergence to equilibrium (instead of exponential convergence). Second, under our assumptions on U which are more restrictive than the one of [DE21, Theorem 6], we can improve the constants (and in particular avoid some exponential dependence in the Lipschitz constant L).

⊲ Compared with Lemma 4.5 , this result improves the dependence in γ but it is worth noting that the bound is also better with respect to Ψ (and thus to the dimension).

Proof. With the notations of [DE21, Theorem 6], let t rel = inf{t > 0, ε 1 (t) ≤ 1/ √ 2}. Using Lemma 4.6, one can upper-bound t rel by asking the two right-hand terms of (32) to be bounded by 1/4. With φ(t) = t δ with δ ∈ (0, 1), this leads to: t rel r max{(log 4) δ , (4c -1 )

1 1-δ Ψ r 1-δ }.
By (31) and Lemma 4.7(ii), we get for any λ ∈ (0, 1],

W 2 (π, π γ ) ≤ c r γ λ e λt rel L 3 Ψ. Let λ = t -1 rel .
In this case, we obtain

W 2 (π, π γ ) ≤ c r γt rel L 3 Ψ r,δ γc -1 1-δ L 3 2 Ψ 1 2 + r 1-δ .
Lemma 4.6. Assume (H 1 r ). Then, for any γ ∈ (0, γ ⋆ ] and for any positive function φ : R + → R,

W 2 2 (π, π γ P t ) r W 2 2 (π, π γ ) e -2φ(t) + φ(t) ct Ψr . (32)
Remark 4.7. ⊲ The proof of (i) is mostly a continuous-time version of the one of Proposition 4.6.

⊲ As mentioned in Remark 4.5, the proof can be adapted to provide exponential rates but unfortunately our method would lead to exponential dependence in the dimension. For this section, the lack of exponential rate does not have a serious impact on the bounds. Nevertheless, if we needed to improve our bounds, an idea would be to apply [CFG22, Theorem 5.6]. In this result, the authors provide exponential rates under assumptions which are similar to ours. However the related constant depends on the density of the semi-group and it would be necessary to be able to control it with respect to the parameters of the model.

Proof. Denoting by T x t = ∂ x X x t , the first variation process related to (X x t ) t≥0 , we have:

X y t -X x t = 1 0 T x+λ(y-x) t (y -x)dλ.
Thus,

|X y t -X x t | 2 ≤ 1 0 T x+λ(y-x) t 2 |y -x| 2 dλ,
where . stands for the operator norm associated with the Euclidean norm. Since T x is the solution to

dT x t = -D 2 U (X x t )T x t dt with T x 0 = I d , one easily checks that T x+λ(y-x) t 2 ≤ e -2 t 0 λ U (X x+λ(y-x) s )ds .
Thus,

|X y t -X x t | 2 ≤ |x -y| 2 1 0 e -2 t 0 λ U (X x+λ(y-x) s
)ds dλ.

Following the arguments of Proposition 4.6, we get for any positive function φ,

E e -2 t 0 λ U (X x+λ(y-x) s )ds ≤ e -2φ(t) + φ(t) t E 1 t t 0 λ -1 D 2 U X x+λ(y-x) u du ≤ e -2φ(t) + φ(t) t sup s∈[0,t]} E λ -1 D 2 U X x+λ(y-x) s
.

By (H 1 r ), one deduces that

E[|X y t -X x t | 2 ] ≤ |x -y| 2 e -2φ(t) + φ(t) ct sup t≥0]} E U r X (1-λ)x+λy t uc |x -y| 2 e -2φ(t) + φ(t) ct (U r (x) + U r (y) + Ψ r ) ,
where in the second line, we used Proposition 4.3 and the convexity of U . Let now ν be a coupling of π and π γ . We have

W 2 2 (π, π γ P t ) ≤ |x -y| 2 (ν(dx, dy) e -2φ(t) + φ(t) ct (π(U r ) + π γ (U r ) + Ψ r ) .
Taking the infimum over the set of couplings ν of π and π γ and using again Proposition 4.3, this yields

W 2 2 (π, π γ P t ) r W 2 2 (π, π γ ) e -2φ(t) + φ(t) ct Ψr Lemma 4.7. (i) Let U be a C 3 -convex function. Then, E[|X x γ -Xy γ | 2 ] ≤ |x -y| 2 e λγ + c γ,λ (x, y)γ 3 . with c γ,λ (x, y) = e λγ 6λ L 2 |∇U (y)| 2 + σ 4 ∆(∇U ) 2 2,∞ + 2λσL D 2 U 2,∞ ( √ γ)
where

D 2 U 2,∞ = sup x∈R d D 2 U F , ∆(∇U ) 2,∞ = sup x∈R d d i=1 |∆∂ i U | 2 , and S(x, γ) = sup u∈[0,γ] E[|b(X x u )| 2 ] 1 2 . (ii) Let (H 1 r ) hold. Assume that U is C 3 with ∆(∇U ) 2 2,∞ r σ -4 L 3 Ψ.
Then, a constant c r exists such that for all γ ∈ (0, γ ⋆ ], for all λ ∈ (0, 1],

W 2 2 (π γ P nγ , π γ ) ≤ c r γ 2 λ 2 e λ(n+1)γ L 3 Ψ.
Remark 4.8. The assumption on ∆(∇U ) is calibrated to control its contribution by L 3 Ψ. That simplifies the purpose and we could keep its specific contribution at the price of technicalities. However, this assumption is not really restrictive: denoting by A(x) the d × d-matrix defined by A i,j (x) = D 3 i,j,j U (x). One easily checks that ∆(∇U ) 2 2,∞ = sup

x∈R d A(x) 2 F ≤ d sup x∈R d λA(x) ,
the second inequality coming from a classical inequality related to the Frobenius norm. Since L ≥ sup x∈R d λD 2 U(x) , the assumption is for instance true if sup

x∈R d λA(x) ≤ σ -2 sup x∈R d ( λD 2 U(x) ) 4 Ψ σ 2 dL .
To conclude, note that Ψ σ 2 dL is well controlled: for instance, under (H 1 r ) and (H 2 r ), Ψ

σ 2 dL r c -1 c L ∨ 1 .
Remark 4.9. The calibration of the parameter λ is of first importance in the proof of Proposition 4.7 in order to avoid exponential dependence in the dimension.

Proof. The proof is an adaptation of Lemma 5.2 and Proposition 5.3 of [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF] but with the viewpoint that U is only convex. More precisely, we start with a one-step control of the error between the diffusion and its Euler scheme by setting

F x,y (t) = 1 2 E[|X x t -Xy t | 2 ], t ∈ [0, γ].
Then, setting b = -∇U , we have

F ′ x,y (t) = E X x t -Xy t , b(X x t ) -b(y) = E X x t -Xy t , b(X x t ) -b( Xy t ) + E X x t -Xy t , b( Xy t ) -b(y) ≤ E X x t -Xy t , b( Xy t ) -b(y) ,
where in the last line we used the convexity of U which involves that ∇U (x) -∇U (y), xy ≥ 0.

We then write

E X x t -Xy t , b( Xy t ) -b(y) = E X x t -Xy t , b( Xy t ) -b(y + σB t ) (33) + E X x t -Xy t , b(y + σB t ) -b(y) . (34)
Let λ > 0. For the right-hand side of (33), we use the elementary inequality, |uv| ≤ λ

2 |u| 2 + 1 2λ |v| 2 to obtain E X x t -Xy t , b( Xy t ) -b(y + σB t ) ≤ λ 2 F x,y (t) + t 2 2λ L 2 |b(y)| 2 . (35)
For (34), the Itô formula applied to

b i = -∂ i U leads to b i (y + σB t ) -b i (y) = σ 2 t 0 ∆b i (y + σB s )ds + σ t 0 ∇b i (y + σB s ), dB s .
On the one hand, setting ∆b = (∆b i ) d i=1 ,

E X x t -Xy t , σ 2 t 0 ∆b(y + σB s )ds ≤ λ 2 F x,y (t) + σ 4 2λ t 2 ∆b 2 2,∞ , where ∆b 2 2,∞ = sup x∈R d d i=1 |∆b i (x)| 2 .
On the other hand, using the fact that M defined by M t = t 0 ∇b(y + σB s ), dB s is a martingale (we refer to [START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF] for the details), we get

|E X x t -Xy t , σ t 0 ∇b(y + σB s ), dB s | ≤ σL ∇b 2,∞ s 3 2 S(x, γ) + σs √ d , where S(x, γ) = sup u∈[0,γ] E[|b(X x u )| 2 ] 1 2 and ∇b 2,∞ = sup x∈R d ∇b(x) F .
Finally, from what precedes, we deduce that

F ′ x,y (t) ≤ λF x,y (t) + t 2 2λ L 2 |b(y)| 2 + σ 4 ∆b 2 2,∞ + 2λL ∇b 2,∞ √ tS(x, γ) + σ √ d .
A standard Gronwall argument then leads to

E[|X x γ -Xy γ | 2 ] ≤ |x -y| 2 e λγ + γ 0 s 2 e λ(γ-s) ds L 2 |b(y)| 2 + σ 4 ∆b 2 2,∞ + 2λσL ∇b 2,∞ √ tS(x, γ) + σ √ d ≤ |x -y| 2 e λγ + γ 3 c γ,λ (x, y) with c γ,λ (x, y) = e λγ 6λ L 2 |b(y)| 2 + σ 4 ∆b 2 2,∞ + 2λσL ∇b 2,∞ √ γS(x, γ) + σ √ d .
(ii) Iterating the above inequality, we obtain for each n ≥ 1,

E[|X x nγ -Xx nγ | 2 ] ≤ γ 3 n-1 k=0 E[c γ,λ (X x kγ , Xx kγ ))]e λ(n-k)γ
Integrating the initial condition with respect to π γ , we get

W 2 (π γ P nγ , π γ ) ≤ γ 2 e λnγ sup k≥0 E[c γ,λ (X x kγ , Xx kγ ))]π γ (dx) ≤ γ 2 λ 2 e λ(n+1)γ L 2 π γ (|b| 2 ) + σ 4 ∆b 2 2,∞ + 2λσL ∇b 2,∞ √ γ sup n≥0 E[S(X x nγ , γ)]π γ (dx) + σ √ d ,
where in the second line, we used the stationarity property of π γ . Now, under (H 1 r ), |b| 2 = |∇U | 2 ≤ 2LU (with the same idea than one which leads to (18)) so that by Proposition 4.3(iii), π γ (|b| 2 ) r L Ψ. On the other hand, by the Itô formula and the fact that ∆U ≤ dL,

E[U (X x t )] ≤ U (x) + σ 2 t 0 E[∆U (X x s )]ds ≤ U (x) + σ 2 dL, so that S(x, γ) ≤ √ 2L sup u∈[0,γ] E[U (X x u )] 1 2 ≤ 2LU (x) + σ √ 2dL.
Again, with the help of Proposition 4.3(iii),

sup n≥0 E[S(X x nγ , γ)]π γ (dx) r √ L Ψ 1 2 + σ √ dL.
Thus, using that γ ≤ L -1 ,

W 2 (π γ P nγ , π γ ) r γ 2 λ 2 e λ(n+1)γ L 3 Ψ + σ 4 ∆b 2 2,∞ + σλ ∇b 2,∞ ( Ψ + σ √ dL) .
Since for a symmetric d × d-matrix A, A F ≤ √ d λA , one deduces that ∇b 2,∞ = D 2 U 2,∞ ≤ √ dL. It easily follows that σλL ∇b 2,∞ ( √ Ψ + σ √ dL) ≤ L 3 Ψ (using that L ≥ 1 and Ψ ≥ d). The result follows.

5 Proof of Theorem 2.2

Following the bias-variance decomposition of the MSE:

Y(f ) -π(f ) 2 2 ≤ [E[Y(f )] -π(f )] 2 + Var(Y(f ))
, we successively study the bias and the variance contributions and end the section by the proof of Theorem 2.2.

Step 1: Bias of the procedure

In the sequel, Y(J, (γ j ) j , τ, (T j ) j , f ) is usually written Y for the sake of simplicity. We start with a telescopictype decomposition:

Y(f ) -π(f ) = 1 T 0 T0 0 f ( Xγ0,x0 s γ 0 ) -π γ0 (f )ds + J j=1 1 T j Tj 0 f ( Xγj,x0 s γ j-1 ) -π γj (f )ds - 1 T j Tj 0 f ( Xγj-1,x0 s γ j-1
)π γj-1 (f )ds

+ π γJ (f ) -π(f ). ( 36
)
Let us now study the bias generated by the first and second terms of the right-hand side of (36).

Lemma 5.1. Assume (H 1 r ) and γ 0 ∈ (0, γ ⋆ ]. Let x ∈ R d such that U (x) r Ψ. Then, for any r ∈ [0, 1) and δ ∈ (0, 1 2 ], there exists a constant c r,δ (depending only on r and δ) such that for all T ≥ 1, for all Lipschitz continuous function f : R d → R,

1 T T 0 E x [f ( Xγ,x0 s )] -π γ (f )ds 2 ≤ c r,δ [f ] 2 1 C (1) bias T 2 with C (1) bias = c -1 2 ∨ c -3-4δ 1-δ Ψ1+3r+ 4δr 1-δ .
Proof. Let us apply Proposition 4.5 with

φ(n) = nγ (nγ+1) 1-δ and κ = 2(1+δ) 1-δ = 2 + 4δ 1-δ for δ ∈ (0, 1/2]. Using that φ(n) ≥ (nγ) δ , we have 1 T T 0 E x [f ( Xγ,x0 s )] -π γ (f )ds r,κ [f ] 1 T T 0 h φ,κ (s)ds r [f ] 1 T c -1 2 Ψ 1+r 2 T 0 e -t δ dt + c -3 2 -2δ 1-δ Ψ 1+3r 2 + 2δr 1-δ T 0 (1 + t) -1-δ dt r [f ] 1 δT Γ 1 δ c -1 2 Ψ 1+r 2 + c -3 2 -2δ 1-δ Ψ 1+3r 2 + 2δr 1-δ
, where in the last line, we used standard arguments of comparisons between series and integrals. The result follows.

We are now ready to state a proposition about the control of the bias of the procedure.

Proposition 5.1. Assume (H 1 r ) and γ 0 ∈ (0, γ ⋆ ]. Let x ∈ R d such that U (x) r Ψ. Let δ ∈ (0, 1 2 ] and let f be a continuous Lipschitz function with

[f ] 1 = 1. Let J ∈ N * . Then, (i) |E x [Y(f )] -π(f )| 2 r,δ C (1) bias J j=0 1 T 2 j + C (2,1) bias γ J with C (2,1) bias = L c 2 1-δ ∧ c Ψ1+3r+ 2δr 1-δ .
(ii) If the assumptions of Proposition 4.7 are fulfilled,

|E x [Y(f )] -π(f )| 2 r,δ C
(1) bias

J j=0 1 T 2 j + C (2,2) bias γ 2 J with C (2,2) bias = c -2 1-δ L 3 Ψ1+ 2r 1-δ .
Proof. (i) Taking the expectation in (36), we obtain:

|E x [Y(f ) -π(f )]| ≤ 1 T 0 T0 0 E x0 f ( Xγ0,x0 s γ 0 ) -π γ0 (f )ds + J j=1 1 T j Tj 0 E f ( Xγj,x0 s γ j-1
)π γj (f )ds

+ J j=1 1 T j Tj 0 E f ( Xγj-1,x0 s γ j-1 ) -π γj-1 (f )ds + |π γJ (f ) -π(f )| .
For the three first terms, we apply Lemma 5.1 and for the last one, Lemma 4.5. The result follows.

(ii) It is the same proof using Proposition 4.7 to control the last term (instead of Lemma 4.5).

Step 2 : Control of the variance

Now we have to control the variance of our estimator. Owing to the independency between the layers, Var(Y(J, (γ j ) j , (T j ) j , f

)) = Var 1 T 0 T0 0 f ( Xγ0,x s γ 0 )ds + J j=1 Var 1 T j Tj 0 G γj s ds , (37)
where for some given γ > 0 and s > 0,

G γ s = f X γ 2 ,x s γ -f Xγ,x s γ .
Before going further, let us recall that in order that the multilevel method be efficient, the correcting layers must have a small variance. In the long-time setting, this involves to be able to control the L 2 -distance between couplings of Euler schemes with steps γ and γ/2. By Proposition 4.4, this is still possible under (H 1 r ), and such a property allows to obtain the following result: Lemma 5.2. Assume (H 1 r ) and γ 0 ∈ (0, γ ⋆ ]. Let x ∈ R d such that U (x) r Ψ. Let δ ∈ (0, 1 2 ] and κ > 2 1-δ . Let f be a continuous Lipschitz function.Then, for all T > 0,

Var 1 T T 0 G γ s ds r,δ,κ [f ] 2 1 C (1) var (κ, δ)γ 1-1 κ(1-δ) T ,
where

C (1) var (κ, δ) = L 1-1 κ(1-δ) (c -3-δ κ(1-δ) 2 ∨ c - 3+κ-(κ+1)δ κ(1-δ) 2 ) Ψ1+(4-2 κ )r+ε(δ,κ)r with ε(δ, κ) = 3 - 2 κ - 2 κ(1 -δ) δ 1 -δ .
Let us study the two right-hand members successively. For (40), the Cauchy-Schwarz inequality and (38) yield:

E F γ 2 , s γ -u γ , X γ 2 ,x u γ -F γ, s γ -u γ , Xγ,x u γ G γ u r,δ F γ 2 , s γ -u γ , X γ 2 ,x u γ 2 + F γ, s γ -u γ , Xγ,x u γ 2 Lγ c 2 1-δ Ψ1+3r+ 2δr 1-δ .
By Proposition 4.5 or more precisely by (29) combined with Proposition 4.3(iii)9 applied with φ(n) = (nγ) δ ,

F γ 2 , s γ -u γ , X γ 2 ,x u γ 2 + F γ, s γ -u γ , Xγ,x u γ 2 r,δ,κ c -1 2 Ψ 1+r 2 e -(s γ -u γ ) δ +c -κ+1 2 Ψ 1+r(1+κ) 2 (s γ -u γ ) -κ(1-δ) 2 .
Now, let us remark that if su ≥ t 0 , t 0 ≥ 2 and γ ∈ (0, γ ⋆ ], then s γu γ ≥ 1 (since γ ⋆ ≤ 1). Noting that for any t ≥ 1, e -t δ δ t -κ(1-δ)

2
and that for any κ > 2 1-δ ,

T (u+t0)∧T (s γ -u γ ) -κ(1-δ) 2 ds ≤ +∞ u+t0 (s -u -γ) -κ(1-δ) 2 ds ≤ (t 0 -γ) 1-κ(1-δ) 2 κ(1-δ) 2 -1 κ,δ t 0 2 1-κ(1-δ) 2
we deduce that for any t 0 ≥ 2 and for any γ ∈ (0,

γ ⋆ ] T (u+t0)∧T E F γ 2 , s γ -u γ , X γ 2 ,x u γ -F γ, s γ -u γ , Xγ,x u γ G γ u ds r,δ,κ (γL)
1 2 Ψ1+2r+ δr 1-δ + κr 2 c 3 2 + δ 1-δ ∧ c 3+κ 2 + δ 1-δ t 0 2 1-κ(1-δ) 2 .
For (41), using that s γ ≥ s γu γ , we remark that we can obtain the same bound so that:

T (u+t0)∧T Cov (G γ s , G γ u ) ds r,δ,κ (γL)
1 2 c 3 2 + δ 1-δ ∧ c 3+κ 2 + δ 1-δ Ψ1+2r+ δr 1-δ + κr 2 t 0 2 1-κ(1-δ) 2 .
In view of the above bound and of the one obtained in (39), we now optimize the choice of t 0 by taking t 0 solution to: (γL)

1 2 c 3 2 + δ 1-δ ∧ c 3+κ 2 + δ 1-δ Ψ1+2r+ δr 1-δ + κr 2 t 0 2 1-κ(1-δ) 2 = Lγt 0 c 2 1-δ Ψ1+3r+ 2δr 1-δ . i.e., t 0 = 2 1-2 κ(1-δ) (c 1 2 + δ 1-δ ∨ c 1-κ 2 + δ 1-δ ) 2 κ(1-δ) (Lγ) -1 κ(1-δ) Ψ(1-2 κ ) r 1-δ - 2δ κ(1-δ) 2 r .
Plugging this value of t 0 into (39), this leads to: for any κ > 2 1-δ ,

T u Cov (G γ s , G γ u ) ds r,δ,κ (γL) 1-1 κ(1-δ) (c -3 2 -δ 1-δ ∨ c -3+κ 2 -δ 1-δ ) 2 κ(1-δ) Ψ1+(4-2 κ )r+ε(δ,κ)r , where ε(δ, κ) = 3 -2 κ -2 κ(1-δ) δ 1-δ .
The result follows.

In the next proposition, we are now able to work on the variance of the multilevel procedure.

Proposition 5.2. Assume (H 1 r ) and γ 0 ∈ (0, γ ⋆ ]. Let x ∈ R d such that U (x) r Ψ. Let δ ∈ (0, 1 2 ] and κ > 2 1-δ . Let f be a continuous Lipschitz function.Then,

Var(Y(J, (γ j ) j , (T j ) j , f )) r,δ,κ [f ] 2 1   C (1) var (κ, δ) J j=1 γ 1-1 κ(1-δ) j T j + C (2) var T 0   ,
where C

(1) var (κ, δ) is defined in Lemma 5.2 and C

(2)

var = c -3 2 ∨ c -5 2 -2δ 1-δ Ψ1+2r+ 2δr 1-δ .
Proof. We assume (without loss of generality) that [f ] 1 = 1 and f (x ⋆ ) = 0. In view of the decomposition (37), we apply Lemma 5.2 for each level j ∈ {1, . . . , J} with T = T j and γ = γ j-1 . We obtain for any δ ∈ (0, 1/2] and κ > 2/(1δ),

Var(Y(J, (γ j ) j , (T j ) j , f )) ≤ Var 1 T 0 T0 0 f ( Xγ0,x0 s γ 0 )ds + C (1) var (κ, δ) J j=1 γ 1-1 κ(1-δ) j T j .
It remains to control the first term, i.e. the variance related to the first level. We use similar arguments as in the proof of Lemma 5.2 (see in particular ( 40) and what follows). First, one can check that for every 0

≤ u ≤ s ≤ T , Cov f ( Xγ0,x0 u γ 0 ), f ( Xγ0,x0 s γ 0 ) = E F γ 0 , s γ0 -u γ0 , Xγ0,x u γ 0 f ( Xγ0,x0 u γ 0 ) -E F γ 0 , s γ0 , x E f ( Xγ0,x0 u γ 0 ) ≤ F γ 0 , s γ0 -u γ0 , Xγ0,x u γ 0 2 + F γ 0 , s γ0 , x 2 f Xγ0,x0 u γ 0 2
, by Cauchy-Schwarz inequality. Then, by Proposition 4.5 (and footnote 9) applied with φ(n) = nγ and κ = 2(1+δ) 1-δ , one deduces that (we leave the details to the reader),

T u Cov f ( Xγ0,x0 u γ 0 ), f ( Xγ0,x0 s γ 0 ) ds r,δ c -1 2 ∨ c -3 2 -2δ 1-δ Ψ 1+3r 2 + 2δr 1-δ × sup u≥0 f Xγ0,x0 u γ 0 2 r,δ c -3 2 ∨ c -5 2 -2δ 1-δ Ψ1+2r+ 2δr 1-δ ,
where in the second line, we used Proposition 4.3(iii) and the fact that (by Lemma 4.2)

|f (x)| 2 = |f (x) -f (x ⋆ )| 2 ≤ |x -x ⋆ | 2 ≤ U 1+r (x) c .

Step 3 : Proof of Theorem 2.2

Back to the bias-variance decomposition, we deduce from Proposition 5.1 and Proposition 5.2 that, up to a constant depending on κ, δ and r, the MSE is lower than ε 2 if the following conditions are satisfied (with δ ∈ (0, 1/2] and κ > 2/(1δ)):

             (i.a) : C (1) bias J j=0 1 T 2 j ≤ ε 2 , (i.b) : C (2,1) bias γ J ≤ ε 2 or (i.b) ′ : C (2,2) bias γ 2 J ≤ ε 2 , (ii.a) : C (2) var T 0 ≤ ε 2 , (ii.b) : C (1) var (κ, δ) J j=1 γ 1-1 κ(1-δ) j T j ≤ ε 2 . ( 42
)
Note that (i.b) corresponds to Proposition 5.1(i) whereas (i.b)' corresponds to Proposition 5.1(ii). Let us assume that γ j = γ 0 2 -j and T j = T 0 2 -(1-ρ)j , where ρ ≥ 1/2, γ 0 and T 0 are positive numbers which will calibrated further. With these choices, the above conditions read (up to universal constants):

       (i.a) : T 0 ≥ 2 (1-ρ)J C (1) bias ε -1 (i.b) : 2 J ≥ C (2,1) bias γ 0 ε -2 or (i.b) ′ : 2 J ≥ C (2,2) bias γ 0 ε -1 , (ii.a) : T 0 ≥ C (2) var ε -2 , (ii.b) : T 0 ≥ C (1) var (κ, δ)γ 1-1 κ(1-δ) 0 J j=1 2 (-ρ+ 1 κ(1-δ) )j ε -2 . ( 43
)
Proof of Theorem 2.2 (i) In this case, we have to calibrate the parameters according to (i.a), (i.b), (ii.a) and (ii.b) are satisfied. First, for (i.b), we need 2 J ≥ C

(2,1) bias γ 0 ε -2 so we can set:

J = log 2 C (2,1) bias γ 0 ε -2 .
Then, set ρ = 1/2. With the above value of J and the condition κ > 2/(1δ),

2 J 2 ≤ 2γ 0 C (2,1) bias ε -1 and J j=1 2 (-1 2 + 1 κ(1-δ) )j κ,δ 1.
Hence, (i.a), (ii.a), (ii.b) are satisfied (up to a constant depending on κ, δ and r only) if

T 0 ≥ Cε -2 with C = max γ 0 C (1) bias C (2,1) bias , C (2) var , C (1) var (κ, δ)γ 1-1 κ(1-δ) 0 .
The complexity of the procedure is then:

C(Y) = 2   T 0 γ 0 + J j=1 T j γ j   T 0 γ 0 2 J 2 r,δ,κ C C (2,1) bias ε -3 √ γ 0 .
To deduce the result, it is now enough to remark that with κ = 2(1+δ) 1-δ , γ 0 ≤ 1/(4L),

C ≤ (c -3 4 ∨ c -5 2 -2δ 1-δ ) Ψ1+3r+ 3δr 1-δ so that C C (2,1) bias ≤ √ L(c -5 4 ∧ c -7 2 -3δ 1-δ ) Ψ 3 2 + 9 2 r+ 4δr 1-δ ,
as soon as δ < 1/3. The main result then follows from a change of variable replacing δ by δ = aδ with a small enough.

(ii) In this case, we have to calibrate the parameters according to (i.a), (i.b)', (ii.a) and (ii.b). First, for (i.b)', we need 2 J ≥ C

(2,2) bias γ 0 ε -1 so we can set:

J = log 2 C (2,2) bias γ 0 ε -1 . Then, if ρ > 1 κ(1-δ) , (
T 0 ≥ Cε -2 with C = max C (1) bias γ 2 0 C (2,2) bias 1-ρ 2 , C (2) var , C (1) var (κ, δ)γ 1-1 κ(1-δ) 0 ,
and the complexity of the procedure satisfies:

C(Y) T 0 γ 0 2 ρJ r,δ,κ,ρ C(C (2,2) bias ) ρ 2 ε -2-ρ γ ρ 0 . Set κ = 1+δ ρ(1-δ) = 1 ρ + 2δ ρ(1-δ) . For δ small enough and γ 0 ≤ 1/L, γ 1-1 κ(1-δ) 0 C (1) var (κ, δ) ≤ (c -3ρ(1-δ 1-δ ) ∨ c -(1+3ρ)-5δ ) Ψ1+(4-2ρ)r+ 4δr 1-δ .
Using that γ 0 ≤ 1/(4L), C

bias γ 2 0 C

(2,2) bias

1-ρ 2 ≤ L ρ 2 (c -1 4 -1-ρ 1-δ ∨ c -3 2 -1-ρ 1-δ -2δ 1-δ ) Ψ1-ρ 2 + 5-2ρ 2 r+(3-ρ) δr 1-δ .
Using that ρ ≤ 1/2, this yields (at the price of replacing δ by aδ for a small enough)

C ≤ L ρ 2 c -( 5 4 -ρ)∧(3ρ)+δ ∨ c -5 2 -δ Ψ1+(4-2ρ+δ)r .
The result follows.

we get

U ( Xt ) ≤ U (x) -t|∇U (x)| 2 (1 -2Lt) + σ √ t ∇U (x), Z + 2Lσ 2 t|Z| 2 .
Let θ > 0 and define,

f θ : x → e θU(x) (46)
We deduce from the previous inequality that

E[f θ Xt ] ≤ f θ (x)e -θt|∇U(x)| 2 (1-2Lt) E e θσ √ t ∇U(x),Z +2θLσ 2 t|Z| 2 ≤ f θ (x)e -θt|∇U(x)| 2 (1-2Lt) d i=1 E[e αiZi+βi|Zi| 2 ],
where α i = θσ √ t∂ i U (x) and β i = 2θLσ 2 t. A standard computation shows that for any u ∈ R and any v < 1/2,

E Z1∼N (0,1) [e uZ1+vZ 2 1 ] = 1 √ 1 -2v e u 2 2(1-2v) . (47)
Thus,

d i=1 E[e αiZi+βi|Zi| 2 ] = 1 1 -2θLσ 2 t d 2 e θ 2 σ 2 t|∇U (x)| 2 2(1-2θLσ 2 t) This yields E[f θ Xt ] ≤ f θ (x)e -θt|∇U(x)| 2 (1-2Lt) e -d 2 log(1-2θLσ 2 t) exp θ 2 σ 2 t|∇U (x)| 2 2(1 -2θLσ 2 t) .
Since, γL ≤ 1/4 and θσ 2 ≤ 1/8, 2θLσ 2 t ∈ [0, 1/2] and we can use the elementary inequality log(1x) ≥ -2x for all x ∈ [0, 1/2] to obtain:

E[f θ Xt ] ≤ f θ (x)e -c t,x,θ |∇U(x)| 2 +2dθLσ 2 t with c t,x = θt 1 -2Lt -θσ 2 ≥ θt 4 . For t = γ, this yields E[f θ Xt ] ≤ f θ (x)e -θγ 4 (|∇U(x)| 2 -8dL) . Let C M := {x ∈ R d , |∇U (x)| 2 -8dL ≤ M }.
We get

E[f θ Xt ] ≤ f θ (x)e 2θγdL 1 {x∈CM } + f θ (x)e -θγM 4 1 {x∈C c M } ≤ f θ (x)e -θγM 4 + sup x∈CM f θ (x)(e 2θγdL -e -θγM 4 )
In order to control sup x∈CM f θ (x), one needs to include C M in a level set of U . By (18) and the fact that U (x ⋆ ) = 1, one checks that

C M ⊂ x ∈ R d , U (x) ≤ 1 + M + 8dL 2c 1 1-r so that with t = γ, E[f θ Xγ ] ≤ e -θγM 4 f θ (x) + c(M, γ, θ) with c(M, γ, θ) = e θ(1+ M +8dL 2c ) 1
1-r (e 2θγdLe -θγM 4 ).

36

An induction leads to

sup n≥0 E[f θ Xnγ ] ≤ f θ (x) + c(M, γ, θ) 1 -e -θγM 4 . Setting M = 8dL, c(M, γ, θ) 1 -e -θγM 4 = e θ(1+ 8dL c ) 1 1-r sinh(2θγdL)
e -θγdL sinh(θγdL) = e θ(1+ 8dL c ) 1 1-r +θdL cosh(θγdL).

(ii) We now deal with the additional assumption (H 2 r ). The idea is now to refine the controls by taking into account that the largest eigenvalue also decreases at infinity. Unfortunately, this refinement will require additional technicalities and concentration arguments. By (44), ( 45) and (H 2 r ),

U ( Xt ) ≤ U (x) -t|∇U (x)| 2 (1 -2tL) + σ √ t ∇U (x), Z + 2cσ 2 t|Z| 2 1 0 U -r (ξ λ )dλ.
Keeping in mind that f θ (x) = e θU(x) , this leads to

E f θ Xt ≤ f θ (x) exp -θt|∇U (x)| 2 (1 -2tL) E exp θσ √ t ∇U (x), Z + 2θcσ 2 t|Z| 2 1 0 U -r (ξ λ )dλ =:E .
(48) In order to get a sharp bound of the expectation E, we choose to divide it into two parts depending on a parameter K which will be calibrated below:

E = E exp θσ √ t ∇U (x), Z + 2θcσ
U -r (ξ) =: C U,K (x),
that gives

E 2 ≤ E exp σθ √ t ∇U (x), Z + 2σ 2 θct|Z| 2 C U,K (x) .
Using again (47), this involves that

E 2 ≤ exp - d 2 log 1 -4θcσ 2 tC U,K (x) + σ 2 θ 2 t|∇U (x)| 2 2(1 -4θctσ 2 ) ≤ exp 4dθcσ 2 tC U,K (x) + σ 2 θ 2 t|∇U (x)| 2 2(1 -4θctσ 2 ) ,
where in the last line we used the inequality log(1x) ≥ -2x for all x ∈ [0, 1/2]. Once again, under θσ 2 ≤ 1/8 and tc ≤ 1/4, one checks that σ 2 θ(2(1 -4θctσ 2 )) -1 ≤ 2/7 ≤ 1/3. Thus, where for the second inequality, we used that e -x ≤ 1/(2x) for x ≥ 1 and 1-r 2θγc ≥ 1 (θ ≤ 1). One also checks that γM ≤ 1 since θ ≤ 1. By the inequality e -x ≤ 1 -1 2 x for x ∈ [0, 1], this implies that e -γM ≤ 1 -2γθc 1r =⇒ e -cK + e -γM ≤ 1 -γθc 1r < 1.

E
Plugging into (55) and using the inequality e -x ≥ 1x for x ≥ 0, this yields sup n≥0 E x f θ Xnγ ≤ f θ (x) + e cr θd(1+σ 2 )c c

(1r)(e 4γcσ 2 θd -1) + 2γθc γθc .

To conclude, we need to separate two situations. If γθcd ≤ 1, then the inequality e x ≤ 1 + 4x for x ∈ [0, 1] leads to sup where in the last inequality, we used that 4γc ≤ 1 ≤ c c . This concludes the proof.

(iii) Noting that Ψ r Ψ, the first bound is obvious. For the second one, it is enough to note that under (H 1 r ), (X t ) t≥0 and ( Xnγ ) n≥0 converge in distribution to π and π γ respectively so that with a uniform integrability argument combined with the first bound of (iii), the convergence holds for along functions U p for any p > 0.

B Proof of Proposition 4.3

The idea is to use Jensen inequality to derive controls of the polynomial moments from exponential moments. To this end, we begin with the following lemma: When only (H 1 r ) holds, this yields

E x [U p (X t )] ≤ σ 2 (p -1) + U (x) + 1 + dL 2c 1 1-r p ≤ c p U p (x) + (1 + σ 2 ) 1 + dL 2c 1 1-r p .
Under (H 1 r ) and (H 2 r ), we get

E x [U p (X t )] ≤ σ 2 (p -1) + σ 2 log dL c + U (x) + 4 1 1-r ∨ dc c p .
Using that log(x) ≤ x and that L ≤ c (since U (x) ≥ 1), the second bound follows.

(ii) Assume (H 1 r ). Owing to Proposition 4.2(i) applied with θ = 1/(8σ 2 ), we can use Lemma B.1 with V = U ( Xnγ ), a = e θU(x) , ρ = 1 and b = θ 1 + 8dL c 1 1-r + 2θdL (we used that cosh(u) ≤ e u for u ≥ 0). This

  i.a), (ii.a), (ii.b) are satisfied (up to a constant depending on κ, δ and r only) if

  2 ≤ exp 4dθcσ 2 tC U,K (x) + tθ 3 |∇U (x)| 2 . (50)Plugging (49) and (50) into (48), we obtainE f θ Xt ≤ f θ (x) exp -θt|∇U (x)| 2 (1 -2tL -1 3 e -cK + e 4dσ 2 θctCU,K (x) ≤ f θ (x)e -cK + f θ (x) exp -t θ 6 |∇U (x)| 2 -4dσ 2 θcC U,K (x) ,where in the second line, we used that 2tL ≤ 1/2. Now, let us follow the same strategy as in the first case by settingCM = x ∈ R d ; θ 6 |∇U (x)| 2 -4dσ 2 θcC U,K (x) ≤ M . Then E f θ Xt ≤ f θ (x)e -cK + f θ (x)e -tM 1 Cc M (x) + f θ (x) exp 4tdσ 2 θcC U,K (x) -θt 6 |∇U (x)| 2 1 CM (x) ≤ f θ (x) e -cK + e -tM + f θ (x) exp 4tdσ 2 θcC U,K (x) -θt 6 |∇U (x)| 2e -tM 1 CM ,(51)If we now assume that the parameters are chosen in such a way thate -cK + e -γM < 1,(54)an induction leads to sup n≥0 E x f θ Xnγ ≤ f θ (x) + e θ mK e 4γcσ 2 θde -γM 1e -cKe -γM .In this case, denoting by c r a positive constant which only depends on r (and which may change from line to line), we havem K ≤ c r d(1 + σ 2 )cc and e -cK ≤ θγc 1r ,

n≥0E

  x f θ Xnγ ≤ f θ (x) + e cr θd(1+σ 2 )c c (16σ 2 d + 2).If θγcd ≥ 1 (so that θγc ≥ 1/d), we obtain the following bound:sup n≥0 E x f θ Xnγ ≤ f θ (x) + e cr θd(1+σ 2 )c c (de 4γcσ 2 θd + 2) ≤ f θ (x) + 3de cr θd(1+σ 2 )c c

Lemma B. 1 .

 1 Let V denote a non negative random variable which satisfies E[e θV ] < e a + ρe b for positive θ, a, ρ and b.Then, for anyp ≥ 1, E[V p ] ≤ θ -p (p -1 + a + b + log(2ρ)) p . (56)Proof. Let p ≥ 1 and remark thatE[V p ] = θ -p E log p (e θV ) ≤ θ -p E log p (e p-1+θV) .The function x → log p (x) being concave on [e p-1 , +∞), we deduce from the Jensen inequality thatE[V p ] ≤ θ -p (p -1 + log(E[e θV ])) p ≤ θ -p p -1 + log e a + ρe b p .The lemma then follows from the following inequality: for a, b > 0 and ρ ≥ 1, log(e a + ρe b ) ≤ a + b + log(2ρ) (since e a + ρe b ≤ 2ρe a+b ).Proof of Proposition 4.3. Let us consider separately the continuous and discrete cases. Let us also remark that it is enough to prove the result for p ≥ 1 (when p ≤ 1, one can use the bound obtained for p = 1 combined with the Jensen inequality).

( i )

 i Owing to Proposition 4.1, we can apply Lemma B.1 with θ= σ -2 , V = U (X t ), a = U(x)

≤.

  yields E x [U p ( Xnγ )] ≤ θ -p p -1 + θU (x) + θ 1 U (x) + c p (1 + σ 2 ) dL + 1This yields the bound under (H 1 r ) only. For the bound under (H 1 r ) and (H 2 r ), Proposition 4.2(ii) applied with θ = 1 ∧1/(8σ 2 ) allows us to use Lemma B.1 with V = U ( Xnγ ), a = e θU(x) , ρ = c (c denoting a universal constant) and b = c r θd(1+σ 2 )c c

  •, • and | • |. The set M d,d refers to the set of d × d-real matrices, we denote by • the operator norm associated with the Euclidean norm. For a symmetric matrix A, we denote respectively by λ A and λA its lowest and highest eigenvalues. The Frobenius norm for A ∈ M d,d is denoted by A F .

	The Lipschitz constant of a given (Lipschitz) function

  2 t|Z| 2 1 {|Z| 2 ≥K}Under the assumptions on θ and c, 8θcσ 2 t ≤ 1 4 for any t ∈ [0, γ]. Using the elementary inequality log(1-x) ≥ -2x for all x ∈ [0, 1/2],E 1 ≤ exp 4dθcσ 2 t + 2θ 2 tσ 2 |∇U (x)| 2

					≤ exp	1 -8θctσ 2 2θ 2 tσ 2 |∇U (x)| 2 1 -8θctσ 2 -K 8 +	d 8	-+	K 8 d log 2 d log 2 + 4 4 .
	Using again that θσ 2 ≤ 1/8 and 8θcσ 2 t ≤ 1 4 , we deduce that
	E 1 ≤ exp	θt 3	|∇U (x)| 2 -c K , with c K =	1 8	(K -d (1 + 2 log 2)) .	(49)
	Bound for E 2 : First, we have
	sup ξ∈[x, Xt]	1 {|Z| 2 ≤K} U -r (ξ) ≤	sup ξ∈B(x,t|∇U(x)|+	√ tKσ 2 )
									=:E1
	+ E exp θσ	√	t ∇U (x), Z + 2θcσ 2 t|Z| 2	0	1	U -r (ξ λ )dλ 1 {|Z| 2 <K}
									=:E2
									1/2
	≤	d i=1	E Zi∼N (0,1) exp 2θσ	√ t∂ i U (x)Z i + 4θcσ 2 tZ 2 i	1/2	P |Z| 2 ≥ K	1/2 .
	By (47), this yields
	E 1 ≤ ≤ exp -1 -8θcσ 2 t 1 d 4 log 1 -8θcσ 2 t + d 2 exp 2θ 2 σ 2 t|∇U (x)| 2 1 -8θcσ 2 t 2θ 2 tσ 2 |∇U (x)| 2 1/2 1 -8θctσ 2	P |Z| 2 ≥ K P |Z| 2 ≥ K	1/2 1/2 .
	By exponential Markov inequality and (47) applied with u = 0 and v = 1/4,
	E 1 ≤ exp -≤ exp -	d 4 d 4	log 1 -8θcσ 2 t + log 1 -8θcσ 2 t +	2θ 2 tσ 2 |∇U (x)| 2 1 -8θctσ 2 2θ 2 tσ 2 |∇U (x)| 2 1 -8θctσ 2	--	K 8 K 8	|Z| 2 4 d log 2 E e + 4	1/2 .

,

Bound for E 1 : By Cauchy-Schwarz inequality we have

E 1 ≤ E exp 2θσ √ t ∇U (x), Z + 4θcσ 2 t|Z| 2 1/2 P |Z| 2 ≥ K

Decreasing according the levels but constant for each layer.

This paper is written in the multiplicative setting with a so-called Multilevel-Romberg point of view.

The "Laplace case" will refer to the setting where the potential has a flat gradient. The simplest example is U (x) = |x|. In this case, the invariant distribution is a Laplace distribution. That is the reason why we use this terminology.

Note that the control of π(|.| 2 ) is strongly linked to the so-called KLS-conjecture.

The fact that L is greater than 1 is clearly not fundamental but allows to simplify the usually technical expressions which appear in the sequel.

To ease notation we have voluntarily omitted an assumption about ε: we have to consider ε small enough, we refer to[START_REF] Egéa | Multilevel-Langevin pathwise average for Gibbs approximation[END_REF] to get more precision.

In fact, Proposition 4.5 is written under the assumption U (x) Ψ but here, we need to integrate with respect to the initial condition. To extend to this setting, the idea is to start from (29) and to use the bounds of Proposition 4.3(iii). This allows us to retrieve controls which are similar to Proposition 4.5.

U is also L/2-Lipschitz. This could be alternatively used in this proof.

Acknowledgements

The present author is deeply grateful to F.Panloup for his numerous suggestions and discussions that improved the quality of this paper. The author also thanks the SIRIC ILIAD Nantes-Angers program supported by the French National Institute (INCA-DGOS-Inserm 12558 grant) for funding M. Egéa's Ph.D. thesis.

Remark 5.1. In the uniformly convex case, the variance is controlled by γ log(1/γ) T whereas, here, we are only able to obtain γ 1-1 κ(1-δ)

T

. This difference is due to the lack of exponential convergence to equilibrium under our assumptions. Note that if we leave κ go to ∞, we are moving ever closer to the uniformly convex bound. However, the constant depends on κ and explodes when κ → +∞. The interesting point is that the exponent of Ψ remains bounded when κ → +∞, which means that the dependence in the dimension is slightly impacted by the choice of κ.

First, at the price of replacing f by f /[f ] 1 ,we can assume in the sequel that [f ] 1 ≤ 1. Then,

By Proposition 4.4 and the fact that U (x) uc Ψ, we deduce that for every δ ∈ (0, 1],

This yields a first bound for Cov (G γ s , G γ u ):

Hence, for any t 0 > 0,

We now want to take advantage of the convergence to equilibrium to get a second bound when su ≥ t 0 : since G γ u is F u γ -measurable, we have for any s ≥ u γ ,

and hence,

On the other hand,

As a consequence,

A Proof of Proposition 4.2

Consider the process Xt t>0 defined by Xt = x -t∇U (x) + σ √ tZ where Z = (Z 1 , . . . , Z d ) ∼ N (0, Id R d ). By a Taylor expansion with integral remainder of the function U we have

where ξ λ = λ Xt + (1λ)x.

(i) In this first part, we only assume that ∇U is L-Lipschitz so that λD 2 U(ξ λ ) ≤ L. Thus, since

Now, let us show that CM is included in a level set of U . First, following the arguments which lead to (18), one is also able to show that

By the triangular inequality we get

, where in the second line, we used (52) and the fact that t ∈ [0, γ]. Since tc 1-r ≤ 1 4 , one can check here that if U (x) ≥ 8γKσ 2 c 1-r , we have for every t ∈ [0, γ],

With the help of (18), this implies that

and one can deduce that this term is greater than

From these conditions and (53), we finally get

Going back to (51) (and using that C U,K (x) ≤ 1 for all x), we obtain ∀t ∈ [0, γ], E f θ Xt ≤ f θ (x) e -cK + e -tM + e θmK e 4tcσ 2 θde -tM .