A spectral gap for Metropolis-adjusted Langevin algorithm with a uniformly randomized step size
Abstract
Let π(d x)∝ e−U(x) d x on ℝd, where U is continuously differentiable and m-strongly convex with a globally L-Lipschitz gradient, 0<m≤ L<∞, and κ=L/m. Fixed-step Metropolis-adjusted Langevin algorithm (MALA) has known warm-start mixing-time upper bounds of order κ√d, up to logarithmic factors. A spectral-gap lower bound at the corresponding scale (κ√d)−1 would give an upper bound of order κ√d on the Monte Carlo asymptotic variance relative to independent sampling, uniformly over all square-integrable functions. However, when κ is bounded away from~1, the best fixed-step spectral gap that can be guaranteed uniformly over this target class is at most of order max{log(κd)/(κd), e−cd} for some positive universal constant~c. We show that uniform randomization of the step size improves this worst-case guarantee. At each iteration, the algorithm draws h∼Unif(0,H) and performs one ordinary MALA transition. Choosing H of order [L√(d(1+log d+logκ))]−1 yields a right spectral-gap lower bound of order 1/(κ√(d(1+log d+logκ))), uniformly over the target class. Thus, given κ> 1, for all square-integrable functions, the ratio of the Monte Carlo asymptotic variance relative to independence sampling has an upper bound of order √(d log d). This contrasts with fixed-MALA, where the ratio can be as bad as d/log d in thew worst-case scenario. The spectral gap also gives geometric convergence of the lazy kernel from every initial density in L2(π), central limit theorems, and nonstationary mean-square error bounds. This work was developed with substantial assistance from ChatGPT.
Related
- Nii-MALA: A Fast Metropolis-Adjusted Langevin Sampler with Radial Velocity Benchmarks
- Persistence Pays: Square-root condition-number dependence for Metropolis-adjusted kinetic Langevin Monte Carlo with a non-reversibly updated accept/reject uniform
- Spectral Gap Inheritance for Metropolis-Hastings with Reversible Proposals
- A spectral clustering-type algorithm for the consistent estimation of the Hurst distribution in moderately high dimensions
- Lifted Restricted Isometry Property and Fast Algorithm for Spectral Compressed Sensing With Near-Optimal Sample Complexity
BibTeX
@misc{qin2026spectral,
title = {{A spectral gap for Metropolis-adjusted Langevin algorithm with a uniformly randomized step size}},
author = {Qian Qin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05847},
eprint = {2609.05847},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05847},
}
RIS
TY - UNPB
TI - A spectral gap for Metropolis-adjusted Langevin algorithm with a uniformly randomized step size
AU - Qian Qin
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.05847
UR - https://arxiv.org/abs/2609.05847
AB - Let π(d x)∝ e^−U(x) d x on ℝ^d, where U is continuously differentiable and m-strongly convex with a globally L-Lipschitz gradient, 0<m≤ L<∞, and κ=L/m. Fixed-step Metropolis-adjusted Langevin algorithm (MALA) has known warm-start mixing-time upper bounds of order κ√d, up to logarithmic factors. A spectral-gap lower bound at the corresponding scale (κ√d)^−1 would give an upper bound of order κ√d on the Monte Carlo asymptotic variance relative to independent sampling, uniformly over all square-integrable functions. However, when κ is bounded away from~1, the best fixed-step spectral gap that can be guaranteed uniformly over this target class is at most of order max{log(κd)/(κd), e^−cd} for some positive universal constant~c. We show that uniform randomization of the step size improves this worst-case guarantee. At each iteration, the algorithm draws h∼Unif(0,H) and performs one ordinary MALA transition. Choosing H of order [L√(d(1+log d+logκ))]^−1 yields a right spectral-gap lower bound of order 1/(κ√(d(1+log d+logκ))), uniformly over the target class. Thus, given κ> 1, for all square-integrable functions, the ratio of the Monte Carlo asymptotic variance relative to independence sampling has an upper bound of order √(d log d). This contrasts with fixed-MALA, where the ratio can be as bad as d/log d in thew worst-case scenario. The spectral gap also gives geometric convergence of the lazy kernel from every initial density in L^2(π), central limit theorems, and nonstationary mean-square error bounds. This work was developed with substantial assistance from ChatGPT.
ER -