Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo
This provides foundational theoretical guarantees for sampling in non-convex settings, advancing the general theory of non-log-concave sampling with applications to distributions satisfying Poincaré inequalities.
The paper tackles the problem of sampling from non-log-concave densities using Langevin Monte Carlo, proving that it achieves ε-relative Fisher information in O(L²d²/ε²) iterations, analogous to non-convex optimization complexity bounds.
For the task of sampling from a density $π\propto \exp(-V)$ on $\mathbb{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.