Abstract
We study the convergence of Hamiltonian Monte Carlo, a general (and practical) method for sampling Gibbs distributions. Our analysis shows that the rate of convergence is bounded in terms of natural smoothness parameters of an associated Riemannian manifold. For the problem of uniformly sampling polytopes, we show that RHMC using the log barrier function improves the state of the art. Then we use RHMC together with Gaussian Cooling on manifolds to obtain a faster algorithm for estimating the volume of a polytope. For polytopes in R^n specified by O(n) inequalities, the complexity is O*(n^{5/3}) steps. For volume computation, this is a considerable improvement over the previous best bound of O(n^4) steps. A key ingredient is the proof of a variant of the KLS isoperimetry conjecture for manifolds defined by barrier functions.