CodedReduce: A Fast and Robust Framework for Gradient Aggregation in Distributed Learning
By Amirhossein Reisizadeh, Saurav Prakash, Ramtin Pedarsani, Amir Salman Avestimehr. 2019
30 citations recorded by the source corpus.
We focus on the commonly used synchronous Gradient Descent paradigm for large-scale distributed learning, for which there has been a growing interest to develop efficient and robust gradient aggregation strategies that overcome two key system bottlenecks: communication bandwidth and stragglers’ delays. In particular, Ring-AllReduce (<italic>RAR</italic>) design has been proposed to avoid bandwidth bottleneck at any particular node by allowing each worker to only communicate with its neighbors that are arranged in a logical ring. On the other hand, Gradient Coding (<italic>GC</italic>) has been recently proposed to mitigate stragglers in a master-worker topology by allowing carefully designed redundant allocation of the data set to the workers. We propose a joint communication topology design and data set allocation strategy, named CodedReduce (<italic>CR</italic>), that combines the best of both <italic>RAR</italic> and <italic>GC</italic>. That is, it parallelizes the communications over a tree topology leading to efficient bandwidth utilization, and carefully designs a redundant data set allocation and coding strategy at the nodes to make the proposed gradient aggregation scheme robust to stragglers. In particular, we quantify the communication parallelization gain and resiliency of the proposed <italic>CR</italic> scheme, and prove its optimality when the communication topology is a regular tree. Moreover, we characterize the expected run-time of <italic>CR</italic> and show order-wise speedups compared to the benchmark schemes. Finally, we empirically evaluate the performance of our proposed <italic>CR</italic> design over Amazon EC2 and demonstrate that it achieves speedups of up to <inline-formula> <tex-math notation="LaTeX">$27.2\times $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$7.0\times $ </tex-math></inline-formula>, respectively over the benchmarks <italic>GC</italic> and <italic>RAR</italic>.
Subfields: Artificial Intelligence, Computer Science Applications
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
- Aryan Mokhtari
- Hamed Hassani
- Amirhossein Reisizadeh
- Ramtin Pedarsani
- Yuanming Shi
- Khaled Ben Letaief
- Ali Jadbabaie
- Tao Jiang
In Computer Science Applications
Citations in the corpus
- FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, methodology): “…and compression in distributed learning has recently gained considerable attention for both master-worker [Alistarh et al., 2017, Bernstein et al., 2018, Seide et al., 2014, Smith et al., 2016] and masterless topologies [Koloskova et al., 2019, Reisizadeh et al., 2019a, Zhang et al., 2018].”
- Communication-Efficient Edge AI: Algorithms and Systems (2020, methodology): “However, the algorithm deployed on the ring topology are inherently sensitive to stragglers [112].”