Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices

Santosh Vempala; Andre Wibisono

NeurIPS 2019poster336 citations

Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices

Abstract

We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution $\nu = e^{-f}$ on $\R^n$. We prove a convergence guarantee in Kullback-Leibler (KL) divergence assuming $\nu$ satisfies log-Sobolev inequality and $f$ has bounded Hessian. 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 log-Sobolev or Poincar\'e inequality.

BibTeX

@inproceedings{NEURIPS2019_65a99bb7,
 author = {Vempala, Santosh and Wibisono, Andre},
 booktitle = {Advances in Neural Information Processing Systems},
 editor = {H. Wallach and H. Larochelle and A. Beygelzimer and F. d\textquotesingle Alch\'{e}-Buc and E. Fox and R. Garnett},
 pages = {},
 publisher = {Curran Associates, Inc.},
 title = {Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices},
 url = {https://proceedings.neurips.cc/paper_files/paper/2019/file/65a99bb7a3115fdede20da98b08a370f-Paper.pdf},
 volume = {32},
 year = {2019}
}