为分布式计算中的慢节点问题，提出基于学习理论的通用编码计算新框架。
Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting
- 用均方误差损失直接衡量计算结果与恢复值的差距
- 在最坏情况和概率场景下，损失率分别达到O(S³N⁻³)和O(log³ₚ(N)N⁻³)
- 适用于深度学习等无严格代数结构的现代计算任务
编码计算已成为缓解分布式计算系统中慢节点影响的强大范式。然而，现有编码计算方案主要针对多项式求值、矩阵乘法等高度结构化的精确计算，通常依赖严格的恢复阈值，这大大限制了其在现代机器学习任务（尤其是深度神经网络）中的应用，因为这些任务通常缺乏刚性代数结构，且许多情况下只需准确近似而非精确恢复。为此，我们从学习理论视角重新审视编码计算，提出通用编码计算（GCC）。不同于传统代数工具，GCC通过自然的端到端均方误差损失来建模，直接度量期望计算结果与恢复估计之间的差异。通过推导合适的上界，并将编码器和解码器限制在具有温和光滑性约束的再生核希尔伯特空间（RKHS）中，我们证明编码器和解码器可表示为RKHS核函数的线性组合，其系数可高效计算。该框架使我们能在两种互补的慢节点设置下建立理论性能保证：在包含N个工作节点、最多S个慢节点的最坏情形下，端到端损失至少以速率O(S³N⁻³)衰减；在每个工作节点独立以概率p出现慢节点的概率设置下，期望损失仍可收敛至O(log³ₚ(N)N⁻³)。
原文摘要 · Abstract (English)
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})$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。