A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates

Yossi Arjevani, Ohad Shamir, Nathan Srebro
Proceedings of the 31st International Conference on Algorithmic Learning Theory, PMLR 117:111-132, 2020.

Abstract

We establish matching upper and lower complexity 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v117-arjevani20a, title = {A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates}, author = {Arjevani, Yossi and Shamir, Ohad and Srebro, Nathan}, booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory}, pages = {111--132}, year = {2020}, editor = {Kontorovich, Aryeh and Neu, Gergely}, volume = {117}, series = {Proceedings of Machine Learning Research}, month = {08 Feb--11 Feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v117/arjevani20a/arjevani20a.pdf}, url = {https://proceedings.mlr.press/v117/arjevani20a.html}, abstract = {We establish matching upper and lower complexity 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.} }
Endnote
%0 Conference Paper %T A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates %A Yossi Arjevani %A Ohad Shamir %A Nathan Srebro %B Proceedings of the 31st International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Aryeh Kontorovich %E Gergely Neu %F pmlr-v117-arjevani20a %I PMLR %P 111--132 %U https://proceedings.mlr.press/v117/arjevani20a.html %V 117 %X We establish matching upper and lower complexity 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.
APA
Arjevani, Y., Shamir, O. & Srebro, N.. (2020). A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates. Proceedings of the 31st International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 117:111-132 Available from https://proceedings.mlr.press/v117/arjevani20a.html.

Related Material