# Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 99 references that are in the map.
- First posted on arXiv 16 Oct 2022.

## Builds on (most cited first, 30 of 48)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [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)
- [Theoretical guarantees for approximate sampling from smooth and log-concave densities](https://mlsanity.com/paper/1412.7392/) (2014)
- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [High-dimensional Bayesian inference via the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1605.01559/) (2016)
- [Underdamped Langevin MCMC: A non-asymptotic analysis](https://mlsanity.com/paper/1707.03663/) (2017)
- [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)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient](https://mlsanity.com/paper/1710.00095/) (2017)
- [Privacy Amplification by Iteration](https://mlsanity.com/paper/1808.06651/) (2018)
- [Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreau](https://mlsanity.com/paper/1612.07471/) (2016)
- [The Randomized Midpoint Method for Log-Concave Sampling](https://mlsanity.com/paper/1909.05503/) (2019)
- [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Mirrored Langevin Dynamics](https://mlsanity.com/paper/1802.10174/) (2018)
- [Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss](https://mlsanity.com/paper/2205.13710/) (2022)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Wasserstein Control of Mirror Langevin Monte Carlo](https://mlsanity.com/paper/2002.04363/) (2020)
- [On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness](https://mlsanity.com/paper/2005.13097/) (2020)
- [Efficient constrained sampling via the mirror-Langevin algorithm](https://mlsanity.com/paper/2010.16212/) (2020)
- [Sampling from a log-concave distribution with Projected Langevin Monte Carlo](https://mlsanity.com/paper/1507.02564/) (2015)
- [Differentially Private Learning Needs Hidden State (Or Much Faster Convergence)](https://mlsanity.com/paper/2203.05363/) (2022)
- [Global Non-convex Optimization with Discretized Diffusions](https://mlsanity.com/paper/1810.12361/) (2018)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)

## Built on by (most cited first, 22 of 22)

- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Certified Machine Unlearning via Noisy Stochastic Gradient Descent](https://mlsanity.com/paper/2403.17105/) (2024)
- [Shifted Interpolation for Differential Privacy](https://mlsanity.com/paper/2403.00278/) (2024)
- [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)
- [Fast Convergence of Phi-Divergence Along the Unadjusted Langevin Algorithm and Proximal Sampler](https://mlsanity.com/paper/2410.10699/) (2024)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness](https://mlsanity.com/paper/2410.01068/) (2024)
- [Parallel Simulation for Log-concave Sampling and Score-based Diffusion Models](https://mlsanity.com/paper/2412.07435/) (2024)
- [Concentration of the Langevin Algorithm's Stationary Distribution](https://mlsanity.com/paper/2212.12629/) (2022)
- [Characterizing Dependence of Samples along the Langevin Dynamics and Algorithms via Contraction of Phi-Mutual Information](https://mlsanity.com/paper/2402.17067/) (2024)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy](https://mlsanity.com/paper/2310.14661/) (2023)
- [Sampling with Adaptive Variance for Multimodal Distributions](https://mlsanity.com/paper/2411.15220/) (2024)
- [Online Learning and Unlearning](https://mlsanity.com/paper/2505.08557/) (2025)
- [Learning with Simulators: No Regret in a Computationally Bounded World](https://mlsanity.com/paper/2606.13576/) (2026)
- [Mixing Times and Privacy Analysis for the Projected Langevin Algorithm under a Modulus of Continuity](https://mlsanity.com/paper/2501.04134/) (2025)
- [Privacy Amplification in Differentially Private Zeroth-Order Optimization with Hidden States](https://mlsanity.com/paper/2506.00158/) (2025)
- [Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data](https://mlsanity.com/paper/2605.11170/) (2026)
- [Local and Global Contraction Principles for MCMC Mixing](https://mlsanity.com/paper/2606.03033/) (2026)

## Abstract (arXiv)

Sampling from a high-dimensional distribution is a fundamental task in statistics, engineering, and the sciences. A canonical approach is the Langevin Algorithm, i.e., the Markov chain for the discretized Langevin Diffusion. This is the sampling analog of Gradient Descent. Despite being studied for several decades in multiple communities, tight mixing bounds for this algorithm remain unresolved even in the seemingly simple setting of log-concave distributions over a bounded domain. This paper completely characterizes the mixing time of the Langevin Algorithm to its stationary distribution in this setting (and others). This mixing result can be combined with any bound on the discretization bias in order to sample from the stationary distribution of the continuous Langevin Diffusion. In this way, we disentangle the study of the mixing and bias of the Langevin Algorithm. Our key insight is to introduce a technique from the differential privacy literature to the sampling literature. This technique, called Privacy Amplification by Iteration, uses as a potential a variant of R'enyi divergence that is made geometrically aware via Optimal Transport smoothing. This gives a short, simple proof of optimal mixing bounds and has several additional appealing properties. First, our approach removes all unnecessary assumptions required by other sampling analyses. Second, our approach unifies many settings: it extends unchanged if the Langevin Algorithm uses projections, stochastic mini-batch gradients, or strongly convex potentials (whereby our mixing time improves exponentially). Third, our approach exploits convexity only through the contractivity of a gradient step -- reminiscent of how convexity is used in textbook proofs of Gradient Descent. In this way, we offer a new approach towards further unifying the analyses of optimization and sampling algorithms.