Sharp convergence rates for Langevin dynamics in the nonconvex setting

We study the problem of sampling from a distribution p^*(x) propto expleft(-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 ε of p^* in 1-Wasserstein distance. For the first-order method (overdamped Langevin MCMC), the iteration complexity is tildeOleft(ecLR2d/ε2right), where d is the dimension of the underlying space. For the second-order method (underdamped Langevin MCMC), the iteration complexity is tildeOleft(ecLR2√d/ε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 ε. It is exponential, however, in the problem parameter LR2, which is a measure of non-log-concavity of the target distribution.