# Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 41 references that are in the map.
- First posted on arXiv 28 Aug 2026.

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

- [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)
- [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)
- [On the Optimal Recovery Threshold of Coded Matrix Multiplication](https://mlsanity.com/paper/1801.10292/) (2018)
- [Towards Optimal Sobolev Norm Rates for the Vector-Valued Regularized Least-Squares Algorithm](https://mlsanity.com/paper/2312.07186/) (2023)
- [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)
- [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)

## Abstract (arXiv)

Coded computing has emerged as a powerful paradigm for mitigating the impact of straggling workers in distributed computing systems. However, existing coded-computing schemes are predominantly designed for the exact recovery of highly structured computations, such as polynomial evaluation and matrix multiplication, and typically rely on strict recovery thresholds. These assumptions significantly limit their applicability to modern machine-learning workloads, particularly deep neural networks (DNNs), whose computations generally lack rigid algebraic structure and, in many applications, require only accurate approximations rather than exact recovery. To address this gap, we revisit coded computing from a learning-theoretic perspective and introduce General Coded Computing (GCC). Rather than adopting existing algebraic tools, GCC formulates coded computing through a natural end-to-end mean-squared error loss that directly measures the discrepancy between the desired computations and their recovered estimates. By deriving suitable upper bounds and restricting the encoder and decoder to a reproducing kernel Hilbert space (RKHS) with mild smoothness constraints, we show that both the encoder and decoder admit specific representations as linear combinations of RKHS kernel functions. This representation allows the corresponding coefficients to be computed efficiently. Moreover, this framework enables us to establish theoretical performance guarantees for GCC under two complementary straggler regimes. In the worst-case setting with N worker nodes, and at most S stragglers, we show that the end-to-end loss decays at least at rate O(S3N-3) for standard configurations. We then study a probabilistic setting in which each worker independently straggles with probability p. We prove that the expected loss can still converge at rate O(log1/p3(N)N-3).