Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration

11/20/2022
by   Nawaf Bou-Rabee, et al.
0

A novel randomized time integrator is suggested for unadjusted Hamiltonian Monte Carlo (uHMC) in place of the usual Verlet integrator; namely, a stratified Monte Carlo (sMC) integrator which involves a minor modification to Verlet, and hence, is easy to implement. For target distributions of the form μ(dx) ∝ e^-U(x) dx where U: ℝ^d →ℝ_≥ 0 is both K-strongly convex and L-gradient Lipschitz, and initial distributions ν with finite second moment, coupling proofs reveal that an ε-accurate approximation of the target distribution μ in L^2-Wasserstein distance 𝒲^2 can be achieved by the uHMC algorithm with sMC time integration using O((d/K)^1/3 (L/K)^5/3ε^-2/3log( 𝒲^2(μ, ν) / ε)^+) gradient evaluations; whereas without additional assumptions the corresponding complexity of the uHMC algorithm with Verlet time integration is in general O((d/K)^1/2 (L/K)^2 ε^-1log( 𝒲^2(μ, ν) / ε)^+ ). Duration randomization, which has a similar effect as partial momentum refreshment, is also treated. In this case, without additional assumptions on the target distribution, the complexity of duration-randomized uHMC with sMC time integration improves to O(max((d/K)^1/4 (L/K)^3/2ε^-1/2,(d/K)^1/3 (L/K)^4/3ε^-2/3) ) up to logarithmic factors. The improvement due to duration randomization turns out to be analogous to that of time integrator randomization.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset