Near-Optimal Straggler Mitigation for Distributed Gradient Methods

By Songze Li, Seyed Mohammadreza Mousavi Kalan, Amir Salman Avestimehr, M. Soltanolkotabi. 2017

103 citations recorded by the source corpus.

Modern learning algorithms use gradient descent updates to train inferential models that best explain data. Scaling these approaches to massive data sizes requires proper distributed gradient descent schemes where distributed worker nodes compute partial gradients based on their partial and local data sets, and send the results to a master node where all the computations are aggregated into a full gradient and the learning model is updated. However, a major performance bottleneck that arises is that some of the worker nodes may run slow. These nodes a.k.a. stragglers can significantly slow down computation as the slowest node may dictate the overall computational time. We propose a distributed computing scheme, called Batched Coupon's Collector (BCC) to alleviate the effect of stragglers in gradient methods. We prove that our BCC scheme is robust to a near optimal number of random stragglers. We also empirically demonstrate that our proposed BCC scheme reduces the run-time by up to 85.4% over Amazon EC2 clusters when compared with other straggler mitigation strategies. We also generalize the proposed BCC scheme to minimize the completion time when implementing gradient descent-based algorithms over heterogeneous worker nodes.

Subfields: Artificial Intelligence, Computational Mechanics

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 Computational Mechanics

Citations in the corpus

Decentralized gradient methods: does topology matter? (2020, neutral): “Stragglers can significantly reduce computation speed in a multi-machine setting (Ananthanarayanan et al., 2013; Karakus et al., 2017; Li et al., 2018).”
The Role of Network Topology for Distributed Machine Learning (2019, methodology): “Recently some straggling mitigation techniques for distributed gradient methods have been proposed [13], [12].”
Federated Learning via Over-the-Air Computation (2018, background): “, devices that run slow) may cause significant delays [8], [17].”
Rateless codes for near-perfect load balancing in distributed matrix-vector multiplication (2018, background): “There are also works dealing with coded gradient descent [24, 43, 56], coded convolution [15], coded Fourier Transform [64], Page Rank [62], and coded distributed optimization [36] – in general any distributed linear computation can essentially be expressed as a matrix multiplication/addition operat”
Throughput-Optimal Topology Design for Cross-Silo Federated Learning (2020, background): “Reference [78] studies how to select the degree of a regular topology when the duration of a communication round is determined by stragglers [44, 55].”
Polynomially Coded Regression: Optimal Straggler Mitigation via Data Encoding (2018, methodology): “In particular, we empirically compare the performance of our proposed PCR scheme with the GC scheme in [16] (specifically, the cyclic repetition scheme), the naive uncoded scheme for which there is no data redundancy among the workers, and the batched coupon’s collector (BCC) scheme in [19] that ran”
Communication-Efficient Edge AI: Algorithms and Systems (2020, background): “Communication-Efficient Edge AI Systems Data Partition Based Edge Training Systems • Fast aggregation via over-the-air computation [21], [84], [85], [86] • Aggregation frequency control with limited bandwidth and computation resources [87], [88], [89] • Data reshuffling via index coding and pliable ”