Concentration of the Langevin Algorithm's Stationary Distribution

MaRDI QIDQ6421606zbMATH OpenFDO

Authors Jason M. Altschuler, Kunal Talwar

Publication date 23 December 2022

Abstract: A canonical algorithm for log-concave sampling is the Langevin Algorithm, aka the Langevin Diffusion run with some discretization stepsize $eta>0$. This discretization leads the Langevin Algorithm to have a stationary distribution $p{i}_{eta}$ which differs from the stationary distribution $pi$ of the Langevin Diffusion, and it is an important challenge to understand whether the well-known properties of $pi$ extend to $p{i}_{eta}$. In particular, while concentration properties such as isoperimetry and rapidly decaying tails are classically known for $pi$, the analogous properties for $p{i}_{eta}$ are open questions with direct algorithmic implications. This note provides a first step in this direction by establishing concentration results for $p{i}_{eta}$ that mirror classical results for $pi$. Specifically, we show that for any nontrivial stepsize $eta>0$, $p{i}_{eta}$ is sub-exponential (respectively, sub-Gaussian) when the potential is convex (respectively, strongly convex). Moreover, the concentration bounds we show are essentially tight. Key to our analysis is the use of a rotation-invariant moment generating function (aka Bessel function) to study the stationary dynamics of the Langevin Algorithm. This technique may be of independent interest because it enables directly analyzing the discrete-time stationary distribution $p{i}_{eta}$ without going through the continuous-time stationary distribution $pi$ as an intermediary.

This page was built for publication: Concentration of the Langevin Algorithm's Stationary Distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6421606)