面向分层联邦学习的统一化聚类算法FEDUC研究学术报告

一、 研究团队、发表期刊与时间 本研究的主要作者为 Qianpiao Ma， Yang Xu， Hongli Xu， Jianchun Liu 和 Liusheng Huang。作者们来自中国科学技术大学计算机科学与技术学院、苏州高等研究院以及紫金山实验室。该项研究以论文形式发表于 *IEEE Transactions on Mobile Computing*（IEEE移动计算汇刊）期刊，该刊为计算机科学领域移动计算方向的顶级国际期刊。论文的在线发表日期为2024年2月19日，最终版本发布于2024年10月的第23卷第10期。

二、 研究背景与目标 本研究的核心科学领域为联邦学习在移动边缘计算场景下的高效部署与优化。联邦学习作为一种分布式机器学习范式，允许多个边缘设备（或称工作者）在不共享原始数据的情况下协同训练模型，从而在保护数据隐私的同时利用分散的数据。然而，在实际的边缘计算环境中部署联邦学习面临三大关键挑战：1) 边缘异构性：不同边缘设备的计算能力、网络连接、数据量存在巨大差异；2) 资源约束：边缘设备通常计算和通信资源有限；3) 非独立同分布数据：每个设备收集的数据通常不是从整体数据分布中均匀抽样的，数据分布差异巨大。

为了应对这些挑战，联邦学习发展出了不同的架构，主要包括参数服务器架构、点对点架构和分层聚合架构。参数服务器架构存在单点瓶颈和扩展性差的问题；点对点架构虽然扩展性好，但为了实现与参数服务器架构相当的性能，需要大量节点间通信，通信开销巨大。分层聚合架构作为一种折中方案，将工作者组织成多个集群，每个集群部署一个聚合器。该架构包含两层聚合：簇内聚合和簇间聚合。簇内聚合在每个集群内部进行，簇间聚合则在聚合器之间协作进行。分层聚合架构既能分散参数服务器的负载，又能通过使簇内模型保持一致来缓解点对点架构中的高方差问题。

然而，现有的分层聚合架构研究存在一个关键不足：未能提供一个统一的聚类方法以适应多样化的簇间聚合模式。簇间聚合模式可以从结构（集中式或分布式）和通信模式（同步或异步）两个维度划分，组合出四种主要模式：集中式同步（censyn）、集中式异步（cenasy）、分布式同步（decsyn）和分布式异步（decasy）。不同的簇间聚合模式，其收敛性能受到不同因素的影响，例如：1) 集群间的数据分布（对所有模式重要）；2) 各集群参与异步簇间聚合的频率（对cenasy和decasy模式重要）；3) 分布式结构中的簇间拓扑连接（对decsyn和decasy模式重要）。现有聚类方法（如仅考虑通信时间或仅考虑数据分布）无法同时优化这些因素，导致在不同的簇间模式下可能表现不佳。

因此，本研究的目标是：深入探究不同簇间聚合模式的收敛性能与上述关键因素之间的定量关系，并基于此分析，设计一个统一的、可适配不同簇间聚合模式的聚类算法，以最大化分层联邦学习的训练性能。

三、 研究流程与方法 本研究是一个理论分析与算法设计相结合的工作，主要流程分为四个关键步骤：收敛性理论分析、簇内聚合策略优化、问题建模与统一聚类算法设计，以及实验验证。

第一步：四种簇间聚合模式的收敛性理论分析 这是研究的核心理论基础。研究团队首先对联邦学习中常用的损失函数做了标准假设（L-光滑性和μ-强凸性），然后针对分层聚合架构的四种模式（censyn， cenasy， decsyn， decasy），分别进行了严格的收敛性证明。 * 研究对象与模型：研究考虑了一个由n个工作者（V）和m个聚合器（S）构成的系统。每个工作者拥有本地数据集和损失函数。工作者被聚类到m个集群中，每个集群由一个聚合器负责。 * 分析方法与流程： 1. 基础分析（簇内聚合）：首先，研究人员推导了在一个固定的集群内，执行t‘轮簇内聚合后的模型损失期望值与最优损失之间差距的上界。这个上界表达式（引理1）揭示了损失差距与一个收敛因子ρ0以及一个残差误差项γj有关。其中γj包含了与该集群数据分布相关的关键项ξj，它代表了集群损失函数的梯度与全局损失函数梯度之间的最大差异，是衡量集群数据非独立同分布程度的核心指标。 2. 模式特异性分析（簇间聚合）： * 对censyn模式：分析了在集中式同步模式下，经过r次全局（簇间）聚合后，全局模型的收敛上界（定理1）。结果表明，其收敛速率与数据分布无关，但最终的残差误差δ与各集群的γj加权和有关。 * 对cenasy模式：分析了在集中式异步模式下，聚合器以不同频率ψj参与全局聚合时模型的收敛上界（定理2）。结果显示，收敛因子κ(x) 不仅与数据分布（通过βj）有关，还与各聚合器的参与频率ψj紧密相关。收敛速度受限于参与频率最低的聚合器。 * 对decsyn模式：分析了在分布式同步模式下，聚合器与其邻居交换模型时，加权全局模型的收敛上界（定理3）。其残差误差δ不仅依赖于各集群的γj，还通过一个由簇间拓扑和数据大小权重构成的矩阵S(x) 反复作用，表明拓扑结构对误差传播有复杂影响。 * 对decasy模式：分析了在分布式异步模式下，模型收敛的上界（定理4）。这是最复杂的情况，收敛性能同时受到各聚合器参与频率ψj和簇间拓扑S(x) 的共同影响。 * 关键产出：最终，研究团队将四种模式的收敛上界统一表达为一个标准形式：f(x, w0, t) = κ(x)(f(w0) - f*) + δ(x)。其中，κ(x)为收敛因子，反映收敛速度；δ(x)为残差误差，反映最终能收敛到最优解多近的邻域。κ(x)和δ(x)的具体表达式因模式而异，并且都是聚类策略x的函数。

第二步：簇内聚合时隙共享调度策略优化 为了处理边缘异构性（计算和通信时间不同）和通信资源约束，研究团队为簇内聚合的上行链路（工作者上传模型给聚合器）设计了一个最优时隙共享调度算法。 * 方法与流程：该策略的核心思想是，在任何时刻，集群中只有一个工作者在占用信道向聚合器上传模型。由于工作者本地训练可以并行进行，因此调度顺序决定了整个簇内聚合的完成时间。研究人员将此问题建模为一个经典的单机调度问题。通过理论证明（定理5），最优调度策略是按照工作者本地训练完成时间（lc_i）的升序来安排他们的模型上传顺序。该策略能最小化集群内所有工作者完成模型上传和聚合的总时间，记为l_opt_j。

第三步：问题建模与统一聚类算法（FEDUC）设计 基于前两步的理论成果，研究团队将“为分层联邦学习寻找最优聚类”的问题形式化。 * 问题建模：目标是在给定的簇内聚合完成时间约束（l_opt_j(x) ≤ l_max_j）下，找到一个聚类策略x（即每个工作者分配给哪个聚合器），以最小化对应簇间模式下的收敛上界f(x, w0, t)。这是一个带有复杂约束的组合优化问题。 * 算法设计：为解决此问题，研究人员提出了名为FEDUC的启发式贪心算法。算法流程如下： 1. 输入：工作者数据量、数据分布（按类别）、各聚合器的完成时间阈值。 2. 初始化：所有工作者未分配集群。将所有工作者按其数据量降序排列成一个队列（优先处理数据量大的工作者有助于获得更好的整体解）。 3. 迭代分配：按顺序处理队列中的每个工作者。对于当前工作者vi，尝试将其临时分配给每一个聚合器sj。 4. 可行性检查：计算如果将vi分配给sj后，集群sj的预估最优完成时间l_opt_j。如果超过阈值l_max_j，则舍弃该分配。 5. 效益评估：对于所有可行的sj，计算此时整个系统的收敛上界f(x, w0, t)。 6. 决策：选择能使f(x, w0, t)最小的聚合器j*，将vi永久分配给该聚合器。 7. 输出：处理完所有工作者后，输出最终的聚类策略x。 FEDUC算法的时间复杂度为O(n log n + n*m)，能够在多项式时间内求得高质量的近似解。

第四步：实验验证 研究团队在模拟的边缘计算环境中进行了广泛的实验，以验证FEDUC算法的有效性。 * 实验设置： * 环境与拓扑：使用PySyft库模拟一个40m×40m区域，部署16个网格状分布的聚合器，100个随机分布的工作者。为cenasy模式设置了距离中心参数服务器不同距离的聚合器以模拟不同的参与频率；为decsyn模式定义了基于地理相邻性的簇间拓扑。 * 模型与数据：使用了逻辑回归和卷积神经网络模型，在MNIST和CIFAR-10数据集上进行测试。采用“标签倾斜划分”来模拟工作者间的非独立同分布数据。 * 对比基准：与两种经典聚类方法对比：1) 通信感知聚类（ComAw）：将工作者分配给通信时间最短的聚合器；2) 数据感知聚类（DataAw）：根据数据分布相似性进行聚类，旨在使集群间数据接近独立同分布。 * 评估指标：损失函数曲线、测试准确率、达到目标准确率所需的训练时间。 * 实验流程：在四种簇间聚合模式下，分别运行采用FEDUC、ComAw和DataW聚类策略的分层联邦学习训练过程，记录并比较各项性能指标。

四、 主要研究结果 理论分析与实验验证共同支撑了本研究的主要结论。

1. 理论分析结果： * 定量关系明确：成功推导出了四种簇间聚合模式收敛上界与关键因素（数据非独立同分布度ξj、参与频率ψj、拓扑矩阵S(x)）之间的精确数学关系（见定理1-4）。这为算法设计提供了直接的优化目标。 * 统一框架建立：将所有模式的收敛性能统一表达为f(x, w0, t) = κ(x)(f(w0) - f*) + δ(x)，使得针对不同模式的聚类优化可以在同一个理论框架下进行。 * 关键推论：从理论公式中得出重要推论，指导算法设计：a) 对于异步模式（cenasy， decasy），将工作者更多地聚类到参与频率高的聚合器可以加速收敛（降低κ(x)）；b) 减少集群间的数据非独立同分布程度可以降低残差误差δ(x)；c) 对于分布式模式，拓扑结构通过矩阵S(x)影响δ(x)的累积。

2. 算法与实验验证结果： * FEDUC聚类特性：实验测量了不同算法聚类后的结果。如图5所示，FEDUC在各模式下产生的集群间数据差异（用地球移动距离衡量）均接近专门优化此目标的DataW算法，远优于ComAw。如图6所示，FEDUC的最大簇内聚合完成时间在各模式下均显著低于DataW，且略优于或接近ComAw。这说明FEDUC成功地在平衡数据分布和通信延迟方面取得了优异效果。 * 对异步模式频率的适应性：如图7所示，在cenasy模式下，FEDUC算法成功地将更多工作者分配给了参与频率更高的聚合器（如S9， S10），这与理论推论1一致，从而优化了收敛因子。 * 对分布式模式拓扑的适应性：如图8所示，在decsyn模式下，FEDUC算法倾向于将工作者分配给拥有更多邻居连接（更高连接度）的聚合器，这有助于在分布式拓扑中更好地传播和融合模型信息。 * 训练性能大幅提升：核心性能对比实验表明，FEDUC算法显著加速了所有四种模式的训练。 * 在censyn模式下，相比最好的基准方法（DataW），FEDUC将训练速度提升了1.79倍。 * 在cenasy模式下，相比基准方法，提升达到5.88倍。这突出显示了在异步场景下考虑参与频率的巨大收益。 * 在decsyn模式下，提升达到了惊人的7.39倍，证明了在分布式同步结构中联合优化数据分布和拓扑的重要性。 * 在decasy模式下，提升为5.32倍。 * 在所有案例中，FEDUC最终达到的模型测试准确率也均不低于或优于基准方法。这些实验数据强有力地支持了FEDUC算法的普适性和优越性。

五、 研究结论与价值 本研究得出核心结论：通过深入分析不同簇间聚合模式的收敛性，并设计与之适配的统一聚类算法FEDUC，可以系统地、显著地提升分层联邦学习在各种操作模式下的训练效率。

研究的科学价值在于： 1. 理论贡献：首次系统化地给出了四种主流分层联邦学习聚合模式在非独立同分布数据、异构环境下的收敛性分析，建立了收敛性能与数据分布、参与异步性、网络拓扑之间的定量关系模型，填补了该领域的理论空白。 2. 方法论贡献：提出了首个面向分层联邦学习的统一聚类框架。FEDUC算法不是针对某一特定模式的专用方案，而是一个可配置、可适配的通用解决方案。它将通信约束、数据分布优化、异步频率感知和拓扑结构感知等多个优化目标融入一个统一的贪心决策框架中。 3. 应用价值：为在实际边缘计算系统中部署高效、鲁棒的分层联邦学习提供了强有力的工具。系统设计者无需再为不同的通信模式（同步/异步）和架构（集中/分布式）分别设计和调优聚类策略，可以直接采用FEDUC来获得接近最优的集群组织方案，从而降低部署复杂度，提升系统性能。

六、 研究亮点 1. 问题的前瞻性与系统性：敏锐地抓住了分层联邦学习中“聚类策略需适配多种聚合模式”这一未被充分研究但至关重要的问题，并进行了系统性的探索。 2. 理论与实践的紧密结合：研究没有停留在理论分析，也没有仅进行经验性的算法设计，而是以深刻的理论分析（定理1-4）为指导，推导出算法设计的原则（推论），进而开发出高效的算法（FEDUC），最后通过详实的实验验证了理论的有效性和算法的优越性。 3. 创新性的统一框架：提出的FEDUC算法是本研究最大的亮点之一。其“统一性”体现在能够通过调整目标函数f(x, w0, t) 中的κ(x)和δ(x)表达式，无缝适应四种不同的簇间聚合模式，这是对现有单一目标聚类方法的重要超越。 4. 对实际因素的全面考量：研究模型全面考虑了边缘计算中的三大挑战（异构性、资源约束、非独立同分布），并在算法中同时考虑了通信时间约束和数据分布优化，使得解决方案具有很高的实用价值。

七、 其他有价值的补充 论文还讨论了FEDUC算法对工作者移动性的潜在处理方式，即通过记录工作者的历史位置信息并定期重新运行聚类算法来更新集群分配，这增强了算法在动态环境下的适用性。此外，研究虽然主要针对凸损失函数进行了理论分析，但在实验部分成功地将所提方法应用于非凸的CNN模型，并取得了显著效果，表明了该方法具有超越理论假设范围的良好泛化能力。