Acceleration via Symplectic Discretization of High-Resolution Differential Equations
Bin Shi, Simon S. Du, Weijie J. Su, Michael I. Jordan
We study first-order optimization methods obtained by discretizing ordinary
differential equations (ODEs) corresponding to Nesterov's accelerated gradient
methods (NAGs) and Polyak's heavy-ball method. We consider three discretization
schemes: an explicit Euler scheme, an implicit Euler scheme, and a symplectic
scheme. We show that the optimization algorithm generated by applying the
symplectic scheme to a high-resolution ODE proposed by Shi et al. 
achieves an accelerated rate for minimizing smooth strongly convex functions.
On the other hand, the resulting algorithm either fails to achieve acceleration
or is impractical when the scheme is implicit, the ODE is low-resolution, or
the scheme is explicit.