Unadjusted Hamiltonian MCMC with stratified Monte Carlo time integration

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)∝e−U(x)dx where U:Rd→R≥0 is K-strongly convex but only L-gradient Lipschitz, and initial distributions ν with finite second moment, coupling proofs reveal that an ε-accurate approximation of the target distribution in L2-Wasserstein distance W2 can be achieved by the uHMC algorithm with randomized time integration using O((d/K)1/3(L/K)5/3ε−2/3log(W2(μ,ν)/ε)+) gradient evaluations; whereas for such rough target densities the corresponding complexity of the uHMC algorithm with Verlet time integration is in general O((d/K)1/2(L/K)2ε−1log(W2(μ,ν)/ε)+). Metropolis-adjustable randomized time integrators are also provided.