第二章 FedAvg 算法 (Federated Averaging Algorithm)

一、导读

2.1 本章学习目标

深入理解 FedAvg 算法的核心思想、数学原理和完整工作流程

掌握 FedAvg 与 FedSGD 算法的区别及各自的适用条件

理解 FedAvg 中本地训练（Local Training）与模型聚合（Model Aggregation）的数学表达

分析 FedAvg 在 IID 和 Non-IID 数据分布下的收敛特性

掌握 FedAvg 的关键超参数（本地训练轮数 E、批大小 B、客户端比例 C）对算法性能的影响

了解 FedAvg 的变体算法及其改进策略

能够在实际场景中实现和调优 FedAvg 算法

理解 FedAvg 算法的局限性及后续改进方向

2.2 为什么本章如此重要

FedAvg（Federated Averaging）算法是联邦学习领域最具影响力的基础算法，由 McMahan 等人在 2017 年的经典论文 "Communication-Efficient Learning of Deep Networks from Decentralized Data" 中提出。该算法的提出标志着联邦学习从理论概念走向了可实现的工程实践，为整个联邦学习研究领域奠定了算法基础。

FedAvg 的核心创新在于引入了"多轮本地训练"的思想。与简单的联邦梯度下降（FedSGD）不同，FedAvg 允许每个客户端在上传模型更新之前，使用本地数据进行多个 epoch 的训练。这一设计极大地减少了通信轮次，使得联邦学习在实际部署中变得可行。在移动设备等带宽受限的场景中，通信开销往往是主要的性能瓶颈，FedAvg 通过以计算换通信的策略，有效地解决了这一问题。

FedAvg 算法的重要性还体现在它建立的算法框架上。后续大量的联邦学习研究工作，无论是针对 Non-IID 数据的改进（如 FedProx、SCAFFOLD），还是针对系统异构性的优化（如 FedNova、FedMA），都是以 FedAvg 为基础进行扩展和改进的。深入理解 FedAvg 的数学原理、收敛性分析和实现细节，是掌握联邦学习算法设计的必备基础。

从工程实践的角度看，FedAvg 是目前应用最广泛的联邦学习算法。无论是开源框架（如 Flower、FedML、LEAF）还是工业部署（如 Google 的输入法模型训练），FedAvg 及其变体都是默认的基础算法。掌握 FedAvg 的实现细节和调优技巧，对于联邦学习的工程实践具有重要的指导意义。

2.3 核心问题引导

FedAvg 算法是如何通过本地训练减少通信开销的？其背后的直觉是什么？

FedAvg 与 FedSGD 在算法流程和收敛性上有什么本质区别？

在 Non-IID 数据分布下，FedAvg 为什么会出现收敛困难？其数学原因是什么？

本地训练轮数 E 的增加会带来哪些正面和负面影响？如何选择合适的 E 值？

FedAvg 的客户端采样策略对算法收敛有什么影响？

如何从理论上分析 FedAvg 的收敛速率？关键假设条件有哪些？

FedAvg 在实际部署中面临哪些工程挑战？如何优化？

二、核心概念详解

2.1 FedAvg 算法的数学形式化

FedAvg 算法的目标是在不共享原始数据的前提下，最小化以下全局目标函数：

全局目标函数定义为各客户端本地目标函数的加权平均：

$$f(w) = \sum_{k=1}^{K} \frac{n_k}{n} F_k(w)$$

其中，$K$ 是参与客户端的总数，$n_k$ 是第 $k$ 个客户端的本地数据量，$n = \sum_{k=1}^{K} n_k$ 是所有客户端的数据总量，$F_k(w)$ 是第 $k$ 个客户端的本地目标函数，通常定义为：

$$F_k(w) = \frac{1}{n_k} \sum_{i=1}^{n_k} \ell_k(w; x_i^k, y_i^k)$$

这里 $\ell_k(w; x_i^k, y_i^k)$ 是第 $k$ 个客户端上第 $i$ 个样本的损失函数。

FedAvg 算法的完整流程如下：在每一轮通信 $t$ 中，服务器首先将当前全局模型 $w_t$ 发送给选定的客户端子集 $S_t$（$|S_t| = C \cdot K$，其中 $C$ 是客户端采样比例）。每个被选中的客户端 $k$ 使用本地数据对模型进行 $E$ 轮（epoch）的本地 SGD 训练，每轮训练使用批大小为 $B$ 的小批量梯度下降。训练完成后，客户端 $k$ 将更新后的模型 $w_{t+1}^k$ 返回服务器。服务器对所有收到的模型进行加权平均，得到新的全局模型：

$$w_{t+1} = \sum_{k \in S_t} \frac{n_k}{n_{S_t}} w_{t+1}^k$$

其中 $n_{S_t} = \sum_{k \in S_t} n_k$。

这个加权平均操作是 FedAvg 名称的由来，也是算法的核心聚合步骤。权重的选择（基于数据量的比例加权）确保了每个数据样本对全局模型的贡献是均等的，避免了数据量大的客户端对全局模型产生过大的影响。

2.2 FedSGD 与 FedAvg 的对比分析

FedSGD（Federated Stochastic Gradient Descent）是 FedAvg 的特殊情况，即本地训练轮数 $E = 1$ 且批大小 $B$ 等于本地数据量 $n_k$ 的情况。在 FedSGD 中，每个客户端在每轮通信中只计算一次完整梯度（Full Gradient），然后将梯度上传至服务器进行聚合。

两者的核心区别在于本地计算的深度。FedSGD 每轮通信中每个客户端只进行一次梯度计算，需要更多的通信轮次才能收敛，但每轮的通信内容（梯度）相对较小且确定性强。FedAvg 允许客户端进行多轮本地训练，显著减少了通信轮次，但每轮传输的是完整的模型参数而非梯度，且由于本地训练的深度不同，模型更新的方向和幅度更加不确定。

从通信效率的角度看，FedAvg 在大多数实际场景中优于 FedSGD。实验结果表明，在 IID 数据分布下，FedAvg 可以将通信轮次减少 10 到 100 倍。然而在 Non-IID 数据分布下，过多的本地训练可能导致客户端模型过度偏离全局模型，反而降低收敛速度。

从理论分析的角度看，FedSGD 的收敛性分析相对简单，可以借鉴传统 SGD 的收敛性理论。FedAvg 的理论分析则更加复杂，需要考虑本地训练步数、数据异构性、客户端采样等多个因素的耦合效应。McMahan 等人在原始论文中给出了 FedAvg 在 IID 情况下的收敛性分析，但 Non-IID 情况下的理论保证直到后续工作才逐步完善。

2.3 FedAvg 的收敛性分析

FedAvg 的收敛性分析是理解算法行为和指导参数调优的重要理论基础。原始论文在若干假设条件下，给出了 FedAvg 在强凸（Strongly Convex）和非强凸目标函数下的收敛速率。

关键假设条件包括：

假设一，Lipschitz 平滑性：每个客户端的本地目标函数 $F_k$ 是 $L$-Lipschitz 平滑的，即梯度满足 $\|\nabla F_k(w) - \nabla F_k(v)\| \leq L \|w - v\|$。

假设二，强凸性（可选）：全局目标函数 $f$ 是 $\mu$-强凸的。

假设三，有界梯度和方差：每个客户端的随机梯度满足有界方差 $\mathbb{E}[\|g_k(w; \xi) - \nabla F_k(w)\|^2] \leq \sigma_k^2$ 和有界二阶矩 $\mathbb{E}[\|g_k(w; \xi)\|^2] \leq G_k^2$。

假设四，数据异构性度量：定义 $\Gamma^2 = \mathbb{E}[\|\nabla F_k(w^) - \nabla f(w^)\|^2]$ 来度量数据分布的异构程度。当数据为 IID 时，$\Gamma = 0$。

在这些假设下，对于强凸情况，FedAvg 的收敛速率为 $O(\frac{1}{T})$，其中 $T$ 是总的通信轮次。但收敛界中包含了与 $\Gamma$（数据异构性）和 $E$（本地训练轮数）相关的项，表明数据异构性越大或本地训练轮数越多，收敛误差可能越大。

这一理论结果揭示了 FedAvg 的一个核心矛盾：增加本地训练轮数 $E$ 可以减少通信开销，但会增大由数据异构性引起的收敛误差。这一矛盾在 Non-IID 场景下尤为突出，成为后续许多改进算法（如 FedProx、SCAFFOLD）的出发点。

2.4 关键超参数的影响与调优

FedAvg 算法的性能对超参数的选择非常敏感。主要超参数包括客户端采样比例 $C$、本地训练轮数 $E$、批大小 $B$ 和学习率 $\eta$。

客户端采样比例 $C$ 控制每轮参与训练的客户端数量。较大的 $C$ 值意味着更多的客户端参与训练，每轮聚合的模型更新更具代表性，有助于加速收敛。然而，较大的 $C$ 值也增加了每轮的通信开销和服务器计算负担。在实践中，$C$ 通常设置为 0.01 到 0.1 之间，即每轮选择 1% 到 10% 的客户端参与训练。

本地训练轮数 $E$ 是最关键的超参数之一。较小的 $E$ 值（如 $E = 1$，即 FedSGD）需要更多的通信轮次但收敛行为更稳定。较大的 $E$ 值减少了通信轮次，但可能导致客户端模型过度拟合本地数据，尤其在 Non-IID 场景下。实验表明，$E$ 在 1 到 20 之间通常能取得较好的效果，具体最优值取决于数据分布的异构程度。

批大小 $B$ 影响本地训练的梯度估计质量。较小的 $B$ 引入更多的随机性，有助于跳出局部最优，但梯度估计的方差更大。较大的 $B$ 提供更准确的梯度估计，但可能导致过拟合。在联邦学习中，$B$ 的选择还需要考虑客户端的计算资源限制。

学习率 $\eta$ 的调度策略对收敛性有重要影响。常用的策略包括固定学习率、指数衰减和自适应学习率。在联邦学习中，由于每轮通信后模型会被聚合更新，学习率的设置需要同时考虑本地训练和全局聚合的影响。

2.5 FedAvg 的系统实现与工程优化

在实际工程部署中，FedAvg 的实现需要考虑诸多实际因素。

客户端掉队（Straggler）问题是工程实现中的主要挑战之一。由于客户端设备的异构性（不同的计算能力、网络条件、可用时间），部分客户端可能无法在预期时间内完成本地训练并返回结果。同步 FedAvg 需要等待所有被选中的客户端完成训练，掉队者的存在会严重拖慢整体训练速度。解决方案包括：异步聚合（Asynchronous Aggregation），允许服务器在收到部分客户端的更新后即进行聚合；超时机制（Timeout），设定等待时间上限，对超时的客户端进行忽略或使用其上一次的结果。

模型初始化与恢复也是重要的工程问题。在实际部署中，联邦学习过程可能因为各种原因中断（如服务器维护、网络故障），系统需要能够从最近的状态恢复训练。此外，全局模型的初始化策略（如使用预训练模型）对最终性能也有显著影响。

客户端选择策略对训练效果有重要影响。随机采样是最基本的策略，但在实际场景中可能需要考虑客户端的可用性、数据量、计算能力等因素。基于奖励的客户端选择机制可以激励更多客户端参与训练。

三、深入分析与讨论

3.1 FedAvg 在 Non-IID 场景下的性能退化分析

FedAvg 在 Non-IID 数据分布下的性能退化是一个重要的研究问题。实验研究表明，当数据从 IID 分布逐渐变为高度 Non-IID 分布时，FedAvg 的测试准确率可能下降 10% 到 40% 不等，具体取决于任务的复杂度和 Non-IID 的程度。

性能退化的根本原因可以从优化和统计两个角度理解。从优化角度看，当各客户端的数据分布差异较大时，各客户端的本地最优解也会存在较大差异。FedAvg 的加权平均聚合操作试图找到一个对所有客户端都"公平"的全局解，但在高度 Non-IID 的情况下，这样的全局解可能并不存在或质量较差。更具体地，当本地训练轮数 $E$ 较大时，每个客户端的模型会向其本地最优解靠近，而这些本地最优解之间的差异使得聚合后的全局模型处于一个不利的优化位置。

从统计角度看，Non-IID 数据分布意味着全局模型需要拟合一个更加复杂的分布。在集中式训练中，所有数据混合在一起，模型可以自然地学习到全局的数据分布。而在联邦学习中，每个客户端只能看到自己局部的数据分布，模型聚合后的全局表示可能无法充分捕捉数据的整体结构。

这一分析直接推动了后续一系列改进算法的发展，如 FedProx 通过添加近端项（Proximal Term）限制本地模型过度偏离全局模型，SCAFFOLD 通过使用控制变量（Control Variate）修正梯度漂移（Gradient Drift），FedNova 通过归一化本地更新来消除不同本地训练步数的影响。

3.2 FedAvg 的变体与改进算法

针对 FedAvg 的局限性，研究者提出了多种变体和改进算法。这些改进可以从不同的维度进行分类。

针对 Non-IID 数据分布的改进：FedProx 在本地目标函数中添加了近端项 $\frac{\mu}{2}\|w - w_t\|^2$，限制本地模型不偏离全局模型太远。理论分析表明，这一简单的修改可以显著改善 Non-IID 场景下的收敛性。SCAFFOLD 使用控制变量来修正每个客户端的梯度更新方向，消除由数据异构性引起的梯度漂移。FedNova 通过归一化本地更新向量，使得不同本地训练步数的客户端更新具有可比性。

针对通信效率的改进：FedPAQ（Periodic Averaging and Quantization）结合了周期性平均和梯度量化技术，进一步减少通信开销。QFedQ（Quantized Federated Learning）通过梯度压缩和量化来减少每轮通信的数据量。

针对隐私保护的改进：DP-FedAvg 在模型聚合过程中引入差分隐私机制，通过裁剪和加噪来保护单个客户端的隐私。安全聚合（Secure Aggregation）确保服务器只能获得聚合后的模型更新，而无法看到单个客户端的贡献。

针对系统异构性的改进：FedAsync 采用异步聚合策略，允许服务器在收到部分客户端的更新后即进行聚合。FedBuff 结合了同步和异步的优点，使用缓冲区机制来平衡训练效率和模型质量。

3.3 FedAvg 的理论下界与最优性

一个自然的问题是：FedAvg 是否是联邦学习的最优算法？是否存在理论上更优的聚合策略？

从通信复杂度的角度看，已有研究证明了联邦学习在某些设置下的通信复杂度下界。对于凸优化问题，在 IID 数据分布下，FedAvg 的通信复杂度在量级上是最优的。但在 Non-IID 设置下，FedAvg 并非理论最优，存在改进空间。

从统计最优性的角度看，如果目标是找到一个使全局损失函数最小化的模型，那么在 Non-IID 设置下，简单的加权平均聚合并非最优策略。最优的聚合策略应该考虑到数据分布的异构性，对不同客户端的更新进行差异化处理。这引出了个性化联邦学习（Personalized Federated Learning）的研究方向，其目标不是找到一个统一的全局模型，而是为每个客户端找到一个适合其本地数据分布的个性化模型。

四、实践案例

4.1 基于 Flower 框架的 FedAvg 实现

Flower 是一个流行的开源联邦学习框架，提供了 FedAvg 的标准实现。以下分析一个使用 Flower 实现 FedAvg 的典型流程。

在 Flower 框架中，联邦学习系统由 Strategy（策略）和 Client（客户端）两个核心组件构成。Strategy 定义了服务器端的聚合逻辑，Client 定义了客户端的本地训练逻辑。FedAvg 的实现对应于 FedAvg Strategy 和相应的 Client 实现。

在训练流程中，服务器首先初始化全局模型，然后在每一轮通信中执行以下步骤：第一，使用 configure_fit 方法为选定的客户端配置训练参数（如全局模型权重、本地训练轮数、学习率等）；第二，被选中的客户端使用本地数据进行训练，返回训练结果；第三，服务器使用 aggregate_fit 方法对收到的模型更新进行加权平均聚合；第四，重复上述过程直到达到预定的通信轮次或收敛条件。

在实践中，需要注意的关键点包括：模型权重的序列化与反序列化（Flower 使用 NumPy 数组表示模型参数）、客户端选择的策略配置、训练结果的异常处理（如客户端返回空结果的情况）以及训练过程的日志记录和监控。

4.2 FedAvg 在图像分类任务中的实验分析

以 CIFAR-10 图像分类任务为例，分析 FedAvg 在不同实验设置下的性能表现。

实验设置：使用 100 个模拟客户端，每个客户端拥有 CIFAR-10 的一个子集作为本地数据。全局模型使用标准的 CNN 架构（包含 2 个卷积层和 2 个全连接层）。通过 Dirichlet 分布（参数 $\alpha$）控制数据的 Non-IID 程度，$\alpha$ 越小表示数据分布越不均匀。

实验结果表明：在 IID 设置（$\alpha \to \infty$）下，FedAvg 可以达到与集中式训练相近的测试准确率（约 72%）。当 $\alpha$ 减小到 0.1 时（高度 Non-IID），测试准确率下降到约 55%。增加本地训练轮数 $E$ 在 IID 设置下可以加速收敛，但在 Non-IID 设置下可能导致性能下降。客户端采样比例 $C$ 从 0.05 增加到 0.2 可以带来一定的性能提升，但提升幅度随 $C$ 的增大而递减。

这些实验结果验证了理论分析的结论：Non-IID 数据分布是 FedAvg 性能退化的主要原因，而本地训练轮数的选择需要在通信效率和收敛质量之间进行权衡。

五、常见误区与注意事项

5.1 误区一：FedAvg 中的加权平均是最优聚合策略

加权平均聚合是 FedAvg 的核心操作，但它并非在所有情况下都是最优的。在 Non-IID 设置下，不同客户端的模型更新可能包含互补的信息，简单的加权平均可能丢失这些有价值的信息。更复杂的聚合策略（如基于注意力机制的聚合、基于中位数的鲁棒聚合等）在某些场景下可能表现更好。

5.2 误区二：增加本地训练轮数总是有益的

增加本地训练轮数 $E$ 虽然可以减少通信开销，但并不总是带来性能提升。在 Non-IID 设置下，过多的本地训练会导致客户端模型过度拟合本地数据分布，偏离全局模型，反而降低聚合后的全局模型质量。实践中，$E$ 的选择需要根据数据分布的异构程度进行调优。

5.3 误区三：FedAvg 对所有客户端公平

FedAvg 的目标是最小化全局损失函数的加权平均，这并不意味着对所有客户端公平。在 Non-IID 设置下，全局模型可能对某些客户端的数据分布表现良好，而对另一些客户端表现较差。如果应用需要保证每个客户端的模型质量，需要考虑个性化联邦学习或公平性约束。

5.4 注意事项：学习率的选择

FedAvg 中的学习率选择需要特别谨慎。由于每轮通信后模型会被聚合更新，学习率的设置需要同时考虑本地训练和全局聚合的影响。过大的学习率可能导致模型在聚合后出现振荡，过小的学习率则会导致收敛过慢。建议使用学习率衰减策略，并在训练初期使用较小的学习率进行预热。

5.5 注意事项：客户端数量对算法的影响

客户端数量 $K$ 对 FedAvg 的性能有重要影响。客户端数量过少时，每轮聚合的模型更新可能不具有代表性，导致全局模型质量不稳定。客户端数量过多时，每轮需要选择的客户端子集大小也需要相应增加，否则每个客户端对全局模型的贡献会被稀释。实践中，需要根据任务复杂度和数据分布特点选择合适的客户端数量。

六、本章小结

本章详细分析了 FedAvg 算法的数学原理、收敛性、超参数影响和工程实现。FedAvg 通过引入多轮本地训练机制，以计算换通信，显著减少了联邦学习中的通信开销。我们从数学形式化出发，理解了全局目标函数的定义和加权平均聚合的原理，对比了 FedAvg 与 FedSGD 的区别，分析了收敛性条件和 Non-IID 数据分布下的性能退化原因。通过实验案例，我们验证了理论分析的结论，了解了超参数调优的实践经验。FedAvg 虽然存在 Non-IID 场景下的性能退化等局限性，但作为联邦学习的基础算法，其思想和框架为后续改进算法的发展提供了坚实的基础。下一章我们将探讨如何通过安全聚合技术保护联邦学习中的模型更新安全。

七、思考题与练习

推导 FedAvg 在单轮通信中的计算复杂度，并分析其与客户端数量 $K$、本地训练轮数 $E$、批大小 $B$ 的关系。

设计一个实验，验证本地训练轮数 $E$ 对 FedAvg 在 Non-IID 数据分布下性能的影响。描述实验设置、评估指标和预期结果。

假设一个联邦学习系统中有 10 个客户端，每个客户端的数据量分别为 1000, 2000, 500, 3000, 1500, 800, 2500, 1200, 1800, 900。请计算在 FedAvg 聚合时每个客户端的权重，并分析这种权重分配方式的合理性。

比较 FedAvg 与分布式 SGD（D-SGD）在通信效率、收敛性和适用场景方面的异同。

实现一个 FedAvg 的变体，将加权平均聚合替换为中位数聚合（Coordinate-wise Median），分析其在存在恶意客户端场景下的鲁棒性。

分析 FedAvg 在以下场景中的适用性：（a）各客户端的计算能力差异很大；（b）网络带宽极低且不稳定；（c）数据分布极度不均匀。针对每个场景提出改进建议。

从信息论的角度分析，FedAvg 的加权平均聚合操作在信息保留和信息损失方面的特性。是否存在信息论意义下的最优聚合策略？

调研并总结 FedAvg 在至少三个不同应用领域（如自然语言处理、推荐系统、语音识别）中的具体应用案例，分析其技术挑战和解决方案。