# ϵ-Approximate Coded Matrix Multiplication Is Nearly Twice as Efficient as Exact Multiplication

@article{Jeong2021ApproximateCM, title={ϵ-Approximate Coded Matrix Multiplication Is Nearly Twice as Efficient as Exact Multiplication}, author={Haewon Jeong and Ateet Devulapalli and Viveck R. Cadambe and Fl{\'a}vio du Pin Calmon}, journal={IEEE Journal on Selected Areas in Information Theory}, year={2021}, volume={2}, pages={845-854} }

We study coded distributed matrix multiplication from an approximate recovery viewpoint. We consider a system of <inline-formula> <tex-math notation="LaTeX">$P$ </tex-math></inline-formula> computation nodes where each node stores <inline-formula> <tex-math notation="LaTeX">$1/m$ </tex-math></inline-formula> of each multiplicand via linear encoding. Our main result shows that the matrix product can be recovered with <inline-formula> <tex-math notation="LaTeX">$\epsilon $ </tex-math></inline… Expand

#### One Citation

Price of Precision in Coded Distributed Matrix Multiplication: A Dimensional Analysis

- Computer Science, Mathematics
- 2021 IEEE Information Theory Workshop (ITW)
- 2021

A rudimentary asymptotic dimensional analysis of AMD codes inspired by the Generalized Degrees of Freedom (GDoF) framework previously developed for wireless networks indicates that for the same upload/storage, once the precision levels of the task assignments are accounted for, AMD codes are not better than a replication scheme which assigns the full computation task to every server. Expand

#### References

SHOWING 1-10 OF 46 REFERENCES

“Short-Dot”: Computing Large Linear Transforms Distributedly Using Coded Short Dot Products

- Computer Science, Mathematics
- IEEE Transactions on Information Theory
- 2019

The key novelty in this work is that in the particular regime where the number of available processing nodes is greater than the total number of dot products, Short-Dot has lower expected computation time under straggling under an exponential model compared to existing strategies. Expand

Coded Sparse Matrix Multiplication

- Computer Science
- ICML
- 2018

A new coded computation strategy, calledparse code, is developed, which achieves near the optimal recovery threshold, low computation overhead, and linear decoding time, and is implemented and demonstrated over both uncoded and current fastest coded strategies. Expand

Speeding Up Distributed Machine Learning Using Codes

- Computer Science, Mathematics
- IEEE Transactions on Information Theory
- 2018

This paper focuses on two of the most basic building blocks of distributed learning algorithms: matrix multiplication and data shuffling, and uses codes to reduce communication bottlenecks, exploiting the excess in storage. Expand

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

- Mathematics, Computer Science
- NIPS
- 2017

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… Expand

CodedSketch: Coded Distributed Computation of Approximated Matrix Multiplication

- Computer Science
- 2019 IEEE International Symposium on Information Theory (ISIT)
- 2019

This paper proposes CodedSketch, as a distributed straggler-resistant scheme to compute an approximation of the multiplication of two massive matrices, using count–sketch as a hash-based compression scheme, and a structured polynomial code on the columns of the first and rows of the second matrix. Expand

Hierarchical Coded Computation

- Computer Science, Mathematics
- 2018 IEEE International Symposium on Information Theory (ISIT)
- 2018

This work partitions each node's computation into layers of sub-computations such that each layer can be treated as (distinct) erasure channel and designs different erasure codes for each layer so that all layers have the same failure exponent. Expand

Fundamental Limits of Approximate Gradient Coding

- Computer Science
- Proc. ACM Meas. Anal. Comput. Syst.
- 2019

Two approximate gradient coding schemes that exactly match such lower bounds based on random edge removal process are proposed, which provide order-wise improvement over the state of the art in terms of computation load, and are also optimal in both computation load and latency. Expand

On the optimal recovery threshold of coded matrix multiplication

- Computer Science, Mathematics
- 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
- 2017

We provide novel coded computation strategies for distributed matrix-matrix products that outperform the recent “Polynomial code” constructions in recovery threshold, i.e., the required number of… Expand

Coded fourier transform

- Computer Science, Mathematics
- 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
- 2017

This is the first code that achieves the optimum robustness in terms of tolerating stragglers or failures for computing Fourier transforms, and the reconstruction process for coded FFT can be mapped to MDS decoding, which can be solved efficiently. Expand

Stochastic Gradient Coding for Straggler Mitigation in Distributed Learning

- Computer Science, Mathematics
- IEEE Journal on Selected Areas in Information Theory
- 2020

This work proposes an approximate gradient coding scheme called SGC, which works when the stragglers are random, and proves that the convergence rate of SGC mirrors that of batched Stochastic Gradient Descent (SGD) for the <inline-formula> <tex-math notation="LaTeX">$\ell _{2}$ </tex- Math> loss function, and shows how the convergence rates can improve with the redundancy. Expand