分层联邦学习①-SHARE

SHARE: Shaping Data Distribution at Edge for Communication-Efficient Hierarchical Federated Learning

摘要：

联合学习（FL）可以在移动节点上实现分布式模型训练，而无需共享对隐私敏感的原始数据。然而，为了实现高效的FL，一个重大挑战是提交模型更新的通信开销过高，因为通常需要频繁的云模型聚合才能达到目标精度，尤其是当移动节点处的数据分布不平衡时。通过试点实验，验证了如果模型聚合可以在边缘进行，则可以避免频繁的云模型聚合而不会降低性能。为此，我们介绍了分层联合学习（HFL）框架，其中选择分布式节点的子集作为边缘聚合器来进行边缘聚合。特别是，在HFL框架下，我们提出了一个通信成本最小化（CCM）问题，以最小化边缘/云聚合带来的通信成本，并对边缘聚合器的选择和分布式进行决策

问题提出：

为了实现高效的FL，一个重大挑战是提交模型更新的通信开销过高，因为通常需要频繁的云模型聚合才能达到目标精度，尤其是当移动节点处的数据分布不平衡时。矛盾的是，分布式节点通常在通信/带宽资源方面受到限制，无法频繁与云通信。

此外，随着学习模型结构变得越来越复杂（例如，深度神经网络），模型更新的数据量将显著增加，加剧通信开销。

现有工作：

①压缩方案，如稀疏化、量化和草图，被应用于压缩模型更新，以减少每轮通信的消息大小。它们可以降低每轮通信成本，但代价是精度和收敛速度方面的性能下降不可忽略，因为模型更新的信息无法理想地恢复。

②其他工作试图减少达到目标学习精度所需的云聚合轮次或模型更新的总数。

本文想法：

通过实验发现如果模型聚合可以在边缘进行，就可以避免频繁的云聚合而不会降低性能。如果边缘聚合配置得当，学习性能甚至可以提高。

在分层联邦学习框架下，我们提出了一个通信成本最小化（CCM）问题，以最小化边缘/云聚合带来的通信成本，并对边缘聚合器的选择和分布式进行决策。

一方面，我们专注于将模型更新提交给边缘聚合器和云聚合器的通信成本降至最低，以降低每轮通信成本。另一方面，我们旨在塑造边缘聚合器的数据分布，使其数据分布更加平衡，这可以减少达到目标模型精度所需的通信轮次。由于这两个目标不能同时实现，我们引入了一个参数来调整折衷，并将原始问题转化为数据分布感知通信成本最小化（DD-CCM）问题。由于DD-CCM问题的NP硬度，我们最终设计了两种轻量级算法来协同解决该问题。

具体来说，在给定边缘聚合器集的情况下，我们首先设计了一种基于贪婪的nOde Association（GoA）算法来对节点到边缘的关联进行决策。然后，在GoA的基础上，我们设计了一种LOcal Search（LoS）算法来反向优化边缘聚合器的选择。

SHARE概述：

下图显示了SHARE的工作流程，其中包括问题转换和算法设计的组件。

对于问题转换，有两个优化方向来解决CCM问题，即最小化每轮云聚合中的通信成本，以及减少所需的云聚合数量。

我们首先将CCM问题分为对应于两个方向的子问题，每轮通信成本最小化（PCCM）问题的子问题 1 是为了最小化每轮通信成本。为了确定κ的影响，我们采用Kullback–Leibler散度（KLD）来量化边缘聚合器处数据分布的平衡度。

然后在此基础上，我们提出了子问题2：KLD均值最小化（KMM）问题，以最小化边缘聚合器的KLD值的平均值，即使边缘聚合器中的数据分布更接近均匀分布。

在平衡两个子问题之间的折衷后，将原始问题转化为数据分布感知通信成本最小化（DD-CCM）问题。由于DD-CCM问题的NP硬度，我们最终设计了两种轻量级算法，分别优化边缘聚合器选择和分布式节点关联的高度耦合决策（the highly-coupling decisions of edge aggregator selection and distributed node association）。

问题转换

子问题1 (PCCM)：

在每一轮云聚合中，目标是通过对X和Y做出决策，将分布式计算节点、边缘聚合器和云聚合器之间的总通信成本降至最低。

子问题2(KMM)：

目标是通过对X和Y进行决策，最小化边缘聚合器的数据分布和均匀分布之间的KLD平均值。

需要注意的是，由于目标的竞争，子问题1和子问题2的最优结果有时不能同时实现。下面的权衡是：我们应该根据通信成本或边缘聚合器的数据分布将节点与边缘聚合器相关联吗？为了平衡权衡，我们引入了一个参数γ来调整通信成本和数据分布KLD的权重。然后，原始CCM问题可以转换为以下DD-CCM问题：

算法设计：

为了解决边缘聚合器选择和计算节点关联之间高度复杂的耦合问题，我们设计了两种轻量级算法对它们进行相应的优化。特别是，我们首先回答以下问题：给定一组边缘聚合器，如何将分布式计算节点与它们相关联，从而在不违反约束的情况下，将通信成本和数据分布差异联合最小化？为此，我们提出了一种基于贪婪的nOde关联（GoA）算法来决定节点到边缘的聚合器关联。然后，在GoA的基础上，我们设计了一种LOcal Search（LoS）算法来反向优化边缘聚合器的选择

Subroutine to Distributed Node Association.

Subroutine to Edge Aggregator Selection.

重点研究边缘聚合器的选择问题，以找到最优的边缘聚合器集，在此过程中，通过采用GoA来实现节点关联决策。很容易确认边缘聚合器选择问题是具有个可能选项的组合问题为了实现时间高效的方式，我们设计了一个用于边缘聚合器选择的本地搜索算法，即LoS。

如算法2中所示，从随机选择的初始可行解Es开始，该算法重复以下三个局部改进操作，直到没有任何操作可以降低总通信成本。