2018

ATOMO: Communication-efficient Learning via Atomic Sparsification

Wang, Hongyi, Sievert, Scott, Charles, Zachary et al.

Understand

Distributed model training suffers from communication overheads due to frequent gradient updates transmitted between compute nodes.

To mitigate these overheads, several studies propose the use of sparsified stochastic gradients.
We argue that these are facets of a general sparsification method that can operate on any possible atomic decomposition.
Notable examples include element-wise, singular value, and Fourier decompositions.

Built on

On the design of gradient algorithms for digitally implemented adaptive filters
R Gitlin, J Mazo, and M Taylor · 1973
Earlier work this paper cites.
Transient weight misadjustment properties for the finite precision LMS algorithm
S Alexander · 1987
Earlier work this paper cites.
A nonlinear analytical model for the quantized LMS algorithm-the arbitrary step size case
José Carlos M Bermudez and Neil J Bershad · 1996
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Alex Krizhevsky and Geoffrey Hinton · 2009
Earlier work this paper cites.
Better mini-batch algorithms via accelerated gradient methods
Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan · 2011
Earlier work this paper cites.
Parallel distributed computing using python
Lisandro D Dalcin, Rodrigo R Paz, Pablo A Kler, and Alejandro Cosimo · 2011
Earlier work this paper cites.
Reading digits in natural images with unsupervised feature learning
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng · 2011
Earlier work this paper cites.
Hogwild: A lock-free approach to parallelizing stochastic gradient descent
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu · 2011
Earlier work this paper cites.
The convex geometry of linear inverse problems
Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky · 2012
Earlier work this paper cites.
Large scale distributed deep networks
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Andrew Senior, Paul Tucker, Ke Yang, Quoc V Le, et al · 2012
Earlier work this paper cites.
Stochastic first-and zeroth-order methods for nonconvex stochastic programming
Saeed Ghadimi and Guanghui Lan · 2013
Earlier work this paper cites.
Low-rank matrix factorization for deep neural network training with high-dimensional output targets
Tara N Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ramabhadran · 2013
Earlier work this paper cites.
Restructuring of deep neural network acoustic models with singular value decomposition
Jian Xue, Jinyu Li, and Yifan Gong · 2013
Earlier work this paper cites.
Speeding up convolutional neural networks with low rank expansions
Original
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman · 2014
Earlier work this paper cites.
Communication-efficient distributed dual coordinate ascent
Martin Jaggi, Virginia Smith, Martin Takác, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, and Michael I Jordan · 2014
Earlier work this paper cites.
Caffe: Convolutional architecture for fast feature embedding
Original
Yangqing Jia, Evan Shelhamer, Jeff Donahue, Sergey Karayev, Jonathan Long, Ross Girshick, Sergio Guadarrama, and Trevor Darrell · 2014
Earlier work this paper cites.
1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu · 2014
Earlier work this paper cites.
Very deep convolutional networks for large-scale image recognition
Original
Karen Simonyan and Andrew Zisserman · 2014
Earlier work this paper cites.
Mean-normalized stochastic gradient for large-scale deep learning
Simon Wiesler, Alexander Richard, Ralf Schluter, and Hermann Ney · 2014
Earlier work this paper cites.

Similar

Convex optimization: Algorithms and complexity
Sébastien Bubeck et al · 2015
Cited alongside, same era.
Mxnet: A flexible and efficient machine learning library for heterogeneous distributed systems
Original
Tianqi Chen, Mu Li, Yutian Li, Min Lin, Naiyan Wang, Minjie Wang, Tianjun Xiao, Bing Xu, Chiyuan Zhang, and Zheng Zhang · 2015
Cited alongside, same era.
Global convergence of stochastic gradient descent for some non-convex matrix problems
Christopher De Sa, Christopher Re, and Kunle Olukotun · 2015
Cited alongside, same era.
Taming the wild: A unified analysis of hogwild-style algorithms
Christopher M De Sa, Ce Zhang, Kunle Olukotun, and Christopher Ré · 2015
Cited alongside, same era.
Asynchronous stochastic convex optimization
Original
John C Duchi, Sorathan Chaturapruek, and Christopher Ré · 2015
Cited alongside, same era.
An asynchronous parallel stochastic coordinate descent algorithm
Ji Liu, Stephen J Wright, Christopher Ré, Victor Bittorf, and Srikrishna Sridhar · 2015
Cited alongside, same era.
Perturbed iterate analysis for asynchronous stochastic optimization
Original
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I Jordan · 2015
Cited alongside, same era.
Scalable distributed DNN training using commodity gpu cloud computing
Nikko Strom · 2015
Cited alongside, same era.
TensorFlow: A system for large-scale machine learning
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al · 2016
Cited alongside, same era.
Revisiting distributed synchronous SGD
Original
Jianmin Chen, Xinghao Pan, Rajat Monga, Samy Bengio, and Rafal Jozefowicz · 2016
Cited alongside, same era.
Big Batch SGD: Automated inference using adaptive batch sizes
Original
Soham De, Abhay Yadav, David Jacobs, and Tom Goldstein · 2016
Cited alongside, same era.
Deep residual learning for image recognition
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun · 2016
Cited alongside, same era.

Then

Distributed mean estimation with limited communication
Original
Ananda Theertha Suresh, Felix X Yu, Sanjiv Kumar, and H Brendan McMahan · 2016
Later among the works it cites.
DoReFa-Net: training low bitwidth convolutional neural networks with low bitwidth gradients
Original
Shuchang Zhou, Yuxin Wu, Zekun Ni, Xinyu Zhou, He Wen, and Yuheng Zou · 2016
Later among the works it cites.
Sparse communication for distributed gradient descent
Original
Alham Fikri Aji and Kenneth Heafield · 2017
Later among the works it cites.
Qsgd: Communication-efficient SGD via gradient quantization and encoding
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic · 2017
Later among the works it cites.
Adacomp: Adaptive residual gradient compression for data-parallel distributed training
Original
Chia-Yu Chen, Jungwook Choi, Daniel Brand, Ankur Agrawal, Wei Zhang, and Kailash Gopalakrishnan · 2017
Later among the works it cites.
Understanding and optimizing asynchronous low-precision stochastic gradient descent
Christopher De Sa, Matthew Feldman, Christopher Ré, and Kunle Olukotun · 2017
Later among the works it cites.
Densely connected convolutional networks
Gao Huang, Zhuang Liu, Kilian Q Weinberger, and Laurens van der Maaten · 2017
Later among the works it cites.
Deep gradient compression: Reducing the communication bandwidth for distributed training
Original
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally · 2017
Later among the works it cites.
Automatic differentiation in PyTorch
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer · 2017
Later among the works it cites.
Paleo: A performance model for deep neural networks
Hang Qi, Evan R. Sparks, and Ameet Talwalkar · 2017
Later among the works it cites.
Gradient sparsification for communication-efficient distributed optimization
Original
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang · 2017
Later among the works it cites.
Terngrad: Ternary gradients to reduce communication in distributed deep learning
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li · 2017
Later among the works it cites.
Zipml: Training linear models with end-to-end low precision, and a little bit of deep learning
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang · 2017
Later among the works it cites.
signSGD: compressed optimisation for non-convex problems
Original
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Anima Anandkumar · 2018
Closest in time.
High-accuracy low-precision training
Original
Christopher De Sa, Megan Leszczynski, Jian Zhang, Alana Marzoev, Christopher R Aberger, Kunle Olukotun, and Christopher Ré · 2018
Closest in time.
Synchronous multi-GPU deep learning with low-precision communication: An experimental study
Demjan Grubic, Leo Tam, Dan Alistarh, and Ce Zhang · 2018
Closest in time.
SparCML: high-performance sparse communication for machine learning
Original
Cèdric Renggli, Dan Alistarh, and Torsten Hoefler · 2018
Closest in time.
Variance-based gradient compression for efficient distributed deep learning
Original
Yusuke Tsuzuku, Hiroto Imachi, and Takuya Akiba · 2018
Closest in time.
Gradient diversity: a key ingredient for scalable distributed learning
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…