Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices

By Santosh Srinivas Vempala, Andre Wibisono. Neural Information Processing Systems, 2019

353 citations recorded by the source corpus.

We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution $\nu = e^{-f}$ on $\mathbb{R}^n$. We prove a convergence guarantee in Kullback-Leibler (KL) divergence assuming $\nu$ satisfies a log-Sobolev inequality and the Hessian of $f$ is bounded. Notably, we do not assume convexity or bounds on higher derivatives. We also prove convergence guarantees in Renyi divergence of order $q > 1$ assuming the limit of ULA satisfies either the log-Sobolev or Poincare inequality.

View Paper: https://www.semanticscholar.org/paper/dbc024fb80661114e80e179cdfefb97fe5a58955

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Adil Salim
2. Sitan Chen
3. Sinho Chewi
4. Jungshian Li
5. Yuanzhi Li
6. Anru R. Zhang
7. Michael S. Albergo

Citations in the corpus

• Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions (2022, methodology): “…have TV ( p T , q ) ≤ ε , it suffices to have score error ε score ≤ O ( ε ). e We remark that the iteration complexity of N = Θ( L 2 d ε 2 ) matches state-of-the-art complexity bounds for the Langevin Monte Carlo (LMC) algorithm for sampling under a log-Sobolev inequality (LSI), see [VW19; Che+21a].”