Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices

Santosh S. Vempala, Andre Wibisono

Abstract

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 R\'enyi divergence of order $q > 1$ assuming the limit of ULA satisfies either the log-Sobolev or Poincar\'e inequality. We also prove a bound on the bias of the limiting distribution of ULA assuming third-order smoothness of $f$, without requiring isoperimetry.
BibTeX
@inproceedings{vempala2019rapid,
  author = {Santosh S. Vempala and Andre Wibisono},
  title = {{Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=tUogTcjIP4},
}
Figure