mlsanityData to 14 Oct 2026

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

arXiv 2209.12771 ↗First posted 26 Sep 2022stat.ML cs.DS cs.LGcited by 8

Not on the map. Why?

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.

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

13 of 35 references.

References · 13

  1. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 118
  2. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  3. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  4. 2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
  5. 2019High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithmcited by 36
  6. 2019Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributionscited by 28
  7. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  8. 2022Langevin Monte Carlo for Contextual Banditscited by 22
  9. 2021Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributionscited by 19
  10. 2018Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlocited by 11
  11. 2021An Introduction to Hamiltonian Monte Carlo Method for Samplingcited by 8
  12. 2022Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Timecited by 7
1 more
  1. 2022On the Dissipation of Ideal Hamiltonian Monte Carlo Samplercited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 3; 2026: 1.

8 papers.

  1. 2023Improved Discretization Analysis for Underdamped Langevin Monte Carlocited by 28
  2. 2024Entropy contraction of the Gibbs sampler under log-concavitycited by 13
  3. 2024Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentrationcited by 5
  4. 2024Tuning diagonal scale matrices for HMCcited by 4
  5. 2025New affine invariant ensemble samplers and their dimensional scalingcited by 4
  6. 2025Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdowncited by 4
  7. 2025On Accelerated Mixing of the No-U-turn Samplercited by 2
  8. 2026A Theoretical Comparison of No-U-Turn Sampler Variants: Necessary and Sufficient Convergence Conditions and Mixing Time Analysis under Gaussian Targetscited by 1