Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication

By Qian Yu, Mohammad Ali Maddah-Ali, Amir Salman Avestimehr. 2017

511 citations recorded by the source corpus.

We consider a large-scale matrix multiplication problem where the computation is carried out using a distributed system with a master node and multiple worker nodes, where each worker can store parts of the input matrices. We propose a computation strategy that leverages ideas from coding theory to design intermediate computations at the worker nodes, in order to efficiently deal with straggling workers. The proposed strategy, named as \emph{polynomial codes}, achieves the optimum recovery threshold, defined as the minimum number of workers that the master needs to wait for in order to compute the output. Furthermore, by leveraging the algebraic structure of polynomial codes, we can map the reconstruction problem of the final output to a polynomial interpolation problem, which can be solved efficiently. Polynomial codes provide order-wise improvement over the state of the art in terms of recovery threshold, and are also optimal in terms of several other metrics. Furthermore, we extend this code to distributed convolution and show its order-wise optimality.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications, ML Systems & Hardware, Algorithms & Complexity

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 Theory and Mathematics

In Computer Networks and Communications

In ML Systems & Hardware

In Algorithms & Complexity

Citations in the corpus

FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization (2019, methodology): “Many methods have been proposed to address systems heterogeneity and in particular stragglers in distributed learning using coding theory, e.g., [Dutta et al., 2016, Lee et al., 2018, Reisizadeh et al., 2019b, Tandon et al., 2016, Yu et al., 2017].”
Robust and Communication-Efficient Collaborative Learning (2019, background): “Another line of work proposed using coding theoretic ideas for speeding up distributed machine learning (Lee et al., 2018c; Tandon et al., 2016; Yu et al., 2017; Reisizadeh et al., 2019b,c), but they work mostly for master-worker setup and particular computation types such as linear computations or…”
On the Capacity of Secure Distributed Matrix Multiplication (2018, methodology): “This methodology is similar to the one proposed in [9], [10] for distributed matrix multiplication problem.”
“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products (2017, background): “Our recent work [30] (that builds on [27]–[29]) as well as concurrent work of Yu et al.”
Improving Distributed Gradient Descent Using Reed-Solomon Codes (2017, methodology): “[10], use a carefully-designed RS code for matrix multiplication.”
Distributed and Private Coded Matrix Computation with Flexible Communication Load (2019, background): “The recovery threshold of this scheme is improved by [8] which introduces so called polynomial codes.”
Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal Coding (2018, methodology): “Entangled polynomial code generalizes the previously proposed polynomial code for distributed matrix multiplication [9], which was designed for the special case of p = 1 (i.”
GASP Codes for Secure Distributed Matrix Multiplication (2018, background): “This follows the general mantra of evaluation codes and, in particular, polynomial codes as originally introduced in [8] and [9].”
Private Secure Coded Computation (2019, methodology): “We denote the minimum number of sub-computation results to recover f(A,BD) by K which was referred to as recovery threshold in [9].”
Coded computation over heterogeneous clusters (2017, background): “Coding schemes for high-dimensional matrix-matrix multiplication have been developed in [17]– [21].”
Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes (2018, background): “[35] introduced a coding scheme called polynomial codes to mitigate straggler in distributed matrix multiplication.”
Secure Distributed Computing With Straggling Servers Using Polynomial Codes (2019, methodology): “Proof of Theorem 5: For a distributed convolution task where each worker can store 1 m fraction of a and 1 n fraction of b without security constraints, lower bound on optimal recovery threshold is max{m, n} [8].”
Cross-Iteration Coded Computing (2018, background): “Some contemporary works on polynomial-encoded matrix operations include [31], [42], and also, notably [43], which focuses on matrix operations with reduced communication costs.”