On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness

Abstract

We study sampling from a target distribution ${\nu }_{\ast }=e^{-f}$ using the unadjusted Langevin Monte Carlo (LMC) algorithm. For any potential function $f$ whose tails behave like $\Vert x{\Vert }^{\alpha }$ for $\alpha \in [1,2]$, and has $\beta$-Hölder continuous gradient, we prove that $\tilde{\mathcal{O}}\left(d^{\frac{1}{\beta }+\frac{1+\beta }{\beta }(\frac{2}{\alpha }-1_{\{\alpha \ne 1\}})}{\epsilon }^{-\frac{1}{\beta }}\right)$ steps are sufficient to reach the $\epsilon$-neighborhood of a $d$-dimensional target distribution ${\nu }_{\ast }$ in KL-divergence. This convergence rate, in terms of $\epsilon$ dependency, is not directly influenced by the tail growth rate $\alpha$ of the potential function as long as its growth is at least linear, and it only relies on the order of smoothness $\beta$. One notable consequence of this result is that for potentials with Lipschitz gradient, i.e. $\beta =1$, our rate recovers the best known rate $\tilde{\mathcal{O}}(d{\epsilon }^{-1})$ which was established for strongly convex potentials in terms of $\epsilon$ dependency, but we show that the same rate is achievable for a wider class of potentials that are degenerately convex at infinity. The growth rate $\alpha$ starts to have an effect on the established rate in high dimensions where $d$ is large; furthermore, it recovers the best-known dimension dependency when the tail growth of the potential is quadratic, i.e. $\alpha =2$, in the current setup. Our framework allows for finite perturbations, and any order of smoothness $\beta \in (0,1]$; consequently, our results are applicable to a wide class of non-convex potentials that are weakly smooth and exhibit at least linear tail growth.

arXiv comment51 pages, 2 figures

References in corpus (16)

• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Convergence of Langevin MCMC in KL-divergence
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• The promises and pitfalls of Stochastic Gradient Langevin Dynamics
• Is There an Analog of Nesterov Acceleration for MCMC?
• Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• The Randomized Midpoint Method for Log-Concave Sampling
• Complexity of randomized algorithms for underdamped Langevin dynamics
• Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo
• An Efficient Sampling Algorithm for Non-smooth Composite Potentials
• Langevin Monte Carlo without smoothness
• Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition
• A Moreau-Yosida approximation scheme for a class of high-dimensional posterior distributions
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• Black-box sampling for weakly smooth Langevin Monte Carlo using p-generalized Gaussian smoothing

Cited by in corpus (10)

• Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networks
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• On the Ergodicity, Bias and Asymptotic Normality of Randomized Midpoint Sampling Method
• Sqrt(d) Dimension Dependence of Langevin Monte Carlo
• Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Particle Dual Averaging: Optimization of Mean Field Neural Networks with Global Convergence Rate Analysis
• Approximation of heavy-tailed distributions via stable-driven SDEs
• Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited
• Higher Order Generalization Error for First Order Discretization of Langevin Diffusion