Sharp Convergence Rates for Langevin Dynamics in the Nonconvex Setting
We study the problem of sampling from a distribution $p^(x) \propto \exp\left( U(x)\right) where the function $U$ is $L$ smooth everywhere and $m$ strongly convex outside a ball of radius $R$ but potentially nonconvex inside this ball. We study both overdamped and underdamped Langevin MCMC and establish upper bounds on the number of steps required to obtain a sample from a distribution that is within \epsilon$ of $p^ in $1$ Wasserstein distance. For the first order method (overdamped Langevin MCMC) the iteration complexity is \tilde{\mathcal{O}\left(e^{cLR^2}d/\epsilon^2\right) where $d$ is the dimension of the underlying space. For the second order method (underdamped Langevin MCMC) the iteration complexity is \tilde{\mathcal{O}\left(e^{cLR^2}\sqrt{d}\epsilon\right) for an explicit positive constant $c$ Surprisingly, the iteration complexity for both these algorithms is only polynomial in the dimension $d$ and the target accuracy \epsilon$ It is exponential, however, in the problem parameter $LR^2$ which is a measure of non log concavity of the target distribution.
ArXiv