通用编码计算的学习理论基础：掉队者场景

# 广义编码计算的学习理论基础：滞后场景  
来源：https://arxiv.org/html/2608.28910

## 广义编码计算的学习理论基础：滞后场景

**致谢**：本工作部分由美国国家科学基金会资助（基金号 CIF-2348638）。  
**致谢**：本工作曾在2024年神经信息处理系统大会（NeurIPS 2024，加拿大温哥华，2024年12月10日至15日）、2025年IEEE国际信息论研讨会（ISIT 2025，美国密歇根州安阿伯，2025年6月22日至27日）以及一篇综述论文\[1 (https://arxiv.org/html/2608.28910#bib.bib1)\]中发表部分内容。

**作者**：  
Behrooz Tahmasebi  
隶属机构：哈佛大学  
邮箱：[email protected]  

Mohammad Ali Maddah-Ali  
隶属机构：明尼苏达大学双城分校  
邮箱：[email protected]  

### 摘要

编码计算已成为缓解分布式计算系统中滞后工作节点影响的强大范式。然而，现有编码计算方案主要针对高度结构化计算（如多项式求值和矩阵乘法）的精确恢复而设计，通常依赖严格的恢复阈值。这些假设显著限制了其在现代机器学习工作负载中的适用性，特别是深度神经网络（DNN），因为DNN的计算通常缺乏严格的代数结构，且在许多应用场景下仅需近似精确恢复而非精确恢复。为填补这一空白，我们从学习理论的角度重新审视编码计算，并提出了广义编码计算（GCC）。GCC不采用现有的代数工具，而是通过自然的端到端均方误差损失来构建编码计算，该损失直接衡量期望计算结果与恢复估计值之间的差异。通过推导合适的上界，并将编码器和解码器限制在具有平滑约束的再生核希尔伯特空间（RKHS）中，我们证明了编码器和解码器均可表示为RKHS核函数的线性组合。这种表示形式使得对应的系数能够高效计算。此外，该框架使我们能够为GCC在两种互补的滞后情景下建立理论性能保证。在最坏情况下，设有 \(N\) 个工作节点和最多 \(S\) 个滞后节点，我们证明在标准配置下端到端损失至少以 \(O(S^3 N^{-3})\) 的速率衰减。随后，我们研究了每个工作节点独立以概率 \(p\) 滞后的概率情景。我们证明期望损失仍能以 \(O(\log_{1/p}^3(N) N^{-3})\) 的速率收敛。在具有数百万参数的复杂DNN架构上的大量实验验证了理论预测，并表明GCC比最先进的编码计算方案实现了更低的重建误差和更快的收敛速度。

### 索引术语  
分布式计算、编码计算、平滑样条、非参数回归、滞后容错

## I. 引言

分布式计算已成为管理海量数据集和评估日益复杂函数（如机器学习模型）不可或缺的技术。通常，这些系统在主从架构下运行，中央**主节点**将计算任务分配给一组**工作节点**。然而，将这些任务分配到大型集群中会引入系统性漏洞，最显著的是存在**滞后节点**——即经历不可预测延迟或未能在规定时限内返回结果的工作节点。传统的朴素分配策略（将数据分区无冗余地分配给各个工作节点）受限于最慢的节点，导致严重的资源利用不足。为解决这一瓶颈，**编码计算**被引入，其灵感来源于通信领域的纠错码\[2 (https://arxiv.org/html/2608.28910#bib.bib2), 3 (https://arxiv.org/html/2608.28910#bib.bib3), 4 (https://arxiv.org/html/2608.28910#bib.bib4), 5 (https://arxiv.org/html/2608.28910#bib.bib5), 6 (https://arxiv.org/html/2608.28910#bib.bib6), 7 (https://arxiv.org/html/2608.28910#bib.bib7), 8 (https://arxiv.org/html/2608.28910#bib.bib8)\]。通过向分布式数据中故意注入结构化冗余，主节点可以仅使用部分工作节点的输出来恢复精确的计算结果。尽管非常成功，但经典的编码计算本质上是针对有限域上的代数任务和高度结构化的计算（如矩阵乘法和多项式求值）而开发的\[3 (https://arxiv.org/html/2608.28910#bib.bib3), 4 (https://arxiv.org/html/2608.28910#bib.bib4), 5 (https://arxiv.org/html/2608.28910#bib.bib5), 9 (https://arxiv.org/html/2608.28910#bib.bib9), 6 (https://arxiv.org/html/2608.28910#bib.bib6), 10 (https://arxiv.org/html/2608.28910#bib.bib10), 7 (https://arxiv.org/html/2608.28910#bib.bib7)\]。此外，这些方法保证精确恢复，但施加了严格的**恢复阈值**：如果非滞后工作节点的数量低于此阈值，解码过程将完全失败。这种刚性使得经典方案不适用于更一般和复杂的计算，例如缺乏结构化代数特性且仅需良好近似的深度神经网络。

为了将编码计算的适用范围扩展到更广泛的功能类，已出现几个研究方向。初步尝试试图通过多项式代理来近似非多项式目标函数，从而将一般计算纳入经典框架\[11 (https://arxiv.org/html/2608.28910#bib.bib11), 12 (https://arxiv.org/html/2608.28910#bib.bib12)\]。然而，由于实数域上的高次多项式插值容易出现数值不稳定，后续研究主要致力于改进底层的编码机制，例如使用替代多项式基或模拟编码\[13 (https://arxiv.org/html/2608.28910#bib.bib13), 14 (https://arxiv.org/html/2608.28910#bib.bib14), 15 (https://arxiv.org/html/2608.28910#bib.bib15), 16 (https://arxiv.org/html/2608.28910#bib.bib16), 17 (https://arxiv.org/html/2608.28910#bib.bib17)\]。最近，人们认识到许多应用（包括机器学习工作负载）本质上能容忍小的计算扰动，因此转向**近似编码计算**的范式转变获得了关注\[10 (https://arxiv.org/html/2608.28910#bib.bib10), 18 (https://arxiv.org/html/2608.28910#bib.bib18), 19 (https://arxiv.org/html/2608.28910#bib.bib19), 20 (https://arxiv.org/html/2608.28910#bib.bib20), 21 (https://arxiv.org/html/2608.28910#bib.bib21)\]。通过有意地用有界近似误差交换精确恢复，这些方法消除了严格的恢复阈值约束，从而产生了一个更灵活的系统，主节点可以从任何工作节点子集计算出良好的近似值，并且最终计算的准确性随着更多工作节点返回结果而提高。

尽管实现了这种范式转变，这些尝试最终未能弥合经典编码计算与一般分布式计算系统之间的鸿沟。这种脱节的根本原因在于经典编码计算基础性地依赖于代数编码理论，而这一范式本质上与一般的高维函数不兼容。例如，虽然多项式近似对于简单的非线性函数（如\[12 (https://arxiv.org/html/2608.28910#bib.bib12)\]中用于逻辑回归设置的sigmoid函数）有用，但在理论上和实践中，使用单个全局多项式以可接受的精度来近似深度神经网络的复杂、高度非线性行为是不可行的。因此，尽管使用多项式近似或改进多项式基提供了一定的灵活性，但这些方法仍然依赖于代数结构，而这些结构根本无法扩展到任意实值函数。这种不匹配促使我们重新审视编码计算的设计原则。\[22 (https://arxiv.org/html/2608.28910#bib.bib22)\]中的工作通过摆脱严格的代数编码，并利用逼近论工具来处理一般计算任务，在此方向迈出了第一步。然而，其编码器和解码器并非明确设计为优化端到端编码计算目标。相反，它们的设计主要受现成的逼近论工具引导，没有直接机制来最小化恢复函数与真实计算目标之间的误差。因此，开发一种直接优化任意高维连续函数近似误差的统一方法仍是一个开放性挑战。

为填补这一关键空白，我们提出了广义编码计算（GCC），这是一个弥合编码计算与一般分布式计算之间鸿沟的新框架。与依赖刚性代数结构或现成近似技术的先前方法不同，GCC围绕一个明确的端到端损失函数构建，该函数与编码计算的核心目标一致：从部分工作节点返回的结果中准确地近似一批输入数据上的目标函数值。为了系统地最小化此目标，我们将编码器和解码器限制在二阶Sobolev函数的再生核希尔伯特空间（RKHS）中。这种泛函分析公式使得可以使用学习理论和样条逼近的工具。我们不是直接求解原始的联合优化问题，而是推导出端到端损失的一个可处理的上界。该上界分解为两个可解释的项：一个解码器近似项，衡量解码器从返回的工作节点输出中重建目标计算的准确性；一个编码器近似项，衡量编码器忠实保留原始输入批数据的程度。然而，解码器近似项同时依赖于编码器和解码器。通过引用表示定理，我们证明了编码器和解码器都可以表示为RKHS核函数的线性组合，其系数可以以闭式解高效计算。因此，尽管编码设计基于学习理论，但编码器和解码器都不需要训练。

总而言之，本文的主要贡献如下：

- **编码计算的学习理论公式化**：我们引入了广义编码计算（GCC），这是一个适用于超越代数结构化任务的编码计算框架。该框架围绕一个明确的端到端损失函数构建，该函数直接捕获了核心的编码计算目标：从部分工作节点返回的结果中准确地近似一批输入上的目标函数值。通过将编码器和解码器公式化为二阶Sobolev函数RKHS中的函数，我们通过该损失函数的可处理上界获得了一种设计高效编码和解码程序的原则性方法。

- **理论保证与收敛速率**：我们刻画了GCC在两种互补的滞后情景下的端到端损失。在最坏情况下，最多有 \(S\) 个滞后节点，我们证明在标准节点配置下，损失至少以 \(O(S^3/N^3)\) 的速率衰减。我们还分析了每个工作节点独立以概率 \(p\) 滞后的概率情景。我们证明期望损失仍能以 \(O(\log_{1/p}^3(N)/N^3)\) 的速率趋于零。

- **广泛的实验评估**：我们在多种计算任务上验证了GCC框架，从经典的结构化目标函数（如多项式）到高度复杂的最先进深度神经网络，包括Vision Transformers (ViTs)\[23 (https://arxiv.org/html/2608.28910#bib.bib23)\]。数值评估有力地支持了我们的理论推导，表明与现有的最先进编码计算方案相比，GCC实现了更优的恢复精度和更快的收敛速度。

本文其余部分的组织结构如下。第II节（https://arxiv.org/html/2608.28910#S2）形式化了分布式计算问题并引入了GCC框架。第III节（https://arxiv.org/html/2608.28910#S3）介绍了本文中使用的数学预备知识。第IV节（https://arxiv.org/html/2608.28910#S4）和第V节（https://arxiv.org/html/2608.28910#S5）分别在最坏情况和概率滞后模型下阐述主要理论结果。第VI节（https://arxiv.org/html/2608.28910#S6）提供了主要结果的证明。第VII节（https://arxiv.org/html/2608.28910#S7）展示了实验设置和结果。第VIII节（https://arxiv.org/html/2608.28910#S8）总结了论文并讨论了未来的研究方向。附录A（https://arxiv.org/html/2608.28910#A1）、B（https://arxiv.org/html/2608.28910#A2）和C（https://arxiv.org/html/2608.28910#A3）收集了理论分析中使用的补充定义和数学工具，而附录D（https://arxiv.org/html/2608.28910#A4）提供了主要定理证明中使用的辅助引理的证明。

### I-A. 符号说明

在本文中，标量用非粗体小写字母表示（例如 \(x\)），向量用粗体小写字母表示（例如 \(\mathbf{x}\)），矩阵用粗体大写字母表示（例如 \(\mathbf{A}\)）。集合用花体大写字母表示（例如 \(\mathcal{S}\)）。编码后的量用波浪号表示；例如，\(\widetilde{\mathbf{x}}\) 表示编码后的向量，\(\widetilde{\mathbf{A}}\) 表示编码后的矩阵。对于 \(n \in \mathbb{N}\)，我们使用简写 \([n] := \{1, 2, \ldots, n\}\)。对于有限集 \(\mathcal{S}\)，其基数表示为 \(|\mathcal{S}|\)。对于可微的标量值函数 \(f: \mathbb{R}^d \to \mathbb{R}\)，其在 \(\mathbf{x}\) 处的梯度表示为 \(\nabla f(\mathbf{x}) \in \mathbb{R}^d\)，海森矩阵表示为 \(D^2 f(\mathbf{x}) \in \mathbb{R}^{d \times d}\)。对于向量值函数 \(f = [f_1, \ldots, f_m]^T: \mathbb{R}^d \to \mathbb{R}^m\)，\(\nabla f_j(\mathbf{x})\) 和 \(D^2 f_j(\mathbf{x})\) 分别表示其第 \(j\) 个分量的梯度和海森矩阵。对于定义在区间 \(\Omega \subseteq \mathbb{R}\) 上的函数 \(g: \Omega \to \mathbb{R}^M\)，我们用 \(g^{(i)}\) 表示其相对于标量参数的第 \(i\) 阶弱导数（见定义3（https://arxiv.org/html/2608.28910#Thmdefinition3)），按分量计算。特别地，\(g^{(0)} := g\)，我们使用简写 \(g' := g^{(1)}\) 和 \(g'' := g^{(2)}\)。欧几里得范数表示为 \(\|\cdot\|_2\)，矩阵 \(\mathbf{A}\) 的算子范数定义为 \(\|\mathbf{A}\|_{\mathrm{op}} := \sup_{\|\mathbf{x}\|_2=1} \|\mathbf{A}\mathbf{x}\|_2\)。对于可测集 \(\Omega \subseteq \mathbb{R}\)，其勒贝格测度表示为 \(\operatorname{Leb}(\Omega)\)。