Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization
Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization
复制标题
DOI：
10.48550/arxiv.2203.16217
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Yuri Kinoshita;Taiji Suzuki
中科院分区：
文献类型：
--
作者：
Yuri Kinoshita;Taiji Suzuki
随机梯度朗之万动力学是解决采样问题和非凸优化的最基本算法之一，出现在许多机器学习应用中。特别是，它的减方差版本在今天得到了特别的关注。本文研究了这类问题的两个变体，即随机方差降阶梯度朗之万动力学和随机递归梯度朗之万动力学。我们在光滑性和Log-Sobolev不等式的单独假设下证明了它们对目标分布的收敛性，这些条件比这些算法在以前的工作中使用的条件弱。将批大小和内部循环长度设置为$\sqrt{n}$后，实现$\epsilon$ -精度的梯度复杂度为$\tilde{O}((n+dn^{1/2}\epsilon^{-1})\gamma^2 L^2\alpha^{-2})$，这比以前的任何分析都有所改进。我们还展示了我们的结果在非凸优化中的一些基本应用。
The stochastic gradient Langevin Dynamics is one of the most fundamental algorithms to solve sampling problems and non-convex optimization appearing in several machine learning applications. Especially, its variance reduced versions have nowadays gained particular attention. In this paper, we study two variants of this kind, namely, the Stochastic Variance Reduced Gradient Langevin Dynamics and the Stochastic Recursive Gradient Langevin Dynamics. We prove their convergence to the objective distribution in terms of KL-divergence under the sole assumptions of smoothness and Log-Sobolev inequality which are weaker conditions than those used in prior works for these algorithms. With the batch size and the inner loop length set to $\sqrt{n}$, the gradient complexity to achieve an $\epsilon$-precision is $\tilde{O}((n+dn^{1/2}\epsilon^{-1})\gamma^2 L^2\alpha^{-2})$, which is an improvement from any previous analyses. We also show some essential applications of our result to non-convex optimization.