# Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework

arXiv: https://arxiv.org/abs/2406.00300 · HTML: https://mlsanity.com/paper/2406.00300/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 62 references that are in the map.
- First posted on arXiv 1 Jun 2024.

## Builds on (most cited first, 20 of 20)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [RepVGG: Making VGG-style ConvNets Great Again](https://mlsanity.com/paper/2101.03697/) (2021)
- [Speeding Up Distributed Machine Learning Using Codes](https://mlsanity.com/paper/1512.02673/) (2015)
- [Lagrange Coded Computing: Optimal Design for Resiliency, Security and Privacy](https://mlsanity.com/paper/1806.00939/) (2018)
- [Polynomial Codes: an Optimal Design for High-Dimensional Coded Matrix Multiplication](https://mlsanity.com/paper/1705.10464/) (2017)
- [Straggler Mitigation in Distributed Optimization Through Data Encoding](https://mlsanity.com/paper/1711.04969/) (2017)
- [A Scalable Approach for Privacy-Preserving Collaborative Machine Learning](https://mlsanity.com/paper/2011.01963/) (2020)
- [CodedPrivateML: A Fast and Privacy-Preserving Framework for Distributed Machine Learning](https://mlsanity.com/paper/1902.00641/) (2019)
- [Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing](https://mlsanity.com/paper/2009.08327/) (2020)
- [CodedSketch: A Coding Scheme for Distributed Computation of Approximated Matrix Multiplication](https://mlsanity.com/paper/1812.10460/) (2018)
- [Analog Lagrange Coded Computing](https://mlsanity.com/paper/2008.08565/) (2020)
- [Near-Optimal Straggler Mitigation for Distributed Gradient Methods](https://mlsanity.com/paper/1710.09990/) (2017)
- [OverSketch: Approximate Matrix Multiplication for the Cloud](https://mlsanity.com/paper/1811.02653/) (2018)
- [OverSketched Newton: Fast Convex Optimization for Serverless Systems](https://mlsanity.com/paper/1903.08857/) (2019)
- [When Do Redundant Requests Reduce Latency ?](https://mlsanity.com/paper/1311.2851/) (2013)
- [On the Capacity of Secure Distributed Matrix Multiplication](https://mlsanity.com/paper/1806.00469/) (2018)
- [ApproxIFER: A Model-Agnostic Approach to Resilient and Robust Prediction Serving Systems](https://mlsanity.com/paper/2109.09868/) (2021)
- [Parity Models: A General Framework for Coding-Based Resilience in ML Inference](https://mlsanity.com/paper/1905.00863/) (2019)
- [On the Upload versus Download Cost for Secure and Private Matrix Multiplication](https://mlsanity.com/paper/1906.10684/) (2019)

## Built on by (most cited first, 5 of 5)

- [General Coded Computing: Adversarial Settings](https://mlsanity.com/paper/2502.08058/) (2025)
- [General Coded Computing in a Probabilistic Straggler Regime](https://mlsanity.com/paper/2502.00645/) (2025)
- [Adversarial Robustness of Nonparametric Regression](https://mlsanity.com/paper/2505.17356/) (2025)
- [DReS: Dual Reconstruction Smoothing for Functional Regularization](https://mlsanity.com/paper/2510.00253/) (2025)
- [Manifold-Aware General Coded Computing for Straggler-Resilient Distributed Computing](https://mlsanity.com/paper/2609.00552/) (2026)

## Abstract (arXiv)

Coded computing has emerged as a promising framework for tackling significant challenges in large-scale distributed computing, including the presence of slow, faulty, or compromised servers. In this approach, each worker node processes a combination of the data, rather than the raw data itself. The final result then is decoded from the collective outputs of the worker nodes. However, there is a significant gap between current coded computing approaches and the broader landscape of general distributed computing, particularly when it comes to machine learning workloads. To bridge this gap, we propose a novel foundation for coded computing, integrating the principles of learning theory, and developing a framework that seamlessly adapts with machine learning applications. In this framework, the objective is to find the encoder and decoder functions that minimize the loss function, defined as the mean squared error between the estimated and true values. Facilitating the search for the optimum decoding and functions, we show that the loss function can be upper-bounded by the summation of two terms: the generalization error of the decoding function and the training error of the encoding function. Focusing on the second-order Sobolev space, we then derive the optimal encoder and decoder. We show that in the proposed solution, the mean squared error of the estimation decays with the rate of O(S3 N-3) and O(S^frac85N^frac-35) in noiseless and noisy computation settings, respectively, where N is the number of worker nodes with at most S slow servers (stragglers). Finally, we evaluate the proposed scheme on inference tasks for various machine learning models and demonstrate that the proposed framework outperforms the state-of-the-art in terms of accuracy and rate of convergence.