A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates

By Yossi Arjevani, Ohad Shamir, Nati Srebro. 2018

77 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, background): “[4] showed an improved bound matching the non-accelerated (15) for delayed updates (with a fixed delay) on quadratic objectives.”
Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Methods (2022, background): “Similar assumption is widely used to analyze gradient descent with sampling with replacement (SGD) where a noisy oracle for the global function f is assumed [2, 4].”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, methodology): “ of delays in the gradients—compressed gradients with error compensation, and local SGD. 1.1 Main Contributions and Structure Our main contributions are: • In Section 4 we generalize the analysis of (Arjevani et al., 2018) of (D-SGD) to quasi-convex functions, and show the iteration complexity O˜ σ2”