SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
复制标题
DOI：
--
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Lam M. Nguyen;Phuong Ha Nguyen;Marten van Dijk;Peter Richtárik;K. Scheinberg;Martin Takác
中科院分区：
文献类型：
--
作者：
Lam M. Nguyen;Phuong Ha Nguyen;Marten van Dijk;Peter Richtárik;K. Scheinberg;Martin Takác
随机梯度下降(SGD)是许多机器学习应用中选择的优化算法，如正则化经验风险最小化和训练深度神经网络。在随机梯度范数一致有界的假设下，进行了SGD的经典收敛分析。虽然这可能适用于一些损失函数，但对于目标函数是强凸的情况，它总是被违反。在(Bottou等人，2016)中，在随机梯度关于真梯度范数有界的假设下，对SGD的收敛进行了新的分析。在这里，我们证明了对于机器学习中出现的随机问题，这个界总是成立的；我们还提出了一种学习速率递减的SGD的替代收敛分析，其结果比(Bottou等人，2016)中的条件更宽松。然后我们继续进行异步并行设置，并证明了HogWild的收敛！算法，在学习速率减小的情况下，得到了该方法的第一个收敛结果。
Stochastic gradient descent (SGD) is the optimization algorithm of choice in many machine learning applications such as regularized empirical risk minimization and training deep neural networks. The classical convergence analysis of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss functions, it is always violated for cases where the objective function is strongly convex. In (Bottou et al.,2016), a new analysis of convergence of SGD is performed under the assumption that stochastic gradients are bounded with respect to the true gradient norm. Here we show that for stochastic problems arising in machine learning such bound always holds; and we also propose an alternative convergence analysis of SGD with diminishing learning rate regime, which results in more relaxed conditions than those in (Bottou et al.,2016). We then move on the asynchronous parallel setting, and prove convergence of Hogwild! algorithm in the same regime, obtaining the first convergence results for this method in the case of diminished learning rate.