{'fraction_non_alphanumeric': 0.049147532710954116, 'fraction_numerical': 0.016004037054392097, 'mean_word_length': 4.282463823305408, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 14, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A systematic approach to Lyapunov analyses of continuous-time models in convex optimization

First-order methods are often analyzed via their continuous-time models, where their worst-case convergence properties are usually approached via Lyapunov functions. In this work, we provide a systematic and principled approach to find and verify Lyapunov functions for classes of ordinary and stochastic differential equations. More precisely, we extend the performance estimation framework, originally proposed by Drori and Teboulle [10], to continuous-time models. We retrieve convergence results comparable to those of discrete methods using fewer assumptions and convexity inequalities, and provide new results for stochastic accelerated gradient flows.


Introduction.
Convex optimization is an important tool in the numerical analyst toolbox. It serves, among others, for framing modeling problems in data science and signal processing. A number of convex optimization problem take the form: where f is convex, differentiable, and x ∈ R d contains the variables of the model. First-order methods are very popular to solve these problems, due to their attractive low cost per iteration, and to the fact that data science applications typically do not require very accurate solutions [6]. Gradient descent is a common first-order method, which starts from a point x 0 ∈ R d , its iterates are given by the simple recursion where γ > 0 is a step size. DenotingẊ t = d dt X t , gradient descent with small step sizes γ is directly related to the so-called gradient flow: where the solution X t of the ODE verifies X t k ≈ x k with the identification t k = γk. In numerical integration, gradient descent (1.2) is also known as the Euler explicit scheme for integrating the gradient flow. Recently, Su et al. [37] have interpreted Nesterov's accelerated gradient [25] in a similar fashion through its continuous version, paving the way to several continuous analyses of accelerated methods [34,47,46].
Many applications entail some randomness and require a stochastic modeling of the function f , which is often defined in terms of an expectation f (x) = E ξ [f (x, ξ)]. The function f is the expectation over some random variable ξ, and accounts some random modeling. When ξ is drawn uniformly from a finite set of possible samples (ξ 1 , ..., ξ n ), we have a finite sum f (x) = 1 n n k=1f (x, ξ k ). As soon as the number of data points n is large, computing the gradient of a finite sum, as it is done in gradientbased methods, is possibly expensive (computing the gradient of each element of the sum, which is possibly very large). Stochastic gradient descent (SGD) provides an alternative with lower computational burden per iteration, by evaluating only the gradient of a singlef (·, ξ i k ) per iteration, where γ > 0 is the step size, ξ i k is drawn uniformly at random in (ξ 1 , ..., ξ n ), and thereby E ξ [∇f (x k , ξ i k )] = f (x k ) is an unbiased estimate of the full gradient. Li et al. [21,22] have proven a connection with stochastic differential equations (SDE): where σ(X t ) is a noise parameter connected to parameters of the method, that was further developed by Shi et al. [36,48]. This connection has raised many questions regarding approximate equivalences between optimization methods and continuoustime models, and tools for analyzing convergence speeds of discrete methods. Usually, gradient flows and first-order methods are studied via worst-case convergence properties, that have to be verified for any function of a given class, and any trajectory generated by the ODE or the optimization method. In many cases, continuous approaches seem to allows for shorter and simpler proofs, together with intuitions on what can be expected from optimization methods.
The analysis of continuous-time models often relies on Lyapunov stability arguments, as in system theory and physics, where energy dissipation plays a crucial role. The existence of such Lyapunov functions provides direct convergence proof for ODEs under consideration. The main challenge in the Lyapunov approach is to find a suitable function that is decreasing along all trajectories generated by an ODE.
From an outsider point of view, these analyses are often seen as complicated and technical to reach. In this work, we remedy this problem by extending the systematic approach based on semidefinite programming (SDP) developed by Drori and Teboulle [9] for certifying convergence of optimization methods. This technique is referred as "performance estimation problems" (PEPs). The main contribution of this work is to provide a tool for simultaneously analyzing convergence of continuous-time models, and constructing Lyapunov functions suited to gradient flows in a systematic way, using small-sized SDPs reformulations. Furthermore, this procedure benefits from tightness properties, meaning that the feasibility of the SDP allows to conclude about the existence of some Lyapunov functions.

Lyapunov functions.
When dealing with convergence rates of gradient flows, many proofs typically rely on a Lyapunov function. In control theory, such functions are common for studying stability of dynamical systems [17]. Definition 1.1. Given a trajectory X t , we call V : R d → R a Lyapunov function if it is differentiable and satisfies the conditions: 1. V(x) = 0 ⇐⇒ x = x ⋆ , 2. V(X t ) 0, 3. d dt V(X t ) 0. Given an ODE starting from x 0 and a class of functions F , a function V(·) is a Lyapunov function if the inequality d dt V(X t ) 0 is verified for all trajectories X t generated by ODEs originating from functions f ∈ F . There exist similar definitions of Lyapunov functions for discrete optimization methods [42,32,20].
Lyapunov functions are suited to deriving both linear and sublinear convergence rates. When looking for linear convergence rates (as we may expect for strongly convex functions), the third condition is typically replaced by d dt V(X t ) −τ V(X t ), where τ depends on the class of functions and on the ODE.
With this approach, convergence guarantees highly depend on the choice of Lyapunov functions. For a specific ODE and class of functions F , there are often multiple choices of valid Lyapunov functions. In this work, we look for Lyapunov functions in a class of quadratic functions that is popular both in the discrete [25,10] and continuous time [37] literature.
1.2. Prior works. Lyapunov functions are common for analyzing continuous and discrete time models in convex optimization. Convergence proofs for Nesterov's accelerated gradient method typically rely on such Lyapunov functions [25], [10,Theorem 4.8]. In the recent work [3], the authors proposed Lyapunov-based analyses for many first-order methods, for linear and sublinear convergence rates. Continuoustime versions of optimization methods also often involve Lyapunov arguments, such as Nesterov's accelerated gradient flow introduced in [37], and its high-resolution ODEs for strongly convex functions proposed in [34], or accelerated mirror descent whose continuous dynamics was analyzed in [18].
Different techniques were developed to compute suitable Lyapunov functions. The authors of [46] proposed an approach based on Bregman Lagrangian for accelerated methods in potentially non-Euclidean settings, further developed in [47]. [8] directly derived Lyapunov functions from Hamiltonian equations describing dynamics of ODEs. Using similar conservation laws in a dilated coordinate system, [38] also generated Lyapunov functions in a principled way.
Given a class of functions and an optimization method, proving a convergence rate mostly consists in combining inequalities characterizing the class of functions at hand. Recently, the automated search for combination of inequalities formulated as semidefinite program was formalized by Drori and Teboulle [9], and led to the notion of performance estimation problems. Their work was followed up in [45,44] to provide worst-case bounds in a principled way, and extended to the Lyapunov framework [42]. A competing strategy inspired by control theory was developed by [20,15], where Lyapunov functions for discrete-time models are constructed using integral quadratic constraints (IQCs) and semidefinite programming; a similar approach was applied to continuous-time models in [11]. Connections between Lyapunov functions obtained via the IQC framework in continuous and discrete-time, were later highlighted by [32].
For stochastic differential equations (SDEs), convergence proofs can also be obtained through the Lyapunov approach, together with Ito's calculus. [26] analyzed both SGD, SAGA [7], and SVRG [16], for some well-chosen Lyapunov functions. [48,49] extended the framework of [46] to the stochastic setting. To the best of our knowledge, a systematic way of verifying a Lyapunov functions in the stochastic setting has not been developed yet.

Contributions and organization.
In this work, we are concerned with worst-case convergence analyses of ordinary and stochastic differential equations, for modeling optimization methods. We propose a principled approach to worst-case analyses based on Lyapunov functions, SDPs and Ito's calculus.
In Section 2, we extend the performance estimation approach developed for optimization methods to gradient flows, that originates from a (possibly strongly) convex function. In short, we find Lyapunov functions as feasible points of certain linear ma-trix inequalities (LMIs). Building on the first part of this work for ODEs, we analyze continuous versions of stochastic optimization algorithms. All codes for numerical results are provided at https://github.com/CMoucer/PEP ODEs.
Section 3 studies properties of trajectories generated by SDEs, as approximations to stochastic gradient methods. We obtain a simple version of the trade-off between forgetting the initial conditions and diminishing the noise, with and without averaging. It appears that decreasing step sizes, together with a non-uniform version of averaging, allows to reach an optimal trade-off. Our results match those obtained for the stochastic gradient method, in a compact way compared with discrete analyses.
In Section 4, we prove that accelerated gradient flows require diminishing step sizes to converge in the stochastic setting. In contrast to first-order stochastic gradient flow, averaging does not preserve convergence for fixed step size.
1.4. Assumptions. Throughout this work, functions to be minimized are convex (see Problem 1.1). Under this assumption, stationary points are global minimizers. We restrict ourselves to continuous-time versions of gradient descent, accelerated gradient descent and stochastic gradient descent. Such methods gather information about functions to be minimized by evaluating its (sub)gradient at past iterates.
Let us recall a few basic definitions and properties characterizing the classes of functions under consideration within the next sections. A function f : We consider in particular the class of convex closed proper (CCP) functions (i.e., functions whose epigraphs are non-empty closed convex sets). For simplicity, we assume in addition differentiability of f , even if results do not require it for convex gradient differential inclusions [4,Section 3.2]. Then, f is convex if and only if for Smoothness is a common assumption for analyzing optimization methods, that limits the growth rate of the function. A function f is L-smooth if the gradient is L-Lipschitz, that is if for any x, y, A differentiable function f is µ-strongly convex if for any x, y ∈ R d it satisfies Strong convexity ensures the function is not too flat, and the unicity of the minimizer x ⋆ . We denote by F µ,L the family of L-smooth µ-strongly closed convex proper functions, with 0 µ L +∞. Weaker assumptions than strong convexity are also encountered in the literature for analyzing gradient algorithms, and leads to similar convergence guarantees. Among them, Lojasiewicz [23] introduced the Lojasiewicz inequality, under which Polyak [28,Theorem 4] showed linear convergence of gradient descent. Other relaxed versions of strong convexity followed [5,24].

2.
A principled approach to Lyapunov functions for gradient flows. In this section, we study convergence properties of the gradient flow and its accelerated versions, via quadratic Lyapunov functions. We prove that verifying such a Lyapunov function can be formulated as a LMI. This framework allows to search for Lyapunov functions, and to derive convergence bounds for non-autonomous gradient flows.
2.1. Gradient flow. We consider the gradient floẇ Without further assumptions, the function f is decreasing along the trajectory X t solution to the gradient flow. The Lyapunov function V(X t ) = f (X t ) has indeed a Under additional convexity assumptions, it is possible to derive Lyapunov functions in a principled way, and deduce worst-case convergence speeds of the gradient flow. As a first stage, let us consider gradient flows originating from strongly convex functions and establish linear (or exponential) convergence of the flows.
This convergence guarantee follows directly from the time-derivative of the Lyapunov function V(X t ) = f (X t ) − f ⋆ , together with strong convexity (or Lojasiewicz Given the specific gradient flows studied in this work, it is reasonable to search for Lyapunov functions made of linear combinations of function values, and a quadratic form in the trajectory X t . We simply refer to them as quadratic Lyapunov functions: where a, c are fixed nonnegative constants that do not depend on t. Such Lyapunov functions are common for proving convergence of gradient flows (and of optimization methods), and cover for instance the Lyapunov used to prove convergence of the gradient flow under strong convexity (2.1). Given a Lyapunov function V a,c , the idea is to find the smallest value of τ such that the condition holds for any functions f ∈ F µ,∞ and any trajectory X t generated by the gradient flow. After integrating, a convergence guarantee in function values is given by V a,c (X t ) e −τ t V a,c (X 0 ). Given a certain Lyapunov function V a,c and a time t, we get that the largest acceptable τ is a solution to: subject to V a,c (X t ) = 1, This minimization problem is invariant in t. It is established in [45,9] that these so-called performance estimation problems (PEP) can be formulated as SDPs (details are provided in Appendix A.1 for completeness). Because of the condition f ∈ F µ,∞ , the maximization problem (2.4) is infinite-dimensional. Recall that a differentiable function f ∈ F µ,∞ verifies for all points Introducing alternate variables f t , f ⋆ , g t and g ⋆ (informally: subject to V a,c (X t ) = 1, The fact (2.5) produces an upper bound on −τ directly follows from the fact that any sampled strongly convex function satisfy these inequalities at the sampled points X t and x ⋆ . Thereby, any feasible point to (2.4) corresponds to a feasible for (2.5) with the same objective value. In the other direction, [45,Corollary 2] (which provides a constructive way to obtain some f ∈ F µ,∞ that interpolates the triplets (X i , g i , f i ) t,⋆ ) ensures that any feasible point to (2.5) can be translated to a feasible point to (2.4) with also the same objective value, thereby reaching the equivalence between formulations (2.4) and (2.5).
In a second stage, we introduce G = a Gram matrix and a vector F = [f t , f ⋆ ], thereby obtaining a semidefinite reformulation: Those developments allow arriving to the following worst-case results.
Theorem 2.1. Let V a,c be a quadratic Lyapunov function (2.2) with a, c 0, τ 0, and functions f ∈ F µ,∞ be strongly convex with parameter µ > 0. We consider gradient flows (1.3) originating from functions f ∈ F µ,∞ and starting from an initial point x 0 ∈ R d , where d ∈ N is the dimension. The following assertions are equivalent: is satisfied for all f ∈ F µ,∞ , all trajectories X t solutions to the gradient flow and all dimensions d ∈ N.
• There exist λ 1 , λ 2 0 such that Proof. The procedure to obtain the LMI is fully detailed in Appendix A.1, and consists in taking the standard Lagrangian dual of the SDP (2.6).
A few conclusions can be drawn from the LMI equivalence from Theorem 2.1. First, it provides a necessary and sufficient condition for a quadratic Lyapunov function V a,c to decrease at a specific rate τ 0 for all functions f ∈ F µ,∞ . The infeasibility of the LMI allows to conclude about the existence of a Lyapunov function such that the rate τ is achieved for all functions in the class. Second, it is possible to search over the class of quadratic Lyapunov functions that certify linear convergence. Given a rate τ , the LMI is indeed jointly convex in λ 1 , λ 2 , a, c. Finally, thanks to linearity of the feasibility problem in τ , a bisection search allows to optimize over the convergence rate. In other words, we can optimize jointly over the Lyapunov function and the worst-case guarantee.  In Figure 1a, we obtain the fastest linear convergence rate that can be achieved using quadratic Lyapunov functions. Together with Theorem 2.1 we retrieve the known linear worst-case convergence speed in e −2µ from Scieur et al. [33, Proposition 1.1], without improvement. The numerical approach though allows to ensure tightness with a numerical function f that matches this convergence guarantee (see Figure 1b and the method in [43,Chapter 3]). Let us build on these results to analyze the gradient flow originating from a (possibly non strongly) convex function, where the difficulty comes from the time-dependence of Lyapunov functions. Following theorems are obtained using the same methodology.

Minimizing convex functions.
In the case where f ∈ F 0,∞ , worst-case convergence rates often are sublinear. Again, as in discrete time, it is possible to obtain convergence guarantees using time-dependent quadratic Lyapunov functions.
for any functions f ∈ F 0,∞ , and any trajectories X t generated by the gradient flow ( using convexity). After integrating, we recover a convergence bound in function values from the literature [37, p.7], [11,Section 6 We consider the family of quadratic Lyapunov functions: where a t , c t are differentiable functions from R + to R + . When the Lyapunov function is decreasing along the trajectory X t , that is d dt V(X t ) 0, a convergence guarantee in function values is given by Looking for a worst-case guarantee with a Lyapunov approach can be cast as: Remark 2.2. The strongly convex case as defined above is a particular case of the convex one, using a specific Lyapunov function ) be a quadratic Lyapunov function for a t , c t nonnegative differentiable functions and functions f ∈ F 0,∞ be convex. Given the gradient flow (1.3) originating from convex functions f ∈ F 0,∞ and starting from x 0 ∈ R d , where d ∈ N is the dimension. The following assertions are equivalent: If these assertions are satisfied, c t is decreasing, and a t tc t .
Proof. The LMI is obtained following the previous methodology (Appendix A.1), and the inequality a t tc t directly from the LMI.
Choosing c t = 1 2 and a t = t for the Lyapunov function parameters, and λ for all convex functions f ∈ F 0,∞ , for all trajectories X t generated by the gradient flow, and all dimensions d ∈ N.
The differential LMI equivalence from Theorem 2.3 is jointly convex in λ introducing derivatives (to be compared with iterates for discrete optimization methods). In contrast with the minimization of strongly convex functions, numerically solving this LMI is not available because of the dependence in t. Other quadratic Lyapunov functions could be derived. However, the condition a t c t t together withċ t 0 implies that the convergence cannot be faster than 1 t . 2.2. Accelerated gradient flows. A major improvement to gradient descent dates back to Nesterov in 1983 [25], with an accelerated gradient method (AGM), where γ, α k are nonnegative parameters depending on the class of functions to minimize. The current iterate is computed thanks to a so-called momentum. This combination of past iterates allows more control over the accumulated error. This idea was first introduced by Polyak [27] with the heavy-ball method, starting from where α k > 0 is the momentum method. Yet, compared with Nesterov's accelerated gradient method, the heavy-ball method lacks global acceleration beyond quadratics.
When reducing the step size γ, these schemes happen to be closely related to second-order differential equations, for β t 0 a function that depends on α k , Recently, accelerated gradient methods have been analyzed using second-order differential equations [34,32,47,15]. Reversely, the accelerated gradient method and the heavy-ball method may be seen as discretization schemes of these second order ODEs, as many other schemes. Discretization techniques are, among others, discussed by [48,36,47]. Taking integration theory's point of view, Scieur et al. [33] proved that these multi-step methods may even be seen as discretization schemes of the gradient flow (for quadratics).
Again, ODEs and multi-step first-order methods as defined above are often handled using quadratic Lyapunov functions. We extend the systematic Lyapunov approach developed previously to accelerated gradient flows. Let V at,Pt be the family of quadratic Lyapunov functions for second-order gradient flows, is a symmetric matrix with differentiable parameters, and a t is a differentiable function, such that the Lyapunov is nonnegative when evaluated on the gradient flow. After integrating, this approach leads to convergence bounds for instance in function values, such that f at .
2.2.1. Minimizing strongly convex functions. Let f ∈ F µ,L , with strong convexity parameter µ > 0, and scheme parameters be defined by γ = 1 √ µγ in Nesterov's accelerated gradient methods (2.9). When reducing the step size γ, the continuous-time limit of y k in (2.9) is exactly the Polyak damped oscillator [27], where t = γk, as it has already been highlighted in previous works [11,32,34]. This ODE is also the limit of the heavy-ball method (2.10). Shi et al. [34] proved a convergence guarantee in f Wilson et al. [47,Appendix B] using the Bregman-Lagrangian approach, and by Sanz-Serna and Zygalakis using the IQC framework [32,11]. We compute linear convergence guarantees using quadratic Lyapunov functions with constant parameters (2.11).
Theorem 2.4. Let V a,P be a quadratic Lyapunov function (2.11), where a 0, and P a symmetric matrix. Let τ 0, µ 0, d ∈ N be the dimension, and the Polyak damped oscillator (2.12) be starting from x 0 ∈ R d , and originating from strongly convex functions f ∈ F µ,∞ . The following assertions are equivalent: is satisfied for all functions f ∈ F µ,∞ , all trajectories X t generated by Polyak damped oscillator, and all di- Proof. The LMI equivalence is obtained introducing the Gram matrix G = P ⊤ P , where P = (Ẋ t , X t − x ⋆ , g t ) and using the PEP methodology. The first LMI refers to the non-increasing condition for the Lyapunov function, and the second LMI to the positivity of the Lyapunov for all trajectories and convex functions.
The LMI is a feasibility problem, jointly convex in λ 1 , λ 2 , ν 1 , ν 2 0 and in Lyapunov parameters a, P . Given parameters a, P and a rate τ , it is a verification tool for V a,P to be a Lyapunov function decreasing at rate τ . As for gradient flows, we can perform a bisection search over τ to find the fastest linear convergence rate that can be verified using quadratic Lyapunov functions (see Figure 2a). It provides a numerical tool for choosing Lyapunov parameters (Figure 2b) for which the worst-case linear convergence rate is achieved.
Corollary 2.5. Let us consider the Polyak damped oscillator (2.12) starting from x 0 ∈ R d where d ∈ N is the dimension, and originating from strongly convex for all functions f ∈ F µ,∞ , all trajectories X t generated by Polyak damped oscillator, and all dimensions d ∈ N.
This class of quadratic Lyapunov functions is inspired by [42] in discrete time, where a stricter positivity condition on P 0 hindered proving tight convergence of Nesterov's accelerated gradient. Similarly, the Lyapunov function from Corollary 2.12 for all functions f ∈ F µ,∞ , all trajectories X t generated by Polyak damped oscillator, and all dimensions d ∈ N. This Lyapunov is a feasible point of the LMI (2.13) from Theorem 2.   Strong convexity parameter µ Lyapunov parameters and a = 1, as a function of the condition number µ.
Su et al. [37,Theorem 3] proved the following inequality is verified for all functions f and all trajectories X t generated by AGF, Their proof exhibits a Lyapunov function V(X t , t 0 by convexity of f ). The following theorem provides a systematic condition for a quadratic function V (2.11) to be a Lyapunov function for AGF (2.14).
Theorem 2.6. Let V at,Pt be a quadratic Lyapunov function (2.11), where a t 0 is a differentiable function, and P t 0 with differentiable parameters. Given the accelerated gradient flow (2.14) starting from x 0 ∈ R d where d ∈ N is the dimension, and originating from convex functions f ∈ F 0,∞ , the following assertions are equivalent: • The inequality d dt V at,Pt (X t , t) 0 is satisfied for all functions f ∈ F 0,∞ , all trajectories X t generated by the accelerated gradient flow and all dimensions d ∈ N.
Proof. The proof follows those from Theorem 2.4 and 2.1.
The LMI from Theorem 2.6 is differentiable and convex in λ t . Even when studying second-order gradient flows, the number of interpolation inequalities (or of dual values λ (i) t ) is bounded by two, enforcing short proofs. Theorem 2.6 allows to retrieve the Lyapunov function exhibited by Su et al. [37,Theorem 3], and its associated convergence guarantee. Choosing a t = t 2 and P t = 2 1 t/2 t/2 t 2 /4 for the Lyapunov parameters, and λ , for all functions f ∈ F 0,∞ , for all trajectories X t generated accelerated gradient flows, and all dimensions d ∈ N. As for gradient flows originating from convex functions, we did not compute numerically worst-case scenarios because of the time-dependence of the Lyapunov function.
2.3. Higher-order convergence and time dilation. In this section, we analyze convergence of non-autonomous gradient flows, and provide convergence rates depending on their parameters. It appears that higher order convergence of gradient flows is highly connected to time dilation.
2.3.1. Non-autonomous first-order gradient flow. Let f be a convex function, and X t be the solution to the non-autonomous first-order gradient flow, where α t 0 is a continuous function (such that the flow is converging). It is natural to wonder if it is possible to accelerate such gradient flows when changing α t . A change of variable connects this ODE to the gradient flow (1.3), for which α t = 1. Let Y t be the solution to the gradient flow, and τ t = t 0 α s ds be a time change variable. Then, , which is exactly the non-autonomous gradient flow. The following corollaries can be obtained by performing the appropriate change of variable in LMI from Theorem 2.3.
Corollary 2.7. Let us consider non-autonomous gradient flows (2.15) starting from x 0 ∈ R d where d ∈ N is the dimension, and originating from possibly strongly convex functions f ∈ F µ,∞ , where µ 0.
0 for all functions f ∈ F 0,∞ , for all trajectories X t generated by non-autonomous gradient flows and all dimensions d ∈ N.
A convergence guarantee is given by , all trajectories X t generated by the non-autonomous gradient flow and all dimensions d ∈ N.
A convergence guarantee is given by . Remark 2.8. When considering α t = 1 above, that is τ t = t, we recover exactly the results from Theorem 2.1 and Theorem 2.3.
As mentioned by Orvieto and Lucchi [26] in the stochastic setting, and for accelerated methods by Wibisono et al. [46], one can thus either work with Y t generated by the non-autonomous gradient flow (2.15), or with X t generated by the gradient flow. However, the acceleration on Y t is not preserved after discretizing the flow. Applying explicit Euler scheme to a non-autonomous gradient flow (2.15) with α s = α > 0 and originating from f ∈ F 0,L , a condition on step sizes h > 0 arises 0 h 2 Lα . When focusing on continuous-time models for analyzing explicit optimization methods, that only calls for past gradient iterates, we prefer working with the gradient flow (1.3). However, non-autonomous gradient flows (2.15) may be useful for analyzing other methods such as proximal methods. More generally, and in the next section, we analyze gradient flows without adjusting the time scale (taking α t = 1).

2.3.2.
A non-autonomous second-order gradient flows. Nesterov's accelerated gradient flow reaches an 1 t 2 convergence (see Theorem 2.6) in function values. Considering the family of quadratic Lyapunov functions (2.11), we study convergence of non-autonomous second-order gradient flows and draw comparison with the accelerated gradient flow. Let β t 0 be a continuous function, and a second-order non-autonomous ODE, (2) t 0, there is no time change formula that connects their associated ODE. In other words, they are in the same time-scale. Theorem 2.10 provides an LMI equivalence for analyzing convergence of trajectories X t generated by second-order gradient flows (2.16) using quadratic Lyapunov functions (2.11).
Theorem 2.10. Let us consider V at,Pt quadratic Lyapunov functions (2.11), and non-autonomous second-order gradient flows (2.16) starting from x 0 ∈ R d where d ∈ N is the dimension, and originating from possibly non-strongly convex functions f ∈ F µ,∞ where µ 0. The following assertions are equivalent: • The inequality d dt V at,Pt (X t , t) 0 is satisfied for all functions f ∈ F µ,∞ , for X t generated by non-autonomous second-order gradient flows, and all dimen- For a given function β t 0, the LMI remains convex in λ (1) t , λ (2) t 0. Compared with the LMI derived from Nesterov's accelerated gradient method in Theorem 2.6, the LMI is parametrized by β t .
Corollary 2.11. Let us consider non-autonomous second-order gradient flows starting from x 0 ∈ R d (2.16) where d ∈ N is the dimension, and originating from possibly non-strongly convex functions f ∈ F µ,∞ where µ 0. The Lyapunov function Proof. The proof follows from Theorem 2.10, and is detailed in Appendix A.2.
Non-autonomous second-order gradient flows (2.16) cannot converge faster than Nesterov's accelerated gradient flow in function values, that is to say not faster than 1 t 2 , when using quadratic Lyapunov functions parametrized by β t 0 from Corollary 2.11. To analyze Nesterov's accelerated gradient methods using ODEs, Su et al. [37] introduced parametrized second-order gradient flows, that fit the model (2.16), holds for all convex functions f and all trajectories X t generated by accelerated gradient flows [ Remark 2.12. Polynomial convergence can be achieved up to a change of variable, as it was shown by Wisobono et al. [46] with τ t = t p/2 (α t = p 2 t p/2−1 ). Nesterov's accelerated gradient flow (r = 3) has an ODEẌ t + p+1 tẊ t + p 2 4 t p−2 ∇f (X t ) = 0 for p 2. For all convex functions and all trajectories X t generated by the ODE starting from x 0 , a convergence bound in function value is given by f We have extended the performance estimation approach to continuous-time models, using Lyapunov functions. Given an ODE and a class of functions, we presented a semidefinite formulation equivalent with the existence of a quadratic Lyapunov function. This LMI provides a principled way to generate Lyapunov functions, even when dealing with non-autonomous parametrized ODEs. It turns out only two convex inequalities (in (X t , x ⋆ ) and (x ⋆ , X t ), see Theorem 2.6) are involved in convergence proofs for continuous-time models. For strongly convex functions, we proved numerically worst-case guarantees from Corollary 2.1 and cannot be improved using a specific family of quadratic Lyapunov functions. Even if the connection between discrete and continuous-time does not allow to directly transfer results to the analysis of first-order methods, their convergence analyses are be closely related.

SDEs for modeling SGD.
Convergence results for stochastic convex optimization often require additional assumptions on function classes, refined choices of step sizes and averaged iterates. Their analyses raise challenges and more complex proofs in contrast with deterministic methods. Prior works have been concerned with the connection between stochastic methods and stochastic differential equations (SDEs) [21,26,48]. This section is devoted to convergence analyses of SDEs using the Lyapunov framework. As for ODEs, verifying a Lyapunov function will be cast as verifying the feasibility of a small-sized LMI.
Let us recall the stochastic gradient descent method (SGD) where γ > 0 is the step size, ξ i k are uniformly drawn in (ξ 1 , ..., ξ n ), and where ∇f (x k , ξ i k ) is an unbiased estimate of full gradient ∇f (x k ). Li et al. [21] introduced stochastic modified equations (SMEs) to model SGD, rewriting it as has zero mean and a covariance matrix equal . The corresponding SDE is given by where B t is a standard Brownian motion, is an (order-1 weak) approximation of SGD ([21, Theorem 1], [22]). The SDE approximation of SGD allows to take into account the role of fixed step size in the dynamics of SGD (while keeping them small).
Under mild assumptions on f , Li et al. proved the weak approximation of SGD by this SDE on a finite interval [0, T ]: there exists C > 0 such that However, this approach is limited since C depends exponentially on T . In the literature, matching rates are often obtained extending Lyapunov functions from continuous to discrete time [35,26,34].
Remark 3.1. The SDE (3.2) is an approximation of SGD for small step sizes γ. When taking the step size to zero, the noise term actually disappears, and the limiting ODE of SGD is exactly the gradient flow (1.3). Similarly, the stochastic Langevin dynamics x k+1 = x k − γ∇f (x k ) − √ γξ k has the limiting ODE dX t = −∇f (X t )dt + √ 2dB t , where the step size is not taken into account.
Compared with the gradient flow, SGD does not converge to a stationary point under fixed step sizes [2,41]. Convergence to a stationary point requires diminishing step sizes such as γ k = 1 √ k . Li et al. [21,Section 4.1] (and later Orvieto and Lucchi [26, Section 2.1]) proposed to include this varying learning rate in the dynamics: where γ is the maximum allowed learning rate and h k ∈ [0, 1] is the varying part. For h t 0 a continuous function corresponding to discrete h k , the SDE is given by We treat the covariance matrix Σ(X t ) as symmetric, already implied by the notation Σ(X t ) 1/2 , but unstructured with bounded variance Σ(X t ) Σ along any trajectory X t generated by the approximating SDE (3.3). Compared to ODEs, functions f ∈ F 0,L to be optimized using SDEs are in addition assumed to be possibly L-smooth with L ∈ (0, ∞], and to be twice differentiable. We propose to analyze approximating SDEs with averaging techniques, and to include later varying step sizes. Verifying Lyapunov functions thanks to small-sizes LMI, we retrieve convergence results from discrete optimization methods, using appropriate choices of step sizes.

Lyapunov functions do not always extend to the stochastic setting.
The analysis of the gradient flow in the deterministic case provides Lyapunov functions that are decreasing along trajectories generated by ODEs. The direct transfer of these Lyapunov functions to the stochastic setting is not always suited to the variance term, as detailed below. Under constant step sizes γ > 0, an approximating SDE of SGD is dX t = −∇f (X t )dt + (γΣ(X t )) 1/2 dB t .
In SDE theory, a time-differential of a function of a solution to a stochastic process is given by Ito's Lemma [39,Theorem 4.2].
Lemma 3.2 (Ito's Lemma). For g a twice differentiable function, and X t a stochastic process solution to the SDE (3.2), 3.1.1. Minimizing strongly convex functions. When the SDE originates from (possibly non-smooth) strongly convex functions f ∈ F µ,∞ , the Lyapunov function from the deterministic setting extends well to SDEs. In the deterministic setting, we have shown in Theorem 2.1 that the function V(x, t) = e 2µt (f (x) − f ⋆ ) is a Lyapunov function in the worst-case. Applying Ito's formula to this Lyapunov function with X t a solution to the SDE (3.2), we obtain d dt EV(X t , t) 1 2 e 2µt γETr(∇ 2 xx f (X t )Σ(X t )). After integrating between 0 and t, we have Additional requirements on f , such as smoothness and twice differentiability, are needed for convergence. For example, if f is in addition L-smooth with L < ∞ and using the bounded covariance assumption Σ(X t ) Σ, the variance term is bounded by 1 2 LγTr(Σ). Under constant step sizes, the SDE approximating SGD converges to a diffusion, and cannot get to a stationary point x ⋆ in the worst-case, but the extra term is linear in the step size γ. As in the deterministic case, the forgetting of initial conditions remains of order O(e −2µt ).

Minimizing convex functions.
When f ∈ F 0,∞ , Lyapunov functions induce convergence bounds with a possibly diverging variance term. When considering deterministic gradient flows (1.3) originating from convex functions, a Lyapunov function followed from Theorem 2.3: Assuming X t are solutions X t to SDEs (3.2) originating from convex functions f ∈ F 0,∞ , we compute the derivative to this Lyapunov function thanks to Ito's formula ). Thanks to twice differentiability, bounded covariance Σ(X t ) Σ, and assuming in addition L-smoothness of f , a convergence bound is given by Taylor and Bach proved a comparable convergence bound for SGD [41,Theorem 5], applying the Lyapunov performance estimation approach under similar assumptions (bounded variance, smoothness of f ). Tough, we cannot conclude about convergence of SGD in the worst-case without further assumptions. Optimization methods have been developed to ensure the global convergence of SGD to the optimum, among them averaging [30] and diminishing step sizes.
3.2. Diminishing the step size is a key to success. We study convergence of SDEs with varying step sizes (3.3). In contrast to the deterministic setting, in which varying step sizes correspond to a time rescaling, the time change plays a direct role on the variance term (explicit formula by Orvieto and Lucchi in [26,Theorem 5]). Our problem can be formulated as follows, where V are Lyapunov functions, is computed with Ito's formula. The first two terms corresponds exactly to taking the derivative in trajectories generated by ODEs (2.15) (or the SDEs (3.3) with γ = 0), and the last term to a variance term. Because of the trace in a second-order derivative and in the covariance matrix Σ(X t ), we do not take this term into account in an LMI reformulation. Instead, we propose to first derive a family of Lyapunov functions using LMIs from the deterministic setting, and then to optimize their parameters so that the variance term converges conveniently. Corollary 3.3. Let f ∈ F 0,∞ be twice differentiable functions, and let us consider SDEs with varying step sizes (3.3) starting from X 0 ∈ R d , where d ∈ N is the dimension. The quadratic Lyapunov function from the family (2.8) twice differentiable functions f ∈ F 0,∞ , all trajectories X t generated by SDEs (3.3), Proof. The Lyapunov function V directly comes from Corollary 2.7, for nonautonomous first-order gradient flows. The bound on E[f (X t ) − f ⋆ ] is obtained using Ito's formula on V along trajectories X t generated by approximating SDEs (3.3).
The convergence bound from Corollary 3.3 is divided into two terms: a term that forgets the initial conditions and a variance term due to noise. Convergence is mostly controlled by the step size (ȧ (1) t = 2h t ). Bach and Moulines [2, Theorem 5] provided a comparable but much more complex analysis for stochastic gradient descent, for a specific family of step sizes. Let us compare our results, assuming h t = 1 (t+1) α , where α 0. The Lyapunov function from Corollary 3.3 is given by The forgetting of the initial condition is thus bounded by x0−x⋆ 2 (t+1) 1−α . Provided Σ(X t ) Σ, the variance term is bounded by: Because of the variance term, the Lyapunov converges if and only if α 1 2 . In other words, convergence is not guaranteed for constant step sizes (α = 0). If α ∈ (1/2, 2/3), the convergence in function value is bounded by O( 1 t 2α−1 ). If α ∈ (2/3, 1), the convergence in function value is bounded by O( 1 t 1−α ). As for SGD [2, Theorem 5], the convergence regime changes at α = 2 3 with a global convergence rate in 1 t 1/3 , for which the variance term and the term that forgets the initial conditions converges at the same rate (up to log(t)). It is therefore possible to reach convergence with diminishing step sizes. Other techniques have been developed to improve the tradeoff between faster convergence and larger step sizes.
3.3. Averaging for larger step sizes. Polyak-Ruppert averaging [30,29] is a standard way to improve convergence of SGD. In the discrete setting, convergence guarantees are considered at an averaged sequence defined by: Other averaging techniques were later developed, such as primal averaging [40] and averaging with respect to some nonnegative function [19]. Primal averaging is detailed for comparison in Appendix C.

Polyak-Ruppert averaging.
In this section, we analyze convergence properties of SDEs (3.3) with varying step sizes under Polyak-Ruppert averaging. Taylor and Bach [41, Theorem 6] provided a decreasing Lyapunov function along (x k , x k ) (3.4), and a condition on the step size for convergence to the optimum. An approximating SDE for Polyak-Ruppert averaging is: with step size γ > 0 that is taken close to zero, and a variable term h t ∈ [0, 1]. We introduce the family of quadratic Lyapunov functions: (2) t 0 are differentiable real functions, and P t = p t ,Pt , and SDEs (3.5), the performance estimation problem is formulated by: A possible control of this quantity is presented in Theorem 3.4.
Theorem 3.4. Let f ∈ F 0,∞ be twice differentiable functions, and SDEs be taken under Polyak-Ruppert averaging (3.5) starting from x 0 ∈ R d , where d ∈ N is the dimension, and V be quadratic Lyapunov functions defined by (3.6). The following assertions are equivalent, t ∇ xx f (X t ) + 2p (11) t I d )Σ(X t ))h 2 t γ is satisfied for all functions f ∈ F 0,∞ , all trajectories (X t ,X t ) generated by SDEs under Polyak-Ruppert averaging (3.5), and all dimensions d ∈ N.
Proof. The proof follows the methodology from Section 2.1.1, and using the Gram The variance term increases with a (1) t , and its convergence requires an additional smoothness assumption on f . For this reason, we propose to analyze the convergence based on Lyapunov functions on the averaged sequence only (V 0,a (2) t ,Pt ).
Corollary 3.5 (Averaging and diminishing step sizes). Let f ∈ F 0,∞ be twice differentiable functions, SDEs be taken under Polyak-Ruppert averaging (3.5) starting tht is a non-increasing function, the Lyapunov function for all twice differentiable functions f ∈ F 0,∞ , all trajectories X t generated by SDEs (3.5) and all dimensions d ∈ N. Then, Proof. The proof follows from Theorem 3.4 (see Appendix B.1).
When a Under the assumptions of Corollary 3.5, let us consider a bounded covariance matrix Σ(X t ) Σ, a step size h t = 1 (t+1) α , and a (2) t = t β for α 0 and 0 β 1 some parameters. The decreasing condition imposes α + β 1. A different behavior is expected from α and β: on the one hand, an ideal step size should be large (α small), and on the other hand, we aim at converging as fast as possible (β large). The term that forgets the initial conditions is bounded by O( 1 t β ), and the variance term by O( 1 t α ) if β = α. When α = β, the variance term is in log(t) 2t β . Hence, a natural choice is α = β = 1 2 , retrieving results from [2, Theorem 4] [41, Table 2] in discrete optimization.

Weighted averaging.
Polyak-Ruppert performs uniform averaging of trajectories X t over the time step. We introduce weighted averaging to analyze SGD, that is defined with respect to a function u t 0 [19], Under weighted averaging, and with C u t = ut t 0 usds , the SDE is We study convergence of this generalized version of Polyak-Ruppert averaging, and compare it to traditional averaging techniques.
Theorem 3.6. Let f ∈ F µ,∞ be twice differentiable functions, possibly strongly convex µ 0, and SDEs be given by (3.7), starting from x 0 ∈ R d where d ∈ N is the dimension. Assuming˙ ut 2ht 2µu t , the Lyapunov function verifies d dt EV(X t ,X u t , t) 1 2 u t h t γTr(Σ(X t )) for all twice differentiable functions f ∈ F 0,∞ , all trajectories (X t ,X t ) generated by SDEs with averaging (3.7), and all dimensions d ∈ N.
For strongly convex functions f ∈ F µ,∞ , polynomial convergence can be reached for the term that contains the initial conditions. However, the variance term cannot converge faster than the step size. Given a bounded covariance matrix Σ(X t ) Σ, the variance term behaves after integrating by part h t . Hence, averaging allows a better convergence for the terms containing initial conditions, but does not play a role in the variance term. To conclude, weighted averaging does not improve convergence results obtained under Polyak-Ruppert or primal averaging. The trade-off between the forgetting of the initial conditions and the noise term mostly relies on step sizes.
We have analyzed convergence of SGD together with averaging techniques in continuous-time, using approximating SDEs (3.3). Compared with discrete time, the continuous-time analysis leads to similar convergence results, while benefiting from simpler formulations, fewer assumptions especially on step sizes. Using this approach, we analyzed the trade-off between non-uniform averaging and step sizes, paving the way to a better understanding of averaging techniques. In the next session, we explore new convergence analyses for stochastic accelerated methods.
4. Accelerating the gradient flow. For both stochastic and deterministic models, we have retrieved known convergence results for continuous-time models approximating optimization methods. In this section, we provide convergence guarantees for second order gradient flows, and in particular for AGF (2.14).
In the deterministic setting, convergence of gradient descent was improved using a momentum. In this section, let f ∈ F 0,∞ be twice differentiable function and γ > 0 be constant step sizes. Li [22,Theorem 16,Section 4.4] proved that Nesterov accelerated gradient has the approximating SDE (for order-1 weak approximations), As for SGD, the Lyapunov function V( 2 obtained from Theorem 2.6 does not allow to conclude about convergence to a stationary point of trajectories X t generated by stochastic accelerated gradient flows (4.1). Assuming bounded covariance Σ(X t ) Σ and applying Ito's formula to V(·) along X t , In the following, we explore Polyak-Ruppert averaging together with diminishing step sizes, to analyze convergence of second-order SDEs.
4.1. Averaging does not preserve convergence rates. Averaging was a key to success for improving convergence of SGD (see Section 3). It is natural to wonder if averaging preserves the acceleration of Nesterov's gradient flow [37]. Let us define stochastic sedond-order gradient flows with Polyak-Ruppert averaging: where β t 0 is a function, and a family of quadratic Lyapunov functions, where P t 0 and a (1) t , a (2) t 0 are differentiable functions.
t ,Pt be quadratic Lyapunov functions, and stochastic accelerated gradient flows under Polyak-Ruppert averaging (4.2) with constant step sizes h t = 1, starting from x 0 ∈ R d , where d ∈ N is the dimension. Then it holds that: • When a (1) γΣ(X t )) for all twice-differentiable functions f ∈ F 0,∞ , all trajectories (X t ,X t ) generated by SDEs (4.2), and all dimensions d ∈ N, then V = 0.
• When a (2) t γΣ(X t )), with a (1) t t 2 for all functions f ∈ F 0,∞ , all trajectories X t generated by stochastic second-order gradient flows (4.2) and all dimensions d ∈ N. Then, it holds that Proof. The proof follow from Theorem 2.10 (see Appendix B.3).
To conclude, with constant step sizes, there is no Lyapunov functions that allows to forget the initial conditions while reducing the variance term. Primal averaging leads to similar results (see Appendix C). Therefore, averaging plays a different role in second-order SDEs than in first-order SDEs under Polyak-Ruppert averaging.

Diminishing step sizes.
Averaging was not conclusive for finding a convergence guarantee of Nesterov's accelerated gradient flow with a diffusion term. Let us consider second-order stochastic gradient flows with varying step sizes h t 0, We propose a Lyapunov function among the class of quadratic functions (2.11).
Theorem 4.2. Let f ∈ F 0,∞ be twice differentiable functions, X t be a trajectory generated by stochastic second-order gradient flows (4.4) with varying step sizes h t 0 and γ > 0, starting from x 0 ∈ R d , where d ∈ N is the dimension. Assuminġ a t a t 2 3 (β t + 1 2ḣ t ht ) and t → (ȧt) 2 2htat a decreasing function, the Lyapunov function verifies d dt EV(X t , t) 1 4 Tr(a t h t Σ(X t ))γ for all functions f ∈ F 0,∞ , all trajectories X t generated by stochastic second-order gradient flows (4.4) and all dimensions d ∈ N.
Proof. This result is obtained extending the LMI for ODEs from Theorem 2.10 and Corollary 2.11 to varying step sizes.
Let us now assume that h t = 1 (t+1) α and β t = b t , where α, b > 0. It follows from Theorem 4.2, thatȧ t β at t , where β 2b−α 3 and α + β 2, and We assume bounded covariance of Σ(X t ) Σ, then β min( 2b−α 3 , 2 − α). On the one hand, the smaller the step sizes, the better the convergence for the term that contains the initial conditions. On the other hand, the variance term behaves as 1 t β if β α − 1, and as 1 t α−1 otherwise (convergence requiring then α 1 and β 1). For Nesterov's accelerated gradient flow with b = 3, we have β = 2 − α α − 1, and therefore α 3 2 . Taking α = 3 2 , a convergence bound is given by: We retrieve result from Corollary 3.5 for the SDE approximating SGD with Polyak-Ruppert averaging, with smaller step sizes. It does not seem possible to accelerate SGD when diminishing the step size. Ghadimi and Lan [31, Corollary 3] proved a convergence bound for a randomized stochastic accelerated gradient method with β = 2 and α = 1 2 , that we do not retrieved. However, in their approach, the function is minimized over a compact, convex domain, whereas our approach focuses on an unbounded domain.

5.
Conclusion and future work. We have developed a systematic approach for generating Lyapunov functions for families of ODEs and SDEs. Verifying such a Lyapunov function can be formulated as an LMI. From this formulation, it is possible to derive Lyapunov functions and the associated convergence bounds. We retrieve results from discrete optimization methods with shorter proofs, and fewer assumptions.
While obtaining guarantees for stochastic optimization methods might be tedious, the SDE approach allows for simpler analyses of the trade-off between the variance term and term that forgets the initial conditions. A shortcoming of this approach is that this analysis does not include approximation guarantees between optimization methods and their continuous-time counterparts. In the deterministic setting, stability techniques are often developed to quantify this approximation efficiency [13]. In stochastic analysis, stochastic modified equation have been introduced by Li et al. [21, Theorem 1] to better approximate SGD, and stochastic methods with momentum. For non-convex functions, some analysis have also been done by Shi et al [36]. However, these approximation theorems often require many assumptions on the class of functions, which we believe could be further simplified using computer-assisted proofs.
Appendix A. Proof for ODEs.
Proof. Let us consider X t a solution to the gradient flow (1.3) starting from x 0 ∈ R d , and a quadratic Lyapunov function of the form V at,ct (X t , t) = a t · (f (X t ) − f ⋆ ) + c t · X t − x ⋆ 2 such that a t , c t are differentiable and V at,ct is nonnegative over the trajectory X t . The family of function f is supposed to be µ-strongly convex, with µ 0. We are going to prove the LMI equivalence of Theorem 2.3 and Theorem 2.1.
Let us first rephrase our objective, that is computing a Lyapunov function that is decreasing along X t .
Since f ∈ F µ,∞ , this problem is at first sight infinite-dimensional, and thus not easily solvable. Let us reformulate it as an feasibility condition over the class of functions,

max
Xt∈R d ,d∈N d dt V at,ct (X t , t), ∃f ∈ F µ,∞ : This problem remains infinite-dimensional, but we can reformulate it thanks to an interpolation theorem of the class of functions F µ,L on (X i , g i , f i ), with 0 µ L ∞. A set {(X i , g i , f i ) i∈I } is said to be F µ,L -interpolable if there exist f ∈ F µ,L such that f i = f (X i ) and g i = ∇f (X i ) for all i ∈ I. It turns out that the formulation for this class of functions is quite simple.
Theorem A.1. [45,Theorem 4]: Set {(X i , g i , f i )} i∈I if F µ,L interpolable if and only if the following set of conditions holds for every pair of indices i ∈ I and j ∈ J .
This theorem allows to replace the problem above by a quadratic program, linear in f t , f ⋆ ) and quadratic in (x t , g t , x ⋆ ).

max
Let G be a Gram matrix defined by G = X t − x ⋆ 2 X t − x ⋆ , g t X t − x ⋆ , g t g t In this convex case, strong duality holds via Slater's conditions [45,Theorem 6]. Consider the Lagrangian dual of the SDP, that can be cast as a minimization problem at time t, t ,Pt (X t ,X t , t), subject to dX t = −h t ∇f (X t )dt + h t (γΣ(X t )) 1/2 dB t , dX t = X t −X t t dt.
Let us rewrite the SDE, Let us denote Y t = X t X t , and V a (1) t ,Pt (X t ,X t , t) = V(Y t , t), ]. Then, we have, The noise term only depends on the second derivative of f in X t and contains a noise term Σ(X t ). We propose to not take the noise term into account in the SDP formulation. The inequality t ,Pt (X t ,X t , t) is satisfied for any trajectory (X t ,X t ) generated by the SDE under Polyak-Ruppert averaging (3.5) and any function f ∈ F 0,∞ . This is directly equivalent to E[ ∂ ∂t V(Y t , t) + ∂ ∂y V dYt dt ] 0, where Y t = X tXt ⊤ . We notice that this inequality is exactly equivalent to d dt V(Ỹ t , t) 0 whereỸ t = X tXt ⊤ are trajectories generated by the deterministic gradient flow obtained from the SDE (3.5) with γ = 0. Thus, an equivalent reformulation to Equation (B.2) is given by: t ,Pt (X t ,X t , t) subject to dX t = −h t ∇f (X t )dt, dX t = X t −X t t dt.
Using convex interpolation on triplets {(X t , g t , f t ), (X t ,ḡ t ,f t ), (X ⋆ , 0, f (X ⋆ ))} such that there exists f ∈ F 0,∞ verifying f t = f (X t ), g t = ∇f (X t ), f (X t ) =f t and f t = ∇f (X t ), the infinite dimensional problem has a quadratic program formulation. Introducing the Gram matrix G = Y ⊤ Y 0, Y = [X t − x ⋆ ,X t − x ⋆ , g t ,ḡ t ], the Theorem C.3 concludes in an other way that it is not possible to obtain a convergence guarantee on an averaged sequence of an accelerated method. However, we can wonder if there exists other transformations that ensures convergence of both the averaged sequence and the noise.