Source-linked AI summary
Sparse Communication for Distributed Gradient Descent
Alham Fikri Aji, Kenneth Heafield
TL;DR
Distributed gradient descent is slowed by costly communication, and prior compression approaches were less established for neural machine translation. The paper sparsifies gradient updates by dropping small values, optionally adds quantization, and evaluates configurations on NMT and MNIST, achieving speedups while preserving final accuracy or BLEU.
Problem
Distributed training exchanges gradients and parameters over costly networks, while prior approximate compression methods were mainly tested on speech recognition and toy MNIST systems.
Method
The paper applies Gradient Dropping by removing small-magnitude updates and exchanges sparse matrices, optionally applying 1-bit quantization afterward.
Results
49% average speed improvement was achieved for MNIST and 22% for NMT, with the reported experiments preserving final accuracy or BLEU.
Takeaways & Limitations
Sparse communication can accelerate distributed training substantially on MNIST and NMT, although configuration choices such as thresholding and normalization matter for translation.
Takeaways & Limitations
NMT is less tolerant of quantization and global thresholding can underperform because its parameters have different scales, making layer normalization or local per-parameter thresholds necessary.
Abstract
from arXiv · showhide
We make distributed stochastic gradient descent faster by exchanging sparse updates instead of dense updates. Gradient updates are positively skewed as most updates are near zero, so we map the 99% smallest updates (by absolute value) to zero then exchange sparse matrices. This method can be combined with quantization to further improve the compression. We explore different configurations and apply them to neural machine translation and MNIST image classification tasks. Most configurations work on MNIST, whereas different configurations reduce convergence rate on the more complex translation task. Our experiments show that we can achieve up to 49% speed up on MNIST and 22% on NMT without damaging the final accuracy or BLEU.
1 Introduction
The paper studies sparse and quantized communication for data-parallel distributed training, focusing on whether approximations developed for speech and MNIST transfer effectively to neural machine translation. It motivates this comparison through differences in parameter access and gradient structure between NMT and MNIST.
- Motivation: Data-parallel training reduces large-model training time by having nodes optimize different data subsets while exchanging gradients and parameters.The paper identifies network communication as a major cost of this setup.
- Motivation: Prior approaches compress network traffic through 1-bit quantization or sparse matrices that drop small updates.These methods were previously developed and tested on speech recognition and toy MNIST systems.
- Motivation: When these approximations are ported to NMT, translation is less tolerant to quantization than the earlier application settings.
- NMT and MNIST: NMT contains three large embedding matrices whose vocabulary-related gradients are expected to be skewed because mini-batches access only a small fraction of words.The matrices are source-input, target-input, and target-output embeddings.
- NMT and MNIST: MNIST exercises every parameter in each mini-batch, unlike NMT, creating a contrasting gradient-access pattern for evaluating communication approximations.The paper uses a toy MNIST system because prior work used a similar setup.
2 Related Work
Related work compresses gradients or changes SGD’s communication schedule to reduce network cost. The paper positions its approach as a continuous form of sending important updates between minibatches.
- Communication and SGD: Asynchronous SGD architectures let workers push and pull models independently, avoiding waits for slower workers.
- Communication and SGD: Lock-free updates allow race conditions, while exchanging updates after multiple minibatches reduces communication frequency.
- Communication and SGD: This work sends the most important updates between minibatches, making it a more continuous communication approach.
- Gradient Compression: 1-Bit SGD and Quantization SGD convert gradient updates into 1-bit matrices to reduce data communication.
- Gradient Compression: Threshold quantization sends updates larger than a predefined threshold, but choosing an effective threshold is difficult because it can change during optimization.Dryden et al. instead set the threshold to retain a constant number of gradients per iteration.
3 Distributed SGD
The distributed SGD system shards parameters across servers while every client retains a full parameter copy. Workers exchange gradient pieces with responsible servers and pull updated parameters from all servers.
- Parameter Sharding: The architecture uses distributed SGD with parameter sharding, with each of N workers acting as both a client and a server.Each server is responsible for 1/Nth of the parameters.
- Client Computation: Clients keep copies of all parameters and use them to compute gradients on their assigned data.
- Communication: Each client splits gradients into N pieces and pushes them to the appropriate servers.
- Communication: Clients pull parameters from all servers, and each node communicates with all N nodes regarding 1/Nth of the parameters.This keeps bandwidth per node constant.
4 Sparse Gradient Exchange
Gradient Dropping sparsifies transmissions by removing the smallest updates by absolute value while preserving their residuals locally. The method supports sparse parameter deltas, approximate threshold selection, and either global or per-matrix thresholds under scale differences.
- Gradient Dropping: Gradient Dropping removes the R% smallest gradients by absolute value and sends the remaining values as a sparse matrix.Unlike prior work that separately drops positive and negative gradients, it uses one absolute-value threshold.
- Residuals: Dropped gradients are retained as local residuals and added to the next gradient before another dropping step.This prevents accumulated small gradients from being permanently zeroed.
- Algorithm: Algorithm 1 selects a threshold, zeroes dropped entries, stores the residual difference, and returns the surviving updates in sparse form.
- Transmission Scope: Gradient Dropping applies to all data transmissions, including parameter pulls represented as deltas from each client’s last pulled version.The server stores the last pulled copy; asynchronous SGD uses one copy per client.
- Threshold Selection: The threshold can be approximated by selecting it from a 0.1% sample of the gradient.Exact selection is described as expensive.
- Threshold Scope: Layer normalization enables one global threshold, whereas without it global thresholding degrades NMT convergence because parameter scales differ.A threshold can alternatively be selected locally for each parameter matrix.
5 Experiment
Experiments evaluate gradient dropping on MNIST and Romanian→English NMT, varying drop ratios, thresholding, normalization, compression, speed, convergence, and final quality. The method achieves substantial speedups while generally preserving MNIST accuracy and NMT BLEU, although some NMT configurations slow convergence.
- Experimental setup: Experiments compare gradient-dropping ratios from 90% to 99.9% using loss, MNIST accuracy, and NMT BLEU.The evaluated tasks are MNIST image classification and Romanian→English neural machine translation.
- Drop ratio: 99% dropping exchanges 50x less data with little impact on NMT convergence or BLEU.Dropping 99.9% still permits learning but produces a worse BLEU score.
- Local vs Global Threshold: Global thresholding underperforms on NMT without layer normalization, whereas layer normalization has no visible impact on MNIST.The NMT system has more parameter categories and varied parameter scales than the three-layer MNIST network.
- Training speed: 49% average speed improvement occurs on MNIST, compared with 22% for NMT using batch size 32.Communication represents 41% of MNIST training time and 17% in the additional NMT batch-size-32 scenario.
- Convergence Rate: MNIST final accuracy increases from 99.28% baseline to 99.42% with a 99% drop rate, while final NMT BLEU scores remain essentially unchanged.NMT convergence is 23% faster than baseline at batch size 32 but nearly the same at batch size 80.
- Quantization: 1-bit quantization slows NMT convergence but does not affect MNIST configurations in the reported experiments.The authors report that 2-bit quantization is sufficient for NMT because its top 1% gradients are more skewed.
6 Conclusion and Future Work
The method exploits skewed gradient updates to reduce communication, can be combined with quantization, and achieves substantial speedups, although configuration choices affect NMT convergence.
- Keeping 99% of gradient updates locally makes communication 50x smaller with coordinate-value encoding.
- 1-bit quantization was intended to further compress communication, but it does not work for NMT.
- 2-bit quantization is likely sufficient for NMT, separating large movers from small changes.
- Most tested configurations work on MNIST, whereas NMT requires attention to skew and parameter-scale differences.
- 22% speedup was achieved on a 4-Titan-X NMT experiment with batch size 32.