Sparse Communication for Distributed Gradient Descent

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 440–445 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Sparse Communication for Distributed Gradient Descent Alham Fikri Aji and Kenneth Heafield School of Informatics, University of Edinburgh 10 Crichton Street Edinburgh EH8 9AB Scotland, European Union a.fikri@ed.ac.uk, kheafiel@inf.ed.ac.uk Abstract We make distributed stochastic gradient descent faster by exchanging sparse up- dates instead of dense updates. Gradi- ent 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 quan- tization to further improve the compres- sion. We explore different configura- tions and apply them to neural machine translation and MNIST image classifica- tion tasks. Most configurations work on MNIST, whereas different configurations reduce convergence rate on the more com- plex 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 Distributed computing is essential to train large neural networks on large data sets (Raina et al., 2009). We focus on data parallelism: nodes jointly optimize the same model on different parts of the training data, exchanging gradients and param- eters over the network. This network commu- nication is costly, so prior work developed two ways to approximately compress network traffic: 1-bit quantization (Seide et al., 2014) and sending sparse matrices by dropping small updates (Strom, 2015; Dryden et al., 2016). These methods were developed and tested on speech recognition and toy MNIST systems. In porting these approxima- tions to neural machine translation (NMT) ( ˜Neco and Forcada, 1996; Bahdanau et al., 2014), we find that translation is less tolerant to quantization. Throughout this paper, we compare neural ma- chine translation behavior with a toy MNIST sys- tem, chosen because prior work used a similar system (Dryden et al., 2016). NMT parameters are dominated by three large embedding matrices: source language input, target language input, and target language output. These matrices deal with vocabulary words, only a small fraction of which are seen in a mini-batch, so we expect skewed gra- dients. In contrast, MNIST systems exercise ev- ery parameter in every mini-batch. Additionally, NMT systems consist of multiple parameters with different scales and sizes, compared to MNIST’s 3-layers network with uniform size. More for- mally, gradient updates have positive skewness co- efficient (Zwillinger and Kokoska, 1999): most are close to zero but a few are large. 2 Related Work An orthogonal line of work optimizes the SGD algorithm and communication pattern. Zinke- vich et al. (2010) proposed an asynchronous ar- chitecture where each node can push and pull the model independently to avoid waiting for the slower node. Chilimbi et al. (2014) and Recht et al. (2011) suggest updating the model without a lock, allowing race conditions. Additionally, Dean et al. (2012) run multiple minibatches be- fore exchanging updates, reducing the communi- cation cost. Our …

Content truncated to 500 words