Sqrt(d) Dimension Dependence of Langevin Monte Carlo

Abstract

This article considers the popular MCMC method of unadjusted Langevin Monte Carlo (LMC) and provides a non-asymptotic analysis of its sampling error in 2-Wasserstein distance. The proof is based on a refinement of mean-square analysis in Li et al. (2019), and this refined framework automates the analysis of a large class of sampling algorithms based on discretizations of contractive SDEs. Using this framework, we establish an $\tilde{O}(\sqrt{d}/\epsilon )$ mixing time bound for LMC, without warm start, under the common log-smooth and log-strongly-convex conditions, plus a growth condition on the 3rd-order derivative of the potential of target measures. This bound improves the best previously known $\tilde{O}(d/\epsilon )$ result and is optimal (in terms of order) in both dimension $d$ and accuracy tolerance $\epsilon$ for target measures satisfying the aforementioned assumptions. Our theoretical analysis is further validated by numerical experiments.

v1 submitted on May 28, 2021 (NeurIPS 2021 deadline); v2 added an important reference and discussions; v3 is the camera ready version

References in corpus (5)

• Underdamped Langevin MCMC: A non-asymptotic analysis
• The Randomized Midpoint Method for Log-Concave Sampling
• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Optimal dimension dependence of the Metropolis-Adjusted Langevin Algorithm
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling

Cited by in corpus (1)

• The Mirror Langevin Algorithm Converges with Vanishing Bias