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

Researchers introduced General Coded Computing (GCC), a learning-theoretic framework for coded computing that handles straggling workers in distributed systems without requiring exact recovery or rigid algebraic structure, targeting modern machine-learning workloads like deep neural networks. The framework, detailed in arXiv:2608.28910v1, uses an end-to-end mean-squared error loss and RKHS-based encoders/decoders, achieving worst-case end-to-end loss decay at rate O(S^3N^{-3}) with N worker nodes and at most S stragglers, and expected loss convergence at O(log_{1/p}^3(N)N^{-3}) when each worker straggles independently with probability p.

arXiv:2608.28910v1 Announce Type: new Abstract: 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 S^3N^{-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 \log {1/p}^3 N N^{-3} $.