We study the problem of sampling from a distribution where the negative logarithm of the target density is $L$-smooth everywhere and $m$-strongly convex outside a ball of radius $R$, but potentially non-convex inside this ball. We study both overdamped and underdamped Langevin MCMC and prove upper bounds on the time required to obtain a sample from a distribution that is within $\epsilon$ of the target distribution in $1$-Wasserstein distance. For the first-order method (overdamped Langevin MCMC), the time complexity is $\tilde{\mathcal{O}}\left(e^{cLR^2}\frac{d}{\epsilon^2}\right)$, where $d$ is the dimension of the underlying space. For the second-order method (underdamped Langevin MCMC), the time complexity is $\tilde{\mathcal{O}}\left(e^{cLR^2}\frac{\sqrt{d}}{\epsilon}\right)$ for some explicit positive constant $c$. Surprisingly, the convergence rate is only polynomial in the dimension $d$ and the target accuracy $\epsilon$. It is however exponential in the problem parameter $LR^2$, which is a measure of non-logconcavity of the target distribution.

本研究研究了在采样中采用了过阻尼和欠阻尼Langevin MCMC，证明了算法的迭代复杂度在维度和目标准确度方面均是多项式级别的，但在问题参数LR ^ 2中是指数级别的，从而可以更好地进行非凸优化。

非凸背景下 Langevin 动力学算法的尖锐收敛速率