Taming Momentum in a Distributed Asynchronous Environment

Ido Hakimi, Saar Barkai, Moshe Gabel, Assaf SchusterarXiv 2019 · OpenReview

Abstract

Although distributed computing can significantly reduce the training time of deep neural networks, scaling the training process while maintaining high efficiency and final accuracy is challenging. Distributed asynchronous training enjoys near-linear speedup, but asynchrony causes gradient staleness - the main difficulty in scaling stochastic gradient descent to large clusters. Momentum, which is often used to accelerate convergence and escape local minima, exacerbates the gradient staleness, thereby hindering convergence. We propose DANA: a novel technique for asynchronous distributed SGD with momentum that mitigates gradient staleness by computing the gradient on an estimated future position of the model's parameters. Thereby, we show for the first time that momentum can be fully incorporated in asynchronous training with almost no ramifications to final accuracy. Our evaluation on the CIFAR and ImageNet datasets shows that DANA outperforms existing methods, in both final accuracy and convergence speed while scaling up to a total batch size of 16K on 64 asynchronous workers.

Introduction

Training massive deep neural networks requires distributing workloads across large clusters of GPUs or CPUs. Traditionally, this is done via Synchronous SGD (SSGD), where all workers must synchronize their updates. While simple, SSGD suffers from the "straggler problem," where the entire cluster waits for the slowest node. Asynchronous SGD (ASGD) offers a faster alternative by allowing workers to operate independently. However, ASGD introduces gradient staleness: by the time a worker pushes a gradient, the master model has already been updated by other workers, rendering the original gradient outdated.

The Challenge of Momentum and Gradient Staleness

The primary obstacle in scaling ASGD is the interaction between gradient staleness and momentum. While momentum is essential for modern deep learning performance, it significantly worsens staleness. Momentum pushes the master model's parameters further away from the state a worker initially pulled, creating a widening "gap" in parameter space.

Visualizing gradient staleness: a worker pulls parameters at time $t$, but by the time it pushes its gradient, the master has already progressed to $t+\tau$.

This paper argues that the "gap"—the Euclidean distance between the worker's parameters and the master's—is the critical metric for staleness. Because momentum vectors are typically much larger than individual gradients, the master model "runs away" from workers much faster in momentum-heavy settings, often leading to divergence on large clusters.

DANA: Distributed Adaptive NAG ASGD

To address this, we propose DANA, which adapts Nesterov’s Accelerated Gradient (NAG) to the distributed setting. DANA utilizes a "look-ahead" mechanism to predict future model states:

  • DANA-Zero: The master node maintains separate momentum vectors for every worker and sends an estimated future position ($\hat{\theta}$) of the parameters, accounting for expected updates during computation.
  • DANA-Slim: An optimized version that offloads future-prediction calculations to the worker side, eliminating master-side overhead while maintaining performance.
  • DANA-DC: Integrates DANA with Taylor expansion-based "Delay Compensation" to further refine gradient accuracy.

NAG's inherent ability to "peek" into the future serves as a natural counter-measure to the "look-back" nature of staleness in asynchronous environments.

Experimental Results

We evaluated DANA on CIFAR-10/100 and ImageNet (ResNet-50), scaling up to a total batch size of 16K across 64 asynchronous workers.

Comparison of the parameter "gap" across different worker counts and algorithms. DANA variants consistently maintain a lower gap compared to standard ASGD and other momentum-based methods.

Our results demonstrate that DANA-Slim and DANA-DC maintain high accuracy even at large scales where competing methods like YellowFin or standard NAG-ASGD fail to converge. In real-world GPU cluster tests, DANA-Slim achieved a 25% speedup over optimized SSGD implementations without sacrificing final accuracy. Furthermore, DANA proved robust in heterogeneous environments where worker speeds vary significantly.

Conclusion and Future Work

DANA demonstrates that momentum can be successfully integrated into asynchronous distributed training. While DANA-Slim mitigates master-side computation, communication bottlenecks remain a challenge for clusters with hundreds of nodes; future work may involve sharding parameter servers. Additionally, we aim to extend the DANA look-ahead logic to other optimizers like Nadam or integrate it with communication-efficient frameworks like EASGD.

Summary updated

Abstract

Although distributed computing can significantly reduce the training time of deep neural networks, scaling the training process while maintaining high efficiency and final accuracy is challenging. Distributed asynchronous training enjoys near-linear speedup, but asynchrony causes gradient staleness - the main difficulty in scaling stochastic gradient descent to large clusters. Momentum, which is often used to accelerate convergence and escape local minima, exacerbates the gradient staleness, thereby hindering convergence. We propose DANA: a novel technique for asynchronous distributed SGD with momentum that mitigates gradient staleness by computing the gradient on an estimated future position of the model's parameters. Thereby, we show for the first time that momentum can be fully incorporated in asynchronous training with almost no ramifications to final accuracy. Our evaluation on the CIFAR and ImageNet datasets shows that DANA outperforms existing methods, in both final accuracy and convergence speed while scaling up to a total batch size of 16K on 64 asynchronous workers.
BibTeX
@misc{hakimi2019taming,
  author = {Ido Hakimi and Saar Barkai and Moshe Gabel and Assaf Schuster},
  title = {{Taming Momentum in a Distributed Asynchronous Environment}},
  year = {2019},
  eprint = {1907.11612},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.11612},
}
Figure