Concentration of the Langevin Algorithm's Stationary Distribution
share
A canonical algorithm for log-concave sampling is the Langevin Algorithm, aka the Langevin Diffusion run with some discretization stepsize η > 0. This discretization leads the Langevin Algorithm to have a stationary distribution π_η which differs from the stationary distribution π of the Langevin Diffusion, and it is an important challenge to understand whether the well-known properties of π extend to π_η. In particular, while concentration properties such as isoperimetry and rapidly decaying tails are classically known for π, the analogous properties for π_η are open questions with direct algorithmic implications. This note provides a first step in this direction by establishing concentration results for π_η that mirror classical results for π. Specifically, we show that for any nontrivial stepsize η > 0, π_η 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 π_η without going through the continuous-time stationary distribution π as an intermediary.
READ FULL TEXT