Based on a new coupling approach, we prove that the transition step of the Hamiltonian Monte Carlo algorithm is contractive w.r.t. a carefully designed Kantorovich ($L^{1}$ Wasserstein) distance. The lower bound for the contraction rate is explicit. Global convexity of the potential is not required, and thus multimodal target distributions are included. Explicit quantitative bounds for the number of steps required to approximate the stationary distribution up to a given error $\epsilon $ are a direct consequence of contractivity. These bounds show that HMC can overcome diffusive behavior if the duration of the Hamiltonian dynamics is adjusted appropriately.
1 January 2010 in SIAM Journal on Numerical Analysis
This paper presents a Lie–Trotter splitting for inertial Langevin equations (geometric Langevin algorithm) and analyzes its long-time statistical properties. The splitting is defined as a composition of a variational integrator with an Ornstein–Uhlenbeck flow. Assuming that the exact solution and the splitting are geometrically ergodic, the paper proves the discrete invariant measure of the splitting approximates the invariant measure of inertial Langevin equations to within the accuracy of the variational integrator in representing the Hamiltonian. In particular, if the variational integrator admits no energy error, then the method samples the invariant measure of inertial Langevin equations without error. Numerical validation is provided using explicit variational integrators with first-, second-, and fourth-order accuracy.
15 May 2008 in Foundations of Computational Mathematics
The Metropolis-Adjusted Langevin Algorithm (MALA), originally introduced to sample exactly the invariant measure of certain stochastic differential equations (SDEs) on infinitely long time intervals, can also be used to approximate pathwise the solution of these SDEs on finite time intervals. However, when applied to an SDE with a nonglobally Lipschitz drift coefficient, the algorithm may not have a spectral gap even when the SDE does. This paper reconciles MALA's lack of a spectral gap with its ergodicity to the invariant measure of the SDE and finite time accuracy. In particular, the paper shows that its convergence to equilibrium happens at an exponential rate up to terms exponentially small in time-step size. This quantification relies on MALA's ability to exactly preserve the SDE's invariant measure and accurately represent the SDE's transition probability on finite time intervals.
This paper surveys in detail the relations between numerical integration and the Hamiltonian (or hybrid) Monte Carlo method (HMC). Since the computational cost of HMC mainly lies in the numerical integrations, these should be performed as efficiently as possible. However, HMC requires methods that have the geometric properties of being volume-preserving and reversible, and this limits the number of integrators that may be used. On the other hand, these geometric properties have important quantitative implications for the integration error, which in turn have an impact on the acceptance rate of the proposal. While at present the velocity Verlet algorithm is the method of choice for good reasons, we argue that Verlet can be improved upon. We also discuss in detail the behaviour of HMC as the dimensionality of the target distribution increases.
4 November 2009 in Communications on Pure and Applied Mathematics