The Convergence of Hamiltonian Monte Carlo
summary
Proves that Hamiltonian Monte Carlo run with the Hessian manifold metric (log barrier) mixes far faster on polytopes — roughly MN^{2/3} mixing steps (with polylog factors and ε–dependence for volume), versus quadratic or worse for previous walks. Key tools are a new isoperimetric bound on the manifold, explicit drift from the Hessian, and approximating the Hamiltonian ODE by low‑degree polynomials so each step is a linear‑system solve. No Metropolis filter; experiments show near‑constant steps and practical speed comparable to hit‑and‑run.
AI-written summary · about
chapters (10)
- 0:00Intro
- 0:35The Sampling Problem
- 3:33Sampling polytopes
- 6:17Polytope Volume
- 7:35How to sample? Random walks
- 11:01Dikin Walk with Metropolis filter
- 13:32Nature's solution: Brownian motion
- 18:15Hamiltonian Monte Carlo
- 26:21Implementation
- 27:54Gaussian Cooling on Manifolds
related talks
01h 10mAn Introduction to Hamiltonian Monte Carlo Method for Sampling
34mFast Algorithms for Multivariate ODEs arising in Sampling and Learning
12mIterative Methods and High-Dimensional Statistics
33mHessian Matrix Inversion in 10^10 Dimensions with Parametric Bootstraps
01h 03mSampling Crash Course
58mContinuous Methods 2
01h 07mEfficient Classical Simulation of Many-body Systems with Local Integrals of Motion
01h 18mOptimization I