Poster
Acceleration via Symplectic Discretization of High-Resolution Differential Equations
Bin Shi · Simon Du · Weijie Su · Michael Jordan
East Exhibition Hall B, C #102
Keywords: [ Convex Optimization ] [ Optimization ] [ Computational Complexity ] [ Theory ]
We study first-order optimization algorithms 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: symplectic Euler (S), explicit Euler (E) and implicit Euler (I) schemes. We show that the optimization algorithm generated by applying the symplectic scheme to a high-resolution ODE proposed by Shi et al. [2018] achieves the accelerated rate for minimizing both strongly convex function and convex function. 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.
Live content is unavailable. Log in and register to view live content