ICDE 2023 | 异构数据上的分布式正则化联邦学习

时空实验室 2024-08-01

141

近年来，联邦学习（FL）越来越流行，与传统的分布式学习相比，FL独特的挑战主要在于通信效率和非IID（异构数据）问题。虽然广泛采用的FedAvg框架可以显著减少通信开销，但FL在非IID数据上的有效性尚未得到充分探索。本次为大家带来数据库领域顶级会议ICDE 2023的文章《Distribution-Regularized Federated Learning on Non-IID Data》，论文提出了一种用于非IID数据的联邦学习的分布正则化，以减少客户端之间数据分布的差异，并设计了两种新颖的分布式学习算法（rFedAvg和rFedAvg+），用于有效地进行具有分布正则化的学习。

一. 背景

联邦学习（FL）是一种新的分布式机器学习范式，它允许多个客户端共同训练模型，而每个客户端拥有的原始训练样本不能被共享。联邦学习在许多实际应用中具有广泛的应用前景，例如智能手机用户可以联合训练准确的下一个单词预测模型，企业或医院可以在隐私规定下合作训练联邦模型。与传统的分布式学习相比，联邦学习面临着独特的技术挑战。在联邦学习中，每个客户端持有的数据样本可能来自不同的分布（非独立同分布，或非IID）。此外，客户端与中央服务器之间的带宽和交互次数可能受到限制，这些问题可能会严重恶化分布式随机梯度下降（SGD）算法的有效性和效率。

FedAvg是一个知名的通信高效的联邦学习框架，它通过客户端采样和本地训练实现了分布式SGD，其中一部分客户端执行多步本地梯度下降，服务器通过加权平均它们的模型参数来聚合本地模型。尽管FedAvg在提高FL的通信效率方面取得了成功，但在非IID数据上可能效果不佳。这是因为在非IID数据上训练的高度发散的模型的简单平均可能导致显著的效用损失。多项研究提出了改善FedAvg在非IID数据上有效性的补救措施。然而，它们大多在强假设下的理论分析中停止，有些甚至在某些基准测试中的准确度低于原始FedAvg。

论文从领域自适应的角度探索了非IID数据上的联邦学习。图1显示了在IID和非IID划分的CIFAR10上，由FedAvg从3个客户端生成的最后一个全连接（FC）层的特征。

图1 FedAvg在CIFAR10上的特征可视化

由图像知，在IID数据上，来自不同客户端的特征分布是一致的，可以产生一致的模型（图1a、1b、1c中的黑线），因此模型的平均是有效的。然而，在非IID数据上，特征分布彼此不同，因此本地分类模型可能存在差异（图1d、1e、1f中的黑线）。它们的简单平均会导致混淆和分类准确率的下降。论文提出了一种分布式正则化，以减少非IID数据上联邦学习中客户端之间的数据分布差异，将任意两个客户端之间数据分布的差异最小化，以便他们的本地模型倾向于具有一致的特征表示。然而，直接将FedAvg应用于带有分布正则化的联邦学习是不可行的。这是因为正则化器度量客户端之间的成对距离，其计算需要在每次梯度下降中客户端之间进行通信，这将打破FedAvg中的本地训练步骤，也会带来高通信成本。因此，论文设计了基于FedAvg的新分布式优化算法，可以高效地近似分布正则化器。

二.方法介绍

2.1 联邦学习中的分布正则化

2.1.1 标准联邦学习
论文考虑了一个具有N个客户端的一般联邦学习模型，目标是最小化所有客户端的加权平均目标函数，其中每个客户端的局部目标是最小化经验风险。在联邦学习中，数据分区不能在各方之间共享，只有中间结果被通信到中央服务器进行优化，并且数据可以是非IID的。论文的解决方案基于FedAvg框架，但FedAvg框架没有解决非IID数据问题，论文通过引入分布正则化来明确考虑在非IID数据上的学习。

2.1.2 分布正则化
论文假设每个客户端的数据来自相同的分布，但分布在客户端之间有所不同。为了有效地学习不同扭曲的数据分布，论文提出将这些分布投影到一个公共空间，使得投影分布之间的距离最小化。论文采用最大平均差异（MMD）的经验估计作为客户端数据分布之间的距离，并通过添加一个新的局部目标来修改标准联邦学习模型，该目标明确捕获客户端之间的成对数据分布差异。优化这个模型需要新的联邦学习算法，因为直接应用FedAvg会导致高通信成本，并且在优化这个模型时也无法保证收敛。

2.2 rFedAvg算法和rFedAvg+算法

2.2.1 算法目标
优化目标由标准联邦学习目标和分布正则化项组成。标准联邦学习目标可以通过FedAvg等通信高效的算法进行优化，但精确计算正则化项需要在每对客户端之间进行额外的通信来计算成对的MMD距离，这会导致至少

的通信开销。

2.2.2 预备知识：FedAvg算法

FedAvg是公认的通信高效优化标准联邦学习目标的框架，它基于同步分布式大批量SGD，主要有两个步骤：(1)客户端的本地更新和 (2)服务器的全局聚合。在每一轮t中，按采样比例SR采样一部分客户端，其中客户端k将执行本地小批量SGD，学习率为

，批量大小为B，进行E步。之后，中央服务器通过对它们进行加权平均来聚合本地模型，即

。在FedAvg中，采样比例SR、本地步骤数E和小批量大小B共同控制计算和通信开销。当SR = 1且E = 1时，FedAvg简化为标准的同步分布式SGD。

2.2.3 rFedAvg算法

基本思想：直接应用FedAvg会在每轮t中计算客户端k和k'之间的距离

。rFedAvg的基本思想是使用延迟映射来避免这种全局通信。具体来说，论文定义一个本地映射算子

，这样距离就变成了

。延迟映射指的是，在t轮的客户端k，论文使用k'在某个之前轮t' < t的本地映射

来计算它们之间的距离。本地映射δ的同步遵循FedAvg中的同步，即每E个本地步骤同步一次。

算法细节：算法1展示了rFedAvg算法。注意，在FedAvg中，迭代次数t（即梯度下降步骤）在本地和全局步骤中没有区别。使用额外的概念c来表示全局通信（同步）步骤，以避免歧义。在每个通信步骤，迭代次数t是t=c⋅E。算法总共运行C个通信轮次，等于C⋅EC⋅E次迭代。在全局步骤c之后的第i个本地训练步骤中，客户端k计算梯度Fk′，其中

，

。延迟映射

在全局步骤c时由服务器广播，因此在i步后延迟。本地训练后，每个客户端发送他们的

以及本地模型参数到服务器进行聚合和后续通信。

图2 算法1

备注：rFedAvg算法有两个缺点：假设δ是一个d维向量。那么单轮通信开销至少是

，因为服务器必须向N个客户端广播N·d维向量的副本。每个延迟的

是使用每个客户端的本地模型参数

计算的，这可能加剧客户端之间的差异。

2.2.4 rFedAvg+算法

基本思想：为了进一步减少通信成本并避免映射的不一致计算，论文提出了rFedAvg+算法，它在以下方面修改了rFedAvg：在每轮中增加了一个同步步骤，在计算映射之前获得一致的全局模型。通过计算所有

的平均值而不是计算它们之间的距离来减少通信开销。

算法细节：算法2展示了rFedAvg+算法。论文主要详细描述这两个修改。首先，论文允许服务器和客户端在每个通信轮次中通信两次。第一次时，服务器和客户端只同步全局模型。第二次时，每个客户端使用全局模型计算

然后将其发送回服务器。这样客户端可以在计算它们之间的距离时达成共识。其次，服务器将使用客户端δ的平均值而不是N维向量δ。因此，通信开销从

降低到O(dN)。在这种情况下，

的目标将从

变为

。注意

和

关于

的梯度相同，因此收敛仍然可以保持，而

也可以被视为

的紧密下界。

图3 算法2

备注：rFedAvg+将总通信开销从

降低到O(dN)，尽管客户端需要在每个训练轮中与服务器通信两次。正如论文将在评估中展示的，rFedAvg+在测试准确率方面通常优于rFedAvg，并且每轮训练时间也更高效。还值得一提的是，尽管论文假设所有客户端都参与了rFedAvg和rFedAvg+的描述，但实证研究表明，在部分参与的情况下它们也是有效的。然而，所提出的方法仍然有一些局限性。例如，它们只能缓解数据异质性问题，而不能在极端非IID（即有异常值）的情况下完全解决它。在这种情况下，一个可能的补救措施是首先消除异常值，论文的方法将是可行的。

三．实验

3.1 实验设置

比较方法：论文比较了FedAvg、FedProx、Scaffold、q - FedAvg、rFedAvg和rFedAvg+这几种方法。

数据集：论文在4个数据集上比较了不同方法的性能，包括MNIST、CIFAR10、Sent140和FEMNIST。

模型和超参数：对于MNIST和CIFAR10，论文使用相同的CNN结构，对于Sent140，论文使用2层LSTM + 1层FC。每个算法都有特定的超参数设置。

实验环境：论文使用PyTorch 1.8.0实现了所有方法，并在五个Intel（R）Xeon（R）Platinum 8269CY 3.10GHz CPU上进行了实验，代码已开源。

评估指标：论文使用训练损失和测试准确性作为评估指标，并记录每轮的训练时间来比较rFedAvg和rFedAvg+的效率。

3.2 效率和效果研究

表1 在交叉筒仓设置下的三个数据集上的测试精度

表2 在跨设备设置的三个数据集上进行测试精度

在MNIST数据集上的结果：MNIST上的结果如图4、图5、表I和表II所示。论文记录了60轮通信的准确率，从图4a和图5a观察到，rFedAvg和rFedAvg+在平均情况下比基线算法收敛得更快且更稳定，而Scaffold和FedAvg在跨设备0%相似度设置中也具有竞争力。FedProx和q-FedAvg的表现相对较差，它们的方差也更大。在交叉筒仓0%相似度设置中（图4b，图5b），除了FedProx之外，各方法之间的差距变小了，但论文仍然可以从表I中发现rFedAvg+表现最好。当相似度为10%时，所有算法的性能都有所提高，而rFedAvg和rFedAvg+的优势变小了。当相似度为100%时，所有算法的表现几乎相同。

图4 MNIST数据集上的精确度曲线

图5 MNIST数据集上的损失函数曲线

在CIFAR10数据集上的结果：CIFAR10上的结果如图6、图7、表I和表II所示。论文记录了200轮的结果，可以大致发现，CIFAR10的非IID分割可能导致与IID分割相比约30%的准确率损失，这意味着CIFAR10更适合进行非IID评估。在完全非IID的情况下（相似度0%），rFedAvg+在跨设备和交叉筒仓设置中表现最佳，并且比其他方法高出2%以上。FedAvg仍然具有竞争力，并明显优于FedProx和q-FedAvg。还可以观察到，基线测试准确率的曲线在跨设备设置中特别波动剧烈，而rFedAvg和rFedAvg+的曲线看起来更稳定，平均值更高。随着相似度增加到10%和100%，所有方法的准确率迅速提高，所提出的方法的优势不太明显，甚至在交叉筒仓相似度10%的设置中被FedAvg超越。这些结果表明只有一小部分共享IID数据可以带来显著的性能提升。

图6 CIFAR10数据集上的精确度曲线

图7 CIFAR10数据集上的损失函数曲线

在Sent140数据集上的结果：Sent140上的结果如图8、图9、表I和表II所示。论文记录了30轮的结果，在具有非IID数据的跨设备设置中，可以从图8a和图9a观察到，与基线相比，rFedAvg和rFedAvg+的优势非常明显。根据表II，它们可以领先超过3%，并且根据图8a，收敛速度的优越性也非常明显。在IID数据上，FedAvg的性能接近所提出的方法。在交叉筒仓设置中，可以发现rFedAvg和rFedAvg+在非IID数据上仍然显著优于基线，而FedProx和q-FedAvg几乎无法收敛。它们在Sent140上表现不佳的原因可能是它们只为SGD设计，并且不支持其他优化器。但是所提出的rFedAvg和rFedAvg+仍然可以很好地与RMSProp一起工作，这验证了论文方法的更好兼容性。

图8 Sent140数据集上的精确度曲线

图9 Sent140数据集上的损失函数曲线

在FEMNIST数据集上的结果：FEMNIST上的结果如图10所示。论文评估了两种设置：100个客户端和500个客户端，并记录了80轮的结果。在图表中，低成本指的是SR = 0.1，E = 10，高成本指的是SR = 0.2，E = 20。可以观察到，所提出的rFedAvg在所有基线中表现最佳，而rFedAvg+在100个客户端和500个客户端中也显示出有竞争力的性能。

图10 FEMNIST数据集上的精确度曲线

参数研究：论文研究了超参数λ、N、E和SR的影响，如图11。发现合适的λ对于优化很重要，N、E和SR的变化会影响准确性，在跨设备和非IID设置中找到合适的阈值可以减少不必要的通信成本。

图11 参数研究

效率评估：如图12，rFedAvg和rFedAvg+需要更少的轮次来达到特定的准确性水平，rFedAvg+的平均训练时间通常是rFedAvg的一半，并且接近FedAvg。rFedAvg+中δ的大小不会随着客户端数量的增加而扩展，大大节省了通信开销。

图12 效率评估

3.3 结果总结

总的来说，论文提出的方法rFedAvg和rFedAvg+在非IID数据上通常可以比FedAvg提高0.95% - 2.19%的交叉槽设置和0.34% - 3.50%的交叉设备设置的性能。rFedAvg+在交叉设备设置中运行速度约为rFedAvg的两倍，论文的方法还可以提高最差客户端的性能，并且在一定程度的隐私保护下是稳健的。

四．总结

论文研究了联邦学习中的非IID问题，提出了一种分布正则化来减少客户端之间数据分布的差异，并设计了两种新的通信高效的分布式学习算法rFedAvg和rFedAvg+。论文从理论上证明了它们对于强凸目标的收敛性，并通过实验验证了它们在非IID数据上的有效性和效率。未来，数据异构性问题仍然是联邦学习的主要挑战，从单一角度的解决方案如正则化不能完全解决这个问题，未来的方向可以是结合自适应参与者选择和个性化联邦学习与集中式训练框架，以同时提高全局模型的泛化能力和本地模型的个性化性能。

-End-

本文作者

刘明星

重庆大学计算机科学与技术2022级本科生，重庆大学Start Lab团队成员。

主要研究方向：数据压缩、分布式训练

重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有3~5名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

图文｜刘明星

编辑｜徐小龙

审核｜李瑞远

审核｜杨广超

正则化分布式算法通信

文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

ICDE 2023 | 异构数据上的分布式正则化联邦学习

评论