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

今天给大家带来一篇名为《并行联邦学习：一种具有理论保证的联邦学习加速方案》的论文解读，在本文中，提出了一个新的联邦学习算法P-FedAvg（Parallel Federated Averaging），作者认为可以部署多个分散的参数服务器以建立一个并行联邦学习系统。以此来解决在典型联邦学习系统中，集中式的参数服务器可能会因为延迟和带宽问题成为系统的性能瓶颈。论文标题：Accelerating Federated Learning via Parallel Servers: A Theoretically Guaranteed Approach论文链接：https://ieeexplore.ieee.org/document/9769746/

1

背景介绍

在典型的联邦学习系统中，通常部署一个集中式的参数服务器，用于协调多个客户端的训练学习。但是一个集中式的参数服务器可能会因为延迟和带宽问题成为系统的性能瓶颈。主要原因在于：一是地理上高度异构的客户端很难同时与一个参数服务器建立快速的网络连接；二是在海量的客户端参与训练的场景下，单个参数服务器的通信能力将严重受限。在本文中，我们认为可以部署多个分散的参数服务器以建立一个并行联邦学习系统，并提出了一个新的联邦学习算法P-FedAvg（Parallel Federated Averaging）。我们在理论上分析了该算法的收敛性，通信代价以及最优混合权重。基于理论分析，我们进一步探讨了P-FedAvg在几种典型拓扑下的收敛性、通信代价和健壮性，与其他方案相比，我们的算法可以有效加快训练速度。下面我们将从算法设计、收敛性和通信代价分析、实验结果、未来工作与总结等层面进行介绍。
作者介绍：本文第一作者为刘学正，刘学正是中山大学计算机学院在读博士生，专注于联邦学习系统架构优化与通信效率提升，已发表SCI论文3篇，EI论文4篇，相关论文发表在IEEE/ACM ToN、IEEE TDSC、IEEE INFOCOM等国际高水平会议与权威期刊上。本文介绍的方案已被ToN 2022接受。
2

并行联邦学习系统与算法设计

在传统的联邦系统中，通常部署一个集中式的参数服务器，用于协调多个客户端的训练学习。在每一轮的训练中，参数服务器通过互联网收集客户端的中间计算结果（如模型参数），并采用模型平均算法（如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使得算法的收敛速度最快，接下来我们首先对算法的收敛性进行分析。

3

收敛性分析

在进行收敛性分析之前，我们先简单介绍以下几个相关的假设。我们认为损失函数满足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除了可以保证较好的收敛性外，最重要的是可以将中心服务器的通信负载分散到多个服务器上，使得通信效率更高。我们将在第四部分对通信代价进行详细分析。

4

通信代价分析

为了展示P-FedAvg的通信优势，我们将从通信量和通信时间两个角度对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的优势主要体现在通信上，随着计算开销的增大（即β变大），加速比将减小。

图2：在5个参数服务器下，P-FedAvg相对于FedAvg的加速比，β代表计算开销相对通信开销的比例

5

混合权重和拓扑影响

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

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

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

图3：五种拓扑示意图关于如何确定拓扑结构，我们考虑了五种不同拓扑结构（如图3所示）并进行了案例分析。表2展示了P-FedAvg在不同拓扑结构下各项指标的对比情况。对于收敛速度（由p决定），complete收敛最快，2d-torus和balanced tree相对较慢，其次是ring，barbell。对于通信代价，complete要求任意两个参数服务器直接通信因而代价最大，ring，2d-torus和balanced tree相对较低，而barbell则取决于两边团的规模  。对于鲁棒性，complete最健壮，2d-torus和ring相对较差，balanced tree和barbell最差。
表2：不同拓扑下P-FedAvg指标对比基于以上，我们可以看出并行联邦学习的拓扑设计是一个非常复杂的问题，需要综合考虑收敛性、通信代价和鲁棒性。通过拓扑案例分析，可知2d-torus是个不错的选择，因为它在各方面都可以获得不错的性能。     6

实验效果

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

不同拓扑对收敛性的影响

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

在五种不同拓扑下，我们分别计算出complete，2d-torus，ring，balanced tree和barbell的p值分别为1.0，0.84，0.29，0.12和0.08。如图4所示，complete和2d-torus相对于其他拓扑的收敛速度更快，barbell收敛最慢。这与我们的理论结果是一致的。不同算法收敛速度的比较

图5：相同训练时间下，不同算法模型准确率变化图

如图5所示，P-FedAvg在相同的训练时间下，可以获得更高的模型准确率，主要原因在于P-FedAvg可以把通信开销分散到不同的参数服务器上，从而加速整个训练过程。混合权重对收敛速度的影响图6：不同混合权重下模型准确略的变化情况如图6所示，本文中推导的最优混合权重相比于随机权重、均一权重的方法可以取得更快收敛速度。其中，随机权重效果最差，均一权重的收敛性能与最优权重非常接近。7

总结与未来工作

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

本文来源：FATE开源社区

END

往期推荐

FLASH:面向高性能的联邦学习硬件加速结构
基于互信息的深度神经网络后门攻击
联邦学习 (FL) 中常见的3种模型聚合方法的 Tensorflow 代码示例
Graph-Fraudster:面向图垂直联邦学习的对抗攻击

欢迎投稿邮箱：[e-mail]参与更多讨论，请添加小编微信加入交流群