M Fathi

N Frikha

TRANSPORT-ENTROPY INEQUALITIES AND DEVIATION ESTIMATES FOR STOCHASTIC APPROXIMATIONS SCHEMES

Keywords: 1991 Mathematics Subject Classification. 60H35, 65C30, 65C05. January 31, 2013 deviation bounds, transportation-entropy inequalities, Euler scheme, stochastic approximation algorithms, stochastic approximation with averaging

. The key point is to properly quantify the contribution of the diffusion term to the concentration regime. We also derive a general non-asymptotic deviation bound for the difference between a function of the trajectory of a continuous Euler scheme associated to a diffusion process and its mean. Finally, we obtain non-asymptotic bound for stochastic approximation with averaging of trajectories, in particular we prove that averaging a stochastic approximation algorithm with a slow decreasing step sequence gives rise to optimal concentration rate.

Introduction

In this work, we derive transport-entropy inequalities and, as a consequence, non-asymptotic deviation estimates for the laws at a given time step of two kinds of discrete-time and d-dimensional stochastic evolution scheme of the form

X n+1 = X n + γ n+1 H(n, X n , U n+1 ), n ≥ 0, X 0 = x ∈ R d , (1.1)
where (γ n ) n≥1 is a deterministic positive sequence of time steps, the (U i ) i∈N * are i.i.d. R q -valued random variables defined on some probability space (Ω, F , P) with law µ and the function H : N × R d × R q → R d is a measurable function satisfying for all x ∈ R d , for all n ∈ N, H(n, x, .) ∈ L1 (µ), and µ(du)-a.s., H(n, ., u) is continuous. Here and below, we will also assume that µ satisfies a Gaussian concentration property, that is there exists β > 0 such that for every real-valued 1-Lipschitz function f defined on R q and for all λ ≥ 0:

E[exp(λf (U 1 ))] ≤ exp(λE[f (U 1 )] + βλ 2 4 ). (GC(β))
It is well known that (GC(β)) implies the following deviation bound

P[f (U 1 ) -E[f (U 1 )] ≥ r] ≤ exp(- r 2 β ) ∀r ≥ 0,
Examples of random variables satisfying this property include Gaussians, as well as bounded random variables. A characterization of (GC(β)) is given by Gaussian tail of U 1 , that is there exists ε > 0 such that E[exp(ε|U 1 | 2 )] < +∞, see e.g. Bolley and Villani [START_REF] Bolley | Weighted Csiszár-Kullback-Pinsker inequalities and applications to transportation inequalities[END_REF]. The two claims are actually equivalent.

We are interested in furthering the discussion, initiated in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF], about giving non asymptotic deviation bounds for two specific problems related to evolution schemes of the form (1.1). The first one is the deviation between a function of an Euler like discretization scheme of a diffusion process at a fixed deterministic date and its mean. The second one refers to the deviation between a stochastic approximation algorithm at a given time-step and its target. Under some mild assumptions, in particular the assumption that the function u → H(n, x, u) is lipschitz uniformly in space and time, it is proved in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF] that both recursive schemes share the Gaussian concentration property of the innovation.

In the present work, we point out the contribution of the diffusion term to the concentration rate which to our knowledge is new. This covers many situations and gives rise to different regimes ranging from exponential to Gaussian. We also derive a general non-asymptotic deviation bound for the difference between a function of the trajectory of a continuous Euler scheme associated to a diffusion process and its mean. It turns out that, under mild assumptions, the concentration regime is log-normal. Finally, we study non-asymptotic deviation bound for stochastic approximation with averaging of trajectories according to the averaging principle of Ruppert & Polyak, see e.g. [START_REF] Ruppert | Stochastic approximation[END_REF] and [START_REF] Polyak | Acceleration of stochastic approximation by averaging[END_REF].

Euler like Scheme of a Diffusion Process

We consider a Brownian diffusion process (X t ) t≥0 defined on a filtered probability space (Ω, F , (F t ) t≥0 , P), satisfying the usual conditions, and solution to the following stochastic differential equation (SDE)

X t = x + t 0 b(s, X s )ds + t 0 σ(s, X s )dW s , (SDE b,σ )
where (W t ) t≥0 is a q-dimensional (F t ) t≥0 Brownian motion and the coefficients b, σ are assumed to be uniformly Lipschitz continuous in space and measurable in time.

A basic problem in Numerical Probability is to compute quantities like E x [f (X T )] for a given Lipschitz continuous function f and a fixed deterministic time horizon T using Monte Carlo simulation. For instance, it appears in mathematical finance and represents the price of a European option with maturity T when the dynamics of the underlying asset is given by (SDE b,σ ). Under suitable assumptions on the function f and the coefficients b, σ, namely smoothness or non degeneracy, it can also be related to the Feynman-Kac representation of the heat equation associated to the generator of X. To this end, we first introduce some discretization schemes of (SDE b,σ ) that can be easily simulated. For a fixed time step ∆ = T /N, N ∈ N * , we set t i := i∆, for all i ∈ N and define an Euler like scheme by

X ∆ 0 = x, ∀i ∈ [[0, N -1]], X ∆ ti+1 = X ∆ ti + b(t i , X ∆ ti )∆ + σ(t i , X ∆ ti )∆ 1/2 U i+1 , (1.2)
where (U i ) i∈N * is a sequence of R q -valued i.i.d. random variables with law µ satisfying: E[U 1 ] = 0 q , E[U 1 U * 1 ] = I q , where U * 1 denotes the transpose of the column vector U 1 and 0 q , I q respectively denote the zero vector of R q and the identity matrix of R q ⊗ R q . We also assume that µ satisfies (GC(β)) for some β > 0. The main advantage of such a situation is that it includes the case of the standard Euler scheme where U 1 d = N (0, I q ) (satisfying (GC(β)) with β = 2) and the case of the Bernoulli law where U 1 d = (B 1 , • • • , B q ), (B k ) k∈ [[1,q]] are i.i.d random variables with law µ = 1 2 (δ -1 + δ 1 ), which turns out to be one of the only realistic options when the dimension is large.

The weak error E

D (f, ∆, T, b, σ) = E x [f (X T )] -E x [f (X ∆
T )] corresponds to the discretization error when replacing the diffusion X by its Euler scheme X ∆ for the computation of E x [f (X T )]. It has been widely investigated in the literature. Since the seminal work of [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF], it is known that, under smoothness assumption on the coefficients b, σ, the standard Euler scheme produces a weak error of order ∆. In a hypoelliptic setting for the coefficients b and σ and for a bounded measurable function f , Bally and Talay obtained the expected order using Malliavin calculus. For a uniformly elliptic diffusion coefficient σσ * and if b, σ are three times continuously differentiable, the same order for the weak error is established in [START_REF] Konakov | Edgeworth type expansions for euler schemes for stochastic differential equations[END_REF]. The same order ∆ is still valid in the situation where the Gaussian increments are replaced by (non necessarily continuous) random variables (U i ) 1≤i≤N having the same covariance matrix and odd moments up to order 5 as the law N (0, I q ) and if b, σ, f are smooth enough. Let us finally mention the recent work [START_REF] Alfonsi | Pathwise optimal transport bounds between a one-dimensional diffusion and its euler scheme[END_REF] where the authors study the weak trajectorial error using coupling techniques. More precisely, they prove that the Wasserstein distance between the law of a uniformly elliptic and one-dimensional diffusion process and the law of its continuous Euler scheme X c,∆ with time step ∆ := T /N is smaller than O(N -2/3+ǫ ), ∀ǫ > 0.

The expansion of E D also allows to improve the convergence rate to 0 of the discretization error using Richardson-Romberg extrapolation techniques, see e.g. [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF].

In order to have a global control of the numerical procedure for the computation of E x [f (X T )], it remains to approximate the expectation E x [f (X ∆ T )] using a Monte Carlo estimator M -1 × M k=1 f ((X ∆,x T ) j ) where the ((X ∆,x T ) j ) j∈[[1,M]] are M independent copies of the scheme (1.2) starting at the initial value x at time 0. This gives rise to an empirical error defined by

E Emp (M, f, ∆, T, b, σ) = E x [f (X ∆ T )] -M -1 × M j=1 f ((X ∆,x T ) j
). Consequently, the global error associated to the computation of E x [f (X T )] writes as

E Glob (M, ∆) = E x [f (X T )] -E x [f (X ∆ T )] + E x [f (X ∆ T )] - 1 M × M j=1 f ((X ∆,x T ) j ) := E D (f, ∆, T, b, σ) + E Emp (M, f, ∆, T, b, σ).
It is well-known that if f (X ∆,x T ) belongs to L 2 (P) the central limit theorem provides an asymptotic rate of convergence of order M 1/2 . If f (X ∆,x T ) ∈ L 3 (P), a non-asymptotic result is given by the Berry-Essen theorem. However, in practical implementation, one is interested in obtaining deviation bounds in probability for a fixed M and a given threshold r > 0, that is explicitly controlling the quantity P (E Emp (M, ∆) ≥ r).

In this context, Malrieu and Talay [START_REF] Malrieu | Concentration inequalities for Euler schemes[END_REF] obtained Gaussian deviation bounds in an ergodic framework and for a constant diffusion coefficient. Concerning the standard Euler scheme, Menozzi and Lemaire [START_REF] Lemaire | On some non asymptotic bounds for the Euler scheme[END_REF] obtained two-sided Gaussian bounds up to a systematic bias under the assumptions that the diffusion coefficient is uniformly elliptic, σσ * is Hölder-continuous, bounded and that b is bounded. Frikha and Menozzi [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF], getting rid of the non-degeneracy assumption on σ, recently obtained Gaussian deviation bound under the mild smoothness condition that b, σ are uniformly Lipschitz-continuous in space (uniformly in time) and that σ is bounded. The main tool of their analysis is to exploit similar decompositions used in [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF] for the analysis of the weak error. It should be noted that it is the boundedness of σ that gives rise to the Gaussian concentration regime for the deviation of the empirical error.

Using optimal transportation techniques, Blower and Bolley [START_REF] Blower | Concentration inequalities on product spaces with applications to Markov processes[END_REF] obtained Gaussian concentration inequalities and transportation inequalities for the joint law of the first n positions of a stochastic processes with state space some Polish space. However, continuity assumptions in Wasserstein metric need to be checked which can be hard in practice, see conditions (ii) in their Theorems 1.1, 1.2 and 2.1. The authors provide a computable sufficient condition which notably requires the smoothness of the transition law, see Proposition 2.2. in [START_REF] Blower | Concentration inequalities on product spaces with applications to Markov processes[END_REF].

In the current work, we get rid of the boundedness of σ and we only need the Gaussian concentration property of the innovation. We suppose that the coefficients satisfy the following smoothness and domination assumptions (HS) The coefficients b, σ are uniformly Lipschitz continuous in space uniformly in time.

(HD α ) There exists a C 2 (R d , R * + ) function V satisfying ∃C V > 0, |∇V | 2 ≤ C V V, η := 1 2 sup x∈R d ∇ 2 V (x) < +∞ and ∃α ∈ (0, 1], such that for all x ∈ R d , ∃C b > 0, sup t∈[0,T ] |b(t, x)| 2 ≤ C b V (x), , ∃C σ > 0, sup t∈[0,T ] T r(a(t, x)) ≤ C σ V 1-α (x).
where a = σσ * .

The idea behind assumption (HD α ) is to parameterize the growth of the diffusion coefficient in order to quantify its contribution to the concentration regime. Indeed, under (HS) and (HD α ), with α ∈ [1/2, 1], and if the innovations satisfy (GC(β)), for some positive β, we derive non-asymptotic deviation bounds for the statistical error

E ∆ M (x, T, f ) -E x [f (X ∆ T )] ranging from exponential (if α = 1/2) to Gaussian (if α = 1)
regimes. Therefore, we greatly improve the results obtained in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF].

Our approach here is different from [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF]. Indeed, in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF], the key tool consists in writing the deviation using the same kind of decompositions that are exploited in [START_REF] Talay | Expansion of the global error for numerical schemes solving stochastic differential equations[END_REF] for the analysis of the discretization error. In the current work, we will use the fact that the Euler-like scheme (1.2) defines an inhomogenous Markov chain having Feller transitions P k , k = 0, • • • , N -1, defined for non negative or bounded Borel function f : R d → R by

P k (f )(x) = E f (X ∆ t k+1 ) X ∆ t k = x = E f x + b(t k , x)∆ + σ(t k , x)∆ 1/2 U , k = 0, • • • , N -1. For every k, p ∈ {0, • • • , N -1}, k ≤ p,
we also define the iterative kernels for a non negative or bounded Borel function f :

R d → R P k,p (f )(x) = P k • • • • • P p-1 (f )(x) = E f (X ∆ tp ) X ∆ t k = x .
For a 1-Lipschitz function f and λ ≥ 0, using that the law µ of the innovation satisfies (GC(β)) for some positive β, we obtain

P N -1 (exp(λf ))(x) = E exp λf x + b(t N -1 , x)∆ + σ(t N -1 , x)∆ 1/2 U ≤ exp λP N -1 (f )(x) + β λ 2 4 ∆|σ(t N -1 , x)| 2
If σ is bounded, the Gaussian concentration property will readily follow provided the iterated kernel functions P k,p (f ) are uniformly Lipschitz. Under the mild smoothness assumption (HS), this can be easily derived, see Proposition 3.2. Otherwise, using (HD α ), we obtain

P N -1 (exp(λf ))(x) ≤ exp λP N -1 (f )(x) + C σ β∆ 4 λ 2 V 1-α (x) . (1.3)
The last inequality is the first step of our analysis. To investigate the empirical error, the key idea is to exploit recursively from (1.3) that the increments of the scheme (1.2) satisfy (GC(β)) and to adequately quantify the contribution of the diffusion term V 1-α (x) to the concentration rate. Under (HS) and (HD α ), the latter is addressed using flow techniques and integrability results on the law of the scheme (1.2), see Propositions 3.1 and 3.3.

Stochastic Approximation Algorithm

Beyond concentration bounds of the empirical error for Euler-like schemes, we want to look at non asymptotic bounds for stochastic approximation algorithms. Introduced by H. Robbins and S. Monro [START_REF] Robbins | A stochastic approximation method[END_REF], these recursive algorithms aim at finding a zero of a continuous function h : R d → R d which is unknown to the experimenter but can only be estimated through experiments. Successfully and widely investigated since this seminal work, such procedures are now commonly used in various contexts such as convex optimization since minimizing a function amounts to finding a zero of its gradient.

To be more specific, the aim of such an algorithm is to find a solution θ * to the equation h(θ) := E[H(θ, U )] = 0, where H : R d × R q → R d is a Borel function and U is a given R q -valued random variable with law µ. The function h is generally not computable, at least at a reasonable cost. Actually, it is assumed that the computation of h is costly compared to the computation of H for any couple (θ, u) ∈ R d × R q and to the simulation of the random variable U .

A stochastic approximation algorithm corresponds to the following simulation-based recursive scheme

θ n+1 = θ n -γ n+1 H(θ n , U n+1 ), n ≥ 0, θ 0 ∈ R d , (1.4)
where (U n ) n≥1 is an i.i.d. R q -valued sequence of random variables with law µ defined on a probability space (Ω, F , P) and (γ n ) n≥1 is a sequence of non-negative deterministic steps satisfying the usual assumption n≥1 γ n = +∞, and

n≥1 γ 2 n < +∞. (1.5)
When the function h is the gradient of a potential, the recursive procedure (1.4) is a stochastic gradient algorithm. Indeed, replacing H(θ n , U n+1 ) by h(θ n ) in (1.4) leads to the usual deterministic descent gradient method. When h(θ) = M (θ)ℓ, θ ∈ R, where M is a monotone function, say increasing, we can write

M (θ) = E[N (θ, U )]
where N : R × R q → R is a Borel function and ℓ is a given constant such that the equation M (θ) = ℓ has a solution. Setting H = Nℓ, the recursive procedure (1.4) then corresponds to the seminal Robbins-Monro algorithm and aims at computing the level of the function M .

The key idea of stochastic approximation algorithms is to take advantage of an averaging effect along the scheme due to the specific form of h(θ) := E[H(θ, U )]. This allows to avoid the numerical integration of h at each step of a classical first-order optimization algorithm. In the present paper, we make no attempt to provide a general discussion concerning convergence results of stochastic approximation algorithms. We refer readers to [START_REF] Duflo | Algorithmes stochastiques[END_REF], [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF] for some general results on the a.s. convergence of such procedures under the existence of a so-called Lyapunov function, i.e. a continuously differentiable function L : R d → R + such that ∇L is Lipschitz, |∇L| 2 ≤ C(1 + L) for some positive constant C and ∇L, h ≥ 0.

See also [START_REF] Laruelle | Stochastic approximation with averaging innovation applied to finance[END_REF] for a convergence theorem under the existence of a pathwise Lyapunov function. For the sake of simplicity, in the sequel it is assumed that θ * is the unique solution of the equation h(θ) = 0 and that the sequence (θ n ) n≥0 defined by (1.4) converges a.s. towards θ * .

We assume that the law µ of the innovation satisfies (GC(β)) for some β > 0 and that the step sequence (γ n ) n≥1 satisfies (1.5). We also suppose that the following assumptions on the function H are in force:

(HL) For all u ∈ R q , the function H(., u) is Lipschitz-continuous with a Lipschitz modulus having linear growth in the variable u, that is:

∃C H > 0, ∀u ∈ R q , sup (θ,θ ′ )∈(R d ) 2 |H(θ, u) -H(θ ′ , u)| |θ -θ ′ | ≤ C H (1 + |u|).
(HLS) α (Lyapunov Stability-Domination) There exists a

C 2 (R d , R * + ) function L satisfying ∃C L > 0, |∇L| 2 ≤ C L L, η := 1 2 sup x∈R d ∇ 2 L(x) < +∞ such that ∀θ ∈ R d , h(θ), ∇L(θ) ≥ 0, and ∃C h > 0, ∀θ ∈ R d , |h(θ)| 2 ≤ C h L(θ).
and ∃α ∈ (0, 1],

∃C α > 0, ∀θ ∈ R d , sup (u,u ′ )∈(R q ) 2 |H(θ, u) -H(θ, u ′ )| |u -u ′ | ≤ C α L 1-α 2 (θ) (HUA) (Uniform Attractivity) The map h : θ ∈ R d → E[H(θ, U )] is continuously differentiable in θ and there exists λ > 0 s.t. ∀θ ∈ R d , ∀ξ ∈ R d , λ|ξ| 2 ≤ Dh(θ)ξ, ξ .
Compared to [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF], our assumptions are weaker. Indeed, it is assumed in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF] that the map (θ, u) ∈ R d × R q → H(θ, u) is uniformly Lipschitz continuous. In our current framework, this latter assumption is replaced by (HL) and (HLS) α .

The last assumption (HUA), which already appeared in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF], is introduced to derive a sharp estimate of the concentration rate in terms of the step sequence. Let us note that such assumption appears in the study of the weak convergence rate order for the sequence (θ n ) n≥1 as described in [START_REF] Duflo | Algorithmes stochastiques[END_REF] or [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF]. Indeed, it is commonly assumed that the matrix Dh(θ * ) is uniformly attractive that is Re(λ min ) > 0 where λ min is the eigenvalue with the smallest real part. In our current framework, this local condition on the Jacobian matrix of h at the equilibrium is replaced by the uniform assumption (HUA). This allows to derive sharp estimates for the concentration rate of the sequence (θ n ) n≥1 around its target θ * and to provide a sensitivity analysis for the bias δ n := E[|θ nθ * |] with respect to the starting point θ 0 .

Let us note that under (HUA) and the linear growth assumption

∀θ ∈ R d , E |H(θ, U )| 2 ≤ C(1 + |θ -θ * | 2 ),
which is satisfied if (HL) and (HLS) α , with α ∈ [0, 1], hold and if µ satisfies (GC(β)) for some β > 0, the function L : θ → 1 2 |θθ * | 2 is a Lyapunov function for the recursive procedure defined by (1.4) so that one easily deduces that θ n → θ * , a.s. as n → +∞.

The global error between the stochastic approximation procedure θ n at a given time step n and its target θ * can be decomposed as an empirical error and a bias as follows

|θ n -θ * | = |θ n -θ * | -E θ0 [|θ n -θ * |] + E θ0 [|θ n -θ * |] := E Emp (γ, n, H, λ, α) + δ n (1.6)
where we introduced the notations

E Emp (γ, n, H, λ, α) = |θ n -θ * | -E θ0 [|θ n -θ * |] and δ n := E θ0 [|θ n -θ * |].
The empirical error E Emp (γ, n, H, λ, α) is the difference between the absolute value of the error at time n and its mean whereas the bias δ n corresponds to the mean of the absolute value of the difference between the sequence (θ n ) n≥0 at time n and its target θ * . Unlike the Euler like scheme, a bias systematically appears since we want to derive a deviation bound for the difference between θ n and its target θ * . This term strongly depends on the choice of the step sequence (γ n ) n≥1 and the initial point θ 0 , see Proposition 4.4 for a sensitivity analysis.

As for Euler like schemes, our strategy is different from [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF]. Indeed, we exploit again the fact that the stochastic approximation scheme (1.4) defines an inhomogenous Markov chain having Feller transitions P k , k = 0, • • • , N -1, defined for non negative or bounded Borel function f : R d → R by

P k (f )(θ) = E [ f (θ k+1 )| θ k = θ] = E [f (θ -γ k+1 H(θ, U ))] , k = 0, • • • , N -1.
For every k, p ∈ {0, • • • , N -1}, k ≤ p, we also define the iterative kernels for a non negative or bounded Borel function f : R d → R as follows

P k,p (f )(θ) = P k • • • • • P p-1 (f )(θ) = E [ f (θ p )| θ k = θ] .
For a 1-Lipschitz function f and for all λ ≥ 0, using (HLS) α and that the law µ of the innovation satisfies (GC(β)) for some positive β, we obtain

P N -1 (exp(λf ))(θ) = E [exp (λf (θ -γ N H(θ, U )))] ≤ exp λP N -1 (f )(θ) + β λ 2 4 C 2 α γ 2 N L 1-α (θ) (1.7)
Let us note the similarity between (1.3) and (1.7). If (HLS) α holds with α = 1 then the last term appearing in the right hand side of the last inequality is uniformly bounded in θ. This latter assumption corresponds to the framework developed in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF] and leads to a Gaussian concentration bound.

Otherwise, the problem is more challenging. Under the mild domination assumption (HLS) α , the key idea consists again in exploiting recursively from (1.7) that the increments of the stochastic approximation algorithm (1.4) satisfy (GC(β)) and in properly quantifying the contribution of the diffusion term L 1-α (θ) to the concentration rate.

As already noticed in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF], the concentration rate and the bias strongly depends on the choice of the step sequence. In particular, if γ n = c n , with c > 0 then the optimal concentration rate and bias is achieved if c > 1 2λ , see Theorem 2.2. in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF]. Otherwise, they are sub-optimal. This kind of behavior is well-known concerning the weak convergence rate for stochastic approximation algorithm. Indeed, if c > 1 2Re(λmin) we know that a Central Limit Theorem holds for the sequence (θ n ) n≥1 (see e.g. [START_REF] Duflo | Algorithmes stochastiques[END_REF]). Let us note that the condition c > 1 2λ as well as c > 1 2Re(λmin) is difficult to handle and may lead to a blind choice in practical implementation. To circumvent such a difficulty, it is fairly well-known that the key idea is to carefully smooth the trajectories of a converging stochastic approximation algorithm by averaging according to the Ruppert & Polyak averaging principle, see e.g. [START_REF] Ruppert | Stochastic approximation[END_REF] and [START_REF] Polyak | Acceleration of stochastic approximation by averaging[END_REF]. It consists in devising the original stochastic approximation algorithm (1.4) with a slow decreasing step

γ n = c b + n ν , ν ∈ 1 2 , 1 , c, b > 0,
and to simultaneously compute the empirical mean ( θn ) n≥1 of the sequence (θ n ) n≥0 by setting

θn = θ 0 + • • • + θ n-1 n = θn-1 - 1 n θn-1 -θ n-1 .
(1.8)

We will not enter into the technicalities of the subject but under mild assumptions (see e.g. [START_REF] Duflo | Algorithmes stochastiques[END_REF], p.169) one shows that

√ n( θn -θ * ) L → N (0, Σ * ), n → +∞,
where Σ * is the optimal covariance matrix. For instance, for d = 1, one has Σ * = V ar(H(θ * ,U))

(h ′ (θ * )) 2
. Hence, the optimal weak rate of convergence √ n is achieved for free without any condition on the constants c or b. However, this result is only asymptotic and so far, to our best knowledge, non-asymptotic estimates for the deviation between the empirical mean sequence ( θn ) n≥0 at given time step and its target θ * , that is non-asymptotic averaging principle were not investigated.

The sequence (z n ) n≥0 defined by

z n := ( θn+1 , θ n ) is F -adapted, i.e. for all n ≥ 0, z n is F n -measurable, where F n := σ(θ 0 , U k , k ≤ n). Moreover, it defines an inhomogenous Markov chain having Feller transitions K k , k = 0, • • • , N -1, defined for non negative or bounded Borel function f : R d × R d → R by K k (f )(z) = E[ f (z k+1 )| z k = z] = E[ f ( θk+2 , θ k+1 ) ( θk+1 , θ k ) = (z 1 , z 2 )], = E f k + 1 k + 2 z 1 + 1 k + 2 (z 2 -γ k+1 H(z 2 , U )), z 2 -γ k+1 H(z 2 , U ) .
For every k, p ∈ {0, • • • , N -1}, k ≤ p, we define the iterative kernels for a non negative or bounded Borel function f :

R d × R d → R K k,p (f )(z) = K k • • • • K p-1 (f )(z) = E[ f (z p )| z k = z].
Hence, for any 1-Lipschitz function and for all λ ≥ 0, using again (HLS) α and that the law µ of the innovation satisfies (GC(β)) for some positive β, one has for all k ∈ {0,

• • • , N -1} K k (exp(λf ))(z) = E [ exp (λf (z k+1 ))| z k = z] ≤ exp λK k (f )(z) + β λ 2 4 C α γ k+1 ( 1 k + 2 + 1)L 1-α 2 (z 2 ) 2 ≤ exp λK k (f )(z) + βλ 2 C 2 α γ 2 k+1 L 1-α (z 2 ) (1.9)
where we used that for all (z

1 , z 2 ) ∈ R d ×R d , the functions u → f k+1 k+2 z 1 + 1 k+2 (z 2 -γ k+1 H(z 2 , u)), z 2 -γ k+1 H(z 2 , u) are Lipschitz-continuous with Lipschitz modulus equals to C α γ k+1 ( 1 k+2 + 1)L 1-α 2 (z 2 ).
Here again, (1.7) and (1.9) are quite similar and if α = 1 the concentration regime turns out to be Gaussian. Otherwise, an analysis along the lines of the methodology developed so far provides the concentration regime of the stochastic approximation algorithm with averaging of trajectories.

Transport-Entropy inequalities

As a by-product of our analysis, we derive transport-entropy inequalities for the law of both stochastic approximation schemes. We recall here basic definitions and properties. For a complete overview and recent developments in the theory of transport inequalities, the reader may refer to the recent survey [START_REF] Gozlan | Transport inequalities. A survey. Markov Process[END_REF]. We will denote by P(R d ) the set of probability measures on R d .

For p ≥ 1, we consider the set P p (R d ) of probability measures with finite moment of order p. The Wasserstein metric W p (µ, ν) of order p between two probability measures µ, ν ∈ P p (R d ) is defined by

W p p (µ, ν) = inf R d ×R d |x -y| p π(dx, dy) : π ∈ P(R d × R d ), π 0 = µ, π 1 = ν
where π 0 and π 1 are two probability measures standing for the first and second marginals of

π ∈ P(R d × R d ).
For µ ∈ P(R d ), we define the relative entropy w.r.t ν ∈ P(R d ) as

H(µ, ν) = R d log dµ dν dµ if µ ≪ ν and H(µ, ν) = +∞ otherwise.
We are now in position to define the notion of transport-entropy inequality. Here as below, Φ : R + → R + is a convex, increasing function with Φ(0) = 0.

Definition 1.1. A probability measure µ on R d satisfies a transport-entropy inequality with function Φ if for all ν ∈ P(R d ), one has

Φ(W 1 (ν, µ)) ≤ H(ν, µ)
For the sake of simplicity, we will write that µ satisfies T Φ .

The following proposition comes from Corollary 3.4. of [START_REF] Gozlan | Transport inequalities. A survey. Markov Process[END_REF].

Proposition 1.1. The following propositions are equivalent:

• The probability measure µ satisfies T Φ .

• For all 1-Lipschitz function f , one has

∀λ ≥ 0, exp(λf )dµ ≤ exp λ f dµ + Φ * (λ) ,
where Φ * is the monotone conjugate of Φ defined on R + as Φ * (λ) = sup ρ≥0 {λρ -Φ(ρ)}.

Such transport-entropy inequalities are very attractive especially from a numerical point of view since they are related to the concentration of measure phenomenon which allows to establish non-asymptotic deviation estimates. The three next results put an emphasis on this point. Suppose that (X n ) n≥1 is a sequence of independent and identically distributed R d -valued random variables with common law µ.

Corollary 1.1. If µ satisfies T Φ then for all 1-Lipschitz function f and for all r ≥ 0, for all M ≥ 1, one has

P | 1 M M k=1 f (X k ) -E[f (X 1 )]| ≥ r ≤ 2 exp(-M Φ(r))
Proposition 1.2. If µ satisfies T Φ then the empirical measure µ n defined as

µ n = 1 n n k=1 δ X k satisfies the following concentration bound P (W 1 (µ n , µ) ≥ E[W 1 (µ n , µ)] + r) ≤ exp (-nΦ(r)) .
where for x ∈ R d , δ x stands for the Dirac mass at point x.

The quantity E[W 1 (µ, µ n )] will go to zero as n goes to infinity, by convergence of empirical measures, but we still need quantitative bounds. The next result is an adaptation of a result of [START_REF] Svetlozar | Mass transportation problems. Vol. II. Probability and its Applications[END_REF] on similar bounds but for the distance W 2 . For sake of completeness, we provide a proof in Appendix 4.2.

Proposition 1.3. Assume that µ has a finite moment of order d + 3. Then, one has

E[W 1 (µ n µ)] ≤ C(d, µ)n -1/(d+2)
where

C(d, µ) := 4 √ d + 2 R d (1 + |x| d+1 ) -1 dx 2 -2d + 2 3-d |y| d+3 µ(dy) + 2 3-d d(d + 3)!.
In view of Kantorovich-Rubinstein duality formula, namely

W 1 (µ, ν) = sup f dµ -f dν : [f ] 1 ≤ 1
where [f ] 1 denotes the Lipschitz-modulus of f , the latter result provides the following concentration bounds

∀r ≥ 0, ∀M ≥ 1, P sup f :[f ]1≤1 1 M M k=1 f (X k ) -E[f (X 1 )] ≥ C(d, µ)M -1/(d+2) + r ≤ exp (-M Φ(r)) .
Similar results were first obtained for different concentration regimes by Bolley, Guillin, Villani [BGV07] relying on a non-asymptotic version of Sanov's Theorem. Some of these results have also been derived by Boissard [Boi11] using concentration inequalities, and were also extended to ergodic Markov chains up to some contractivity assumptions in the Wasserstein metric on the transition kernel.

Some applications are proposed in [START_REF] Bolley | Quantitative concentration inequalities for empirical measures on non-compact spaces[END_REF]. Such results can indeed provide non-asymptotic deviation bounds for the estimation of the density of the invariant measure of a Markov chain. Let us note that the (possibly large) constant C(d, µ) appears as a trade-off to obtain uniform deviations over all Lipschitz functions. As a consequence of the transport-entropy inequalities obtained for the laws at a given time step of Euler like schemes and stochastic approximation algorithm, we will derive non-asymptotic deviation bounds in the Wasserstein metric.

Main Results

Euler like schemes and diffusions

Theorem 2.1 (Transport-Entropy inequalities for Euler like schemes). Denote by X ∆,0,x T the value at time T of the scheme (1.2) associated to the diffusion (SDE b,σ ) starting at point x at time 0. Denote the Lipschitz modulus of b and σ appearing in the diffusion process (SDE b,σ ) by [b] 1 and [σ] 1 , respectively and by µ ∆,0,x T the law of X ∆,0,x T . Assume that the innovations (U i ) i≥1 in (1.2) satisfy (GC(β)) for some β > 0 and that the coefficients b, σ satisfy (HS) and

(HD α ) for α ∈ [ 1 2 , 1]. Then, µ ∆,0,x T satisfies T Φ * α with Φ * α (λ) = sup ρ≥0 {λρ -Φ α (ρ)} with: • If α ∈ ( 1 2 , 1], for all ρ ≥ 0 Φ α (ρ) = Ψ α (T, ∆, b, σ, x)(ρ 2 ∨ ρ 2α 2α-1 ), with Ψ α (T, ∆, b, σ, x) = K 3.1 (ϕ(T, b, σ, ∆) 2 ∨ ϕ(T, b, σ, ∆) α 2α-1 ), ϕ(T, b, σ, ∆) = C σ β (1+C(∆)∆) 4C(∆) e 3C(∆)T , C(∆) := 2[b] 1 + [σ] 2 1 + ∆[b] 2 1 and the constant K 3.1 being defined in Corollary 3.1. • If α = 1 2 , for all ρ ∈ [0, ϕ(T, b, σ, ∆) -1/2 λ 3.2 ) Φ 1/2 (ρ) = K 3.2 (ρϕ(T, b, σ, ∆) 1/2 /λ 3.2 ) 2 1 -(ρϕ(T, b, σ, ∆) 1/2 /λ 3.2 )
where the positive constants λ 3.2 and K 3.2 are defined in Corollary 3.2.

Note that in the above theorem, we do not need any non-degeneracy condition on the diffusion coefficient. In the case α ∈ ( 1 2 , 1], one easily gets the following explicit formula:

• If λ ∈ [0, 2Ψ], then Φ * α (λ) = 1 4Ψ λ 2 ; • If λ ∈ [ 2α 2α-1 Ψ, +∞), then Φ * α (λ) = 1 2α 2α-1 2αΨ 2α-1 λ 2α ; • If λ ∈ (2Ψ, 2α 2α-1 Ψ),then Φ * α (λ) = λ -Ψ.
Let us note that the linear behavior of Φ * α on a small interval is due to the fact that Φ α is not C 1 . One may want to replace ρ 2 ∨ ρ 2α 2α-1 by ρ 2 + ρ 2α 2α-1 (up to a factor 2) in the expression of Φ α . However, in this case, an explicit expression for Φ * α does not exist (except for the case α = 1) and only its asymptotic behavior can be derived so that one is led to compute it numerically in practical situations.

In the case α = 1/2, tedious but simple computations show that

Φ * 1/2 (λ) = 1 + λ 3.2 K 3.2 ϕ(T, b, σ, ∆) 1/2 λ 1 2 -1 2 .
This behavior corresponds to a concentration profile that is Gaussian at short distance, and exponential at large distance.

Corollary 2.1. (Non-asymptotic deviation bounds) Under the same assumptions as Theorem 2.1, one has:

• for all real-valued 1-Lipschitz function f defined on R d , for all α ∈ [1/2, 1] for all M ≥ 1 and all r ≥ 0,

P x | 1 M M k=1 f ((X ∆ T ) k ) -E x [f (X ∆ T )]| ≥ r ≤ 2 exp(-M Φ * α (r)),
• for all α ∈ [1/2, 1], for all M ≥ 1 and all r ≥ 0,

P x sup f :[f ]1≤1 1 M M k=1 f ((X ∆ T ) k ) -E x [f (X ∆ T )] ≥ C(d, µ ∆,0,x T )M -1/(d+2) + r ≤ exp (-M Φ * α (r)) ,
where the ((X ∆ T ) k ) 1≤k≤M are M independent copies of the scheme (1.2) starting at point x at time 0 and evaluated at time T .

Remark 2.1 (Extension to smooth functions of a finite number of time step). The previous transport-inequalities and non-asymptotic bounds could be extended to smooth functions of a finite number of time step such as the maximum of a scalar Euler like scheme. In that case, it suffices to introduce the additional state variable

(M ∆ ti ) i≥1 := (max k∈[[0,i]] X ∆ t k ) i≥1 . Now, the couple (X ∆ ti , M ∆ ti )
1≤i≤N is Markovian and similar arguments could be easily extended to the couple for Lipschitz functions of both variables.

Remark 2.2 (Transport-Entropy inequalities for the law of a diffusion process). The previous transportinequalities and non-asymptotic bounds could be extended to the law at time T of the diffusion process solution to (SDE b,σ ) by passing to the limit ∆ → 0. Indeed, it is well-known that under (HS), one has X ∆ T a.s.

-→ X T , as ∆ → 0 and by Lebesgue theorem, one deduces from the first result of Corollary 2.1 that the empirical error (empirical mean) of X T itself satisfies a non-asymptotic deviation bound with a similar deviation function (just pass to the limit ∆ → 0 in all constants). Then, using Corollary 5.1 in [START_REF] Gozlan | Transport inequalities. A survey. Markov Process[END_REF] (equivalence between deviation of the empirical mean and transport-entropy inequalities), one easily derives that the law of X T satisfies a similar transport-entropy inequalities when α ∈ (1/2, 1].

We want to point out that it is the growth of σ that gives the concentration regime ranging from Gaussian concentration bound if α = 1 to exponential when α = 1 2 . However, in many popular models in finance, the diffusion coefficient is linear, for instance practitioners often have to deal with Black-Scholes like dynamics of the form

X t = x 0 + t 0 b(X s )X s ds + t 0 σ(X s )X s dW s for smooth, bounded coefficients b, σ. For the estimation of E x [f (X ∆ T )] for a Lipschitz function f : R d → R, or even in more general situations, the estimation of E x [f (X ∆ )] for a Lipschitz function f : C → R, where C := C([0, T ], R d ) stands for the space of R d -valued continuous functions on [0, T ], equipped with the uniform norm ||f || ∞ := sup 0≤t≤T |f (t)|,
the expected concentration is the log-normal one. To deal with the latter case, we consider the continuous Euler scheme X c,∆ associated to (SDE b,σ ) and writing

∀t ∈ [0, T ], X c,∆ t = x + t 0 b(φ(s), X c,∆ φ(s) )ds + t 0 σ(φ(s), X c,∆ φ(s) )dW s , x ∈ R d . (2.1)
where we set φ(t) := t i for t i ≤ t < t i+1 , i ∈ N. The next result provides a general non-asymptotic deviation bound for the empirical error under very mild assumptions.

Theorem 2.2 (General non-asymptotic deviation bounds). Denote by X c,∆ := (X c,∆ t ) 0≤t≤T the path of the scheme (2.1) with step ∆ starting from point x at time 0. Assume that ∀t ∈ [0, T ], the coefficients b(t, .) and σ(t, .) are continuous functions in x and that they satisfy the linear growth assumption:

∀x ∈ R d , sup t∈[0,T ] |b(t, x)| ≤ C b (1 + |x|), sup t∈[0,T ] T r(a(t, x)) ≤ C σ (1 + |x| 2 ).
Then, for all 1-Lipschitz function f : C → R, for all M ∈ N * , for all r ≥ 0, one has

P x | 1 M M k=1 f ((X c,∆ ) k ) -E x [f (X c,∆ )]| ≥ r ≤        2 exp - r 2 M (2(1+|x|)) 2 exp(2κ(b,σ,T )) , if r ≤ 1 √ M 2(1 + |x|)e κ(b,σ,T ) 2 exp - 1 4κ(b,σ,T ) log r 2 M (2(1+|x|)) 2 2 , otherwise
where κ(b, σ, T ) := 28(1 + (C σ ∨ C b )T ) and ((X c,∆ ) k ) 1≤k≤M are M independent copies of the scheme (2.1). The result remains valid when one considers the path of the diffusion X solution to (SDE b,σ ) instead of the continuous Euler scheme.

Stochastic approximation algorithms

Theorem 2.3 (Transport-Entropy inequalities for stochastic approximation algorithms). Let N ∈ N * . Assume that the function H of the recursive procedure (θ n ) 0≤n≤N (with starting point θ 0 ∈ R d ) defined by (1.4) satisfies (HL), (HUA) and (HLS) α for α ∈ [ 1 2 , 1], and that the step sequence γ = (γ n ) n≥0 satisfies (1.5). Suppose that the law of the innovation satisfies (GC(β)), β > 0. Denote by µ γ,0,θ0 N the law of θ N . Then, µ γ,0,θ0

N satisfies T Φ * α with Φ * α,N (λ) = sup ρ≥0 {λρ -Φ α,N (
ρ)} and one has:

• If α ∈ ( 1 2 , 1], for all ρ ≥ 0 Φ α,N (ρ) = ϕ α (γ, H, θ 0 )(C γ N ρ 2 ∨ C γ,α N ρ 2α 2α-1 )
with the two concentration rates

C γ N := N -1 k=0 γ 2 k+1 Π1,N Π 1,k , with Π 1,N := N -1 k=0 (1 -2λγ k+1 + C H,µ γ 2 k+1 ) and C γ,α N := N -1 k=0 γ 2α 2α-1 k+1 ( Π1,N Π 1,k ) 2α 2α-1 ((k + 1) log 2 (k + 4)) 1-α 2α-1 for all N ≥ 1, where C H,µ := 2C 2 H (1 + E[|U | 2 ]) and ϕ α (γ, H, θ 0 ) is an explicit constant defined in Proposition 4.3. • If α = 1 2 , for all ρ ∈ [0, λ 4.1 /s N ), Φ 1/2,N (ρ) = 2ϕ 1/2 (γ, H, θ 0 )C γ N (ρ/λ 4.1 ) 2 1 -(ρs N /λ 4.1 ) with sN := max 0≤k≤N -1 (k + 1) 1/2 log(k + 4)γ k+1 Π1,N Π 1,k 1 2 exp( N -1 p=0 1 (p+1) log 2 (p+4)
) and the (positive) constants ϕ 1/2 (γ, H, θ 0 ) and λ 4.1 are defined in Proposition 4.3.

As in the case of Euler like schemes, for α ∈ ( 1 2 , 1], we have:

• if λ ∈ [0, 2ϕ(C γ N /(C γ,α N ) 2α-1 ) 1 2(1-α) ], then Φ * α,N (λ) = λ 2 /(4ϕC γ N ); • If λ ∈ [ 2α 2α-1 ϕ(C γ N /(C γ,α N ) 2α-1 ) 1 2(1-α) , +∞), then Φ * α,N (λ) = 1 2α 2α-1 2αϕ 2α-1 (λ 2α /(C γ,α N ) 2α-1 ); • If λ ∈ (2ϕ(C γ N /(C γ,α N ) 2α-1 ) 1 2(1-α) , 2α 2α-1 ϕ(C γ N /(C γ,α N ) 2α-1 ) 1 2(1-α) ), then Φ * α,N (λ) = ( C γ N C γ,α N ) 2α-1 2(1-α) λ - ϕ (C γ N ) α 1-α (C γ,α N ) 2α-1 1-α .
For α = 1 2 , we obtain the following explicit bound for the Legendre transform of

Φ 1/2,N ∀λ ≥ 0, Φ * 1/2,N (λ) = 2ϕC γ N s2 N 1 + sN λ 4.1 λ 2ϕC γ N 1 2 -1 2
Hence, for N ≥ 1 being fixed, the following simple asymptotic behaviors can be easily derived:

• When λ is small, Φ * 1/2,N (λ) ∼ λ 2 4.1 λ 2 /(2ϕC γ N ); • When λ goes to infinity, Φ * 1/2 (λ) ∼ λ 4.1 λ/s N .
Corollary 2.2. (Non-asymptotic deviation bounds) Under the same assumptions as Theorem 2.3, one has

P θ0 (|θ N -θ * | ≥ r + δ N ) ≤ exp -Φ * α,N (r)
and

δ N := E θ0 [|θ N -θ * |].
Moreover, the bias δ N at step N satisfies

δ N ≤ e -λΓ1,N +Cα,µΓ2,N |θ 0 -θ * | + (2C α,µ ) 1 2 N -1 k=0 γ 2 k+1 e -2λ(Γ1,N -Γ 1,k+1 )+2Cα,µ(Γ2,N -Γ 2,k+1 ) 1 2 , where Γ 1,N := N k=1 γ k , Γ 2,N := N k=1 γ 2 k , C α,µ := λ 2 /2 + 2C α KE[|U | 2 ]
with K > 0. Now, we investigate the impact of the step sequence (γ n ) n≥1 on the concentration rate sequences C γ N , C γ,α N , sN and the bias δ N . Let us note that a similar analysis has been performed in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF]. We obtain the following results:

• If we choose γ n = c n , with c > 0. Then δ N → 0, N → +∞, Γ 1,N = c log(N ) + c ′ 1 + r N , c ′ 1 > 0 and r N → 0, so that Π 1,N = O(N -2cλ ). -If c < 1 2λ , the series N k=1 γ 2 k /Π 1,k , N -1 k=0 γ 2α 2α-1 k+1 (1/Π 2α 2α-1 1,k )((k + 1) log 2 (k + 4)) 1-α 2α-1 converge so that we obtain C γ N = O(N -2cλ ), C γ,α N = O(N -2α 2α-1 cλ ), sN = O(N -cλ ).
-If c > 1 2λ , a comparison between the series and the integral yields

C γ N = O(N -1 ), C γ,α N = O((log(N )) 2 1-α 2α-1 N -α 2α-1 ), sN = O(log(N )N -1 2
). Let us notice that we find the same critical level for the constant c as in the Central Limit Theorem for stochastic algorithms. Indeed, if c > 1 2Re(λmin) where λ min denotes the eigenvalue of Dh(θ * ) with the smallest real part then we know that a Central Limit Theorem holds for (θ n ) n≥1 (see e.g. [START_REF] Duflo | Algorithmes stochastiques[END_REF], p.169). Such behavior was already observed in [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF].

The associated bound for the bias is the following:

δ N ≤ K |θ 0 -θ * | N λc + (2C α,µ ) 1 2 N λc∧ 1 2 . • If we choose γ n = c n ρ , c > 0, 1 2 < ρ < 1, then δ N → 0, Γ 1,N ∼ c 1-ρ N 1-ρ as N → +∞ and elementary computations show that there exists C > 0 s.t. for all N ≥ 1, Π 1,N ≤ C exp(-2λ c 1-ρ N 1-ρ ).
Hence, for all ǫ ∈ (0, 1ρ) we have:

C γ N = Π 1,N N k=1 γ 2 k Π -1 1,k ≤ c 2    Π 1,N Π -1 1,N -N ρ+ǫ N -N ρ+ǫ k=1 1 k 2ρ + N k=N -N ρ+ǫ +1 1 k 2ρ    ≤ c 2 C exp(-2λ c 1 -ρ (N 1-ρ -(N -N ρ+ǫ ) 1-ρ )) + N ρ+ǫ (N -N ρ+ǫ + 1) 2ρ ≤ c 2 C exp(-2λcN ǫ ) + 1 N ρ-ǫ .
Up to a modification of ǫ, this yields

C γ N = Π 1,N N k=1 γ 2 k Π -1 1,k = o(N -ρ+ǫ ), ǫ ∈ (0, 1 -ρ). Similar computations show that C γ,α N = o(N -(ρ-(1-α))
2α-1

-ǫ ) and we clearly get sN = O log(N )N -(ρ-1 2 ) .

Concerning the bias, from Corollary 2.2, we directly obtain the following bound:

δ N ≤ K exp - λc 1 -ρ N 1-ρ |θ 0 -θ * | + (2C α,µ ) 1 2 N ρ 2 -ǫ
, ∀ǫ > 0.

The impact of the initial difference |θ 0θ * | is exponentially smaller compared to the case γ n = c n . This is natural since the step sequence is decreasing slower to 0.

Theorem 2.4 (Transport-Entropy inequalities for stochastic approximation with averaging of trajectories). Let N ∈ N * . Assume that the function H of the recursive procedure θ = (θ n ) 0≤n≤N (with starting point θ 0 ∈ R d ) defined by (1.4) satisfies (HL), (HUA) and (HLS) α for α ∈ [ 1 2 , 1], and that the step sequence γ = (γ n ) n≥1 satisfies (1.5). Suppose that the law of the innovation satisfies (GC(β)), β > 0. Denote by μγ,0,θ0 N the law of θN where θ is the empirical mean of θ defined by (1.8). Then, μγ,0,θ0 N satisfies TΦ * α,N with Φ * α,N (λ) = sup ρ≥0 λρ -Φα,N (ρ) and one has:

• If α ∈ ( 1 2 , 1], for all ρ ≥ 0 Φα,N (ρ) = ϕ α (γ, H, θ 0 )( Cγ N ρ 2 ∨ Cγ,α N ρ 2α 2α-1 )
where ϕ α (γ, H, θ 0 ) is a positive constant defined in Section 4.2.

• If α = 1 2 , for all ρ ∈ [0, λ 4.1 /ŝ N ), Φ1/2,N (ρ) = 2ϕ 1/2 (γ, H, θ 0 ) Cγ N (ρ/λ 4.1 ) 2 1 -(ρŝ N /λ 4.1 )
where ϕ 1/2 (γ, H, θ 0 ) and λ 4.1 are positive constants defined in Proposition 4.3. where the three concentration rate sequences are defined for N ∈ N * by

Cγ N := N -1 k=1 γ2 k,N , Cγ,α N := N -1 k=1 γ 2α 2α-1 k,N ((k+1) log 2 (k+4)) 1-α 2α-1 , ŝN := max 1≤k≤N -1 (k+1) 1 2 log(k+4)γ k,N e N -1 p=0 1 (p+1) log 2 (p+4) with γk,N := γ k N (1 + N -1 j=k+1 ( Π1,j Π 1,k ) 1
2 ), and Π 1,N :=

N -1 p=0 (1 -2λγ p+1 + C H,µ γ 2 p+1 ).
As regards the explicit computation of the Legendre transform of Φα,N , similarly to the previous theorem, we have:

• for α ∈ ( 1 2 , 1]: -if λ ∈ [0, 2ϕ( Cγ N /( Cγ,α N ) 2α-1 ) 1 2(1-α) ], then Φ * α,N (λ) = (λ 2 /4ϕ Cγ N ); -If λ ∈ [ 2α 2α-1 ϕ( Cγ N /( Cγ,α N ) 2α-1 ) 1 2(1-α) , +∞), then Φ * α,N (λ) = 1 2α 2α-1 2αϕ 2α-1 (λ 2α /( Cγ,α N ) 2α-1 ); -If λ ∈ (2ϕ( Cγ N /( Cγ,α N ) 2α-1 ) 1 2(1-α) , 2α 2α-1 ϕ( Cγ N /( Cγ,α N ) 2α-1 ) 1 2(1-α) ), then Φ * α,N (λ) = ( Cγ N Cγ,α N ) 2α-1 2(1-α) λ - ϕ ( Cγ N ) α 1-α ( Cγ,α N ) 2α-1 1-α . • for α = 1 2 , ∀λ ≥ 0, Φ * 1/2,N (λ) = 2ϕ Cγ N ŝ2 N 1 + ŝN λ 4.1 λ 2ϕ Cγ N 1 2 -1 2
Hence, for N ≥ 1 being fixed, the following simple asymptotic behaviors can be easily derived:

-When λ is small, Φ * 1/2,N (λ) ∼ λ 2 4.1 λ 2 /(2ϕ Cγ N );
-When λ goes to infinity, Φ * 1/2 (λ) ∼ λ 4.1 λ/ŝ N . Corollary 2.3. (Non-asymptotic deviation bounds) Under the same assumptions as Theorem 2.4, for all N ≥ 1 for all r ≥ 0, one has P θ0 θNθ * ≥ r + δN ≤ exp -Φ * α,N (r) and δN := E θ0 θNθ * . Now, we analyze the impact of the step sequence on the concentration rate sequences Cγ N , Cγ,α N , ŝN and the bias δN . We first simplify the expression of the concentration rate. Let us note that since the step sequence (γ n ) n≥1 satisfies (1.5), there exists a positive constant K > 0 such that (Π 1,j Π -1 1,k )

1 2 ≤ K exp(-λ(Γ 1,j -Γ 1,k+1 )), k < j. Moreover, since the function x → exp(-λx) is decreasing on [Γ 1,p , Γ 1,p+1 ], one clearly gets for all i, j ∈ {0, • • • , N -1}, i < j M j -M i := j-1 p=i exp(-λΓ 1,p+1 )γ p+1 = j-1 p=i Γ1,p+1 Γ1,p exp(-λΓ 1,p+1 )dx ≤ 1 λ (exp(-λΓ 1,i ) -exp(-λΓ 1,j ))
so that, using the latter bound and an Abel transform, we obtain

N -1 j=k+1 exp(-λΓ 1,j+1 ) = N -1 j=k+1 (M j+1 -M j )γ -1 j+1 ≤ - 1 λ   N -1 j=k+1 (exp(-λΓ 1,j+1 ) -exp(-λΓ 1,j ))γ -1 j+1   ≤ - 1 λ   e -λΓ1,N γ -1 N +1 -e -λΓ 1,k+1 γ -1 k+2 - N -1 p=k+1 e -λΓ1,p+1 (γ -1 p+2 -γ -1 p+1 )  
which finally leads to the following bound

γk,N ≤ K λ   γ k γ -1 k+2 N + γ k N N -1 p=k+1 e -λ(Γ1,p-Γ 1,k+1 ) (γ -1 p+2 -γ -1 p+1 )   . (2.2)
Now, we are in position to study the impact of the step sequence (γ n ) n≥1 on the concentration rate sequences:

• If we select γ n = c n with c > 0, then, using that Γ 1,N = c log(N ) + c ′ 1 + r N , c ′ 1 > 0 with r N → 0, one easily derives from (2.2) that there exists

C > 0 such that γk,N ≤ C   1 N + 1 k 1-cλ 1 N N -1 p=k 1 p λc   ,
and a comparison between the series and the integral yields the following bounds:

-

If λc < 1 2 , one has: Cγ N = O(N -2cλ ), Cγ,α N = O(N -2α 2α-1 cλ ) and ŝN = O(N -cλ ). -If λc > 1 2 , one has: Cγ N = O(N -1 ), Cγ,α N = O((log(N )) 2 1-α 2α-1 N -α 2α-1
) and ŝN = O(N -1 2 ). Hence, we clearly see that for the case γ n = c n , averaging the trajectories of a stochastic approximation algorithm is not the key to circumvent the lake of robustness concerning the choice of the constant c.

The bound for the bias is obtained by averaging the bound previously obtained for δ N . We easily get:

δN ≤ 1 N N -1 k=0 E θ0 [|θ k -θ * |] ≤ K |θ 0 -θ * | N λc + (2C α,µ ) 1 2 N λc∧ 1 2 • If we choose γ n = c n ρ , c > 0, 1 2 < ρ < 1 then we have for k ≤ p Γ 1,p -Γ 1,k = p j=k+1 j -ρ = p j=k+1 j+1 j 1 j ρ dx ≥ p+1 k+1 1 x ρ dx ≥ 1 1 -ρ (p + 1) 1-ρ -(k + 1) 1-ρ
so that for some positive constant C which may vary from line to line

N -1 p=k+1 e -λ(Γ1,p-Γ 1,k+1 ) (γ -1 p+2 -γ -1 p+1 ) ≤ Ce λ 1-ρ (k+1) 1-ρ   N -1 p=k+1 e -λ 1-ρ (p+1) 1-ρ 1 (p + 1) 1-ρ   ≤ Ce λ 1-ρ (k+1) 1-ρ N k+1 e -λ 1-ρ x 1-ρ x -(1-ρ) dx ≤ Ce λ 1-ρ (k+1) 1-ρ N 1-ρ (k+1) 1-ρ e -λ 1-ρ x x 2ρ-1 1-ρ dx
where we use a change of variable in the latter integral. For k large enough, the function

x → e -λ 1-ρ x x 2ρ 1-ρ is decreasing on [k, +∞) which implies e λ 1-ρ (k+1) 1-ρ (N -1) 1-ρ (k+1) 1-ρ e -λ 1-ρ x x 2ρ 1-ρ 1 x 1 1-ρ dx ≤ C(k + 1) 2ρ - 1 -ρ ρ x -ρ 1-ρ +∞ (k+1) 1-ρ ≤ C(k + 1) ρ .
Hence, we finally have γk,N = O(N -1 ) so that Cγ

N = O(N -1 ), Cγ,α N = O((log(N )) 2 1-α 2α-1 N -α 2α-1
) and ŝN = O(log(N )N -1 2 ). Hence, averaging has allowed the concentration rate to go from the slow concentration rates o(N -ρ+ǫ ), o(N -ρ-(1-α) 2α-1 -ǫ ) for all ǫ > 0 and O log(N )N -(ρ-1 2 ) to the optimal rates O(N -1 ), O((log(N )) 2 1-α 2α-1 N -α 2α-1 ) and ŝN = O(log(N )N -1 2 ) for free, i.e. without any condition on the step sequence parameter c.

Concerning the bias, by averaging the bias sequence (δ k ) 1≤k≤N -1 we directly obtain the following bound

δN ≤ K |θ 0 -θ * | N + (2C α,µ ) 1 2 N ρ 2 -ǫ
, ∀ǫ > 0 Hence, we see that there is no sub-exponential decreasing of the impact of the initial condition but a decay at rate O(N -1 ). Consequently, this leads us to say that a stochastic approximation algorithm must be averaged after few iterations in practical implementations and not directly from the first step.

Euler Scheme: Proof of the Main Results

In this section we will assume that (HS) and (HD α ) are in force.

Proof of Theorem 2.1

The proof of Theorem 2.1 is divided into several propositions. Proposition 3.1. Denote by X ∆,0,x := (X ∆,0,x t k ) 0≤k≤N the scheme (1.2) with time step ∆ = T /N , N ∈ N * associated to the diffusion (SDE b,σ ) starting from x at time 0. Assume that the innovations (U i ) i≥1 of (1.2) satisfy (GC(β)) for some β > 0. Then, there exists ε β > 0 which only depends on the law µ such that for all λ < min(1, ε β (2ηαC σ T exp(CT )) -1 ), one has

sup 0≤n≤N log E x exp(λV α (X ∆,0,x tn )) ≤ λ exp(CT )V α (x) + 1 2 log E exp λ2ηαC σ T exp(CT )|U 1 | 2 . with C := C(b, σ, V, α, ∆) = α(C V C b ) 1 2 + βC σ α 2 (1 + 2η∆) 2 (C V + C b ) + αηC b ∆.
Proof. Using the concavity of x → x α , α ∈ (0, 1], we have for all k ≥ 0

V α (X ∆ t k+1 ) -V α (X ∆ t k )) ≤ αV α-1 (X ∆ t k )(V (X ∆ t k+1 ) -V (X ∆ t k )).
A Taylor expansion of order 2 of the function V , recalling that 2η = sup

x∈R d ∇ 2 V (x) < +∞, yields V (X ∆ t k+1 ) -V (X ∆ t k )) ≤ ∇V (X ∆ t k ).(X ∆ t k+1 -X ∆ t k ) + η|X ∆ t k+1 -X ∆ t k | 2 ,
which together with the previous inequality leads to

V α (X ∆ t k+1 ) -V α (X ∆ t k ) ≤ α∆ ∇V (X ∆ t k ).b(t k , X ∆ t k ) V 1-α (X ∆ t k ) + α∆ 1 2 ∇V (X ∆ t k ).σ(t k , X ∆ t k )U k+1 V 1-α (X ∆ t k ) + αη∆ 2 |b(t k , X ∆ t k )| 2 V 1-α (X ∆ t k ) + 2αη∆ 3 2 b(t k , X ∆ t k ).σ(t k , X ∆ t k )U k+1 V 1-α (X ∆ t k ) + αη∆ |σ(t k , X ∆ t k )U k+1 | 2 V 1-α (X ∆ t k ) . From (HD α ), for all (x, u) ∈ R d × R q , we clearly have sup t∈[0,T ] |∇V (x).b(t, x)| ≤ (C V C b ) 1 2 V (x) and sup t∈[0,T ] |σ(t, x)u| 2 ≤ C σ V 1-α (x)|u| 2 which yields V α (X ∆ t k+1 ) ≤ V α (X ∆ t k )(1 + α(C V C b ) 1 2 ∆ + αηC b ∆ 2 ) + α∆ 1 2 (1 + 2η∆) (∇V (X ∆ t k ) + b(X ∆ t k )).σ(X ∆ t k )U k+1 V 1-α (X ∆ t k ) + C σ αη∆|U k+1 | 2 .
Using (HD α ), ∀x ∈ R d the functions g(x, .) : u → (∇V (x)+b(x)).σ(x)u

V 1-α (x)
are Lipschitz, and more precisely satisfy

∀x ∈ R d , sup (u,u ′ )∈(R q ) 2 |g(x, u) -g(x, u ′ )| |u -u ′ | ≤ (C 1/2 V + C 1/2 b )C 1/2 σ V α 2 (x).
Hence, from the Cauchy Schwarz inequality and since the law of the innovations satisfy (GC(β)) for some β > 0, there exists ǫ β > 0 such that for λ < min(1, ε β (2ηαC σ ∆) -1 ), one has

E exp(λV α (X ∆ t k+1 )) F t k ≤ exp(λV α (X ∆ t k )(1 + α(C V C b ) 1 2 ∆ + αηC b ∆ 2 )) × E exp(2λα∆ 1 2 (1 + 2η∆)g(X ∆ t k , U k+1 )) F t k 1 2 × E exp(2ληαC σ ∆|U k+1 | 2 ) F t k 1 2 ≤ exp(λV α (X ∆ t k )(1 + α(C V C b ) 1 2 ∆ + αηC b ∆ 2 )) × exp(λ 2 βα 2 ∆(1 + 2η∆) 2 (C V + C b )C σ V α (X ∆ t k )) × E exp(2ληαC σ ∆|U 1 | 2 ) 1 2 ≤ exp(λC(∆)V α (X ∆ t k ))E exp(2ληαC σ ∆|U 1 | 2 ) 1 2 ,
where C(∆)

:= 1 + ∆ α(C V C b ) 1 2 + βC σ α 2 (1 + 2η∆) 2 (C V + C b ) + αηC b ∆ . Now define V k = V α (X ∆ t k ) C(∆) k , for k ∈ {0, • • • , N }.
Taking expectation in both sides of the previous inequality clearly implies

E [exp(λV k+1 )] ≤ E [exp(λV k )] E exp λ 2ηαC σ ∆ C(∆) k+1 |U 1 | 2 1 2
and by a straightforward induction, for n ∈ {0, • • • , N } we have

E [exp(λV n )] ≤ exp(λV 0 ) n-1 k=0 E exp λ 2ηαC σ ∆ C(∆) k+1 |U 1 | 2 1 2
, which finally yields, for λ < min(1,

ε β (2ηαC σ ∆C(∆) n ) -1 ), E exp(λV α (X ∆ tn )) ≤ exp(λC(∆) n V α (X 0 )) n-1 k=0 E exp λ2ηαC σ ∆C(∆) k+1 |U 1 | 2 1 2 . Observe now that C(∆) N ≤ exp(CT ) with C := C(b, σV, α, ∆) = α(C V C b ) 1 2 + βC σ α 2 (1 + 2η∆) 2 (C V + C b ) + αηC b ∆.
Using Jensen's inequality, the latter bound clairly provides the following control of the quantity of interest for λ < min(1,

ε β (2ηαC σ T exp(CT )) -1 ) sup 0≤n≤N log E exp(λV α (X ∆ tn )) ≤ λ exp(CT )V α (X 0 ) + 1 2 log E exp λ2ηαC σ T exp(CT )|U 1 | 2 .
Corollary 3.1. Under the same assumptions as Proposition 3.1, for all α ∈ ( 1 2 , 1], one has ∀λ ≥ 0, sup

0≤n≤N log E x exp(λV 1-α (X ∆ tn )) ≤ K 3.1 (λ ∨ λ α 2α-1 )
where K 3.1 := max (Ψ 1 (T, ∆, x, b, σ), Ψ 2 (T, ∆, x, b, σ)) and

Ψ 1 (T, ∆, x, b, σ) := e 2α-1 α ρ - 1-α 2α-1 exp ρ 1 -α α e CT V α (x) + 1 2 log E[e ǫ β (1-α) 2α |U| 2 ] + V 1-α (x) + C σ E[|U | 2 ] K 1-α α e (1-α)KT , Ψ 2 (T, ∆, x, b, σ) := ρ -1-α 2α-1 2α -1 α + ρ 1 -α α e CT V α (x) + 1 2 log E exp ǫ β (1 -α) 2α |U | 2 , ρ := 1 2 min(1, ε β (2ηαC σ T exp(CT )) -1 ), C := C(b, σV, α, ∆) = α(C V C b ) 1 2 + βC σ α 2 (1 + 2η∆) 2 (C V + C b ) + αηC b ∆ K := K(V, b, ∆) = (C V C b ) 1 2 + ηC b ∆ Proof. For λ ∈ [0, 1], one has E x [exp(λV 1-α (X tn ))] = 1 + λE x [V 1-α (X tn )] + k≥2 λ k k! E x [V (1-α)k (X tn )] ≤ 1 + λE x [V 1-α (X tn )] + λ k≥0 1 k! E x [V (1-α)k (X tn )] ≤ exp λ(E x [V 1-α (X tn )] + E x [e V 1-α (Xt n ) ]) ,
Tedious but simple computations, in the spirit of Proposition 3.1, show that

E x [V 1-α (X tn )] ≤ E x [V α (X tn )] 1-α α ≤ V 1-α (x) + C σ E[|U | 2 ] K 1-α α e (1-α)KT .

TRANSPORT-ENTROPY INEQUALITIES AND DEVIATION ESTIMATES FOR STOCHASTIC APPROXIMATIONS SCHEMES 19

with

K := K(V, b, ∆) = (C V C b ) 1 2 + ηC b ∆.
Thanks to the following Young inequality, for all ρ > 0, for all

x ∈ R d , V 1-α (x) ≤ 1-α α ρV α (x) + 2α-1 α ρ -1-α 2α-1 , which is valid if α ∈ ( 1 2 , 1], one has for ρ = ρ := 1 2 min(1, ε β (2ηαC σ T exp(CT )) -1 ) sup 0≤n≤N E x [e V 1-α (X ∆,0,x tn ) ] ≤ exp( 2α -1 α ρ -1-α 2α-1 ) sup 0≤n≤N E x exp 1 -α α ρV α (X ∆,0,x tn ) ≤ exp( 2α -1 α ρ -1-α 2α-1 ) exp ρ 1 -α α e CT V α (x) + 1 2 log E[exp( ǫ β (1 -α) 2α |U | 2 )]
where we used Proposition 3.1 for the last inequality. Now, for all λ > 1, using the Young type inequality λV

1-α (X tn ) ≤ ( 2α-1 α )ρ -1-α 2α-1 λ α 2α-1 + ( 1-α α )ρV α (X tn )
, valid for all ρ > 0 (to be chosen later on) and for all α ∈ ( 1 2 , 1], one derives

E x [exp(λV 1-α (X tn ))] ≤ exp ( 2α -1 α )ρ -1-α 2α-1 λ α 2α-1 E x exp 1 -α α ρV α (X tn ) ≤ exp Kλ α 2α-1 with K(ρ) := 2α-1 α ρ -1-α 2α-1 + log(E x exp 1-α α ρV α (X tn ) ) and 1-α α ρ < min(1, ε β (2ηαC σ T exp(CT )) -1
). We select ρ = ρ in the last inequality to complete the proof and use Proposition 3.1 to bound the quantity K(ρ).

Corollary 3.2. Under the same assumptions as Proposition 3.1, one has ∀λ ∈ [0, λ 3.2 ), sup

0≤n≤N log E x exp(λ 2 V 1/2 (X ∆ tn )) ≤ K 3.2 (λ/λ 3.2 ) 2 1 -(λ/λ 3.2 ) where K 3.2 := λ 2 3.2 exp(CT )(2V 1/2 (x)+2ηαC σ E[|U 1 | 2 ]T ) and λ 3.2 satisfies E[exp(λ 2 3.2 2ηαC σ T exp(CT )|U 1 | 2 )] ≤ 2.
Proof. By definition of λ 3.2 , we have ∀k ≥ 1,

λ 2k 3.2 (2ηαC σ T exp(CT )) k E[|U 1 | 2k ] ≤ 2k!. Consequently, setting temporarily C 1 := exp(CT )V 1/2 (x), C 2 := 2ηαC σ T exp(CT ) for sake of simplicity, simple computations show that log E exp λ 2 C 2 |U 1 | 2 -λ 2 C 2 E[|U 1 | 2 ] = log   1 + k≥1 λ 2k C k 2 E[|U 1 | 2k ] k!   -λ 2 C 2 E[|U 1 | 2 ] ≤ k≥2 λ 2k C k 2 E[|U 1 | 2k ] k! ≤ 2 k≥2 λ λ 3.2 2k ≤    2 (λ/λ3.2) 2 1-(λ/λ3.2) , if λ < λ 3.2 , +∞, otherwise.
hence, using Proposition 3.1 for α = 1 2 and ∀λ ∈ [0, λ 3.2 ), we clearly get

sup 0≤n≤N log E x exp(λ 2 V 1/2 (X ∆ tn )) ≤ λ 2 3.2 C 1 + C 2 E[|U 1 | 2 ] 2 (λ/λ 3.2 ) 2 + (λ/λ 3.2 ) 2 1 -(λ/λ 3.2 ) ≤ 2λ 2 3.2 C 1 + C 2 E[|U 1 | 2 ] 2 (λ/λ 3.2 ) 2 1 -(λ/λ 3.2 ) .
This completes the proof.

[P k,p (f )] 1 := sup (x,x ′ )∈(R d ) 2 |P k,p (f )(x) -P k,p (f )(x ′ )| |x -x ′ | ≤ [f ] 1 (1 + C(b, σ, ∆)∆) p-k 2
where [f ] 1 stands for the Lipschitz modulus of the function f and

C(b, σ, ∆) = 2[b] 1 + [σ] 2 1 + ∆[b] 2 1 . Proof.
Using the Cauchy Schwarz inequality and (HS), for all (x, y) ∈ (R d ) 2 and for all k ∈ {0, • • • , N -1}, one has

|P k (f )(x) -P k (f )(y)| ≤ [f ] 1 E f (x + b(t k , x)∆ + σ(t k , x)U 1 ) -f (y + b(t k , y)∆ + ∆ 1 2 σ(t k , y)U 1 ) ≤ [f ] 1 E x -y + (b(t k , x) -b(t k , y))∆ + ∆ 1 2 (σ(t k , x) -σ(t k , y))U 1 2 1 2 ≤ [f ] 1 (1 + C(b, σ, ∆)∆) 1 2 |x -y|.
A straightforward induction argument completes the proof.

Proposition 3.3. (Control of the Laplace transform) Denote by X ∆

T the value at time T of the scheme (1.2) associated to the diffusion (SDE b,σ ). Assume that the innovations (U n ) n≥1 in (1.2) satisfy (GC(β)) for some β > 0. Let f be a real-valued 1-Lipschitz-continuous function defined on R d . For all λ ≥ 0 and for all α ∈ ( 1 2 , 1], one has

E x exp(λf (X ∆ T )) ≤ exp(λE x f (X ∆ T ) ) exp K 3.1 (ϕ(T, b, σ, ∆) ∨ ϕ(T, b, σ, ∆) α 2α-1 )(λ 2 ∨ λ 2α 2α-1 ) , with ϕ(T, b, σ, ∆) := C σ β (1+C(∆)∆) 4C(∆) e 3C(∆)T and C(∆) := 2[b] 1 + [σ] 2 1 + ∆[b] 2 1 . If α = 1 2 , for all λ ∈ [0, ϕ(T, b, σ, ∆) -1/2 λ 3.2 ), one has E x exp(λf (X ∆ T )) ≤ exp(λE x f (X ∆ T ) ) exp K 3.2 (λϕ(T, b, σ, ∆) 1/2 /λ 3.2 ) 2 1 -(λϕ(T, b, σ, ∆) 1/2 /λ 3.2 ) .
Proof. As mentionned earlier on in the introduction, we begin our proof using that the law µ of the innovation satisfies (GC(β)) and (HD α ). Hence, for λ ≥ 0 and k ∈ {0, • • • , N -1}, one has

P k (exp(λf ))(x) = E exp λf x + b(t k , x)∆ + σ(t k , x)∆ 1/2 U k+1 ≤ exp λP k (f )(x) + β λ 2 4 [f ] 2 1 ∆|σ(t k , x)| 2 ≤ exp λP k (f )(x) + C σ β λ 2 4 [f ] 2 1 ∆V 1-α (x) . (3.1)
Taking expectation from both sides of the last inequality and using the Hölder inequality with conjugate exponents (p, q) (to be specified later on) leads to

E x exp(λf (X ∆ t k+1 )) ≤ E x exp(λpP k (f )(X ∆ t k )) 1 p E x exp qC σ β 4 ∆λ 2 [f ] 2 1 V 1-α (X ∆ t k ) 1 q . (3.2)
Now, we apply the last inequality for f := P k+1,N (f ) and obtain

E x exp(λP k+1,N (f )(X ∆ t k+1 )) ≤ E x exp(λpP k,N (f )(X ∆ t k )) 1 p E x exp qC σ β 4 ∆λ 2 [P k+1,N (f )] 2 1 V 1-α (X ∆ t k ) 1 q
Consequently, an elementary induction yields

E x exp(λf (X ∆ T )) = E x exp(λP N,N (f )(X ∆ tN )) ≤ E x exp(λp N P 0,N (f )(x)) 1 p N × N -1 k=0 E x exp C σ β 4 λ 2 qp 2k ∆[P N -k,N (f )] 2 1 V 1-α (X ∆ t N -k-1 ) 1 q 1 p k ≤ exp(λE x f (X ∆ T ) ) exp N -1 k=0 1 p k 1 q sup 0≤n≤N log E x e Cσ β 4 λ 2 ∆qp 2N (1+C(∆)∆) N V 1-α (X ∆ tn )
where we used Proposition 3.2 for the last inequality. Observe now that since (p, q) are conjugate exponents, we have

1 q N -1 k=0 1 p k = 1 q (1 -1 p N ) 1 1-1 p ≤ 1 q p p-1 = 1, so that E x exp(λf (X ∆ T )) ≤ exp(λE x f (X ∆ T ) ) exp sup 0≤n≤N log E x e Cσ β 4 λ 2 ∆qp 2N (1+C(∆)∆) N V 1-α (X ∆ tn )
.

Setting p := 1 + C(∆)∆, q = p p-1 = 1+C(∆)∆ C(∆)∆
and using the straightforward inequality (1 + C(∆)∆) 3N ≤ exp(3C(∆)T ), we derive

E x exp(λf (X ∆ T )) ≤ exp(λE x f (X ∆ T ) ) exp sup 0≤n≤N log E x e Cσ β(1+C(∆)) 4C(∆) e 3C(∆)T λ 2 V 1-α (X ∆ tn )
.

We set ϕ(T, b, σ,

∆) := C σ β (1+C(∆)∆) 4C(∆) e 3C(∆)T . For α ∈ ( 1 2 , 1], Corollary 3.1 clearly implies E x exp(λf (X ∆ T )) ≤ exp(λE x f (X ∆ T ) ) exp K 3.1 (ϕ(T, b, σ, ∆) ∨ ϕ(T, b, σ, ∆) α 2α-1 )(λ 2 ∨ λ 2α 2α-1 )
and for α = 1 2 , according to Proposition 3.2, for λ < ϕ(T, b, σ, ∆) -1/2 λ 3.2 , one has

E x exp(λf (X ∆ T )) ≤ exp(λE x f (X ∆ T ) ) exp K 3.2 (λϕ(T, b, σ, ∆) 1/2 /λ 3.2 ) 2 1 -(λϕ(T, b, σ, ∆) 1/2 /λ 3.2 ) .

Proof of Theorem 2.2

We will prove the result for the process X solution of (SDE b,σ ). The proof for the continuous Euler scheme is similar.

Lemma 3.1. Under the assumptions of Theorem 2.2, for all p ≥ 1, one has

E x [ sup 0≤t≤T |X t | 2p ] ≤ (1 + |x|) 2p exp(26p 2 (1 + (C b ∨ C σ )T )). Proof. Let g : x → 1 + |x| 2 satisfying for all x ∈ R d , ∇g(x) = g -1 (x)x, ∇ 2 g(x) = g -1 (x)I d -g -3 (x)xx * and V : x → g 2p (x).
We apply Itô's formula to the process V (X t ) with ∇V (x) = 2pg(x) 2p-1 ∇g(x) and

∇ 2 V (x) = 2pg(x) 2p-1 ∇ 2 g(x) + 2p(2p -1)g(x) 2p-2 ∇g(x)∇g(x) * noticing that for all t ∈ [0, T ] ∇V (x).b(t, x) + 1 2 T r(σ * ∇ 2 V σ)(t, x) ≤ 2pC b g(x) 2p-1 (1 + |x|) + 1 2 C σ (1 + |x| 2 )||∇ 2 V (x)|| ≤ 4pC b g(x) 2p + 1 2 C σ (1 + |x| 2 )(4pg(x) 2p-2 + 2p(2p -1)g(x) 2p-2 ) ≤ 4p(C b ∨ C σ )g(x) 2p + 2p(C b ∨ C σ )g(x) 2p + p(2p -1)(C b ∨ C σ )g(x) 2p ≤ 8p 2 (C b ∨ C σ )V (x)
we clearly obtain,

V (X τm t ) ≤ V (x) + 8p 2 (C b ∨ C σ ) t 0 V (X τm s )ds + t∧τm 0 (∇V * σ)(X τm s )dW s , (3.3)
where we classically introduced the stopping time τ m := inf {t ≥ 0 : |X t -x| ≥ m} for m ∈ N * and the notation X τm := (X t∧τm ) t≥0 . The stochastic integral M m t := t∧τm 0 (∇V * σ)(X τm s )dW s defines a continuous martingale so that taking expectation in the previous inequality clearly yields

E x [V (X τm t )] ≤ V (x) + 8p 2 (C b ∨ C σ ) t 0 E x [V (X τm s )]ds.
Now, using Gronwall's lemma we derive

∀m ∈ N * , sup t∈[0,T ] E x [V (X τm t )] ≤ (1 + |x|) 2p exp(8p 2 (C b ∨ C σ )T )
As τ m → +∞ a.s., as m → +∞ (since sup s∈[0,t] |X s | < +∞) using Fatou's lemma, we finally obtain for all p ≥ 1 sup

0≤t≤T E x [V (X t )] = sup 0≤t≤T E x [g(X t ) 2p ] ≤ (1 + |x|) 2p exp(8p 2 (C b ∨ C σ )T ). (3.4)
We then observe that Itô's formula also implies

E x [ sup 0≤s≤t V (X τm t )] ≤ V (x) + 8p 2 (C b ∨ C σ ) t 0 E x [ sup 0≤u≤s V (X τm u )]ds + E x [(M m t ) * ] (3.5)
where (M m t ) * := sup 0≤s≤t M m s . Combining Jensen's and Doob's inequalities, one clearly gets

E x [(M m t ) * ] 2 ≤ E x [((M m t ) * ) 2 ] ≤ 4E x [(M m t ) 2 ] ≤ 16p 2 C σ t 0 E x [g(X τm s ) 4p ]ds ≤ 16p 2 C σ T (1 + |x|) 4p exp(32p 2 (C b ∨ C σ )T ) where we used ∀x ∈ R d , (∇V * σ) 2 (x) ≤ 4p 2 C σ g(x) 4p-2 (1+|x| 2 ) = 4p 2 C σ g(x)
4p and (3.4) for the last inequality. Consequently, plugging the latter estimate into (3.5), one has for all t ∈ [0, T ]

E x [ sup 0≤s≤t V (X τm t )] ≤ V (x) + 4p(C σ T ) 1 2 (1 + |x|) 2p exp(16p 2 (C b ∨ C σ )T ) + 8p 2 (C b ∨ C σ ) t 0 E x [ sup 0≤u≤s V (X τm u )]ds ≤ (1 + |x|) 2p (1 + 4p(C σ T ) 1 2 exp(16p 2 (C b ∨ C σ )T )) + 8p 2 (C b ∨ C σ ) t 0 E x [ sup 0≤u≤s
V (X τm u )]ds so that using Gronwall's lemma yields and passing to the limit m → +∞, for all p ≥ 1

E x [ sup 0≤t≤T |X t | 2p ] ≤ E x [ sup 0≤s≤T V (X t )] ≤ 2(1 + |x|) 2p exp(26p 2 (1 + (C b ∨ C σ )T )).
For all real-valued and 1-Lipschitz function f defined on C and for all p ≥ 1, one has

E x [|f (X) -E x [f (X)]| 2p ] = E x [|f (X) -f (0) + f (0) -E x [f (X)]| 2p ] ≤ 2 2p E x [||X|| 2p ∞ ] ≤ 2 2p+1 (1 + |x|) 2p exp(26p 2 (1 + (C b ∨ C σ )T )) (3.6)
where we used Lemma 3.1 for the last inequality. Now, combining the Chebyshev and Rosenthal inequalities for independent zero-mean random variables (see e.g. [START_REF] Johnson | Best constants in moment inequalities for linear combinations of independent and exchangeable random variables[END_REF]), for all p ≥ 1, there exists C 2p > 0 such that

P x 1 M | M k=1 f (X k ) -E x [f (X)]| ≥ r ≤ E x [( M k=1 f (X k ) -E x [f (X)]) 2p ] r 2p M 2p ≤ C 2p E x [|f (X) -E x [f (X)]| 2p ] r 2p M p ≤ 2 (2(1 + |x|)) 2p exp(28p 2 (1 + (C b ∨ C σ )T )) r 2p M p := 2 exp(-ϕ(p)) with ϕ(p) := -κ(b, σ, T )p 2 + p log( r 2 M (2(1+|x|)) 2
) and where we used for all p ≥ 1, C 2p ≤ (2p) 2p ≤ exp(2p 2 ), see e.g. p.235-236 in [START_REF] Johnson | Best constants in moment inequalities for linear combinations of independent and exchangeable random variables[END_REF], and (3.6) for the last inequality. Optimizing the latter inequality with respect to p with p ≥ 1, i.e. selecting p = 1 2κ(b,σ,T ) log( r 2 M

(2(1+|x|)) 2 ), we obtain

P x 1 M | M k=1 f (X k ) -E x [f (X)]| ≥ r ≤ 2 exp - 1 4κ(b, σ, T ) log r 2 M (2(1 + |x|)) 2 2
for r 2 M ≥ (2(1 + |x|)) 2 exp(2κ(b, σ, T )). Otherwise, using the Jensen and Rosenthal inequalities, one has for all p ∈ [0, 1]

E x [( M k=1 f (X k ) -E x [f (X)]) 2p ] ≤ E x [( M k=1 f (X k ) -E x [f (X)]) 2 ] p ≤ M C 2 E x [|f (X) -E x [f (X)]| 2 ] p ≤ M p 4(2(1 + |x|)) 2 exp(κ(b, σ, T ))
p where we used (3.6) for the last inequality. Now, noticing that we have 4e ≤ exp(κ(b, σ, T )), Chebyshev's inequality yields

P x 1 M | M k=1 f (X k ) -E x [f (X)]| ≥ r ≤ C p r 2p M p ≤ 2 (Cp) p r 2p M p ≤ 2 exp(-ϕ(p)) with ϕ(p) := -p log(p) + p log( r 2 M C ), C := (2(1 + |x|)) 2 exp(2κ(b, σ, T ) -1
) and where we used that for all p ≥ 0, C p ≤ 2(Cp) p since the function p → 2p p is minimized for p = exp(-1) and 2 exp(-1/e)) > 1. Consequently, optimizing over p such that p ≤ 1, i.e. selecting p = r 2 M Ce , one has

P x 1 M | M k=1 f (X k ) -E x [f (X)]| ≥ r ≤ 2 exp - r 2 M (2(1 + |x|)) 2 exp(2κ(b, σ, T ))
for r 2 M ≤ Ce = (2(1 + |x|)) 2 exp(2κ(b, σ, T )). This completes the proof.

Stochastic Approximation Algorithm: Proof of the main Results

Throughout this section we will assume that (HL), (HLS) α and (HUA) are in force.

Proof of Theorem 2.3

The proof of Theorem 2.3 is divided into several propositions. Proposition 4.1. Denote by θ := (θ n ) 0≤n≤N the scheme (1.4) with step sequence γ = (γ n ) 0≤n≤N satisfying (1.5). Assume that the innovations (U i ) i≥1 of (1.4) satisfy (GC(β)) for some β > 0. Then, there exists ε β > 0 which only depends on the law µ such that for all λ < min(1, ε β (8ηαC 2 α Π 2,N ) -1 ), one has

sup 0≤n≤N log (E θ0 [exp(λL α (θ n ))]) ≤ (L α (θ 0 )+C N -1 k=0 γ 2 k+1 )Π 2,N λ+ 1 2 N -1 k=0 γ 2 k+1 log E exp 8ηαC 2 α Π 2,N λ|U | 2 . with Π 2,N = Π 2,N (α) := N -1 k=0 (1 + (2ηαC h + β 2 α 2 C 2 α )γ 2 k+1 ) and C = 4ηαC 2 α E[|U | 2 ].
Proof. The proof relies on similar arguments as those used in the proof of Proposition 3.1. Using the concavity of x → x α , α ∈ (0, 1], a Taylor expansion of order 2 of the function L, and finally (HLS) α , for all k ∈ {0, • • • , N -1}, we have

L α (θ k+1 ) -L α (θ k ) ≤ αL α-1 (θ k ) ∇L(θ k ).(θ k+1 -θ k ) + η|θ k+1 -θ k | 2 , = -γ k+1 αL α-1 (θ k ) ∇L(θ k ), h(θ k ) -γ k+1 αL α-1 (θ k ) ∇L(θ k ), (H(θ k , U k+1 ) -h(θ k ) + αηγ 2 k+1 L α-1 (θ k )|H(θ k , U k+1 )| 2 , ≤ -γ k+1 αL α-1 (θ k ) ∇L(θ k ), H(θ k , U k+1 ) -h(θ k ) + 2ηαγ 2 k+1 L α-1 (θ k )|H(θ k , U k+1 ) -h(θ k )| 2 + 2ηαγ 2 k+1 L α-1 (θ k )|h(θ k )| 2 .
Let us note that (HLS)

α implies that ∀(θ, u) ∈ R d × R q , |H(θ, u) -h(θ)| 2 = |H(θ, u) -E[H(θ, U )]| 2 ≤ 2C 2 α L 1-α (θ)(E[|U | 2 ] + |u| 2 ) which leads to L α (θ k+1 ) -L α (θ k ) ≤ -γ k+1 αL α-1 (θ k ) ∇L(θ k ), H(θ k , U k+1 ) -h(θ k ) + 4ηαC 2 α γ 2 k+1 E[|U | 2 ] + 4ηαC 2 α γ 2 k+1 |U k+1 | 2 + 2ηαC h γ 2 k+1 L α (θ k ).
Using again (HLS) α , ∀θ ∈ R d the functions g(θ, .) : u → ∇L(θ),H(θ,u)-h(θ)

L 1-α (θ)
are Lipschitz and more precisely satisfy

∀θ ∈ R d , sup (u,u ′ )∈(R q ) 2 |g(θ, u) -g(θ, u ′ )| |u -u ′ | ≤ C α L α 2 (θ). Consequently, denoting C = 4ηαC 2 α E[|U | 2 ]
, from the Cauchy-Schwarz inequality and since the law of the innovation satisfies (GC(β)) for some β > 0, there exists ǫ β > 0 such that for λ < min(1, ε β (8ηαC 2 α γ 2 1 ) -1 ), one has

E [ exp(λL α (θ k+1 )| F k ] ≤ exp(λ(1 + 2ηαC h γ 2 k+1 )L α (θ k )) exp(Cγ 2 k+1 λ)E [ exp(-2αλγ k+1 g(θ k , U k+1 ))| F k ] 1 2 × E exp(8ηαλC 2 α γ 2 k+1 |U k+1 | 2 ) F k 1 2 ≤ exp(λ(1 + (2ηαC h + β 2 C 2 α α)γ 2 k+1 )L α (θ k )) exp(Cγ 2 k+1 λ)E exp(8ηαλC 2 α γ 2 k+1 |U | 2 ) 1 2
In the aim of simplifying notations, we define Π 2,n :=

n-1 k=0 (1 + (2ηαC h + β 2 C 2 α α)γ 2 k+1
) and temporarily set

L k := L α (θ k ) Π 2,k , for k ∈ {0, • • • , N }.
Taking expectation in both sides of the previous inequality clearly implies

E θ0 [exp(λL k+1 )] ≤ E θ0 [exp(λL k )] exp C γ 2 k+1 Π 2,k+1 λ E exp 8ηαC 2 α γ 2 k+1 Π 2,k+1 λ|U | 2 1 2
and by a straightforward induction, for n ∈ {0, • • • , N } we have

E θ0 [exp(λL n )] ≤ exp(λL 0 ) exp C n-1 k=0 γ 2 k+1 Π 2,k+1 λ n-1 k=0 E exp 8ηαC 2 α γ 2 k+1 Π 2,k+1 λ|U | 2 1 2
, which finally yields for λ < min(1, ε β (8ηαC 2 α γ 2 1 ) -1 )

E θ0 [exp(λL α (θ n ))] ≤ exp(Π 2,n L α (θ 0 )λ) exp C n-1 k=0 Π 2,n Π 2,k+1 γ 2 k+1 λ n-1 k=0 E exp 8ηαC 2 α Π 2,n Π 2,k+1 γ 2 k+1 λ|U | 2 1 2
.

Up to a modification of a constant, we can assume without loss of generality that sup 0≤n≤N γ n+1 = γ 1 ≤ 1 so that using the Jensen's inequality, the latter bound clairly provides the following control of the quantity of interest for λ < min(1,

ε β (8ηαC 2 α Π 2,N ) -1 ) sup 0≤n≤N log E θ0 e λL α (θn) ≤ L α (θ 0 ) + C N -1 k=0 γ 2 k+1 Π 2,N λ + 1 2 N -1 k=0 γ 2 k+1 log E e 8ηαC 2 α Π2,N λ|U| 2 .
Corollary 4.1. Assume that the assumptions of Proposition 4.1 are satisfied. Then, for all α ∈ ( 1 2 , 1], one has ∀λ ≥ 0, sup

0≤n≤N log E θ0 exp(λL 1-α (θ n )) ≤ K 4.1 (λ ∨ λ α 2α-1 )
where K 4.1 := max(Ψ 1 (γ, α, θ 0 , H), Ψ 2 (γ, α, θ 0 , H)) and

Ψ 1 (γ, α, θ 0 , H) = L 1-α (θ 0 ) + (8ηαC 2 α E[|U | 2 ] N -1 k=0 γ 2 k+1 ) 1-α α N -1 k=0 (1 + 2η(1 -α)C h γ 2 k+1 ) + exp 2α -1 α ρ -1-α 2α-1 × exp L α (θ 0 ) + 2αC N -1 k=0 γ 2 k+1 Π 2,N ρ 1 -α α + 1 2 N -1 k=0 γ 2 k+1 log E e ε β (1-α) 2α |U| 2 Ψ 2 (γ, α, θ 0 , H) = 2α -1 α ρ -1-α 2α-1 + L α (θ 0 ) + C N -1 k=0 γ 2 k+1 Π 2,N ρ 1 -α α + 1 2 N -1 k=0 γ 2 k+1 log E e ε β (1-α) 2α |U| 2 ρ = 1 2 min(1, ε β (8ηαC 2 α Π 2,N ) -1 )
Proof. We only give a sketch of proof since it is rather similar to the one of Corollary 3.1. For λ ∈ [0, 1], one has

E θ0 [exp λL 1-α (θ n ) ] ≤ exp λ(E θ0 [L 1-α (θ n )] + E θ0 [exp(L 1-α (θ n ))] .
Tedious but simple computations in the spirit of Proposition 4.1 easily show that

sup 0≤n≤N E θ0 [L 1-α (θ n )] ≤ sup 0≤n≤N E θ0 [L α (θ n )] 1-α α ≤ L 1-α (θ 0 ) + (8ηαC 2 α E[|U | 2 ] N -1 k=0 γ 2 k+1 ) 1-α α N -1 k=0 (1+2η(1-α)C h γ 2 k+1 ).
Moreover, thanks to the Young type inequality L 1-α (θ) ≤ 1-α α ρL α (θ) + 2α-1 α ρ -1-α 2α-1 , for every (ρ, θ) ∈ R * + × R d and α ∈ ( 1 2 , 1] and using Proposition 4.1, one obtains for

ρ = ρ := 1 2 min(1, ε β (8ηαC 2 α Π 2,N ) -1 ) sup 0≤n≤N E θ0 [e L 1-α (θn) ] ≤ exp 2α -1 α ρ -1-α 2α-1 exp L α (θ 0 ) + C N -1 k=0 γ 2 k+1 Π 2,N ρ 1 -α α + 1 2 N -1 k=0 γ 2 k+1 log E e ε β (1-α) 2α |U| 2 , so that for all λ ∈ [0, 1] E θ0 [exp λL 1-α (θ n ) ] ≤ Ψ 1 (γ, α, θ 0 , H)λ.
Now, for λ > 1, we use the Young-type inequality λL

1-α (θ n ) ≤ 2α-1 α ρ -1-α 2α-1 λ α 2α-1 + 1-α α ρL α (θ n ) to derive E θ0 [exp(λL 1-α (θ n ))] ≤ exp Kλ α 2α-1 with K(ρ) := 2α-1 α ρ -1-α 2α-1 + log E θ0 exp 1-α α ρL α (θ n ) and 1-α α ρ < min(1, ε β (8ηαC 2 α Π 2,N ) -1
). We select ρ = ρ in the last inequality and use Proposition 4.1 to bound the quantity K(ρ).

[P k,p (f )] 1 := sup (θ,θ ′ )∈(R d ) 2 |P k,p (f )(θ) -P k,p (f )(θ ′ )| |θ -θ ′ | ≤ [f ] 1 p-1 i=k (1 -2λγ i+1 + C H,µ γ 2 i+1 ) 1 2
where [f ] 1 stands for the Lipschitz modulus of the function f and

C H,µ := 2C 2 H (1 + E[|U | 2 ]
). Proof. Using the Cauchy-Schwarz inequality, (HUA) then (HL), for all (θ, θ ′ ) ∈ (R d ) 2 , one has

|P k (f )(θ) -P k (f )(θ ′ )| ≤ E [|f (θ -γ k+1 H(θ, U k+1 )) -f (θ ′ -γ k+1 H(θ ′ , U k+1 ))|] ≤ [f ] 1 E (θ -θ ′ -γ k+1 (H(θ, U k+1 ) -H(θ ′ , U k+1 ))) 2 1 2 ≤ [f ] 1 (θ -θ ′ ) 2 -2γ k+1 θ -θ ′ , h(θ) -h(θ ′ ) + γ 2 k+1 E |H(θ, U k+1 ) -H(θ ′ , U k+1 )| 2 1 2 ≤ [f ] 1 (1 -2λγ k+1 + 2C 2 H (1 + E[|U | 2 ])γ 2 k+1 ) 1 2 |θ -θ ′ |.
A straightforward induction argument completes the proof.

Proposition 4.3. (Control of the Laplace transform) Denote by θ N the value at step N of the stochastic approximation algorithm (1.4) with step sequence γ := (γ n ) n≥1 satisfying (1.5). Assume that the innovations (U n ) n≥1 in (1.4) satisfy (GC(β)) for some β > 0. Let f be a real-valued 1-Lipschitz-continuous function defined on R d . Then, for all λ ≥ 0, for all N ≥ 1, for all α ∈ ( 1 2 , 1], one has

∀λ ≥ 0, E θ0 [exp(λf (θ N ))] ≤ exp (E θ0 [λf (θ N ))]) exp ϕ α (γ, H, θ 0 )(C γ N λ 2 ∨ C γ,α N λ 2α 2α-1 )
with the two concentration rates C γ N :=

N -1 k=0 γ 2 k+1 Π1,N Π 1,k , with Π 1,N := N -1 k=0 (1 -2λγ k+1 + C H,µ γ 2 k+1 ) and C γ,α N := N -1 k=0 γ 2α 2α-1 k+1 ( Π1,N Π 1,k ) 2α 2α-1 ((k+1) log 2 (k+4))
1-α 2α-1 for all N ≥ 1 and where ϕ α (γ, H, θ 0 ) := K 4.1 2

1-α 2α-1 βC 2 α 4 ∨ ( βC 2 α 4 ) α 2α-1 exp 1 2α-1 N -1 k=0 1 (k+1) log 2 (k+4) . If α = 1
2 , then there exists two positive constants λ 4.1 and ϕ 1/2 (γ, H, θ 0 ) such that

∀λ ∈ [0, λ 4.1 /s N ), E θ0 [exp(λf (θ N ))] ≤ exp (λE θ0 [f (θ N )]) exp 2ϕ 1/2 (γ, H, θ 0 )C γ N (λ/λ 4.1 ) 2 1 -(λs N /λ 4.1 ) with sN := max 0≤k≤N -1 (k + 1) 1/2 log(k + 4)γ k+1 Π1,N Π 1,k 1 2 exp( N -1 p=0 1 (p+1) log 2 (p+4) ).
Proof. The proof relies on similar arguments as those used for the proof of Proposition 3.3. For λ ≥ 0 and k ∈ {0, • • • , N -1}, one has

P k (exp(λf ))(θ) ≤ exp λP k (f ) + λ 2 4 βγ 2 k+1 [f ] 2 1 C 2 α L 1-α (θ)
Taking expectation on both sides of the last inequality with θ = θ k and applying the Hölder inequality with conjugate exponents (p k , q k ) (to be fixed later on), one obtains

E θ0 [exp(λf (θ k ))] ≤ E θ0 [exp (λp k P k (f )(θ k ))] 1 p k E θ0 exp q k λ 2 4 βγ 2 k+1 [f ] 2 1 C 2 α L 1-α (θ k ) 1 q k
and applying the last inequality to f := P k+1,N (f ) yields

E θ0 [exp(λP k+1,N (f )(θ k ))] ≤ E θ0 [exp (λp k P k,N (f )(θ k ))] 1 p k E θ0 exp q k λ 2 4 βγ 2 k+1 [P k+1,N (f )] 2 1 C 2 α L 1-α (θ k ) 1 q k . (4.1) We use Corollary 4.1 to obtain for α ∈ ( 1 2 , 1] E θ0 exp q k λ 2 4 βγ 2 k+1 [P k+1,N (f )] 2 1 C 2 α L 1-α (θ k ) 1 q k ≤ exp K 4.1 βC 2 α 4 ∨ βC 2 α 4 α 2α-1 ×(γ 2 k+1 [P k+1,N (f )] 2 1 λ 2 ∨ γ 2α 2α-1 k+1 [P k+1,N (f )] 2α 2α-1 1 q 1-α 2α-1 k λ 2α 2α-1 ) := f k (λ)
where we temporarily set f k (λ) := exp K 4.1

βC 2 α 4 ∨ βC 2 α 4 α 2α-1 (γ 2 k+1 [P k+1,N (f )] 2 1 λ 2 ∨ γ 2α 2α-1 k+1 [P k+1,N (f )] 2α 2α-1 1 q 1-α 2α-1 k λ 2α 2α-1 )
for all λ ≥ 0 in the interests of simplifying notation and analysis. Now, an elementary induction argument leads to

E θ0 [exp(λf (θ N ))] = E θ0 [exp(λP N,N f (θ N ))] ≤ E θ0 [exp(λ N -1 k=0 p k P 0,N (f )(θ 0 ))] 1 N -1 k=0 p k N -1 k=0 f N -1-k λ k i=1 p N -i 1 k i=1 p N -i (4.2) We select p k := 1 + 1 (k+1) log 2 (k+4) , q k = (1 + 1 (k+1) log 2 (k+4) )(k + 1) log 2 (k + 4) ≤ 2(k + 1) log 2 (k + 4), k = 0, • • • , N -1 so that N -1
k=0 p k converges and more precisely we have

N -1 k=0 p k < exp( N -1 k=0 1 (k+1) log 2 (k+4) ) < ∞. We introduce for sake of simplicity ϕ α (γ, H, θ 0 ) := K 4.1 2 1-α 2α-1 βC 2 α 4 ∨ ( βC 2 α 4 ) α 2α-1 exp 1 2α-1 N -1 k=0 1
(k+1) log 2 (k+4) . Now, using Proposition 4.2 and Corollary 4.1, we easily derive from (4.2)

∀λ ≥ 0, E θ0 [exp(λf (θ N ))] ≤ exp (E θ0 [λf (θ N ))]) exp ϕ α (γ, H, θ 0 )(C γ N λ 2 ∨ C γ,α N λ 2α 2α-1 ) with C γ,α N := N -1 k=0 γ 2α 2α-1 k+1 ( Π1,N Π 1,k ) 2α 2α-1 ((k + 1) log 2 (k + 4)) 1-α 2α-1 . For α = 1
2 , we start from (4.1). First, we use the control obtained in Proposition 4.1 to derive

E θ0 exp q k λ 2 4 βγ 2 k+1 [P k+1,N (f )] 2 1 C 2 1/2 L 1 2 (θ k ) 1 q k ≤ exp L 1 2 (θ 0 ) + C N -1 p=0 γ 2 p+1 Π 2,N (1/2) βC 2 1/2 4 γ 2 k+1 [P k+1,N (f )] 2 1 λ 2 + 1 q k 1 2 N -1 p=0 γ 2 p+1 × log E exp βηC 4 1/2 Π 2,N (1/2) q k γ 2 k+1 [P k+1,N (f )] 2 1 λ 2 |U | 2 .
To simplify the latter bound, that is to obtain an explicit and computable formula for the second term appearing in the right hand side, we will need the following lemma:

Lemma 4.1. For all λ ∈ [0, λ 4.1 /s 1/2 N ), one has log E exp βηC 4 1/2 Π 2,N (1/2) q k γ 2 k+1 [P k+1,N (f )] 2 1 λ 2 |U | 2 ≤ βηC 4 1/2 Π 2,N (1/2) E[|U | 2 ]q k γ 2 k+1 [P k+1,N (f )] 2 1 λ 2 + 2q k γ 2 k+1 [P k+1,N (f )] 2 1 (λ/λ 4.1 ) 2 1 -(λs 1/2 N /λ 4.1 ) , with s N := max 0≤k≤N -1 q k γ 2 k+1 Π1,N Π 1,k and λ 4.1 satisfies E[exp(λ 2 4.1 βηC 4 1/2 Π 2,N (1/2) |U | 2 )] ≤ 2.
Proof. The proof is similar to the proof of Corollary 3.2. By definition of λ

4.1 , λ 2p 4.1 (βηC 4 1/2 Π 2,N (1/2)/2) p E[|U | 2p ] ≤ 2p!, ∀p ≥ 1. Hence, setting C 1 := βηC 4 1/2 Π 2,N (1/2) we easily deduce, log E e λ 2 C1q k γ 2 k+1 [P k+1,N (f )] 2 1 |U| 2 -λ 2 C 1 q k γ 2 k+1 [P k+1,N (f )] 2 1 E[|U | 2 ] ≤ p≥2 λ 2p C p 1 (q k γ 2 k+1 [P k+1,N (f )] 2 1 ) p E[|U | 2p ] p! ≤ 2 p≥2 λ 2 q k γ 2 k+1 [P k+1,N (f )] 2 1 λ 2 4.1 p ≤    2q k γ 2 k+1 [P k+1,N (f )] 2 1 (λ/λ4.1) 2 1-(λs 1/2 N /λ4.1) , if λ < λ 4.1 /s 1/2 N , +∞, otherwise.
This completes the proof.

Using the previous lemma, we obtain for all λ ∈ [0, λ 4.1 /s

1/2 N ), E θ0 exp q k λ 2 4 βγ 2 k+1 [P k+1,N (f )] 2 1 C 2 1/2 L 1 2 (θ k ) 1 q k ≤ exp Ψ(N, γ, θ 0 )γ 2 k+1 [P k+1,N (f )] 2 1 λ 2 + N -1 p=0 γ 2 p+1 γ 2 k+1 [P k+1,N (f )] 2 1 (λ/λ 4.1 ) 2 1 -(λs 1/2 N /λ 4.1 )
, where we introduced the notation Ψ(N, γ, θ 0

) := L 1 2 (θ 0 ) + C N -1 p=0 γ 2 p+1 Π 2,N (1/2) βC 2 1/2 4 +βηC 4 1/2 Π 2,N (1/2) E[|U | 2 ]
. Now, as for α ∈ ( 1 2 , 1], an induction argument in the spirit of (4.2) yields for all λ ∈ [0, λ 4.1 /s N )

E θ0 [exp(λf (θ N ))] ≤ exp (λE θ0 [f (θ N )]) exp C γ N Ψ (N, γ, θ 0 ) e N -1 k=0
1 (k+1) log 2 (k+4) λ 2 +e N -1 k=0 1 (k+1) log 2 (k+4) N -1 p=0 γ 2 p+1 C γ N (λ/λ 4.1 ) 2 1 -(λs N /λ 4.1 ) , ≤ exp (λE θ0 [f (θ N )]) exp 2ϕ 1/2 (γ, H, θ 0 )C γ N (λ/λ 4.1 ) 2 ∨ (λ/λ 4.1 ) 2 1 -(λs N /λ 4.1 ) = exp (λE θ0 [f (θ N )]) exp 2ϕ 1/2 (γ, H, θ 0 )C γ N (λ/λ 4.1 ) 2 1 -(λs N /λ 4.1 ) with ϕ 1/2 (γ, H, θ 0 ) := exp( N -1 k=0 1 (k+1) log 2 (k+4) )(λ 2 4.1 Ψ(N, γ, θ 0 )+ N -1 p=0 γ 2 p+1 ), sN := s 1/2 N exp( N -1 k=0 1 (k+1) log 2 (k+4)
), and where we used again

N -1 k=0 p k < exp( N -1 k=0 1 (k+1) log 2 (k+4) ).
In contrast to Euler like schemes, a bias appears in the non-asymptotic deviation bound for the stochastic approximation algorithm. Consequently, it is crucial to have a control on it. At step n of the algorithm, it is given by δ

n := E[|θ n -θ * |].
Under the current assumptions (HL), (HLS) α , (HUA), we have the following proposition.

Proposition 4.4 (Control of the bias). For all n ≥ 1, we have

δ n ≤ exp (-λΓ 1,n + C α,µ Γ 2,n ) |θ 0 -θ * |+(2C α,µ ) 1 2 n-1 k=0 γ 2 k+1 exp (-2λ(Γ 1,n -Γ 1,k+1 ) + 2C α,µ (Γ 2,n -Γ 2,k+1 )) 1 2 , where Γ 1,n := n k=1 γ k , Γ 2,n := n k=1 γ 2 k , C α,µ := λ 2 /2 + 2C α KE[|U | 2 ] with K > 0.
Proof. With the notations of Section 1.2, we define for all n ≥ 1, ∆M

n := h(θ n-1 ) -H(θ n-1 , U n ) = E[ H(θ n-1 , U n )| F n-1 ] -H(θ n , U n ). Recalling that (U n ) n≥1 is
:= σ(θ 0 , U 1 , • • • , U n , ); n ≥ 1).
From the dynamic (1.4), we now write for all n ≥ 0,

z n+1 := θ n+1 -θ * = θ n -θ * -γ n+1 {h(θ n ) -∆M n+1 } = θ n -θ * -γ n+1 1 0 dλDh(θ * + λ(θ n -θ * ))(θ n -θ * ) + γ n+1 ∆M n+1 ,
where we used that h(θ * ) = 0 for the last equality. Setting J n :=

1 0 dλDh(θ * + λ(θ n -θ * )), we obtain z n+1 = (I -γ n+1 J n )z n + γ n+1 ∆M n+1 which yields E θ0 [|z n+1 | 2 ] = E θ0 [|I -γ n+1 J n | 2 |z n | 2 ] + 2γ n+1 E θ0 [(I -γ n+1 J n )∆M n+1 ] + γ 2 n+1 E θ0 [|∆M n+1 | 2 ] = E θ0 [|I -γ n+1 J n | 2 |z n | 2 ] + γ 2 n+1 E θ0 [|∆M n+1 | 2 ].
From assumption (HLS) α , we deduce that

∀(θ, u) ∈ R d × R q , |h(θ)-H(θ, u)| 2 ≤ 2C 2 α L 1-α (θ)(E[|U | 2 ]+ |u| 2
) which combined with the independence of θ n and U n+1 clearly implies

E θ0 [|h(θ n ) -H(θ n , U n+1 )| 2 ] ≤ 4C 2 α E[|U | 2 ]E θ0 [L 1-α (θ n )].
Now, let us notice that L has sub-quadratic growth so that there exists a constant K > 0 such that

E θ0 |∆M n+1 | 2 = E θ0 |h(θ n ) -H(θ n , U n+1 )| 2 ≤ 4C 2 α E[|U | 2 ]E θ0 L 1-α (θ n ) ≤ 4KC 2 α E[|U | 2 ](1 + E θ0 [|z n | 2 ]),
which provides the following bound

E θ0 [|z n+1 | 2 ] ≤ (1 -λγ n+1 ) 2 E θ0 [|z n | 2 ] + 4KC 2 α E[|U | 2 ]γ 2 n+1 E θ0 [|z n | 2 ] ≤ 1 -2λγ n+1 + 2C α,µ γ 2 n+1 E θ0 [|z n | 2 ] + 2C α,µ γ 2 n+1 .
Temporarily setting Πn = n-1 p=0 (1 -2λγ p+1 + 2C α,µ γ 2 p+1 ), a straightforward induction argument provides γ 2 k+1 e -2λ(Γ1,n-Γ 1,k+1 )+2Cα,µ(Γ2,n-Γ 2,k+1 )

where we used the elementary inequality, 1 + x ≤ exp(x), x ∈ R. This completes the proof.

|K k,p (f )(z) -K k,p (f )(z ′ )| ≤ k + 1 p + 1 |z 1 -z ′ 1 | + 1 p + 1 p j=k+1 Π 1,j Π 1,k 1 2 |z 2 -z ′ 2 |
where Π 1,p = p-1 k=0 (1 -2λγ k+1 + C H,µ γ 2 k+1 ). Proof. Let (z, z ′ ) ∈ (R d × R d ) 2 . We denote by z k,z p,1 = θk,z p+1 and z k,z p,2 = θ k,z p the values at step p of the two components of the stochastic approximation algorithm (z n ) n≥0 starting at point z at step k. Using (1.8) and a straightforward induction, one easily derives θk,z p+1 =

k + 1 p + 1 z 1 + 1 p + 1 p j=k+1 θ k,z j ,
so that taking conditional expectation in the previous equality and using Proposition 4.2,we obtain

|K k,p (f )(z) -K k,p (f )(z ′ )| = |E[f ( θk,z p+1 )] -E[f ( θk,z ′ p+1 )]| ≤ E[| θk,z p+1 -θk,z ′ p+1 |] ≤ k + 1 p + 1 |z 1 -z ′ 1 | + 1 p + 1 p j=k+1 E[|θ k,z j -θ k,z ′ j |] ≤ k + 1 p + 1 |z 1 -z ′ 1 | + 1 p + 1 p j=k+1 Π 1,j Π 1,k 1 2 |z 2 -z ′ 2 |
Let k ∈ {0, • • • , N -1} and f be a real-valued 1-Lipschitz function defined on R d . Using that the law of the innovations of the scheme satisfies (GC(β)), for all λ ≥ 0, one has

E [ exp(λK k,N -1 f (z k ))| z k-1 = z] = E exp λK k,N -1 f ( k k + 1 θk + 1 k + 1 θ k , θ k ) ( θk , θ k-1 ) = (z 1 , z 2 ) ≤ exp(λK k-1,N -1 (f )(z)) exp(λ 2 β 4 [g] 2 1 )
where g : u → K k,N -1 (f ) k k+1 z 1 + 1 k+1 z 2 -γ k k+1 H(z 2 , u), z 2γ k H(z 2 , u) . Combining Proposition 4.5 and (HLS) α , one easily obtains

[g] 1 ≤ C α L 1-α 2 (z 2 )γ k   1 N + 1 N N -1 j=k+1 Π 1,j Π 1,k 1 2
  so we deduce that

E [ exp(λK k,N -1 f (z k ))| z k-1 ] ≤ exp(λK k-1,N -1 (f )(z k-1 )) exp λ 2 β 4 C 2 α L 1-α (z k-1 )γ 2 k,N
where we introduced the notation γk,N :

= γ k N 1 + N -1 j=k+1 (Π 1,j /Π 1,k ) 1 2
. Hence, taking expectation in the previous inequality and using the Hölder inequality with conjugate exponents (p k , q k ), one clearly gets

E θ0 [exp(λK k,N -1 (f )(z k ))] ≤ E θ0 [exp(λp k K k-1,N -1 (f )(z k-1 ))] 1 p k E θ0 exp λ 2 β 4 C 2 α q k L 1-α (θ k-1 )γ 2 k,N 1 q k
Similarly to the proof of Proposition 4.3, we set p k = 1 + 1 (k+1) log 2 (k+4) , q k = (1 + 1 (k+1) log 2 (k+4) )(k + 1) log 2 (k + 4) ≤ 2(k + 1) log 2 (k + 4) and use Corollary 4.1 to obtain for α ∈ ( 1 2 , 1]

E θ0 exp λ 2 β 4 C 2 α q k L 1-α (θ k-1 )γ 2 k,N 1 q k ≤ exp K 4.1 2 1-α 2α-1 βC 2 α 4 ∨ βC 2 α 4 α 2α-1 (γ 2 k,N λ 2 ∨ γ 2α 2α-1 k,N q 1-α 2α-1 k λ 2α 2α-1
) .

An elementary induction argument allows to conclude Proof. Let X and Y be independent random vectors with laws µ and e ⊗d σ respectively. Then (X, X + Y ) is a coupling of µ and µ σ , and

E
W 1 (µ, µ σ ) ≤ E[|Y |] ≤ E[|Y | 2 ] 1/2 ≤ √ 2dσ.
We therefore have the bound

W 1 (µ n , µ) ≤ W 1 (µ n , µ σ n ) + W 1 (µ σ n , µ σ ) + W 1 (µ σ , µ) ≤ W 1 (µ σ n , µ σ ) + √ 8dσ, (A.3)
so what is left is to bound E[W 1 (µ σ n , µ σ )] and to optimize in σ. The density of µ σ n with respect to the Lebesgue measure is given by g 1,σ,n (x) := 1 n e ⊗d σ (xx i ), and the density of µ σ is g 2,σ (x) := E µ (e ⊗d σ (x -X)). By the Kantorovitch-Rubinstein duality formula, we have This can be proved by using Jensen's inequality with the finite measure Taking σ = n -1/(d+2) , we get the upper bound we were aiming for.

  Proposition 3.2. (Control of the Lipschitz modulus of iterative kernels) Denote the Lipschitz modulus of b and σ appearing in the diffusion process (SDE b,σ ) by [b] 1 and [σ] 1 , respectively. Denote by P k and P k,p = P k • • • • • P p-1 , k, p ∈ {0, • • • , N -1}, k ≤ p the (Feller) transition kernel and the iterative kernels of the Markov chain X ∆ defined by the scheme (1.2), respectively. Then for all real-valued Lipschitz function f and for all k, p ∈ {0, • • • , N -1}, k ≤ p the functions P k (f ) are Lipschitz-continuous and one has

  Proposition 4.2. (Control of the Lipschitz modulus of iterative kernels) Denote by P k and P k,p = P k •• • ••P p-1 , k, p ∈ {0, • • • , N -1}, k ≤ p the (Feller) transition kernel and the iterative kernels of the Markov chain θ defined by the scheme (1.4). Then for all Lipschitz function f and for all k, p ∈ {0, • • • , N -1}, k ≤ p the functions P k (f ) are Lipschitz-continuous and one has

E≤

  θ0 [|z n | 2 ] ≤ Πn |θ 0θ * | 2 + 2C αe -2λΓ1,n+2Cα,µΓ2,n |θ 0θ * | 2 + 2C α,µ n-1 k=0

4. 2 .

 2 Proof of Theorem 2.4 Proposition 4.5. (Control of the Lipschitz modulus of iterative kernels) Denote by K k and Kk,p = K k • • • • • K p-1 , k, p ∈ {0, • • • , N -1}, k ≤ p the (Feller) transition kernel and the iterative kernels of the Markov chain z = ( θ, θ) defined by the scheme (1.4), (1.8). Let f : R d → R be a 1-Lipschitz function. Then for all k, p ∈ {0, • • • , N -1}, k ≤ p the functions K k,p (f ) : z → E[ f ( θp+1 ) z k = z] are Lipschitz-continuous. In particular, for all (z, z ′ ) ∈ (R d × R d ) 2 , one has

≤N

  θ0 exp(λf ( θN )) = E θ0 [exp(λK N -1,N -1 (f )(z N -1 ))] ≤ exp(λE θ0 [f ( θN ]) exp ϕ α (γ, H, θ 0 )( Cγ N λ 2 ∨Cγ,α and where we again introduced, for sake of clarity, the constant ϕ α (γ, H, θ 0 ) := K 4.1 2 log 2 (k+4) . For α = 1 2 , similarly to the proof of Proposition 4.3 (actually use again Lemma 4.1), we derive for all λ ∈ [0, λ 4.1 /s exp Ψ(N, γ, θ 0 )γ 2 k,N λ 2 + ( /λ 4.1 )with sN := max 1≤k≤N -1 (k + 1) log 2 (k + 4)γ 2 k,N , Ψ(N, γ, θ 0 ) := L Π 2,N (1/2) E[|U | 2] and an elementary induction argument clearly yields∀λ ∈ [0, λ 4.1 /ŝ N ), E θ0 [exp(λf (θ N ))] ≤ exp (λE θ0 [f (θ N )]) exp 2ϕ 1/2 (γ, H, θ 0 ) Cγ N (λ/λ 4.1 ) 2 1 -(λŝ N /λ 4.1 ) with ŝN := s1/2 N exp( N -1 k=0 1 (k+1) log 2 (k+4)) and ϕ 1/2 (γ, H, θ 0 ) := exp( N -1 k=0 1 (k+1) log 2 (k+4) )(λ 2 4.1 Ψ(N, γ, θ 0 ) +

W 1

 1 (µ σ n , µ σ ) = sup f :[f ]1≤1 f (x)g 1,σ,n (x)dxf (x)g 2,σ (x)dx ≤ |x||g 1,σ,n (x)g 2,σ (x)|dxTo bound this quantity, we shall use the following Carlson-type inequality: for any nonnegative measurable function f on R d , we havef (x)dx ≤ C d (1 + |x| d+1 )f (x) 2 dx, C d := R d 1 1 + |x| d+1 dx.

  a sequence of i.i.d. random variables we have that (∆M n ) n≥1 is a sequence of martingale increments w.r.t. the natural filtration F := (F n

  1 1+|x| d+1 dx. Using this inequality, we get the boundW 1 (µ σ n , µ σ ) ≤ C d (1 + |x| d+1 )|x| 2 |g 1,σ,n (x)g 2,σ (x)| 2 dx ≤ C d (1 + 2|x| d+3 )|g 1,σ,n (x)g 2,σ (x)| 2 dx.Note that e ⊗d σ (x) 2 = 2 -2d σ -d e ⊗d σ/2 (x), so that we get d+3 |y| d+3 µ(dy) + 2 d+3 |u| d+3 e ⊗d σ/2 (u)du≤ C d 2 d σ d/2 √ n 1 + 2 d+3 |y| d+3 µ(dy) + σ d+3 |u| d+3 e ⊗d 1 (u)du ≤ C d 2 d σ d/2 √ n 1 + 2 d+3 |y| d+3 µ(dy) + 2 d+3 σ d+3 d(d + 3)!In the end, assuming σ ≤ 1, we obtain

	Therefore, 1 + 2 E[W 1 (µ, µ σ )] ≤ E[W 1 (µ σ n , µ σ )] ≤ C d E (1 + 2|x| d+3 )| ≤ C d √ n n , µ σ )] ≤ C d 2 d σ d/2 √ n (1 + 2|x| d+3 ) e ⊗d 1 n e ⊗d σ (x -X i ) -E µ (e ⊗d σ (x -X))| 2 dx σ/2 (x -y)µ(dy)dx ≤ C d 2 d σ d/2 √ n (1 + 2|u + y| d+3 )e ⊗d σ/2 (u)duµ(dy) ≤ C d 2 d σ d/2 √ n (1 + 2 d+3 (|u| d+3 + |y| d+3 ))e ⊗d σ/2 (u)duµ(dy) (1 + 2|x| E[W 1 (µ σ ≤ C d 2 d σ d/2 √ n √ 8dσ + C d 2 d σ d/2 √ n 1 + 2

d+3

)Var µ (e ⊗d σ (x -X))dx

≤ C d √ n (1 + 2|x| d+3 )E[e ⊗d σ (x -X) 2 ]dx. d+3 |y| d+3 µ(dy) + 2 d+3 σ d+3 d(d + 3)! ≤ C(d, µ)(σ + σ -d/2 √ n )

LPMA, Université Pierre et Marie Curie, 4 Place Jussieu, 75005 Paris Cedex, max.fathi@etu.upmc.fr

LPMA, Université Denis Diderot, 175 Rue du Chevaleret 75013 Paris, frikha@math.univ-paris-diderot.fr

Appendix A. Technical results

A.1. Proof of Proposition 1.3

Let e σ := 1 2σ exp(-|x|/σ) be the density of the exponential distribution with variance 2σ 2 on R. If µ is a probability measure on R d , we define µ σ as the convolution of µ with e ⊗d σ , that is

Lemma A.1. If µ is a probability measure on R d with finite first moment, then W 1 (µ, µ σ ) ≤ √ 2dσ.