Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation

DOI10.1145/3188745.3188774MaRDI QIDQ5230366zbMATH OpenOpenAlexFDO

Authors Yin Tat Lee, Santosh S. Vempala

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.06261

zbMATH Keywords

samplingpolytopesHamiltonian dynamicsvolume computation

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Complexity and performance of numerical algorithms (65Y20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: 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.

Recommendations

• Improved polytope volume calculations based on Hamiltonian Monte Carlo with boundary reflections and sweet arithmetics
• Gibbs/Metropolis algorithms on a convex polytope
• Geodesic walks in polytopes
• Fast MCMC sampling algorithms on polytopes
• Random walks in a convex body and an improved volume algorithm

Cited in

(16)

• Fast MCMC sampling algorithms on polytopes
• Fast mixing of Metropolized Hamiltonian Monte Carlo: benefits of multi-step gradients
• Mixing time guarantees for unadjusted Hamiltonian Monte Carlo
• Global convergence of stochastic gradient Hamiltonian Monte Carlo for nonconvex stochastic optimization: nonasymptotic performance bounds and momentum-based acceleration
• High-dimensional MCMC with a standard splitting scheme for the underdamped Langevin diffusion
• A practical algorithm for volume estimation based on billiard trajectories and simulated annealing
• Rapid convergence of the unadjusted Langevin algorithm: isoperimetry suffices
• Truncated log-concave sampling for convex bodies with reflective Hamiltonian Monte Carlo
• Efficient sampling in spectrahedra and volume approximation
• scientific article; zbMATH DE number 7650131 (Why is no real title available?)
• On the mixing time of coordinate Hit-and-Run
• Randomized time Riemannian manifold Hamiltonian Monte Carlo
• scientific article; zbMATH DE number 7236423 (Why is no real title available?)
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Simulating Coulomb and log-gases with hybrid Monte Carlo algorithms
• Improved polytope volume calculations based on Hamiltonian Monte Carlo with boundary reflections and sweet arithmetics

This page was built for publication: Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230366)