Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration

Abstract

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 $\mu (dx)\propto e^{-U(x)}dx$ where $U:{\mathbb{R}}^d\to {\mathbb{R}}_{\ge 0}$ is $K$-strongly convex but only $L$-gradient Lipschitz, and initial distributions $\nu$ with finite second moment, coupling proofs reveal that an $\epsilon$-accurate approximation of the target distribution in $L^2$-Wasserstein distance ${\mathcal{W}}^2$ can be achieved by the uHMC algorithm with randomized time integration using $O\left((d/K{)}^{1/3}(L/K{)}^{5/3}{\epsilon }^{-2/3}\log ({\mathcal{W}}^2(\mu ,\nu )/\epsilon {)}^{+}\right)$ gradient evaluations; whereas for such rough target densities the corresponding complexity of the uHMC algorithm with Verlet time integration is in general $O\left((d/K{)}^{1/2}(L/K{)}^2{\epsilon }^{-1}\log ({\mathcal{W}}^2(\mu ,\nu )/\epsilon {)}^{+}\right)$. Metropolis-adjustable randomized time integrators are also provided.

32 pages, 2 figures

References in corpus (20)

• The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo
• Convergence of Numerical Time-Averaging and Stationary Measures via Poisson Equations
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Randomized Hamiltonian Monte Carlo
• Geometric integrators and the Hamiltonian Monte Carlo method
• Coupling and Convergence for Hamiltonian Monte Carlo
• Numerical integrators for the Hybrid Monte Carlo method
• Compressible Generalized Hybrid Monte Carlo
• Large-time behavior in non-symmetric Fokker-Planck equations
• The Randomized Midpoint Method for Log-Concave Sampling
• Complexity of randomized algorithms for underdamped Langevin dynamics
• Convergence of unadjusted Hamiltonian Monte Carlo for mean-field models
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• On explicit $L^2$-convergence rate estimate for piecewise deterministic Markov processes in MCMC algorithms
• Couplings for Andersen Dynamics
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• HMC and underdamped Langevin united in the unadjusted convex smooth case
• The shifted ODE method for underdamped Langevin MCMC