Optimization with Momentum: Dynamical, Control-Theoretic, and Symplectic Perspectives

Michael Jordan
University of California, Berkeley (UC Berkeley)
Computer Science Division and Department of Statistics

We analyze the convergence rate of various momentum-based optimization algorithms from dynamical systems and Hamiltonian points of view. The analysis exploits fundamental topological properties, such as the continuous dependence of iterates on their initial conditions, to provide a simple characterization of convergence rates. In many cases, closed-form expressions are obtained that relate algorithm parameters to the convergence rate. The analysis encompasses discrete time and continuous time, as well as time-invariant and time-variant formulations, and is not limited to a convex or Euclidean setting. In addition, we show why symplectic discretization schemes are important for momentum-based optimization algorithms, and provide a characterization of algorithms that exhibit accelerated convergence. Finally, we discuss recent work on a generalization of symplectic integrators to dissipative Hamiltonian systems that is able to preserve continuous-time rates of convergence up to a controlled error. [Joint work with Michael Muehlebach, Guilherme Franca and Rene Vidal.]

Presentation (PDF File)

Back to Workshop II: PDE and Inverse Problem Methods in Machine Learning