N Frikha
email: frikha@math.univ-paris-diderot.fr

MULTI-LEVEL STOCHASTIC APPROXIMATION ALGORITHMS

Keywords: 1991 Mathematics Subject Classification. 60F05, 62K12, 65C05, 60H35 Multi-level Monte Carlo methods, stochastic approximation, Ruppert&Polyak averaging principle, Euler scheme

published or not. The documents may come

Introduction

In this paper we propose and analyze a multi-level paradigm for stochastic optimization problem by means of stochastic approximation schemes. The multi-level Monte Carlo method introduced by Heinrich [START_REF] Heinrich | Multilevel Monte Carlo methods[END_REF] and popularized in numerical probability by [START_REF] Kebaier | Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing[END_REF] and [START_REF] Giles | Multilevel Monte Carlo path simulation[END_REF] allows to significantly increase the computational efficiency of the expectation of an R-valued non-simulatable random variable Y that can only be strongly approximated by a sequence (Y n ) n≥1 of easily simulatable random variables (all defined on the same probability space) as the bias parameter n goes to infinity with a weak error or bias E[Y ] -E[Y n ] of order n -α , α > 0. Let us be more specific. In this context, the standard Monte Carlo method uses the statistical estimator M -1 × M j=1 Y n,j where the (Y n,j ) j∈[[1,M]] are M independent copies of Y n . Given the order of the weak error, a natural question is to find the optimal choice of the sample size M to achieve a global error. If the weak error is of order n -α then for a total error of order n -α (α ∈ [1/2, 1]), the minimal computation necessary for the standard Monte Carlo algorithm is obtained for M = n 2α , see [START_REF] Duffie | Efficient monte carlo simulation of security prices[END_REF]. So, if the computational cost required to simulate one sample of U n is of order n then the optimal computational cost of the Monte Carlo method is C MC = C × n 2α+1 , for a positive constant C > 0.

In order to reduce the complexity of the computation, the principle of the multi-level Monte Carlo method introduced by Giles [START_REF] Giles | Multilevel Monte Carlo path simulation[END_REF] as a generalization of Kebaier's approach [START_REF] Kebaier | Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing[END_REF] consists in using the telescopic sum

E[Y m L ] = E[Y 1 ] +
where m ∈ N * \{1} satisfies m L = n. For each level ℓ ∈ {1, • • • , L} the numerical computation of E[Y m ℓ -Y m ℓ-1 ] is achieved by the standard Monte Carlo method with N ℓ independent samples of (Y m ℓ-1 , Y m ℓ ). An important point is that the random sample Y m ℓ and Y m ℓ-1 are perfectly correlated. Then the expectation E[Y n ] is approximated by the following multi-level estimator

1 N 0 N0 j=1 Y 1,j + L ℓ=1 1 N ℓ N ℓ j=1 Y m ℓ ,j -Y m ℓ-1 ,j ,
where for each level ℓ, (Y m ℓ ,j ) j∈[[1,N ℓ ]] is a sequence of i.i.d. random variables with the same law as Y m ℓ .

Based on an analysis of the variance, Giles [START_REF] Giles | Multilevel Monte Carlo path simulation[END_REF] proposed an optimal choice for the sequence (N ℓ ) 1≤ℓ≤L which minimizes the total complexity of the algorithm. More recently, Ben Alaya and Kebaier [START_REF] Ben Alaya | Central limit theorem for the multilevel monte carlo euler method and applications to asian options[END_REF] proposed a different analysis to obtain the optimal choice of the parameters relying on a Lindeberg Feller central limit theorem (CLT) for the multi-level Monte Carlo algorithm. To obtain a global error of order n -α , both approaches allow to achieve a complexity of order n 2α (log n) 2 if the L 2 (P) strong approximation rate E|U n -U | 2 ] of U by U n is of order 1/n. Hence, the multi-level Monte Carlo method is significantly more effective than the crude Monte Carlo and the statistical Romberg methods. Originally introduced for the computation of expectations involving stochastic differential equation (SDE), it has been widely applied to various problems of numerical probability, see Giles [START_REF] Giles | Improved multilevel Monte Carlo convergence using the Milstein scheme[END_REF], Dereich [START_REF] Dereich | Multilevel Monte Carlo algorithms for Lévy-driven SDEs with Gaussian correction[END_REF], Giles, Higham and Mao [START_REF] Giles | Analysing multi-level Monte Carlo for options with non-globally Lipschitz payoff[END_REF] among others. We refer the interested reader to the webpage: http://people.maths.ox.ac.uk/gilesm/mlmc_community.html.

In the present paper, we are interested in broadening the scope of the multi-level Monte Carlo method to the framework of stochastic approximation (SA) algorithm. Introduced by Robbins and Monro [START_REF] Robbins | A stochastic approximation method[END_REF], these recursive simulation based algorithms appear as effective and widely used procedures to solve inverse problems. To be more specific, their aim is to find 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 from both a theoretical and applied point of view 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. In the general Robbins-Monro procedure, the function h writes h(θ) := E[H(θ, U )] where H : R d × R q → R d and U is an R q -valued random vector. To estimate the zero of h, they proposed the algorithm

θ p+1 = θ p -γ p+1 H(θ p , U p+1 ), p ≥ 0 (1.1)
where (U p ) p≥1 is an i.i.d. sequence of copies of U defined on a probability space (Ω, F , P), θ 0 is independent of the innovation of the algorithm with E|θ 0 | 2 < +∞ and γ = (γ p ) p≥1 is a sequence of non-negative deterministic and decreasing steps satisfying the assumption p≥1 γ p = +∞, and

p≥1 γ 2 p < +∞. (1.2)
When the function h is the gradient of a convex potential, the recursive procedure (1.1) is a stochastic gradient algorithm. Indeed, replacing H(θ p , U p+1 ) by h(θ p ) in (1.1) leads to the usual deterministic descent gradient procedure. When h(θ) = k(θ)ℓ, θ ∈ R, where k is a monotone function, say increasing, which writes k(θ) = E[K(θ, U )], K : R × R q → R being a Borel function and ℓ a given desired level, then setting H = Kℓ, the recursive procedure (1.1) aims to compute the value θ such that k( θ) = ℓ.

As in the case of the Monte Carlo method described above, the random vector U is not directly simulatable (at a reasonable cost) but can only be approximated by another sequence of easily simulatable random vectors ((U n ) p ) p≥1 , which strongly approximates U as n → +∞ with a standard weak discretization error (or bias) E[f (U )] -E[f (U n )] of order n -α for a specific class of functions f ∈ C. The computational cost required to simulate one sample of U n is of order n that is Cost(U n ) = K × n for some positive constant K. One standard situation corresponds to the case of a discretization of an SDE by means of an Euler-Maruyama scheme with n time steps. Some typical applications are the computations of the implied volatility or the implied correlation which both boil down to finding the zero of a function which writes as an expectation. Computing the Value-at-Risk and the Conditional Value-at-Risk of a financial portfolio when the dynamics of the underlying assets are given by an SDE also appears as an inverse problem for which a SA scheme may be devised, see e.g. [START_REF] Bardou | Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling[END_REF][START_REF] Bardou | Recursive computation of value-at-risk and conditional value-at-risk using MC and QMC[END_REF]. The risk minimization of a financial portfolio by means of SA has been investigated in [START_REF] Bardou | CVaR hedging using quantization based stochastic approximation algorithm[END_REF][START_REF] Frikha | Shortfall Risk Minimization in Discrete Time Financial Market Models[END_REF]. For more applications and a complete overview in the theory of stochastic approximation, the reader may refer to [START_REF] Duflo | Algorithmes stochastiques[END_REF], [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF] and [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF].

The important point here is that the function h is generally neither known nor computable (at least at reasonable cost) and since the random variable U cannot be simulated, estimating θ * using the recursive scheme (1.1) is not possible. Therefore, two steps are needed to compute θ * :

-the first step consists in approximating the zero θ * of h by the zero θ * ,n of h n defined by h n (θ

) := E[H(θ, U n )],
θ ∈ R d . It induces an implicit weak error which writes

E D (n) := θ * -θ * ,n .
Let us note that θ * ,n appears as a proxy of θ * and one would naturally expect that θ * ,n → θ * as the bias parameter n tends to infinity. -the second step consists in approximating θ * ,n by M ∈ N * steps of the following SA scheme

θ n p+1 = θ n p -γ p+1 H(θ n p , (U n ) p+1 ), p ∈ [[0, M -1]], (1.3)
where ((U n ) p ) p∈[[1,M]] is an i.i.d. sequence of random variables with the same law as U n , θ n 0 is independent of the innovation of the algorithm with sup n≥1 E[|θ n 0 | 2 ] < +∞ and γ = (γ p ) p≥1 is a sequence of non-negative deterministic and decreasing steps satisfying (1.2). This induces a statistical error which writes E S (n, M, γ) := θ * ,nθ n M .

The global error between θ * , the quantity to estimate, and its implementable approximation θ n M can be decomposed as follows:

E glob (n, M, γ) = θ * -θ * ,n + θ * ,n -θ n M := E D (n) + E S (n, M, γ).
The first step of our analysis consists in investigating the behavior of the implicit weak error E D (n). Under mild assumptions on the functions h and h n , namely the local uniform convergence of (h n ) n≥1 towards h and a mean reverting assumption of h and h n , we prove that lim n E D (n) = 0. We next show that under additional assumption, namely the local uniform convergence of (Dh n ) n≥1 towards Dh and the non-singularity of Dh(θ * ), the rate of convergence of the standard weak error h n (θ)h(θ), for a fixed θ ∈ R d , transfers to the implicit weak error E D (n) = θ *θ * ,n .

Regarding the statistical error E S (n, M, γ) := θ * ,nθ n M , it is well-known that under standard assumptions, i.e. a mean reverting assumption on h n and a growth control of the L 2 (P)-norm of the noise of the algorithm, the Robbins-Monro theorem guarantees that lim M E S (n, M, γ) = 0 for each fixed n ∈ N * , see Theorem 2.3 below. Moreover, under mild technical conditions, a CLT holds at rate γ -1/2 (M ), that is, for each fixed n ∈ N * , γ -1/2 (M )E S (n, M, γ) converges in distribution to a normally distributed random variable with mean zero and finite covariance matrix, see Theorem 2.4 below. The reader may also refer to [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF][START_REF] Fathi | Transport-entropy inequalities and deviation estimates for stochastic approximation schemes[END_REF] for some recent developments on non-asymptotic deviation bounds for the statistical error. In particular if we set γ(p) = γ 0 /p, γ 0 > 0, p ≥ 1, the weak convergence rate is √ M provided that 2Re(λ min )γ 0 > 1 where λ min denotes the eigenvalue of Dh(θ * ) with the smallest real part. However, this local condition on the Jacobian matrix of h at the equilibrium is difficult to handle in practical situation.

N. FRIKHA

To circumvent such a difficulty, it is fairly well-known that the key idea is to carefully smooth the trajectories of a converging SA algorithm by averaging according to the Ruppert & Polyak averaging principle, see e.g. [START_REF] Ruppert | Stochastic approximation[END_REF][START_REF] Polyak | Acceleration of stochastic approximation by averaging[END_REF]. It consists in devising the original SA algorithm (1.3) with a slow decreasing step and to simultaneously compute the empirical mean ( θn p ) p≥1 (which a.s. converges to θ * ,n ) of the sequence (θ n p ) p≥0 by setting

θn p = θ n 0 + θ n 1 + • • • + θ n p p + 1 = θn p-1 - 1 p + 1 θn p-1 -θ n p .
(1.4)

The statistical error now writes E S (n, M, γ) := θ * ,nθn M and under mild assumptions a CLT holds at rate √ M without any stringent condition on γ 0 . Given the order of the implicit weak error and a step sequence γ satisfying (1.2) a natural question is to find the optimal balance between the value of n and the number M of steps in (1.3) in order to achieve a given global error. This problem was originally investigated in [START_REF] Duffie | Efficient monte carlo simulation of security prices[END_REF] for the standard Monte Carlo method. The error between θ * and the approximation

θ n M writes θ n M -θ * = θ n M -θ * ,n + θ * ,n -θ * suggesting to select M = γ -1 (1/n 2α
), where γ -1 is the inverse function of γ, when the weak error is of order n -α . However, due to the non-linearity of the SA algorithm (1.3), the methodology developed in [START_REF] Duffie | Efficient monte carlo simulation of security prices[END_REF] does not apply in our context. The key tool to tackle this question consists in linearizing the dynamic of (θ n p ) p∈[[1,M]] around its target θ * ,n , quantifying the contribution of the non linearities in the space variable θ n p and the innovations and finally exploiting stability arguments from SA schemes. Optimizing with respect to the usual choice of the step sequence, the minimal computational cost (to achieve an error of order n -α ) given by C SA = K ×n×γ -1 (1/n 2α ) is reached by setting γ(p) = γ 0 /p, p ≥ 1, provided that the constant γ 0 satisfies a stringent condition involving h n , leading to a complexity of order n 2α+1 . Considering the empirical mean sequence ( θn p ) p∈[[1,n 2α ]] instead of the crude SA estimate also allows to reach the optimal complexity for free without any condition on γ 0 .

To increase the computational efficiency for the estimation of θ * by means of SA algorithm, we investigate in a second part multi-level SA algorithms. The first one is a two-level method, also referred as the statistical Romberg SA method. It consists in approximating the unique zero θ * of h by Θ sr

n = θ n β M1 + θ n M2 -θ n β M2 , β ∈ (0, 1). The couple (θ n M2 , θ n β M2
) is computed using M 2 independent copies of (U n , U 2n ). Moreover the random samples used to obtain θ n β M1 are independent of those used for the computation of (θ n M2 , θ n β M2 ). For an implicit weak error of order n -α , we prove a CLT for the sequence (Θ sr n ) n≥1 through which we are able to optimally set M 1 , M 2 and β with respect to n and the step sequence γ. The intuitive idea is that when n is large, (θ n p ) p∈[[0,M2]] and (θ n β p ) p∈[[0,M2]] are close to the SA scheme (θ p ) p∈[[0,M2]] devised with the innovation variables (U p ) p≥1 so that the correction term writes

θ n M2 -θ M2 -(θ n β M2 -θ M2
). Then we quantify the two main contributions in this decomposition, namely the one due to the non linearity in the space variables (θ n β p , θ n p , θ p ) p∈[[0,M2]] and the one due to the non linearity in the innovation variables (U n β ,p , U n,p , U p ) p≥1 . Under mild smoothness assumption on the function H, the weak rate of convergence is ruled by the non linearity in the innovation variables for which we use the weak convergence of the normalized error n ρ (U n -U ), ρ ∈ (0, 1/2]. The optimal choice of the step sequence is again γ p = γ 0 /p, p ≥ 1 and induces a complexity for the procedure given by C SA-SR = K × n 2α+1/(1+ρ) , provided that γ 0 satisfies again a condition involving h n which is difficult to handle in practice. devised with the same slow decreasing step sequence, this optimal complexity is reached for free by setting M 3 = n 2α , M 4 = n 2α-1/(1+ρ) without any condition on γ 0 .

Moreover, we generalize this approach to the case of multi-level SA method. In the spirit of [START_REF] Giles | Multilevel Monte Carlo path simulation[END_REF] for Monte Carlo path simulation, the multi-level SA scheme estimates θ * ,n by computing the quantity

Θ ml n = θ 1 M0 + L ℓ=1 θ m ℓ M ℓ -θ m ℓ-1 M ℓ
where for every ℓ, the couple (θ m ℓ M ℓ , θ m ℓ-1 M ℓ ) is obtained using M ℓ independent copies of (U m ℓ-1 , U m ℓ ). Here again to establish a CLT for this estimator (in the spirit of [START_REF] Ben Alaya | Central limit theorem for the multilevel monte carlo euler method and applications to asian options[END_REF] for the Monte Carlo path simulation), our analysis follows the lines of the methodology developed so far. The optimal computational cost to achieve an accuracy of order 1/n is reached by setting

M 0 = γ -1 (1/n 2 ), M ℓ = γ -1 (m ℓ log(m)/(n 2 log(n)(m- 1))), ℓ = 1, • • • , L in the case ρ = 1/2.
Once again the step sequence γ(p) = γ 0 /p, p ≥ 1, is optimal among the usual choices of step sequence and it induces a complexity for the procedure given by C SA-ML = K ×n 2 (log(n)) 2 . We thus recover the rates as in the multi-level Monte Carlo path simulation for SDE obtained in [START_REF] Giles | Multilevel Monte Carlo path simulation[END_REF] and [START_REF] Ben Alaya | Central limit theorem for the multilevel monte carlo euler method and applications to asian options[END_REF].

The paper is organized as follows. In the next section we state our main results and list the assumptions. Section 3 is devoted to the proofs. In Section 4 numerical results are presented to confirm the theoretical analysis. Finally, Section 5 is devoted to technical results which are useful throughout the paper.

Main results

In the present paper, we make no attempt to provide an exhaustive discussion related to convergence results of SA schemes. We refer the interested readers to [START_REF] Duflo | Algorithmes stochastiques[END_REF], [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF] and [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF] among others for developments and a more complete overview in SA theory. In the next section, we first recall some basic facts concerning stable convergence (following the notations of [START_REF] Jacod | Asymptotic error distributions for the Euler method for stochastic differential equations[END_REF]) and list classical results of SA theory.

Preliminaries

For a sequence of E-valued (E being a Polish space) random variables (X n ) n≥1 defined on a probability space (Ω, F , P), we say that (X n ) n≥1 converges in law stably to X defined on an extension ( Ω, F , P) of (Ω, F , P) and write X n stably =⇒ X, if for all bounded random variable U defined on (Ω, F , P) and for all h : E → R bounded continuous, one has

E[U h(X n )] → Ẽ[U h(X)], n → +∞.
This convergence is obviously stronger than convergence in law that we denote by "=⇒". Stable convergence was introduced in [START_REF] Rényi | On stable sequences of events[END_REF] and notably investigated in [START_REF] Aldous | On mixing and stability of limit theorems[END_REF]. The following lemma is a basic result on stable convergence that will be useful throughout the paper. We refer to [JP98], Lemma 2.1 for a proof. Here, E and F will denote two Polish spaces. We consider a sequence (X n ) n≥1 of E-valued random variable defined on (Ω, F ).

Lemma 2.1. Let (Y n ) n≥1 be a sequence of F -valued random variable defined on (Ω, F ) satisfying

Y n P -→ Y
where Y is defined on (Ω, F ). If X n stably =⇒ X where X is defined on an extension of (Ω, F ) then, we have

(X n , Y n ) stably =⇒ (X, Y ).
Let us note that this result remains valid when Y n = Y , for all n ≥ 1 We illustrate this notion by the Euler-Maruyama discretization scheme of a diffusion process X solution of an SDE. The following results will be useful in the sequel in order to illustrate multi-level SA methods. We first introduce some notations, namely for

x ∈ R q f (x) =      b 1 (x) σ 11 (x) • • • σ 1q ′ (x) b 2 (x) σ 21 (x) • • • σ 2q ′ (x) . . . . . . • • • . . . b q (x) σ q1 (x) • • • σ qq ′ (x)      and dY t = (dt dW 1 t • • • dW q ′ t )
T where b : R q → R q , σ : R q → R q × R q ′ . Here as below u T denotes the transpose of the vector u. The dynamic of X will be written in the compact form

∀t ∈ [0, T ], X t = x + t 0 f (X s )dY s
with its Euler-Maruyama scheme with time step ∆ = T /n

X n t = x + t 0 f (X n φn(s) )dY s .
We introduce the following smoothness assumption on the coefficients: (HS) The coefficients b, σ are uniformly Lipschitz continuous. (HD) The coefficients b, σ satisfy (HS) and are continuously differentiable.

The following result is due to [START_REF] Jacod | Asymptotic error distributions for the Euler method for stochastic differential equations[END_REF], Theorem 3.2 p.276 and Theorem 5.5, p.293.

Theorem 2.1. Assume that (HD) holds. Then, the process

V n := X n -X satisfies n T V n stably =⇒ V, as n → +∞
the process V being defined by V 0 = 0 and

dV i t = q ′ +1 j=1 q k=1 f ′ ij k (X t )   V k t dY j t - q ′ +1 ℓ=1 f kℓ (X t )dZ ℓj t   (2.5)
where f ′ ij k is the kth partial derivative of f ij and

∀(i, j) ∈ [[2, q ′ + 1]] × [[2, q ′ + 1]], Z ij t = 1 √ 2 1≤k,ℓ≤q t 0 σ ik (X s )σ jℓ (X s )dB kℓ s , ∀j ∈ [[1, q ′ + 1]], Z 1j = 0, ∀i ∈ [[1, q ′ + 1]], Z i1 = 0,
where B is a standard (q ′ ) 2 -dimensional Brownian motion defined on an extension ( Ω, F, ( Ft ) t≥0 , P) of (Ω, F , (F t ) t≥0 , P) and independent of W .

We will also use the following result which is due to [START_REF] Ben Alaya | Central limit theorem for the multilevel monte carlo euler method and applications to asian options[END_REF], Theorem 4.

Theorem 2.2. Let m ∈ N * \{1}. Assume that (HD) holds. Then, we have

m ℓ (m -1)T (X m ℓ -X m ℓ-1 ) stably =⇒ V, as ℓ → +∞.
We now turn our attention to SA. There are various theorems that guarantee the a.s. and/or L p convergence of SA algorithms. We provide below a general result in order to derive the a.s. convergence of such procedures. It is also known as Robbins-Monro Theorem and covers most situations (see the remark below).

Theorem 2.3 (Robbins-Monro Theorem). Let H : R d × R q → R d a Borel function and U a R q -valued random vector with law µ. Define

∀θ ∈ R d , h(θ) = E[H(θ, U )],
and denote by θ * the (unique) solution to h(θ) = 0. Suppose that h is a continuous function that satisfies the mean-reverting assumption ∀θ ∈ R d , θ = θ * , θθ * , h(θ) > 0.

(2.6) Let γ = (γ p ) p≥1 be a sequence of gain parameters satisfying (1.2). Suppose that

∀θ ∈ R d , E|H(θ, U )| 2 ≤ C(1 + |θ -θ * | 2 ) (2.7)
Let (U p ) p≥1 be an i.i.d. sequence of random vectors with common law µ and θ 0 a random vector independent of (U p ) p≥1 satisfying E|θ 0 | 2 < +∞. Then, the recursive procedure defined by

θ p+1 = θ p -γ p+1 H(θ p , U p+1 ), p ≥ 0 (2.8) satisfies θ p a.s.
-→ θ * , as p → +∞.

Let us point out that the Robbins-Monro theorem also covers the framework of stochastic gradient algorithm. Indeed, if the function h is the gradient of a convex potential L, namely h = ∇L where L ∈ C 1 (R d , R + ), that satisfies: ∇L is Lipschitz, |∇L| 2 ≤ C(1 + L) and lim |θ|→+∞ L(θ) = +∞ then, Argmin L is non-empty and according to the following standard lemma θ → 1 2 |θθ * | 2 is a Lyapunov function so that the sequence (θ n ) n≥1 defined by (2.8) converges a.s.

to θ * . Lemma 2.2. Let L ∈ C 1 (R d , R + ) be a convex function, then ∀θ, θ ′ ∈ R d , ∇L(θ) -∇L(θ ′ ), θ -θ ′ ≥ 0.
Moreover, if Argmin L is non-empty, then one has

∀θ ∈ R d \ Argmin L, ∀θ * ∈ Argmin L, ∇L(θ), θ -θ * > 0.
Now, we provide a result on the weak rate of convergence of SA algorithm. In standard situations, it is well-known that a stochastic algorithm (θ p ) p≥1 converges to its target at a rate γ -1/2 p . We also refer to [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF][START_REF] Fathi | Transport-entropy inequalities and deviation estimates for stochastic approximation schemes[END_REF] for some recent developments on non-asymptotic deviation bounds. More precisely, the sequence (γ -1/2 p (θ pθ * )) p≥1 converges in distribution to some normal distribution with a covariance matrix based on E[H(θ * , U )H(θ * , U ) T ] where U is the noise of the algorithm. The following result is due to [START_REF] Pelletier | Weak convergence rates for stochastic approximation with application to multiple targets and simulated annealing[END_REF] (see also [START_REF] Duflo | Algorithmes stochastiques[END_REF], p.161 Theorem 4.III.5) and has the advantage to be local, in the sense that a CLT holds on the set of convergence of the algorithm to an equilibrium which makes possible a straightforward application to multi-target algorithms.

Theorem 2.4. Let θ * ∈ {h = 0}. Suppose that h is twice continuously differentiable in a neighborhood of θ * and that Dh(θ * ) is a stable d × d matrix, i.e. all its eigenvalues have strictly positive real parts. Assume that the function H satisfies the following regularity and growth control property

θ → E H(θ, U )H(θ, U ) T is continuous on R d , ∃ε > 0 s.t. θ → E |H(θ, U )| 2+ε is locally bounded on R d .
Assume that the noise of the algorithm is not degenerated at the equilibrium, that is Γ(θ * ) := E H(θ * , U )H(θ * , U ) T is a positive definite deterministic matrix.

The step sequence of the procedure (2.8) is given by γ p = γ(p), p ≥ 1, where γ is a positive function defined on [0, +∞[ decreasing to zero. We assume that γ satisfies one of the following assumptions:

• γ varies regularly with exponent (-a), a ∈ [0, 1), that is, for any x > 0, lim t→+∞ γ(tx)/γ(t) = x -a . In this case, set ζ = 0. • for t ≥ 1, γ(t) = γ 0 /t and γ 0 satisfies 2Re(λ min )γ 0 > 1, where λ min denotes the eigenvalue of Dh(θ * ) with the lowest real part. In this case, set ζ = 1/(2γ 0 ).

N. FRIKHA

Then, on the event {θ p → θ * }, one has

γ(p) -1/2 (θ p -θ * ) =⇒ N (0, Σ * )
where

Σ * := ∞ 0 exp (-s(Dh(θ * ) -ζI d )) T Γ(θ * ) exp (-s(Dh(θ * ) -ζI d )) ds. Remark 2.1.
In SA theory it is also said that -Dh(θ * ) is a Hurwitz matrix, that is all its eigenvalue has strictly negative real part. The assumption on the step sequence (γ n ) n≥1 is quite general and includes polynomial step sequences. In practical situation, the above theorem is often applied to the usual gain γ p = γ(p) = γ 0 p -a , with 1/2 < a ≤ 1, which notably satisfies (1.2).

Hence we clearly see that the optimal weak rate of convergence is achieved by choosing γ p = γ 0 /p with 2Re(λ min )γ 0 > 1. However the main drawback with this choice is that the constraint on γ 0 is difficult to handle in practical implementation. Moreover it is well-known that in this case the asymptotic covariance matrix is not optimal, see e.g. [START_REF] Duflo | Algorithmes stochastiques[END_REF] or [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF] among others.

As mentioned in the introduction, a solution consists in devising the original SA algorithm (2.8) with a slow decreasing step γ = (γ p ) p≥1 , where γ varies regularly with exponent (-a), a ∈ (1/2, 1) and to simultaneously compute the empirical mean ( θp ) p≥1 of the sequence (θ p ) p≥0 by setting

θp = θ 0 + θ 1 + • • • + θ p p + 1 = θp-1 - 1 p + 1 θp-1 -θ p .
(2.9)

The following result states the weak rate of convergence for the sequence ( θp ) p≥1 . In particular, it shows that the optimal weak rate of convergence and the optimal asymptotic covariance matrix can be obtained without any condition on γ 0 . For a proof, the reader may refer to [START_REF] Duflo | Algorithmes stochastiques[END_REF], p.169.

Theorem 2.5. Let θ * ∈ {h = 0}. Suppose that h is twice continuously differentiable in a neighborhood of θ * and that Dh(θ * ) is a stable d×d matrix, i.e. all its eigenvalues have positive real parts. Assume that the function H satisfies the following regularity and growth control property

θ → E H(θ, U )H(θ, U ) T is continuous on R d , ∃b > 0 s.t. θ → E |H(θ, U )| 2+b is locally bounded on R d .
Assume that the noise of the algorithm is not degenerated at the equilibrium, that is Γ(θ * ) := E H(θ * , U )H(θ * , U ) T is a positive definite deterministic matrix.

The step sequence of the procedure (2.8) is given by γ p = γ(p), p ≥ 1, where γ varies regularly with exponent (-a), a ∈ (1/2, 1). Then, on the event {θ p → θ * }, one has

√ p θp -θ * =⇒ N 0, Dh(θ * ) -1 Γ(θ * )(Dh(θ * ) -1 ) T .

Main assumptions

We list here the required assumptions in our framework to derive our asymptotic results and make some remarks. (HWR1) There exists ρ ∈ (0, 1/2],

n ρ (U n -U ) stably =⇒ V, as n → +∞
where V is an R q -valued random variable eventually defined on an extension ( Ω, F , P) of (Ω, F , P). (HWR2) There exists ρ ∈ (0, 1/2],

m ℓρ (U m ℓ -U m ℓ-1 ) stably =⇒ V m as ℓ → +∞
where V m is an R q -valued random variable eventually defined on an extension ( Ω, F , P) of (Ω, F , P).

(HSR) There exists δ > 0, sup

n≥1 E |n ρ (U n -U )| 2+δ < +∞.
(HR) There exists b ∈ (0, 1],

sup n∈N * ,(θ,θ ′ )∈(R d ) 2 E[|H(θ, U n ) -H(θ ′ , U n )| 2 ] |θ -θ ′ | 2b < +∞. (HDH) For all θ ∈ R d , P(U / ∈ D H,θ ) = 0 with D H,θ := {x ∈ R q : x → H(θ, x) is differentiable at x}. (HLH) For all (θ, θ ′ , x) ∈ (R d ) 2 × R q , |H(θ, x) -H(θ ′ , x)| ≤ C(1 + |x| r )|θ -θ ′ |, for some C, r > 0.
(HI) There exists δ > 0 such that for all R > 0, we have sup

{θ:|θ|≤R, n∈N * } E[|H(θ, U n )| 2+δ ] < +∞. The sequence (θ → E[H(θ, U n )H(θ, U n ) T ]) n≥1 converges locally uniformly towards θ → E[H(θ, U )H(θ, U ) T ]. The function θ → E[H(θ, U )H(θ, U ) T ] is continuous and E[H(θ * , U )H(θ * , U ) T ] is a positive deterministic matrix. (HMR) There exists λ > 0 such that ∀n ≥ 1 ∀θ ∈ R d , θ -θ * ,n , h n (θ) ≥ λ|θ -θ * ,n | 2 .
We will denote λ m the lowest real part of the eigenvalues of Dh(θ * ). We will assume that the step sequence is given by γ p = γ(p), p ≥ 1, where γ is a positive function defined on [0, +∞[ decreasing to zero and satisfying one of the following assumptions: (HS1) γ varies regularly with exponent (-a), a ∈ [0, 1), that is, for any x > 0, lim t→+∞ γ(tx)/γ(t) = x -a . (HS2) for t ≥ 1, γ(t) = γ 0 /t and γ 0 satisfies 2λγ 0 > 1.

Remark 2.2. Assumption (HR) is trivially satisfied when θ → H(θ, x) is Hölder-continuous with modulus having polynomial growth in x. However, it is also satisfied when H is less regular. For instance, it holds for H(θ, x) = 1 {x≤θ} under the additional assumption that U n has a bounded density (uniformly in n).

Remark 2.3. Assumption (HMR) already appears in [START_REF] Duflo | Algorithmes stochastiques[END_REF] and [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF], see also [START_REF] Frikha | Concentration bounds for stochastic approximations[END_REF] and [START_REF] Fathi | Transport-entropy inequalities and deviation estimates for stochastic approximation schemes[END_REF] in another context. It allows to control the L 2 -norm E[|θ n pθ * ,n | 2 ] with respect to the step γ(p) uniformly in n, see Lemma 5.2 in Section 5. As discussed in [START_REF] Kushner | Stochastic approximation and recursive algorithms and applications[END_REF], Chapter 10, Section 5, if one considers the projected version of the algorithm (1.3) on a bounded convex set D (for instance an hyperrectangle Π d i=1 [a i , b i ]) containing θ * ,n , ∀n ≥ 1, as very often happens from a practical point of view, this assumption can be localized on D, that is it holds on D instead of R d . In this case, a sufficient condition is inf θ∈D,n∈N * λ min ((Dh n (θ) + Dh n (θ) T )/2) > 0, where λ min (A) denotes the lowest eigenvalue of the matrix A.

We also want to point out that if it is satisfied then one has λ m ≥ λ. Indeed, writing h n (θ) =

1 0 Dh n (tθ + (1 -t)θ * ,n )(θ -θ * ,n )dt, for all θ ∈ R d , we clearly have θ -θ * ,n , h n (θ) = 1 0 θ -θ * ,n , Dh n (tθ + (1 -t)θ * ,n ) + Dh n (tθ + (1 -t)θ * ,n ) T 2 (θ -θ * ,n ) dt ≥ λ|θ -θ * ,n | 2 .
Using the local uniform convergence of (Dh n ) n≥1 and the convergence of (θ * ,n ) n≥1 toward θ * , by passing to the limit n → +∞ in the above inequality, we obtain

∀θ ∈ K, 1 0 θ -θ * , Dh(tθ + (1 -t)θ * ) + Dh(tθ + (1 -t)θ * ) T 2 (θ -θ * ) dt ≥ λ|θ -θ * | 2
where K is a compact set such that θ * + u m ∈ K, u m being the eigenvector associated to the eigenvalue of Dh(θ * ) with the lowest real part. Hence, selecting θ = θ * + εu m in the previous inequality and passing to the limit ε → 0, we get λ m ≥ λ.

Remark 2.4. Assumptions (HWR1), (HWR2) and (HSR) allow to establish a CLT for the multi-level SA estimators presented in sections 2.5 and 2.6. They include the case of the value at time T of an SDE, namely U = X T approximated by its continuous Euler-Maruyama scheme U n = X n T with n steps. Under (HD) one has ρ = 1/2. Moreover, U may depend on the whole path of an SDE. For instance, one may have U = L T the local time at level 0 of a one-dimensional continuous and adapted diffusion process and the approximations may be given by

U n = [nt] i=1 f u n X i-1 n , √ n X i n -X i-1 n .
Then under some assumptions on the function f and the coefficients b, σ, the weak and strong rate of convergence is ρ = 1/4, see [START_REF] Jacod | Rates of convergence to the local time of a diffusion[END_REF] for more details. Let us note that we do not know what happens when ρ > 1/2 which includes the case of higher order schemes for discretization schemes of SDE.

On the implicit weak error

As already observed the approximation of θ * solution of h(θ) = E[H(θ, U )] = 0 is affected by two errors: the implicit discretization error and the statistical error. Our first results concern the convergence of θ * ,n toward θ * and its convergence rate as n → +∞.

Theorem 2.6. For all n ∈ N * , assume that h and h n satisfy the mean reverting assumption (2.6) of Theorem 2.3. Moreover, suppose that (h n ) n≥1 converges locally uniformly towards h. Then, one has

θ * ,n → θ * as n → +∞.
Moreover, suppose that h and h n , n ≥ 1, are continuously differentiable and that Dh(θ * ) is non-singular. Assume that (Dh n ) n≥1 converges locally uniformly to Dh. If there exists α ∈ R * such that

∀θ ∈ R d , lim n→+∞ n α (h n (θ) -h(θ)) = E(h, α, θ), then, one has lim n→+∞ n α (θ * ,n -θ * ) = -Dh -1 (θ * )E(h, α, θ * ).

On the optimal tradeoff between the implicit error and the statistical error

Given the order of the implicit weak error, a natural question is to find the optimal balance between the value of n in the approximation of U and the number M of steps in (1.3) for the computation of θ * ,n in order to achieve a given global error ε.

Theorem 2.7. Suppose that the assumptions of Theorem 2.6 are satisfied and that h satisfies the assumptions of Theorem 2.4. Assume that (HR), (HI) and (HMR) hold and that h n is twice continuously differentiable with Dh n Lipschitz continuous uniformly in n. If (HS1) or (HS2) is satisfied then one has

n α θ n γ -1 (1/n 2α ) -θ * =⇒ -Dh -1 (θ * )E(h, α, θ * ) + N (0, Σ * ) ,
where

Σ * := ∞ 0 exp (-s(Dh(θ * ) -ζI d )) T E[H(θ * , U )H(θ * , U ) T ] exp (-s(Dh(θ * ) -ζI d )) ds (2.10) with ζ = 0 if (HS1) holds and ζ = 1/2γ 0 if (HS2) holds.
Lemma 2.3. Let δ > 0. Under the assumptions of Theorem 2.7, one has

n α θ n δ γ -1 (1/n 2α ) -θ * ,n δ =⇒ N (0, Σ * ), n → +∞.
Proof of Theorem 2.7. We decompose the error as follows:

θ n γ -1 (1/n 2α ) -θ * = θ n γ -1 (1/n 2α ) -θ * ,n + θ * ,n -θ *
and analyze each term of the above sum. By Lemma 2.3, we have

n α θ n γ -1 (1/n 2α ) -θ * ,n =⇒ N (0, Σ * )
and using Theorem 2.6, we also obtain

n α (θ * ,n -θ * ) → -Dh -1 (θ * )E(h, α, θ * ).
The result of Theorem 2.7 could be construed as follows. For a total error of order 1/n α , it is necessary to achieve at least M = γ -1 (1/n 2α ) steps of the SA scheme defined by (1.3). Hence, in this case the complexity (or computational cost) of the algorithm is given by

C SA (γ) = C × n × γ -1 (1/n 2α ), (2.11)
where C is some positive constant. We now investigate the impact of the step sequence (γ n ) n≥1 on the complexity by considering the two following basic step sequences:

• if we choose γ(p) = γ 0 /p with 2λγ 0 > 1, then C SA = C × n 2α+1 . • if we choose γ(p) = γ 0 /p ρ , 1 2 < ρ < 1 then C SA = C × n 2α/ρ+1
. Hence we clearly see that the minimal complexity is achieved by choosing γ p = γ 0 /p with 2λγ 0 > 1. In this latter case, we see that the computational cost is similar to the one achieved by the classical Monte Carlo algorithm for the computation of E x [f (X T )]. However the main drawback with this choice of step sequence comes from the constraint on γ 0 . Next result shows that the optimal complexity can be reached for free through the smoothing of the procedure (1.3) according to the Ruppert & Polyak averaging principle.

Theorem 2.8. Suppose that the assumptions of Theorem 2.6 are satisfied and that h satisfies the assumptions of Theorem 2.4. Assume that (HR), (HI) and (HMR) hold and that h n is twice continuously differentiable with Dh n Lipschitz continuous uniformly in n. Define the empirical mean sequence ( θn p ) p≥1 of the sequence (θ n p ) p≥1 by setting

θn p = θ 0 + θ n 1 + • • • + θ n p p + 1 = θn p-1 - 1 p + 1 θn p-1 -θ n p
, where the step sequence γ = (γ p ) p≥1 satisfies (HS1) with a ∈ (1/2, 1). Then, one has

n α θn n 2α -θ * =⇒ -Dh -1 (θ * )E(h, α, θ * ) + N 0, Dh(θ * ) -1 E[H(θ * , U )H(θ * , U ) T ](Dh(θ * ) -1 ) T , Lemma 2.4. Let δ > 0.
Under the assumptions of Theorem 2.8, one has

n α θn δ n 2α -θ * ,n δ =⇒ N 0, Dh(θ * ) -1 E[H(θ * , U )H(θ * , U ) T ](Dh(θ * ) -1 ) T , n → +∞.
Proof of Theorem 2.8. Similarly to the proof of Theorem 2.7 we decompose the error as follows:

θn n 2α -θ * = θn n 2α -θ * ,n + θ * ,n -θ * .
Applying successively Theorem 2.6 and Lemma 2.4, we obtain

n α θn n 2α -θ * =⇒ -Dh -1 (θ * )E(h, α, θ * ) + N (0, Σ * ) .
The result of Theorem 2.8 shows that for a total error of order 1/n α , it is necessary to achieve at least M = n 2α steps of the SA scheme defined by (1.3) with step sequence satisfying (HS1) and to simultaneously compute its empirical mean, which represents a negligible part of the total cost. As a consequence, we see that in this case the complexity of the algorithm is given by

C SA-RP (γ) = C × n 2α+1 .
Therefore, the optimal complexity is reached for free without any condition on γ 0 thanks to the Ruppert & Polyak averaging principle.

The statistical Romberg stochastic approximation method

In this section we present a two-level SA scheme that will be also referred as the statistical Romberg SA method which allows to minimize the complexity of the SA algorithm (

θ n p ) p∈[[0,γ -1 (1/n 2α )]] for the numerical computation of θ * solution to h(θ) = E[H(θ, U )] = 0. It is clearly apparent that θ * ,n = θ * ,n β + θ * ,n -θ * ,n β , β ∈ (0, 1).
The statistical Romberg SA scheme independently estimates each of the solutions appearing on the righthand side in a way that minimizes the computational complexity. Let θ n β M1 be an estimator of θ * ,n β using M 1 independent samples of U n β and θ n M2θ n β M2 be an estimator of θ * ,nθ * ,n β using M 2 independent copies of (U n β , U n ). Using the above decomposition, we estimate θ * by the quantity

Θ sr n = θ n β M1 + θ n M2 -θ n β M2 .
It is important to point out here that the couple (θ n M2 , θ n β M2 ) is computed using i.i.d. copies of (U n β , U n ), the random variables U n β and U n being perfectly correlated. Moreover, the random variables used to obtain θ n β M1 are independent to those used for the computation of (θ n M2 , θ n β M2 ). We also establish a central limit theorem for the statistical Romberg based empirical sequence according to the Ruppert and(θ n p , θ n β p ) p∈[[0,M4]] devised with the same slow decreasing step, that is a step sequence (γ(p)) p≥1 where γ varies regularly with exponent (-a), a ∈ (1/2, 1). Theorem 2.9. Suppose that h and h n satisfy the assumptions of Theorem 2.6 with α ∈ (ρ ∨ 2ρβ, 1] and that h satisfies the assumptions of Theorem 2.4. Assume that (HWR1), (HSR), (HD), (HMR), (HDH) and (HLH) hold and that h n are twice continuously differentiable in a neighborhood of θ * , with Dh n Lipschitzcontinuous uniformly in n satisfying:

∀θ ∈ R d , n ρ Dh n (θ) -Dh(θ) → 0, as n → +∞. Suppose that Ẽ (D x H(θ * , U )V )(D x H(θ * , U )V )
T is a positive definite matrix. Assume that the step sequence is given by γ p = γ(p), p ≥ 1, where γ is a positive function defined on [0, +∞[ decreasing to zero, satisfying one of the following assumptions:

• γ varies regularly with exponent (-a), a ∈ (1/2, 1), that is, for any x > 0, lim t→+∞ γ(tx)/γ(t) = x -a .

• for t ≥ 1, γ(t) = γ 0 /t and γ 0 satisfies λγ 0 > α/(2α -2ρβ). Then, for

M 1 = γ -1 (1/n 2α ) and M 2 = γ -1 (1/(n 2α-2ρβ )), one has n α (Θ sr n -θ * ) =⇒ Dh -1 (θ * )E(h, α, θ * ) + N (0, Σ * ), n → +∞ with Σ * := ∞ 0 e -s(Dh(θ * )-ζI d ) T (E H(θ * , U )H(θ * , U ) T + Ẽ D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] T )e -s(Dh(θ * )-ζI d ) ds
Lemma 2.5. Let (θ p ) p≥0 be the procedure defined for p ≥ 0 by

θ p+1 = θ p -γ p+1 H(θ p , (U ) p+1 ) (2.12)
where ((U n ) p , (U ) p ) p≥1 is an i.i.d sequence of random variables with the same law as (U n , U ), (γ p ) p≥1 is the step sequence of the procedure (θ n β p ) p≥0 and (θ n p ) p≥0 and θ 0 is independent of the innovation satisfying E|θ 0 | 2 < +∞. Under the assumptions of Theorem 2.9, one has

n α θ n β γ -1 (1/(n 2α-β )) -θ γ -1 (1/(n 2α-β )) -(θ * ,n β -θ * ) =⇒ N (0, Θ * ), n → +∞, with Θ * := ∞ 0 e -s(Dh(θ * )-ζI d ) T Ẽ D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] T e -s(Dh(θ * )-ζI d ) ds and n α θ n γ -1 (1/(n 2α-β )) -θ γ -1 (1/(n 2α-β )) -(θ * ,n -θ * ) P -→ 0, n → +∞.
Proof of Theorem 2.9. We first write the following decomposition

Θ sr n -θ * = θ n β γ -1 (1/n 2α ) -θ * ,n β + θ n γ -1 (1/n 2α-2ρβ ) -θ n β γ -1 (1/n 2α-2ρβ ) -(θ * ,n -θ * ,n β ) + θ * ,n -θ *
For the last term of the above sum, we use Theorem 2.6 to directly deduce

n α (θ * ,n -θ * ) → -Dh -1 (θ * )E(h, α, θ * ), as n → +∞.
For the first term, from Lemma 2.3 it follows

n α (θ n β γ -1 (1/n 2α ) -θ * ,n β ) =⇒ N (0, Γ * ), with Γ * := ∞ 0 exp (-s(Dh(θ * ) -ζI d )) T E[H(θ * , U )H(θ * , U ) T ] exp (-s(Dh(θ * ) -ζI d )) ds. We decompose the last remaining term, namely θ n γ -1 (1/n 2α-2ρβ ) -θ n β γ -1 (1/n 2α-2ρβ ) -(θ * ,n -θ * ,n β ) as follows θ n γ -1 (1/n 2α-2ρβ ) -θ n β γ -1 (1/n 2α-2ρβ ) -(θ * ,n -θ * ,n β ) = θ n γ -1 (1/n 2α-2ρβ ) -θ γ -1 (1/n 2α-2ρβ ) -(θ * ,n -θ * ) -(θ n β γ -1 (1/n 2α-2ρβ ) -θ γ -1 (1/n 2α-2ρβ ) -(θ * ,n β -θ * ))
and use Lemma 2.5 to conclude the proof.

Theorem 2.10. Suppose that h and h n satisfy the assumptions of Theorem 2.6 (with α ∈ (ρ ∨ 2ρβ, 1]) and that h satisfies the assumptions of Theorem 2.4. Assume that the step sequence γ = (γ p ) p≥1 satisfies (HS1) with a ∈ (1/2, 1) and a >

α 2α-2ρβ ∨ α(1-β) (α-ρβ)
. Suppose that (HWR1), (HSR), (HD), (HMR), (HDH) and (HLH) hold and that h n is twice continuously differentiable in a neighborhood of θ * , with Dh n Lipschitz-continuous uniformly in n satisfying:

∀θ ∈ R d , n α-(α-ρβ)a Dh(θ) -Dh n β (θ) → 0, as n → +∞.
(2.13)

Suppose that Ẽ (D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ])(D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ]) T is a positive defi- nite matrix. Then, for M 3 = n 2α and M 4 = n 2α-2ρβ , one has n α ( Θsr n -θ * ) =⇒ Dh -1 (θ * )E(h, α, θ * ) + N (0, Σ * ), n → +∞,
where

Σ * := Dh(θ * ) -1 (E H(θ * , U )H(θ * , U ) T + Ẽ D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] T )(Dh(θ * ) -1 ) T .
Lemma 2.6. Let ( θp ) p≥1 be the empirical mean sequence associated to (θ p ) p≥1 defined by (2.12).Under the assumptions of Theorem 2.10, one has

n α θn β n 2α-2ρβ -θn 2α-2ρβ -(θ * ,n β -θ * ) =⇒ N (0, Θ * ) with Θ * = Dh(θ * ) -1 Ẽ D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] T (Dh(θ * ) -1 ) T and n α θn n 2α-2ρβ -θn 2α-2ρβ -(θ * ,n -θ * ) P -→ 0.
Proof of Theorem 2.10. We decompose the error as follows

Θsr n -θ * = θn β n 2α -θ * ,n β + θn n 2α-2ρβ -θn β n 2α-2ρβ -(θ * ,n -θ * ,n β ) + θ * ,n -θ * .
For the first term, from Lemma 2.4 it follows that

n α ( θn β n 2α -θ * ,n β ) =⇒ N (0, Dh(θ * ) -1 E H(θ * , U )H(θ * , U ) T (Dh(θ * ) -1 ) T ).
For the last term using Theorem 2.6, we have n α (θ * ,nθ * ) → -Dh -1 (θ * )E(h, α, θ * ). We now focus on the last remaining term, namely θn

n 2α-2ρβ -θn β n 2α-2ρβ -(θ * ,n -θ * ,n β
). We decompose it as follows

θn n 2α-2ρβ -θn β n 2α-2ρβ -(θ * ,n -θ * ,n β ) = θn n 2α-2ρβ -θn 2α-2ρβ -(θ * ,n -θ * ) -( θn β n 2α-2ρβ -θn 2α-2ρβ -(θ * ,n β -θ * ))
where ( θp ) p≥1 is the empirical mean sequence associated to (θ p ) p≥1 and use Lemma 2.6 to conclude the proof.

The multi-level stochastic approximation method

As mentioned in the introduction the multi-level SA method uses L + 1 stochastic schemes with a sequence of bias parameter (m ℓ ) ℓ∈[[0,L]] , for a fixed integer m ≥ 2, that satisfies m L = n and estimates θ * by computing the quantity

Θ ml n = θ 1 M0 + L ℓ=1 θ m ℓ M ℓ -θ m ℓ-1 M ℓ .
It is important to point out here that for each level ℓ the couple (θ m ℓ M ℓ , θ m ℓ-1 M ℓ ) is computed using i.i.d. copies of (U m ℓ-1 , U m ℓ ). Moreover the random variables U m ℓ-1 and U m ℓ use two different bias parameter but are perfectly correlated. Moreover, for two different levels, the SA schemes are based on independent samples. Theorem 2.11. Suppose that h and h m ℓ , ℓ = 0, • • • , L, satisfy the assumptions of Theorem 2.6. Assume that (HWR2), (HSR), (HD), (HMR), (HDH) and (HLH) hold and that h n is twice continuously differentiable in a neighborhood of θ * , with Dh n Lipschitz-continuous uniformly in n. Suppose that Ẽ

[(D x H(θ * , U )V - Ẽ[D x H(θ * , U )V ])(D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ]) T ]
is a positive definite matrix. Assume that the step sequence is given by γ p = γ(p), p ≥ 1, where γ is a positive function defined on [0, +∞[ decreasing to zero, satisfying one of the following assumptions:

• γ varies regularly with exponent (-a), a ∈ (1/2, 1), that is, for any x > 0, lim t→+∞ γ(tx)/γ(t) = x -a .

• for t ≥ 1, γ(t) = γ 0 /t and γ 0 satisfies λγ 0 > 1.

Suppose that ρ satisfies one of the following assumptions:

• if ρ ∈ (0, 1/2), then assume that α > 2ρ, λγ 0 > α/(α -2ρ) (if γ(t) = γ 0 /t) and ∃β > ρ, ∀θ ∈ R d , sup n≥1 n β Dh n (θ) -Dh(θ) < +∞.
In this case we set

M 0 = γ -1 (1/n 2α ) and M l = γ -1 (m ℓ (1+2ρ) 2 (m 1-2ρ 2 -1)/(n 2α (n (1-2ρ) 2 -1))), ℓ = 1, • • • , L. • if ρ = 1/2, then assume that α = 1, θ m ℓ 0 = θ 0 , ℓ = 1, • • • , L, with E[|θ 0 | 2 ] < +∞ and ∃β > 1/2, ∀θ ∈ R d , sup n≥1 n β Dh n (θ) -Dh(θ) < +∞.
In this case we set

M 0 = γ -1 (1/n 2 ) and M l = γ -1 (m ℓ log(m)/(n 2 log(n)(m -1))), ℓ = 1, • • • , L.
Then one has

n α (Θ ml n -θ * ) =⇒ -Dh -1 (θ * )E(h, 1, θ * ) + N (0, Σ * ), n → +∞ with Σ * := ∞ 0 e -s(Dh(θ * )-ζI d ) T (E H(θ * , U 1 )H(θ * , U 1 ) T + Ẽ D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] T )e -s(Dh(θ * )-ζI d ) ds
Proof. We first write the following decomposition

Θ ml n -θ * = θ 1 γ -1 (1/n 2 ) -θ * ,1 + L ℓ=1 θ m ℓ M ℓ -θ m ℓ-1 M ℓ -(θ * ,m ℓ -θ * ,m ℓ-1 ) + θ * ,n -θ *
For the last term of the above sum, we use Theorem 2.6 to directly deduce

n α (θ * ,n -θ * ) → -Dh -1 (θ * )E(h, 1, θ * ), as n → +∞.
For the first term, the standard CLT (theorem 2.4) for stochastic approximation leads to

n α (θ 1 γ -1 (1/n 2α ) -θ * ,1 ) =⇒ N (0, Γ * ), N. FRIKHA with Γ * := ∞ 0 exp (-s(Dh(θ * ) -ζI d )) T E H(θ * , U 1 )H(θ * , U 1 ) T exp (-s(Dh(θ * ) -ζI d )) ds.
To deal with the last remaining term, namely

n α L ℓ=1 θ m ℓ M ℓ -θ m ℓ-1 M ℓ -(θ * ,m ℓ -θ * ,m ℓ-1
) we will need the following lemma.

Lemma 2.7. Under the assumptions of Theorem 2.9, one has

n α L ℓ=1 θ m ℓ M ℓ -θ m ℓ-1 M ℓ -(θ * ,m ℓ -θ * ,m ℓ-1 ) =⇒ N (0, Θ * ), n → +∞, with Θ * := ∞ 0 (e -s(Dh(θ * )-ζI d ) ) T Ẽ D x H(θ * , U )V m -Ẽ[D x H(θ * , U )V m ] D x H(θ * , U )V m -Ẽ[D x H(θ * , U )V m ]
T × e -s(Dh(θ * )-ζI d ) ds.

(2.14)

Remark 2.5. The previous result shows that a CLT for the multi-level stochastic approximation estimator of θ * holds if the standard weak error (and thus the implicit weak error), is of order 1/n α and the strong rate error is of order 1/n ρ with α > ρ or α = 1 and ρ = 1/2. Due to the non-linearity of the procedures, which leads to annoying remainder terms in the Taylor's expansions, those results do not seem to easily extend to a weak discretization error of order 1/n α with α < 1 and ρ = 1/2 or a faster strong convergence rate ρ > 1/2. Moreover, for the same reason this result does not seem to extend to the empirical sequence associated to the multi-level estimator according to the Ruppert & Polyak averaging principle.

Complexity Analysis

The result of Theorem 2.9 can be interpreted as follows. For a total error of order 1/n α , it is necessary to set M 1 = γ -1 (1/n 2α ) steps of a stochastic algorithm with time step n β and M 2 = γ -1 (1/(n 2α-2ρβ )) steps of two stochastic algorithms with time step n and n β using the same Brownian motion, the samples used for the first M 1 steps being independent of those used for the second scheme. Hence, the complexity of the statistical Romberg stochastic approximation method is given by

C SR-SA (γ) = C × (n β γ -1 (1/n 2α ) + (n + n β )γ -1 (1/(n 2α-2ρβ )))
(2.15) under the constraint: α > 2ρβ ∨ ρ. Consequently, concerning the impact of the step sequence (γ n ) n≥1 on the complexity of the procedure we have the two following cases:

• If we choose γ(p) = γ 0 /p then simple computations show that β * = 1/(1 + 2ρ) is the optimal choice leading to a complexity C SR-SA (γ) = C ′ n 2α+1/(1+2ρ) , under the constraint λγ 0 > α(1 + 2ρ)/(2α(1 + 2ρ) -2ρ) and α > 2ρ/(1 + 2ρ). Let us note that this computational cost is similar to the one achieved by the statistical Romberg Monte Carlo method for the computation of E x [f (X T )].

• If we choose γ(p) = γ 0 /p a , 1 2 < a < 1 then the computational cost is given by

C SR-SA (γ) = C ′ (n 2α a +β + n 2α a -β a +1 )
which is minimized for β * = a/(2ρ + a) leading to an optimal complexity

C SR-SA (γ) = C ′ n 2α a + a 2ρ+a .
under the constraint α > 2ρa/(a + 2ρ) ∨ ρ. Observe that this complexity decreases with respect to a and that it is minimal for a → 1 leading to the optimal computational cost obtained in the previous case. Let us also point out that contrary to the case γ(p) = γ 0 /p, p ≥ 1 there is no constraint on the choice of γ 0 . Moreover, such condition is difficult to handle in practical implementation so that a blind choice has often to be made.

The CLT proved in Theorem 2.10 shows that for a total error of order 1/n α , it is necessary to set M 1 = n 2α , M 2 = n 2α-2ρβ and to simultaneously compute its empirical mean, which represents a negligible part of the total cost. Both stochastic approximation algorithm are devised with a step γ satisfying (HS1) with a ∈ (1/2, 1) and a >

α 2α-2ρβ ∨ α(1-β) α-ρβ . It is plain to see that β * = 1/(1 + 2ρ
) is the optimal choice leading to a complexity given by

C SR-RP (γ) = C × n 2α+1/(1+2ρ) , provided that a > α(1+2ρ)
2α+2ρ(2α-1) and ∀θ ∈ R d , n α-(α-ρ 1+2ρ )a Dh(θ) -Dh n 1/(1+2ρ) (θ) → 0 as n → +∞ (note that when a → 1 this condition is the same as in Theorem 2.9). For instance, if α = 1 and ρ = 1/2, then this condition writes a > 2/3 and n 1-3 4 a Dh(θ) -Dh n 1/2 (θ) → 0 and a should be selected sufficiently close to 1 according to the weak discretization error of the Jacobian matrix of h. Therefore, the optimal complexity is reached for free without any condition on γ 0 thanks to the Ruppert & Polyak averaging principle. Let us also note that ought we do not intend to develop this point, it is possible to prove that averaging allows to achieve the optimal asymptotic covariance matrix as for standard SA algorithms.

Finally, concerning the CLT provided in Theorem 2.11 shows that in order to obtain an error of order 1/n α , one has to set

M 0 = γ -1 (1/n 2α ) and M l = γ -1 (m ℓ (1+2ρ) 2 (m 1-2ρ 2 -1)/(n 2α (n (1-2ρ) 2 -1))), if ρ ∈ (0, 1/2) or M 0 = γ -1 (1/n 2 ) and M l = γ -1 (m ℓ log(m)/(n 2 log(n)(m -1))) if ρ = 1/2, ℓ = 1, • • • , L.
In both cases the complexity of the multi-level SA method is given by

C ML-SA (γ) = C × γ -1 (1/n 2α ) + L ℓ=1 M ℓ (m ℓ + m ℓ-1 ) .
(2.16)

As for the Statistical Romberg SA method, we distinguish the two following cases:

• If γ(p) = γ 0 /p then the optimal complexity is given by

C ML-SA (γ) = C n 2α + n 2 (n (1-2ρ) 2 -1) m 1-2ρ 2 -1 L ℓ=1 m -(1+2ρ) 2 ℓ (m ℓ + m ℓ-1 ) = O(n 2α n 1-2ρ ),
if ρ ∈ (0, 1/2) under the constraint λγ 0 > α(α -2ρ) and

C ML-SA (γ) = C n 2 + n 2 (log n) 2 m 2 -1 m(log m) 2 = O(n 2 (log(n)) 2 ),
if ρ = 1/2 under the constraint λγ 0 > 1. These computational costs are similar to those achieved by the multi-level Monte Carlo method for the computation of E x [f (X T )], see [START_REF] Giles | Multilevel Monte Carlo path simulation[END_REF] and [START_REF] Ben Alaya | Central limit theorem for the multilevel monte carlo euler method and applications to asian options[END_REF]. As discussed in [START_REF] Giles | Multilevel Monte Carlo path simulation[END_REF], this complexity attains a minimum near m = 7. • If we choose γ(p) = γ 0 /p a , 1 2 < a < 1 then simple computations show that the computational cost is given by

C ML-SA (γ) = C n 2α a + n 2 a (n 1-2ρ -1) 1 a L ℓ=1 m -(1+2ρ) a ℓ (m ℓ + m ℓ-1 ) = O(n 2α a n 1-2ρ a ), N. FRIKHA if ρ ∈ (0, 1/2) and C ML-SA (γ) = C × n 2 a + n 2 a (log n) 1 a (m -1) 1 a (m + 1) m(log m) 1 a L ℓ=1 m -ℓ( 1 a -1) = O(n 2 a (log n) 1 a )
if ρ = 1/2. Observe that once again these computational costs decrease with respect to a and that they are minimal for a → 1 leading to the optimal computational cost obtained in the previous case. In this last case, the optimal choice for the parameter m depends on the value of a.

Remark 2.6. The value of M 0 in Theorem 2.11 seems arbitrary and is asymptotically suboptimal. Indeed choosing M 0 = γ 1 (1/(n 2α n 1-2ρ )) for ρ ∈ (0, 1/2) and M 0 = γ -1 (1/(n 2 log(n))) for ρ = 1/2 does not change the asymptotic computational complexity and simplifies the asymptotic covariance matrix Σ * . One easily proves that n α (θ 1 M0θ * ,1 ) converges to 0 in probability so that Σ * now writes

Σ * := ∞ 0 e -s(Dh(θ * )-ζI d ) T Ẽ D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ]
T × e -s(Dh(θ * )-ζI d ) ds.

Proofs of main results

Proof of Theorem 2.6

We first prove that θ * ,n → θ * , n → +∞. Let ǫ > 0. The mean-reverting assumption (2.6) and the continuity of u → u, h(θ * + ǫu) on the (compact) set

S d := u ∈ R d , |u| = 1 yields η := inf u∈S d u, h(θ * + ǫu) > 0.
The local uniform convergence of (h n ) n≥1 implies

∃n η ∈ N * , ∀n ≥ n η , θ ∈ B(θ * , ǫ) ⇒ |h n (θ) -h(θ)| ≤ η/2.
Then, using the following decomposition

θ -θ * , h n (θ) = θ -θ * , h(θ) + θ -θ * , h n (θ) -h(θ) one has for θ = θ * ± ǫu, u ∈ S d , ǫ u, h n (θ * + ǫu) ≥ ǫu, h(θ * + ǫu) -ǫη/2 ≥ ǫη -ǫη/2 = ǫη/2 -ǫ u, h n (θ * -ǫu) ≥ -ǫu, h(θ * -ǫu) -ǫη/2 ≥ ǫη -ǫη/2 = ǫη/2
so that, u, h n (θ * + ǫu) > 0 and u, h n (θ *ǫu) < 0 which combined with the intermediate value theorem applied to the continuous function x → u, h n (θ * + xu) on the interval [-ǫ, ǫ] yields: u, h n (θ * + xu) = 0 for some x = x(u) ∈]ǫ, ǫ[. Now we set u = θ *θ * ,n /|θ *θ * ,n | as soon as it is possible (otherwise the proof is complete). Hence, there exists

x * ∈] -ǫ, ǫ[ such that θ * -θ * ,n |θ * -θ * ,n | , h n θ * + x * θ * -θ * ,n |θ * -θ * ,n | = 0
so that multiplying the previous equality by x * + |θ *θ * ,n | we get

θ * ,n + x * |θ * -θ * ,n | + 1 (θ * -θ * ,n ) -θ * ,n , h n θ * ,n + x * |θ * -θ * ,n | + 1 (θ * -θ * ,n ) = 0.
Consequently, by the very definition of θ * ,n , we deduce that x * = -|θ *θ * ,n | and finally |θ *θ * ,n | < ǫ for n ≥ n η . Hence, we conclude that θ * ,n → θ * . We now derive a convergence rate. A Taylor expansion yields for all n ≥ 1

h n (θ * ) = h n (θ * ,n ) + 1 0 Dh n (λθ * ,n + (1 -λ)θ * )dλ (θ * -θ * ,n ).
Combining the local uniform convergence of (Dh n ) n≥1 to Dh, the convergence of (θ * ,n ) n≥1 to θ * and the non-singularity of Dh(θ * ), one clearly gets that for n large enough 1 0 Dh n (λθ * ,n + (1λ)θ * )dλ is non singular and that

1 0 Dh n (λθ * ,n + (1 -λ)θ * )dλ -1 → Dh -1 (θ * ), n → +∞.
Consequently, recalling that h(θ * ) = 0 and h n (θ * ,n ) = 0, it is plain to see

n α (θ * ,n -θ * ) = - 1 0 Dh n (λθ * ,n + (1 -λ)θ * )dλ -1 n α (h n (θ * ) -h(θ * )) → -Dh -1 (θ * )E(h, α, θ * ).

Proof of Lemma 2.3

We define for all p ≥ 1, ∆M

n δ p := h n δ (θ n δ p-1 )-H(θ n δ p-1 , (U n δ ) p ) = E[H(θ n δ p-1 , (U n δ ) p )|F p-1 ]-H(θ n δ p-1 , (U n δ ) p
). Recalling that ((U n δ ) p ) p≥1 is a sequence of i.i.d. random variables we have that (∆M n δ p ) p≥1 is a sequence of martingale increments w.r.t. the natural filtration F := (F p := σ(θ n δ 0 , (U n δ ) 1 , • • • , (U n δ ) p ); p ≥ 1). From the dynamic (1.3), one clearly gets for p ≥ 0

θ n δ p+1 -θ * ,n δ = θ n δ p -θ * ,n δ -γ p+1 Dh n δ (θ * ,n δ )(θ n δ p -θ * ,n δ ) + γ p+1 ∆M n δ p+1 + γ p+1 ζ n δ p with ζ n δ p := Dh n δ (θ * ,n δ )(θ n δ p -θ * ,n δ ) -h n δ (θ n δ p ). Moreover, since Dh n δ is Lipschitz-continuous (uniformly in n) by Taylor's formula one gets ζ n δ p = O(|θ n δ p -θ * ,n δ | 2 ).
Hence, by a simple induction, we obtain

θ n δ n -θ * ,n δ = Π 1,n (θ n δ 0 -θ * ,n δ ) + n k=1 γ k Π k+1,n ∆M n δ k + n k=1 γ k Π k+1,n ζ n δ k-1 + (Dh(θ * ) -Dh n δ (θ * ,n δ ))(θ n δ k-1 -θ * ,n δ ) (3.17)
where Π k,n := n j=k (I dγ j Dh(θ * )), with the convention that Π n+1,n = I d . We now investigate the asymptotic behavior of each term in the above decomposition. Actually in step 1 and step 2 we will prove that the first and third terms in the right-hand side of above equality converges in probability to zero at a faster rate than n -α . We will then prove in step 3 that the second term satisfies a CLT at rate n α .

Step 1: study of the sequence n α Π 1,γ -1 (1/n 2α ) (θ n δ 0θ * ,n δ ), n ≥ 0 First, since -Dh(θ * ) is a Hurwitz matrix, ∀λ ∈ [0, λ m ), there exists C > 0 such that for any k ≤ n, Π k,n ≤ C n j=k (1λγ j ) ≤ C exp(-λ n j=k γ j ). We refer to [START_REF] Duflo | Algorithmes stochastiques[END_REF] and [START_REF] Benveniste | Adaptive algorithms and stochastic approximations[END_REF] for more details. Hence, one has for all η ∈ (0, λ m )

n α E|Π 1,γ -1 (1/n 2α ) (θ n δ 0 -θ * ,n δ )| ≤ C(sup n≥1 E|θ n 0 | + 1)n α exp   -(λ m -η) γ -1 (1/n 2α ) k=1 γ k   .
Selecting η such that 2(λ mη)γ 0 > 2(λη)γ 0 > 1 under (HS2) and any η ∈ (0, λ m ) under (HS1), we derive the convergence to zero of the right hand side of the last but one inequality.

Step 2: study of the sequence

n α γ -1 (1/n 2α ) k=1 γ k Π k+1,γ -1 (1/n 2α ) ζ n δ k-1 + (Dh(θ * ) -Dh n δ (θ * ,n δ ))(θ n δ k-1 -θ * ,n δ )
, n ≥ 0 We focus on the last term of (3.17). Using Lemma 5.2 we get

E n k=1 γ k Π k+1,n (ζ n δ k-1 + (Dh(θ * ) -Dh n δ (θ * ,n δ ))(θ n δ k-1 -θ * ,n δ )) ≤ C n k=1 Π k+1,n (γ 2 k + γ 3/2 k Dh(θ * ) -Dh n δ (θ * ,n δ ) ),
so that by Lemma 5.1 (see also remark 2.3), the local uniform convergence of (Dh n ) n≥1 and the continuity of Dh at θ * , we derive lim sup

n n α E γ -1 (1/n 2α ) k=1 γ k Π k+1,γ -1 (1/n 2α ) (ζ n δ k-1 + (Dh(θ * ) -Dh n δ (θ * ,n δ ))(θ n δ k-1 -θ * ,n δ )) = 0.
Step 3: study of the sequence

n α γ -1 (1/n 2α ) k=1 γ k Π k+1,γ -1 (1/n 2α ) ∆M n δ k , n ≥ 0 We use the following decomposition n k=1 γ k Π k+1,n ∆M n δ k = n k=1 γ k Π k+1,n (h n δ (θ n δ k ) -h n δ (θ * ,n δ ) -(H(θ n δ k , (U n δ ) k+1 ) -H(θ * ,n δ , (U n δ ) k+1 ))) + n k=1 γ k Π k+1,n (h n δ (θ * ,n δ ) -H(θ * ,n δ , (U n δ ) k+1 )) := R n + M n Now, using that E H(θ n δ k , (U n δ ) k+1 )|F k = h n δ (θ n δ k ), E H(θ * ,n δ , (U n δ ) k+1 )|F k = h n δ (θ * ,n δ
) and (HR), we have

E|R n | 2 ≤ n k=1 γ 2 k Π k+1,n 2 E[|θ n δ k -θ * ,n δ | 2a ] ≤ n k=1 γ 2+a k Π k+1,n 2
where we used Lemma 5.2 and Jensen's inequality for the last inequality. Moreover, according to Lemma 5.1, we have lim sup

n n 2α γ -1 (1/n 2α ) k=1 γ 2+a k Π k+1,γ -1 (1/n 2α ) 2 = 0 so that, n α n k=1 γ k Π k+1,n (h n δ (θ n δ k ) -h n δ (θ * ,n δ ) -(H(θ n δ k , (U n δ ) k+1 ) -H(θ * ,n δ , (U n δ ) k+1 ))) L 2 (P)
-→ 0. To conclude we prove that the sequence γ -1/2 (n)M n , n ≥ 0 , satisfies a CLT. In order to do this we apply standard results on CLT for martingale arrays. More precisely, we will apply Theorem 3.2 and Corollary 3.1, p.58 in [START_REF] Hall | Martingale limit theory and its application[END_REF] so that we need to prove that the conditional Lindeberg assumption is satisfied, that is lim

n n k=1 E[|γ -1/2 (n)γ k Π k+1,n (h n δ (θ * ,n δ )-H(θ * ,n δ , (U n δ ) k+1 ))| p ]
= 0, for some p > 2 and that the conditional variance (S n ) n≥1 defined by

S n := 1 γ(n) n k=1 γ 2 k Π k+1,n E k [(h n δ (θ * ,n δ ) -H(θ * ,n δ , (U n δ ) k+1 ))(h n δ (θ * ,n δ ) -H(θ * ,n δ , (U n δ ) k+1 )) T ]Π T k+1,n , = 1 γ(n) n k=1 γ 2 k Π k+1,n Γ n Π T k+1,n with Γ n := E[H(θ * ,n δ , U n δ )(H(θ * ,n δ , U n δ )) T ], since h n δ (θ * ,n δ ) = 0, satisfies S n a.s.
-→ Σ * as n → +∞. We also set Γ

* := E[H(θ * , U ))(H(θ * , U )) T ].
By (HI), it holds for some R > 0 such that ∀n ≥ 1, θ * ,n ∈ B(0, R)

n k=1 E γ -1 2 (n)γ k Π k+1,n (h n δ (θ * ,n δ ) -H(θ * ,n δ , (U n δ ) k+1 )) 2+δ ≤ C sup {θ:|θ|≤R,n∈N * } E[|H(θ, U n )| 2+δ ]γ -1+ δ 2 (n) n k=1 γ 2+δ k Π k+1,n 2+δ
By Lemma 5.1, we have lim sup n γ -1+δ/2 (n) n k=1 γ 2+δ k Π k+1,n 2+δ ≤ lim sup n γ δ/2 (n) = 0, so that the conditional Lindeberg condition, see [START_REF] Hall | Martingale limit theory and its application[END_REF], Corollary 3.1, is satisfied. Now we focus on the conditional variance. By the local uniform convergence of (θ

→ E[H(θ, U n δ )(H(θ, U n δ )) T ]) n≥0 , the continuity of θ → E[H(θ, U )(H(θ, U )) T ]
at θ * and since θ * ,n δ → θ * , we have Γ n → Γ * , so that from Lemma 5.1, it follows that lim sup

n 1 γ(n) n k=1 γ 2 k Π k+1,n (Γ n -Γ * )Π T k+1,n ≤ lim sup n Γ n -Γ * = 0.
Hence we see that lim n S n = lim n

1 γ(n) n k=1 γ 2 k Π k+1,n Γ * Π T k+1
,n if this latter limit exists. Let us note that Σ * given by (2.10) is the (unique) matrix A solution to the Lyapunov equation:

Γ * -(Dh(θ * ) -ζI d )A -A(Dh(θ * ) -ζI d ) T = 0.
We aim at proving that S n a.s.

-→ Σ * . In order to do this, we define

A n+1 := 1 γ(n + 1) n+1 k=1 γ 2 k Π k+1,n Γ * Π T k+1,n
which can be written in the following recursive form

A n+1 = γ n+1 Γ * + γ n γ n+1 (I d -γ n+1 Dh(θ * ))A n (I d -γ n+1 Dh(θ * )) T = A n + γ n (Γ * -Dh(θ * )A n -A n Dh(θ * ) T ) + (γ n+1 -γ n )Γ * + γ n γ n+1 Dh(θ * )A n Dh(θ * ) T + γ n -γ n+1 γ n+1 A n
Under the assumptions made on the step sequence (γ n ) n≥1 , we have γn-γn+1 γn+1

= 2ζγ n + o(γ n ) and γ n+1 -γ n = O(γ 2 n ). Consequently, introducing Z n = A n -Σ * ,
simple computations from the previous equality yield

Z n+1 = Z n -γ n (Dh(θ * ) -ζI d )Z n + Z n (Dh(θ * ) -ζI d ) T + γ n γ n+1 Dh(θ * )Z n Dh(θ * ) T + γ n -γ n+1 γ n+1 -2ζγ n I d Z n + γ n γ n+1 Dh(θ * )Σ * Dh(θ * ) T + (γ n+1 -γ n )Γ * + γ n -γ n+1 γ n+1 -2ζγ n I d Σ *
Let us note that by the very definition of ζ and assumptions (HS1), (HS2), the matrix Dh(θ * ) -ζI d is stable, so that taking the norm in the previous equality, there exists λ > 0 such that

Z n+1 ≤ (1 -λγ n + o(γ n )) Z n + o(γ n )
for n ≥ n 0 , n 0 large enough. By a simple induction, it holds for n ≥ N ≥ n 0 -→ Θ * and the proof is complete.

Z n ≤ C Z N exp(-λs N,n ) + C exp(-λs N,n ) n k=N exp(λs N,k )γ k e k

Proof of Lemma 2.4

We freely use the notations and the intermediate results of the proof of Lemma 2.3. Using (3.17) in its recursive form, for any p ≥ 0 and for n large enough, it holds

θ n δ p -θ * ,n δ = - 1 γ p+1 (Dh n δ (θ * ,n δ )) -1 (θ n δ p+1 -θ n δ p ) + (Dh n δ (θ * ,n δ )) -1 ∆M n δ p+1 + (Dh n δ (θ * ,n δ )) -1 ζ n δ p .
Hence, using an Abel's transform we derive

θn δ n 2α -θ * ,n δ = 1 n 2α + 1 n 2α k=0 θ n δ k -θ * ,n δ = - (Dh n δ (θ * ,n δ )) -1 n 2α + 1 n 2α k=0 1 γ k+1 (θ n δ k+1 -θ n δ k ) + (Dh n δ (θ * ,n δ )) -1 n 2α + 1 n 2α k=0 ∆M n δ k+1 + (Dh n δ (θ * ,n δ )) -1 n 2α + 1 n 2α k=0 ζ n δ k = - (Dh n δ (θ * ,n δ )) -1 n 2α + 1 θ n δ n 2α +1 -θ * ,n δ γ n 2α +1 - θ n δ 0 -θ * ,n δ γ 1 - (Dh n δ (θ * ,n δ )) -1 n 2α + 1 n 2α k=1 1 γ k - 1 γ k+1 (θ n δ k -θ * ,n δ ) + (Dh n δ (θ * ,n δ )) -1 n 2α + 1 n 2α k=0 ∆M n δ k+1 + (Dh n δ (θ * ,n δ )) -1 n 2α + 1 n 2α k=0 ζ n δ k
We now study each term of the above decomposition.

Step 1: study of the sequence

n α n 2α +1 θ n δ n 2α +1 -θ * ,n δ γ n 2α +1 - θ n δ 0 -θ * ,n δ γ1
, n ≥ 0

For the first term, by Lemma 5.2 it follows

E n α n 2α + 1 θ n δ n 2α +1 -θ * ,n δ γ n 2α +1 - θ n δ 0 -θ * ,n δ γ 1 ≤ C 1 n 2α γ n 2α +1 + 1 n α (sup n≥1 E|θ n 0 | + 1) ≤ C 1 n 2α γ n 2α +1 + 1 n α -→ 0,
since by (HS1) one has nγ n → 0, n → +∞.

Step 2: study of the sequence

n α n 2α +1 n 2α k=1 1 γ k -1 γ k+1 (θ n δ k -θ * ,n δ )
, n ≥ 0 Similarly for the second term, we have

E n α n 2α + 1 n 2α k=1 1 γ k - 1 γ k+1 (θ n δ k -θ * ,n δ ) ≤ C 1 n α n 2α k=1 γ 1/2 k 1 γ k+1 - 1 γ k γ -1/2 k E|θ n δ k -θ * ,n δ | ≤ C 1 n α n 2α k=1 γ 1/2 k 1 γ k+1 - 1 γ k → 0, n → +∞.
where we used Lemma 5.2 for the last inequality and assumption (HS1) with a < 1.

Step 3: study of the sequence

n α n 2α +1 n 2α k=0 ∆M n δ k+1
, n ≥ 0 As in the proof of Lemma 2.3, we decompose this sequence as follows

n α n 2α + 1 n 2α k=0 ∆M n δ k+1 = n α n 2α + 1 n 2α k=1 (h n δ (θ n δ k ) -h n δ (θ * ,n δ ) -(H(θ n δ k , (U n δ ) k+1 ) -H(θ * ,n δ , (U n δ ) k+1 ))) + n α n 2α + 1 n 2α k=1 (h n δ (θ * ,n δ ) -H(θ * ,n δ , (U n δ ) k+1 )) := R n + M n
For the sequence (R n ) n≥1 we use (HR) to write

E|R n | 2 ≤ C n 2α n 2α k=0 E|H(θ n δ k , (U n δ ) k+1 ) -H(θ * ,n δ , U n δ )| 2 = C n 2α n 2α k=1 γ 2a k → 0,
owing to Cesàro's Lemma. We now prove a CLT for the sequence (M n ) n≥1 by applying Theorem 3.2 and Corollary 3.1, p.58 in [START_REF] Hall | Martingale limit theory and its application[END_REF]. Since θ * ,n δ → θ * and by (HI) it holds for some R > 0

n 2α k=0 E n α n 2α + 1 (h n δ (θ * ,n δ ) -H(θ * ,n δ , (U n δ ) k+1 )) 2+δ ≤ C n αb ( sup θ:|θ|≤R, n∈N * E|H(θ, U n )| 2+δ ) → 0, n → +∞,
so that the conditional Lindeberg condition is satisfisfied, see [START_REF] Hall | Martingale limit theory and its application[END_REF] Corollary 3.1. Now, we focus on the conditional variance. For convenience, we set

S n := n 2α (n 2α + 1) 2 n 2α k=1 E k [(h n δ (θ * ,n δ ) -H(θ * ,n δ , (U n δ ) k+1 ))(h n δ (θ * ,n δ ) -H(θ * ,n δ , (U n δ ) k+1 )) T ] = n 2α (n 2α + 1) 2 n 2α k=1 E[H(θ * ,n δ , U n δ )(H(θ * ,n δ , U n δ )) T ] = n 4α (n 2α + 1) 2 E[H(θ * ,n δ , U n δ )(H(θ * ,n δ , U n δ )) T ], so that we clearly have S n → E[H(θ * , U )(H(θ * , U )) T ] by the local uniform convergence of (θ → E[H(θ, U n )(H(θ, U n )) T ]) n≥1 , the continuity of θ → E[H(θ, U )(H(θ, U )) T ] at θ * and the convergence of (θ * ,n δ ) n≥1 towards θ * . Therefore, since (Dh n δ (θ * ,n δ )) -1 → (Dh(θ * )) -1 , we conclude that (Dh n δ (θ * ,n δ )) -1 n α n 2α + 1 n 2α k=0 ∆M n δ k+1 =⇒ N (0, Dh(θ * ) -1 E x [H(θ * , U )H(θ * , U ) T ](Dh(θ * ) -1 ) T ).
Step 4: study of the sequence

n α n 2α +1 n 2α k=0 ζ n δ
k , n ≥ 0 Now, observe that by Lemma 5.2 the last term is bounded in L 1 -norm by

n α n 2α + 1 n 2α k=0 E|ζ n δ k | ≤ C n α n 2α k=0 γ k → 0, n → +∞
since γ satisfies (HS1) with a < 1.

3.4. Proof of Lemma 2.5

We will just prove the first assertion of the Lemma. The second one will readily follow. When the exact value of a constant is not important we may repeat the same symbol for constants that may change from one line to next. We come back to the decomposition used in the proof of Lemma 2.3. We consequently use the same notations. Let us note that the procedure (θ p ) p≥0 a.s. converges to θ * and satisfies a CLT according to Theorem 2.4.

From the dynamics of (θ n δ p ) p≥0 and (θ p ) p≥0 we write for p ≥ 0

θ n β p+1 -θ * ,n β = θ n β p -θ * ,n β -γ p+1 Dh n β (θ * ,n β )(θ n β p -θ * ,n β ) + γ p+1 ∆M n p+1 + γ p+1 ζ n β p θ p+1 -θ * = θ p -θ * -γ p+1 Dh(θ * )(θ p -θ * ) + γ p+1 ∆M p+1 + γ p+1 ζ p ,
with ∆M p+1 = h(θ p )-H(θ p , (U ) p+1 ), p ≥ 0, and

ζ n β p := Dh n β (θ * ,n β )(θ n β p -θ * ,n β )-h n β (θ n β p ), ζ p = Dh(θ * )(θ p - θ * ) -h(θ p ).
Since Dh n and Dh are Lipschitz-continuous, by Taylor's formula one gets

ζ n β p = O(|θ n β p -θ * ,n β | 2 ) and ζ p = O(|θ p -θ * | 2 ). Therefore, defining z n β p = θ n β p -θ p -(θ * ,n β -θ * ), p ≥ 0, with z n β 0 = θ * -θ * ,n β ,

by a simple induction argument one has

z n β n = Π 1,n z n β 0 + n k=1 γ k Π k+1,n ∆N n β k + n k=1 γ k Π k+1,n ∆R n β k + n k=1 γ k Π k+1,n ζ n k-1 -ζ k-1 + (Dh(θ * ) -Dh n β (θ * ,n β ))(θ n β k-1 -θ * ,n β ) (3.18)
where Π k,n := n j=k (I dγ j Dh(θ * )), with the convention that Π n+1,n = I d , and ∆N

n β k := h n β (θ * ) -h(θ * ) - (H(θ * , (U n β ) k+1 ) -H(θ * , U k+1 )), ∆R n β k = h n β (θ n β k ) -h n β (θ * ) -(H(θ n β k , (U n β ) k+1 ) -H(θ * , (U n β ) k+1 )) + H(θ k , U k+1 ) -H(θ * , U k+1 ) -(h(θ k ) -h(θ *
)) for k ≥ 1. We will now investigate the asymptotic behavior of each term in the above decomposition. We will see that the second term which represents the non-linearity in the innovation variables (U n β , U ) provides the announced weak rate of convergence.

Step 1: study of the sequence n α Π 1,γ -1 (1/(n 2α-2ρβ )) z n β 0 , n ≥ 0 Under the assumptions on the step sequence γ, one has for all η ∈ (0, λ m )

n α E |Π 1,γ -1 (1/(n 2α-2ρβ )) z n β 0 | ≤ n α Π 1,γ -1 (1/(n 2α-2ρβ )) (E|θ 0 | + sup n≥1 E|θ n 0 | + |θ * ,n β -θ * |) ≤ Cn α exp   -(λ m -η) γ -1 (1/(n 2α-2ρβ )) k=1 γ k   → 0, by selecting η s.t. (λ m -η)γ 0 > (λ -η)γ 0 > α/(2α -2ρβ) if γ(p) = γ 0 /p, p ≥ 1.
Step 2: study of the sequence

n α γ -1 (1/(n 2α-2ρβ )) k=1 γ k Π k+1,γ -1 (1/(n 2α-2ρβ )) ζ n k-1 -ζ k-1 + (Dh(θ * ) -Dh n β (θ * ,n β ))(θ n β k-1 -θ * ,n β ) , n ≥ 0 By Lemma 5.2, one has E n k=1 γ k Π k+1,n (ζ n β k-1 -ζ k-1 + (Dh(θ * ) -Dh n β (θ * ,n β ))(θ n β k-1 -θ * ,n β )) ≤ C n k=1 Π k+1,n (γ 2 k + γ 3/2 k Dh(θ * ) -Dh n β (θ * ,n β ) ),
so that by Lemma 5.1, we easily derive that (if γ(p) = γ 0 /p recall that λγ 0 > α/(2α-2ρβ))

n k=1 γ 2 k Π k+1,n = o(γ α/(2α-2ρβ) (n)) and (recall that λγ 0 > α/(2α -2ρβ) > 1/2) n k=1 γ 3/2 k Π k+1,n = O(γ 1/2 (n)) so that lim sup n n α γ -1 (1/(n 2α-2ρβ )) k=1 γ 2 k Π k+1,γ -1 (1/(n 2α-2ρβ )) = 0.
Moreover, since Dh n β is Lipschitz-continuous (uniformly in n) we clearly have

n k=1 γ 3/2 k Π k+1,n Dh(θ * ) -Dh n β (θ * ,n β ) ≤ n k=1 γ 3/2 k Π k+1,n ( Dh(θ * ) -Dh n β (θ * ) + |θ * ,n β -θ * |) which combined with n ρβ Dh(θ * ) -Dh n β (θ * ) → 0 and n ρβ |θ * ,n β -θ * | → 0 (recall that α > ρ) imply that lim sup n n α γ -1 (1/(n 2α-2ρβ )) k=1 γ 3/2 k Π k+1,γ -1 (1/(n 2α-2ρβ )) Dh(θ * ) -Dh n β (θ * ,n β ) = 0.
Hence, we conclude that

n α γ -1 (1/(n 2α-2ρβ )) k=1 γ k Π k+1,γ -1 (1/(n 2α-2ρβ )) ζ n β k-1 -ζ k-1 + (Dh(θ * ) -Dh n β (θ * ,n β ))(θ n β k-1 -θ * ,n β ) L 1 (P) -→ 0.
Step 3: study of the sequence

n α γ -1 (1/(n 2α-2ρβ )) k=1 γ k Π k+1,γ -1 (1/(n 2α-2ρβ )) ∆R n β k , n ≥ 0 Regarding the third term of (3.18), namely n k=1 γ k Π k+1,n ∆R n β k , we decompose it as follows n k=1 γ k Π k+1,n ∆R n β k = n k=1 γ k Π k+1,n (h n β (θ n β k ) -h n β (θ * ) -(H(θ n β k , (U n β ) k+1 ) -H(θ * , (U n β ) k+1 ))) + n k=1 γ k Π k+1,n (H(θ k , U k+1 ) -H(θ * , U k+1 ) -(h(θ k ) -h(θ * ))) = A n + B n Now, using that E H(θ n β k , (U n β ) k+1 ) -H(θ * , (U n β ) k+1 ) F k = h n β (θ n β k ) -h n β (θ * ) and (HLH) it follows that E|A n | 2 ≤ C n k=1 γ 2 k Π k+1,n 2 (E|θ n β k -θ * ,n β | 2 + |θ * ,n β -θ * | 2 ) ≤ C( n k=1 γ 3 k Π k+1,n 2 + n k=1 γ 2 k Π k+1,n 2 |θ * ,n β -θ * | 2 ) := A 1 n + A 2 n From Lemma 5.1 we get n k=1 γ 3 k Π k+1,n 2 = o(γ 2α/(2α-2ρβ) n ) and n k=1 γ 2 k Π k+1,n 2 = O(γ n ). Conse- quently, we derive lim sup n n 2α A 1 γ -1 (1/(n 2α-2ρβ )) = 0 and lim sup n n 2α A 2 γ -1 (1/(n 2α-2ρβ
)) = 0. Similarly using (HLH) and Lemma 5.2 we derive n α B γ -1 (1/(n 2α-2ρβ ))

L 2 (P) -→ 0 as n → +∞ so that

n α γ -1 (1/(n 2α-2ρβ )) k=1 γ k Π k+1,γ -1 (1/(n 2α-2ρβ )) ∆R n β k P -→ 0, n → +∞. N. FRIKHA
Step 4: study of the sequence

n α γ -1 (1/(n 2α-2ρβ )) k=1 γ k Π k+1,γ -1 (1/(n 2α-2ρβ )) ∆N n β k , n ≥ 0 We now prove a CLT for the sequence n α γ -1 (1/(n 2α-2ρβ )) k=1 γ k Π k+1,γ -1 (1/(n 2α-2ρβ )) ∆N n β k , n ≥ 0 . It holds γ -1 (1/(n 2α-2ρβ )) k=1 E n α γ k Π k+1,γ -1 (1/(n 2α-2ρβ )) ∆N n β k 2+δ ≤ sup n≥1 sup k∈[[1,n]] E n ρβ ∆N n β k 2+δ × n (2+δ)(α-ρβ) γ -1 (1/(n 2α-2ρβ )) k=1 γ 2+δ k Π k+1,γ -1 (1/(n 2α-2ρβ )) 2+δ
.

By Lemma 5.1, we have the following bound:

n k=1 γ 2+δ k Π k+1,n 2+δ = o(γ (2+δ)(α-ρβ)/(2α-2ρβ) (n)) which implies lim sup n n (2+δ)(α-ρβ) γ -1 (1/(n 2α-2ρβ )) k=1 γ 2+δ k Π k+1,γ -1 (1/(n 2α-2ρβ )) 2+δ = 0.
Moreover simple computations lead

E n ρβ ∆N n β k 2+δ ≤ C(|n ρβ (h n β (θ * ) -h(θ * ))| 2+δ + E(n ρβ |H(θ * , U n β ) -H(θ * , U )|) 2+δ ).
For the first term in the above inequality we have sup < +∞, so that the conditional Lindeberg condition holds. Now, we focus on the conditional variance. We set

n≥1 |n ρβ (h n β (θ * ) -h(θ * ))| 2+ δ < +∞ ⇔ α ≥ ρ.
S n := n 2α γ -1 (1/(n 2α-2ρβ )) k=1 γ 2 k Π k+1,γ -1 (1/(n 2α-2ρβ )) E k [∆N n β k (∆N n β k ) T ]Π T k+1,γ -1 (1/(n 2α-2ρβ
)) , and

V n β = U n β -U.
(3.19) A Taylor's expansion yields

n ρβ H(θ * , U n β ) -H(θ * , U ) = D x H(θ * , U )n ρβ V n β + ψ(θ * , U, V n β )n ρβ V n β with ψ(θ * , U, V n β ) P -→ 0. From the tightness of (n ρβ V n β ) n≥1 , we get ψ(θ * , U, V n β )n ρβ V n β P
-→ 0 so that using Theorem 2.1 and Lemma 2.1 yield

n ρβ H(θ * , U n β ) -H(θ * , U ) =⇒ D x H(θ * , U )V.
Moreover, from assumptions (HLH) and (HSR) it follows that

sup n≥1 E |n ρβ (H(θ * , U n β ) -H(θ * , U ))| 2+δ < +∞, which combined with (HDH) imply E n ρβ H(θ * , U n β ) -H(θ * , U ) → Ẽ[D x H(θ * , U )V ] E n ρβ H(θ * , U n β ) -H(θ * , U ) n ρβ H(θ * , U n β ) -H(θ * , U ) T → Ẽ (D x H(θ * , U )V ) (D x H(θ * , U )V ) T .
Hence, we have

Γ n → Γ * := Ẽ D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ]
T where for n ≥ 1 we set

Γ n := n 2ρβ E k [∆N n β k (∆N n β k ) T ]. Consequently, using the following decomposition 1 γ(n) n k=1 γ 2 k Π k+1,n Γ n Π T k+1,n = 1 γ(n) n k=1 γ 2 k Π k+1,n Γ * Π T k+1,n + 1 γ(n) n k=1 γ 2 k Π k+1,n (Γ n -Γ * )Π T k+1,n with lim sup n 1 γ(n) n k=1 γ 2 k Π k+1,n (Γ n -Γ * )Π T k+1,n ≤ C lim sup n Γ n -Γ * = 0,
which is a consequence of Lemma 5.1, we clearly see that lim n S n = lim n

1 γ(n) n k=1 γ 2 k Π k+1,n Γ * Π T k+1
,n if this latter limit exists. Let us note that Θ * is the (unique) matrix A solution to the Lyapunov equation:

Γ * -(Dh(θ * ) -ζI d )A -A(Dh(θ * ) -ζI d ) T = 0.
Following the lines of the proof of Lemma 2.3, step 3, we have S n a.s.

-→ Θ * . We leave the computational details to the reader.

Proof of Lemma 2.6

We will just prove the first assertion. The second one will readily follow. We use C to denote a constant that may change from one line to the next. Using the notations of Lemma 2.5, the sequence (z n β p ) p∈[[0,n 2α-2ρβ ]] can be decomposed as follows:

zn β n 2α-2ρβ = 1 n 2α-2ρβ + 1 n 2α-2ρβ k=0 z n β k = -(Dh(θ * )) -1 1 n 2α-2ρβ + 1 z n β n 2α-2ρβ +1 γ n 2α-2ρβ +1 - z n β 0 γ 1 -(Dh(θ * )) -1 1 n 2α-2ρβ + 1 n 2α-2ρβ k=1 1 γ k - 1 γ k+1 z n β k + (Dh(θ * )) -1 1 n 2α-2ρβ + 1 n 2α-2ρβ k=0 (∆N n β k+1 + ∆R n β k+1 ) + (Dh(θ * )) -1 1 n 2α-2ρβ + 1 n 2α-2ρβ k=0 (ζ n β k -ζ k + (Dh(θ * ) -Dh n β (θ * ,n β ))(θ n β k -θ * ,n β )).
Our aim is to study the contribution of each term in this decomposition.

N. FRIKHA

Step 1: study of the sequence

n α n 2α-2ρβ +1 z n β n 2α-2ρβ +1 γ n 2α-2ρβ +1 - z n β 0 γ1
, n ≥ 0 : Using Proposition 5.1 clearly yields

n α n 2α-2ρβ + 1 E z n β n 2α-2ρβ +1 γ n 2α-2ρβ +1 - z n β 0 γ 1 ≤ C (n α-2ρβ γ n 2α-2ρβ +1 ) (E|μ n β n 2α-2ρβ | + E|r n β n 2α-2ρβ |) + C n α-2ρβ (1 + |θ * -θ * ,n β |).
We evaluate each term appearing in the right hand side of the last but one inequality. First we clearly have

1 (n α-2ρβ )γ n 2α-2ρβ +1 E|μ n β n 2α-2ρβ | ≤ C (n 2α-2ρβ )γ n 2α-2ρβ +1 → 0, as n → +∞, and 1 (n α-2ρβ )γ n 2α-2ρβ +1 E|r n β n 2α-2ρβ | ≤ C n α-2ρβ → 0, as n → +∞.
From these computations we get

n α n 2α-2ρβ + 1 z n β n 2α-2ρβ +1 γ n 2α-2ρβ +1 - z n β 0 γ 1 L 1 (P) -→ 0, as n → +∞.
Step 2: study of the sequence

n α n 2α-2ρβ +1 n 2α-2ρβ k=1 1 γ k -1 γ k+1 z n β k , n ≥ 0 : We use the decomposition of Proposition 5.1 to derive n α n 2α-2ρβ + 1 n 2α-2ρβ k=1 1 γ k - 1 γ k+1 z n β k ≤ n α n 2α-2ρβ + 1 n 2α-2ρβ k=1 1 γ k+1 - 1 γ k (|μ n β k | + |r n β k |).
Then taking the expectation in the previous inequality and using that ρ < 1 we deduce

n α n 2α-2ρβ + 1 n 2α-2ρβ k=1 1 γ k+1 - 1 γ k E|μ n β k | ≤ C n α-ρβ n 2α-2ρβ k=1 1 γ k+1 - 1 γ k γ 1 2 k → 0.
For the second term, we have

n α n 2α-2ρβ + 1 n 2α-2ρβ k=1 1 γ k+1 - 1 γ k E|r n β k | ≤ C n α-2ρβ n 2α-2ρβ k=1 1 γ k+1 - 1 γ k γ k → 0, since α > 2ρβ which in turn implies n α n 2α-β + 1 n 2α-2ρβ k=1 1 γ k - 1 γ k+1 z n β k L 1 (P) -→ 0.
Step 3: study of the sequence

n α n 2α-2ρβ +1 n 2α-2ρβ k=1 (ζ n β k -ζ k + (Dh(θ * ) -Dh n β (θ * ,n β ))(θ n β k -θ * ,n β ))
, n ≥ 0 : Now we focus on the last term. We firstly note that thanks to Lemma 5.2 we clearly have

n α n 2α-2ρβ + 1 E n 2α-2ρβ k=0 (ζ n β k -ζ k ) ≤ C n α-2ρβ n 2α-2ρβ k=0 γ k → 0 since a > α/(2α -2ρβ). Now since Dh n β is Lipschitz-continuous uniformly in n we easily get n α n 2α-2ρβ + 1 E n 2α-2ρβ k=0 (Dh(θ * ) -Dh n β (θ * ,n β ))(θ n β k -θ * ,n β ) ≤ C n α-2ρβ ( Dh(θ * )-Dh n β (θ * ) +|θ * -θ * ,n β |) n 2α-2ρβ k=0 γ 1 2 k , and recalling that n α-(α-ρβ)a Dh(θ * )-Dh n β (θ * ) → 0 and a > α(1-β)/(α-ρβ) which implies n α-(α-ρβ)a |θ * - θ * ,n β | → 0 we deduce n α n 2α-2ρβ + 1 n 2α-2ρβ k=0 (Dh(θ * ) -Dh n β (θ * ,n β ))(θ n β k -θ * ,n β ) L 1 (P) -→ 0.
Step 4: study of the sequence

n α n 2α-2ρβ +1 n 2α-2ρβ k=0 (∆N n β k+1 + ∆R n β k+1
), n ≥ 0 : Similarly to the proof of Lemma 2.7, we decompose the sequence

n α n 2α-2ρβ +1 n 2α-2ρβ k=1 ∆R n β k , n ≥ 1 as follows n α n 2α-2ρβ + 1 n 2α-2ρβ k=0 ∆R n β k = n α n 2α-2ρβ + 1 n 2α-2ρβ k=0 (h n β (θ n β k ) -h n β (θ * ) -(H(θ n β k , (U n β ) k+1 ) -H(θ * , (U n β ) k+1 ))) + n α n 2α-2ρβ + 1 n 2α-β T k=0 (H(θ k , U k+1 ) -H(θ * , U k+1 ) -(h(θ k ) -h(θ * ))) = A n + B n .
From the Cauchy-Schwarz inequality and Lemma 5.2 it easily follows

E|A n | + E|B n | ≤ 1 n α-2ρβ   n 2α-2ρβ k=0 γ k   1 2 → 0 since a > α/(2α -2ρβ) > ρβ/(α -ρβ) so that n α n 2α-2ρβ + 1 n 2α-2ρβ k=0 ∆R n β k P -→ 0, n → +∞.
We now prove a CLT for the sequence

n α n 2α-2ρβ +1 n 2α-2ρβ k=0 ∆N n β k , n ≥ 0 . We first note n 2α-2ρβ k=0 E n α n 2α-2ρβ + 1 ∆N n β k 2+δ ≤ sup n≥1 sup k∈[[0,n]] E n ρβ ∆N n β k 2+δ 1 n αδ-ρβδ → 0 n → +∞
where we used assumptions (HLH) and (HSR) to derive that sup

n≥1 sup k∈[[1,n]] E n ρβ ∆N n β k 2+δ < +∞.
Therefore the conditional Lindeberg condition is satisfied. Then we examine the conditional variance. Recall that (see the the proof of Lemma 2.7) we have

n 2ρβ E k [∆N n β k (∆N n β k ) T ] = n 2ρβ E (H(θ * , U n β ) -H(θ * , U ) -(h n β (θ * ) -h(θ * ))) ×(H(θ * , U n β ) -H(θ * , U ) -(h n β (θ * ) -h(θ * ))) T → Ẽ D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ] D x H(θ * , U )V -Ẽ[D x H(θ * , U )V ]
T , so that if we set

S n := n 2α (n 2α-2ρβ + 1) 2 n 2α-2ρβ k=0 E k [∆N n β k (∆N n β k ) T ] = n 2α-2ρβ n 2α-2ρβ + 1 n 2ρβ E (H(θ * , U n β ) -H(θ * , U ) -(h n β (θ * ) -h(θ * )))(H(θ * , U n β ) -H(θ * , U ) -(h n β (θ * ) -h(θ * ))) T , we clearly get S n → Ẽ (D x H(θ * , U )V ) (D x H(θ * , U )V ) T .
This completes the proof.

3.6. Proof of Lemma 2.7

We come back to the decomposition used in the proof of Lemma 2.3. We consequently use the same notations. We will not go into all computational details. We deal with the case ρ ∈ (0, 1/2). The case ρ = 1/2 can be handled in a similar fashion.

We first write for p ≥ 0

θ m ℓ p+1 -θ * ,m ℓ = θ m ℓ p -θ * ,m ℓ -γ p+1 Dh m ℓ (θ * ,m ℓ )(θ m ℓ p -θ * ,m ℓ ) + γ p+1 ∆M m ℓ p+1 + γ p+1 ζ m ℓ p with ∆M m ℓ p+1 = h m ℓ (θ m ℓ p ) -H(θ m ℓ p , (X m ℓ T ) p+1 ) and ζ m ℓ p = O(|θ m ℓ p+1 -θ * ,m ℓ | 2 ), p ≥ 0. Therefore, defining z ℓ p = θ m ℓ p -θ m ℓ-1 p -(θ * ,m ℓ -θ * ,m ℓ-1 ), p ≥ 0, with z ℓ 0 = θ m ℓ 0 -θ m ℓ 0 -(θ * ,m ℓ -θ * ,m ℓ-1
), by a simple induction argument one has

z ℓ M ℓ = Π 1,M ℓ z ℓ 0 + M ℓ k=1 γ k Π k+1,M ℓ ∆N ℓ k + M ℓ k=1 γ k Π k+1,M ℓ ∆R ℓ k + M ℓ k=1 γ k Π k+1,M ℓ ζ ℓ k-1 -ζ ℓ-1 k-1 + (Dh(θ * ) -Dh m ℓ (θ * ,m ℓ ))(θ m ℓ k-1 -θ * ,m ℓ ) -(Dh(θ * ) -Dh m ℓ-1 (θ * ,m ℓ-1 ))(θ m ℓ-1 k-1 -θ * ,m ℓ-1 ) (3.
:= h m ℓ (θ * )-h m ℓ-1 (θ * )- (H(θ * , (U m ℓ ) k+1 )-H(θ * , (U m ℓ-1 ) k+1 )), ∆R ℓ k = h m ℓ (θ m ℓ k )-h m ℓ (θ * )-(H(θ m ℓ k , (U m ℓ ) k+1 )-H(θ * , (U m ℓ ) k+1 ))+ H(θ m ℓ-1 k , (U m ℓ-1 ) k+1 )-H(θ * , (U m ℓ-1 ) k+1 )-(h m ℓ-1 (θ m ℓ-1 k
)-h m ℓ-1 (θ * )) for k ≥ 0. We follow the same methodology developed so far and quantify the contribution of each term. Once again the weak rate of convergence will be ruled by the second term which involves the non-linearity in the innovation variable (U m ℓ-1 , U m ℓ ), for which we prove a CLT.

Step 1: study of n α L ℓ=1 Π 1,M ℓ z ℓ 0 , n ≥ 0 Under the assumptions on the step sequence γ, for all η ∈ (0, λ m ) we have Π

1,M ℓ ≤ exp(-(λ m - η) M ℓ k=1 γ k ) = Cm ℓ (1+2ρ) 2 (λm-η)γ0 /((n 2α+ 1-2ρ 2 ) (λm-η)γ0 ) if γ(p) = γ 0 /p or Π 1,M ℓ = O(γ(M ℓ )) otherwise. Therefore, if γ(p) = γ 0 /p we select η > 0 such that γ 0 (λ m -η) > α/(α -2ρ) then one has E n α L ℓ=1 Π 1,M ℓ z ℓ 0 ≤ Cn α L ℓ=1 Π 1,M ℓ ≤ C n (λm-η)γ0(2α+ 1-2ρ 2 )-α L ℓ=1 m ℓ(λm-η)γ0 1+2ρ 2 ≤ C n 2(λm-η)γ0(α-2ρ)-α → 0 as n → +∞. Otherwise one has E n α L ℓ=1 Π 1,M ℓ z ℓ 0 ≤ Cn α L ℓ=1 γ(M ℓ ) ≤ C n 1+2ρ 2 n α+ 1-2ρ 2 = C n α-2ρ → 0.
Step 2: study of

n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ ζ ℓ k-1 -ζ ℓ-1 k-1 , n ≥ 0 By Lemma 5.2, one has E n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ ζ ℓ k-1 -ζ ℓ-1 k-1 ≤ Cn α L ℓ=1 M ℓ k=1 γ 2 k Π k+1,M ℓ .
However, by Lemma 5.1 (if γ(p) = γ 0 /p recall that λ m γ 0 > 1) we easily derive lim sup n

1 γ(n) n k=1 γ 2 k Π k+1,n ≤ 1, so that n α L ℓ=1 M ℓ k=1 γ 2 k Π k+1,M ℓ ≤ Cn α L ℓ=1 γ(M ℓ ) → 0, n → +∞.
Step 3: study of

n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ (Dh(θ * ) -Dh m ℓ (θ * ,m ℓ ))(θ m ℓ k-1 -θ * ,m ℓ ) , n ≥ 0 and n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ (Dh(θ * ) -Dh m ℓ-1 (θ * ,m ℓ-1 ))(θ m ℓ-1
k-1θ * ,m ℓ-1 ) , n ≥ 0 By Lemma 5.2 and since Dh m ℓ is a Lipschitz function uniformly in m we clearly have

E n α L ℓ=1 M ℓ k=1 γ 3/2 k Π k+1,M ℓ (Dh(θ * ) -Dh m ℓ (θ * ,m ℓ ))(θ m ℓ k-1 -θ * ,m ℓ ) ≤ n α L ℓ=1 M ℓ k=1 γ 3/2 k Π k+1,n × ( Dh(θ * ) -Dh m ℓ (θ * ) + |θ * ,m ℓ -θ * )|) ≤ Cn α L ℓ=1 γ 1/2 (M ℓ )( Dh(θ * ) -Dh m ℓ (θ * ) + |θ * ,m ℓ -θ * )|)
which combined with sup n≥1 n β Dh(θ * ) -Dh n (θ * ) < +∞ with β > ρ and sup n≥1 n α |θ * ,nθ * | < +∞ imply that

E n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ (Dh(θ * ) -Dh m ℓ (θ * ,m ℓ ))(θ m ℓ k-1 -θ * ,m ℓ ) ≤ C n (1-2ρ) 4 L ℓ=1 m ℓ (1+2ρ) 4 (m -ℓα + m -ℓβ ) ≤ C(n ρ-α + n ρ-β ) so that n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ (Dh(θ * )-Dh m ℓ (θ * ,m ℓ ))(θ m ℓ k-1 -θ * ,m ℓ ) L 1 (P)
-→ 0. By similar arguments, we easily

deduce n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ (Dh(θ * ) -Dh m ℓ-1 (θ * ,m ℓ-1 ))(θ m ℓ-1 k-1 -θ * ,m ℓ-1 ) L 1 (P) -→ 0.
Step 4: study of n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ ∆R ℓ k , n ≥ 0 Using the Cauchy-Schwarz inequality we deduce

E n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ ∆R ℓ k 2 ≤ n α L ℓ=1 M ℓ k=1 γ 2 k Π k+1,M ℓ 2 E|H(θ m ℓ k , (U m ℓ ) k+1 ) -H(θ * , (U m ℓ ) k+1 )| 2 1/2 + n α L ℓ=1 M ℓ k=1 γ 2 k Π k+1,M ℓ 2 E|H(θ m ℓ-1 k , (U m ℓ-1 ) k+1 ) -H(θ * , (U m ℓ-1 ) k+1 )| 2 1/2 ≤ Cn α L ℓ=1 M ℓ k=1 γ 3 k Π k+1,M ℓ 2 1/2
where we used (HLH) and Lemma 5.2. Now from Lemma 5.1 and simple computations it follows

n α L ℓ=1 M ℓ k=1 γ 3 k Π k+1,M ℓ 2 1/2 ≤ Cn α L ℓ=1 γ(M ℓ ) → 0, n → +∞.
Therefore, we conclude that

n L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ ∆R ℓ k L 2 (P)
-→ 0, n → +∞.

Step 5: study of

n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ ∆N ℓ k , n ≥ 0 We now prove a CLT for the sequence n α L ℓ=1 M ℓ k=1 γ k Π k+1,M ℓ ∆N ℓ
k , n ≥ 0 . By Burkholder's inequality and elementary computations, it holds

L ℓ=1 E M ℓ k=1 n α γ k Π k+1,M ℓ ∆N ℓ k 2+δ ≤ Cn (2+δ)α L ℓ=1 E M ℓ k=1 γ 2 k Π k+1,M ℓ 2 |∆N ℓ k | 2 1+δ/2 ≤ Cn (2+δ)α L ℓ=1 ( M ℓ k=1 γ 2 k Π k+1,M ℓ 2 ) δ/2 M ℓ k=1 γ 2+δ k Π k+1,M ℓ 2+δ E|∆N ℓ k | 2+δ .
Using (HLH) and (HSR)

we have sup ℓ≥1 E(m ρℓ |H(θ * , U m ℓ ) -H(θ * , U )|) 2+δ < +∞ so that E|∆N ℓ k | 2+δ ≤ K m ℓ(2ρ+ρδ) .
Moreover, by Lemma 5.1, we have

lim sup n (1/γ (1+δ) (n)) n k=1 γ 2+δ k Π k+1,n 2+δ ≤ 1 and lim sup n (1/γ(n)) n k=1 γ 2 k Π k+1,n 2 ≤ 1.
Consequently we deduce

L ℓ=1 E M ℓ k=1 n α γ k Π k+1,M ℓ ∆N ℓ k 2+δ ≤ Cn (2+δ)α L ℓ=1 γ 1+3δ/2 (M ℓ )m -ℓ(2ρ+ρδ) ≤ C n 2αδ n 2ρ(1+3δ/2)-2ρ-ρδ = C n 2δ(α-ρ)
which in turn implies

L ℓ=1 E M ℓ k=1 n α γ k Π k+1,M ℓ ∆N ℓ k 2+δ
→ 0, n → +∞ so that the conditional Lindeberg condition is satisfied. Now, we focus on the conditional variance. We set

S ℓ := n 2α M ℓ k=1 γ 2 k Π k+1,M ℓ E k [∆N ℓ k (∆N ℓ k ) T ]Π T k+1,M ℓ , and U ℓ = U m ℓ -U m ℓ-1 . (3.21)
Observe that by the very definition of M ℓ one has

S ℓ = 1 γ(M ℓ ) (m 1-2ρ 2 -1) m ℓ (1+2ρ) 2 n 1-2ρ 2 -1 M ℓ k=1 γ 2 k Π k+1,M ℓ E k [∆N ℓ k (∆N ℓ k ) T ]Π T k+1,M ℓ A Taylor's expansion yields H(θ * , U m ℓ ) -H(θ * , U m ℓ-1 ) = D x H(θ * , U )U ℓ + ψ(θ * , U, U m ℓ -U )(U m ℓ -U ) + ψ(θ * , U, U m ℓ-1 -U )(U m ℓ-1 -U )
with (ψ(θ * , U, U m ℓ -U ), ψ(θ * , U, U m ℓ-1 -U ))

P -→ 0 as ℓ → +∞. From the tightness of the sequences (m ρℓ (U m ℓ -U )) ℓ≥1 and (m ρℓ (U m ℓ-1 -U )) ℓ≥1 , we get

m ρℓ ψ(θ * , U, U m ℓ -U )(U m ℓ -U ) + ψ(θ * , U, U m ℓ-1 -U )(U m ℓ-1 -U ) P -→ 0, ℓ → +∞.
Therefore using Theorem 2.1 and Lemma 2.1 yield

m ρℓ H(θ * , U m ℓ ) -H(θ * , U m ℓ-1 ) =⇒ D x H(θ * , U )V m .
Moreover, from assumption (HLH) and (HRH) it follows that

sup ℓ≥1 E m ρℓ (H(θ * , U m ℓ ) -H(θ * , U m ℓ-1 )) 2+δ < +∞, which combined with (HDH) imply m ρℓ E[H(θ * , U m ℓ ) -H(θ * , U m ℓ-1 )] → Ẽ[D x H(θ * , U )V m ] m 2ρℓ E[(H(θ * , U m ℓ ) -H(θ * , U m ℓ-1 ))(H(θ * , U m ℓ ) -H(θ * , U m ℓ-1 )) T ] → Ẽ[(D x H(θ * , U )V m ) (D x H(θ * , U )V m ) T ]
as ℓ → +∞. Hence, we have

m 2ρℓ Γ ℓ → Γ * := Ẽ D x H(θ * , U )V m -Ẽ[D x H(θ * , U )V m ] D x H(θ * , U )V m -Ẽ[D x H(θ * , U )V m ] T where for ℓ ≥ 1 Γ ℓ := E k [∆N ℓ k (∆N ℓ k ) T ] = E[(H(θ * , U m ℓ ) -H(θ * , U m ℓ-1 ))(H(θ * , U m ℓ ) -H(θ * , U m ℓ-1 )) T ] -(h m ℓ (θ * ) -h m ℓ-1 (θ * ))(h m ℓ (θ * ) -h m ℓ-1 (θ * )) T .
Consequently, using the following decomposition

1 γ(M ℓ ) m 2ρℓ M ℓ k=1 γ 2 k Π k+1,M ℓ Γ ℓ Π T k+1,M ℓ = 1 γ(M ℓ ) M ℓ k=1 γ 2 k Π k+1,M ℓ Γ * Π T k+1,M ℓ + 1 γ(M ℓ ) M ℓ k=1 γ 2 k Π k+1,M ℓ m 2ρℓ Γ ℓ -Γ * Π T k+1,M ℓ with lim sup ℓ 1 γ(M ℓ ) M ℓ k=1 γ 2 k Π k+1,M ℓ m 2ρℓ Γ ℓ -Γ * Π T k+1,M ℓ ≤ C lim sup ℓ m 2ρℓ Γ ℓ -Γ * = 0,
which is a consequence of Lemma 5.1, we clearly see that

n 1-2ρ 2 -1 m ℓ (1-2ρ) 2 (m 1-2ρ 2 -1) lim ℓ S ℓ = lim p→+∞ 1 γ(p) p k=1 γ 2 k Π k+1,p Γ * Π T k+1,p
if this latter limit exists. The matrix Θ * defined by (2.14) is the (unique) matrix A solution to the Lyapunov equation:

Γ * -(Dh(θ * ) -ζI d )A -A(Dh(θ * ) -ζI d ) T = 0.
Following the lines of the proof of step 3, Lemma 2.3, we have S ℓ

(n 1-2ρ 2 -1) m ℓ (1-2ρ) 2 (m 1-2ρ 2 -1)
a.s.

-→ Θ * as ℓ → +∞. We leave the computational details to the reader. Finally, from Cesàro's Lemma it follows that

L ℓ=1 S ℓ = m 1-2ρ 2 -1 n 1-2ρ 2 -1 L ℓ=1 S ℓ (n 1-2ρ 2 -1) m ℓ (1-2ρ) 2 (m 1-2ρ 2 -1) m ℓ (1-2ρ) 2 a.s.
-→ n→+∞ Θ * .

Numerical Results

In this section we illustrate the results obtained in Section 2.

Computation of quantiles of a one dimensional diffusion process

We first consider the problem of the computation of a quantile at level l ∈ (0, 1) of a one dimensional diffusion process. This quantity, also referred as the Value-at-Risk at level l in the practice of risk management, is the lowest amount not exceeded by X T with probability l, namely q l (X T ) := inf {θ : P(X T ≤ θ) ≥ l} .

To illustrate the results of sections 2.3 and 2.4, we consider a simple geometric Brownian motion

X t = x + t 0 rX s ds + t 0 σX s dW s , t ∈ [0, T ] (4.22)
for which the quantile is explicitly known at any level l. Hence we have ρ = 1/2. The distribution function of X T being increasing, q l (X T ) is the unique solution of the equation h

(θ) = E x [H(θ, X T )] = 0 with H(θ, x) = 1 {x≤θ} -l. A simple computation shows that q l (X T ) = x 0 exp((r -σ 2 /2)T + σ √ T φ -1 (l))
where φ is the distribution function of the standard normal distribution N (0, 1). We associate to the SDE (4.22) its Euler like scheme X n = (X n t ) t∈[0,T ] with time step ∆ = T /n. We use the following values for the parameters: x = 100, r = 0.05, σ = 0.4, T = 1, l = 0.7. The reference Black-Scholes quantile is q 0.7 (X T ) = 119.69.

Remark 4.1. Let us note that when l is close to 0 or 1 (usually less than 0.05 or more than 0.95) the convergence of the considered SA algorithm is slow and chaotic. This is mainly due to the fact that the procedure obtains few significant samples to update the estimate in this rare event situation. One solution is to combine it with a variance reduction algorithm such as an adaptive importance sampling procedure that will generate more samples in the area of interest, see e.g. [START_REF] Bardou | Computing VaR and CVaR using stochastic approximation and adaptive unconstrained importance sampling[END_REF] and [START_REF] Bardou | Recursive computation of value-at-risk and conditional value-at-risk using MC and QMC[END_REF].

In order to illustrate the result of Theorem 2.6, we plot in Figure 1 the behaviors of nh n (θ * ) and n(θ * ,nθ * ) for n = 100, • • • , 500. Actually, h n (θ * ) is approximated by its Monte Carlo estimator and θ * ,n is estimated by θ n M , both estimators being computed with M = 10 8 samples. The variance of the Monte Carlo estimator ranges from 2102.4 for n = 100 to 53012.5 for n = 500. We set γ p = γ 0 /p with γ 0 = 200. We clearly see that nh n (θ * ) and n(θ

Computation of the level of an unknown function

We turn our attention to the computation of the level of the function θ → e -rT E(X Tθ) + (European call option) for which the closed-form formula under the dynamic (4.22) is given by e

-rT E(X T -θ) + = e -rT xφ(d + (x, θ, σ)) -e -rT θφ(d -(x, θ, σ)), (4.23)
where d ± (x, y, z) = log(x/y)/(z √ T ) ± z √ T /2. Therefore, we first fix a value θ * (the target of our procedure) and compute the corresponding level l = E(X Tθ * ) + by (4.23). The values of the parameters x, r, σ, T remain unchanged. We plot in Figure 3 the behaviors of nh n (θ * ) and n(θ * ,nθ * ) for n = 100, • • • , 500. As in the previous example, h n (θ * ) is approximated by its Monte Carlo estimator and θ * ,n is estimated by θ n M , both estimators being computed with M = 10 8 samples. The variance of the Monte Carlo estimator ranges from 9.73 × 10 6 for n = 100 to 9.39 × 10 7 for n = 500. To compare the three methods to approximate the solution to h(θ) = E x [H(θ, X T )] = 0 with H(θ, x) = l -(xθ) + in terms of computational costs, we compute the different estimators, namely θ n γ -1 (1/n 2 ) where (θ n p ) p≥1 is given by (1.3), Θ sr n and Θ ml n for a set of N = 200 values of the target θ * equidistributed on the interval [90, 110] and for different values of n. For each value n and for each method we compute the complexity given by (2.11), (2.15) and (2.16) respectively and the root-mean-squared error which is given by

RMSE = 1 N N k=1 (Θ n k -θ * k ) 2 1/2
where Θ n k = θ n γ -1 (1/n 2 ) , Θ sr n or Θ ml n is the considered estimator. For each given n, we provide a couple (RMSE, Complexity) which is plotted on Figure 6. Let us note that the multi-level SA estimator has been computed for different values of m (ranging from m = 2 to m = 7) and different values of L. We set γ(p) = γ 0 /p, with γ 0 = 2, p ≥ 1, so that β * = 1/2.

2 + L-1 ℓ=1 θ m ℓ M ℓ -θ m ℓ-1 M ℓ
respectively. We set θ n 1/2 0 = θ 1 0 = x for all k ∈ {1, • • • , M } to initialize the procedures. Moreover, by Lemma 5.2, the L 1 (P)-norm of an increment of a SA algorithm is of order γ 0 /p since E|θ n p+1 -

θ n p | ≤ E[|θ n p+1 - θ * ,n | 2 ] 1/2 + E[|θ n p -θ * ,n | 2 ] 1/2 ≤ C(H, γ) γ(p).
Hence, during the first iterations (say M/100 if M denotes the number of samples of the estimator), to ensure that the different procedures do not jump too far ahead in one step, we freeze the value of θ √ n p+1 (respectively θ m ℓ p+1 ) and reset it to the value of the previous step as soon as |θ

√ n p+1 -θ √ n p | ≤ K/ √ p (respectively |θ m ℓ p+1 -θ m ℓ p | ≤ K/ √ p)
, for a pre-specified value of K. This is just an heuristic approach that notably prevents the algorithm from blowing up during the first steps of the procedure. We select K = 5 in the different procedures. Note anyway that this projection-reinitialization step does not lead to additional bias but slightly increases the complexity of each procedures. In our numerical examples, we observe that it only represents around 1-2% of the total complexity. Now let us interpret Figure 6. The curves of the statical romberg SA and the multi-level SA methods are displaced below the curve of the SA method. Therefore, for a given error, the complexity of both methods are much lower than the one of the crude SA. The difference in terms of computational cost becomes more significant as the RMSE is small, which corresponds to large values of n. The difference between the statistical romberg and the multi-level SA method is not significant for small values of n, i.e. for a RMSE between 1 and 0.1. For a RMSE lower than 5.10 -2 , which corresponds to a number of steps n greater than about 600-700, we observe that the multi-level SA procedure becomes much more effective than both methods. For a RMSE fixed around 1 (which corresponds to n = 100 for the SA algorithm and Statiscal Romberg SA), one divides the complexity by a factor of approximately 5 by using the statistical romberg SA. For a RMSE fixed at 10 -1 , the computational cost gain is approximately equal to 10 by using either the statistical romberg SA algorithm or the multi-level SA one. Finally, for a RMSE fixed at 5.5.10 -2 , the complexity gain achieved by using the multi-level SA procedure instead of the statistical romberg one is approximately equal to 5.

The histograms of Fig 4 illustrates Theorems 2.7, 2.9 and 2.11. The distributions of n(θ n γ -1 (1/n 2 )θ * ), n(Θ sr nθ * ) and n(Θ ml nθ * ), obtained with n = 4 4 = 256 and N = 1000 samples, are close to a normal distribution.

Technical results

We provide here some useful technical results that are used repeatedly throughout the paper. When the exact value of a constant is not important we may repeat the same symbol for constants that may change from one line to next.

Lemma 5.1. Let H be a stable d × d matrix and denote by λ min its eigenvalue with the lowest real part. Let (γ n ) n≥1 be a sequence defined by γ n = γ(n), n ≥ 1, where γ is a positive function defined on [0, +∞[ decreasing to zero and such that n≥1 γ(n) = +∞. Let a, b > 0. We assume that γ satisfies one of the following assumptions:

• γ varies regularly with exponent (-c), c ∈ [0, 1), that is for any x > 0, lim t→+∞ γ(tx)/γ(t) = x -c .

• for t ≥ 1, γ(t) = γ 0 /t with bRe(λ min )γ 0 > a. Let (v n ) n≥1 be a non-negative sequence. Then, for some positive constant C, one has lim sup We study now the impact of the step sequence (γ p ) p≥1 on the above estimate. We first assume that γ p = γ 0 /p with bRe(λ min )γ 0 > a. We select λ > 0 such that bRe(λ min )γ 0 > bλγ 0 > a. Then, one has s p = γ 0 log(p) + c 1 + r p , c 1 > 0 and r p → 0 so that a comparison between the series and the integral yields exp(-λbs n ) so that for any x such that 0 < x < 1, since t → γ a (s -1 (t)) is decreasing, we deduce s(n) 0 exp(λbt)γ a (s -1 (t))dt ≤ γ a (s -1 (0))

  where e n = o(1) and we set s N,n := n k=N γ k . From the assumption (1.2), it follows that for N ≥ n 0 lim sup n Z n ≤ C sup k≥N e k and passing to the limit as N goes to infinity it clearly yields lim sup n Z n = 0. Hence, S n a.s.

  For the second term, using assumptions (HLH) and (HSR) we get sup n≥1 E (n ρβ |H(θ * , U n β ) -H(θ * , U )|) 2+δ < +∞. Hence we conclude that sup n≥1 sup k∈[[1,n]] E n ρβ ∆N n β k 2+δ

  20) where Π k,n := n j=k (I dγ j Dh(θ * )), with the convention that Π n+1,n = I d , and ∆N ℓ k

Figure 1 .

 1 Figure 1. On the left: Weak discretization error n → nh n (θ * ). On the right: Implicit discretization error n → n(θ * ,nθ * ), n = 100, • • • , 500.

Figure 2 .

 2 Figure 2. Histogram of n(θ n γ -1 (1/n 2 )θ * ), n = 100, with N = 1000 samples.

Figure 3 .

 3 Figure 3. On the left: Weak discretization error n → nh n (θ * ). On the right: Implicit discretization error n → n(θ * ,nθ * ), n = 100, • • • , 500.

  v k Π k+1,n b ≤ C lim sup n v n , where Π k,n := n j=k (I dγ j H), with the convention Π n+1,n = I d . n2) -θ * ) probability histogram of n.(θ n γ-1(1/n2) -θ * ), n = 256 ml nθ * ) probability histogram of n.(Θ ml nθ * ), n = 256

Figure 4 .

 4 Figure 4. Histograms of n(θ γ -1 (1/n 2 )θ * ), n(Θ sr nθ * ) and n(Θ ml nθ * ) (from left to right), n = 256, with N = 1000 samples.

  some positive constant C (independent of N ) so that we clearly havelim sup n γ -a n z n+1 ≤ C sup k>N v k .

Figure 5 .Figure 6 .

 56 Figure 5. Complexity with respect to RMSE.

Π=

  xs(n) 0 exp(λbt)dt + γ a (s -1 (xs(n))) s(n) xs(n) exp(λbt)dt ≤ γ a (s -1 (0)) λb exp(λbxs(n)) + γ a (s -1 (xs(n))) λb exp(λbs(n)).Proposition 5.1. Assume that the assumptions of Theorem 2.10 are satisfied. Then, for all n ∈ N there exist two sequences(μ n p ) p∈[[0,n]] and (r n p ) p∈[[0,n]] with rn 0 = θ n 0θ 0 -(θ *θ * ,n ) such that ∀p ∈ [[0, n]], z n p = θ n pθ* ,n -(θ pθ * ) = μn p + rn p and satisfying for all n ∈ N, for all p ∈ [[1, n]] |r n p |] < +∞. Proof. Using (3.18), we define the two sequences (μ n p ) p∈[[0,n]] and (r n p ) p∈[[0,n]] by μn p = p k=1γ k Π k+1,p ∆N n k + p k=1 γ k Π k+1,p (Dh(θ * ) -Dh n (θ * ,n ))(θ n k-1θ * ,n ) + p k=1 γ k Π k+1,n (h n (θ * ,n )h n (θ * ) -(H(θ * ,n , (U n ) k+1 ) -H(θ * , (U n ) k+1 )))andrn p = Π 1,p z n 0 + p k=1 γ k Π k+1,p (ζ n k-1ζ k-1 ) + p k=1 γ k Π k+1,p (h n (θ n k )h n (θ * ,n ) -(H(θ n k , (U n ) k+1 ) -H(θ * ,n , (U n ) k+1 ))) + p k=1 γ k Π k+1,p (H(θ k , U k+1 ) -H(θ * , U k+1 ) -(h(θ k )h(θ * ))).We first focus on the sequence (μ n p ) p∈[[0,n]] . Moreover, by the definition of the sequence (∆N n k ) k∈[[1,n]] and the Cauchy-Schwarz inequality we deriveE p k=1 γ k Π k+1,p ∆N n k ≤ C(E|H(θ * , U n ) -H(θ * , U )| 2 ) 1/2 ( p k=1 γ 2 k Π k+1,p 2 ) 1/2 = O(γ 1/2 p n -ρ ).Taking the expectation for the third term and following the lines of the proof of Lemma 2.7, we obtainE p k=1 γ k Π k+1,p (Dh(θ * ) -Dh n (θ * ,n ))(θ n k-1θ * ,n ) ≤ C k+1,p (|θ * ,nθ * | + Dh(θ * ) -Dh n (θ * ) ) = O(γ 1/2 p n -ρ ).Finally we take the square of the L 2 -norm of the last term and use Lemma 5.1 to deriveE p k=1 γ k Π k+1,p (h n (θ * ,n )h n (θ * ) -(H(θ * ,n , (X n T ) k+1 ) -H(θ * , (X n T ) k+1 ))) 2 ≤ |θ *θ * ,n | 2 O(γ p n -2ρ ).We now prove the bound concerning the sequence (r n p ) p∈[[0,n]] . Under the assumption on the step sequence we haveE[|Π 1,p z n 0 |] ≤ Π 1,p (1 + |θ *θ * ,n |) = O(γ p ). k+1,p (ζ n k-1ζ k-1 ) ≤ C p k=1 γ 2 k Π k+1,p = O(γ p ).Concerning the second term, following the lines of the proof of Lemma 2.7 we simply take the square of its L 2 (P)-norm to derive sup n≥1 E p k=1 γ k Π k+1,p (h n (θ n k )h n (θ * ,n ) -(H(θ n k , (X n T ) k+1 ) -H(θ * ,n , (X n T ) k+1 ))) k Π k+1,p (H(θ k , (X T ) k+1 ) -H(θ * , (X T ) k+1 )) -(h(θ k )h(θ * )) 2 = O(γ 2 p ).

  By considering the empirical mean sequence Θsr

	n = θn β M3 + θn M4 -θn β M4 , where ( θn β p ) p∈[[0,M3]] p ) p∈[[0,M4]] are respectively the empirical means of the sequences (θ n β p , θn β and ( θn p ) p∈[[0,M3]] and (θ n p , θ n β p ) p∈[[0,M4]]

  & Polyak averaging principle. It consists in estimating θ * by

	Θsr n = θn β M3 + θn M4 -θn β M4 ,
	where ( θn β

p ) p∈[[0,M3]] and ( θn p , θn β p ) p∈[[0,M4]] are respectively the empirical means of the sequences (θ n β p ) p∈[[0,M3]]

  * ,nθ * ) are stable with respect to n. The histogram of Fig 2 illustrates Theorem 2.7. The distribution of n(θ n γ -1 (1/n 2 )θ

* ), obtained with n = 100 and N = 1000 samples, is close to a normal distribution.

Hence it follows that exp(-λbs(n))

γ a (n)

and since t → γ a (s -1 (t)) varies regular with exponent -ac/(1c), and lim n→+∞

λb .

An argument similar to the previous case concludes the proof.

Lemma 5.2. Let (θ n p ) p≥0 be the procedure defined by (1.3) where θ n 0 is independent of the innovation of the algorithm with sup n≥1 E|θ n 0 | 2 < +∞. Suppose that the assumption of theorem 2.6 are satisfied and that the mean-field function

where θ * ,n is the unique zero of h n satisfying sup n≥1 |θ * ,n | < +∞. Moreover, we assume that γ satisfies one of the following assumptions:

• γ varies regularly with exponent (-c), c ∈ [0, 1), that is for any x > 0, lim t→+∞ γ(tx)/γ(t) = x -c .

• for t ≥ 1, γ(t) = γ 0 /t with 2λγ 0 > 1. Then, for some positive constant C (independent of p and n) one has:

Proof. From the dynamic of (θ n p ) p≥1 , we have

so that taking expectation in the previous equality and using assumptions (2.7) and (5.24), we easily derive

Now a simple induction argument yields

where we set Π k,p := p j=k (1 -2λγ j + Cγ 2 j ) for sake of simplicity. Moreover, computations similar to the proof of Lemma 5.1 imply ∀p ≥ 1, E|θ n pθ * ,n | 2 ≤ Cγ(p). In order to prove the similar bound for the sequence (θ p ) p≥1 we first observe that since (θ p ) p≥1 converges a.s. to θ * there exists a compact set K (which depends on w) such that θ p ∈ K, for p ≥ 0. Then, Remark 2.3 shows that a mean reverting assumption is satisfied also for h on K with the same constant λ. Finally we conclude using similar arguments as those used above.