# Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 62 references that are in the map.
- First posted on arXiv 27 Sep 2021.

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

- [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)
- [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)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [Convergence of Langevin MCMC in KL-divergence](https://mlsanity.com/paper/1705.09048/) (2017)
- [Structured Logconcave Sampling with a Restricted Gaussian Oracle](https://mlsanity.com/paper/2010.03106/) (2020)
- [Sharp convergence rates for Langevin dynamics in the nonconvex setting](https://mlsanity.com/paper/1805.01648/) (2018)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm](https://mlsanity.com/paper/2012.12810/) (2020)
- [Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients](https://mlsanity.com/paper/1905.12247/) (2019)
- [Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergence](https://mlsanity.com/paper/2007.11612/) (2020)
- [High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm](https://mlsanity.com/paper/1908.10859/) (2019)
- [Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo](https://mlsanity.com/paper/2002.04121/) (2020)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Nonconvex sampling with the Metropolis-adjusted Langevin algorithm](https://mlsanity.com/paper/1902.08452/) (2019)
- [Hessian-Free High-Resolution Nesterov Acceleration for Sampling](https://mlsanity.com/paper/2006.09230/) (2020)
- [A Cubic Algorithm for Computing Gaussian Volume](https://mlsanity.com/paper/1306.5829/) (2013)

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

- [Variational inference via Wasserstein gradient flows](https://mlsanity.com/paper/2205.15902/) (2022)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Improved dimension dependence of a proximal algorithm for sampling](https://mlsanity.com/paper/2302.10081/) (2023)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [On Sampling with Approximate Transport Maps](https://mlsanity.com/paper/2302.04763/) (2023)
- [Sampling via Gradient Flows in the Space of Probability Measures](https://mlsanity.com/paper/2310.03597/) (2023)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (2024)
- [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)
- [Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random steps](https://mlsanity.com/paper/2209.12771/) (2022)
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://mlsanity.com/paper/2210.06539/) (2022)
- [A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetry](https://mlsanity.com/paper/2304.04095/) (2023)
- [Sampling from the Mean-Field Stationary Distribution](https://mlsanity.com/paper/2402.07355/) (2024)
- [High-accuracy and dimension-free sampling with diffusions](https://mlsanity.com/paper/2601.10708/) (2026)
- [Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithm](https://mlsanity.com/paper/2201.08349/) (2022)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [Faster Sampling via Stochastic Gradient Proximal Sampler](https://mlsanity.com/paper/2405.16734/) (2024)
- [Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentration](https://mlsanity.com/paper/2410.06978/) (2024)
- [Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Sampling](https://mlsanity.com/paper/2303.00570/) (2023)
- [Accelerate Langevin Sampling with Birth-Death Process and Exploration Component](https://mlsanity.com/paper/2305.05529/) (2023)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Ensemble-Based Annealed Importance Sampling](https://mlsanity.com/paper/2401.15645/) (2024)
- [Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian models](https://mlsanity.com/paper/2403.09416/) (2024)
- [Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Bias](https://mlsanity.com/paper/2408.13115/) (2024)
- [Score-Based Metropolis-Hastings Algorithms](https://mlsanity.com/paper/2501.00467/) (2024)
- [Hierarchic Flows to Estimate and Sample High-dimensional Probabilities](https://mlsanity.com/paper/2405.03468/) (2024)
- [Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regression](https://mlsanity.com/paper/2412.07999/) (2024)

## Abstract (arXiv)

We study the mixing time of the Metropolis-adjusted Langevin algorithm (MALA) for sampling from a log-smooth and strongly log-concave distribution. We establish its optimal minimax mixing time under a warm start. Our main contribution is two-fold. First, for a d-dimensional log-concave density with condition number kappa, we show that MALA with a warm start mixes in tilde O(kappa √d) iterations up to logarithmic factors. This improves upon the previous work on the dependency of either the condition number kappa or the dimension d. Our proof relies on comparing the leapfrog integrator with the continuous Hamiltonian dynamics, where we establish a new concentration bound for the acceptance rate. Second, we prove a spectral gap based mixing time lower bound for reversible MCMC algorithms on general state spaces. We apply this lower bound result to construct a hard distribution for which MALA requires at least tilde Omega (kappa √d) steps to mix. The lower bound for MALA matches our upper bound in terms of condition number and dimension. Finally, numerical experiments are included to validate our theoretical results.