Sqrt(d) Dimension Dependence of Langevin Monte Carlo
This provides a theoretical improvement for sampling algorithms in machine learning and statistics, though it is incremental as it refines prior analysis.
The paper tackles the problem of analyzing the sampling error of unadjusted Langevin Monte Carlo (LMC) for high-dimensional target measures, establishing an optimal mixing time bound of $ ilde{O}(\sqrt{d}/\epsilon)$ under log-smooth and log-strongly-convex conditions, which improves the previous best bound of $ ilde{O}(d/\epsilon)$.
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}/ε)$ 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/ε)$ result and is optimal (in terms of order) in both dimension $d$ and accuracy tolerance $ε$ for target measures satisfying the aforementioned assumptions. Our theoretical analysis is further validated by numerical experiments.