Stochastic Gradient Push for Distributed Deep Learning

Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, Michael G. Rabbat

Abstract

Distributed data-parallel algorithms aim to accelerate the training of deep neural networks by parallelizing the computation of large mini-batch gradient updates across multiple nodes. Approaches that synchronize nodes using exact distributed averaging (e.g., via AllReduce) are sensitive to stragglers and communication delays. The PushSum gossip algorithm is robust to these issues, but only performs approximate distributed averaging. This paper studies Stochastic Gradient Push (SGP), which combines PushSum with stochastic gradient updates. We prove that SGP converges to a stationary point of smooth, non-convex objectives at the same sub-linear rate as SGD, and that all nodes achieve consensus. We empirically validate the performance of SGP on image classification (ResNet-50, ImageNet) and machine translation (Transformer, WMT'16 En-De) workloads.

Introduction

Training state-of-the-art deep learning models requires distributing workloads across massive GPU clusters. The standard paradigm, Parallel SGD, typically relies on the ALLREDUCE communication primitive to ensure all nodes maintain an identical model state by performing exact gradient averaging. However, ALLREDUCE suffers from two primary bottlenecks: it is strictly synchronous, making it highly sensitive to "straggler" nodes, and it requires high-bandwidth interconnects (like InfiniBand) to remain efficient. In commodity data center environments using standard Ethernet, communication overhead often dominates computation time, severely limiting scalability.

Methods

We propose Stochastic Gradient Push (SGP) and its high-performance variant, Overlap SGP (OSGP), to address these limitations through decentralized, approximate communication.

The Gossip Mechanism (Push-Sum)

Instead of global synchronization, SGP utilizes the Push-Sum algorithm. Each node "pushes" its model parameters to a subset of neighbors. To compensate for potential imbalances in the number of updates received by different nodes, SGP tracks a scalar weight alongside the model to de-bias the approximate averages, ensuring the system eventually reaches a consensus.

Directed Exponential Graphs

To ensure rapid information dissemination, SGP employs a directed exponential graph topology. Nodes communicate with peers at distances of $2^0, 2^1, 2^2, \dots$ hops. This structure allows information from any single node to reach the entire network in $O(\log n)$ steps while maintaining a constant communication degree per node.

Overlap SGP (OSGP)

To further improve efficiency, OSGP allows nodes to overlap computation with communication. By starting the next gradient calculation while the previous model update is still being transmitted, OSGP effectively hides communication latency, which is critical in bandwidth-constrained environments.

Empirical Results

We evaluated SGP on ImageNet (ResNet-50) and WMT’16 English-German (Transformer) benchmarks. Our results demonstrate that exact averaging is not a prerequisite for convergence; the optimization process is robust to the noise introduced by gossip-based approximate averaging.

Training error vs. wall-clock time for ResNet-50 on ImageNet. SGP (blue) converges significantly faster than AR-SGD (red) and D-PSGD (green) in time-constrained settings.

Scalability and Throughput

SGP demonstrates superior scaling on standard 10 Gbps Ethernet. While ALLREDUCE performance degrades significantly as the cluster size increases due to synchronization overhead, SGP maintains near-linear throughput scaling. On a 32-node (256 GPU) cluster, SGP achieved a 3x speedup over standard ALLREDUCE SGD, reaching 76.2% accuracy on ImageNet in 1.7 hours compared to 5.1 hours for the baseline.

Throughput scaling of SGP compared to AR-SGD and D-PSGD. SGP maintains high throughput even on slower Ethernet networks as the number of nodes increases.

Consensus and Accuracy

Theoretical analysis and empirical measurements confirm that nodes achieve consensus rapidly. Although models may diverge slightly during the initial phases of training, the gossip mechanism effectively synchronizes the cluster, resulting in final models that match the accuracy of those trained with exact averaging.

Conclusion

Stochastic Gradient Push offers a robust alternative to synchronous distributed training, particularly in environments where network bandwidth is a bottleneck. By trading exactness for communication speed and asynchronous operation, SGP enables faster training of large-scale models without sacrificing final accuracy. Future work includes combining SGP with gradient compression techniques and exploring its performance in even more heterogeneous network environments.

Summary updated

Abstract

Distributed data-parallel algorithms aim to accelerate the training of deep neural networks by parallelizing the computation of large mini-batch gradient updates across multiple nodes. Approaches that synchronize nodes using exact distributed averaging (e.g., via AllReduce) are sensitive to stragglers and communication delays. The PushSum gossip algorithm is robust to these issues, but only performs approximate distributed averaging. This paper studies Stochastic Gradient Push (SGP), which combines PushSum with stochastic gradient updates. We prove that SGP converges to a stationary point of smooth, non-convex objectives at the same sub-linear rate as SGD, and that all nodes achieve consensus. We empirically validate the performance of SGP on image classification (ResNet-50, ImageNet) and machine translation (Transformer, WMT'16 En-De) workloads. Our code will be made publicly available.
BibTeX
@inproceedings{assran2019stochastic,
  author = {Mahmoud Assran and Nicolas Loizou and Nicolas Ballas and Michael G. Rabbat},
  title = {{Stochastic Gradient Push for Distributed Deep Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=BkWhAcbdZr},
}
Figure