Accelerating Langevin Monte Carlo via Efficient Stochastic Runge-Kutta Methods beyond Log-Concavity

Sampling from a high-dimensional probability distribution is a fundamental algorithmic task arising in wide-ranging applications across multiple disciplines, including scientific computing, computational statistics and machine learning. Langevin Monte Carlo (LMC) algorithms are among the most widely used sampling methods in high-dimensional settings. This paper introduces a novel higher-order and Hessian-free LMC sampling algorithm based on an efficient stochastic Runge--Kutta method of strong order $1.5$ for the overdamped Langevin dynamics. In contrast to the existing Runge--Kutta type LMC of Li et al. (2019) involved with three gradient evaluations, the newly proposed algorithm is computationally cheaper and requires only two gradient evaluations at each iteration. Under certain log-smooth conditions, non-asymptotic error bounds of the proposed algorithms are analyzed in $\mathcal{W}_2$-distance. In particular, a uniform-in-time convergence rate of order $O(d ^{\frac32} h^{\frac32})$ is derived in a non-log-concave setting, matching the convergence rate proved in the aforementioned work but under the log-concavity condition. Numerical experiments are finally presented to demonstrate the effectiveness of the new sampling algorithm.

High-dimensional sampling is a fundamental task in statistics, scientific computing and machine learning. Langevin Monte Carlo (LMC) is a popular approach that is particularly useful in high-dimensional settings, thanks to the gradient information together with random noise. In this paper, we design a new higher-order Hessian-free LMC sampling method that is cheaper to run at each step than existing high-order methods. Moreover, previous theoretical results for high-order Hessian-free sampling methods were established in the strongly convex setting, whereas we provide theoretical guarantees in a non-convex setting. This is more difficult because a strongly convex landscape is like a mountain with a single peak, while a non-convex landscape may have many peaks, valleys and misleading paths, making it much harder to explore reliably. Our experiments further demonstrate the effectiveness of the proposed sampling algorithms.