Random Sampling for Distributed Coded Matrix Multiplication

Wei-Ting Chang, Ravi Tandon

Abstract

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.

Introduction

In the era of large-scale distributed computing, tasks such as training massive AI models are distributed across hundreds of worker nodes. A primary bottleneck in these environments is the "straggler effect," where the overall computation speed is limited by the slowest machine. Coded Distributed Computing (CDC) addresses this by introducing mathematical redundancy, allowing a master node to reconstruct the final result once a specific subset of $K$ workers (the recovery threshold) completes their tasks.

While traditional CDC focuses on exact results, many applications in machine learning can tolerate approximate answers. This paper explores the synergy between coding and randomized sampling to trade accuracy for a significantly lower recovery threshold, thereby enhancing resilience to stragglers.

Methodology

The proposed approach integrates randomized sampling strategies with MatDot codes. Two primary sampling schemes are investigated:

  1. Coded Set-wise Sampling: Submatrix indices are selected without replacement, encoded, and distributed to workers. This ensures that workers always process unique information.
  2. Coded Independent Sampling: Indices are sampled with replacement. While simpler to implement, this may lead to redundant computations as the same submatrix might be processed multiple times.

To minimize approximation error, the authors employ importance sampling. Rather than uniform selection, submatrices are sampled according to an optimal distribution based on their Frobenius norms. This ensures that "heavier" or more significant parts of the matrices are prioritized in the approximation.

Experimental Results

The schemes were validated through synthetic simulations using matrices $A$ ($60 \times 4$) and $B$ ($4 \times 60$), partitioned into $m=4$ submatrices. The primary metric was Normalized Empirical Error across varying recovery thresholds ($K$).

Comparison of Normalized Error vs. Recovery Threshold for Set-wise (left) and Independent (right) sampling.

The results demonstrate a clear tradeoff between the recovery threshold and approximation error. For a system with $m$ partitions, a recovery threshold of $K = 2s - 1$ is achievable for $s$ sampled submatrices.

Numerical comparison of normalized error for different sampling methods and recovery thresholds.

Key findings include:

  • Set-wise Superiority: Set-wise sampling consistently outperforms independent sampling because it avoids redundant submatrix processing. For instance, at $K=3$, optimal set-wise sampling achieved an error of 1.0337, whereas independent sampling resulted in 1.5349.
  • Optimal vs. Uniform Distribution: Using optimal distributions based on matrix norms significantly reduces error compared to uniform sampling across all thresholds, proving that some parts of a matrix are more critical to the final product than others.
  • Exact Recovery: For set-wise sampling, the error drops to zero when the threshold reaches the full computation requirement ($K=7$ in the $m=4$ case).

Discussion and Future Work

This work demonstrates that combining coding with randomized sampling offers a robust framework for approximate distributed computing. However, several avenues for future research remain. The current study is specific to MatDot codes; extending these sampling strategies to Polynomial or Lagrange codes is a logical next step. Additionally, the computational overhead of calculating optimal sampling probabilities for extremely large matrices needs further investigation. Finally, scaling these methods to warehouse-scale data will provide deeper insights into the practical performance of the encoding and decoding processes in real-world distributed systems.

Summary updated

Abstract

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.
BibTeX
@inproceedings{chang2019random,
  author = {Wei-Ting Chang and Ravi Tandon},
  title = {{Random Sampling for Distributed Coded Matrix Multiplication}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2019},
  url = {https://openreview.net/forum?id=tPngl3f1zT},
}
Figure