Sharp convergence rates for Langevin dynamics in the nonconvex setting

MaRDI QIDQ6301158zbMATH OpenFDO

Authors Xiang Cheng, Niladri S. Chatterji, Yasin Abbasi-Yadkori, Peter L. Bartlett, Michael Jordan

Publication date 4 May 2018

Abstract: We study the problem of sampling from a distribution $p^{\ast }(x)proptoexpleft(-U(x)ight)$, 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^{\ast }$ in $1$-Wasserstein distance. For the first-order method (overdamped Langevin MCMC), the iteration complexity is $ildemathcalOleft(e^{cL{R}^2}d/epsilo{n}^{2}ight)$, where $d$ is the dimension of the underlying space. For the second-order method (underdamped Langevin MCMC), the iteration complexity is $ildemathcalOleft(e^{cL{R}^2}sqrtd/epsilonight)$ 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 $L{R}^2$, which is a measure of non-log-concavity of the target distribution.

This page was built for publication: Sharp convergence rates for Langevin dynamics in the nonconvex setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301158)