Straggler Mitigation in Distributed Optimization Through Data Encoding

By Can Bülent Karakus, Yifan Sun, Suhas N. Diggavi, Wotao Yin. 2017

155 citations recorded by the source corpus.

Slow running or straggler tasks can significantly reduce computation speed in distributed computation. Recently, coding-theory-inspired approaches have been applied to mitigate the effect of straggling, through embedding redundancy in certain linear computational steps of the optimization algorithm, thus completing the computation without waiting for the stragglers. In this paper, we propose an alternate approach where we embed the redundancy directly in the data itself, and allow the computation to proceed completely oblivious to encoding. We propose several encoding schemes, and demonstrate that popular batch algorithms, such as gradient descent and L-BFGS, applied in a coding-oblivious manner, deterministically achieve sample path linear convergence to an approximate solution of the original problem, using an arbitrarily varying subset of the nodes at each iteration. Moreover, this approximation can be controlled by the amount of redundancy and the number of nodes used in each iteration. We provide experimental results demonstrating the advantage of the approach over uncoded and data replication strategies.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, ML Systems & Hardware

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

In Optimization & Training

In ML Systems & Hardware

Citations in the corpus

Decentralized gradient methods: does topology matter? (2020, neutral): “For example, Karakus et al. (2017) and Luo et al. (2019) observe experimentally that sparse topologies can eﬀectively reduce the convergence wall-clock time.”
Data Encoding for Byzantine-Resilient Distributed Optimization (2019, methodology): “Data encoding proposed in [KSDY17] for straggler mitigation applies to both GD and CD, but only for quadratic problem.”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “Following the conference publication [1], there have been several interesting works in the coded computing community (see [21] for survey) on coded linear algebra [22]–[37], coded convolutions [47], [48], gradient coding [38]–[42], coded Fast Fourier Transforms [55], [56], performance analysis [45],”
Coded computation over heterogeneous clusters (2017, background): “Straggler mitigation through data encoding in distributed optimization is proposed in [28].”
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].”
Byzantine-Tolerant Distributed Coordinate Descent (2019, methodology): “Data encoding was used in [15] both for distributed GD and CD, but for straggler mitigation; the encoding in [15] has low-redundancy and is efficient.”
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].”
Coded Computation Over Heterogeneous Clusters (2019, background): “Straggler mitigation through data encoding in distributed optimization is proposed in [28].”
Near-Optimal Straggler Mitigation for Distributed Gradient Methods (2017, background): “On the other hand, in [16]–[19], error-correcting codes were applied to combat stragglers’ effect and speed up distributed linear algebra operations (e.”
Fault Tolerance in Iterative-Convergent Machine Learning (2018, methodology): “Coded computing has been proposed as a technique to reduce the effects of stragglers and faults in distributed machine learning (Tandon et al., 2017; Karakus et al., 2017; Lee et al., 2018).”
Data Encoding Methods for Byzantine-Resilient Distributed Optimization (2019, methodology): “Data encoding proposed in [13] applies only to stragglers, and has matrices ˜ S i ’s (which in turn will determine the encoding matrix S ), with the help of another matrix F , which will be used to ﬁnd the error locations, i.e., identities of the compromised worker nodes.”
Communication-Computation Efficient Gradient Coding (2018, background): “While most research focused on recovering the exact results in the presence of stragglers, (Karakus et al., 2017; Raviv et al., 2017; Charles et al., 2017) suggested allowing some small deviations from the exact gradient in each iteration of the gradient descent and showed that one can obtain a good”