The shifted ODE method for underdamped Langevin MCMC

Abstract

In this paper, we consider the underdamped Langevin diffusion (ULD) and propose a numerical approximation using its associated ordinary differential equation (ODE). When used as a Markov Chain Monte Carlo (MCMC) algorithm, we show that the ODE approximation achieves a $2$-Wasserstein error of $\epsilon$ in $\mathcal{O}(d^{\frac{1}{3}}/{\epsilon }^{\frac{2}{3}})$ steps under the standard smoothness and strong convexity assumptions on the target distribution. This matches the complexity of the randomized midpoint method proposed by Shen and Lee [NeurIPS 2019] which was shown to be order optimal by Cao, Lu and Wang. However, the main feature of the proposed numerical method is that it can utilize additional smoothness of the target log-density $f$. More concretely, we show that the ODE approximation achieves a $2$-Wasserstein error of $\epsilon$ in $\mathcal{O}(d^{\frac{2}{5}}/{\epsilon }^{\frac{2}{5}})$ and $\mathcal{O}(\sqrt{d}/{\epsilon }^{\frac{1}{3}})$ steps when Lipschitz continuity is assumed for the Hessian and third derivative of $f$. By discretizing this ODE using a third order Runge-Kutta method, we can obtain a practical MCMC method that uses just two additional gradient evaluations per step. In our experiment, where the target comes from a logistic regression, this method shows faster convergence compared to other unadjusted Langevin MCMC algorithms.

References in corpus (10)

• Accurate sampling using Langevin dynamics
• The computation of averages from equilibrium and nonequilibrium Langevin molecular dynamics
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Randomized Hamiltonian Monte Carlo
• Palindromic 3-stage splitting integrators, a roadmap
• Estimating Convergence of Markov chains with L-Lag Couplings
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Constraint-Based Regularization of Neural Networks
• HMC: avoiding rejections by not using leapfrog and some results on the acceptance rate
• Hamiltonian Assisted Metropolis Sampling

Cited by in corpus (2)

• Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations