Frictionless Hamiltonian Descent and Coordinate Hamiltonian Descent for Strongly Convex Quadratic Problems

Abstract

We propose an optimization algorithm called Frictionless Hamiltonian Descent, which is a direct counterpart of classical Hamiltonian Monte Carlo in sampling. We analyze Frictionless Hamiltonian Descent for strongly convex quadratic functions and show that the method has a non-trivial accelerated rate comparable to that of Heavy Ball flow. We also propose Frictionless Coordinate Hamiltonian Descent and its parallelizable variant, which together encompass the classical Gauss-Seidel method, Successive Over-relaxation, Jacobi method, and more, for solving a linear system of equations. The result not only offers a new perspective on these existing algorithms but also leads to a broader class of update schemes that guarantee convergence.