On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
复制标题
DOI：
--
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Xiaoyun Li;Francesco Orabona
中科院分区：
文献类型：
--
作者：
Xiaoyun Li;Francesco Orabona
随机梯度下降是机器学习目标函数大规模优化的首选方法。然而，其性能变化很大，并且在很大程度上取决于步长的选择。这激发了对自适应步长的大量研究。然而，目前我们对这些方法的理论理解存在差距，特别是在非凸设置中。在本文中，我们开始缩小这一差距：我们在凸和非凸设置中理论上分析了 AdaGrad 步长的广义版本。我们展示了这些步长几乎可以肯定地渐近收敛到零的充分条件，证明了非凸设置中广义 AdaGrad 步长的第一个保证。此外，我们表明这些步长允许自动适应凸和非凸设置中随机梯度的噪声水平，在 $O(1/T)$ 和 $O(1/\sqrt{T})$ 之间插值，直至对数项。
Stochastic gradient descent is the method of choice for large scale optimization of machine learning objective functions. Yet, its performance is greatly variable and heavily depends on the choice of the stepsizes. This has motivated a large body of research on adaptive stepsizes. However, there is currently a gap in our theoretical understanding of these methods, especially in the non-convex setting. In this paper, we start closing this gap: we theoretically analyze in the convex and non-convex settings a generalized version of the AdaGrad stepsizes. We show sufficient conditions for these stepsizes to achieve almost sure asymptotic convergence of the gradients to zero, proving the first guarantee for generalized AdaGrad stepsizes in the non-convex setting. Moreover, we show that these stepsizes allow to automatically adapt to the level of noise of the stochastic gradients in both the convex and non-convex settings, interpolating between $O(1/T)$ and $O(1/\sqrt{T})$, up to logarithmic terms.