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 $\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((d\mathrm{/}K{)}^{1\mathrm{/}3}(L\mathrm{/}K{)}^{5\mathrm{/}3}{\epsilon }^{-2\mathrm{/}3}\log ({\mathcal{W}}^2(\mu ,\nu )\mathrm{/}\epsilon {)}^{+})$ gradient evaluations; whereas for such rough target densities the corresponding complexity of the uHMC algorithm with Verlet time integration is in general $O((d\mathrm{/}K{)}^{1\mathrm{/}2}(L\mathrm{/}K{)}^2{\epsilon }^{-1}\log ({\mathcal{W}}^2(\mu ,\nu )\mathrm{/}\epsilon {)}^{+})$. Metropolis-adjustable randomized time integrators are also provided.