Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods
Nicolas Loizou School of Mathematics, The University of Edinburgh. — E-mail: Peter Richtárik CEMSE, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia — School of Mathematics, The University of Edinburgh, United Kingdom — Moscow Institute of Physics and Technology (MIPT), Dolgoprudny, Moscow, Russia.— E-mail:
Abstract
In this paper we study several classes of stochastic optimization algorithms enriched with heavy ball momentum. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic dual subspace ascent. This is the first time momentum variants of several of these methods are studied. We choose to perform our analysis in a setting in which all of the above methods are equivalent. We prove global nonassymptotic linear convergence rates for all methods and various measures of success, including primal function values, primal iterates (in L2 sense), and dual function values. We also show that the primal iterates converge at an accelerated linear rate in the L1 sense. This is the first time a linear rate is shown for the stochastic heavy ball method (i.e., stochastic gradient descent method with momentum). Under somewhat weaker conditions, we establish a sublinear convergence rate for Cesaro averages of primal iterates. Moreover, we propose a novel concept, which we call stochastic momentum, aimed at decreasing the cost of performing the momentum step. We prove linear convergence of several stochastic methods with stochastic momentum, a
中文速览
带动量的随机优化方法长期缺乏收敛性保证——人们知道随机梯度下降（SGD）加上重球动量（heavy ball momentum）在深度学习中好用，却始终无法证明它能线性收敛。本文把随机梯度下降、随机牛顿法、随机近端点法和随机对偶子空间上升法统一在同一个框架下，首次证明了带重球动量的随机方法（mSGD等）在求解线性方程组对应的随机优化问题时，具有全局非渐近线性收敛率，并在L1意义下达到加速线性收敛。此外，论文还提出了"随机动量"这一新概念——每步只以一定概率执行动量更新，从而降低计算开销，并证明在数据稀疏场景下这类方法的总体复杂度优于确定性动量方法。这项工作填补了随机重球方法理论分析的空白，为在大规模数据优化中安全、有据可依地使用动量技术提供了理论基础。
原文 arXiv:1712.09677;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1712.09677v2