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

preprint2020arXivOpen access

Abstract

We study sampling from a target distribution ν∗=e−f{ν_* = e^{-f}} using the unadjusted Langevin Monte Carlo (LMC) algorithm. For any potential function ff whose tails behave like ∥x∥α{\|x\|^α} for α∈[1,2]{α\in [1,2]}, and has ββ-Hölder continuous gradient, we prove that O~(d1β+1+ββ(2α−1{α≠1})ε−1β){\widetilde{\mathcal{O}} \Big(d^{\frac{1}β+\frac{1+β}β(\frac{2}α - \boldsymbol{1}_{\{α\neq 1\}})} ε^{-\frac{1}β}\Big)} steps are sufficient to reach the εε-neighborhood of a dd-dimensional target distribution ν∗ν_* in KL-divergence. This convergence rate, in terms of εε dependency, is not directly influenced by the tail growth rate αα of the potential function as long as its growth is at least linear, and it only relies on the order of smoothness ββ. One notable consequence of this result is that for potentials with Lipschitz gradient, i.e. β=1β=1, our rate recovers the best known rate O~(dε−1){\widetilde{\mathcal{O}}(dε^{-1})} which was established for strongly convex potentials in terms of εε 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 αα starts to have an effect on the established rate in high dimensions where dd is large; furthermore, it recovers the best-known dimension dependency when the tail growth of the potential is quadratic, i.e. α=2{α= 2}, in the current setup. Our framework allows for finite perturbations, and any order of smoothness β∈(0,1]{β\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.