并行联邦学习：一种具有理论保证的联邦学习加速方案

在传统的联邦系统中，通常部署一个集中式的参数服务器，用于协调多个客户端的训练学习。在每一轮的训练中，参数服务器通过互联网收集客户端的中间计算结果（如模型参数），并采用模型平均算法（如FedAvg算法）对参数进行聚合，同时将结果发回给客户端进行下一轮的训练。

在并行联邦学习系统中，为了缓解中心参数服务器的通信压力，可以部署M个分散的参数服务器，每个参数服务器i负责协调一组客户端  进行训练，参数服务器之间通过某种拓扑相连，并定期交换模型参数，优化目标定义如下：

其中, x代表全局模型参数， 代表客户端j的本地损失函数。为了最小化全局损失函数f(x)，我们将介绍并行联邦学习的一般流程。

图1：一个简单的并行联邦学习系统示例

如图1所示，并行联邦学习的运行过程如下：

（1）每个参数服务器i从本地客户端集合  中随机选择  个客户端，并将本轮的模型参数分发给它们进行训练；

（2）每个客户端收到所属参数服务器的模型参数后在本地进行E轮迭代，并将更新结果返回给参数服务器；

（3）每个参数服务器对  个客户端的模型参数进行聚合，并与邻居参数服务器混合模型参数；

（4）返回至第（1）步直到训练结果满足停止条件。

为了表示聚合参数的过程，我们定义每个客户端更新的参数向量为  ，那么中间参数向量代表  个客户端聚合后的模型参数。为了描述参数交换过程，我们定义每个参数服务器i与邻居节点混合参数的权重，其中且。如果用  代表参数服务器i与邻居节点混合参数后的模型向量，那么参数服务器i完成一轮参数混合可形式化为，这里的。

我们对传统的FedAvg算法进行扩展，设计了P-FedAvg算法（见Algorithm 1）。与FedAvg算法不同的是，在P-FedAvg中，每个参数服务器并行地运行FedAvg算法，同时为了使所有参数服务器的模型参数达成共识，每个参数服务器不仅需要聚合来自客户端的模型参数（算法1第8行）还需要与邻居节点交换模型参数（算法1第10行）。

为了让P-FedAvg可以尽快收敛，参数服务器之间应以全拓扑结构相连，但是考虑到互联网中较高的通信代价，更合理的方案是让所有参数服务器以有限的边相连。我们使用一个M×M 大小的邻接矩阵L来描述参数服务器间的拓扑结构，并使用代表混合矩阵。对于给定的拓扑结构L，为了确定W使得算法的收敛速度最快，接下来我们首先对算法的收敛性进行分析。

收敛性分析

在进行收敛性分析之前，我们先简单介绍以下几个相关的假设。我们认为损失函数满足L-smoothness和u-convex性质，随机梯度的二范数和方差是有界的。

此外，为了描述参数混合过程，我们假设混合矩阵W是一个对称双随机矩阵，那么存在一个固定值p∈(0,1]，使得：

这里代表所有参数服务器模型的平均值，XW表示参数服务器间进行一次模型参数混合。上述假设确保所有参数服务器的模型参数向平均值靠近（称为共识过程）。共识的速度与p值相关，p值的大小介于0~1之间，且和服务器间的拓扑结构相关。关于客户端数据的non-iid（non-independent identical distribution）程度，我们使用Γ表示，即全局损失最优值与局部损失最优值之间的差异程度。更多假设的细节可见原论文第四章节。

基于以上假设，我们推导出了P-FedAvg在客户端全参与和部分参与情况下的收敛上界：

客户端全参与：

客户端部分参与（每个参数服务器随机选择  个客户端）：

我们得出以下几点重要结论：

（1）在客户端全参与情况下，当T足够大时，P-FedAvg和FedAvg的渐进收敛率都是，但是P-FedAvg相对于FedAvg带来了额外的开销，即。直观来说，p值的大小与通信拓扑稀疏程度相关，拓扑越稀疏，p值越小，收敛上界越松。

（2）在客户端部分参与情况下，如果忽略（1）中提到的与p相关的项，P-FedAvg中的与FedAvg的不同（这里），很容易验证。所以当每个参数服务器选择相同的客户端个数时，P-FedAvg和FedAvg可以达到相同的渐进收敛率。但是，由于引入了M个参数服务器，P-FedAvg在实际中可以使得因而相对于FedAvg获得更快的收敛速度。

（3）P-FedAvg除了可以保证较好的收敛性外，最重要的是可以将中心服务器的通信负载分散到多个服务器上，使得通信效率更高。我们将在第四部分对通信代价进行详细分析。

通信代价分析

表格1：P-FedAvg和FedAvg通信量对比

如表格1所示，我们分别对比了P-FedAvg和FedAvg的总通信量和峰值通信量来。假设模型参数大小为s，参与训练的客户端总数目为K，如果有M个参数服务器，每个服务器负责其中的  个客户端，并且。对于FedAvg，一轮全局迭代的总通信量和峰值通信量都是2Ks。对于P-FedAvg，由于多个参数服务器之间需要交换模型参数，总通信量会引入额外的通信开销。但是，P-FedAvg同时将通信量分散到了不同的参数服务器上，峰值通信量变为，相对于FedAvg更低。

通信时间

为了分析P-FedAvg一轮全局迭代的时间，我们首先定义延迟矩阵代表一轮全局迭代中参数服务器i完成本地客户端聚合和发送模型参数到邻居节点i'的总延迟，定义如下：

这里，代表服务器i与客户端j在参数聚合中的通信延迟，  代表客户端本地一轮迭代的计算延迟，代表服务器i和i'在参数混合中的通信延迟。

进一步，与参与训练的客户端个数  、服务器的传输延迟  和客户端的传输延迟   有关，如下：

如果用  代表参数服务器i向邻居服务器传输数据的带宽，那么与参数服务器i的度数  和服务器之间通信链路的可用带宽有关，定义如下：

由于P-FeAvg采用同步的方式运行，受限于最慢的参数服务器，所以我们得到一轮全局迭代的时间α如下：

这里分别代表随机变量的最高阶统计量。而P-FedAvg相对于FedAvg的加速比可以定义如下：

基于以上分析，我们可以得到如下重要结论：

（1）当参数服务器与客户端之间的通信成为瓶颈（当K较大时），P-FedAvg可以将FedAvg的降低为，并达到 的加速比。

（2）一方面，参数服务器间如果增加更多的连接，将会使变大（因为或者将变大），进而使会变大，从而降低P-FedAvg的通信效率。另一方面，越稠密的通信拓扑将导致p值的增大，根据收敛分析，收敛速度将更快。这表明实际并行联邦学习系统的优化将会变得更加复杂。

为了直观地说明P-FedAvg的通信优势，我们用一个例子来说明。假设共有100个客户端参与训练，参数服务器与客户端和参数服务器之间的通信速率均为10Mbps，模型参数大小为50Mb。这里，我们只考虑通信开销，忽略计算开销。对于FedAvg，一轮全局迭代的时间为(2 × 100 × 50Mb)/10Mbps=1000s。对于P-FedAvg，假设有5个参数服务器，每个参数服务器协调20个客户端，那么一轮参数聚合的时间为(2 × 20 × 50Mb)/10Mbps=200s，一轮参数混合的时间为(2  × 50Mb)/10Mbps=10s（假设通信拓扑为环形）。那么P-FedAvg相对于FedAvg的加速比为1000s/(200s+10s)≈4.7。

我们进一步对运行时间进行了模拟。如图2所示，我们设置参数服务器的个数为5，每个服务器选择相同数目的客户端参与训练，且随机变量满足指数分布。随着参与客户端的总数目K的增多，参数服务器与客户端之间的通信逐渐成为瓶颈，P-FedAvg相对与FedAvg的最终加速比可达到5。由于P-FedAvg的优势主要体现在通信上，随着计算开销的增大（即β变大），加速比将减小。

混合权重和拓扑影响

总结：通信拓扑稠密→通信负担大同时p值增大→收敛速度快但每轮时间成本高。

在这一部分，我们将研究在给定拓扑结构下如何确定最优混合权重，以及不同拓扑结构对并行联邦学习收敛性、通信代价和鲁棒性的影响。

对于给定的一个拓扑结构，根据收敛性分析，我们可以通过最大化p值来最小化收敛上界，可以证明，最大化p值等价于最小化，这个问题可以转换为一个半正定规划问题，从而被高效地求解。

实验效果

为了验证理论分析和证明算法的有效性，我们考虑不同通信拓扑和混合矩阵对P-FedAvg收敛的影响，并对比了P-FedAvg与其他算法的性能差异。

不同拓扑对收敛性的影响

图4：相同全局迭代次数下，不同拓扑的P-FedAvg准确率变化图

总结与未来工作

在本文中，我们介绍了一个基于多参数服务器的并行联邦学习框架和P-FedAvg算法。我们对P-FedAvg的收敛性和通信代价进行了理论分析，并研究了不同拓扑对模型收敛的影响，同时给出了确定最优混合权重的方法。实验证明P-FedAvg可以有效加速联邦学习的训练过程。未来我们将从收敛率、通信代价和鲁棒性多方面综合考虑参数服务器之间通信拓扑的设计方法，同时提供对动态拓扑的分析与支持。

往期推荐