Optimization algorithms inspired by the geometry of dissipative systems

Optimization algorithms inspired by the geometry of dissipative systems Alessandro Bravetti 1, Maria L. Daza-Torres 2, Hugo Flores-Arguedas 3, and Michael Betancourt 4 1 Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas (IIMAS), Universidad Nacional Autónoma de México, A.P. 70-543, 04510 Ciudad de México, México alessandro.bravetti@iimas.unam.mx 2 Universidad de Guadalajara, Guadalajara, México, mdazatorres@cimat.mx 3 Centro de Investigación en Matemáticas (CIMAT), Guanajuato, México, hugo.flores@cimat.mx 4 Symplectomorphic LLC, New York, USA, betan@symplectomorphic.com Abstract Accelerated gradient methods are a powerful optimization tool in machine learning and statistics but their development has traditionally been driven by heuristic motivations. Recent research, however, has demonstrated that these methods can be derived as discretizations of dynamical systems, which in turn has provided a basis for more systematic investigations, especially into the structure of those dynamical systems and their structure preserving discretizations. In this work we introduce dynamical systems defined through a contact geometry which are not only naturally suited to the optimization goal but also subsume all previous methods based on geometric dynamical systems. These contact dynamical systems also admit a natural, robust discretization through geometric contact integrators. We demonstrate these features in paradigmatic examples which show that we can indeed obtain optimization algorithms that achieve oracle lower bounds on convergence rates while also improving on previous proposals in terms of stability. Keywords: optimization, accelerated gradient, geometric integrators, contact geometry 1 arXiv:1912.02928v1 Despite their practical utility and explicit convergence bounds, accelerated gradient methods have long been difficult to motivate from a fundamental theory.