Accelerated Sampling with the Inertial Langevin Algorithm

Abstract

We consider the \emph{inertial Langevin algorithm} (ILA), a simple momentum-based method for sampling from Gibbs distributions of the form $\pi (x)\propto \exp (-U(x))$. ILA augments the unadjusted Langevin algorithm with an inertia term and a matching noise rescaling, yielding a sampling analogue of Polyak's heavy-ball method from optimization. This modification provably accelerates convergence. For Gaussian targets, ILA attains Wasserstein-2 accuracy $\delta$ in $\tilde{\mathcal O (\sqrtκ/\sqrtδ)$ iterations, where $\kappa =L/m$ denotes the condition number and $\tilde{\mathcal{O}}$ hides logarithmic factors, thus reaching the ballistic $\sqrt{\kappa }$ complexity known from accelerated optimization and proven to be a lower bound for sampling from Gaussians. Moreover, we show that the method's bias can be fully removed and, thus, complexity reduced to $\tilde \Oc(\sqrtκ)$ by considering the sequence consisting of the average of ever two consecutive ILA iterates, which is shown to be equivalent to the well-known BAOAB splitting scheme in the linear setting. Beyond Gaussians, for $L$-smooth potentials with sufficient growth at infinity, we prove geometric ergodicity of ILA and of its continuous-time analogue, the underdamped Langevin dynamics, together with convergence of the discretization bias to zero as the step size decreases. These guarantees hold under considerably simpler parameter restrictions than previously available in the literature, in particular, not imposing a lower bound on the friction, which is conjectured to be crucial for acceleration. We underpin our theoretical findings with numerical experiments covering ill-conditioned Gaussian distributions, total variation image denoising, and the challenging task of maximum likelihood learning of an energy-based model for molecular structure generation.