On Markov Chain Gradient Descent
On Markov Chain Gradient Descent
复制标题
DOI：
--
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Tao Sun;Yuejiao Sun;W. Yin
中科院分区：
文献类型：
--
作者：
Tao Sun;Yuejiao Sun;W. Yin
随机梯度方法是机器学习、信号处理和其他计算科学和工程中大规模优化问题的主力（算法）。本文研究马尔可夫链梯度下降，随机梯度下降的变种，其中随机样本采取的马尔可夫链的轨迹。现有的方法假设目标是凸的，且是一个可逆的马尔可夫链，因此有其局限性。我们建立了新的非遍历收敛下更宽的步长，非凸问题，和不可逆的有限状态马尔可夫链。非凸性使我们的方法适用于更广泛的问题类。另一方面，不可逆有限状态马尔可夫链可以更快地混合。为了获得这些结果，我们引入了一种新的技术，不同的混合水平的马尔可夫链。数值结果验证了我们的贡献。
Stochastic gradient methods are the workhorse (algorithms) of large-scale optimization problems in machine learning, signal processing, and other computational sciences and engineering. This paper studies Markov chain gradient descent, a variant of stochastic gradient descent where the random samples are taken on the trajectory of a Markov chain. Existing results of this method assume convex objectives and a reversible Markov chain and thus have their limitations. We establish new non-ergodic convergence under wider step sizes, for nonconvex problems, and for non-reversible finite-state Markov chains. Nonconvexity makes our method applicable to broader problem classes. Non-reversible finite-state Markov chains, on the other hand, can mix substatially faster. To obtain these results, we introduce a new technique that varies the mixing levels of the Markov chains. The reported numerical results validate our contributions.