# Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2019.

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

- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [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)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [On Convergence of Federated Averaging Langevin Dynamics](https://mlsanity.com/paper/2112.05120/) (2021)
- [Source-Guided Flow Matching](https://mlsanity.com/paper/2508.14807/) (2025)
- [Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators](https://mlsanity.com/paper/2210.07219/) (2022)
- [Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler](https://mlsanity.com/paper/2302.06085/) (2023)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [An Introduction to Hamiltonian Monte Carlo Method for Sampling](https://mlsanity.com/paper/2108.12107/) (2021)
- [Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps](https://mlsanity.com/paper/2209.12771/) (2022)
- [Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration](https://mlsanity.com/paper/2211.11003/) (2022)
- [Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Time](https://mlsanity.com/paper/2207.02189/) (2022)
- [Fit Like You Sample: Sample-Efficient Generalized Score Matching from Fast Mixing Diffusions](https://mlsanity.com/paper/2306.09332/) (2023)
- [Entropy-based adaptive Hamiltonian Monte Carlo](https://mlsanity.com/paper/2110.14625/) (2021)
- [Faster Sampling via Stochastic Gradient Proximal Sampler](https://mlsanity.com/paper/2405.16734/) (2024)
- [Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Sampling](https://mlsanity.com/paper/2303.00570/) (2023)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Bayesian Federated Learning with Hamiltonian Monte Carlo: Algorithm and Theory](https://mlsanity.com/paper/2407.06935/) (2024)
- [Feel-Good Thompson Sampling for Contextual Bandits: a Markov Chain Monte Carlo Showdown](https://mlsanity.com/paper/2507.15290/) (2025)
- [Hamiltonian Monte Carlo with Asymmetrical Momentum Distributions](https://mlsanity.com/paper/2110.12907/) (2021)
- [On the Dissipation of Ideal Hamiltonian Monte Carlo Sampler](https://mlsanity.com/paper/2209.07438/) (2022)
- [Sampling with Adaptive Variance for Multimodal Distributions](https://mlsanity.com/paper/2411.15220/) (2024)
- [Mirror Langevin diffusions: Convergence rates and Markov chain approximations](https://mlsanity.com/paper/2607.22892/) (2026)
- [Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo](https://mlsanity.com/paper/2102.13068/) (2021)
- [On Convergence of the Alternating Directions SGHMC Algorithm](https://mlsanity.com/paper/2405.13140/) (2024)
- [Randomized Transport Plans via Hierarchical Fully Probabilistic Design](https://mlsanity.com/paper/2408.02701/) (2024)

## Abstract (arXiv)

We study Hamiltonian Monte Carlo (HMC) for sampling from a strongly logconcave density proportional to e-f where f:ℝd → ℝ is μ-strongly convex and L-smooth (the condition number is kappa = L/μ). We show that the relaxation time (inverse of the spectral gap) of ideal HMC is O(kappa), improving on the previous best bound of O(kappa1.5); we complement this with an example where the relaxation time is Omega(kappa). When implemented using a nearly optimal ODE solver, HMC returns an varepsilon-approximate point in 2-Wasserstein distance using widetildeO((kappa d)0.5 varepsilon-1) gradient evaluations per step and widetildeO((kappa d)1.5varepsilon-1) total time.