Acceleration via Symplectic Discretization of High-Resolution Differential Equations
Bin Shi, Simon S Du, Weijie Su, Michael I Jordan
Abstract
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.
BibTeX
@inproceedings{NEURIPS2019_a9986cb0,
author = {Shi, Bin and Du, Simon S and Su, Weijie and Jordan, Michael I},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Acceleration via Symplectic Discretization of High-Resolution Differential Equations},
url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/a9986cb066812f440bc2bb6e3c13696c-Paper.pdf},
volume = {32},
year = {2019}
}