Towards a Theory of Non-Log-Concave Sampling:First-Order Stationarity Guarantees for Langevin Monte Carlo
Abstract
For the task of sampling from a density $\pi \propto \exp(-V)$ on $\R^d$, where $V$ is possibly non-convex but $L$-gradient Lipschitz, we prove that averaged Langevin Monte Carlo outputs a sample with $\varepsilon$-relative Fisher information after $O(L^2 d^2/\varepsilon^2)$ iterations. This is the sampling analogue of complexity bounds for finding an $\varepsilon$-approximate first-order stationary points in non-convex optimization and therefore constitutes a first step towards the general theory of non-log-concave sampling. We discuss numerous extensions and applications of our result; in particular, it yields a new state-of-the-art guarantee for sampling from distributions which satisfy a Poincaré inequality.
Cite
Text
Balasubramanian et al. "Towards a Theory of Non-Log-Concave Sampling:First-Order Stationarity Guarantees for Langevin Monte Carlo." Conference on Learning Theory, 2022.Markdown
[Balasubramanian et al. "Towards a Theory of Non-Log-Concave Sampling:First-Order Stationarity Guarantees for Langevin Monte Carlo." Conference on Learning Theory, 2022.](https://mlanthology.org/colt/2022/balasubramanian2022colt-theory/)BibTeX
@inproceedings{balasubramanian2022colt-theory,
title = {{Towards a Theory of Non-Log-Concave Sampling:First-Order Stationarity Guarantees for Langevin Monte Carlo}},
author = {Balasubramanian, Krishna and Chewi, Sinho and Erdogdu, Murat A and Salim, Adil and Zhang, Shunshi},
booktitle = {Conference on Learning Theory},
year = {2022},
pages = {2896-2923},
volume = {178},
url = {https://mlanthology.org/colt/2022/balasubramanian2022colt-theory/}
}