Timezone: »

 
Poster
Acceleration via Symplectic Discretization of High-Resolution Differential Equations
Bin Shi · Simon Du · Weijie Su · Michael Jordan

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #102
in Optimization -- Convex Optimization »

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.

Keywords: Convex Optimization · Computational Complexity · Theory · Optimization
[ Paper]  [ Slides] 

Author Information

Bin Shi (UC Berkeley)
Simon Du (Institute for Advanced Study)
Weijie Su (The Wharton School, University of Pennsylvania)
Michael Jordan (UC Berkeley)

More from the Same Authors