A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
复制标题
DOI：
--
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Yossi Arjevani;Ohad Shamir;N. Srebro
中科院分区：
文献类型：
--
作者：
Yossi Arjevani;Ohad Shamir;N. Srebro
我们给出了二次函数的梯度下降和随机梯度下降的紧有限时间收敛界，当梯度被延迟并反映从$tau$轮次开始的迭代时。首先，我们证明了在没有随机噪声的情况下，延迟对可获得的优化误差有很大的影响：事实上，这种误差可能与只对$1/tau$的梯度运行的非延迟梯度下降一样糟糕。与之形成鲜明对比的是，我们量化了随机噪声如何使延迟的影响可以忽略不计，改进了以前的工作，这些工作只渐近地或对于小得多的延迟显示了这种现象。此外，在分布式优化的背景下，结果表明，带延迟的梯度下降法的性能与小批量等同步方法相当。我们的结果是基于一种使用母函数分析优化算法的收敛的新技术。
We provide tight finite-time convergence bounds for gradient descent and stochastic gradient descent on quadratic functions, when the gradients are delayed and reflect iterates from $\tau$ rounds ago. First, we show that without stochastic noise, delays strongly affect the attainable optimization error: In fact, the error can be as bad as non-delayed gradient descent ran on only $1/\tau$ of the gradients. In sharp contrast, we quantify how stochastic noise makes the effect of delays negligible, improving on previous work which only showed this phenomenon asymptotically or for much smaller delays. Also, in the context of distributed optimization, the results indicate that the performance of gradient descent with delays is competitive with synchronous approaches such as mini-batching. Our results are based on a novel technique for analyzing convergence of optimization algorithms using generating functions.