GrasAD：基于梯度和累积分布的设备选择方法，用于异步联邦学习

《Knowledge-Based Systems》：GrasAD: Gradient Similarity and Accumulated Distribution-Based Device Selection for Asynchronous Federated Learning

异步联邦学习（AFL）旨在解决异构设备下的隐私保护与非IID数据分布问题，但梯度过时导致模型性能下降。现有方法单独处理数据分布和梯度过时，导致内部冲突。本文提出GrasAD算法，动态选择设备，结合梯度相似性和累计数据分布的重要性指标，优化全局模型收敛。实验表明，GrasAD在多个基准数据集上显著优于现有方法。

　　

李亚楠|王梦辉|任建基|王一萌|袁永亮|倪浩

河南理工大学软件学院，焦作市，454003，中国

摘要

异步联邦学习（AFL）是一种保护隐私的框架，旨在适应设备异构性和数据分布的多样性。通过设备与服务器之间的异步交互，AFL在最大化设备计算能力的同时，受设备状态的影响较小，使其非常适合物联网（IoT）和边缘计算等大规模分布式场景。然而，异步更新机制引入了信息陈旧的问题，这可能会降低模型性能。现有方法主要通过使用反比例函数来抑制陈旧效应，而没有充分利用陈旧更新的潜在价值。为了解决这个问题，我们提出了GrasAD，这是一种动态设备选择方法，它结合了累积分布和梯度相似性来评估本地更新的重要性。GrasAD从两个维度评估本地更新：历史累积分布和当前梯度相似性，分别提供全局和局部视角。设备按重要性而非数值进行排序，以减少规模差异，从而实现更快、更稳定的全局模型收敛。在四个基准联邦数据集上的广泛实验证明了GrasAD的有效性。结果表明，在不同的非独立同分布（non-IID）设置下，GrasAD获得了最高的整体预测准确性，与多种比较算法相比，这种改进是显著的。

引言

联邦学习（FL）[1]是一种分布式框架，它在每次聚合轮次中将模型参数或梯度而不是原始数据传输到随机选定的设备和云服务器之间，从而防止原始隐私泄露。近年来，FL已被应用于各种实际场景，如交通流量预测[2]、无人机[3]和智能家居[4]。FL的一个典型特征是数据是非独立同分布（non-IID）的。如何减轻非独立同分布数据对模型效用影响的问题受到了相当大的关注[5]、[6]。

根据是否同步随机选定设备的本地训练，FL被分为同步FL（SFL [1]）和异步FL（AFL [7]）。虽然同步可以在单次聚合轮次中实现比AFL更高的准确性提升，但SFL也假设所有随机选定的设备具有同质的计算和通信资源。然而，在实践中满足这一假设是困难的。尽管提出了许多策略，如用户分组[8]、设备选择[9]和弹性同步[10]来减轻设备异质性的影响，但问题并未得到根本解决。

相比之下，AFL更适合大型异构设备场景，如边缘计算和物联网（IoT），因为它允许每个设备在不等待其他设备的情况下将其更新的模型参数发送到服务器。然而，提高AFL算法的预测准确性面临许多挑战。特别是，非独立同分布数据和梯度陈旧是两个主要挑战。后者，即梯度陈旧，是由于设备聚合频率不均匀造成的。

尽管有大量的研究，但这些研究都是分别处理这两个挑战，而不是作为一个整体来考虑。对于非独立同分布数据，已经提出了一些方法，如设备选择[11]、梯度残差累积[12]、选择性自蒸馏[13]和近端约束[14]。设备选择在AFL中是一种广泛使用的方法，因为它避免了端侧需要额外的计算。图1展示了这种方法的高级描述。现有研究主要基于当前设备的标签分布[15]、[16]来选择设备，这可能导致累积分布不平衡和模型更新有偏差。对于梯度陈旧，主要方法是设置与陈旧程度成反比的聚合权重，包括指数[17]、线性[18]和幂函数[14]，或者甚至丢弃陈旧程度超过给定阈值的设备[19]。然而，陈旧的梯度可能包含有用信息，简单地降低权重将进一步限制数据有限的设备的贡献。

除了为这两个挑战分别提供解决方案的缺点之外，一个令人困惑的问题是，针对非独立同分布数据和梯度陈旧的不同解决方案之间存在内在冲突。解决非独立同分布数据需要尽可能多样化的数据。然而，降低陈旧梯度权重的解决方案会减少相应设备数据的影响。很少有研究探讨非独立同分布数据和梯度陈旧之间的相互作用。Zhou等人[19]提出了一种一致的梯度标准，并建立了具有高权重的陈旧但高度一致的梯度。然而，他们仅使用当前和累积的梯度信息来减少相互作用的影响，而没有考虑标签分布。如第5节所示，通过同时考虑梯度相似性和累积数据分布，GrasAD在预测准确性方面优于WKAFL。

为了解决上述问题，我们综合考虑了设备选择相似性和累积分布，以减轻非独立同分布数据和梯度陈旧的相互作用影响，并提出了一种名为GrasAD的设备选择AFL算法。从高层次抽象来看，我们首先定义了两个指标：分布重要性指数和梯度重要性指数，分别衡量设备的重要性。随后，我们根据这两个指标的交集来选择聚合设备。特别是，累积数据分布重要性指数用于确保使用的历史数据接近均匀分布（即最大熵），从而减轻非独立同分布数据的影响。梯度重要性指数同时考虑了陈旧程度和梯度相似性，用于最大化高陈旧程度的梯度价值。最终的整体重要性考虑了数据分布、梯度相似性和陈旧程度，用于减少非独立同分布数据和梯度陈旧的联合影响。

总结如下：

• 我们提出了一种新的方法来减轻非独立同分布数据和梯度陈旧的相互作用影响，而不是分别处理它们。基于此，我们提出了一种适用于异构设备场景的设备选择AFL算法GrasAD，同时考虑了累积分布和梯度相似性的重要性。
• 我们提出了两个重要性指数来解决AFL中的设备选择问题。我们首先提出分布重要性指数来衡量使用历史数据的平衡并提高熵。然后我们提出梯度重要性指数来衡量陈旧本地更新的重要性，这样可以利用高陈旧梯度中的潜在信息。
• 我们在标准的LEAF数据集（包括FEMNSIT、CelebA、Synthetic和Shakespeare）上进行了广泛的实验，以验证所提出的GrasAD算法。实验结果表明，GrasAD在所有数据集上的测试准确性、训练速度和稳定性方面都优于几种现有的最佳算法（SOTA）。

部分摘录

设备选择

考虑到具有非独立同分布数据的异构设备，有必要在每次全局聚合中选择合适的设备子集以改进训练过程。现有研究大致可以分为三类：

计算和通信条件。基于每个设备上的计算能力、通信延迟和原始数据，Chen等人[20]提出了一种可比较的节点选择算法，迭代选择参与全局聚合的节点

K-异步FL（K-AFL）

FL（包括SFL和AFL）的模型训练可以定义为以下优化问题，该问题是在由$N$个客户端组成的集合$\underset{w\in R^d}{\min }f\left(w\right)=\sum _{i=1}^{\underset{}{\overset{}{\frac{|D_i|}{|}}}}\left|D\right|E_{\xi ～D_i}{f}_i(w;\xi )$其中$|D_i$$|$表示第个客户端的分布和局部目标函数。$|$表示设备i上的样本数量，而对$|$的求和表示$|。由于实际场景中设备之间的数据是非独立同分布的，因此假设当$i ≠ < />时，$D_i\ne D_j$。

< />

提出的算法GrasAD

GrasAD是一种适用于具有大量异构设备的AFL场景的设备选择算法。GrasAD通过协作探索梯度和累积分布的信息来提高模型效用。我们首先在第4.1节介绍GrasAD的主要概念，并在第4.2节展示了其整体框架。我们在第4.3节和第4.4节分别描述了设备选择和加权聚合的技术细节。

实验

我们进行了广泛的实验来验证所提出的GrasAD，包括参数敏感性分析、消融实验以及与其他最佳算法的比较实验¹。

结论

本研究提出了GrasAD，这是一种结合了梯度相似性和累积数据分布指标的AFL算法，以优化设备选择和模型聚合，从而提高整体模型效用。具体来说，GrasAD根据设备的梯度重要性和数据分布重要性识别候选设备，然后通过计算这两者的交集来选择参与设备。随后应用分段聚合策略进行组合

CRediT作者贡献声明

李亚楠：撰写 – 审稿与编辑。王梦辉：软件实现。任建基：形式分析。王一萌：方法论。袁永亮：资金获取。倪浩：撰写 – 原稿。

利益冲突声明

作者声明他们没有已知的可能会影响本文所述工作的财务利益或个人关系。