Random Sampling for Distributed Coded Matrix Multiplication
This work addresses the need for efficient and robust large-scale computations in applications like machine learning, but it appears incremental as it builds on existing coded and randomized methods.
The paper tackles the problem of distributed matrix multiplication by combining coding for straggler tolerance with random sampling for approximation, investigating tradeoffs between recovery threshold and approximation error.
Matrix multiplication is a fundamental building block for large scale computations arising in various applications, including machine learning. There has been significant recent interest in using coding to speed up distributed matrix multiplication, that are robust to stragglers (i.e., machines that may perform slower computations). In many scenarios, instead of exact computation, approximate matrix multiplication, i.e., allowing for a tolerable error is also sufficient. Such approximate schemes make use of randomization techniques to speed up the computation process. In this paper, we initiate the study of approximate coded matrix multiplication, and investigate the joint synergies offered by randomization and coding. Specifically, we propose two coded randomized sampling schemes that use (a) codes to achieve a desired recovery threshold and (b) random sampling to obtain approximation of the matrix multiplication. Tradeoffs between the recovery threshold and approximation error obtained through random sampling are investigated for a class of coded matrix multiplication schemes.