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

DOI10.1145/3188745.3188774zbMATH Open1429.65009arXiv1710.06261OpenAlexW2963559717MaRDI QIDQ5230366FDOQ5230366

Santosh S. Vempala, Yin Tat Lee

Publication date: 22 August 2019

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

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.

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

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

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)

Cited In (15)

• Mixing time guarantees for unadjusted Hamiltonian Monte Carlo
• 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
• Title not available (Why is that?)
• Efficient sampling in spectrahedra and volume approximation
• On the mixing time of coordinate Hit-and-Run
• Randomized time Riemannian manifold Hamiltonian Monte Carlo
• Title not available (Why is that?)
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Title not available (Why is that?)
• Title not available (Why is that?)
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Nonconvex Stochastic Optimization: Nonasymptotic Performance Bounds and Momentum-Based Acceleration
• Simulating Coulomb and log-gases with hybrid Monte Carlo algorithms

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)