# When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?

arXiv: https://arxiv.org/abs/2304.04724 · HTML: https://mlsanity.com/paper/2304.04724/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 78 references that are in the map.
- First posted on arXiv 10 Apr 2023.

## Builds on (most cited first, 26 of 26)

- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Mean-Field Langevin Dynamics: Exponential Convergence and Annealing](https://mlsanity.com/paper/2202.01009/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm](https://mlsanity.com/paper/1908.10859/) (2019)
- [Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions](https://mlsanity.com/paper/1905.02313/) (2019)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2105.00887/) (2021)
- [Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions](https://mlsanity.com/paper/1708.07114/) (2017)
- [Strong Self-Concordance and Sampling](https://mlsanity.com/paper/1911.05656/) (2019)
- [Optimizing The Integrator Step Size for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1411.6669/) (2014)
- [Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration](https://mlsanity.com/paper/2211.11003/) (2022)
- [Mean-Field Analysis of Two-Layer Neural Networks: Global Optimality with Linear Convergence Rates](https://mlsanity.com/paper/2205.09860/) (2022)

## Built on by (most cited first, 15 of 15)

- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (2024)
- [Sampling from Bayesian Neural Network Posteriors with Symmetric Minibatch Splitting Langevin Dynamics](https://mlsanity.com/paper/2410.19780/) (2024)
- [Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration](https://mlsanity.com/paper/2410.06978/) (2024)
- [Tuning diagonal scale matrices for HMC](https://mlsanity.com/paper/2403.07495/) (2024)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression](https://mlsanity.com/paper/2412.07999/) (2024)
- [Correction to "Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations"](https://mlsanity.com/paper/2402.08711/) (2024)
- [On Accelerated Mixing of the No-U-turn Sampler](https://mlsanity.com/paper/2507.13259/) (2025)
- [Algorithmic warm starts for Hamiltonian Monte Carlo](https://mlsanity.com/paper/2603.22741/) (2026)
- [Operator-Level Quantum Acceleration of Non-Logconcave Sampling](https://mlsanity.com/paper/2505.05301/) (2025)
- [On Convergence of the Alternating Directions SGHMC Algorithm](https://mlsanity.com/paper/2405.13140/) (2024)
- [Numerical Generalized Randomized Hamiltonian Monte Carlo for piecewise smooth target densities](https://mlsanity.com/paper/2504.18210/) (2025)
- [Accelerated Mixing Time of Randomized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2607.12902/) (2026)
- [Delocalization of bias in unadjusted Hamiltonian Monte Carlo and underdamped Langevin](https://mlsanity.com/paper/2607.15208/) (2026)
- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)

## Abstract (arXiv)

We analyze the mixing time of Metropolized Hamiltonian Monte Carlo (HMC) with the leapfrog integrator to sample from a distribution on ℝd whose log-density is smooth, has Lipschitz Hessian in Frobenius norm and satisfies isoperimetry. We bound the gradient complexity to reach ε error in total variation distance from a warm start by tilde O(d1/4polylog(1/ε)) and demonstrate the benefit of choosing the number of leapfrog steps to be larger than 1. To surpass the previous analysis on Metropolis-adjusted Langevin algorithm (MALA) that has tildeO(d1/2polylog(1/ε)) dimension dependency [WSC22], we reveal a key feature in our proof that the joint distribution of the location and velocity variables of the discretization of the continuous HMC dynamics stays approximately invariant. This key feature, when shown via induction over the number of leapfrog steps, enables us to obtain estimates on moments of various quantities that appear in the acceptance rate control of Metropolized HMC. Notably, our analysis does not require log-concavity or independence of the marginals, and only relies on an isoperimetric inequality. To illustrate the relevance of the Lipschitz Hessian in Frobenius norm assumption, several examples that fall into our framework are discussed.