2022/12/24 by Jason M. Altschuler, Kunal Talwar, Altschuler, Jason M. +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Protein Structure and Dynamics #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2212.12629
openalex publication_date 2022/12/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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. We also show that these concentration bounds extend to all iterates along the trajectory of the Langevin Algorithm, and to inexact implementations which use sub-Gaussian estimates of the gradient. 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.