# Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm

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

## Key facts

- Cited by 57 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2020.

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

- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction](https://mlsanity.com/paper/2403.17042/) (2024)
- [Particle Guidance: non-I.I.D. Diverse Sampling with Diffusion Models](https://mlsanity.com/paper/2310.13102/) (2023)
- [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)
- [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)
- [Sqrt(d) Dimension Dependence of Langevin Monte Carlo](https://mlsanity.com/paper/2109.03839/) (2021)
- [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)
- [Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributions](https://mlsanity.com/paper/2106.05480/) (2021)
- [Mean-field Variational Inference via Wasserstein Gradient Flow](https://mlsanity.com/paper/2207.08074/) (2022)
- [Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlo](https://mlsanity.com/paper/2105.00887/) (2021)
- [The query complexity of sampling from strongly log-concave distributions in one dimension](https://mlsanity.com/paper/2105.14163/) (2021)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [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)
- [Asymptotic bias of inexact Markov Chain Monte Carlo methods in high dimension](https://mlsanity.com/paper/2108.00682/) (2021)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [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)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [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)
- [Inferring networks from time series: a neural approach](https://mlsanity.com/paper/2303.18059/) (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)
- [On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions](https://mlsanity.com/paper/2209.02001/) (2022)

## Abstract (arXiv)

Conventional wisdom in the sampling literature, backed by a popular diffusion scaling limit, suggests that the mixing time of the Metropolis-Adjusted Langevin Algorithm (MALA) scales as O(d1/3), where d is the dimension. However, the diffusion scaling limit requires stringent assumptions on the target distribution and is asymptotic in nature. In contrast, the best known non-asymptotic mixing time bound for MALA on the class of log-smooth and strongly log-concave distributions is O(d). In this work, we establish that the mixing time of MALA on this class of target distributions is widetildeTheta(d1/2) under a warm start. Our upper bound proof introduces a new technique based on a projection characterization of the Metropolis adjustment which reduces the study of MALA to the well-studied discretization analysis of the Langevin SDE and bypasses direct computation of the acceptance probability.