# Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 35 references that are in the map.
- First posted on arXiv 26 Sep 2022.

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

- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [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)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [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)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo](https://mlsanity.com/paper/1802.08898/) (2018)
- [An Introduction to Hamiltonian Monte Carlo Method for Sampling](https://mlsanity.com/paper/2108.12107/) (2021)
- [Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time](https://mlsanity.com/paper/2207.02189/) (2022)
- [On the Dissipation of Ideal Hamiltonian Monte Carlo Sampler](https://mlsanity.com/paper/2209.07438/) (2022)

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

- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (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)
- [New affine invariant ensemble samplers and their dimensional scaling](https://mlsanity.com/paper/2505.02987/) (2025)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [On Accelerated Mixing of the No-U-turn Sampler](https://mlsanity.com/paper/2507.13259/) (2025)
- [A Theoretical Comparison of No-U-Turn Sampler Variants: Necessary and Sufficient Convergence Conditions and Mixing Time Analysis under Gaussian Targets](https://mlsanity.com/paper/2603.18640/) (2026)

## Abstract (arXiv)

Hamiltonian Monte Carlo (HMC) is a Markov chain algorithm for sampling from a high-dimensional distribution with density e-f(x), given access to the gradient of f. A particular case of interest is that of a d-dimensional Gaussian distribution with covariance matrix Sigma, in which case f(x) = x^top Sigma-1 x. We show that HMC can sample from a distribution that is varepsilon-close in total variation distance using widetildeO(√kappa d1/4 log(1/varepsilon)) gradient queries, where kappa is the condition number of Sigma. Our algorithm uses long and random integration times for the Hamiltonian dynamics. This contrasts with (and was motivated by) recent results that give an widetildeOmega(kappa d1/2) query lower bound for HMC with fixed integration times, even for the Gaussian case.