Momentum-Based Variance Reduction in Non-Convex SGD
Momentum-Based Variance Reduction in Non-Convex SGD
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Ashok Cutkosky;Francesco Orabona
中科院分区：
文献类型：
--
作者：
Ashok Cutkosky;Francesco Orabona
近年来，方差减少已成为非凸问题中随机梯度下降的有力竞争对手，它提供了第一个提高随机梯度下降收敛速度以寻找一阶临界点的算法。然而，方差减少技术通常需要仔细调整学习率并愿意使用过大的“大批量”才能实现改进的结果。我们提出了一种新算法 STORM，它不需要任何批次并利用自适应学习率，从而实现更简单的实现和更少的超参数调整。我们用于删除批次的技术使用动量变体来实现非凸优化中的方差减少。在平滑损失$F$上，STORM在$T$迭代中找到一个点$\boldsymbol{x}$，其中$\mathbb{E}[\|\nabla F(\boldsymbol{x})\|]\le O(1/\sqrt{T}+\sigma^{1/3}/T^{1/3})$，梯度方差为$\sigma^2$，匹配最优速率，但不需要了解$\西格玛$。
Variance reduction has emerged in recent years as a strong competitor to stochastic gradient descent in non-convex problems, providing the first algorithms to improve upon the converge rate of stochastic gradient descent for finding first-order critical points. However, variance reduction techniques typically require carefully tuned learning rates and willingness to use excessively large "mega-batches" in order to achieve their improved results. We present a new algorithm, STORM, that does not require any batches and makes use of adaptive learning rates, enabling simpler implementation and less hyperparameter tuning. Our technique for removing the batches uses a variant of momentum to achieve variance reduction in non-convex optimization. On smooth losses $F$, STORM finds a point $\boldsymbol{x}$ with $\mathbb{E}[\|\nabla F(\boldsymbol{x})\|]\le O(1/\sqrt{T}+\sigma^{1/3}/T^{1/3})$ in $T$ iterations with $\sigma^2$ variance in the gradients, matching the optimal rate but without requiring knowledge of $\sigma$.