图 1. FL 使人们能够通过中央服务器和客户端之间的模型参数迭代通信，在私有客户端数据上训练机器学习模型[2]

本文是第 29 届国际高性能并行与分布式计算会议（HPDC '20）中的一篇文章。作者首先量化分析了客户端数据和资源异质性如何影响经典 FL 的训练性能和模型准确度。然后，作者提出了 TiFL（Tier-based Federated Learning），一个基于层级（Tier）的联邦学习系统。TiFL 的关键思想是自适应地选择每轮训练时间相近的客户端，这样就可以在不影响模型准确度的情况下解决数据异质性问题。

据此，C 中至少有一个客户端来自τ_m 的概率可以表述为：

由于具有如下约束：

在真实场景中，每一轮都会有大量的客户端被选中，这使得 | K | 非常大，可得 Pr_s≈1。因此，每轮从最慢层级中至少选择一个客户端的概率是相当高的。因此，随机选择客户端的策略可能会导致全局模型训练性能缓慢 。

图 2. (a)每轮训练时间 (对数比例) 与资源和数据量异质性；(b)每个客户端 (No-IID) 不同类数下的准确性

图 3. TiFL 整体架构

1.3 实验分析

表 1. 调度策略详情

图 4. 资源异质性（列 1）和数据量异质性（列 2）的 Cifar10 上不同选择策略的比较结果

图 5. 在 No-IID 异质性（Class）和固定资源水平不同的情况下，Cifar10 上不同选择策略的比较结果

图 6. Cifar10 上不同选择策略的对比结果，包括数据量异质性（Amount）、No-IID 异质性（Class）、资源和数据异质性（Combine）

本文是一篇 ArXiv 预印文章。在经典 FL 问题中，客户端在本地进行训练并将学习到的模型发送给中央服务器。为实现本地模型的聚合需要在客户端和中央服务器之间频繁地进行大量的信息沟通，因而造成了较大的通信负荷。本文的关注点是“高效通信的联邦学习（Communication-Efficient Federated Learning）”。作者提出了一种简单、高效的在通信约束环境下更新全局模型的方法：从有信息更新的客户端中收集模型，并估计没有进行通信的客户端中的局部更新。

Ornstein-Uhlenbeck 过程 (OU) 是一个静止的高斯 - 马尔科夫过程（a stationary Gauss-Markov process），随着时间的推移，它向其平均函数漂移。与 Wiener 过程的漂移是恒定的不同，OU 过程的漂移取决于其当前实现与平均值的距离。形式上，OU 过程{x_t}_t 可以用随机微分方程来描述：

其中，W_t 表示标准 Wiener 过程。上式描述了 OU 过程所限定的随速度漂移的过程，并且具有随方差的布朗运动驱动的波动。

对于 OU 过程，则可以有：

为了建立与 FL 的联系，作者提出在 FL 过程的每一轮 t 中，客户端 k 观察到一个终止于θ_t^(k)的 OU 过程的部分样本路径（即客户端在局部训练期间记录其权重的进展）。样本路径从本轮训练开始时中央服务器广播的θ_t 点（即模型权重）开始。确定本地更新 (由客户端 k) 与之前广播的模型之间的差异：

如果在通信阈值测试结果之后，客户端 k 决定不与中央服务器通信，中央服务器可能会估计客户端的更新量如下：

由于其中的参数λ和μ未知，将其改写为：

上式中的 a 和 b 可以根据之前中央服务器中聚合得到的θ_0,...θ_t 得到。完整过程如 Algorithm 3：

由上述分析可知，本文方法是通过与通信阈值的比对实现的通信减少。由于随着训练的进行梯度范数预计会不断减小，当我们接近最小值时，一个固定的通信阈值可能会对学习过程产生不利影响。本文提出一种根据参与客户端的更新幅度确定的动态通信阈值。在 t=0 时，客户端收到的初始通信阈值τ_0=0，意味着各个客户端在第一轮传输。在接下来的几轮中，客户端要么传输他们的更新和他们更新的范数 m_t^(k) ，要么传输一个 NACK 消息（Negative Acknowledgement）以及他们更新的范数。在 t 轮结束时，中央服务器估计更新范数的平均值：m_t，它们的标准差：s_t，并计算下一轮的通信阈值：

在第 t 轮开始时选择 N 个客户端，中央服务器广播模型参数θ_t，被选择的客户端在本地执行大小为 B 的 mini-batch 的 SGD，时间为 E 个 epochs。在对本地模型更新的范数与通信阈值进行比较后，每个客户端局部决定是否通信其更新，并分别传输模型更新θ_t+1^k 或负确认消息。在这两种情况下，客户端都会发送其训练数据大小 n_k，以实现加权。每个客户端也会向服务器传送其更新的范数（只有一个浮点，32 位，与全模型相比）而不会传送实际的更新。最终第 k 个客户端参数为：

中央服务器在计算上的一种简单替代估计方法是重用上一轮客户端模型，或是直接忽略该客户端。最后，中央服务器更新模型如下：

图 7. FedAvg 在不同通信阈值下采用固定通信阈值通信策略的准确度。高通信阈值阻止了向精确模型收敛，因为所有客户端一旦更新小于通信阈值，就会停止传输

图 8. FedAvg 的每一轮通信与固定通信阈值通信策略的不同通信阈值。较小的通信阈值不能减少通信，而较大的通信阈值在训练过程中完全停止通信，从而导致生成坏的模型

图 9. 模型在合成逻辑回归、EMNIST 和 Shakespeare 上的准确度。OU 客户端抽样策略始终优于竞争方法

图 10. 训练期间各系统的累计通信量以发送的总 KB 数衡量

表 2. EMNIST 和 Shakespeare 数据库实验中通信缩减策略的准确性和通信成本

本文目前也是一篇 ArXiv 预印文章。本文提出了 Oort，一种通过引导参与者选择以提高联邦训练和测试的性能的方法。为了提高模型的 time-to-accuracy 性能，Oort 优先使用那些既拥有对提高模型准确度有较大作用的数据，又具备快速执行训练能力的客户端。为了使 FL 开发人员能够在模型测试中解释他们的结果，Oort 强制执行对参与者数据分布的要求，同时通过客户端选择来提高联邦测试的持续时间。

图 11. Oort 架构。FL 框架的驱动程序使用客户端库与 Oort 进行交互

其中，T 是开发者首选的每一轮的持续时间，t_i 是客户端 i 训练所需的时间。这样一来，那些可能是当前回合理想速度瓶颈的客户端的效用将受到开发者指定的因子α的惩罚，但我们不会奖励 non-straggler 客户端，因为他们的完成度不会影响一个轮次的持续时间。

基于上述客户端效用的定义，我们需要解决以下问题，以便在每轮训练中选择效用最高的参与者：

其中，f∈[0,1]，随着 f→1，Algorithm 1 会自然地优先处理公平性需求最大的客户端。

表 3. Time-to-accuracy 性能

图 12. time-to-accuracy 性能

图 13. Oort 可以限制所有目标的数据偏差。阴影表示给定 y 轴输入的 1000 次运行中 x 轴值的经验 [min,max] 范围

图 14. Oort 在 FL 测试中性能优于 MILP

本文是 IEEE INFOCOM 2020 中的一篇文章，聚焦的是 FL 环境中不同客户端设备中 Non-IID 数据对最终模型性能的影响。作者认为，现有的联邦学习方法并没有解决异构局部数据库带来的统计挑战。由于不同的用户有不同的设备使用模式，位于任何一个客户端设备上的数据样本和标签可能遵循不同的分布，无法代表全局数据分布。在存在 Non-IID 数据的情况下，联邦学习的模型准确度和达到收敛所需的通信轮数方面的性能都显著下降。随机选取的局部数据库可能无法反映全局视图中的真实数据分布，这就不可避免地给全局模型更新带来了偏差。此外，在 Non-IID 数据上局部训练的模型相互之间可能会存在显著差异。将这些不同的模型聚合在一起，就可能会出现收敛速度减速减慢或模型准确度大幅降低的问题。

设备 k 和 k’中的权重偏差可以表示为：

这意味着，即使局部模型以相同的初始权重ω_init 进行训练，根据下式及权重偏差，设备 k 和 k’上的数据分布差异之间也存在隐性联系：

基于上述分析，作者先让 100 台设备各自下载相同的初始全局权重（随机生成），并根据本地数据进行一个 epoch 的 SGD 以得到：ω_1^(k)，k=1,...,100。之后利用 K 中心 (K-Center) 聚类方法将 100 台设备聚类到 10 个组。在每一轮中，从每组中随机选取一台设备参与 FL 训练，结果每轮仍有 10 台设备同时参与。在 Non-IID 设置下，K 中心聚类算法需要 131 轮能够达到目标准确度，比经典的 FEDAVG 算法少 32 轮。该实验表明，通过在每一轮中仔细选择参与设备的集合，特别是在 Non-IID 数据环境下，有可能改进联邦学习的性能。

图 15. 在 Non-IID MNIST 数据上训练 CNN 模型

4.2.2 工作流

图 16 FAVOR 工作流

图 17. MNIST 数据库上 CNN 权重的 PCA 结果

最后，利用下式更新价值函数 Q(s_(t+1), a; θ_t)：

图 18. MNIST 库中不同级别 Non-IID 数据中 准确度 vs 通讯轮数 对比

图 19. FashionMNIST 库中不同级别 Non-IID 数据中 准确度 vs 通讯轮数 对比

图 20. CIFAR-10 库中不同级别 Non-IID 数据中 准确度 vs 通讯轮数 对比

图 21. MNIST 库中对 FL 训练的模型权重进行 PCA 分析，ω_1,ω_2,...,ω_5 分别表示第 1-5 轮的全局模型权重

本文是 2021 年最新的一篇 ArXiv 预印文章。本文聚焦联邦学习中的 Stragglers，即联邦学习的低计算能力或通信带宽的物联网设备，特别是异构优化问题。分布式网络中的 Stragglers 大大降低了现有同步 FL 方法的训练速度，因为现有方法训练速度实际上是由最慢的设备决定的。为了减轻 stragglers 的影响, 本文提出了一种新型的 FL 算法，即混合联邦学习（Hybrid Federated Learning，HFL)，以实现学习效率和效果的平衡 ------- 既考虑正常设备的同步学习，也考虑慢速设备（即 stragglers）的异步学习。

其中，(w_t)^i 表明第 t 轮收到的联合模型，η_t 为第 t 轮的学习效率，η_t 为中央服务器决定的，e 为局部训练 epoch 的指数，X^i 为训练样本。

图 22. 在存在 Stragglers 的情况下，使用同步内核和异步更新器的 HFL 的联邦学习过程

图 22 说明了在存在 Stragglers 的情况下，使用同步内核和异步更新器对所提出的 HFL 进行联合学习的过程，图中仅以一个正常设备和两个 Stragglers 为例。t=0 时，中央服务器初始化一个联合模型（joint model）并将其广播给所有设备。t=1 时，只有普通设备完成本地训练，并将其模型更新返回给中央服务器同步更新联合模型，由同步内核处理。t = 2 和 t = 3 时，当一个 Straggler 完成其局部训练时，异步更新器可以将延迟的模型更新纳入到联合模型中。显然，这种情况下主要的挑战是如何利用延迟的模型更新来完成当前联合模型的训练。上式所示的更新机制存在的问题是，在第 t 轮通信中，第 i 个 Stragglers 实际上会发回一个延迟的梯度。为了达到ω_t 的最优解，我们需要接近 "最新的" 梯度 ，这也是异步 SGD 优化领域的一个著名问题。此外，FL 网络中的 Stragglers 可能具有各种计算能力，这导致τ的分布极不平衡，因此，本文作者开发了一种自适应近似方案来解决这个问题。

作者使用 AD-SGD 方法来解决 FL 中 Stragglers 的延迟梯度和最佳梯度之间的差距问题。具体的，使用计算成本较低的外积梯度来逼近 Hessian 矩阵，在上文作者已经证明其与 Fisher 信息矩阵的计算是等价的。在 AD-SGD 的帮助下，当 FL 中存在 Stragglers 时能够实现学习效率和效果的平衡。

与现有的同步 FL 算法相比，在 HFL 中没有额外的通信轮次和额外的远程设备计算需求。特别是，近似成本主要来自于中央服务器上额外存储的几个以前的联合模型。不过，对前一个联合模型的备份并不违反 FL 网络的隐私设置。

图 23. 凸数据集上的实验结果

图 24. HFL 与现有方法在非凸数据库上的学习性能比较

本文是 CMU 研究人员在 2020 年发表的预印本文章。在异构环境中，通过优先选择本地模型损耗值（loss value）较高的客户端，可以急剧加速误差收敛从而提升通信效率，因此分析和理解有偏客户端选择策略非常重要。在我们分析的第二篇文章《Communication-efficient Federated Learning via Optimal Client Sampling》中就提出了根据客户端权重进行客户端选择的方法。不过这篇文章的作者认为该方案仅限于经验证明，没有严格分析选择偏差如何影响收敛速度。

其中，f(w,ξ)为样本ξ和参数向量 w 组成的复合损失函数。在联邦学习问题中，满足 F(w)最优化的 w * 和满足 F_k(w)最优化的 w*_k 可能区别很大。

其中，当 (t+1) mod τ ≠ 0 时，进行本地模型更新；当(t+1) mod τ = 0 时，进行全局模型更新，同时设备获得更新后的全局模型。根据客户端 k 的局部数据库 B_k 随机抽样得到的大小为 b 的 mini-batch ξ_k^(t) 的随机梯度为：

图 25. 有偏客户端选择示例

其中，Γ表示局部和全局目标函数的固有属性，与客户端选择策略无关。Γ越大意味着数据的异质性越高。如果Γ=0，则意味着局部最优值和全局最优值是一致的，不存在由于客户端选择策略而导致的解偏差。接下来，作者定义了另一个度量方法称为选择偏斜(Selction skew)，它反映了客户端选择策略对局部 - 全局目标差距的影响：

ρ反映了客户选择策略π的倾斜性（skew）。ρ(S(π,w),w’)是全局模型 w 和 w’的函数，在训练过程中发生变化。作者定义与 w 和 w’无关的两个度量标准如下，这两个标准能够表征收敛性分析的保守误差范围：

由作者的分析可知，一个优先选择较大 F_k(w)-F*_k 客户端的选择策略π，将会导致更大的ρ并产生更快的收敛速度。因此，客户端选择策略可以简单确定为选择局部损失最大的客户端 F_k(w)。然而，较大的选择偏斜可能导致较大的不消失误差项。这种简单的选择策略还有一个缺点是：要找到当前的局部损失 F_k(w)，需要将当前的全局模型发送给所有 K 个客户端，让他们评估 F_k 后再发回至中央服务器。这种额外的通信和计算成本可能会非常高，因为客户端 K 的数量通常非常大，而这些客户端的通信和计算能力有限。

图 26. 二次优化实验中π_pow-d 的性能

图 27. 合成数据库上逻辑回归的全局损失

图 28. 在 FMNIST 数据库上不同 d 值情况下不同采样策略的测试准确度和训练损失，K=100，C=0.03

图 29. 不同抽样策略的测试准确度和训练损失

阅读原文

*以上内容转载自澎湃-湃客，数码魅族对内容或做细微删改，不代表本网站赞同其观点和对其真实性负责。