We present a unified framework to analyze the global convergence of Langevin dynamics based algorithms for nonconvex finite-sum optimization with $n$ component functions. At the core of our analysis is a new decomposition scheme of the optimization error, under which we directly analyze the ergodicity of the numerical approximations of Langevin dynamics and prove sharp convergence rates. We establish the first global convergence guarantee of gradient Langevin dynamics (GLD) with iteration complexity $O\big(1/\epsilon \cdot\log(1/\epsilon)\big)$. In addition, we improve the convergence rate of stochastic gradient Langevin dynamics (SGLD) to the "almost minimizer", which does not depend on the undesirable uniform spectral gap introduced in previous studies. Furthermore, we for the first time prove the global convergence guarantee of variance reduced stochastic gradient Langevin dynamics (VR-SGLD) with iteration complexity $O\big(m/(B\epsilon^3)\cdot\log(1/\epsilon)\big)$, where $B$ is the mini-batch size and $m$ is the length of the inner loop. We show that the gradient complexity of VR-SGLD is $O\big(n^{1/2}/\epsilon^{3/2}\cdot\log(1/\epsilon)\big)$, which outperforms $O\big(n/\epsilon\cdot\log(1/\epsilon)\big)$ gradient complexity of GLD, when the number of component functions satisfies $n \geq 1/\epsilon$. Our theoretical analysis shed some light on using Langevin dynamics based algorithms for nonconvex optimization with provable guarantees.

本文提出了强化的 Langevin dynamics 算法和分析框架，理论证明了全局收敛性，能在各自的梯度复杂度内接近极小值。

基于 Langevin 动力学的非凸优化算法的全局收敛性