# Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 49 references that are in the map.
- First posted on arXiv 20 Nov 2022.

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

- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Coupling and Convergence for Hamiltonian Monte Carlo](https://mlsanity.com/paper/1805.00452/) (2018)
- [Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions](https://mlsanity.com/paper/1905.02313/) (2019)
- [Geometric integrators and the Hamiltonian Monte Carlo method](https://mlsanity.com/paper/1711.05337/) (2017)
- [On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method](https://mlsanity.com/paper/2011.03176/) (2020)
- [Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2105.00887/) (2021)
- [Asymptotic bias of inexact Markov Chain Monte Carlo methods in high dimension](https://mlsanity.com/paper/2108.00682/) (2021)
- [Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities](https://mlsanity.com/paper/1812.06243/) (2018)
- [Connecting the Dots: Numerical Randomized Hamiltonian Monte Carlo with State-Dependent Event Rates](https://mlsanity.com/paper/2005.01285/) (2020)
- [Couplings for Andersen Dynamics](https://mlsanity.com/paper/2009.14239/) (2020)

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

- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo](https://mlsanity.com/paper/2404.15253/) (2024)
- [Reflection coupling for unadjusted generalized Hamiltonian Monte Carlo in the nonconvex stochastic gradient case](https://mlsanity.com/paper/2310.18774/) (2023)
- [A Non-asymptotic Analysis for Learning and Applying a Preconditioner in MCMC](https://mlsanity.com/paper/2602.10714/) (2026)
- [Randomized Runge-Kutta-Nystr"om Methods for Unadjusted Hamiltonian and Kinetic Langevin Monte Carlo](https://mlsanity.com/paper/2310.07399/) (2023)
- [On Convergence of the Alternating Directions SGHMC Algorithm](https://mlsanity.com/paper/2405.13140/) (2024)

## Abstract (arXiv)

A randomized time integrator is suggested for unadjusted Hamiltonian Monte Carlo (uHMC) which involves a very minor modification to the usual Verlet time integrator, and hence, is easy to implement. For target distributions of the form μ(dx) propto e-U(x) dx where U: ℝd → ℝ≥ 0 is K-strongly convex but only L-gradient Lipschitz, and initial distributions nu with finite second moment, coupling proofs reveal that an varepsilon-accurate approximation of the target distribution in L2-Wasserstein distance boldsymbolW2 can be achieved by the uHMC algorithm with randomized time integration using Oleft((d/K)1/3 (L/K)5/3 varepsilon-2/3 log( boldsymbolW2(μ, nu) / varepsilon)^+right) gradient evaluations; whereas for such rough target densities the corresponding complexity of the uHMC algorithm with Verlet time integration is in general Oleft((d/K)1/2 (L/K)2 varepsilon-1 log( boldsymbolW2(μ, nu) / varepsilon)^+ right). Metropolis-adjustable randomized time integrators are also provided.