M Dambrine
email: marc.dambrine@univ-pau.fr

Ch

Dossal

B Puig

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

Stochastic Differential Equations for modeling first order optimization methods

Keywords: Lyapunov functions, rate of convergence, SDEs, optimization, geometrical properties of the objective

published or not. The documents may come

Stochastic Differential Equations for modeling first order optimization methods

Introduction

In the recent literature, continuous time approach to first order minimization of a function F is a fruitful field of research. Indeed under some suitable regularity assumptions the sequence generated by a given optimization scheme may converge when the step size h goes to zero to the solution of an ordinary differential equation (ODE). The most striking result in that direction has been obtained by Su, Boyd and Candes in [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF]: let F : R d → R. The Nesterov scheme

y n = x n + n -1 n + 2 (x n -x n-1 ) (1)
x n+1 = y n -h∇F (y n ), (2)
can be seen as a special and nonstandard discretization of the second order differential equation ẍ(t) + 3 t ẋ(t) + ∇F (x(t)) = 0 with x(0) = x 0 and ẋ(0) = 0.

(

) 3
The study of such ODE, the behavior of the solution enlighten the properties of the sequence generated by the Nesterov scheme.

In the present work, the same question is addressed in the stochastic case, more precisely when the objective F is defined as an expectation: F (x) = E[f (x, .)]. In general, there is no closed form for this expectation and an approximation is used. A common approximation is then an empirical estimator of the type

FN (x) = 1 N N i=1 f (x, ω i ),
where N is the number of samples. The gradient of F is then approximated by the gradient of the previous estimator so that

∇F (x) = ∇ FN (x) + G N ,
where G N is a random error. In that context, iterative methods based on gradient evaluation are affected by this error. The gradient scheme of step size h

x n+1 = x n -h∇F (x n ), becomes y n+1 = y n -h ∇ F (y n ) + G N (n) .
Of course, the size of the sampling may vary with the number n of iterations. Therefore, we will consider algorithms of the type

y n+1 = y n + h (Φ(t n , y n ) + σ(t n )G n ) , (4)
where t n = nh and where Φ and σ are given functions, and the G n are assumed to be independent Gaussian vectors of dimension d with the same variance I d . It is known that the sequence of iterates generated by these algorithms converge when h tends to 0 to the solution of the deterministic ODE:

du(t) = Φ(t, u(t))dt (5)
but it appears that the sequence is more precisely approximated for a given h > 0 by the solution of the following high resolution SDE

du(t) = Φ(t, u(t))dt + √ h σ(t)dB t . (6)
That is why we will study this family of high resolution stochastic differential equation (SDE). Note that the idea was introduced in the deterministic setting in a recent work [START_REF] Shi | Understanding the acceleration phenomenon via high-resolution differential equations[END_REF] by Shi, Su and Jordan. Their idea is to consider an ODE whose coefficients depend on the step size h which is not set to 0 to get a better approximation of the inertial discrete scheme.

Thanks to limiting arguments, the authors proposed the following asymptotic approximation for Nesterov scheme for a µ-strongly convex cost function F :

d dt x v =    v - 3 t v -h D 2 F (x)v -1 + √ h 3 ∇F (x)    , (7)
where D 2 F stands for the Hessian of F , with the initial conditions

x(0) = x 0 and v(0) = -2h∇F (x 0 ) 1 + √ µh .

The SDE [START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF] is not classical is the sense that it depends on a parameter h that can go to zero. Actually classical results on the convergence of discretization schemes of SDE do not directly apply to the convergence of the sequence y n defined in (4) to the solution of ( 6) since the SDE (6) depends itself on the parameter step h. The contribution of the following paper is twofold. First we prove that the trajectory of the sequence (y n ) defined in ( 4) is better approximated by the family of SDE [START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF], parameterized by h than by the solution of the classical ODE [START_REF] Aujol | Optimal rate of convergence of an ODE associated to the fast gradient descent schemes for b > 0[END_REF], see Proposition 1. The main new feature is the fact that we consider a time dependant diffusion coefficient σ and not a trajectory dependant diffusion as in [START_REF] Li | Stochastic modified equations and adaptive stochastic gradient algorithms[END_REF]. We give strong convergence (in the sense that the mean of the error goes to 0) results with an additive noise while to our best knowledge only weak convergence can be found in the literature (see [START_REF] Li | Stochastic modified equations and adaptive stochastic gradient algorithms[END_REF]). The purpose of this first analysis is to motivate the study of these high resolution SDE to understand the behavior of the sequence generated by some stochastic algorithms.

Secondly, we propose new convergence rates of the solution of two SDEs, especially a high resolution SDE associated to the Nesterov scheme using some Lyapunov analysis. More precisely we provide convergence rate on the expectation of F (X t )-F (X * ) when F is convex, see Theorem 3 and when F satisfies various geometrical properties, see for example Theorem 4.

The paper is organized as follows: in the second part we show that high resolution SDE provide better approximations of the scheme (4) than the classical ODE approach giving strong convergence results. In the third part we provide first a general analysis allowing to extend some classical Lyapunov analysis for ODEs to SDEs. We illustrate this approach recovering known bounds on the stochastic gradient flow equation. Then in Part 3.2 three new convergence rates are given for the trajectory of an high resolution SDE associated to the Nesterov scheme depending on the geometry of the function to minimize.

On the error of approximation by ODE and SDE

Let (Ω, F, (F t ) t 0 , P) be a complete filtered probability space. We denote by (B t ) t 0 a standard d-dimensional Brownian motion defined on this space, considering that the filtration (F t ) t 0 is in fact the natural filtration of (B t ) t 0 .

Let L 2 (Ω) be the usual space of random variables whose square is integrable with respect to the measure P and L ∞ (0, T, L 2 (Ω)) the usual Bochner space.

For a given h > 0, define the following discrete dynamical system

Y n+1 = Y n + h Φ(t n , Y n ) + h σ(t n )G n , (8)
where G n are independent Gaussian vectors with the same variance I d . Consider a Brownian motion B t in R d and set t n = nh. Noticing that √ hG n has the same distribution that B t n+1 -B tn , we can rewrite the system (8) as

X n+1 = X n + h Φ(t n , X n ) + √ h σ(t n )(B t n+1 -B tn ). (9)
Observe that such a scheme is similar to an Euler-Maruyama scheme with an additional √ h factor that comes from the h factor in [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF].

Proposition 1 states that on a fixed interval [0, T ], the limit problem when the time step h goes to 0 is the deterministic ODE w = Φ(t, w) and that the error measured in L ∞ (0, T, L 2 (Ω)) is proportional to √ h. But the main contribution of Proposition 1 is actually to state that the trajectory X n is better approximated by the SDE:

du(t) = Φ(t, u(t))dt + √ h σ(t)dB t , since the error measured in L ∞ (0, T, L 2 (Ω)), is proportional to h instead of √ h. Proposition 1. Let Φ : R×R d → R d be a C 2 function. Let σ : R → R be a bounded integrable function. Let u 0 be a given vector in R d , h ∈ [0, 1]
and T be non negative real number. Fix N an integer and set T = N h. Define t n = nh, 0 n N and consider the sequence X n defined by recursion

X n+1 = X n + h Φ(t n , X n ) + √ h σ(t n )(B t n+1 -B tn ),
starting with X 0 = u 0 . Let w denotes the solution of the deterministic Cauchy problem w = Φ(t, w) with w(0) = u 0 , and let u be the solution of the stochastic differential equation

du(t) = Φ(t, u(t))dt + √ hσ(t)dB t with u(0) = u 0 .
There exist non negative constants C 1 and C 2 independent of h such that

sup 0 n N w(t n ) -X n L 2 (Ω) C 1 √ h. ( 10
) sup 0 n N u(t n ) -X n L 2 (Ω) C 2 h. ( 11
)
The proof of this proposition is postponed to Appendix A. Notice that these results can be adapted in the case of a variable time step: h is then the supremum of the time steps. Unfortunately it turns out that the Nesterov scheme can not be written using the formulation (8) because the gradient of F (or the function Φ) is evaluated at a point that is not Y n but slightly shifted. Nevertheless Su, Boyd and Candès in [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF] proved that a Lyapunov analysis of the ODE associated to Nesterov scheme may provide an efficient Lyapunov analysis of the discrete scheme. That is why we will consider the SDE associated to this second order ODE, expecting that the analysis will provide tools to analyse the stochastic discrete scheme. Such an analysis would be a natural development of the present work.

Convergence rates for stochastic gradient flow and Nesterov ODE

In this section we study the properties of trajectories solution of SDEs of the form:

dY t = Φ (t, Y t ) dt + √ hσ(t)M dB t , (12)
where σ : R → R is a diffusion term, Φ : R × R m → R m is a given smooth function, M a real matrix of size m × d and h > 0. Throughout the paper, we assume that, for any given initial conditions y 0 ∈ R m , the Cauchy problem associated with the SDE [START_REF] Garrigos | Convergence of the forward-backward algorithm: Beyond the worst case with the help of geometry[END_REF], admits a unique global solution satisfying Y 0 = y 0 , see [START_REF]Stochastic Differential Equations: Introduction with Applications[END_REF]Theorem 5.2.1]. For example since σ does not depend on Y t , the existence and the uniqueness is ensured if the function Φ is Lipschitz with respect to the second variable.

Our main contribution in this section is to prove that the Lyapunov analysis can be extended from ODEs to SDEs providing new decay rates on the expectation of the values F -F * along the trajectories solution of the SDE [START_REF] Garrigos | Convergence of the forward-backward algorithm: Beyond the worst case with the help of geometry[END_REF]. It turns out that our results make assumptions on integrability (in time) of the noise level in the spirit of the perturbation analysis led in the deterministic case by Sebbouh, Dossal and Rondepierre in [START_REF] Sebbouh | Convergence rates of damped inertial dynamics under geometric conditions and perturbations[END_REF].

A key tool in our analysis is the following proposition ensuring that a Lyapunov function associated to an ODE may provide, not necessarily a non increasing function but at least a bounded function in expectation for the stochastic perturbation of an ODE: Proposition 2. Let t 0 0. Let Φ : R × R m → R m be a C 2 function and M a given matrix in R m×d . Consider the stochastic differential equation:

dY t = Φ (t, Y t ) dt + σ(t)M dB t ( 13
)
where σ : R → R denotes the noise coefficient. Let J : R × R m → R be a (time dependant) Lyapunov function for the associated deterministic ODE: Ẏ = Φ(t, Y ) in the sense that J satisfies:

∂ t J (t, Y t ) + ∇J (t, Y t ) • Φ (t, Y t ) 0
for all t t 0 . Then the process J (t) defined by: J (t) = J (t, Y t ), satisfies:

∀t t 0 , E [J (t)] J (t 0 ) + 1 2 t t 0 σ 2 (τ )E T r D 2 22 J (τ, Y τ ) M M dτ,
where the notation D 2 22 denotes the second order derivative with respect to the space variable Y .

Proof. Applying the Itô's formula we get

dJ (t) = [∂ t J (t, Y t ) + ∇J (t, Y t ) • Φ(t, Y t )] dt + σ(t)∇J (t, Y t ) • M dB t + σ(t) 2 2 T r D 2 22 J (t, Y t ) M M dt.
Integrating on [t 0 , t], we get

J (t) J (t 0 ) + t t 0 σ(τ )∇J (τ, Y τ ) • M dB τ + σ(τ ) 2 2 T r D 2 22 J (τ, Y τ ) M M dτ.
Taking the expectation, we get the announced inequality.

Our methodology is first illustrated on the family of SDEs associated to stochastic gradient descent methods which are widely studied in the literature. Let us mention in particular the results of Mertikopoulos and Staudigl who prove almost sure convergence of trajectories to a minimizer under the assumption that the noise level decreases at least like 1/ √ ln t [18, Theorem 4.2]. We then apply the same methodology to the family of SDEs associated to the perturbed Nesterov scheme for the minimization of a given convex function F .

Convergence rate of the stochastic gradient flow

In this paragraph, we consider the stochastic differential equation classically associated to the stochastic gradient descent:

dX t = -∇F (X t )dt + √ hσ(t)dB t , (14)
where F : R d → R denotes the objective function and is assumed to be convex of class C 2 . Theorem 1 provides some results for convex functions and Theorem 2 provides more accurate bounds when F is µ-strongly convex. Then there exists a constant C ς > 0 (affine in h) such that the process solution of (14) with the initial condition X t 0 = x 0 , satisfies:

∀t t 0 , E[F (X t ) -F * ] C ς t ς-1 (15)
and for any β > 0:

∀t t 0 , P F (X t ) -F * 1 t β C ς t ς+β-1 . (16)
Before proving Theorem 1, let us make some comments. First, note that the coefficient ς measures the intensity of the noise. The higher the noise is, the lower the convergence rate becomes. Consider for example the case when σ(t) = t -p for some p > 0. In that case we have: 1) .

t t 0 sσ(s) 2 ds = 1 2(p -1) t -2(p-1) 0 -t -2(p-
A straightforward computation shows that for p > 1, we can set ς = 0 which implies a convergence rate in expectation in 1 t . For p ∈ [1/2, 1[ the parameter ς can be set to ς = -2p+2 and the convergence rate in expectation is in 1 t 2p-1 where 0 < 2p -1 < 1. The coefficient β is chosen to control the convergence rate in probability. It can be interpreted as a trade-off between the decrease on the values F (X t ) -F * and the probability that the bound ( 16) is satisfied. A natural choice for β is β * = 1 -ς which ensures that the two terms in the convergence error in ( 16) are of the same order but in that case, the upper bound in ( 16) is constant and so does not converge to 0. In order to have a decreasing upper bound, β should be chosen as 1 -ς -for > 0 so that the inequality ( 16) can be reformulated in terms of as:

∀t t 0 , P F (X t ) -F * t (ς-1)+ Cς t -
for any ∈ (0, 1 -ς).

Proof of Theorem 1. Let us introduce the Lyapunov energy:

J(t, x) = t(F (x) -F (x * )) + 1 2 x -x * 2
where x * ∈ arg min F . Let X t be a trajectory solution of ( 14) with the initial condition X t 0 = X 0 and J (t) = J(t, X t ). Applying Proposition 2 with M = √ hI d , we have:

∀t t 0 , E [J (t)] J (t 0 ) + h 2 t t 0 σ 2 (τ )E T r D 2 22 J (τ, X τ ) dτ.
The Itô's calculus gives: T r D 2 22 J (t, x) = t∆F (x) + m. Assuming now that F has a uniformly bounded Laplacian, we deduce that there exists a constant A > 0 such that:

∀t t 0 , E [J (t)] J (t 0 ) + Ah t t 0 τ σ 2 (τ )dτ.
Hence using the integrability condition (D 1,ς ):

∀t t 0 , tE [F (X t ) -F * ] E [J (t)] J (t 0 ) + Ah t t 0 τ σ 2 (τ )dτ J (t 0 ) + AhCt ς J (t 0 )t -ς 0 + AhC t ς
Applying Markov inequality, we finally deduce that:

P F (X t ) -F * 1 t β t β E[F (X t ) -F * ] J (t 0 )t -ς 0 + AhC t ς+β-1 .

Convergence rates for µ-strongly convex functions

Let us now consider the class of µ-strongly differentiable convex functions i.e. the class of convex differentiable functions satisfying for any x, y in R d :

∇F (x) -∇F (y), x -y µ x -y 2 .
In the deterministic framework the convergence for this class of function is exponential, see e.g. [START_REF] Garrigos | Convergence of the forward-backward algorithm: Beyond the worst case with the help of geometry[END_REF]. This result can be extended to the stochastic case using a Lyapunov approach:

Theorem 2. Let F : R d → R be a C 2 µ-strongly convex function having a minimizer x * ∈ arg min F and t 0 0. Then the process solution of (14) with

X t 0 = x 0 satisfies ∀t t 0 , E[ X t -x * 2 ] e 2µt 0 x 0 -x * 2 + hd t t 0 e 2µs σ 2 (s) ds e -2µt .
Proof. The key quantities in this study are E(x) = x -x * 2 and E(t) = E(X t ). Applying Itô's formula to the product e 2µt E(t), we get:

d e 2µt E(t) = [2µE(t) -2 ∇F (X t ), X t -x * ] e 2µt dt + hdσ 2 (t)e 2µt dt +2 √ hσ(t)e 2µt X t -X * , dB t
that is in integral form:

∀t t 0 , e 2µt E(t) -e 2µt 0 E(t 0 ) = t t 0 -2 ∇F (X s ), X s -x * ) + 2µE(s) + dhσ 2 (s) e 2µs ds +2 √ h t t 0 σ(s)e 2µs X s -X * , dB s .
Using now the strong convexity of the objective function F , we get:

∀t t 0 , e 2µt E(t) e 2µt 0 E(t 0 ) + 2 √ h t t 0 e 2µs σ(s) X s -X * , dB s + dh t t 0 e 2µs σ 2 (s)ds,
and thus the expected inequality:

e 2µt E[E(t)] e 2µt 0 E(x 0 ) + dh t t 0 e 2µs σ 2 (s) ds.
A natural question is then under what condition on the noise the convergence is still exponential with the same rate as in the deterministic case. Theorem 2 imposes that:

+∞ t 0 σ 2 (s)e 2µs ds
is finite to obtain a non degraded rate of convergence. Indeed, keeping the exponential rate of convergence of the deterministic case seems out of reach in practical application.

Consider now the particular case when σ is assumed to be constant. We then have:

t t 0 e -2µ(t-s) σ 2 ds = σ 2 e -2µt t t 0 e 2µs ds = σ 2 (1 -e -2µ(t-t 0 ) ) 2µ ,
so that Theorem 2 gives:

E[E(t)] e 2µt 0 x 0 -x * 2 e -2µt + dσ 2 h 2µ .
In other words, the process reaches with an exponential rate (the one of the deterministic dynamic) a ball whose radius depends on the time step h and on the diffusion coefficient σ. This is a well-known property of the stochastic gradient (see [START_REF] Bottou | Optimization methods for large-scale machine learning[END_REF] for a review and [START_REF] Laborde | Nesterov's method with decreasing learning rate leads to accelerated stochastic gradient descent[END_REF] for an accelerated version).

Convergence rate of a SDE associated to the Nesterov scheme

In 1983, Nesterov [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o( 1 k 2 )[END_REF] proposes a new inertial optimisation scheme (1), with α = 3, to minimize a convex differentiable function F . The sequence (x n ) n generated by this scheme satisfies

F (x n ) -F (x * ) = O 1 n 2 .
Moreover, Nesterov proved that this rate is optimal on the class of convex functions among first order method.

Since the work of Boyd, Candes and Su [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF], it is known that the Nesterov scheme corresponds in the limit h → 0 to the second order differential equation

ẍ(t) + α t ẋ(t) + ∇F (x(t)) = 0, (17)
with initial conditions x(0) = x 0 and ẋ(0) = 0 and where the friction coefficient α is set to 3.

In [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF], the authors prove that the solution of this ODE satisfies

F (x(t)) -F (x * ) = O 1 t 2
when α 3. Note that this rate can be improved under geometrical conditions such as strong convexity or growth conditions, see for example [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF][START_REF] Attouch | Inertial forward-backward algorithms with perturbations: Application to tikhonov regularization[END_REF][START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF]. The purpose of the following analysis is to extend these former results to the continuous stochastic setting. The second order ODE [START_REF] Lord | An introduction to computational stochastic PDEs[END_REF] in R d is equivalent to the following first order system in the phase space

d dt x(t) v(t) = v(t) -α t v(t) -∇F (x(t)) . (18)
The corresponding stochastic differential equation is then

d X t V t = V t -α t V t -∇F (X t )) dt + √ h σ(t)M dB t , ( 19
)
where M is the matrix with m = 2d rows and d columns

M = 0 d I d
and (B t ) t 0 a standard d-dimensional Brownian motion. Observe that the initial speed v(0) = 0 is mandatory in Nesterov scheme to absorb the singular term. In order to avoid this difficulty that is rather artificial for deriving an asymptotic behavior at t → +∞, we choose to translate the origin of time in order to start at t 0 > 0 so that we consider Equation ( 19) for times t t 0 with the deterministic initial condition x(t 0 ) = x 0 and v(t 0 ) = 0.

Convergence rate for the class of convex functions

Let us first consider the general class of convex functions. Our main result given by Theorem 3, establishes new rates of convergence in expectation and probability under some integrability conditions on the noise: Theorem 3. Let F : R d → R be a C 2 convex function and σ : R → R the noise level. Assume that σ satisfies the integrability condition: there exist ς ∈ [0, 2) and C > 0 such that

(D 2,ς ) ∀t t 0 , t t 0 s 2 σ 2 (s)ds Ct ς .
Then there exists a real constant C ς > 0 such that the process solution of (19) with α

3 satisfies ∀t t 0 , E[F (X t ) -F * ] C ς t ς-2 .
Moreover there exists another real constant C ς > 0 such that for any β > 0:

∀t t 0 , P F (X t ) -F * 1 t β C ς t 2(ς+β-2) . (20)
Before proving this result, let us make some comments. As for the gradient flow the parameter ς measures the intensity of the noise. Consider again the case where σ(t) = t -p for some p > 0. In that case, we have:

t t 0 s 2 σ(s) 2 ds = 1 2p -3 t -2p+3 0 -t -2p+3 .
Thus for any p > 3 2 , we can set: ς = 0 which implies a convergence rate in expectation in 1 t 2 . For p 3 2 , then we can choose:

ς = -2p + 3. Consequently if p ∈] 1 2 , 3 2 ] then the convergence rate in expectation is in 1 t 2p-1 .
We can thus observe that the convergence rates obtained for the stochasticgradient flow (see Theorem 1) and the one obtained for the Nesterov stochastic differential equation ( 19) coincide when p ∈] 1 2 , 1]. In other words, using the Nesterov SDE presents no interest when the diffusion coefficient σ decreases slowly since the stochastic gradient flow provides the same rate of convergence under less demanding integrability conditions on the noise.

Besides, when p ∈ [1, 3 2 ], the rate of convergence for the gradient flow saturates to its deterministic value 1 while the rate for the Nesterov SDE continues to increase with p until reaching the deterministic value 2 when p = 3 2 . Thus in that case the Nesterov SDE provides a better convergence rate on the values F (X t ) -F * than the stochastic gradient.

Finally, as for the gradient flow, the coefficient β is chosen to control the convergence rate in probability. It expresses a trade-off between the the decrease on the values F (X t ) -F * and the probability that the bound (4) is satisfied. A natural choice for β is β * = 2 -ς so that the two terms in the convergence error are of the same order. However, it that case, the upper bound does not converge to 0. In order to have a decreasing upper bound, the parameter β should be chosen as 2 -ς -for some > 0 so that the inequality (20) can be reformulated in terms of as:

P F (X t ) -F * t (ς-2)+ C ς t -2 .
for any ∈ (0, 2 -ς).

Proof of Theorem 3. Let us introduce the following energy function:

E(t, (x, v)) = t 2 (F (x) -F * ) + 1 2 (α -1)(x -x * ) + tv 2 (21)
which is a Lyapunov function as proved in [5, Proposition 1], and:

E(t) = E(t, (X t , V t )). An elementary computation provides T r D 2 22 E (t, (x, v)) M M = ∆ v E(t, x, v) = t 2 d.
Applying Proposition 2 with a diffusion term in √ hσ(t), provides an upper bound on the expectation of the Lyapunov function evaluated on the random trajectory starting from (x 0 , 0) at time t = t 0 :

∀t t 0 , E[E(t)] E(t 0 ) + hd 2 t t 0 s 2 σ 2 (s)ds, (22)
and thus an upper bound for the expectation of the residual:

∀t t 0 , E[F (X t ) -F * ] 1 t 2 E(t 0 ) + hd 2 t t 0 s 2 σ 2 (s)ds .
Using the integrability condition (D 2,ς ), we then deduce that there exists a constant C ς > 0 such that:

∀t t 0 , E[F (X t ) -F * ] C ς t ς-2 .
Observe now that the square of a Lyapunov function is still a Lyapunov function so that we can apply Proposition 2 to

E 2 to dominate E[E 2 ]. We first compute Tr D 2 22 E(t, (x, v)) 2 M M = ∆ v (E(t, x, v) 2 ) = 2 E(t, x, v)∆ v E(t, x, v) + ∇ v E(t, x, v) 2
where:

∇ v E(t, x, v) = t ((α -1)(x -x * ) + tv), hence: ∇ v E(t, x, v) 2 = t 2 (α -1)(x -x * ) + tv 2 2t 2 E(t, x, v) so that 0 ∆ v (E(t, x, v) 2 ) 2t 2 (d + 2) E(t, x, v).
Remembering that [START_REF] Sebbouh | Convergence rates of damped inertial dynamics under geometric conditions and perturbations[END_REF] still holds, we deduce that there is a constant A > 0 such that

E[∆ v (E 2 (t))] At 2+ς .
Applying Proposition 2 it follows that:

∀t t 0 , E[E 2 (t)] E(t 0 ) 2 + A 2 t t 0 s 2+ς σ 2 (s)ds E(t 0 ) 2 + A 2 t ς t t 0 s 2 σ 2 (s)ds.
Using now the integrability condition (D 2,ς ), we deduce that there exists a constant Cς > 0 such that for all t t 0 , we have:

E[E 2 (t)] C ς t 2ς .
After expanding E 2 , we obtain the crude upper bound on the expectation of the square of the residual:

∀t t 0 , t 4 E[(F (X t ) -F * ) 2 ] E[E 2 (t)] Cς t 2ς .
Applying Markov inequality, we finally get:

P F (X t ) -F * 1 t β t 2β E[(F (X t ) -F * ) 2 ] Cς t 2(ς+β-2) .

Convergence rates for convex functions under flatness and sharpness assumptions

Nesterov proved in [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o( 1 k 2 )[END_REF] that the O 1 t 2 rate achieved by its acceleration scheme is optimal in some sense on the set of convex functions. Nevertheless better rates can be achieved if more assumptions are made on the function F to minimize. In [START_REF] Apidopoulos | Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions[END_REF] authors show that this rate actually depends on geometric assumptions on F and on the parameter α of the numerical scheme. This parameter α, in the associated ODE and SDE is a friction parameter. Indeed the solution of ( 17) can be seen as the trajectory of a mobile (a ball in the seminal work of Polyak) directed by a potential slow down by a vanishing friction whose intensity is defined by α.

In his seminal work, Polyak [START_REF] Polyak | Some methods of speeding up the convergence of iteration methods[END_REF] considered a constant friction term and quadratic geometries for F and observed that the optimal friction is 2 √ µ where µ is the minimum eigenvalue of the Hessian of F . If α is smaller than this optimal value, some oscillations may slow down the decay rate, if α is higher, the too large friction slow down the mobile. Hence the optimal friction parameter highly depends on the geometry of F . In [START_REF] Aujol | Optimal rate of convergence of an ODE associated to the fast gradient descent schemes for b > 0[END_REF] Aujol et al. explain how the friction parameter can be chosen for the Nesterov acceleration scheme to optimize the decay of F (X t )-F * depending on geometrical hypotheses on F , more precisely: growth and flatness conditions of F . In this section, these former results are extended to the SDE associated to Nesterov.

Let us consider the subclass of convex functions satisfying both a flatness and a growth condition in the neighborhood of their minimizers: Definition 1 (Growth condition G r ). Let F : R d → R ∪ {+∞} be a differentiable convex function such that argmin F = ∅. The function F is said to satisfy a global growth condition G r for some exponent r 1 and some real constant K r > 0 if:

∀x ∈ R d , K r 2 d(x, argmin F ) r F (x) -F * .
Historically, the growth condition G r is also called r-conditioning [START_REF] Garrigos | Convergence of the forward-backward algorithm: Beyond the worst case with the help of geometry[END_REF] or Hölderian error bounds [START_REF] Bolte | From error bounds to the complexity of first-order descent methods for convex functions[END_REF], and is closely related to the Lojasiewicz inequality [START_REF] Lojasiewicz | Une propriété topologique des sous-ensembles analytiques réels[END_REF][START_REF] Lojasiewicz | Sur la géométrie semi-et sous-analytique[END_REF], a key tool in the mathematical analysis of continuous and discrete dynamical systems [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF][START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF]. Note that in the convex setting, the growth condition G r is equivalent to a global version of the Lojasiewicz inequality, with exponent θ = 1 -1 r ∈ (0, 1] [2, 12]. The growth condition G r can be seen as a sharpness assumption on the function F characterizing functions behaving at least as • r in the neighborhood of their minimizers. Observe that G r implies the growth condition G r for all r > r 1.

Definition 2 (Flatness condition F γ ). Let γ 1. The function F is said to satisfy the hypothesis F γ if for any minimizer x * ∈ argmin F , we have:

∀x ∈ R d , F (x) -F * 1 γ ∇F (x), x -x * .
The hypothesis F γ is a mild assumption, requesting slightly more than the convexity of F in the neighborhood of its minimizers. Any convex function automatically satisfies F 1 and any differentiable function F for which (F -F * ) 1 γ is convex for some γ 1, satisfies F γ .

In [START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF], the authors prove that if F satisfies the condition F γ for some γ 1 then for any minimizer x * there exist M > 0 and η > 0 such that:

∀x ∈ B(x * , η), F (x) -F (x * ) M x -x * γ . ( 23
)
In other words, the hypothesis F γ with γ 1, can be interpreted as a flatness condition: it ensures that the function F is sufficiently flat (at least as flat as x → x γ ) in the neighborhood of its minimizers. We refer the interested reader to [START_REF] Cabot | On the long time behavior of second order differential equations with asymptotically small dissipation[END_REF], [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF], [START_REF] Aujol | Optimal rate of convergence of an ODE associated to the fast gradient descent schemes for b > 0[END_REF] or [START_REF] Aujol | Optimal convergence rates for Nesterov acceleration[END_REF] for more details.

Let us first consider the subclass of convex functions with a "sharp" geometry near its set of minimizers, i.e. satisfying a quadratic growth condition G 2 combined with a flatness assumption. Theorem 4 gives conditions on the friction parameter and on the noise to take advantage of the geometry assumptions made on F to improve the O 1 t 2 decay rate of Theorem 3: Theorem 4. Let F : R d → R be a C 2 convex differentiable function admitting a unique minimizer x * , and F * = inf F . Additionally assume that F satisfies both a global quadratic growth condition G 2 and some flatness assumption F γ for some γ ∈ [START_REF] Apidopoulos | Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions[END_REF][START_REF] Attouch | Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-l ojasiewicz inequality[END_REF].

Let t 0 > 0. Let (X t , V t ) be any solution of the SDE [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o( 1 k 2 )[END_REF] with (X t 0 , V t 0 ) = (x 0 , v 0 ). Assume that the noise level σ satisfies the integrability condition: there exist C > 0 and ς ∈ [0, 2) such that

(D q,ς ) ∀t > 0, t t 0 s q σ 2 (s)ds Ct ς with q = 2αγ γ + 2 .
If α > 1 + 2 γ then the process solution of (19) satisfies:

∀t t c , E[F (X t ) -F * ] 2 t q-ς c 1 + 2α t 0 (γ + 2) √ K 2 2 E M (t 0 ) + d 2 C ς e 2-γ γ+2 α t p+2-ς
where:

t c = max(t 0 , 2α √ γ (γ+2) √ K 2
) and E M (t) = F (X t ) -F * + 1 2 V t 2 denotes the mechanical energy at time t. Moreover, for any β > 0,

P F (X t ) -F * 1 t β 2 t q-ς c 1 + 2α t 0 (γ + 2) √ K 2 2 E M (t 0 ) + d 2 C ς e 2-γ γ+2 α t q-ς-β .
First, observe that the convergence rate q = 2αγ γ+2 reached for ς = 0, is actually larger than 2 when α 3 and γ 1. The fact that the decay rate q = 2αγ γ+2 is a growing function of α may be surprising and raises to questions: is it possible to get an arbitrary large decay rate ? Would it be better to choose a very large α ?

The answer to the first question is : yes we can achieve arbitrary large decay rate but the price to pay is twofold:

1. The integrability on the noise is more restrictive for large α.

The term

q √ K 2 γ q-ς (1 + 1 √ γ ) 2 E M (t 0 )t -ς 0 + C d 2 e 2-γ γ+2 α
is an increasing function of α. It follows that for a given t, the optimal choice for α is not to take α as large as possible.

Proof of Theorem 4. Our analysis relies on the same energy H introduced by Su, Boyd and Candes [START_REF] Su | A differential equation for modeling Nesterov's accelerated gradient method: theory and insights[END_REF], Attouch, Chbani, Peypouquet and Redont [START_REF] Attouch | Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity[END_REF] and Aujol, Dossal [START_REF] Aujol | Optimal rate of convergence of an ODE associated to the fast gradient descent schemes for b > 0[END_REF]:

H(t, (x, v)) = t p E(t, (x, v)) (24)
where

E(t, (x, v)) = t 2 (F (x) -F * ) + 1 2 λ(x -x * ) + tv 2 + ξ 2 x -x * 2 ,
and x * is a minimizer of F . Note that the energy H is not a Lyapunov energy anymore since it is not decreasing along the trajectories of the considered system, but we still have a differential inequation enabling the control on the values. Following the computations detailed in [22, Proof of Theorem 3.1] and applying the Itô's calculus, we have:

dE(t, Y t ) (2 -λγ)t (F (X t ) -F * ) dt + [ξ -λ(λ + 1 -α)] X t -x * , V t dt +(λ + 1 -α) 1 t λ(X t -x * ) + tV t 2 dt - λ 2 t (λ + 1 -α) X t -x * 2 dt + d 2 t 2 σ(t) 2 dt + tσ(t) λ(X t -x * ) + tV t , dB t .
Choosing now: ξ = λ(λ + 1 -α), we then get:

dE(t, Y t ) (2 -λγ)t (F (X t ) -F * ) dt + (λ + 1 -α) 1 t λ(X t -x * ) + tV t 2 dt - λ 2 t (λ + 1 -α) X t -x * 2 dt + d 2 t 2 σ(t) 2 dt + tσ(t) λ(X t -x * ) + tV t , dB t
Introducing the energy H(t, Y t ) = t p E(t, Y t ) we then obtain:

dH(t, Y t ) = t p dE(t, Y t ) + pt p-1 E(t, Y t ) t p (2 -λγ + p)t (F (X t ) -F * ) dt + 2λ + 2 -2α + p 2t λ(X t -x * ) + tV t 2 dt + λ 2t (λ + 1 -α)(p -2λ) X t -x * 2 + tσ(t) λ(X t -x * ) + tV t , dB t + d 2 t 2 σ(t) 2 dt
As in [22, Proof of Theorem 3.1], we choose:

λ = 2α γ + 2 , p = 2αγ γ + 2 -2 (25)
so that: ξ = 2α (γ+2) 2 (2 + γ(1 -α)) and:

dH(t, Y t ) t p ξ 2t (p -2λ) X t -x * 2 + tσ(t) λ(X t -x * ) + tV t , dB t + d 2 t 2 σ(t) 2 dt (26) Let A = ξ(p -2λ).
With our choice of parameters, we have:

A = 2ξ γ+2 ((γ -2)α -(γ + 2)). Assuming α > 1 + 2
γ and γ 2, we necessarily have: ξ < 0, and thus A > 0. Consequently the energy E is not a sum of non-negative terms and we need an additional growth condition G 2 to bound the term X t -x * 2 as done in [START_REF] Sebbouh | Convergence rates of damped inertial dynamics under geometric conditions and perturbations[END_REF].

Assuming that F satisfies some quadratic growth condition G 2 and has a unique minimizer, there exists K 2 > 0 such that:

∀t t 0 , X t -x * 2 2 K 2 (F (X t ) -F * ). ( 27
)
Hence:

∀t t 0 , E(t, Y t ) t 2 (1 + ξ K 2 t 2 ) (F (X t ) -F * ) . ( 28
)
Observe now that since ξ = λ(λ + 1 -α) < 0, we get:

|ξ| = 2α γ + 2 αγ γ + 2 -1 2α 2 γ (γ + 2) 2 . Let t c = max t 0 , 2α √ γ (γ+2) √ K 2
. We thus have:

1 + ξ K 2 t 2 1
2 for all t t c . Hence:

∀t t c , E(t, Y t ) t 2 2 (F (X t ) -F * ) . ( 29
)
Combining ( 26), ( 27) and ( 29), we get in expectation:

∀t t c , dH(t, Y t ) 2A K 2 t 3 H(t, Y t ) + t p+1 σ(t) λ(X t -x * ) + tV t , dB t + d 2 t p+2 σ(t) 2 dt
Integrating now between t c and t, we get:

∀t t c , E[H(t, Y t )] E[H(t c , Y tc )] + 2A K 2 t tc E[H(s, Y s )] s 3 ds + d 2 t tc s p+2 σ(s) 2 ds E[H(t c , Y tc )] + 2A K 2 t tc E[H(s, Y s )] s 3 ds + C ς d 2 t ς
According to the Grönwall lemma, we then have:

∀t t c , E[H(t, Y t )] E[H(t c , Y tc )] + d 2 t tc s p+2 σ(s) 2 ds exp( t tc 2A K 2 s 3 ds) E[H(t c , Y tc )] + d 2 C ς t ς exp( A K 2 t 2 c
).

Let us now prove that the energy H(t c , Y tc ) is uniformly bounded by the mechanical energy

E M (t) = F (X t ) -F * + 1 2 V t 2 at time t c : E(t c , Y tc ) = t 2 c (F (X tc ) -F * ) + 1 2 λ(X tc -x * ) + t c V tc 2 + ξ 2 X tc -x * 2 = t 2 c E M (t c ) + λ 2 2 X tc -x * 2 + λt c X tc -x * , V tc + ξ 2 X tc -x * 2 t 2 c E M (t c ) + λ 2 2 X tc -x * 2 + λt c X tc -x * , V tc .
Using the quadratic growth condition G 2 and the following inequality:

2| X tc -x * , v tc | K 2 X tc -x * 2 + 1 √ K 2 V tc 2 , (30)
we finally get:

E(t c , Y tc ) t 2 c + 2 λt c √ K 2 + λ 2 K 2 E M (t c ) = t c + λ √ K 2 2 E M (t c ).
Hence:

∀t t c , E[H(t, Y t )] t p c t c + λ √ K 2 2 E[E M (t c )] + d 2 C ς t ς exp( A K 2 t 2 c ) t p+2 c 1 + λ t c √ K 2 2 E[E M (t c )] + d 2 C ς t ς exp( 2 -γ γ + 2 α)
since by construction:

A K 2 t 2 c A 2|ξ| = 2-γ γ+2 α.
Observe now that the mean of the mechanical energy is non-increasing. Indeed:

∀t t 0 , E M (t) = E M (t 0 ) + t t 0 dE M (s)ds = E M (t 0 ) + t t 0 - α s V s 2 ds + σ(s) V s , dB s Hence: ∀t t 0 , E[E M (t)] E M (t 0
) and:

∀t t c , E[H(t, Y t )] t p+2 c 1 + λ t c √ K 2 2 E M (t 0 ) + d 2 C ς t ς exp( 2 -γ γ + 2 α) t p+2 c 1 + λ t 0 √ K 2 2 E M (t 0 ) + d 2 C ς t ς exp( 2 -γ γ + 2 α)
Remember now that the values of F along the trajectories of the SDE [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o( 1 k 2 )[END_REF] are controlled by the energy E as stated in (29). Thus:

∀t t c , E[F (X t ) -F * ] 2 t p+2 c 1 + λ t 0 √ K 2 2 E M (t 0 ) + d 2 C ς t ς e 2-γ (γ+2)α t p+2 2 t p+2-ς c 1 + λ t 0 √ K 2 2 E M (t 0 ) + d 2 C ς e 2-γ (γ+2)α t p+2-ς Finally observe that if t c = 2α √ γ (γ+2) √ K 2
> t 0 , we then get:

∀t t c , E[F (X t ) -F * ] 2 2α √ γ (γ + 2) √ K 2 p+2-ς 1 + λ t 0 √ K 2 2 E M (t 0 ) + d 2 C ς e 2-γ γ+2 α t p+2-ς .
as expected.

The second Theorem considers the case of convex functions with a "flat" geometry near its set of minimizers, i.e. roughly speaking functions behaving like • γ with γ > 2.

Theorem 5. Let F : R d → R be a C 2 convex differentiable function admitting a unique minimizer x * , and F * = inf F . Additionally assume that F satisfies both a global growth condition G γ and some flatness assumption F γ for some γ > 2.

Let t 0 > 0. Let (X t , V t ) be any solution of the SDE [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o( 1 k 2 )[END_REF] with (X t 0 , V t 0 ) = (x 0 , v 0 ). Assume that the noise level σ satisfies the integrability condition: there exist C > 0 and ς ∈ [0, 2) such that

(D p,ς ) t t 0 s p+2 σ(s) 2 ds Ct ς where p = 4 γ -2 . ( 31
)
If α γ+2 γ-2 then for all t t 0 we have:

E[F (X t ) -F * ]   t -ς 0 H(t 0 , Y t 0 ) + d 2 C γ-2 γ + λα K -2 γ γ 2 t -ς γ-2 γ 0   γ γ-2 t -2γ γ-2 +ς . (32)
Moreover, for any β > 0,

P F (X t ) -F * 1 t β   t -ς 0 H(t 0 , Y t 0 ) + d 2 C γ-2 γ + λα K -2 γ γ 2 t -ς γ-2 γ 0   γ γ-2 t -2γ γ-2 +ς+β .
We can notice here that for any γ > 2 the decay rate 2γ γ-2 (corresponding to ς = 0) is greater than 2 when γ is large enough. Indeed this Theorem give conditions on the friction parameter α and on the noise to take advantage of the geometry of F . If α is chosen too small, the trajectories will oscillate and the decay rate will be smaller. The critical value for α is γ+2 γ-2 . For all values beyond this one, the asymptotic rate is the same : 2γ γ-2 -ς, but the bound is a growing function of α and thus, the optimal value of α seems to be γ+2 γ-2 .

Proof of Theorem 5. In this proof we still consider the energy (24) defined by:

H(t, (x, v)) = t p E(t, (x, v))
where E(t, (x, v)) = t (a(t, (x, v)) + b(t, (x, v)) + ξc(t, (x, v))) using the following notations:

a(t, (x, v)) = t(F (x) -F * ), b(t, (x, v)) = 1 2t λ(x -x * ) + tv) 2 , c(t, (x, v)) = 1 2t x -x * 2 .
But the choice of parameters is slightly different. Here we choose:

λ = 2 γ -2 , p = 2λ, ξ = λ(λ + 1 -α) (33)
Note that with this choice, we have: ξ < 0 since α γ+2 γ-2 . Let Y t = (X t , V t ). Applying the Itô calculus to H(t, Y t ) and following the same steps as in [22, Proof of Theorem 3.1], we can prove that:

dH(t, Y t ) t p 2( γ + 2 γ -2 -α)b(t, Y t )dt + tσ(t) λ(X t -x * ) + tV t ,
We now need the control on the values F (X t )-F * from the energy. Using |ξ| = λ(α-λ-1) λα, we have:

H(t, Y t ) = t p+1 (a(t, Y t ) + b(t, Y t ) + ξc(t, Y t ) t p+1 a(t, Y t ) -λαt p+1 c(t, Y t ).
Hence:

∀t t 0 , t p+1 E[a(t, Y t )] -λαt p+1 E[c(t, Y t )] E[H(t 0 , Y t 0 )] + d 2 t t 0 s p+2 σ(s) 2 ds.
Assume now that F has a unique minimizer and satisfies the growth condition G γ with γ > 2.

We then have:

c(t, Y t ) K -2 γ γ 2 1-2 γ t -2 γ -1 a(t, Y t ) 2 γ .
Noticing that: 2 γ (p + 2) + 1 = p + 1, we have:

t p+1 c(t, Y t ) K -2 γ γ 2 1-2 γ t p+1 a(t, Y t ) 2 γ .
Hence:

E[t p+1 a(t, Y t ) -λα K -2 γ γ 2 1-2 γ t p+1 a(t, Y t ) 2 γ ] t p+1 E[a(t, Y t )] -λαt p+1 E[c(t, Y t )] E[H(t 0 , Y t 0 )] + d 2 t t 0 s p+2 σ(s) 2 ds.
Applying the Jensen inequality to the convex function x → x γ 2 we get

E[t p+1 a(t, Y t )] -λα K -2 γ γ 2 E[ t p+1 a(t, Y t ) ] 2 γ E[H(t 0 , Y t 0 )] + d 2 t t 0 s p+2 σ(s) 2 ds
Let us apply then the following lemma with δ = 2 γ , m = λα 2 ds for any t t 0 : Lemma 1. Let δ ∈ (0, 1), m > 0 and M > 0

K -2 γ γ 2 and M = E[H(t 0 , Y t 0 )] + d 2 t t 0 s p+2 σ(s)
x -mx δ M ⇒ x (M 1-δ + m) 1 1-δ . ( 36
)
We then deduce that:

E[t p+1 a(t)]   E[H(t 0 , Y t 0 )] + d 2 t t 0 s p+2 σ(s) 2 ds γ-2 γ + λα K -2 γ γ 2   γ γ-2 (37)
Remembering that: a(t) = t(F (x(t)) -F * ), we finally deduce that for all t t 0 ,

t p+2 E[F (x(t)) -F * ]   E[H(t 0 , Y t 0 )] + d 2 t t 0 s p+2 σ(s) 2 ds γ-2 γ + λα K -2 γ γ 2   γ γ-2   E[H(t 0 , Y t 0 )] + d 2 Ct ς γ-2 γ + λα K -2 γ γ 2   γ γ-2   t -ς 0 H(t 0 , Y t 0 ) + d 2 C γ-2 γ + λα K -2 γ γ 2 t -ς γ-2 γ 0   γ γ-2 t -2γ γ-2 +ς .

Conclusion

In many practical applications, the number of samples cannot be arbitrary large and σ has a nonnegative limit when t goes to +∞. In that case, the stochastic gradient method is well-known to reach a ball around the minimizer with a radius depending on this limit. In particular it does not converges to the minimizer even in the very favorable case of a µ-strictly convex objective. Therefore, a variable time step is usually used: for example h n = h n -a with a ∈ (0, 1). We are considering the variable time stepping case in a on going work.

In [START_REF] Shi | Acceleration via symplectic discretization of high-resolution differential equations[END_REF] the authors proposed new optimization algorithms based on the symplectic Euler method classically used for the numerical approximation of Hamiltonian ODE. Under the strong convexity assumption of the cost function F , the authors manage to recover the acceleration phenomenon with rather large step size. Their conclusion is high-resolution ODEs and symplectic schemes are critical to achieve acceleration using numerical discretization. . . Lyapunov functions play a key role in such analyses, and also allow aspects of the continuous-time analysis to be transferred to discrete time. A natural extension of this work is to study the stochastic version of the high resolution ODE [START_REF] Bolte | The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems[END_REF].

Thanks. The first author is indebted to Pr. G. Vallet for instructive discussions on the numerical discretizations of SDEs and for pointing to us the reference [START_REF] Lord | An introduction to computational stochastic PDEs[END_REF] and the basis of the analysis of Section 2.

The error analysis for the deterministic limit stated in [START_REF] Bottou | Optimization methods for large-scale machine learning[END_REF] is a direct consequence of the following result. Proposition 3. Let Φ : R × R d → R d be a Lipschitz function.Let σ : R → R be a bounded integrable function. Let u 0 be a given vector in R d , h ∈ [0, 1] T be non negative real number. Fix N an integer and set T = N h. Define t n = nh, 0 n N and consider the sequences X n and Y n defined by recursion

X n+1 = X n + h Φ(t n , X n ) + √ h σ(t n )(B t n+1 -B tn ), Y n+1 = Y n + h Φ(t n , Y n ),
starting with X 0 = Y 0 = u 0 . Then, there exists a non negative constant C 1 such that the following error estimate holds

sup 0 n N Y n -X n L 2 (Ω) C 1 √ h. ( 39
) Proof of Proposition 3 Consider the misfit e k = X k -Y k , k ∈ N. By construction, it satisfies e k+1 = e k + h (Φ(t k , X k ) -Φ(t k , Y k )) - √ hσ(t k )(B t k+1 -B t k ).
Let n ∈ N. Summing these relations from k = 0 to k = n and remembering that X 0 = Y 0 , we get:

e n+1 = h n k=1 (Φ(t k , X k ) -Φ(t k , Y k )) - √ h n k=0 σ(t k )(B t k+1 -B t k )
which implies:

E[|e n+1 | 2 ] 2h 2 E   n k=1 (Φ(t k , X k ) -Φ(t k , Y k )) 2   + 2hE   n k=0 σ(t k )(B t k+1 -B t k ) 2   .
Observe now that using the inequality (38), we have:

E   n k=1 (Φ(t k , X k ) -Φ(t k , Y k )) 2   n n k=1 E (Φ(t k , X k ) -Φ(t k , Y k )) 2 nLip(Φ) 2 n k=1 E[|e k | 2 ],
where Lip(Φ) denotes the Lipschitz constant of the function Φ. For the second term, we use that the Brownian increments are both independent and centered to get

E   n k=0 σ(t k )(B t k+1 -B t k ) 2   = n k=0 σ(t k ) 2 E B t k+1 -B t k 2 (n + 1) σ 2 ∞ h.
Combining the last two inequalities we then get:

E[|e n+1 | 2 ] ≤ 2nh 2 Lip(Φ) 2 n k=0 E[|e k | 2 ] + n + 1 n σ 2 ∞ 2hT Lip(Φ) 2 n k=0 E[|e k | 2 ] + 2 σ 2 ∞
Finally, applying the discrete Grönwall Lemma we obtain the inequality (39) as expected:

∀n N, E[|e n | 2 ] 4T σ 2 ∞ e 2T Lip(Φ) 2 h.
The second inequality ( 10) is a direct consequence of the previous one and of the classical error estimate for the explicit Euler scheme.

The key of the proof of second is mainly a precise error estimate for the Euler-Maruyama method in the case of an additive noise with a precise computation of the constant. This requires more regularity on the function Φ. We use the notation Lip(σ) to denote the (best) Lipschitz constant of σ and where ∆ 2 Φ to denote the Laplacian of Φ with respect to the second variable. Proposition 4. Let Φ : R × R d → R d be a C 2 Lipschitz function with a bounded second derivative. Let σ : R → R be a bounded Lipschitz function. Let u 0 be a given vector in R d and let h, λ ∈ [0, 1] and T be non negative real number. Fix N an integer and set T = hN . Let u be the solution of the stochastic differential equation:

du = Φ(t, u(t))dt + λσ(t)dB t ,
with the initial condition u(0) = u 0 . Set t n = nh and consider the sequence X n defined by recursion

X n+1 = X n + h Φ(t n , X n ) + λσ(t n )(B t n+1 -B tn ).
Then sup

0 n N u(t n ) -X n L 2 (Ω) Ch,
where the non negative constant C can be chosen as

C = e T 2 Lip(Φ) 2 2 3 T Lip(σ) 2 +6T 2 Lip(Φ) 2 Φ 2 ∞ +9T Lip(Φ) 2 σ 2 ∞ + 3 2 T 2 ∆ 2 Φ 2 ∞ σ 4 ∞ + 2T 2 Lip(Φ) 2
independent of λ and h.

In this work, we are deeply interested in the particular case λ = √ h corresponding to (X n ) defined in [START_REF] Bolte | Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity[END_REF], we obtain the error analysis for the approximation by the SDE stated in [START_REF] Cabot | On the long time behavior of second order differential equations with asymptotically small dissipation[END_REF].

Proof of Proposition 4 Consider the error e n = u(t n ) -X n at step n. By definition, it satisfies the recursion formula :

e n+1 = e n + t n+1 tn (Φ(s, u(s)) -Φ(t n , X n )) ds + λ t n+1 tn (σ(s) -σ(t n )) dB s .
Summing from 0 to n, we get ∆ 2 Φ(s, u(τ ))λ 2 σ 2 (τ )dτ

e n+1 = t n+1 0 Φ(s, u(s)) -Φ(t n(s) , X n(s) ) ds + λ t n+1 0 σ(s) -σ(
2 ds 1 3 t 2 n+1 λ 4 ∆ 2 Φ 2 ∞ σ 4 ∞ h 2 .
For the second term, we first expand the square, then use the fact that the increments of the noise are independent and centered, finally the Cauchy-Schwarz inequality and Itô isometry Gathering all the previous estimations, we obtain that

E
E |e n+1 | 2 Ch 2 + 6hT Lip(Φ) 2 n k=1 E |e k | 2 .
where the constant C is explicitly given by

C = 2 3 λ 2 T Lip(σ) 2 + 6T 2 Lip(Φ) 2 Φ 2 ∞ +9T λ 2 Lip(Φ) 2 σ 2 + 3 2 T 2 λ 4 ∆ 2 Φ 2 ∞ σ 4 ∞ + 2T 2 Lip(Φ) 2 .
As λ ∈ [0, 1],

C C = 2 3 T Lip(σ) 2 + 6T 2 Lip(Φ) 2 Φ 2 ∞ +9T Lip(Φ) 2 σ 2 ∞ + 3 2 T 2 ∆ 2 Φ 2 ∞ σ 4 ∞ + 2T 2 Lip(Φ) 2 .
We apply Grönwall lemma to get that for any n N

E |e n | 2
Ch 2 e nhT Lip(Φ) 2

Ch 2 e T 2 Lip(Φ) 2 .

  3.1.1 Convergence rate for C 2 convex functions Theorem 1. Let F : R d → R be a C 2 convex function with a bounded Laplacian and admitting at least one minimizer. Let F * = min F and t 0 > 0. Assume that the diffusion σ satisfies the integrability condition: there exist C > 0 and ς ∈ [0, 1) such that

	t
	(D 1,ς ) ∀t t 0 ,	sσ 2 (s)ds Ct ς .
	t 0

  t n(s) ) dB s where n(s) denotes the entire part: n(s) = s/h for any 0 s T so that: n(s) = k when t k s < t k+1 . It follows thatE[|e n+1 | 2 ] 2 E Φ(s, u(s)) -Φ(t n(s) , X n(s) ) dsThe first term is split to get a suitable boundΦ(s, u(s))-Φ(t n(s) , X n(s) ) = Φ(s, u(s)) -Φ(s, u(t n(s) )) + Φ(s, u(t n(s) )) -Φ(t n(s) , u(t n(s) )) + Φ(t n(s) , u(t n(s) )) -Φ(t n(s) , X n(s) ), Φ(t n(s) , u(t n(s) )) -Φ(t n(s) , X n(s) ) dsRemembering that n(s) = k when s ∈ [t k , t k+1 ], we have: ∆ 2 Φ(s, u(τ ))λ 2 σ 2 (τ )dτ ds 2 using the convexity inequality (38). We now study each term in the last sum. Using (38) again, the Cauchy-Schwarz inequality and the properties of Φ, we get

	E 1					= E	0 t n+1	t n+1 Φ(s, u(s)) -Φ(s, u(t n(s) )) ds	2	2
	0 +2λ 2 E t k ∂ 2 Φ(s, u(τ ))Φ(τ, u(τ ))dτ + t n+1 0 σ(s) -n(s) ) dB s s s t k ∂ 2 Φ(s, u(τ ))λσ(τ τ 2 . The second term is estimated using the Itô isometry: = E n k=0 t k+1 t k + 2  1 2 s t k ∆ 2 Φ(s, u(τ ))λ 2 σ 2 (τ )dτ ds 
	E	0	t n+1	σ(s) -σ(t n(s) ) dB s 3E n k=0 t k+1 2 t k +3E n k=0	= s t k ∂ 2 Φ(s, u(τ ))Φ(τ, u(τ ))dτ ds t n+1 0 σ(s) -σ(t n(s) ) 2 dt t k+1 t k t k ∂ 2 Φ(s, u(τ ))λσ(τ )dB τ ds 1 2 T Lip(σ) 2 h 2 . 3 s 2
	so that: t k E E t n+1 + 3 4 n t k+1 s E k=0 t k n k=0 t k+1 t k s t 2
	where		E 1	t n+1 k=0 E (n + 1) n = E 0 t n+1 (n + 1) n k=0 h E	t k+1 t k t k+1 t k	s t 2 s t 2 ds
		t n+1 E		t n+1 0	0 t n+1 t n(s) s		2	ds	1 3	t 2 n+1 Lip(Φ) 2 Φ 2 ∞ h 2 .
	0 The same method holds for the third term
	E 2 t k+1 t k t t n+1 n s k=0 s and that by Cauchy-Schwarz inequality E 0 t n(s)	1 3	T 2 Lip(Φ) 2 h 2 ,
	t n+1							2	Lip(Φ) 2	t n+1	|u(t n(s) ) -X n(s) |ds	2
	0							0
						Lip(Φ) 2 t n+1	t n+1	|u(t n(s) ) -X n(s) | 2 ds = Lip(Φ) 2 t n+1	n	|e k | 2 h
								0	k=1
	so that							n
						E 3 hLip(Φ) 2 t n+1	E[|e k | 2 ].
								k=1

0

Φ(s, u(s)) -Φ(t n(s) , X n(s) ) ds

2 3(E 1 + E 2 + E 3 ) Φ(s, u(s)) -Φ(s, u(t n(s) )) ds 2 , E 2 = E Φ(s, u(t n(s) )) -Φ(t n(s) , u(t n(s) )) ds 2 , E 3 = E Φ(t n(s) , u(t n(s) )) -Φ(t n(s) , X n(s) ) ds 2 .

The E 2 term is bounded using Lipschitz properties of Φ

To bound E 1 , we first use Itô formula to the process τ → Φ(s, u(τ )) to get

Φ(s, u(s)) -Φ(s, u(t n(s) )) = s t n(s) ∂ 2 Φ(s, u(τ ))Φ(τ, u(τ ))dτ + s t n(s) ∂ 2 Φ(s, u(τ ))λσ(τ )dB τ + 1 2 s t n(s) ∆ 2 Φ(s, u(τ ))λ 2 σ 2 (τ )dτ. k ∂ 2 Φ(s, u(τ ))Φ(τ, u(τ ))dτ ds k ∂ 2 Φ(s, u(τ ))Φ(τ, u(τ ))dτ ds k ∂ 2 Φ(s, u(τ ))Φ(τ, u(τ ))dτ ∂ 2 Φ(s, u(τ ))Φ(τ, u(τ ))dτ k ∆ 2 Φ(s, u(τ ))λ 2 σ 2 (τ )dτ ds 2 t n+1 E

The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR) under reference ANR-PRC-CE23 Masdol.

A Proofs of Proposition 1

Let us now detail the proofs of Proposition 1. The two statements [START_REF] Bottou | Optimization methods for large-scale machine learning[END_REF] and [START_REF] Cabot | On the long time behavior of second order differential equations with asymptotically small dissipation[END_REF] will be proven independently. For those proofs, we will need the following inequality: for any collection of K vectors x 1 , . . . , x K , it holds

which is a consequence of the Jensen inequality, and the discrete Grönwall lemma:

Lemma 2 (Discrete Grönwall Lemma). Let (z n ) n∈N be a sequence of positive real numbers with z 0 = 0. If there are nonnegative constants C, τ and L such that, for any n 0 it holds

then for all n 0 z n Ce Lnτ .


Michel Mitov
email: mitov@cemes.fr

Corinne Binet

Alain Boudet

Christian Bourgerette

Glassy Cholesteric Broadband Reflectors with a Pitch Gradient: Material Design, Optical Properties and Microstructure

  L'archive ouverte pluridisciplinaire


Deeya Saha

Marta Iannuccelli

Christine Brun

Andreas Zanzoni
email: andreas.zanzoni@univ-amu.frluana.licata@uniroma2.it.

Luana Licata

The intricacy of the viral-human protein interaction networks: resources, data and analyses

Keywords: Protein-protein interactions, virus-host protein-protein interaction databases, virus-human interactomes, molecular interaction data standards, SARS-CoV-2, emerging viruses Viral-human protein interaction resources

Viral infections are one of the major causes of human diseases that cause yearly millions of deaths and seriously threaten global health, as we have experienced with the COVID-19 pandemic.

Numerous approaches have been adopted to understand viral diseases and develop pharmacological treatments. Among them, the study of virus-host protein-protein interactions is a powerful strategy to comprehend the molecular mechanisms employed by the virus to infect the host cells and to interact with their components. Experimental protein-protein interactions described in the scientific literature have been systematically captured into several molecular interaction databases. These data are organized in structured formats and can be easily downloaded by users to perform further bioinformatic and network studies.

Network analysis of available virus-host interactomes allow us to understand how the host interactome is perturbed upon viral infection and what are the key host proteins targeted by the virus and the main cellular pathways that are subverted.

In this review, we give an overview of publicly available viral-human protein-protein interactions resources and the community standards, curation rules and adopted ontologies.

A description of the main virus-human interactome available is provided, together with the main network analyses that have been performed. We finally discuss the main limitations and future challenges to assess the quality and reliability of protein-protein interaction datasets and resources.

Introduction

Infectious diseases, including respiratory viral infections, are among the top 10 causes of death worldwide accounting for millions of fatalities every year, especially in low-income countries (World Health Organization, 2020). Moreover, the increasing incidence of (re-)emerging infectious diseases is posing serious global health threats [START_REF] Jones | Global trends in emerging infectious diseases[END_REF][START_REF] Cui | Origin and evolution of pathogenic coronaviruses[END_REF][START_REF] Pierson | The continued threat of emerging flaviviruses[END_REF], as exemplified by the COVID-19 pandemic [START_REF] Morens | Emerging Pandemic Diseases: How We Got to COVID-19[END_REF].

The development of effective antiviral pharmacological treatments relies on an in-depth understanding of the virus biology and the host response [START_REF] Eckhardt | A systems approach to infectious disease[END_REF]. In the last Viral-human protein interaction resources decades, protein-protein interaction (PPI) discovery experiments have gained momentum among the different approaches to study viral diseases [START_REF] De Chassey | Virus-host interactomics: new insights and opportunities for antiviral drug discovery[END_REF][START_REF] Goodacre | Protein-protein interactions of human viruses[END_REF]. Indeed, the systematic mapping of interactions between viral and host proteins can provide a better understanding of the molecular mechanisms of viral infections and identify viral perturbations underlying disease phenotypes, thus suggesting novel potential targets of therapeutic intervention [START_REF] Cakir | Target Discovery for Host-Directed Antiviral Therapies: Application of Proteomics Approaches[END_REF].

Over the years, these interaction maps described in the scientific literature have been systematically captured into several publicly available molecular interaction databases (e.g., [START_REF] Guirimand | VirHostNet 2.0: surfing on the web of virus/host molecular interactions data[END_REF][START_REF] Calderone | Using the MINT Database to Search Protein Interactions[END_REF][START_REF] Del Toro | The IntAct database: efficient access to fine-grained molecular interaction data[END_REF][START_REF] Oughtred | The BioGRID database: A comprehensive biomedical resource of curated protein, genetic, and chemical interactions[END_REF].

The interaction data is organized in structured formats [START_REF] Orchard | The minimum information required for reporting a molecular interaction experiment (MIMIx)[END_REF][START_REF] Porras | Towards a unified open access dataset of molecular interactions[END_REF], that can be easily processed and exploited to perform downstream computational and network analyses [START_REF] Porras | Towards a unified open access dataset of molecular interactions[END_REF].

In this review, we discuss the state-of-the-art of available PPI resources and in particular those dedicated to viruses and the human host. A brief description of the available datasets is provided along with the developed community standards, curation rules and strategies, adopted ontologies and controlled vocabularies, quality control procedures and scoring systems. We also give an overview of the largest available viral-human interactomes with a particular focus on the recently generated interaction maps between SARS-CoV-2 and human proteins, as well as those of other (re-)emerging viruses like Zika and Dengue, outlining common and virus-specific interaction and host-cell perturbation patterns.

We discuss how these interaction networks can provide novel mechanistic insights on viral infection biology and can suggest novel pharmacological strategies. Finally, we review the main limitations of molecular interaction resources and datasets and their future challenges.

Public resources collecting virus-host protein-protein interaction data

Virus-host molecular interactions, mostly PPIs, detected from high-throughput studies, together with those identified in hundreds of biochemical and biophysical low-throughput studies, have been gathered in distinct public databases using structured formats [START_REF] Licata | The MIntAct Project and Molecular Interaction Databases[END_REF][START_REF] Goodacre | Protein-protein interactions of human viruses[END_REF].

Viral-human protein interaction resources

These public resources can be divided in: (i) primary databases that collect only manually curated molecular interactions extracted from peer-reviewed journals and related to different viruses and their relative hosts, such as MINT [START_REF] Calderone | Using the MINT Database to Search Protein Interactions[END_REF]), IntAct (Del Toro et al., 2021), and BioGRID [START_REF] Oughtred | The BioGRID database: A comprehensive biomedical resource of curated protein, genetic, and chemical interactions[END_REF]; (ii) metadatabases integrating data from primary resources, such as VirusMentha [START_REF] Calderone | VirusMentha: a new resource for virus-host protein interactions[END_REF] and APID [START_REF] Alonso-López | APID database: redefining protein-protein interaction experimental evidences and binary interactomes[END_REF]; (iii) databases combining experimental interaction data with predicted PPIs, such as virusSTRING [START_REF] Szklarczyk | The STRING database in 2021: customizable protein-protein networks, and functional characterization of user-uploaded gene/measurement sets[END_REF], human-virus PPI database (HVIDB) [START_REF] Yang | HVIDB: a comprehensive database for human-virus protein-protein interactions[END_REF] and the pathogen-host interaction search tool PHISTO [START_REF] Durmuş Tekir | PHISTO: pathogen-host interaction search tool[END_REF]; (iv) databases, such as VirHostnet3.0 database [START_REF] Guirimand | VirHostNet 2.0: surfing on the web of virus/host molecular interactions data[END_REF], which are both primary resources collecting manually annotated PPIs and metadatabases integrating data from other molecular interaction databases; and (v) databases collecting information only related to a specific virus-host interactome, such as DenHunt [START_REF] Karyala | DenHunt -A Comprehensive Database of the Intricate Network of Dengue-Human Interactions[END_REF] and DenvInt [START_REF] Dey | DenvInt: A database of protein-protein interactions between dengue virus and its hosts[END_REF] for the Dengue virus, the HIV-1 Human Interaction Database [START_REF] Ako-Adjei | HIV-1, human interaction database: current status and new features[END_REF] and the Hepatitis C Virus Protein Interaction Database (HCVpro) [START_REF] Kwofie | HCVpro: hepatitis C virus protein interaction database[END_REF].

Despite the large amount of data accumulated over the years in these resources, the early data collection did not follow common criteria in terms of data curation and standardization. This discrepancy in dataset formats and curation strategies is sometimes the cause of heterogeneous data generation, which is difficult to filter, use and analyze without data loss and a time-consuming scrupulous work by bioinformaticians. With this in mind, several years ago, the Molecular Interaction working group of the HUPO-Proteomics Standards Initiative (HUPO-PSI) has developed standards, tools and Controlled Vocabularies (CVs) that have allowed life science communities to combine and analyze datasets collected and stored in different molecular interaction databases [START_REF] Kerrien | Broadening the horizon--level 2.5 of the HUPO-PSI format for molecular interactions[END_REF][START_REF] Deutsch | Proteomics Standards Initiative: Fifteen Years of Progress and Future Work[END_REF]. In 2007, the working group defined the minimum information required for reporting a molecular interaction experiment (MIMIx), which enables the systematic capture and the access to interaction data in different resources [START_REF] Orchard | The minimum information required for reporting a molecular interaction experiment (MIMIx)[END_REF]. Several databases have adopted this standard over the years, (e.g., BIOGRID, IntAct, MINT, VirHostNet), thus enabling seamless integration of distinct interaction datasets at the minimum level of interaction details, such as interaction detection and participant detection methods.

For instance, the integration of virus-human PPIs from the main resources collecting virushost interactions (e.g., MINT, IntAct, VirHostnet 3.0 and BIOGRID, data fetched in August Viral-human protein interaction resources 2021), generates a very large set of 54237 interactions between viral and human proteins (Figure 1A). Notably, the overlap between them is very small and mainly consists of the largescale virus-human interactomes (Figure 1B), suggesting that the different resources may use complementary strategies to mine the available literature.

IMEx databases, their curation strategies and adopted standards

Starting from 2012, some of the major resources collecting PPI data, agreed to unify their curation efforts to obtain a shared and non-redundant dataset, which is annotated using the same curation rules and common export standards.

The result of this coordination is the International Molecular Exchange (IMEx) consortium (http://www.imexconsortium.org/), whose members (such as IntAct, MINT, DIP, UniProtKB) have agreed to curate only experimentally interaction data coming from peer-reviewed papers.

The consortium members are all professional bio-curators, employing a common detailed curation guideline and up-to-date controlled vocabularies that allow high accuracy of quality control procedures. For instance, interaction data is checked twice before its release, and specific tools are used (e.g., the PSI-MI semantic validator [START_REF] Montecchi-Palazzi | The PSI semantic validator: a framework to check MIAPE compliance of proteomics data[END_REF])

to automatically check for potential errors and discrepancies related to the PSI-MI ontology of all the entries. All IMEx entries are annotated with a wealth of details, such as the role played by the participant within the experiment (e.g., bait, prey, neutral), host organism information, cell line or tissue where the experiment was carried out, and several other features related to the interaction, such as binding sites, mutation effect, construct tags, parameters and stoichiometry [START_REF] Porras | Towards a unified open access dataset of molecular interactions[END_REF].

IMEx datasets can be filtered according to the MIscore, a scoring system that measures the quality of a PPI based on the number of manuscripts reporting the interaction, the type of interaction and the experimental methods used to detect the given interaction [START_REF] Villaveces | Merging and scoring molecular interactions utilising existing community standards: tools, use-cases and a case study[END_REF].

Viral-human protein interaction resources

All IMEx virus-host datasets are available at the IntAct download page (https://www.ebi.ac.uk/intact/download/datasets). As of August 2021, the IMEx virus-human dataset consists of 22,896 PPIs (Supplementary Table 1). Coronaviridae, Orthomyxoviridae, Papillomaviridae and Herpesviridae are among the most represented families (Figure 1C).

The datasets contain not only virus-human host interactions, but also interactions involving proteins from other animal viruses and hosts. A dedicated COVID-19 dataset is as well available [START_REF] Perfetto | The IMEx coronavirus interactome: an evolving map of Coronaviridae-host molecular interactions[END_REF].

Main limitations of PPI data and their impact on interactome analysis

Studies of virus-host interactomes have turned out to be extremely powerful to identify the main host target proteins and the biological processes perturbed during a viral infection, but also to predict new potential therapeutic targets and drugs repurposing candidates [START_REF] Bouhaddou | The Global Phosphorylation Landscape of SARS-CoV-2 Infection[END_REF]Gordon et al., 2020b).

However, the quality and reliability of these analyses are biased by several factors, such as the interactome coverage, the methodologies applied to generate the PPI network, the lack of low throughput validation studies, true negative PPIs and the types of standards adopted to annotate those data [START_REF] Braun | An experimentally derived confidence score for binary protein-protein interactions[END_REF][START_REF] Venkatesan | An empirical framework for binary interactome mapping[END_REF].

Most of the available molecular interaction data is associated with the frequently studied viral families due to their impact on public health and global economy (Figure 1C). Their interactomes are often the result of large-scale yeast two-hybrid or AP-MS screens (de [START_REF] De Chassey | Virus-host interactomics: new insights and opportunities for antiviral drug discovery[END_REF][START_REF] Shapira | A physical and regulatory map of host-influenza interactions reveals pathways in H1N1 infection[END_REF][START_REF] Tripathi | Network based analysis of hepatitis C virus core and NS4B protein interactions[END_REF][START_REF] Muller | Large scale genotype comparison of human papillomavirus E2-host interaction networks provides new insights for e2 molecular functions[END_REF][START_REF] Dolan | Identification and comparative analysis of hepatitis C virus-host cell protein interactions[END_REF][START_REF] Wang | Comparative influenza protein interactomes identify the role of plakophilin 2 in virus restriction[END_REF]Gordon et al., 2020a;[START_REF] Li | Virus-Host Interactome and Proteomic Survey Reveal Potential Virulence Factors Influencing SARS-CoV-2 Pathogenesis[END_REF][START_REF] Stukalov | Multilevel proteomics reveals host perturbations by SARS-CoV-2 and SARS-CoV[END_REF] (Supplementary Table 2, Figure 1D).

According to the methodology applied, different subsets of PPIs and different interaction types (direct or indirect) can be detected, and this partially explains the poor overlap often observed between large-scale PPI datasets [START_REF] Braun | Interactome mapping for analysis of complex phenotypes: insights from benchmarking binary interaction assays[END_REF]. Furthermore, these differences are often related to the strategies employed by researchers during the selection of high confident interactors and the removal of spurious interactors [START_REF] Walhout | A genetic strategy to eliminate self-activator baits prior to high-throughput yeast two-hybrid screens[END_REF][START_REF] Hein | A human interactome in three quantitative dimensions organized by stoichiometries and abundances[END_REF][START_REF] Choi | Maximizing binary interactome mapping with a minimal number of assays[END_REF].

Viral-human protein interaction resources

As an example, the three main high-throughput experimental screens to map the interactome between SARS-CoV-2 and human proteins employed similar AP-MS methodologies (Gordon et al., 2020a;[START_REF] Li | Virus-Host Interactome and Proteomic Survey Reveal Potential Virulence Factors Influencing SARS-CoV-2 Pathogenesis[END_REF][START_REF] Stukalov | Multilevel proteomics reveals host perturbations by SARS-CoV-2 and SARS-CoV[END_REF]. However, Gordon et al. and Li et al. used HEK293T cells,while Stukalov et al. used A549 cells. Despite the use of the same technique and in two cases of the same cell line, the three screens detected a different number of interactions and showed a poor overlap in terms of human targets. However, pathway enrichment analyses revealed commonalities in the biological processes and cellular pathways targeted by viral proteins, such as cell cycle and response to stress [START_REF] Perfetto | The IMEx coronavirus interactome: an evolving map of Coronaviridae-host molecular interactions[END_REF]. This variability can be further amplified by different experimental conditions, tissues or cell lines used or experimental and participant modifications (e.g., use of chemicals or drugs, use and position of a tag, protein mutations). Ammari et al. showed that the use of rich datasets, such as the ones provided by IMEx resources, allows to perform more comprehensive network analysis whose output can differ greatly depending on the biological context or methodology used. For example, the host interacting partners of HCV proteins change depending on the cell line used to perform the experiments (e.g., Huh7 versus HEK293) and consequently the cellular processes in which they are involved [START_REF] Ammari | Leveraging Experimental Details for an Improved Understanding of Host-Pathogen Interactome[END_REF].

All these aspects must be considered before selecting, merging and analyzing PPI datasets.

The choice of a dataset containing information on the biological context [START_REF] Porras | Towards a unified open access dataset of molecular interactions[END_REF] in which the interactions have occurred, can allow more sophisticated analysis and reliable outcomes.

Another important aspect that can strongly impact the evaluation of the quality of a virus-host interactome is the use of small-scale biochemical and biophysical studies that can validate and confirm the interactions found in large-scale experiments. A detailed analysis of the available validated virus-host interactions has been presented in a recent review [START_REF] Goodacre | Protein-protein interactions of human viruses[END_REF].

In-silico approaches based on sequence (e.g., [START_REF] Eid | DeNovo: virus-host sequence-based proteinprotein interaction prediction[END_REF][START_REF] Liu-Wei | DeepViral: prediction of novel virus-host interactions from protein sequences and infectious disease phenotypes[END_REF]) and structural similarity (e.g., [START_REF] De Chassey | Structure homology and interaction redundancy for discovering virus-host protein interactions[END_REF][START_REF] Lasso | A Structure-Informed Atlas of Human-Virus Interactions[END_REF]), as well as protein Viral-human protein interaction resources docking [START_REF] Wierbowski | A 3D structural SARS-CoV-2-human interactome to explore genetic and drug perturbations[END_REF], has been also used to predict virus-host protein-protein interactions. The recent advent of deep-learning methods to predict protein structures [START_REF] Senior | Improved protein structure prediction using potentials from deep learning[END_REF][START_REF] Baek | Accurate prediction of protein structures and interactions using a three-track neural network[END_REF] as well as protein macromolecular complexes [START_REF] Baek | Accurate prediction of protein structures and interactions using a three-track neural network[END_REF][START_REF] Bryant | Improved prediction of protein-protein interactions using[END_REF][START_REF] Evans | Protein complex prediction with AlphaFold-Multimer[END_REF], can be a useful complementary strategy to identify or validate the molecular determinants of virus-host protein interactions identified in experimental assays.

Finally, negative PPIs can be extremely important for validating interaction data or to assess the quality of interaction prediction methods. To our knowledge, the Negatome Database 2.0 is the only available resource collecting valuable negative interaction data [START_REF] Blohm | Negatome 2.0: a database of non-interacting proteins derived by literature mining, manual annotation and protein structure analysis[END_REF]. Indeed, the database lists experimentally verified non-interacting proteins identified either by manual curation from literature (2171 negative interactions, 75 of which involve at least one viral protein) or derived by the analysis of the protein structures from the PDB (4397 negative interactions, only two involve at least one viral protein).

The IMEx consortium databases also collect negative interactions [START_REF] Porras | Towards a unified open access dataset of molecular interactions[END_REF].

However, the size of the dataset is still small (~1000 PPIs) and only 18 of those are negative virus-host interactions, suggesting that, on one hand, researchers should systematically provide the negative interaction data coming from their experiments, and on the other hand, additional curation effort is needed to extract this information from the scientific literature.

Viral-human interactomes: from network perturbation to dysregulated biological processes in disease

Over the past two decades, several high-throughput techniques, such as yeast two-hybrid and affinity purification coupled to mass spectrometry (AP-MS), have been developed to map model organism interactomes in order to decipher the dynamics and complexity of interaction networks [START_REF] Snider | Fundamentals of protein interaction network mapping[END_REF]. These methodologies have also been applied to chart the interactome between several viruses and the human host (Supplementary Table 2 and Figure 1D-E).

The first virus-host interaction maps that have been deciphered (EBV, HCV) revealed that viral proteins preferentially target highly connected proteins (hubs) among their host proteins [START_REF] Calderwood | Epstein-Barr virus and virus human protein interaction maps[END_REF][START_REF] De Chassey | Virus-host interactomics: new insights and opportunities for antiviral drug discovery[END_REF]. As these hub proteins are relatively close

Viral-human protein interaction resources

in the network to a large number of proteins involved in different cellular processes, this could represent a virus strategy to subvert the cellular processes at its own benefit [START_REF] Bösl | Common Nodes of Virus-Host Interaction Revealed Through an Integrated Network Analysis[END_REF].

Early structural bioinformatics analyses showed that human-cell hijacking by viral proteins can be achieved through interface mimicry of endogenous interactions (i.e., interaction between host proteins) [START_REF] Franzosa | Structural principles within the human-virus protein-protein interaction network[END_REF][START_REF] Garamszegi | Signatures of pleiotropy, economy and convergent evolution in a domain-resolved map of human-virus protein-protein interaction networks[END_REF]. Notably, they estimated that up to one-third of the viral-human interactions studied can be related to this phenomenon, in particular through the mimicry of non-globular protein interaction elements known as short linear motifs (SLiMs), which are short stretches of contiguous amino acids residues that often mediate transient PPIs [START_REF] Davey | Attributes of short linear motifs[END_REF] and have emerged through convergent evolution [START_REF] Davey | How viruses hijack cell regulation[END_REF]. Viral abuse of SLiMs is widespread [START_REF] Davey | How viruses hijack cell regulation[END_REF][START_REF] Hagai | Use of host-like peptide motifs in viral proteins is a prevalent strategy in host-virus interactions[END_REF][START_REF] Via | How pathogens use linear motifs to perturb host cell networks[END_REF], and the pervasiveness of interface mimicry provides potential connections between infectious agents and human diseases [START_REF] Chen | Convergent perturbation of the human domain-resolved interactome by viruses and mutations inducing similar disease phenotypes[END_REF][START_REF] Lasso | A Sweep of Earth's Virome Reveals Host-Guided Viral Protein Structural Mimicry and Points to Determinants of Human Disease[END_REF]. Indeed, the targeted and consequently perturbed processes by human viruses encompass different and relevant signaling pathways: TGFbeta for SARS-CoV-2 and Hepatitis C Virus (HCV) [START_REF] De Chassey | Virus-host interactomics: new insights and opportunities for antiviral drug discovery[END_REF][START_REF] Stukalov | Multilevel proteomics reveals host perturbations by SARS-CoV-2 and SARS-CoV[END_REF]; JAK/STAT for HCV [START_REF] De Chassey | Virus-host interactomics: new insights and opportunities for antiviral drug discovery[END_REF]; Notch for Epstein-Barr Virus (EBV), Human Papillomavirus (HPV), Polyoma Virus (PyV), and Adenovirus (Ad5) [START_REF] Fossum | Evolutionarily conserved herpesviral protein interaction networks[END_REF]; Wnt for Influenza A Virus (IAV-H1N1) [START_REF] Shapira | A physical and regulatory map of host-influenza interactions reveals pathways in H1N1 infection[END_REF], and cellular processes such as autophagy (SARS-CoV-2) [START_REF] Stukalov | Multilevel proteomics reveals host perturbations by SARS-CoV-2 and SARS-CoV[END_REF], apoptosis (EBV, HPV, PyV, and Ad5) [START_REF] Fossum | Evolutionarily conserved herpesviral protein interaction networks[END_REF], focal adhesion (HCV) [START_REF] De Chassey | Virus-host interactomics: new insights and opportunities for antiviral drug discovery[END_REF] or nonsense-mediated mRNA decay (Semliki Forest Virus (SFV) [START_REF] Contu | Characterisation of the Semliki Forest Virus-host cell interactome reveals the viral capsid protein as an inhibitor of nonsense-mediated mRNA decay[END_REF]). The identification of targeted cellular functions is usually performed using computational tools for functional enrichment analysis such as g:Profiler [START_REF] Raudvere | g:Profiler: a web server for functional enrichment analysis and conversions of gene lists (2019 update)[END_REF] and Metascape [START_REF] Zhou | Metascape provides a biologist-oriented resource for the analysis of systems-level datasets[END_REF].

The blockade of some key factors through interactions is also often observed from PPI analysis. Whereas SARS-CoV-2 proteins perturb the NF-kB-repressing factor (NKRF), therefore potentially contributing to the host inflammatory response by acting on the IL-8mediated chemotaxis of neutrophils [START_REF] Li | Virus-Host Interactome and Proteomic Survey Reveal Potential Virulence Factors Influencing SARS-CoV-2 Pathogenesis[END_REF], the Ebola virus increases its own transcription and replication by interfering with an ubiquitin ligase (RBBP6) (Batra et al., Viral-human protein interaction resources 2018). Zika and Dengue viruses suppresses interferon-stimulated genes by inhibiting the recruitment of the transcription complex PAF1C [START_REF] Shah | Comparative Flavivirus-Host Protein Interaction Mapping Reveals Mechanisms of Dengue and Zika Virus Pathogenesis[END_REF], and HIV protects its replication by cleaving EIF3D, a subunit of eukaryotic translation initiation factor 3, able to inhibit HIV replication [START_REF] Jäger | Global landscape of HIV-human protein complexes[END_REF]. Conversely, interactome analysis also allows discovering host proteins that protect against infection such as Plakophilin 2 (PKP2), a natural inhibitor of IAV polymerase complex [START_REF] Wang | Comparative influenza protein interactomes identify the role of plakophilin 2 in virus restriction[END_REF].

In addition, interaction analysis can explain disease phenotypes and unravel pathogenic mechanisms. The Zika virus (ZIKV) can cause neurodevelopmental defects [START_REF] Platt | Zika virus-related neurotropic flaviviruses infect human placental explants and cause fetal demise in mice[END_REF]. The viral NS4A protein interacts with a gene linked to hereditary microcephaly in humans (hANKLE2) [START_REF] Shah | Comparative Flavivirus-Host Protein Interaction Mapping Reveals Mechanisms of Dengue and Zika Virus Pathogenesis[END_REF]. Strikingly, the ubiquitous expression of NS4A in wild type Drosophila phenocopies microcephaly that, in turn, is rescued by the expression of hANKLE2 and or its ortholog in Drosophila (dAnkle2) [START_REF] Shah | Comparative Flavivirus-Host Protein Interaction Mapping Reveals Mechanisms of Dengue and Zika Virus Pathogenesis[END_REF]. Virus-host PPI mapping therefore provides biological insights and unveils potential pathogenic mechanisms.

Finally, although beyond the scope of this review, in the case of vector-borne diseases such as Dengue and Zika fever, the comparison between the virus-vector and the virus-host interaction maps (i.e., [START_REF] Shah | Comparative Flavivirus-Host Protein Interaction Mapping Reveals Mechanisms of Dengue and Zika Virus Pathogenesis[END_REF]) can reveal promising drug target candidates or treatment strategies to reduce the risk of viral resistance.

Viral-host Interactomes of the emerging viruses: Commonalities and specificities

Viruses have evolved sophisticated strategies to enter and evade host-cell defense and accelerate viral replication by perturbing a variety of cellular functions. Several integrated network analyses revealed that some of these strategies are virus-specific whereas others perturb common cellular pathways [START_REF] Pichlmair | Viral immune modulators perturb the human molecular network by common and unique strategies[END_REF][START_REF] Shah | Comparative Flavivirus-Host Protein Interaction Mapping Reveals Mechanisms of Dengue and Zika Virus Pathogenesis[END_REF][START_REF] Bösl | Common Nodes of Virus-Host Interaction Revealed Through an Integrated Network Analysis[END_REF].

In this section, we focus on four emerging viruses (SARS-CoV-2, Ebola virus, ZIKV and SFV), for which a repertoire of PPIs with human proteins in the IMEx consortium databases. As shown previously [START_REF] Bösl | Common Nodes of Virus-Host Interaction Revealed Through an Integrated Network Analysis[END_REF], the four viruses show both common and specific human protein interactors (Figure 1F) as well as in terms of targeted biological processes. For instance, among the commonly targeted cellular functions, the most represented are related to protein translation and RNA processing (Supplementary Table 3), in agreement with the Viral-human protein interaction resources biology of RNA viruses. Indeed, around one quarter of the known ~2000 human RNA binding proteins (RBPs) has been shown to play a critical role during viral infection [START_REF] Garcia-Moreno | Unconventional RNA-binding proteins step intothe virus-host battlefront[END_REF].

Interestingly, only five human interactors are shared by all the four viruses, and four out of five are RNA binding proteins or RBPs. One of them is the prohibitin (PHB1), which is known for its role in cell-to-cell transmission of herpes virus [START_REF] Watanabe | Prohibitin-1 Contributes to Cell-to-Cell Transmission of Herpes Simplex Virus 1 via the MAPK/ERK Signaling Pathway[END_REF] and plays a pivotal role during other viral infections like that of Enterovirus and HCV [START_REF] Liu | A Novel Class of Small Molecule Compounds that Inhibit Hepatitis C Virus Infection by Targeting the Prohibitin-CRaf Pathway[END_REF][START_REF] Too | Prohibitin plays a critical role in Enterovirus 71 neuropathogenesis[END_REF]. Interestingly, RBPs that are commonly targeted by ZIKV, SFV and SARS-CoV-2 are not only involved in mRNA translation but in many other immunoregulatory processes.

Fifty-nine proteins are commonly targeted by ZIKV, SFV and SARS-CoV-2 (Figure 1F). All of them have RNA binding activity and some of them also take active part in immune regulation.

For instance, DDX21, an RNA helicase, acts in innate immune response as positive regulator of NF-kB signaling [START_REF] Zhang | DDX1, DDX21, and DHX36 Helicases Form a Complex with the Adaptor Molecule TRIF to Sense dsRNA in Dendritic Cells[END_REF][START_REF] Chen | Cellular DDX21 RNA Helicase Inhibits Influenza A Virus Replication but Is Counteracted by the Viral NS1 Protein[END_REF][START_REF] Abdullah | DDX21, a Host Restriction Factor of FMDV IRES-Dependent Translation and Replication[END_REF] and as antiviral factor [START_REF] Chen | Cellular DDX21 RNA Helicase Inhibits Influenza A Virus Replication but Is Counteracted by the Viral NS1 Protein[END_REF]. In addition, many RBPs commonly targeted by the three viruses are associated with ubiquitin mediated protein degradation pathways (e.g., RPS7, RPL11, RPS2, RPL5) and regulation of apoptotic processes (e.g., SERBP1, RSL1D1, RPS7), thus underlying the key role of RBPs in virus-host interactions. Do these emerging viruses strategically target RBPs, as also shown for IAV-H1N1 [START_REF] Shapira | A physical and regulatory map of host-influenza interactions reveals pathways in H1N1 infection[END_REF]? If this is the case, what are the consequences of the hijacking of RBPs on host defense response upon infection? These are still open questions. However, recent studies highlight the antiviral or immune related function of RBPs [START_REF] Newman | RNA binding proteins as regulators of immune cell biology[END_REF][START_REF] Díaz-Muñoz | Uncovering the Role of RNA-Binding Proteins in Gene Expression in the Immune System[END_REF][START_REF] Garcia-Moreno | System-wide Profiling of RNA-Binding Proteins Uncovers Key Regulators of Virus Infection[END_REF] and their implication in viral processes [START_REF] Embarc-Buh | RNA-Binding Proteins at the Host-Pathogen Interface Targeting Viral Regulatory Elements[END_REF][START_REF] Kamel | Global analysis of protein-RNA interactions in SARS-CoV-2-infected cells reveals key regulators of infection[END_REF].

Among SARS-CoV-2 specific human targets, there are 23 proteins linked to ER-associated protein degradation pathways members, such as BAG6 and STUB1. Recently, a study has shown that ER stress inducer thapsigargin inhibits coronavirus replication [START_REF] Shaban | Multi-level inhibition of coronavirus replication by chemical ER stress[END_REF]. Moreover, coronaviruses, including SARS-CoV-2, suppress ER quality control processes or ER associated degradation which is re-activated by the drug thapsigargin [START_REF] Shaban | Multi-level inhibition of coronavirus replication by chemical ER stress[END_REF]. Hence, targeting of ERAD pathways by SARS-CoV-2 or other coronaviruses could be a unique strategy to evade host defense and facilitate viral replication within the host.

ZIKV specific human targets are mainly involved in mitochondrial translation. Recent studies show that ZIKV infection impairs mitochondrial functions [START_REF] Yang | Zika Virus-Induced Neuronal Apoptosis via Increased Mitochondrial Fragmentation[END_REF][START_REF] Yau | Dysregulated Metabolism Underpins Zika Virus Infection-Associated Impairment in Fetal Development[END_REF].

Viral-human protein interaction resources

On the other hand, SFV specific interactors are involved in nonsense mediated mRNA decay (NMD) [START_REF] Contu | Characterisation of the Semliki Forest Virus-host cell interactome reveals the viral capsid protein as an inhibitor of nonsense-mediated mRNA decay[END_REF]. Indeed, SFV inhibits NMD, which in turn helps the stabilization of the viral genomic RNA within the host cell [START_REF] Contu | Characterisation of the Semliki Forest Virus-host cell interactome reveals the viral capsid protein as an inhibitor of nonsense-mediated mRNA decay[END_REF].

Altogether, a quick scrutiny of the human interactors of these four emerging viruses sheds light on some of the common as well as specific strategies to subvert host cellular machinery.

Further and deeper investigation of these common and specific human proteins can therefore generate testable hypotheses on the infection biology of emerging and re-emerging diseases.

Conclusion and future challenges

PPI databases are important resources to gather and organize in structured formats virushost PPI datasets useful for further network analysis. A better coverage of the curated virushost PPIs together with the complete annotation of the experimental feature details, such as the biological context of an interaction, are necessary to perform more sophisticated network analysis. Indeed, network analysis has been proved to be fundamental to understand the perturbed cellular machinery by viruses.

Reverse genetic systems are used to manipulate virus genomes in order to understand genotypic variation or to investigate specific gene functions [START_REF] Messer | Development and characterization of a reverse genetic system for studying dengue virus serotype 3 strain variation and neutralization[END_REF][START_REF] V'kovski | Coronavirus biology and replication: implications for SARS-CoV-2[END_REF]. These technologies can be also useful to contextualize virus-host PPIs during the virus life cycle and to gain important information on virus pathological processes at the molecular level.

Furthermore, the integration of interactome data with available proteomic, genetic, structural and clinical data can give a more comprehensive picture of the biological process perturbed during viral infection, paving the way to the identification of novel drug targets and successful treatments [START_REF] Bouhaddou | The Global Phosphorylation Landscape of SARS-CoV-2 Infection[END_REF]Gordon et al., 2020b;[START_REF] Wierbowski | A 3D structural SARS-CoV-2-human interactome to explore genetic and drug perturbations[END_REF].

Figure legends Figure 1 .

 legends1 Figure legends

Funding

This work was supported by the European Union's Horizon 2020 Research and Innovation Programme (Project ID 101003633, RiPCoN; C.B and A.Z). Luana Licata acknowledges The Italian Association for Cancer Research [AIRC IG 2017 no. 20322] for financial support.

Conflict of Interest

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.


Corinne Binet

Alexandrine Lavernhe

Michel Mitov

Christian Bourgerette

How to broaden the light reflection band in cholesteric liquid crystals? A new approach based on polymorphism

published or not. The documents may come

How to broaden the light reflection band in cholesteric liquid crystals? A new approach based on polymorphism

Alexandrine Lavernhe, Michel Mitov,