拜占庭容错聚合方法

尽管联邦平均（FedAvg）提供了一种聚合客户端贡献的简单机制，但其对标准平均值计算的依赖使其极易受到干扰。FedAvg 很容易在一些参与方可能存在故障或主动恶意行为（即所谓的拜占庭客户端）的环境中被破坏。单个客户端提交一个精心构造的、任意大的或仅仅是无意义的更新，就能使全局模型严重偏离最优解，可能导致发散甚至引入隐藏后门。这种脆弱性需要专门设计聚合策略来抵御此类对抗行为。

拜占庭容错聚合的核心思想借鉴了鲁棒统计学。这些方法不使用对异常值敏感的算术平均值，而是采用受极端值影响较小的估计器。目标是识别并降低权重 (weight)或丢弃与大多数更新相比显得异常的更新，假设拜占庭客户端是少数，并且其更新与诚实客户端提交的更新明显不同。

下面我们来考察几种聚合方法：

坐标级中位数

平均值最简单的替代方案可能是坐标级中位数。我们不按分量对更新向量 (vector)进行平均，而是计算所有接收到的客户端更新中每个坐标的中位数。

假设我们接收到 $n$ 个更新向量 $v_1, v_2, ..., v_n$，每个维度为 $d$。聚合更新 $v_{agg}$ 的计算方式是，其第 $j$ 个分量（$v_{agg, j}$）是所有接收到的更新的第 $j$ 个分量的中位数：

$v_{agg, j} = \text{中位数}(v_{1,j}, v_{2,j}, ..., v_{n,j})$

对于每个维度 $j = 1, ..., d$。

这种方法计算效率高，明显快于几何中位数等更复杂的方法。尽管其理论保障有时较弱，但在实践中通常表现良好，并且在某些假设下可以容忍接近 50% 的拜占庭客户端比例。它的主要缺点是它独立处理每个维度，可能漏掉以关联方式跨多个维度构造的恶意更新。

截断均值

截断均值提供了另一种计算上合理的方法。它的作用是丢弃一部分最可能是异常值的更新，然后计算剩余更新的平均值。

具体来说，对于每个坐标 $j$，服务器对值 $v_{1,j}, v_{2,j}, ..., v_{n,j}$ 进行排序。假设预期的拜占庭客户端比例上限为 $\beta$，服务器会移除该坐标的 $\beta n$ 个最小值和 $\beta n$ 个最大值。聚合更新 $v_{agg, j}$ 的第 $j$ 个分量是剩余 $(1 - 2\beta)n$ 个值的平均值。

截断均值的效果取决于正确估计 $\beta$。如果 $\beta$ 设置过低，聚合仍可能受到拜占庭影响。如果设置过高，诚实客户端的更新可能被不必要地丢弃，可能减缓收敛速度或降低模型质量，尤其是在高度异构（非独立同分布）的环境中，诚实更新可能自然存在较大差异。

Krum 和 Multi-Krum

Krum 采用了一种不同的方法，通过选择一个被认为是“最具代表性”或“最中心”的单个更新。它假设诚实客户端的更新在参数 (parameter)空间中彼此相对接近，而拜占庭更新将是异常值。

对于每个接收到的更新 $v_i$，Krum 根据到其 $k$ 个最近邻居（在其他更新中）的欧几里得距离平方和计算一个分数。令 $N_k(i)$ 为与 $v_i$ 最接近的 $k$ 个更新的索引集（不包括 $v_i$ 本身）。$v_i$ 的分数为：

$score(i) = \sum_{l \in N_k(i)} ||v_i - v_l||_2^2$

服务器选择分数最小的单个更新 $v_{i^*}$ 作为本轮的聚合结果：

$i^* = \arg \min_i score(i)$ $v_{agg} = v_{i^*}$

参数 $k$ 必须根据假设的拜占庭客户端最大数量 $f$ 仔细选择，通常 $k = n - f - 2$，以确保最佳诚实客户端的邻域计算排除所有拜占庭客户端。

如果拜占庭客户端数量小于 $(n - k - 1) / 2$，Krum 保证容错性。然而，仅选择一个更新可能导致收敛缓慢或不稳定。Multi-Krum 通过选择 Krum 分数最低的 $m$ 个更新（通常 $m$ 较小，例如 $m=5$ 或 $m=10$）并对其进行平均来解决此问题。这通常在容错性和稳定性之间提供更好的平衡。

Krum 示意图。诚实更新（蓝色）聚集在一起，而拜占庭更新（红色）是异常值。Krum 识别出一个更新（例如，实心蓝色圆圈），其最近邻居距离很近，表明它可能是诚实的。

其他聚合器（几何中位数，Bulyan）

• 几何中位数： 找到一个点 $w$，使其到所有客户端更新 $v_i$ 的欧几里得距离之和最小： $w = \arg \min_w \sum_{i=1}^n ||w - v_i||_2$。它具有强大的理论容错性（可以容忍高达 50% 的拜占庭客户端），但计算成本高昂，因为它需要一个迭代优化过程。
• Bulyan： 一种更复杂的方法，通过迭代过程将类 Krum 选择阶段与坐标级中位数或截断均值过滤相结合。它实现了高理论容错性，但伴随较大的计算开销。

实际考量与权衡

选择聚合器涉及多方面的权衡：

1. 容错性与计算开销： 坐标级中位数和截断均值等方法的计算成本低于 Krum、几何中位数或 Bulyan，但可能提供较弱的理论保障或需要仔细的参数 (parameter)调整（例如截断均值中的 $\beta$）。
2. 假设： 大多数方法假设拜占庭更新是异常值。复杂的攻击者可能试图构造位于诚实更新集群内部的更新，可能逃避 Krum 等基于距离的方法的检测。
3. 对收敛的影响： 与 FedAvg 相比，聚合器在 没有攻击存在时 有时会减缓收敛。这是因为它们可能丢弃有效更新，尤其是在非独立同分布（Non-IID）场景中，诚实客户端更新自然会表现出高方差。
4. 参数调整： Krum 需要根据攻击者数量 $f$ 的估计值设置 $k$。截断均值需要设置截断比例 $\beta$。不正确的估计可能降低性能或容错性。

实践中，选择在很大程度上取决于具体应用、预期的威胁级别、服务器可用的计算资源以及客户端间的统计异构程度。如果拜占庭攻击是一个重要的考量，坐标级中位数、截断均值或 Multi-Krum 等方法的计算开销通常是值得的投入，相对于标准 FedAvg 可能的失败。这些高级聚合规则是构建可靠联邦学习系统在潜在对抗环境中的必要工具。