异步联邦论文学习--2_异步联邦学习

标题：SAFA: A Semi-Asynchronous Protocol for Fast
Federated Learning With Low Overhead

DOI:10.1109/TC.2020.2994391

cite：Wu W, He L, Lin W, et al. SAFA: A semi-asynchronous protocol for fast federated learning with low overhead[J]. IEEE Transactions on Computers, 2020, 70(5): 655-668.

背景引言总结：

出于隐私考虑，分布式学习中发展出FL。

同步FL的限制

        1） 有效参与者的不可靠部分：在每一轮中，服务器随机选择一部分客户端进行本地培训，并期望他们提交本地训练结果。然而，鉴于终端设备的不可靠性质，提交其结果的客户端数量非常不确定；

        2） 低轮效率：为了在每轮结束时汇总本地结果，FedAvg必须等待所有选定的客户端完成，其中可能有掉队的客户端，而崩溃的客户端可能永远不会响应。因此，全局学习进度被暂停，直到达到超时阈值；

        3） 客户利用率低：通过随机选择，许多有能力的客户即使准备好并愿意参加培训，也可能闲置；

        4） 进度浪费：所选客户端可能无法及时完成本地培训，所取得的进度可能会被浪费，因为客户端将被迫用全局模型覆盖其本地模型

论文贡献总结：

        1）考虑到终端设备的不可靠性和异构性，提出了一种半异步联合平均（SAFA）协议，以减轻老化，提高效率，更好地利用掉队者取得的进展。

        2）引入了一个简单的超参数，即滞后容忍，来灵活地控制SAFA协议的行为。我们还通过观察滞后容忍度如何影响同步率和版本方差等关键指标，实证分析了滞后容忍度对SAFA的影响。

        3）在从微小到相对大规模的边缘环境的多个FL设置中，对几个典型的机器学习任务进行了广泛的实验来评估SAFA。SAFA是根据几个重要指标进行评估的，如模型准确性、回合效率和通信成本。

 系统模型

        符号列表：

                

优化目标:

PS：这里文章中提到所采用的目标函数与我上篇论文所总结的论文里的目标函数不同，上篇论文目标函数定义为平均损失的平均值（在局部分区上），这在局部分区级别是公平的，但在样本级别则不然，因为本地部分区中的数据样本在其目标函数中具有更大的权重。（question 1）

Semi-Asynchronous Federated Averaging(SAFA)协议:

        SAFA由三个操作组成：滞后容忍模型分布、训练后客户端选择和判别聚合。SAFA驱动的典型FL过程如图所示。

 Lag-Tolerant Model Distribution:

1、在一轮本地培训开始之前，服务器会根据当前版本将所有客户端分为三种状态（或类别）：最新、不推荐和可容忍，定义如下。

        

        up-to-date clinets：已完成上一轮本地训练（并成功提交模型）的客户在本轮培训开始时被视为最新客户。

        deprecated clients：仍然将本地训练建立在与全局模型的版本相比过于陈旧的模型上的客户端。

        tolerable clients：那些不以最新的全局模型为基础进行本地培训的客户，但他们所基于的模型版本也不太旧。这是一个介于最新和不推荐之间的状态。

SAFA只要求最新和不推荐使用的客户端与服务器同步（防止模型分支和防止模型受到过时模型的严重影响），而允许可容忍的客户端与服务器保持异步。这就是为什么SAFA被称为半异步分布式训练方案的原因。

2、在设备上完成一轮本地训练后，客户将根据SAFA中的客户选择结果被标记为已挑选、未被挑选或崩溃，这是一个训练后的过程。

        picked clients：在本轮中本地训练结果被选择用于以下聚合步骤的客户端。

        undrafted clients:  本地训练结果未被选择但仍被服务器缓存以供将来使用的客户端。
        crashed clients:  未能完成一轮本地培训的客户(存在崩溃概率，即以一定的概率随机掉线)

3、滞后容忍分布原则可以公式化如下

表示在第t轮开始时的最新全局模型参数（即来自上一轮的聚合结果），并且表示客户端k的局部模型的参数；代表滞后容限，这是SAFA中唯一的超参数。

注意：参数滞后容忍度在某些方面控制着通信开销和联邦优化收敛速度之间的权衡。

Client Selection

1、定义了一个称为有效更新率（EUR）的指标，以衡量从本地（即所有客户端）到云（即中央服务器）的有效更新比例：

        简单地增加pick分数可能会在FL环境中带来问题(上行链路拥挤等)，而客户的崩溃是不可预测或可控的（提高客户稳定性超出了本文的范围）。作为一种解决方案，让中央服务器在本地训练后收集本地更新，而不是在全局轮开始时随机选择客户端。这意味着服务器不需要等待那些指定的客户端进行聚合，而是能够在接收到C部分更新后执行聚合步骤。

2、如果每个设备参与每一轮的可能性相等，则会引入偏差，因为它们在性能和网络访问权限方面不同。建议使用补偿客户选择算法来减轻偏差。原则很简单——对那些参与较少的客户给予更高的优先级。选择策略的伪代码如算法1。

Discriminative Aggregation

采用三个判别步骤来聚合本地更新：

        Pre-aggregation Cache Update:

表示缓存结构的第k个条目，并且表示在第t轮训练的局部模型。

不推荐使用的客户端的条目将替换为全局模型.

        

        SAFA Aggregation:

        

        Post-aggregation Cache Update:

算法2中概述的所提出的SAFA协议的完整工作流程.

        

Analysis of Lag Tolerance

        引入了两个整体度量：同步率（SR）和版本方差（VV）。SR测量下行链路的使用情况，通过下行链路将全局模型分发到网络边缘。VV是基于本地更新的版本分布来定义的。对于SAFA，我们制定SR和VV如下：

r是全局轮次的数量，m是客户端的数量。

是在第t轮训练的客户端的版本分布，即。

        

当滞后容忍度很小时，客户端/模型会经常被弃用，从而导致模型分发的成本相对较高。如果它被设置为一个大值，服务器将对掉队者非常宽容，这可能会导致局部模型版本的高方差，从而减缓全局模型的收敛速度。(实验比较细，感兴趣的可以看原文)

        

Bias Analysis

        从理论上分析了客户之间的性能和可靠性差异导致的客户选择bias。两个客户端（例如，客户端A和客户端B）之间的bias是指客户端A对全局模型做出贡献的机会与客户端B的机会的比率。（省略数学证明，原文详细可自行阅读）

、

        情况1表示客户端选择不足（即，太多崩溃无法满足挑选百分比C）。

        情况3意味着，我们可以通过仅从上一轮未选择的客户端中选择到达的更新来满足选择比率C，因为它们由SAFA进行优先级排序。

        情况2介于1和3之间。也就是说，我们通过首先选择优先的（即上一轮未被选中或崩溃的）客户端，然后选择在这一轮中也提交了本地更新的其他客户端，来满足选择比率C。

PS：FedAvg尽管在训练开始前使用随机选择也会产生bias，因为客户退出或选择退出的频率不同。

算法：

在新的一轮选择中，判断达到的更新，如果上一轮中未选中加入队列则优先放入选择队列中，否则加入Q队列。若是达到最大等待时间还不满足选择比例C，则按排队顺序从Q队列选取更新加入P队列中。

个人疑问

”目标函数定义为平均损失的平均值（在局部分区上），这在局部分区级别是公平的，但在样本级别则不然，因为较小的本地分区中的数据样本在其目标函数中具有更大的权重。”如何体现更大的权重，数学原理是怎样的？

AI解答：

在目标函数定义为平均损失的平均值时，每个本地分区的损失函数被计算并求取平均值，然后再对所有本地分区的平均损失进行求平均。这种方法确保了每个本地分区对整体目标函数的贡献是相等的，从而实现了局部分区级别上的公平性。

然而，在样本级别上，较小的本地分区中的数据样本在计算目标函数时具有更大的权重。这是因为较小的分区中的样本数量较少，因此每个样本对该分区的平均损失有更大的影响。这可能导致在样本级别上存在不公平性，即某些样本对整体目标函数的贡献更大。

有谁可以用数学证明推导一下吗，我没推出来。