Toward Understanding the Impact of Staleness in Distributed Machine Learning

Wei Dai, Yi Zhou, Nanqing Dong, Hao Zhang, Eric P. Xing

This paper, published at ICLR 2019, provides a comprehensive look at one of the most persistent headaches in distributed systems: staleness. When training machine learning models across many machines, developers often choose between "synchronous" (everyone waits for everyone else) and "asynchronous" (everyone goes as fast as they can) execution. The latter is faster but results in workers using "stale" model parameters that don't reflect the most recent updates.

TL;DR

The authors systematically decouple system performance from statistical efficiency to show that staleness impacts different ML models and optimizers in wildly different ways. They introduce "gradient coherence" as a key metric to explain why some algorithms are robust to delays while others fail, and they provide a new theoretical convergence proof for asynchronous SGD in non-convex optimization.

What Problem Does This Paper Address?

In distributed machine learning, there is a fundamental trade-off between system throughput (how many batches you can process per second) and statistical efficiency (how much progress each batch makes toward the goal).

Asynchronous systems have high throughput because they eliminate "straggler" effects—no one waits for the slowest machine. However, they suffer from staleness. Previous research was contradictory: some papers claimed asynchrony is a "free lunch" for speed, while others showed it severely damages model quality. This paper seeks to resolve these contradictions by asking: How exactly does staleness affect convergence across different models, and can we predict which algorithms will handle it best?

Methods and Datasets

The researchers used a simulation-based approach to isolate the effects of staleness. By running experiments on a single machine and manually injecting delays ($s$), they could precisely control the level of staleness without the "noise" of real-world network fluctuations.

They tested a massive matrix of models and algorithms across several standard benchmarks:

  • Models: CNNs (ResNets on CIFAR-10), RNNs (LSTMs on Penn Treebank), DNNs, Multi-class Logistic Regression (MLR), and VAEs (on MNIST), LDA (on 20 NewsGroup), and Matrix Factorization (on MovieLens 1M).
  • Algorithms: 7 different optimizers including vanilla SGD, Momentum, Adam, Adagrad, and RMSProp.
  • Staleness Levels: Ranging from 0 (synchronous) to 50 (very stale).

Crucially, they introduced the concept of Gradient Coherence—a measure of the cosine similarity between current gradients and those from previous iterations. If gradients are "coherent" (pointing in similar directions over time), the model should theoretically be more tolerant of stale information.

Key Insights and Ideas

  • Depth Breeds Sensitivity: Deeper models are significantly more fragile under staleness. For example, staleness slowed down a ResNet-32 much more than a ResNet-8. This suggests that as models get more complex, the "cost" of asynchrony rises.
Impact of staleness on CNNs (ResNets) with varying depths and optimizers.
  • Optimizer Robustness Varies: Adagrad proved remarkably robust to staleness, whereas Momentum-based methods and Adam were highly sensitive. This explains why previous literature was so divided—the "success" of an asynchronous system often depends entirely on which optimizer was chosen.
Impact of staleness on DNNs, showing increased sensitivity with greater network depth.
  • The LDA Phase Transition: Latent Dirichlet Allocation (LDA) showed a unique "phase transition" behavior. It was almost entirely immune to staleness up to a certain threshold (around $s=10$), after which it suddenly and completely failed to converge.
  • Coherence is the Key: The authors found that gradient coherence typically improves as a model approaches convergence. Their theoretical analysis shows that if you have high gradient coherence, you can afford to use a more "aggressive" (larger) step size even in the face of high staleness.

Key Results

  • Convergence Slowdown: In extreme cases, high staleness required up to 6x more batches to reach the same target accuracy compared to a synchronous baseline. This highlights that the throughput gains of asynchrony can easily be wiped out by the loss in statistical efficiency.
  • Theoretical Matching: The authors proved that asynchronous SGD for non-convex optimization matches the best-known convergence rate of $O(1/\sqrt{T})$, provided the step size is properly adapted to the level of staleness and gradient coherence.
  • Worker Amplification: Increasing the number of workers doesn't just increase throughput; it compounds the staleness effect. The slowdown on 8 workers was often more than double the slowdown on 4 workers for the same staleness level.

Limitations and Future Work

  • Simulation vs. Reality: While the simulation allowed for controlled variables, real-world distributed systems have more complex, non-uniform delay patterns (e.g., bursty network traffic) that weren't fully captured.
  • LDA Failure: While the paper identifies the "phase transition" in LDA, it doesn't provide a full theoretical explanation for why it happens at that specific threshold.
  • Consistency Models: The authors focused on staleness but deferred the study of "read-my-write" consistency (where a worker can at least see its own most recent updates) to future work.

Summary updated

Abstract

Most distributed machine learning (ML) systems store a copy of the model parameters locally on each machine to minimize network communication. In practice, in order to reduce synchronization waiting time, these copies of the model are not necessarily updated in lock-step, and can become stale. Despite much development in large-scale ML, the effect of staleness on the learning efficiency is inconclusive, mainly because it is challenging to control or monitor the staleness in complex distributed environments. In this work, we study the convergence behaviors of a wide array of ML models and algorithms under delayed updates. Our extensive experiments reveal the rich diversity of the effects of staleness on the convergence of ML algorithms and offer insights into seemingly contradictory reports in the literature. The empirical findings also inspire a new convergence analysis of SGD in non-convex optimization under staleness, matching the best-known convergence rate of O(1/\sqrt{T}).
BibTeX
@inproceedings{dai2019toward,
  author = {Wei Dai and Yi Zhou and Nanqing Dong and Hao Zhang and Eric P. Xing},
  title = {{Toward Understanding the Impact of Staleness in Distributed Machine Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=dbSThr0QtEF},
}
Figure