Stochastic Gradient Push for Distributed Deep Learning

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

410 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Electrical and Electronic Engineering, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Electrical and Electronic Engineering

In Optimization & Training

Citations in the corpus

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, background): “…might be restrictive or never be satisﬁed 5 and proposed alternative conditions [Nguyen et al., 2018, Vaswani et al., 2018, Gower et al., 2019, 2021, Khaled et al., 2020, Khaled and Richtárik, 2020, Assran et al., 2019, Koloskova et al., 2020, Patel and Zhang, 2021, Loizou et al., 2020, 2021].”
Stochastic Hamiltonian Gradient Methods for Smooth Games (2020, background): “We speculate that similar ideas to the ones presented in this work can be used for the development of efﬁcient decentralized methods (Assran et al., 2019; Koloskova et al., 2020) for solving problem (3).”
Advances and Open Problems in Federated Learning (2019, background): “They consider undirected network graphs, although the case of directed networks (encoding unidirectional channels which may arise in real-world scenarios such as social networks or data markets) has also been studied in [30, 200].”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “…to note that we do not assume a uniform bound on the variance (as many prior work, such as Li et al., 2019; Tang et al., 2018b; Lian et al., 2017; Assran et al., 2019) but instead allow the bound on the noise and the diversity to grow with the gradient norm (similar assumptions are common in the…”
Decentralized gradient methods: does topology matter? (2020, neutral): “4 Assran et al. (2019) provide similar results in terms of the graph diameter and maximum degree.”
Central Server Free Federated Learning over Single-sided Trust Social Networks (2019, background): “The proofs of following two lemmas can be found in existing literature (Nedi´c and Olshevsky, 2014, 2016; Assran and Rabbat, 2018; Assran et al., 2018).”
SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum (2019, methodology): “Decentralized training (Jiang et al., 2017; Lian et al., 2017; 2018; Assran et al., 2019) reduces idling due to blocking and stragglers by employing approximate gradient aggregation (e.g., via gossip or distributed averaging).”
Decentralized Deep Learning with Arbitrary Communication Compression (2019, methodology): “…successfully demonstrated that decentralized methods are a competitive alternative to centralized training schemes for deep learning (Lian et al., 2017; Assran et al., 2019) we here signiﬁcantly expand the possible applications by enabling training in strongly communication-restricted environments.”
MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling (2019, background): “subsequently applied it to distributed deep learning in both synchronous [9], [10], [11] and asynchronous settings [12], [13].”
On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization (2019, background): “For example, (Lian et al., 2017; Jiang et al., 2017; Assran et al., 2018) consider decentralized parallel SGD where global gradient aggregations 1If an algorithm has O(1/ √ T ) convergence, then it takes 1/ 2 iterations to attain an O( ) accurate solution.”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, background): “Lianet al. (2017); Tang et al. (2018b,a); Assran et al. (2018) consider the non-convex setting with Tang et al. (2018a) also applying gradient quantization techniques to reduce the communication cost.”
Decentralized Online Learning: Take Benefits from Others’ Data without Sharing Your Own to Track Global Trend (2019, methodology): “Given an adjacent matrix of a decentralized network, there are many methods including Push-Sum [Assran et al., 2018] and Sinkhorn matrix scaling [Knight, 2008] to obtain a W .”
SGD: General Analysis and Improved Rates (2019, neutral): “Similar conditions have been also proved and used in the analysis of decentralized variants of SGD (Lian et al., 2017; Assran et al., 2018).”
Asynchronous Decentralized Online Learning (2021, background): “The usual way [20, 2] to bypass such harsh requirements is to design a communication scheme whose P ( l ) only satisfies the column stochasticity, i.e., P ( l ) ⊤ 1 = 1 .”
From distributed machine learning to federated learning: a survey (2021, background): “, an exponential graph [7], can improve the convergence rate, which accelerates the training speed.”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, methodology): “, it may cause network congestion), motivating the use of degree-bounded topologies where every client sends and receives a small number of messages at each round [5, 61].”
Who started this rumor? Quantifying the natural differential privacy guarantees of gossip protocols (2019, background): “istributed and can be deployed over a peer-to-peer (P2P) network to make them highly scalable with the number of peers in the system, see for instance the recent trend in AI and machine learning [1]– [3]. More generally, P2P networks enable participants to share information without the need for any ”
PopSGD: Decentralized Stochastic Gradient Descent in the Population Model (2019, positive): “References [32, 33, 13] consider SGD-type algorithms in the non-convex setting, while references [48, 31] analyze the use of quantization in the gossip setting.”
A Non-Asymptotic Analysis of Network Independence for Distributed Stochastic Gradient Descent (2019, background): “Several works [10, 25, 11, 12, 22, 35, 26, 36, 2, 38, 34] have shown that distributed methods may compare with their centralized counterparts under certain conditions.”
Revisiting Randomized Gossip Algorithms: General Framework, Convergence Rates and Novel Block and Accelerated Protocols (2019, result): “• Node j: x i = ω( xi+x k j 2 ) + (1− ω)x k−1 j , • Any other node `: x ` = x k ` , where ω ∈ [1, 2).”