# Nonconvex sampling with the Metropolis-adjusted Langevin algorithm

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2019.

## Built on by (most cited first, 15 of 15)

- [Provably Robust Score-Based Diffusion Posterior Sampling for Plug-and-Play Image Reconstruction](https://mlsanity.com/paper/2403.17042/) (2024)
- [Minimax Mixing Time of the Metropolis-Adjusted Langevin Algorithm for Log-Concave Sampling](https://mlsanity.com/paper/2109.13055/) (2021)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [Learning General Halfspaces with General Massart Noise under the Gaussian Distribution](https://mlsanity.com/paper/2108.08767/) (2021)
- [Convergence Rates for Non-Log-Concave Sampling and Log-Partition Estimation](https://mlsanity.com/paper/2303.03237/) (2023)
- [Bregman Proximal Langevin Monte Carlo via Bregman--Moreau Envelopes](https://mlsanity.com/paper/2207.04387/) (2022)
- [ELF: Federated Langevin Algorithms with Primal, Dual and Bidirectional Compression](https://mlsanity.com/paper/2303.04622/) (2023)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Testing Noise Assumptions of Learning Algorithms](https://mlsanity.com/paper/2501.09189/) (2025)
- [Smoothed Agnostic Learning of Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.17782/) (2025)
- [Subsampling Error in Stochastic Gradient Langevin Diffusions](https://mlsanity.com/paper/2305.13882/) (2023)
- [A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube](https://mlsanity.com/paper/2511.07244/) (2025)
- [Efficiently handling constraints with Metropolis-adjusted Langevin algorithm](https://mlsanity.com/paper/2302.11971/) (2023)
- [Gibbs-Based Information Criteria and the Over-Parameterized Regime](https://mlsanity.com/paper/2306.05583/) (2023)
- [Local and Global Contraction Principles for MCMC Mixing](https://mlsanity.com/paper/2606.03033/) (2026)

## Abstract (arXiv)

The Langevin Markov chain algorithms are widely deployed methods to sample from distributions in challenging high-dimensional and non-convex statistics and machine learning applications. Despite this, current bounds for the Langevin algorithms are slower than those of competing algorithms in many important situations, for instance when sampling from weakly log-concave distributions, or when sampling or optimizing non-convex log-densities. In this paper, we obtain improved bounds in many of these situations, showing that the Metropolis-adjusted Langevin algorithm (MALA) is faster than the best bounds for its competitor algorithms when the target distribution satisfies weak third- and fourth- order regularity properties associated with the input data. In many settings, our regularity conditions are weaker than the usual Euclidean operator norm regularity properties, allowing us to show faster bounds for a much larger class of distributions than would be possible with the usual Euclidean operator norm approach, including in statistics and machine learning applications where the data satisfy a certain incoherence condition. In particular, we show that using our regularity conditions one can obtain faster bounds for applications which include sampling problems in Bayesian logistic regression with weakly convex priors, and the nonconvex optimization problem of learning linear classifiers with zero-one loss functions. Our main technical contribution in this paper is our analysis of the Metropolis acceptance probability of MALA in terms of its "energy-conservation error," and our bound for this error in terms of third- and fourth- order regularity conditions. Our combination of this higher-order analysis of the energy conservation error with the conductance method is key to obtaining bounds which have a sub-linear dependence on the dimension d in the non-strongly logconcave setting.