Fetching the paper…

Reading the bibliography…

2018

On Symplectic Optimization

Betancourt, Michael, Jordan, Michael I., Wilson, Ashia C.

Original
PDF
Post on X

Understand

Accelerated gradient methods have had significant impact in machine learning -- in particular the theoretical side of machine learning -- due to their ability to achieve oracle lower bounds.

But their heuristic construction has hindered their full integration into the practical machine-learning algorithmic toolbox, and has limited their scope.
In this paper we build on recent work which casts acceleration as a phenomenon best explained in continuous time, and we augment that picture by providing a systematic methodology for converting continuous-time dynamics into discrete-time algorithms while retaining oracle rates.
Our framework is based on ideas from Hamiltonian dynamical systems and symplectic integration.

On Symplectic Optimization · Around

Built on

Problem Complexity and Method Efficiency in Optimization
Nemirovskii, A. and Yudin, D · 1983
Earlier work this paper cites.
A method of solving a convex programming problem with convergence rate o(1/k2)
Nesterov, Y · 1983
Earlier work this paper cites.
Methods of Differential Geometry in Analytical Mechanics , volume 158 of North-Holland Mathematics Studies
de León, M. and Rodrigues, P. R · 1989
Earlier work this paper cites.
Classical Dynamics: A Contemporary Approach
José, J. V. and Saletan, E. J · 1998
Earlier work this paper cites.
Simulating Hamiltonian Dynamics
Leimkuhler, B. and Reich, S · 2004
Earlier work this paper cites.

Similar

On the nonlinear stability of symplectic integrators
McLachlan, R. I., Perlmutter, M., and Quispel, G. R. W · 2004
Cited alongside, same era.
Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations
Hairer, E., Lubich, C., and Wanner, G · 2006
Cited alongside, same era.
Introduction to Smooth Manifolds
Lee, J. M · 2013
Cited alongside, same era.
The fundamental incompatibility of scalable Hamiltonian Monte Carlo and naive data subsampling
Betancourt, M · 2015
Cited alongside, same era.

Then

Accelerated mirror descent in continuous and discrete time
Krichene, W., Bayen, A., and Bartlett, P · 2015
Later among the works it cites.
A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights
Su, W., Boyd, S., and Candes, E. J · 2016
Later among the works it cites.
A variational perspective on accelerated methods in optimization
Original
Wibisono, A., Wilson, A. C., and Jordan, M. I · 2016
Later among the works it cites.
Accelerated gradient descent escapes saddle points faster than gradient descent
Original
Jin, C., Netrapalli, P., and Jordan, M. I · 2017
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…