通用编码计算的学习理论基础：落后者环境

arXiv:2608.28910v1 公告类型：新 摘要：编码计算已成为减轻分布式计算系统中落后工作人员影响的强大范例。然而，现有的编码计算方案主要是为高度结构化计算的精确恢复而设计的，例如多项式求值和矩阵乘法，并且通常依赖于严格的恢复阈值。这些假设极大地限制了它们对现代机器学习工作负载的适用性，特别是深度神经网络（DNN），其计算通常缺乏严格的代数结构，并且在许多应用中只需要精确的近似而不是精确的恢复。为了解决这一差距，我们从学习理论的角度重新审视编码计算，并引入通用编码计算（GCC）。 GCC 没有采用现有的代数工具，而是通过自然的端到端均方误差损失来制定编码计算，该损失直接测量所需计算与其恢复的估计之间的差异。通过推导合适的上限并将编码器和解码器限制在具有温和平滑度约束的再现核希尔伯特空间（RKHS）中，我们表明编码器和解码器都接受特定的表示作为 RKHS 核函数的线性组合。这种表示允许有效地计算相应的系数。此外，这个框架使我们能够在两个互补的落后者制度下为海湾合作委员会建立理论上的绩效保证。在最坏的情况下，有 $N$ 个工作节点，最多有 $S$ 个落后者，我们表明，对于标准配置，端到端损耗至少以 $O(S^3N^{-3})$ 的速率衰减。然后我们研究一个概率设置，其中每个工人独立地以 $p$ 的概率陷入困境。我们证明预期损失仍然可以以 $O(\log_{1/p}^3(N)N^{-3})$ 速率收敛。