Data to 7 Oct 2026

Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm

arXiv 2012.12810 ↗First posted 23 Dec 2020math.ST cs.LG stat.THcited by 57

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 7; 2022: 9; 2023: 14; 2024: 10; 2025: 10; 2026: 7.

57 papers.

Sort:

By area:

2022Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptionscited by 440
2024Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstructioncited by 73
2023Particle Guidance: non-I.I.D. Diverse Sampling with Diffusion Modelscited by 65
2021Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Samplingcited by 44
2023Faster high-accuracy log-concave sampling via algorithmic warm startscited by 44
2023Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequalitycited by 31
2023Improved dimension dependence of a proximal algorithm for samplingcited by 29
2021Sqrt(d) Dimension Dependence of Langevin Monte Carlocited by 25
2022Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Samplingcited by 21
2023On Sampling with Approximate Transport Mapscited by 20
2021Lower Bounds on Metropolized Sampling Methods for Well-Conditioned Distributionscited by 19
2022Mean-field Variational Inference via Wasserstein Gradient Flowcited by 19

38 more

2021Mixing Time Guarantees for Unadjusted Hamiltonian Monte Carlocited by 18
2021The query complexity of sampling from strongly log-concave distributions in one dimensioncited by 18
2022Fisher information lower bounds for samplingcited by 12
2023Query lower bounds for log-concave samplingcited by 12
2023When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?cited by 12
2021Asymptotic bias of inexact Markov Chain Monte Carlo methods in high dimensioncited by 11
2023Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithmcited by 11
2025Mixing Time of the Proximal Sampler in Relative Fisher Information via Strong Data Processing Inequalitycited by 11
2022Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integratorscited by 10
2023Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimationcited by 10
2023Algorithmic Aspects of the Log-Laplace Transform and a Non-Euclidean Proximal Samplercited by 9
2022Hamiltonian Monte Carlo for efficient Gaussian sampling: long and random stepscited by 8
2022Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constantscited by 8
2023Inferring networks from time series: a neural approachcited by 7
2024Sampling from the Mean-Field Stationary Distributioncited by 7
2026High-accuracy and dimension-free sampling with diffusionscited by 7
2022Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithmcited by 6
2022On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributionscited by 6
2024A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplerscited by 5
2025On the query complexity of sampling from non-log-concave distributionscited by 5
2023Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Samplingcited by 4
2023Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithmscited by 4
2024Convergence of Unadjusted Langevin in High Dimensions: Delocalization of Biascited by 4
2024Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spacescited by 3
2024R'enyi-infinity constrained sampling with d3 membership queriescited by 3
2024Mixing of the No-U-Turn Sampler and the Geometry of Gaussian Concentrationcited by 3
2024Fast Mixing of Data Augmentation Algorithms: Bayesian Probit, Logit, and Lasso Regressioncited by 3
2025Active Learning with Bayesian Multi-Fidelity Laplace Neural Operators for Oscillatory Parametric PDEscited by 2
2026High-accuracy log-concave sampling with stochastic queriescited by 2
2024Sampling with Adaptive Variance for Multimodal Distributionscited by 1
2025Operator-Level Quantum Acceleration of Non-Logconcave Samplingcited by 1
2025Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributionscited by 1
2025Sampling by averaging: A multiscale approach to score estimationcited by 1
2026A proximal gradient algorithm for composite log-concave samplingcited by 1
2021On Mixing Times of Metropolized Algorithm With Optimization Step (MAO) : A New Frameworkcited by 0
2023Learning variational autoencoders via MCMC speed measurescited by 0
2024Linear Noise Approximation Assisted Bayesian Inference on Mechanistic Model of Partially Observed Stochastic Reaction Networkcited by 0
2025Exploring Non-Convex Discrete Energy Landscapes: An Efficient Langevin-Like Sampler with Replica Exchangecited by 0

50 most cited of 57 All 57 (JSON)