mlsanityData to 14 Oct 2026

Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions

arXiv 2106.05480 ↗First posted 10 Jun 2021cs.DS cs.CC cs.LGcited by 19

Not on the map. Why?

Abstract (arXiv)

We give lower bounds on the performance of two of the most popular sampling methods in practice, the Metropolis-adjusted Langevin algorithm (MALA) and multi-step Hamiltonian Monte Carlo (HMC) with a leapfrog integrator, when applied to well-conditioned distributions. Our main result is a nearly-tight lower bound of widetildeOmega(kappa d) on the mixing time of MALA from an exponentially warm start, matching a line of algorithmic results up to logarithmic factors and answering an open question of Chewi et. al. We also show that a polynomial dependence on dimension is necessary for the relaxation time of HMC under any number of leapfrog steps, and bound the gains achievable by changing the step count. Our HMC analysis draws upon a novel connection between leapfrog integration and Chebyshev polynomials, which may be of independent interest.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 17 of its 58 references that are in the map. First posted on arXiv 10 Jun 2021.

Builds on

17 of 58 references.

References · 17

  1. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 208
  2. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 146
  3. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 133
  4. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 127
  5. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 118
  6. 2020Structured Logconcave Sampling with a Restricted Gaussian Oraclecited by 86
  7. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 78
  8. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 62
  9. 2020Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithmcited by 57
  10. 2019Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradientscited by 51
  11. 2019High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithmcited by 36
  12. 2019Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributionscited by 28
5 more
  1. 2020Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlocited by 22
  2. 2021Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlocited by 18
  3. 2019Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Boundscited by 16
  4. 2018Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlocited by 11
  5. 2020Oracle Lower Bounds for Stochastic Gradient Sampling Algorithmscited by 8

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 2; 2022: 5; 2023: 7; 2024: 2; 2025: 2; 2026: 1.

19 papers.

Sort:

  1. 2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 45
  2. 2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
  3. 2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
  4. 2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 22
  5. 2023When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?cited by 15
  6. 2022Fisher information lower bounds for samplingcited by 12
  7. 2023Query lower bounds for log-concave samplingcited by 12
  8. 2021Asymptotic bias of inexact Markov Chain Monte Carlo methods in high dimensioncited by 11
  9. 2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 10
  10. 2022Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random stepscited by 8
  11. 2022Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constantscited by 8
  12. 2022Accelerating Hamiltonian Monte Carlo via Chebyshev Integration Timecited by 7
7 more
  1. 2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 6
  2. 2023Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithmscited by 4
  3. 2024Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Biascited by 4
  4. 2025On Accelerated Mixing of the No-U-turn Samplercited by 2
  5. 2025Sampling by averaging: A multiscale approach to score estimationcited by 1
  6. 2026A Theoretical Comparison of No-U-Turn Sampler Variants: Necessary and Sufficient Convergence Conditions and Mixing Time Analysis under Gaussian Targetscited by 1
  7. 2023Learning variational autoencoders via MCMC speed measurescited by 0