2018

Slow and Stale Gradients Can Win the Race: Error-Runtime Trade-offs in Distributed SGD

Dutta, Sanghamitra, Joshi, Gauri, Ghosh, Soumyadip et al.

Understand

Distributed Stochastic Gradient Descent (SGD) when run in a synchronous manner, suffers from delays in waiting for the slowest learners (stragglers).

Asynchronous methods can alleviate stragglers, but cause gradient staleness that can adversely affect convergence.
In this work we present a novel theoretical characterization of the speed-up offered by asynchronous methods by analyzing the trade-off between the error in the trained model and the actual training runtime (wallclock time).
The novelty in our work is that our runtime analysis considers random straggler delays, which helps us design and compare distributed SGD algorithms that strike a balance between stragglers and staleness.

Built on

A stochastic approximation method
Herbert Robbins and Sutton Monro · 1951
Earlier work this paper cites.
Distributed asynchronous deterministic and stochastic gradient optimization algorithms
John Tsitsiklis, Dimitri Bertsekas, and Michael Athans · 1986
Earlier work this paper cites.
A course in microeconomic theory
David M Kreps · 1990
Earlier work this paper cites.
The mnist database of handwritten digits
Yann LeCun · 1998
Earlier work this paper cites.
A first course in probability
Ross Sheldon · 2002
Earlier work this paper cites.
Convex optimization
Stephen Boyd and Lieven Vandenberghe · 2004
Earlier work this paper cites.
Learning multiple layers of features from tiny images
Alex Krizhevsky and Geoffrey Hinton · 2009
Earlier work this paper cites.
Adaptive subgradient methods for online learning and stochastic optimization
John Duchi, Elad Hazan, and Yoram Singer · 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.
Distributed delayed stochastic optimization
Alekh Agarwal and John C Duchi · 2011
Earlier work this paper cites.
Algorithms
Robert Sedgewick and Kevin Wayne · 2011
Earlier work this paper cites.
Large scale distributed deep networks
Jeffrey Dean et al · 2012
Earlier work this paper cites.
Optimal distributed online prediction using mini-batches
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao · 2012
Earlier work this paper cites.
A stochastic gradient method with an exponential convergence rate for finite training sets
Nicolas L Roux, Mark Schmidt, and Francis R Bach · 2012
Earlier work this paper cites.
Imagenet classification with deep convolutional neural networks
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton · 2012
Earlier work this paper cites.
The tail at scale
Jeffrey Dean and Luiz André Barroso · 2013
Earlier work this paper cites.
Accelerating stochastic gradient descent using predictive variance reduction
Rie Johnson and Tong Zhang · 2013
Earlier work this paper cites.
Solving the straggler problem with bounded staleness
James Cipar, Qirong Ho, Jin Kyu Kim, Seunghak Lee, Gregory R. Ganger, Garth Gibson, Kimberly Keeton, and Eric Xing · 2013
Earlier work this paper cites.
More effective distributed ml via a stale synchronous parallel parameter server
Qirong Ho, James Cipar, Henggang Cui, Seunghak Lee, Jin Kyu Kim, Phillip B Gibbons, Garth A Gibson, Greg Ganger, and Eric P Xing · 2013
Earlier work this paper cites.
Stochastic Processes: Theory for Applications
Robert G. Gallager · 2013
Earlier work this paper cites.
Efficient mini-batch training for stochastic optimization
Mu Li, Tong Zhang, Yuqiang Chen, and Alexander J. Smola · 2014
Earlier work this paper cites.
On the delay-storage trade-off in content download from coded distributed storage systems
Gauri Joshi, Yanpei Liu, and Emina Soljanin · 2014
Earlier work this paper cites.

Similar

Exploiting bounded staleness to speed up big data analytics
Henggang Cui, James Cipar, Qirong Ho, Jin Kyu Kim, Seunghak Lee, Abhimanu Kumar, Jinliang Wei, Wei Dai, Gregory R Ganger, Phillip B Gibbons, et al · 2014
Cited alongside, same era.
Adam: A method for stochastic optimization
Diederik P. Kingma and Jimmy Ba · 2015
Cited alongside, same era.
Using straggler replication to reduce latency in large-scale parallel computing
Da Wang, Gauri Joshi, and Gregory Wornell · 2015
Cited alongside, same era.
Queues with redundancy: Latency-cost analysis
Gauri Joshi, Emina Soljanin, and Gregory Wornell · 2015
Cited alongside, same era.
Asynchronous parallel stochastic gradient for nonconvex optimization
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu · 2015
Cited alongside, same era.
Asynchronous stochastic convex optimization: the noise is in the noise and sgd don’t care
Sorathan Chaturapruek, John C Duchi, and Christopher Ré · 2015
Cited alongside, same era.
Deep learning with elastic averaging sgd
Sixin Zhang, Anna E Choromanska, and Yann LeCun · 2015
Cited alongside, same era.
Optimization methods for large-scale machine learning
Original
Léon Bottou, Frank E. Curtis, and Jorge Nocedal · 2016
Cited alongside, same era.
An overview of gradient descent optimization algorithms
Original
Sebastian Ruder · 2016
Cited alongside, same era.
Addressing the straggler problem for iterative convergent parallel ml
Aaron Harlap, Henggang Cui, Wei Dai, Jinliang Wei, Gregory R. Ganger, Phillip B. Gibbons, Garth A. Gibson, and Eric P. Xing · 2016
Cited alongside, same era.
Short-dot: Computing large linear transforms distributedly using coded short dot products
Sanghamitra Dutta, Viveck Cadambe, and Pulkit Grover · 2016
Cited alongside, same era.
Fault-tolerant distributed logistic regression using unreliable components
Yaoqing Yang, Pulkit Grover, and Soummya Kar · 2016
Cited alongside, same era.

Then

Improving distributed gradient descent using reed-solomon codes
Original
Wael Halbawi, Navid Azizan-Ruhi, Fariborz Salehi, and Babak Hassibi · 2017
Later among the works it cites.
Coded distributed computing for inverse problems
Yaoqing Yang, Pulkit Grover, and Soummya Kar · 2017
Later among the works it cites.
Polynomial codes: an optimal design for high-dimensional coded matrix multiplication
Qian Yu, Mohammad Maddah-Ali, and Salman Avestimehr · 2017
Later among the works it cites.
Encoded distributed optimization
Can Karakus, Yifan Sun, and Suhas Diggavi · 2017
Later among the works it cites.
Straggler mitigation in distributed optimization through data encoding
Can Karakus, Yifan Sun, Suhas Diggavi, and Wotao Yin · 2017
Later among the works it cites.
Approximate gradient coding via sparse random graphs
Original
Zachary Charles, Dimitris Papailiopoulos, and Jordan Ellenberg · 2017
Later among the works it cites.
Coded terasort
Songze Li, Sucha Supittayapornpong, Mohammad Ali Maddah-Ali, and Salman Avestimehr · 2017
Later among the works it cites.
On the optimal recovery threshold of coded matrix multiplication
Mohammad Fahim, Haewon Jeong, Farzin Haddadpour, Sanghamitra Dutta, Viveck Cadambe, and Pulkit Grover · 2017
Later among the works it cites.
Codes for Distributed Computing: A Tutorial
Viveck Cadambe and Pulkit Grover · 2017
Later among the works it cites.
Perturbed iterate analysis for asynchronous stochastic optimization
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I Jordan · 2017
Later among the works it cites.
More iterations per second, same quality–why asynchronous algorithms may drastically outperform traditional ones
Original
Robert Hannah and Wotao Yin · 2017
Later among the works it cites.
Asynchronous coordinate descent under more realistic assumptions
Tao Sun, Robert Hannah, and Wotao Yin · 2017
Later among the works it cites.
Asaga: Asynchronous parallel saga
Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien · 2017
Later among the works it cites.
Yellowfin and the art of momentum tuning
Original
Jian Zhang, Ioannis Mitliagkas, and Christopher Ré · 2017
Later among the works it cites.
Gradient diversity empowers distributed learning
Original
Dong Yin, Ashwin Pananjady, Max Lam, Dimitris Papailiopoulos, Kannan Ramchandran, and Peter Bartlett · 2017
Later among the works it cites.
On the convergence properties of a k k -step averaging stochastic gradient descent algorithm for nonconvex optimization
Original
Fan Zhou and Guojing Cong · 2017
Later among the works it cites.
Speeding up distributed machine learning using codes
Kangwook Lee, Maximilian Lam, Ramtin Pedarsani, Dimitris Papailiopoulos, and Kannan Ramchandran · 2018
Closest in time.
Communication-computation efficient gradient coding
Original
Min Ye and Emmanuel Abbe · 2018
Closest in time.
A fundamental tradeoff between computation and communication in distributed computing
Songze Li, Mohammad Ali Maddah-Ali, Qian Yu, and A Salman Avestimehr · 2018
Closest in time.
A Unified Coded Deep Neural Network Training Strategy based on Generalized PolyDot codes
Sanghamitra Dutta, Ziqian Bai, Haewon Jeong, Tze Meng Low, and Pulkit Grover · 2018
Closest in time.
Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication
Original
Ankur Mallick, Malhar Chaudhari, and Gauri Joshi · 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…