General Coded Computing Mitigates Stragglers in Distributed ML Workloads.

Distributed computing systems often suffer from "stragglers" – slow or failing worker nodes that delay overall computation. While traditional coded computing schemes exist, they are typically designed for exact recovery of highly structured computations, limiting their applicability to modern machine learning workloads, which often require only accurate approximations. This research addresses this gap by introducing General Coded Computing (GCC). GCC re-frames coded computing from a learning-theoretic perspective, using an end-to-end mean-squared error loss to measure the discrepancy between desired and recovered computations. By restricting encoders and decoders to a reproducing kernel Hilbert space (RKHS), the framework allows for efficient computation of coefficients and provides theoretical performance guarantees. The paper analyzes GCC under two straggler regimes: a worst-case scenario and a probabilistic setting. It demonstrates that the end-to-end loss decays at a rate of O(S^3N^-3) in the worst-case (S stragglers out of N workers) and O(log_{1/p}^3(N)N^-3) in the probabilistic setting (each worker straggles with probability p). This provides a robust foundation for applying coded computing to less structured, approximate machine learning tasks.