Generalized Fractional Repetition Codes for Binary Coded Computations
Authors:
- Neophytos CharalambidesNCNeophytos Charalambides
- Hessam MahdavifarHMHessam Mahdavifar
- Alfred O. Hero IiiAIAlfred O. Hero Iii
Preprint
Abstract
This paper addresses the gradient coding and coded matrix multiplication problems in distributed optimization and coded computing. We present a numerically stable binary coding method which overcomes the drawbacks of the \textit{Fractional Repetition Coding} gradient coding method proposed by Tandon et al., and can also be leveraged by coded computing networks whose servers are of heterogeneous nature. Specifically, we propose a construction for fractional repetition gradient coding; while ensuring that the generator matrix remains close to perfectly balanced for any set of coded parameters, as well as a low complexity decoding step. The proposed binary encoding avoids operations over the real and complex numbers which are inherently numerically unstable, thereby enabling numerically stable distributed encodings of the partial gradients. We then make connections between gradient coding and coded matrix multiplication. Specifically, we show that any gradient coding scheme can be extended to coded matrix multiplication. Furthermore, we show how the proposed binary gradient coding scheme can be used to construct two different coded matrix multiplication schemes, each achieving different trade-offs.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Coded matrix computation with gradient coding2023
- Efficient fair principal component analysisMachine Learning, 2022
- Analog Lagrange Coded ComputingIEEE Journal on Selected Areas in Information Theory, 2021
- Stochastic Gradient Coding for Straggler Mitigation in Distributed LearningIEEE Journal on Selected Areas in Information Theory, 2020
- Gradient Coding Based on Block Designs for Mitigating Adversarial Stragglers2019
- Distributed Stochastic Gradient Descent Using LDGM Codes2019
- Gradient Coding with Clustering and Multi-Message Communication2019
- A Unified Coding Framework for Distributed Computing with Straggling Servers2017
- Design of capacity-approaching irregular low-density parity-check codesIEEE Transactions on Information Theory, 2001
- The Approximation of One Matrix by Another of Lower RankPsychometrika, 1936