Abstract
We propose a family of optimization methods that achieve linear convergenceusing first-order gradient information and constant step sizes on a class ofconvex functions much larger than the smooth and strongly convex ones. Thislarger class includes functions whose second derivatives may be singular orunbounded at their minima. Our methods are discretizations of conformalHamiltonian dynamics, which generalize the classical momentum method to modelthe motion of a particle with non-standard kinetic energy exposed to adissipative force and the gradient field of the function of interest. They arefirst-order in the sense that they require only gradient computation. Yet,crucially the kinetic gradient map can be designed to incorporate informationabout the convex conjugate in a fashion that allows for linear convergence onconvex functions that may be non-smooth or non-strongly convex. We study indetail one implicit and two explicit methods. For one explicit method, weprovide conditions under which it converges to stationary points of non-convexfunctions. For all, we provide conditions on the convex function and kineticenergy pair that guarantee linear convergence, and show that these conditionscan be satisfied by functions with power growth. In sum, these methods expandthe class of convex functions on which linear convergence is possible withfirst-order computation.