Optimization Online


Hamiltonian Descent Methods

Chris J. Maddison(cmaddis***at***stats.ox.ac.uk)
Daniel Paulin(paulindani***at***gmail.com)
Yee Whye Teh(y.w.teh***at***stats.ox.ac.uk)
Brendan O'Donoghue(bodonoghue***at***google.com)
Arnaud Doucet(doucet***at***stats.ox.ac.uk)

Abstract: We propose a family of optimization methods that achieve linear convergence using first-order gradient information and constant step sizes on a class of convex functions much larger than the smooth and strongly convex ones. This larger class includes functions whose second derivatives may be singular or unbounded at their minima. Our methods are discretizations of conformal Hamiltonian dynamics, which generalizes the classical momentum method to model the motion of a particle with non-standard kinetic energy exposed to a dissipative force and the gradient field of the function of interest. They are first-order in the sense that they require only gradient computation. Yet, crucially the kinetic gradient map can be designed to incorporate information about the convex conjugate in a fashion that allows for linear convergence on convex functions that may be non-smooth or non-strongly convex. We study in detail one implicit and two explicit methods. For one explicit method, we provide conditions under which it converges to stationary points of non-convex functions. For all, we provide conditions on the convex function and kinetic energy pair that guarantee linear convergence, and show that these conditions can be satisfied by functions with power growth. In sum, these methods expand the class of convex functions on which linear convergence is possible with first-order computation.

Keywords: linear convergence; non-strongly convex; non-globally Lipschitz gradients; heavy ball; momentum

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Pre-Print: arXiv:1809.05042 Publication Date: 09/2018

Download: [PDF]

Entry Submitted: 09/22/2018
Entry Accepted: 09/22/2018
Entry Last Modified: 09/22/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society