Metraipolis › archive › dc_ad273133cc4f
Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting — arXiv:2608.28910
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.28910
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T08:32:31.343Z
- SHA-256 of the archived text
1e3b6d5130fd7e6735a7f039494347da7c9234445a777bf878de81878377b62a- Stable URL of this page
https://metraipolis.com/documento/dc_ad273133cc4f
How to cite
Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting — arXiv:2608.28910 — arXiv (en), https://arxiv.org/abs/2608.28910 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ad273133cc4f (Metraipolis archive dc_ad273133cc4f, sha256 1e3b6d5130fd7e6735a7f039494347da7c9234445a777bf878de81878377b62a)
BibTeX
@misc{dcad273133cc4f,
title = {Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting — arXiv:2608.28910},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.28910},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ad273133cc4f; sha256 1e3b6d5130fd7e6735a7f039494347da7c9234445a777bf878de81878377b62a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28910. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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})$.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-01 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.28910 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T08:13:26.712Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).