# Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo

arXiv: https://arxiv.org/abs/2202.05214 · HTML: https://mlsanity.com/paper/2202.05214/

## Key facts

- Cited by 63 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 69 references that are in the map.
- First posted on arXiv 10 Feb 2022.

## Builds on (most cited first, 22 of 22)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis](https://mlsanity.com/paper/1702.03849/) (2017)
- [Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices](https://mlsanity.com/paper/1903.08568/) (2019)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization](https://mlsanity.com/paper/1707.06618/) (2017)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [The promises and pitfalls of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1811.10072/) (2018)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [Assigning a value to a power likelihood in a general Bayesian model](https://mlsanity.com/paper/1701.08515/) (2017)
- [Global Non-convex Optimization with Discretized Diffusions](https://mlsanity.com/paper/1810.12361/) (2018)
- [Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity](https://mlsanity.com/paper/1907.11331/) (2019)
- [Non-asymptotic bounds for sampling algorithms without log-concavity](https://mlsanity.com/paper/1808.07105/) (2018)
- [Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond](https://mlsanity.com/paper/1906.07868/) (2019)
- [Langevin Monte Carlo without smoothness](https://mlsanity.com/paper/1905.13285/) (2019)
- [On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1802.05431/) (2018)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [Bayesian model comparison with the Hyv"arinen score: computation and consistency](https://mlsanity.com/paper/1711.00136/) (2017)
- [Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithm](https://mlsanity.com/paper/2201.08349/) (2022)

## Built on by (most cited first, 30 of 63)

- [Principled Probabilistic Imaging using Diffusion Models as Plug-and-Play Priors](https://mlsanity.com/paper/2405.18782/) (2024)
- [Provable Probabilistic Imaging using Score-Based Generative Priors](https://mlsanity.com/paper/2310.10835/) (2023)
- [Forward-backward Gaussian variational inference via JKO in the Bures-Wasserstein Space](https://mlsanity.com/paper/2304.05398/) (2023)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Provable Benefit of Annealed Langevin Monte Carlo for Non-log-concave Sampling](https://mlsanity.com/paper/2407.16936/) (2024)
- [A Proximal Algorithm for Sampling](https://mlsanity.com/paper/2202.13975/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Regularized Stein Variational Gradient Flow](https://mlsanity.com/paper/2211.07861/) (2022)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [Split Gibbs Discrete Diffusion Posterior Sampling](https://mlsanity.com/paper/2503.01161/) (2025)
- [Sampling with Mollified Interaction Energy Descent](https://mlsanity.com/paper/2210.13400/) (2022)
- [Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization](https://mlsanity.com/paper/2203.16217/) (2022)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality](https://mlsanity.com/paper/2502.05623/) (2025)
- [Theoretical Guarantees for Variational Inference with Fixed-Variance Mixture of Gaussians](https://mlsanity.com/paper/2406.04012/) (2024)
- [Complexity Analysis of Normalizing Constant Estimation: from Jarzynski Equality to Annealed Importance Sampling and beyond](https://mlsanity.com/paper/2502.04575/) (2025)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited](https://mlsanity.com/paper/2306.08494/) (2023)
- [Particle-based Variational Inference with Generalized Wasserstein Gradient Flow](https://mlsanity.com/paper/2310.16516/) (2023)
- [Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms](https://mlsanity.com/paper/2206.03792/) (2022)
- [Taming under isoperimetry](https://mlsanity.com/paper/2311.09003/) (2023)
- [Taming Score-Based Diffusion Priors for Infinite-Dimensional Nonlinear Inverse Problems](https://mlsanity.com/paper/2405.15676/) (2024)
- [Tamed Langevin sampling under weaker conditions](https://mlsanity.com/paper/2405.17693/) (2024)
- [Constrained Langevin Algorithms with L-mixing External Random Variables](https://mlsanity.com/paper/2205.14192/) (2022)
- [Provably Fast Finite Particle Variants of SVGD via Virtual Particle Stochastic Approximation](https://mlsanity.com/paper/2305.17558/) (2023)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [The Poisson Midpoint Method for Langevin Dynamics: Provably Efficient Discretization for Diffusion Models](https://mlsanity.com/paper/2405.17068/) (2024)
- [Fast Conditional Mixing of MCMC Algorithms for Non-log-concave Distributions](https://mlsanity.com/paper/2306.10506/) (2023)

## Abstract (arXiv)

For the task of sampling from a density π propto exp(-V) on ℝ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( L2 d2/varepsilon2) 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'e inequality.