# Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2018.

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

- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps](https://mlsanity.com/paper/2209.12771/) (2022)
- [Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time](https://mlsanity.com/paper/2207.02189/) (2022)
- [Faster Sampling via Stochastic Gradient Proximal Sampler](https://mlsanity.com/paper/2405.16734/) (2024)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities](https://mlsanity.com/paper/2406.13036/) (2024)
- [Subsampling Error in Stochastic Gradient Langevin Diffusions](https://mlsanity.com/paper/2305.13882/) (2023)
- [A New Framework for Variance-Reduced Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.04613/) (2021)
- [Bayesian deep learning framework for uncertainty quantification in high dimensions](https://mlsanity.com/paper/2210.11737/) (2022)
- [On Convergence of the Alternating Directions SGHMC Algorithm](https://mlsanity.com/paper/2405.13140/) (2024)

## Abstract (arXiv)

Hamiltonian Monte Carlo (HMC) is a widely deployed method to sample from high-dimensional distributions in Statistics and Machine learning. HMC is known to run very efficiently in practice and its popular second-order "leapfrog" implementation has long been conjectured to run in d1/4 gradient evaluations. Here we show that this conjecture is true when sampling from strongly log-concave target distributions that satisfy a weak third-order regularity property associated with the input data. Our regularity condition is weaker than the Lipschitz Hessian property and allows us to show faster convergence bounds for a much larger class of distributions than would be possible with the usual Lipschitz Hessian constant alone. Important distributions that satisfy our regularity condition include posterior distributions used in Bayesian logistic regression for which the data satisfies an "incoherence" property. Our result compares favorably with the best available bounds for the class of strongly log-concave distributions, which grow like d^1/2 gradient evaluations with the dimension. Moreover, our simulations on synthetic data suggest that, when our regularity condition is satisfied, leapfrog HMC performs better than its competitors -- both in terms of accuracy and in terms of the number of gradient evaluations it requires.