# Log-concave sampling: Metropolis-Hastings algorithms are fast

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

## Key facts

- Cited by 118 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2018.

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

- [Improved analysis for a proximal algorithm for sampling](https://mlsanity.com/paper/2202.06386/) (2022)
- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Reverse Diffusion Monte Carlo](https://mlsanity.com/paper/2307.02037/) (2023)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Beyond Log-Concavity and Score Regularity: Improved Convergence Bounds for Score-Based Generative Models in W2-distance](https://mlsanity.com/paper/2501.02298/) (2025)
- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [Stochastic Localization via Iterative Posterior Sampling](https://mlsanity.com/paper/2402.10758/) (2024)
- [A Proximal Algorithm for Sampling from Non-smooth Potentials](https://mlsanity.com/paper/2110.04597/) (2021)
- [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)
- [On the Convergence of Black-Box Variational Inference](https://mlsanity.com/paper/2305.15349/) (2023)
- [On Sampling with Approximate Transport Maps](https://mlsanity.com/paper/2302.04763/) (2023)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Zeroth-Order Sampling Methods for Non-Log-Concave Distributions: Alleviating Metastability by Denoising Diffusion](https://mlsanity.com/paper/2402.17886/) (2024)
- [Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition](https://mlsanity.com/paper/2206.00508/) (2022)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Chain of Log-Concave Markov Chains](https://mlsanity.com/paper/2305.19473/) (2023)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Counterfactual inference in sequential experiments](https://mlsanity.com/paper/2202.06891/) (2022)
- [Denoising MCMC for Accelerating Diffusion-Based Generative Models](https://mlsanity.com/paper/2209.14593/) (2022)
- [Entropy contraction of the Gibbs sampler under log-concavity](https://mlsanity.com/paper/2410.00858/) (2024)
- [When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint](https://mlsanity.com/paper/2110.01827/) (2021)
- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Fast parallel sampling under isoperimetry](https://mlsanity.com/paper/2401.09016/) (2024)
- [Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequality](https://mlsanity.com/paper/2502.05623/) (2025)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Enhanced gradient-based MCMC in discrete spaces](https://mlsanity.com/paper/2208.00040/) (2022)
- [Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators](https://mlsanity.com/paper/2210.07219/) (2022)
- [Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Sampler](https://mlsanity.com/paper/2302.06085/) (2023)

## Abstract (arXiv)

We consider the problem of sampling from a strongly log-concave density in ℝd, and prove a non-asymptotic upper bound on the mixing time of the Metropolis-adjusted Langevin algorithm (MALA). The method draws samples by simulating a Markov chain obtained from the discretization of an appropriate Langevin diffusion, combined with an accept-reject step. Relative to known guarantees for the unadjusted Langevin algorithm (ULA), our bounds show that the use of an accept-reject step in MALA leads to an exponentially improved dependence on the error-tolerance. Concretely, in order to obtain samples with TV error at most δ for a density with condition number kappa, we show that MALA requires O big(kappa d log(1/δ) big) steps, as compared to the O big(kappa2 d/δ2 big) steps established in past work on ULA. We also demonstrate the gains of MALA over ULA for weakly log-concave densities. Furthermore, we derive mixing time bounds for the Metropolized random walk (MRW) and obtain O(kappa) mixing time slower than MALA. We provide numerical examples that support our theoretical findings, and demonstrate the benefits of Metropolis-Hastings adjustment for Langevin-type sampling algorithms.