Coded matrix computation with gradient coding
Authors:
- 25 June 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2183-2188
Abstract
Polynomial based approaches, such as the Mat-Dot and entangled polynomial codes (EPC) have been used extensively within coded matrix computations to obtain schemes with good recovery thresholds. However, these schemes are well-recognized to suffer from poor numerical stability in decoding. Moreover, the encoding process in these schemes involves linearly combining a large number of input submatrices, i.e., the encoding weight is high. For the practically relevant case of sparse input matrices, this can have the undesirable effect of significantly increasing the worker node computation time. In this work, we propose a generalization of the EPC scheme by combining the idea of gradient coding along with the basic EPC encoding. Our technique allows us to reduce the weight of the encoding and arrive at schemes that exhibit much better numerical stability; this is achieved at the expense of a worse threshold. By appropriately setting parameters in our scheme, we recover several well-known schemes in the literature. Simulation results show that our scheme provides excellent numerical stability and fast computation speed (for sparse input matrices) as compared to EPC and Mat-Dot codes.Keywords
All Related Versions
Funding Information
- Ministry of Education
- National Science Foundation
This publication has 18 references indexed in Scilit:
- Entangled Polynomial Codes for Secure, Private, and Batch Distributed Matrix Multiplication: Breaking the "Cubic" Barrier2020
- Straggler-Resistant Distributed Matrix Computation via Coding Theory: Removing a Bottleneck in Large-Scale Data ProcessingIEEE Signal Processing Magazine, 2020
- Straggler Mitigation in Distributed Matrix Multiplication: Fundamental Limits and Optimal CodingIEEE Transactions on Information Theory, 2020
- Random Khatri-Rao-Product Codes for Numerically-Stable Distributed Matrix Multiplication2019
- On the Optimal Recovery Threshold of Coded Matrix MultiplicationIEEE Transactions on Information Theory, 2019
- Universally Decodable Matrices for Distributed Matrix-Vector Multiplication2019
- Distributed Matrix-Vector Multiplication: A Convolutional Coding Approach2019
- C3LES: Codes for Coded Computation that Leverage Stragglers2018
- Exploitation of Stragglers in Coded Computation2018
- Speeding Up Distributed Machine Learning Using CodesIEEE Transactions on Information Theory, 2017