Su-Boyd-Candes (2014) made a connection between Nesterov's method and an ordinary differential equation (ODE).   We show if a Hessian damping term is added to the ODE from Su-Boyd-Candes (2014), then Nesterov's method arises as a straightforward discretization of the modified ODE. Analogously,  in the strongly convex case, a Hessian damping term is added to Polyak's ODE, which is then discretized to yield Nesterov's method for strongly convex functions.    Despite the Hessian term, both second order ODEs can be represented as first order systems.

 Established Liapunov analysis is used to recover the accelerated rates of convergence in both continuous and discrete time.   Moreover, the Liapunov analysis can be extended to the case of stochastic gradients which allows the full gradient case to be considered as a special case of the stochastic case.   The result is a unified approach to convex acceleration in both continuous and discrete time and in  both the stochastic and full gradient cases. 
  Su et al. (2014) made a connection between Nesterov's method for a convex, L-smooth function, f , and the second order, ordinary differential equation (ODE) x + 3 tẋ + ∇f (x) = 0 (A-ODE)However Su et al. (2014) did not show that Nesterov's method arises as a discretization of (A-ODE). In order to obtain such a discretization, we consider the following ODE, which has an additional Hessian damping term with coefficient 1/ √ L. DISPLAYFORM0 Notice that (H-ODE) is a perturbation of (A-ODE), and the perturbation goes to zero as L → ∞. Similar ODEs have been studied by BID1 , they have been shown to accelerate gradient descent in continuous time in .Next , we consider the case where f is also µ-strongly convex, and write C f := L/µ for the condition number of f . Then Nesterov's method in the strongly convex case arises as discretization of the following second order ODË DISPLAYFORM1 (H-ODE-SC) is a perturbation of Polyak's ODE (Polyak, 1964) x + 2 √ µẋ + ∇f (x) = 0 which is accelerates gradient when f is quadratic see (Scieur et al., 2017) .In each case, both continuous and discrete, as well and convex and strongly convex, it is possible to provide a proof of the rate using a Liapunov function. These proofs are already established in the literature: we give citations below, and also provide proof in the Appendix.Moreover, the analysis for Nesterov's method in the full gradient can be extended to prove acceleration in the case of stochastic gradients. Acceleration of stochastic gradient descent has been established by Lin et al. (2015) and BID7 , see also BID8 . A direct acceleration method with a connection to Nestero'v method was done by BID0 . Our analysis unifies the continuous time ODE with the algorithm, and includes full gradient acceleration as a special case. The analysis proceeds by first rewriting (H-ODE) (and (H-ODE-SC)) as first order systems involving ∇f , and then replacing the ∇f with g = ∇f + e. Both the continuous and discrete time methods achieve the accelerated rate of convergence, provided |e| goes to zero quickly enough. The condition on |e|, is given below in (12) and (13) -it is faster than the corresponding rate for stochastic gradient descent. When e = 0 we recover the full gradient case.The renewed interested in the continuous time approach began with the work of Su et al. (2014) and was followed Wibisono et al. (2016); Wilson et al. (2016) . Continuous time analysis also appears in BID6 , BID11 , and BID10 . However, continuous time approaches to optimization have been around for a long time. Polyak's method Polyak ( 1964) is related to successive over relaxation for linear equations (Varga, 1957) which were initially used to accelerate solutions of linear partial differential equations (Young, 1954) . A continuous time interpretation of Newton's method can be found in (Polyak, 1987) or BID1 . The mirror descent algorithm of Nemirovskii et al. (1983) has a continuous time interpretation BID5 . The Liapunov approach for acceleration had already appeared in BID4 for FISTA.The question of when discretizations of dynamical systems also satisfy a Liapunov function has been studied in the context of stabilization in optimal control BID12 . More generally, Stuart & Humphries (1996 ) studies when a discretization of a dynamical system preserves a property such as energy dissipation.
We derive Nesterov's method arises as a straightforward discretization of an ODE different from the one in Su-Boyd-Candes and prove acceleration the stochastic case
{"src": "scitldr-AIC_train", "paper_id": "HJMINj05tQ"}