mlsanityData to 7 Oct 2026

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

arXiv 2109.13055 ↗First posted 27 Sep 2021stat.ML cs.LG stat.COcited by 44

Not on the map. Why?

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.

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

Builds on

18 of 62 references.

References · 18

  1. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  2. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  3. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 144
  4. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  5. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 117
  6. 2017Convergence of Langevin MCMC in KL-divergencecited by 86
  7. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 85
  8. 2018Sharp convergence rates for Langevin dynamics in the nonconvex settingcited by 67
  9. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 61
  10. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  11. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  12. 2020Convergence of Langevin Monte Carlo in Chi-Squared and Renyi Divergencecited by 42
6 more
  1. 2019High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithmcited by 36
  2. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  3. 2021Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributionscited by 19
  4. 2019Nonconvex sampling with the Metropolis-adjusted Langevin algorithmcited by 15
  5. 2020Hessian-Free High-Resolution Nesterov Acceleration for Samplingcited by 7
  6. 2013A Cubic Algorithm for Computing Gaussian Volumecited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 12; 2024: 11; 2025: 8; 2026: 7.

44 papers.

Sort:

By area:

  1. 2022Variational inference via Wasserstein gradient flowscited by 84
  2. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
  3. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  4. 2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
  5. 2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 21
  6. 2023On Sampling with Approximate Transport Mapscited by 20
  7. 2023Sampling via Gradient Flows in the Space of Probability Measurescited by 20
  8. 2022Fisher information lower bounds for samplingcited by 12
  9. 2023Query lower bounds for log-concave samplingcited by 12
  10. 2023When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?cited by 12
  11. 2024Entropy contraction of the Gibbs sampler under log-concavitycited by 12
  12. 2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 11
32 more
  1. 2022Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random stepscited by 8
  2. 2022Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constantscited by 8
  3. 2023A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetrycited by 7
  4. 2024Sampling from the Mean-Field Stationary Distributioncited by 7
  5. 2026High-accuracy and dimension-free sampling with diffusionscited by 7
  6. 2022Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithmcited by 6
  7. 2024Faster Sampling via Stochastic Gradient Proximal Samplercited by 5
  8. 2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 5
  9. 2023Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Samplingcited by 4
  10. 2023Accelerate Langevin Sampling with Birth-Death Process and Exploration Componentcited by 4
  11. 2023Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithmscited by 4
  12. 2024Ensemble-Based Annealed Importance Samplingcited by 4
  13. 2024Scalability of Metropolis-within-Gibbs schemes for high-dimensional Bayesian modelscited by 4
  14. 2024Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Biascited by 4
  15. 2024Score-Based Metropolis-Hastings Algorithmscited by 4
  16. 2024Hierarchic Flows to Estimate and Sample High-dimensional Probabilitiescited by 3
  17. 2024Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentrationcited by 3
  18. 2024Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regressioncited by 3
  19. 2025A Langevin sampling algorithm inspired by the Adam optimizercited by 3
  20. 2025Mixing times of data-augmentation Gibbs samplers for high-dimensional probit regressioncited by 2
  21. 2026High-accuracy log-concave sampling with stochastic queriescited by 2
  22. 2025Convergence Analysis of the Wasserstein Proximal Algorithm beyond Geodesic Convexitycited by 1
  23. 2025Operator-Level Quantum Acceleration of Non-Logconcave Samplingcited by 1
  24. 2025Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributionscited by 1
  25. 2025Sampling by averaging: A multiscale approach to score estimationcited by 1
  26. 2026A Non-asymptotic Analysis for Learning and Applying a Preconditioner in MCMCcited by 1
  27. 2026A proximal gradient algorithm for composite log-concave samplingcited by 1
  28. 2026A Mathematical Introduction to Diffusion Modelscited by 1
  29. 2026Windowed thinning and query complexity for the bouncy particle and Zigzag samplerscited by 1
  30. 2023Learning variational autoencoders via MCMC speed measurescited by 0
  31. 2025Polynomial Mixing Times of Simulated Tempering for Mixture Targets by Conductance Decompositioncited by 0
  32. 2026Accelerated High-Accuracy Sampling from a Warm Start via the Proximal Bouncy Particle Samplercited by 0