超越客户端平均：随机SCAFFOLD中客户端无关的二阶平稳偏差分量

# 超越客户端平均：随机 SCAFFOLD 中与客户端无关的二阶稳态偏差分量
来源：https://arxiv.org/html/2608.26765

###### 摘要
现有的随机 SCAFFOLD 的常步长分析识别出一个主导的 \(O(\gamma/N)\) 稳态均值偏差，并表明随着客户端数量增加，高阶偏差可能持续存在，但未在系数层面识别出第一个与客户端无关的贡献。对于具有一维同质客户端、固定本地步数 \(H\) 和有界加性梯度噪声的全参与随机 SCAFFOLD，我们证明，对 \(N \geq 2\) 一致地，
\[
\mathbb{E}_{\pi_{\gamma,N,H}}[x] - x^{\star} = -\frac{f'''(x^{\star})\sigma^{2}}{4f''(x^{\star})^{2}}\frac{\gamma}{N} - \frac{f'''(x^{\star})\sigma^{2}}{12f''(x^{\star})}\frac{(H-1)(5H-1)}{H}\gamma^{2} + O_{H}\left(\frac{\gamma^{2}}{N} + \gamma^{3}\right).
\]
因此，客户端平均抑制了主导的 \(O(\gamma/N)\) 偏差，但当其系数非零时，并未移除与客户端无关的 \(O(\gamma^{2})\) 分量。其机制是间接的：尽管直接的控制贡献在线性全局平均中逐路径抵消，但控制仍然改变了每轮内的本地轨迹及其二阶矩。因此，新的梯度噪声和持续的控制波动产生了局部二阶矩修正，而非二次曲率将其转化为稳态均值偏差。对于二次目标，该系数消失。数值实验与预测的系数、其随客户端数量增加的持续性以及所述联合余项一致。该结果限于一维同质固定 \(H\) 的设定。

## 1 引言
联邦学习通过通信换取本地计算：每个参与的客户端在服务器平均其更新之前执行若干随机梯度步骤。这种设计可以显著减少同步，但本地轨迹可能会向客户端特定的方向漂移。SCAFFOLD 通过将控制变量附加到本地更新来解决此问题，使客户端能够更紧密地跟踪共同的优化方向 [6 (https://arxiv.org/html/2608.26765#bib.bib1)]。大多数分析研究的是有限时间收敛。然而，在常步长下，随机迭代会继续围绕最优值波动，其长期行为由一个不变分布描述，该分布的均值不一定等于最小化点。最近对随机 SCAFFOLD 的常步长分析使通常的“更多客户端有帮助”的直觉变得精确，并识别了其高阶极限。Mangold 等人 [12] (https://arxiv.org/html/2608.26765#bib.bib2) 建立了稳态性、直到高阶项的客户端数量线性加速，以及一个不随客户端数量增加而消除的高阶稳态偏差分量。在标量同质特例中，他们的主导稳态均值偏差层为 \(O(\gamma/N)\)，其中 \(\gamma\) 是步长，\(N\) 是参与客户端的数量。尽管如此，他们的分析仍未在系数层面解决与客户端无关的高阶贡献。我们询问客户端平均是否抑制了该第一个与客户端无关的贡献，如果没有，哪个项首先承载它，以及什么机制生成它。在此设定下，我们的答案是否定的。对于具有一维同质客户端、固定本地步数 \(H\)、足够小的常步长 \(\gamma\) 和有界加性梯度噪声的全参与随机 SCAFFOLD，我们证明
\[
\mathbb{E}_{\pi_{\gamma,N,H}}[x] - x^{\star} = -\frac{\tau\sigma^{2}}{4a^{2}}\frac{\gamma}{N} - \frac{\tau\sigma^{2}}{12a}\frac{(H-1)(5H-1)}{H}\gamma^{2} + O_{H}\left(\frac{\gamma^{2}}{N} + \gamma^{3}\right), \tag{1}
\]
其中 \(a = f''(x^{\star})\)，\(\tau = f'''(x^{\star})\)。第一个显示的层随客户端数量增加而减小；第二个则不。一致余项还表明，在已知的 \(\gamma/N\) 层被移除后，归一化残差沿每个联合序列 \(N \to \infty\) 和 \(\gamma \to 0\) 收敛到显示的 \(\gamma^{2}\) 系数。

#### 为什么这很重要。
客户端平均既减少了稳态波动，也减少了已知的主导均值偏差层，这表明增加参与度应能持续提高长期精度。方程 (1) 识别了该机制在展开式中的一个限制：当其系数非零时，与客户端无关的 \(\gamma^{2}\) 分量在 \(\gamma/N\) 层变得更小后，不会通过进一步平均而减少。仅增加 \(N\) 无法减少此分量；减小步长可以，而基于系数的偏差校正是未来工作的自然方向。

令 \(Y\) 表示在稳态下通过对客户端 \(c\) 和本地步索引 \(h = 0, \ldots, H-1\) 均匀采样获得的局部迭代。精确的稳态均值平衡等式给出 \(\mathbb{E}[f'(Y)] = 0\)，然后局部泰勒展开给出启发式：
\[
0 = \mathbb{E}[f'(Y)] \approx a \mathbb{E}[Y] + \frac{\tau}{2}\mathbb{E}[Y^{2}], \quad \mathbb{E}[Y] \approx -\frac{\tau}{2a}\mathbb{E}[Y^{2}].
\]
因此，二阶矩到均值的直觉直接来自精确的稳态平衡加上局部泰勒展开：非二次曲率将二阶矩修正转化为均值偏移。在 SCAFFOLD 中，控制在线性客户端平均中抵消，但它们仍然影响中间的本地轨迹。因此，新的梯度噪声和持续的控制波动改变了本地轨迹的二阶矩，然后曲率将其转化为稳态偏差；图 1 (https://arxiv.org/html/2608.26765#S1.F1) 总结了这个间接通道。

参见图注
图 1：与客户端无关的稳态偏差层背后的机制。服务器处的线性控制抵消并未消除控制对中间本地轨迹的影响。新的噪声和持续的控制波动改变了本地二阶矩，而非二次曲率将其转化为均值偏移。

贡献如下。
- • 客户端平均在二阶的限制。我们识别了一个显式的与客户端无关的 \(\gamma^{2}\) 稳态偏差系数，对于固定的 \(H\)，余项在 \((\gamma, 1/N)\) 上联合一致。
- • SCAFFOLD 内的轨迹级机制。我们将该系数追溯到两个局部二阶矩来源：新的随机梯度噪声和持续的控制波动。
- • 针对性的数值检查。我们测试了随客户端数量增加的持续性、向预测系数的收敛，以及当随机性或非二次曲率被移除时的行为。

标量分析在超出一维时仍有意义，因为它分离出了三个也出现在更高维动态中的要素：持续的控制二阶矩、轮内本地轨迹和非线性曲率。它们的相互作用将涉及协方差-三阶导数收缩；建立这样的扩展仍然开放。

#### 主张边界。
该定理涉及全参与、一维同质客户端、有界加性噪声和固定 \(H\)。它在 \(N\) 和小的 \(\gamma\) 上一致，但在 \(H \to \infty\) 时不一致，并且它没有识别 \(\gamma^{2}\) 的完整有限 \(N\) 系数。源分解是 SCAFFOLD 内部的，不是与 FedAvg 的定理级比较。两个显示层的交叉是一个渐近尺度比较，不是对总有限步偏差的单调性陈述。数值实验是有限设置的一致性检查。多维、异质客户端、状态相关噪声和去偏扩展仍然开放。

第 2 节 (https://arxiv.org/html/2608.26765#S2) 定位结果。第 3 节 (https://arxiv.org/html/2608.26765#S3) 将标准 SCAFFOLD 控制与证明中使用的零和参数化联系起来。第 4 节 (https://arxiv.org/html/2608.26765#S4) 和第 5 节 (https://arxiv.org/html/2608.26765#S5) 陈述定理并推导其机制，而第 6 节 (https://arxiv.org/html/2608.26765#S6) 和第 7 节 (https://arxiv.org/html/2608.26765#S7) 总结证明和数值证据。

## 2 相关工作
#### 联邦平均和本地 SGD。
联邦平均 (FedAvg) 引入了迭代本地模型平均作为联邦学习的通信高效原语 [13 (https://arxiv.org/html/2608.26765#bib.bib9)]；更广泛的优化和系统景观由 Kairouz 等人 [5] (https://arxiv.org/html/2608.26765#bib.bib16) 综述。其优化核心与本地 SGD 密切相关，在本地 SGD 中，工作节点在同步之前采取若干随机梯度步骤。早期理论确立，本地 SGD 可以在通信更少的同时保留小批量 SGD 的统计速率 [14 (https://arxiv.org/html/2608.26765#bib.bib10)]，随后的分析阐明了相同和异质客户端目标的不同作用 [7 (https://arxiv.org/html/2608.26765#bib.bib11)]，以及本地更新优于或不优于小批量 SGD 的范围 [16 (https://arxiv.org/html/2608.26765#bib.bib12)]。

#### SCAFFOLD 和控制校正。
SCAFFOLD 通过添加控制变量来增强本地更新，以校正客户端漂移 [6 (https://arxiv.org/html/2608.26765#bib.bib1)]。最近的工作改进了有限时间图景：Luo 等人 [8] (https://arxiv.org/html/2608.26765#bib.bib3) 在梯度/Hessian 相似性和高阶光滑条件下获得了改进的本地 SGD 和 SCAFFOLD 速率，而 Mangold 和 Moulines [11] (https://arxiv.org/html/2608.26765#bib.bib5) 对任意本地步数给出了精细的二次分析。这些结果解释了何时本地计算和控制校正能改善有限时间优化，但它们没有表征常步长随机 SCAFFOLD 生成的不变分布的均值。

#### 常步长随机优化和稳态律。
在适当的稳定性和正则性条件下，常步长随机梯度方法自然地在不变分布方面进行研究。这种观点出现在常步长 SGD 的扩散近似 [9 (https://arxiv.org/html/2608.26765#bib.bib14)] 中，并且出现在稳态随机梯度动态的小步长严格刻画 [3 (https://arxiv.org/html/2608.26765#bib.bib13), 2 (https://arxiv.org/html/2608.26765#bib.bib15)] 中。特别是，Chen 等人 [2] (https://arxiv.org/html/2608.26765#bib.bib15) 在它们的条件下，获得了光滑强凸 SGD 及相关随机近似模型的缩放稳态律的高斯/李雅普诺夫刻画，而 Dieuleveut 等人 [3] (https://arxiv.org/html/2608.26765#bib.bib13) 推导了稳态/渐近矩展开，并使用 Richardson-Romberg 外推来减少步长偏差。同样的视角最近在联邦和去中心化算法中得到发展。Mangold 等人 [10] (https://arxiv.org/html/2608.26765#bib.bib4) 通过其马尔可夫结构分析了常步长 FedAvg，表征了稳态偏差和方差，推导了一阶偏差展开，并构建了联邦 Richardson-Romberg 校正。Mangold 等人 [12] (https://arxiv.org/html/2608.26765#bib.bib2) 将此框架扩展到随机 SCAFFOLD，证明了稳态律的存在性和几何收敛性、客户端数量方差缩减，以及一个一阶稳态均值偏差展开，其标量同质主导层为 \(O(\gamma/N)\)。Versini 等人 [15] (https://arxiv.org/html/2608.26765#bib.bib8) 为去中心化 SGD 获得了相关的一阶稳态偏差和方差展开，分离了随机性、异质性和网络效应。

#### 非线性和高阶稳态偏差。
此处研究的机制属于常步长随机近似中更广泛的噪声-非线性相互作用类。Allmeier 和 Gast [1] (https://arxiv.org/html/2608.26765#bib.bib7) 允许马尔可夫噪声依赖于迭代点，证明了一个 \(O(\alpha)\) 稳态偏差界，并将 Polyak-Ruppert 时间平均偏差细化为 \(\alpha V + O(\alpha^{2})\)。Huo 等人 [4] (https://arxiv.org/html/2608.26765#bib.bib6) 表明，马尔可夫记忆和非线性可以相互作用，产生常步长稳态偏差的不同分量。这些结果确立了持续的随机波动可以被非线性动力学转化为均值偏移。然而，它们没有确定 SCAFFOLD 本地控制递归生成的算法特定高阶系数。

#### 当前结果的定位。
最接近的起点是 Mangold 等人 [12] (https://arxiv.org/html/2608.26765#bib.bib2)。我们使用它们的稳态律存在性和几何收敛性、粗略迭代矩界、主导控制二阶矩，以及已知的 \(O(\gamma/N)\) 偏差系数。Mangold 等人确立随机 SCAFFOLD 保留了一个不随客户端数量增加而消除的高阶稳态偏差。尽管如此，他们的分析没有在系数层面识别与客户端无关的贡献。在一维同质固定 \(H\) 的设定中，我们明确解决了这种结构：第一个与客户端无关的项是 \(N^{0}\gamma^{2}\)，其闭式系数分解为新的轮内本地梯度噪声和持续的 SCAFFOLD 控制二阶矩。该结果与 Mangold 和 Moulines [11] (https://arxiv.org/html/2608.26765#bib.bib5) 的二次理论互补：二次目标支持更精细的任意 \(H\) 收敛分析，但 \(f''' \equiv 0\) 移除了此处分离的二阶矩到均值的转化。源分解是 SCAFFOLD 内部的；它不是与 FedAvg 的定理级比较，后者需要匹配的二阶 FedAvg 展开。

## 3 设定和精确等式
我们故意使用同质标量设定，消除客户端异质性作为偏差的混杂来源，分离 SCAFFOLD 控制递归本身的随机效应。所有 \(N\) 个客户端都参与每一轮通信。即使目标相同，随机客户端控制仍然是非平凡的，因为它们持续从有噪声的本地轨迹中刷新。唯一最小值平移到 \(x^{\star} = 0\)，所有 \(N \geq 2\) 个客户端共享相同的目标 \(f_{c} = f\)，并且本地步数 \(H \geq 2\) 是固定的。目标满足 \(f \in C^{5}(\mathbb{R})\) 和 \(0 < \mu \leq f''(y) \leq L < \infty\)，且具有有界的三阶到五阶导数。我们记 \(a := f''(0) > 0\)，\(\tau := f'''(0)\)，\(\kappa := f''''(0)\)。在客户端 \(c\) 的本地步 \(h\)，随机梯度为
\[
\nabla F_{c,h}(y) = f'(y) + \varepsilon_{c,h},
\]
其中新的