Generalized Fractional Repetition Codes for Binary Coded Computations
- 14 January 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (3) , 2170-2194
Abstract
This paper addresses the gradient coding and coded matrix multiplication problems in distributed optimization and coded computing. We present a computationally efficient coding method which overcomes the drawbacks of the 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 coding parameters, as well as a low complexity decoding step. The proposed binary encoding avoids operations over the real and complex numbers which inherently introduce numerical and rounding errors, thereby enabling accurate 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
Funding Information
- U.S. National Science Foundation (NSF CCF-2246213, CCF-2312752)
- Army Research Office (W911NF2310343)
- U.S. Department of Energy (DE-NA0003921)
- Center for Ubiquitous Connectivity (CUbiC) under the JUMP 2.0 Program
- EnCORE Institute under NSF (2217058)
This publication has 67 references indexed in Scilit:
- Efficient fair principal component analysisMachine Learning, 2022
- Randomized nonnegative matrix factorizationPattern Recognition Letters, 2018
- On the optimal recovery threshold of coded matrix multiplication2017
- Anytime coding for distributed computation2016
- Coded Distributed Computing: Straggling Servers and Multistage Dataflows2016
- Understanding Machine Learning2014
- Fractional repetition codes for repair in distributed storage systems2010
- Design of capacity-approaching irregular low-density parity-check codesIEEE Transactions on Information Theory, 2001
- Near Shannon limit performance of low density paritycheck codesElectronics Letters, 1996
- The Approximation of One Matrix by Another of Lower RankPsychometrika, 1936