Accelerating Langevin Monte Carlo via Randomization

As a fundamental algorithmic task, sampling from a high-dimensional probability distribution finds wide-ranging applications in scientific computing, computational statistics and machine learning. In particular, Langevin Monte Carlo (LMC) sampling algorithms are among the most widely used ones and have received increasing attention in recent years. By injecting additional randomness for every iteration, this paper aims to propose two novel higher-order LMC algorithms, including a Taylor scheme involved with the Hessian of the potential and a Hessian-free Runge–Kutta type variant. Under gradient Lipschitz and Hessian Lipschitz conditions, both algorithms are shown to enjoy non-asymptotic ${\mathcal{W}}_2$-error bounds of order $O(d{h}^{3/2})$ beyond log-concavity, which guarantees a mixing time complexity $\tilde{O}(d^{2/3}{ϵ}^{-2/3})$. This improves the dimension-dependence of mixing time complexity $\tilde{O}(d{ϵ}^{-2/3})$ for the existing high-order LMC algorithms. Moreover, the error analysis of the newly proposed algorithms do not require any Lipschitz condition on the 3rd-order derivative of the potential, which is, however, necessary in obtaining the desired convergence order $1.5$ of existing high-order LMC methods. Some numerical experiments are reported to support the effectiveness of new sampling algorithms.