ICML 2018oral153 citations
Coded Sparse Matrix Multiplication
Sinong Wang, Jiashang Liu, Ness Shroff
Abstract
In a large-scale and distributed matrix multiplication problem $C=A^{\intercal}B$, where $C\in\mathbb{R}^{r\times t}$, the coded computation plays an important role to effectively deal with “stragglers” (distributed computations that may get delayed due to few slow or faulty processors). However, existing coded schemes could destroy the significant sparsity that exists in large-scale machine learning problems, and could result in much higher computation overhead, i.e., $O(rt)$ decoding time. In this paper, we develop a new coded computation strategy, we call
BibTeX
@InProceedings{pmlr-v80-wang18e,
title = {Coded Sparse Matrix Multiplication},
author = {Wang, Sinong and Liu, Jiashang and Shroff, Ness},
booktitle = {Proceedings of the 35th International Conference on Machine Learning},
pages = {5152--5160},
year = {2018},
editor = {Dy, Jennifer and Krause, Andreas},
volume = {80},
series = {Proceedings of Machine Learning Research},
month = {10--15 Jul},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v80/wang18e/wang18e.pdf},
url = {https://proceedings.mlr.press/v80/wang18e.html},
abstract = {In a large-scale and distributed matrix multiplication problem $C=A^{\intercal}B$, where $C\in\mathbb{R}^{r\times t}$, the coded computation plays an important role to effectively deal with “stragglers” (distributed computations that may get delayed due to few slow or faulty processors). However, existing coded schemes could destroy the significant sparsity that exists in large-scale machine learning problems, and could result in much higher computation overhead, i.e., $O(rt)$ decoding time. In this paper, we develop a new coded computation strategy, we call