Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation
This work addresses the problem of efficient sampling and volume computation for polytopes, with applications in optimization and statistics, representing a significant advance over prior methods.
The authors provided the first rigorous proof of convergence for Riemannian Hamiltonian Monte Carlo, a method for sampling Gibbs distributions, showing the rate depends on manifold smoothness parameters. They applied this to uniformly sample polytopes and compute volumes, achieving O*(mn^{2/3}) steps, which improves the state of the art.
We give the first rigorous proof of the convergence of Riemannian 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. We then apply the method with the manifold defined by the log barrier function to the problems of (1) uniformly sampling a polytope and (2) computing its volume, the latter by extending Gaussian cooling to the manifold setting. In both cases, the total number of steps needed is O^{*}(mn^{\frac{2}{3}}), improving the state of the art. A key ingredient of our analysis is a proof of an analog of the KLS conjecture for Gibbs distributions over manifolds.