paperFL

基本信息

标题: “REFL: Resource-Efficient Federated Learning”
作者: Ahmed M. Abdelmoniem, Atal Narayan Sahu, Marco Canini, Suhaib A. Fahmy
作者所属机构:

  • Ahmed M. Abdelmoniem: Queen Mary University of London, Assiut University, Egypt (主要工作在KAUST)
  • Atal Narayan Sahu, Marco Canini, Suhaib A. Fahmy: KAUST (King Abdullah University of Science and Technology)

会议: Eighteenth European Conference on Computer Systems (EuroSys '23)
会议时间和地点: 2023年5月8日-12日，意大利 罗马
DOI: 10.1145/3552326.3567485
关键词: 计算方法学, 机器学习, 分布式算法

论文二十问

  1. 论文试图解决什么问题？
    论文试图解决联邦学习（Federated Learning, FL）中的资源效率问题。具体来说，目标是优化FL系统在异构环境中的资源使用效率，以减少达到目标准确率所需的计算资源，而不显著影响达到目标准确率的时间

  2. 这是否是一个新的问题？
    是的，这是一个新问题。尽管已有研究关注提高FL的收敛速度和系统效率，但这些方法往往忽略了最大化可用资源利用率和减少浪费的工作。论文提出的资源高效联邦学习（REFL）方法首次考虑了参与者预测可用性并将其作为选择基础

  3. 这篇文章要验证一个什么科学假设？
    论文要验证的科学假设是，通过智能参与者选择（Intelligent Participant Selection, IPS）和感知延迟聚合（Staleness-Aware Aggregation, SAA）可以在不显著影响时间到准确率的情况下，优化FL系统的资源使用效率。

  4. 有哪些相关研究？如何归类？谁是这一课题在领域内值得关注的研究员？
    相关研究主要包括以下几类：

    • 提高收敛速度的研究
    • 改进系统效率的研究
    • 选择具有高统计和系统效用的参与者

    值得关注的研究员包括：

    • Fan Lai, Mosharaf Chowdhury 等
    • Timothy Yang, Galen Andrew, Françoise Beaufays 等

  5. 论文中提到的解决方案之关键是什么？
    论文中的关键解决方案是引入REFL方法，其中包括智能参与者选择（IPS）和感知延迟聚合（SAA）两个主要组件。IPS通过选择未来可能性最低的参与者来优化资源使用，SAA则通过处理过期更新以提高统计效率

  6. 论文中的实验是如何设计的？
    实验采用了两种实验设置：过度承诺（OC）和动态报告（DL）。在OC设置中，FL服务器超额选择参与者，并等待所有参与者的更新；在DL设置中，服务器选择目标参与者数量，并在预设的报告截止日期前聚合所有收到的更新

  7. 用于定量评估的数据集是什么？代码有没有开源？
    用于定量评估的数据集包括Google Speech、Open Image、Reddit、StackOverflow等。代码开源在FedScale框架中，该框架用于FL系统的模拟和评估。

  8. 论文中的实验及结果有没有很好地支持需要验证的科学假设？
    是的，实验结果表明，REFL在减少资源使用的同时，能够在不同数据映射和实验设置下实现更好的模型质量，从而验证了科学假设

  9. 这篇论文到底有什么贡献？
    论文的主要贡献包括：

    • 提出了考虑参与者可用性的智能选择方法
    • 设计了感知延迟聚合算法以优化资源使用
    • 提供了在异构环境中提高FL系统资源效率的方法

  10. 下一步呢？有什么工作可以继续深入？
    下一步的工作可以包括：

    • 对超参数进行详细的敏感性分析和消融研究
    • 在更大规模和更多样化的实际环境中测试REFL方法
    • 探索其他可能的优化策略，如动态调整参与者目标数量等

  11. 要了解深入，一个模型为什么好？
    这个模型之所以好是因为它通过智能参与者选择（IPS）和感知延迟聚合（SAA）方法，在保证模型收敛速度的同时，显著减少了资源的浪费。IPS选择未来可用性最低的参与者，最大化利用可用资源；SAA处理延迟的更新，提高统计效率。

  12. 以前的模型为什么不好？
    以前的模型存在以下几个问题：

  • 资源浪费：例如SAFA方法虽然允许半异步更新，但会导致大量计算资源浪费，因为会选择所有可用的参与者，最终丢弃大部分计算更新。
  • 时间效率低：FedAvg方法虽然资源浪费少，但在参与者数量少时收敛时间显著增加，增加参与者数量又会导致资源使用显著增加。

  1. 哪个关键点对性能提升最大？
    感知延迟聚合（SAA）对性能提升最大。SAA通过处理延迟更新，显著提高了统计效率，使得即使在非独立同分布（non-IID）数据环境下，也能显著提高模型质量和资源效率。

  2. 编程怎么实现？
    编程实现包括以下几个步骤：

  • 智能参与者选择（IPS）：基于未来可用性预测模型，选择预期可用性最低的参与者。
  • 感知延迟聚合（SAA）：在聚合更新时考虑延迟更新，通过设定阈值和调节权重来处理延迟更新。
    实现代码集成在FedScale框架中，并作为Python模块。

  1. 论文源代码和paper匹配度怎么样、都覆盖了吗？
    论文的源代码在FedScale框架中开源，并覆盖了论文中提出的主要方法和实验设置，能够重现论文中的实验结果。

  2. 哪些数学运算是关键的？
    关键的数学运算包括：

  • 更新权重计算：根据延迟和统计效用调整权重。
  • 梯度计算和聚合：计算每轮更新的梯度并进行聚合，以确保模型更新的有效性。
  1. 整个全流程是怎么走的？
    全流程包括：
  • 参与者选择：通过IPS选择未来可用性最低的参与者。
  • 本地训练：参与者在本地进行模型训练并生成更新。
  • 延迟更新处理：通过SAA处理延迟更新，确保统计效用。
  • 模型聚合：服务器聚合更新并更新全局模型。
  1. 数据是怎样流动的？其中是怎样变换的？各个变换有什么实际意义？
  • 数据流动：数据在本地进行训练，生成的模型更新发送到服务器。
  • 数据变换：在聚合过程中，通过权重调整处理延迟更新，提高统计效用和资源利用率。
  • 实际意义：提高FL系统的资源效率，减少资源浪费，保证模型质量。
  1. 既要关注具体实现思路、也要关注上层抽象意义。作者灵感从何而来？
  • 具体实现思路：采用智能参与者选择和感知延迟聚合，提高资源利用效率。
  • 上层抽象意义：解决FL系统中资源浪费和时间效率低的问题。
  • 灵感来源：从现有方法的缺陷中获取灵感，例如SAFA和FedAvg方法的资源浪费和时间效率问题。
  1. 作者思考路线如何？
    作者通过分析现有FL系统的缺陷，提出了REFL方法，并通过智能参与者选择和感知延迟聚合，优化资源使用效率。实验结果验证了所提出方法的有效性，解决了资源浪费和时间效率低的问题。

Abstract

联邦学习（Federated Learning, FL）通过使用本地数据进行分布式训练，从而增强隐私保护并减少通信。然而，随着部署规模的扩大，它在数据分布、设备能力和参与者可用性方面呈现出诸多挑战，这些挑战会影响模型的收敛性和偏差。现有的FL方案采用随机参与者选择来提高选择过程的公平性，但这可能导致资源使用效率低下和训练质量下降。在这项工作中，我们系统地解决了FL中的资源效率问题，展示了智能参与者选择和整合延迟参与者更新的好处。我们证明了这些因素如何在提高资源效率的同时改善训练模型的质量。

1.Introduction

近年来，分布式机器学习（ML）部署旨在将计算推向数据源，以增强隐私和安全性【6, 27】。使用这种方法训练模型被称为联邦学习（Federated Learning, FL）。由于参与设备的高度异质性，FL带来了各种挑战，从强大的边缘集群和智能手机到低资源的物联网设备（如监控摄像头、传感器等）。这些设备生成并存储用于训练共享ML模型的应用数据。苹果、谷歌和Facebook等大型服务提供商部署FL来训练计算机视觉（CV）和自然语言处理（NLP）模型，用于图像分类、目标检测和推荐系统等应用【15-17, 20, 59, 60, 68】。FL还被用于训练分布式医学影像数据【39】和智能相机图像【25】的模型。

FL训练的生命周期如下。首先，FL操作员使用独立数据集构建模型架构并确定超参数。然后，参与者在多个集中管理的轮次中进行模型训练，直到获得满意的模型质量。FL的主要挑战在于大量参与者在计算能力和数据分布方面的异质性，这会影响训练的性能【6, 27】。

时间到准确率（Time-to-accuracy）是一个关键的性能指标，也是该领域许多工作的重点【27, 32, 37, 64, 67】。它取决于训练的统计效率和系统效率。前者受参与者数量、小批量大小、本地步数的影响。这些因素通常作为超参数来针对特定FL任务进行调整。系统效率主要由完成训练轮次的时间决定，这取决于选择哪些参与者以及它们是否成为无法按时完成更新的“拖尾者”。通常会设置报告截止日期以限制轮次时长，但如果只有不足数量的参与者在截止日期前完成，整个轮次将失败并从头再来。由于紧迫的截止日期可能导致更多轮次失败，这可以通过超额选择每轮参与者数量来缓解，以增加在截止日期前完成的概率。失败的轮次和超额的参与者会导致计算浪费，这在以前的FL方法中大多被忽视了。对时间的关注还导致了不适应非独立同分布（non-IID）数据分布的方案，因为它们偏向某些学习者【36】。最后，参与者的可用性各异，这在处理数据异质性时需要考虑【6, 27, 36, 67】。

上述所有因素都会导致资源浪费——学习者进行的训练工作未能增强模型，无论是因为最终被丢弃的更新还是数据分布不佳。我们认为，这种资源浪费阻碍了用户参与FL，并使FL系统的扩展到更大规模和更多样化的计算能力变得困难。我们旨在优化FL系统在异构环境中的资源到准确率比率。这意味着在不显著影响时间到准确率的情况下，减少达到目标准确率所消耗的计算资源。通过在设计中考虑异质性，我们还希望展示对学习者中现实数据分布的改进鲁棒性。

现有努力旨在提高收敛速度（即在更少轮次内提升模型质量）【37, 61】或系统效率（即减少轮次时长）【42, 43】，或选择具有高统计和系统效用的学习者【32】。这些方法忽略了最大化利用可用资源的重要性，同时减少浪费的工作量。为了解决这些问题，我们提出了资源高效联邦学习（REFL），这是一种在不牺牲统计和系统效率的情况下，最大化FL系统资源效率的实用方案。REFL通过将参与者更新的收集与模型更新的聚合分离来实现这一目标。 REFL还智能地选择那些未来可用性最小的参与者。据我们所知，这是第一个以预测可用性为基础进行FL参与者选择并展示其重要性的方法。REFL可以作为现有FL系统的插件模块进行集成，并兼容现有的FL隐私保护技术【7, 8】。

总之，我们的主要贡献如下：

  1. 我们强调了在FL中学习者有限能力和可用性的资源使用重要性，并提出REFL以智能选择参与者并高效利用其资源。
  2. 我们提出了感知延迟聚合和智能参与者选择算法，以在最小化对时间到准确率影响的情况下改进资源使用。
  3. 我们使用真实世界的FL基准测试实现并评估了REFL，并将其与最先进的解决方案进行比较，以展示其为FL系统带来的好处。

2.Background

我们回顾了FL生态系统，重点关注系统设计方面的考虑，并基于真实数据集的经验证据突出了主要挑战。我们通过强调现有设计的主要缺陷来激发我们的工作。

2.1 FL

我们考虑了在联邦平均（FedAvg）[6, 43]中引入的流行FL设置。FedAvg模型由一个（逻辑上）集中化的服务器和分布式学习者组成，例如智能手机或物联网设备。学习者本地维护私有数据，并协作训练一个共享的全局模型。FL的一个关键假设是缺乏信任，这意味着训练数据不应离开数据源，任何可能的私有数据泄露在通信过程中都应避免。

全局模型的训练是在一系列轮次中进行的。如图1所示，在每轮训练开始时，服务器会等待（在选择窗口期间）足够数量的可用学习者进行签到。然后，服务器从签到的学习者中抽取一个子集——称为参与者——在当前轮次中进行训练。参与者获取最新版本的模型以及任何必要的配置（例如超参数设置）。

每个参与者在其本地数据上训练模型指定的轮数，并生成一个模型更新（即全局模型的增量），然后将其发送给服务器。服务器等待直到目标数量的参与者发送他们的更新来聚合它们并更新全局模型。此过程结束当前轮次，并在每轮中重复上述步骤，直到达到某个目标（例如目标模型质量或训练预算）。

为了确保进展，服务器通常会等待模型更新直到报告截止日期。拖尾者可能会在截止日期之后到达的更新将被丢弃。如果在截止日期前收到的参与者更新至少达到目标数量，则该轮次被认为是成功的，否则该轮次将被中止并重新尝试。

FL设置与传统的ML训练不同，因为分布式学习者可能表现出以下类型的异质性：

  1. 数据异质性：学习者通常拥有数量、类型和分布各异的数据点；
  2. 设备异质性：由于硬件和网络能力的不同，学习者设备具有不同的速度；
  3. 行为异质性：学习者的可用性在各轮次之间变化，并且可能有学习者在变得不可用时放弃当前轮次。

异质性给FL系统设计者带来了几个挑战，因为每轮选择的参与者会极大地影响训练模型的质量和训练速度。下面我们简要回顾了现有的设计，这些设计作为我们不同方法的背景动机（第3节）。我们在第8节讨论了其他相关工作。

这张图展示了联邦学习（FL）中的一个训练轮次的流程:

  • FL服务器：图中左上角的FL服务器负责管理整个训练过程。
  • 学习者（Learners）：不同颜色的线代表不同的学习者。
  • 轮次i：图中的时间线从左到右表示一个训练轮次（Round i）的进行。

  1. 选择阶段（Selection）： 学习者在选择窗口内进行签到（Check-in）。此时，服务器从签到的学习者中选取一部分作为参与者（Participants）;未被选择的学习者标记为“Not chosen”，这些学习者不参与当前轮次的训练。

  2. 任务分配（Task）：被选择的学习者接收任务，即获取最新的模型版本和训练所需的配置参数（如超参数设置）。

  3. 训练阶段（Training）：参与者使用本地数据进行训练。图中绿色和橙色线表示两个参与者在进行本地训练。训练完成后，生成模型更新（即全局模型的增量）。

  4. 报告阶段（Reporting）：参与者在报告截止日期前（Reporting deadline）提交更新。只有在截止日期前收到的更新才会被聚合;图中蓝色线表示按时报告的参与者，其更新会被用于聚合;报告延迟的更新（Late reporting）不会被聚合，图中橙色线表示了延迟报告的参与者。

  5. 聚合阶段（Aggregation）：服务器聚合收到的更新并更新全局模型。此时，当前轮次结束，进入下一个轮次（Round i+1）。

2.2 现有的联邦学习系统

考虑到学习者的不可靠性，SAFA [64] 允许拖尾参与者进行半异步更新。SAFA 颠覆了 FedAvg 的参与者选择过程：它对所有学习者进行训练，并在预设百分比的学习者返回他们的更新时结束一个轮次。SAFA 允许参与者在轮次截止日期后报告，在这种情况下，更新会被缓存并在后续轮次中应用。然而，SAFA 只容忍在设定的延迟阈值内的学习者更新。因此，SAFA 通过仅等待部分参与者的更新来减少轮次时长，同时缓存确保拖尾参与者的计算努力不被完全浪费，并能够提升统计效率。

FLeet [13] 允许延迟更新，但采用了一个阻尼因子，随着延迟增加，赋予更新较小的权重。这有利于不丢弃超过延迟阈值的更新。然而，他们的 AdaSGD 协议不直接兼容传统的 FL 设置，如 FedAvg，且 FLeet 在每个本地小批量后同步模型梯度。

Oort [32] 使用一种偏向高效用学习者的参与者选择算法。Oort 中学习者的效用包括统计效用和系统效用。统计效用通过训练损失作为代理来衡量，而系统效用则以完成时间的函数来衡量。Oort 优先选择快速学习者以减少轮次时长。同时，它使用一个节奏算法，在需要统计效率时，可以通过延长轮次时长来包括未探索的（或慢速的）学习者。

3 资源高效联邦学习的案例

我们通过强调系统效率和资源多样性之间的权衡作为FL中相互冲突的优化目标来激发REFL的研究动机。在现有的最先进FL系统中，展示了这两个目标的极端，说明它们在常见的FL基准测试中是如何不足的。

3.1 系统效率与资源多样性

当前的FL设计要么旨在减少时间到准确率（即系统效率）【32】，要么旨在增加学习者池的覆盖范围以增强数据分布并公平地分配训练工作负载（即资源多样性）【37, 64, 65】，但并未考虑学习者的工作浪费成本。第一个目标导致对某些类别学习者的歧视性方法，偏向选择计算速度快的学习者或模型更新质量高的学习者（即那些具有高统计效用的学习者）【32, 37】。第二个目标则需要将计算理想地分散到所有可用学习者，但代价是可能导致更长的轮次时长【64, 65】和显著的工作浪费。

这两个相互冲突的目标为FL系统设计者带来了挑战性的权衡。在极端的一端，Oort积极优化系统效率，忽略学习者数据的多样性，以提高时间到准确率。这种极端的影响是，由于选择公平性差，对高水平数据异质性具有较低的鲁棒性，可能会生成一个无法覆盖大多数学习者数据的全局模型。在另一端，SAFA放弃了预训练选择，选择所有可用学习者以最大化资源多样性，但代价是显著增加的资源浪费。

为了在这两个极端之间取得平衡，FL系统应在不显著牺牲系统效率的情况下，实现足够水平的资源多样性。 我们的目标是综合现有系统提供的机会，设计一种新的整体方法，能够同时实现资源多样性和系统效率目标，同时将累计资源使用量作为主要指标。我们首先展示现有系统未能实现这两个目标并导致显著的资源浪费。我们还强调了它们在我们设计REFL时所提供的机会。

3.2 过时更新与资源浪费

借鉴异步方法【19, 65】，SAFA允许拖尾参与者通过过时更新为全局模型做出贡献。我们首先评估了SAFA的资源使用情况（即学习者在训练中累计花费的时间）和资源浪费情况（即学习者生成但未纳入模型的更新所花费的时间）。我们将SAFA的性能与一种假设完美预言（即知道哪些过时更新最终会被聚合，不会超过过时阈值）的版本（称为SAFA+O）进行比较。我们将过时阈值设置为5轮，目标参与者百分比设置为10%。我们使用Google提供的语音数据集（以下简称Google Speech基准测试）【63】，并使用FedScale的数据到学习者映射【31】（详见表1和第5节）。我们将学习者总数设置为1000，轮次截止时间设置为100秒。我们使用真实世界的用户行为轨迹来模拟学习者的可用性动态【67】。

图2显示了资源使用（x轴）和最终测试准确率（y轴）；图中的线条标注了达到最终准确率所需的时间（这一风格在本文其他图表中也有体现）。由于轮次时间受截止日期限制，SAFA和SAFA+O的运行时间相等。值得注意的是，SAFA在资源使用方面效率低下，消耗的资源几乎是SAFA+O的5倍，才能达到相同的最终准确率。通过选择所有可用的学习者，然后最终丢弃大量计算的更新，SAFA浪费了约80%的学习者计算时间。图中还包括了FedAvg随机选择10和100个参与者的运行情况。尽管资源浪费较低，但FedAvg使用10个参与者的运行时间显著增加（5倍），以达到与SAFA相同的准确率；可以通过使用100个参与者来权衡资源使用和运行时间，以类似于SAFA+O的资源使用达到相同的准确率。我们注意到，均匀随机的数据映射产生了类似的结果。

机会。原则上，允许过时更新可以减少轮次时长并实现更好的时间到准确率，同时保留拖尾者的贡献。然而，主要挑战在于平衡参与者数量以避免显著的资源浪费。这很困难，因为系统必须估算设备上的训练时间，并考虑学习者掉线或超过过时阈值的概率。这表明，除了处理过时更新外，我们还必须直接解决资源多样性的问题。


这张图展示了SAFA、SAFA+O以及分别有10个和100个参与者的FedAvg在资源使用方面的比较。图中x轴表示累计资源使用（以小时为单位，并采用对数刻度），y轴表示测试准确率（百分比）。每种方法达到目标准确率的运行时间以彩色注释的形式显示在最终数据点附近。

FedAvg_10在较低的资源使用下，准确率上升较慢，需要较多时间（8.6小时）才能达到目标准确率; FedAvg_100在资源使用接近100小时时，迅速达到较高的准确率，显示出较高的资源效率; SAFA虽然可以在较短时间内（1.4小时）达到目标准确率，但其资源使用极其高效不佳，达到目标准确率所需资源接近1000小时; SAFA+O在资源使用和时间效率上均表现出色，资源使用显著低于SAFA，且在接近200小时的资源使用下达到了较高的准确率（50%），并在1.7小时内完成。

3.3 参与者选择与资源多样性

许多现有的FL系统使用统一随机采样器来选择参与者【6, 9, 68】。如Oort所述【32】，这种简单策略容易选择计算能力不同的学习者，导致拖尾者延长轮次时长。另一方面，Oort的方法通过选择快速学习者，虽然能减少轮次时间，但会使模型偏向于某个子集的学习者，从而降低数据多样性。

为了实践验证这一点，我们比较了Oort的参与者选择器与随机采样器（Random）。我们使用Google Speech基准测试进行1000轮训练，并比较两种不同数据映射情况下的效果。在第一种情况下，数据点根据FedScale的客户端到数据的映射【31】分配给学习者。在第二种情况下，数据点均匀分布在参与者之间，但每个参与者被限制只能拥有约10%的标签（非IID）。为了强调采样策略的效果，我们设置所有学习者始终可用；稍后我们会研究可用性动态的影响。


图3显示了资源使用对测试准确率的影响。在FedScale的数据映射场景中，Oort显著优于随机选择，因为Oort通过利用快速学习者大大减少了轮次时长。相反，在非IID情况下（标签限制映射），随机选择由于较高的资源（和数据）多样性，在可容忍的运行时间增加下实现了更高的准确率。

参与者的可用性影响全局模型中表示的全局数据分布【21】。我们分析了来自【67】的一个涉及超过136K用户的一周FL应用的设备行为轨迹，发现70%的学习者最多可用10分钟，而50%的学习者最多可用5分钟。这意味着实际上FL轮次通常应持续几分钟以获取大多数参与者的更新。分析还表明，低可用性学习者可能需要特别考虑，以增加唯一参与者的数量，而不会对整体训练时间产生不利影响。

我们现在在Google Speech基准测试的FedScale和非IID情况下重复类似的实验，并对比在两种条件下Oort和Random参与者选择方法的执行：1）所有学习者都可用（AllAvail）；2）学习者的可用性基于设备行为轨迹的动态变化（DynAvail）。图4显示，在FedScale情况下，学习者的可用性对结果没有显著影响，因为学习者持有的数据点具有可比的分布。然而，在非IID情况下，学习者的可用性对模型准确率有显著影响（我们观察到10个百分点的下降）。

机会。为了实现更好的模型泛化性能，模型应联合训练来自大量学习者数据样本。虽然Oort关于知情参与者选择的见解导致更快的轮次时长，但需要更多考虑学习者动态可用性，以确保更广泛的学习者覆盖。这表明，除了学习者的多样性和计算能力外，我们还需要有效优先考虑可用性有限的学习者。

4 REFL 设计

REFL 的目标是通过最大化资源多样性来增强 FL 训练过程的资源效率，同时不牺牲系统效率。REFL 通过减少延迟参与者的资源浪费并优先考虑那些可用性较低的参与者来实现这一目标。它利用一种有理论支持的方法，根据更新质量来整合过时更新，从而帮助提高训练性能。它提出了一种聚合权重的缩放规则，以减轻过时更新的影响。

REFL 的两个核心组件是：

  1. 智能参与者选择（IPS）：优先选择那些能改善资源多样性的参与者。
  2. 感知延迟聚合（SAA）：在不影响时间到准确率的情况下提高资源效率。

为了说明主要区别，图5对比了 REFL 和 Oort。首先，REFL 使学习者能够跟踪可用性模式，帮助预测未来的可用性。因此，REFL 能够优先选择那些可用性最低的参与者（如图5中的 ■ 和 ■），以最大化不同学习者数据分布的训练覆盖率。REFL 还允许拖尾参与者在设定的轮次时长之外提交延迟结果（如图5中的 ■ 和 ■）。与 Oort 不同，Oort 因为设备能力较差而丢弃这些更新，而这种方法减少了拖尾者的工作浪费，这些拖尾者可能拥有对模型训练非常有价值的数据。

4.1 智能参与者选择（IPS）

智能参与者选择（IPS）通过增加资源多样性，使全局模型能够捕获广泛的学习者数据分布。此外，它还提供了一个可选组件，通过智能适应每轮次的参与者数量，进一步减少资源浪费。

最少可用性优先算法1描述了IPS组件如何从大量可用学习者中智能选择参与者。每个学习者定期训练一个模型来预测其未来的可用性。当学习者 (l) 签到时，服务器发送轮次时长的运行平均估计值 (\mu_t)。学习者使用预测模型确定其在时间段 ([\mu_t, 2\mu_t]) 内的可用性概率，并将其报告给服务器。在选择窗口结束时，服务器按升序排序学习者的概率 (P)，并随机打乱概率相同的学习者。然后，服务器选择前 (N_t) 个学习者参与本轮训练（即最少可用的学习者）。类似于Google的FL系统【6】，参与者在提交更新后，会有几个轮次（例如5轮）不与服务器签到。

可用性预测模型预测模型应简单、开销低，并在学习者设备上本地训练以保护隐私。在本工作中，我们不提出新的可用性模型，而是使用现成的时间序列模型来预测学习者的未来可用性。线性模型如自回归积分滑动平均（ARIMA）或平滑ARIMA可以在从设备事件（如空闲、充电、连接WIFI、屏幕锁定等）中收集的最小特征集上训练【22, 23】。我们使用基于上述线性模型的Prophet预测工具【58】。我们在Stunner数据集上训练一个预测模型，这是一个包含大量移动用户设备事件（例如设备的充电状态）的大型数据集【57】。给定未来的时间窗口，模型生成设备在查询时间窗口内的充电状态（即可用性）的概率。在第5节中，我们展示了训练的模型能够提供高准确度的可用性预测。

自适应参与者目标（APT） IPS可以通过调整操作员预设的目标参与者数量 (N_0) 来优化资源使用。首先，服务器更新其轮次时长的移动平均估计 (\mu_t = (1 - \alpha)D_{t-1} + \alpha\mu_{t-1})，其中 (D_{t-1}) 是前一轮的时长 (t - 1)。然后，在开始第 (t) 轮之前，服务器向每个当前拖尾者 (s \in L_s)（从第 (t-1) 轮开始）探测其预计剩余上传时间 (RT_s)。接下来，服务器计算有多少拖尾者（(B_t)）可以在当前轮次内完成（即 (RT_s \leq \mu_t)）。因此，目标参与者数量为第 (t) 轮调整为 (N_t = \max (1, N_0 - B_t))。这确保了每轮大约聚合 (N_0) 个更新（即总的新鲜和过时更新）。在大规模场景中，这可能会进一步改善资源消耗。注意，无论客户的可用性如何，APT都是一个附加方案，以避免过度承诺参与者，从而进一步减少资源消耗。

算法1

4.2 时效感知聚合 (SAA)

该组件使参与者可以在回合截止日期之后提交更新，并将这些过期的更新与新的更新一起处理。由于模型在过期更新到达时可能会发生显著漂移，因此这些过期的更新可能会带来噪音。为了减轻这种影响，我们基于一个增强因子对过期更新进行加权(见第4.2.3节)。

我们还提供了一个收敛性分析以证实时效的好处。我们独立于其他REFL组件分析了这一效应，因为所有REFL组件是互补的。由于FedAvg[6, 43]是最著名的FL算法之一，我们分析了包含时效的FedAvg（称为过期同步FedAvg，参见算法2）。在标准假设下，我们的收敛性分析表明，每轮由于时效引起的误差很小，因此梯度差异不大（见引理3）。由于每轮的这种小误差，我们在定理1中展示了过期同步FedAvg以与FedAvg相同的渐近速率收敛。

4.2.1 收敛性分析

我们从理论上证明了带有过期更新的FedAvg可以收敛并获得收敛速率。考虑以下包含总共 ( m ) 台设备的联邦优化问题：

[
\min_{x \in \mathbb{R}^d} f(x) …= \frac{1}{m} \sum_{j \in [m]} f_j(x), \tag{1}
]

其中 ( f_i(x) = E_{z_i \sim D_i} [l(x; z_i)] ) 表示在从 (D_i) 中采样的输入 ( z_i ) 上评估的损失函数 ( l(x; z_i) )。

算法2给出了求解(1)的过期同步FedAvg的伪代码。在这里， ( g_{i, t, k} ) 表示在第 ( i ) 个参与者在第 ( t ) 轮局部迭代第 ( k ) 次计算的随机梯度，使得 ( g_{i, t, k} = \nabla f(y_{i, t, k}) + \xi_{i, t, k} )，并且 ( E[\xi_{i, t, k} | x_{i, t, k}] = 0 )。

模型更新的时效被建模为一个回合延迟。为了便于说明，我们在算法2中考虑了固定的 ( \tau ) 回合延迟。然而，我们的分析适用于由 ( \tau ) 限制的可变延迟。

假设：我们对损失函数考虑以下一般假设。

假设1.（光滑性）在每个参与者 ( i \in [n] ) 处的函数 ( f_i : \mathbb{R}^d \rightarrow \mathbb{R} ) 是 ( L ) 平滑的，即对于每个 ( x, y \in \mathbb{R}^d )，我们有：

[ f_i(y) \leq f_i(x) + \langle \nabla f_i(x), y - x \rangle + \frac{L}{2} |y - x|^2. ]

假设2.（全局最小值）存在 ( x^* )，使得 ( f(x^) = f^ \leq f(x) )，对于所有 ( x \in \mathbb{R}^d )。

假设3.（有界噪声）[54] 对于每个随机噪声 ( \xi_{i, t, k} )，存在 ( M \geq 0 )， ( \sigma^2 > 0 )，使得 ( E[|\xi_{i, t, k}|^2 | x_t] \leq M |\nabla f(x_{i, t, k})|^2 + \sigma^2 )，对于所有 ( x_t \in \mathbb{R}^d )。

4.2.2 收敛性结果

下一个定理提供了非凸收敛速率。

定理1. 设假设1, 2 和 3 成立。然后，对于算法2，我们有：

[
\frac{1}{nT K} \sum_{t=0}^{T-1} \sum_{i=1}^{n} \sum_{k=0}^{K-1} E[|\nabla f(y_{i, t, k})|^2] = O\left( \frac{\sigma \sqrt{L (f(x_0) - f^*)}}{\sqrt{nT K}} + \max\left{ \frac{L \sqrt{\tau K (n \tau K + M)}}, \frac{L (K + M/n)}{T K} \right} \right).
]


我们的分析基于误差反馈框架[54]，该框架又受到扰动迭代分析[41]的启发。我们首先定义过期同步FedAvg的更新：

[ v_t = \begin{cases}
0, & \text{如果} t < \tau \
\frac{1}{n} \sum_{i=1}^{n} \sum_{k=0}^{K-1} g_{i, t-\tau, k}, & \text{否则}.
\end{cases}
]

使用这个 ( v_t ) 的定义，我们有：

[ x_{t+1} = x_t - v_t \quad \forall t. ]

让我们也定义由于异步引起的误差 ( e_t ) 为：

[ e_t = \sum_{j=1}^{\tau} \mathbf{1}{(t-j) \geq 0} \left( \frac{\gamma}{n} \sum{i=1}^{n} \sum_{k=1}^{K} g_{i, t-j, k} \right). ]

其中 ( \mathbf{1}_{Z} ) 表示集合 ( Z ) 的指示函数。

下一个引理中的递归关系对于算法2的扰动迭代分析至关重要。

引理1. 定义迭代序列 ( {x_t}{t \geq 0} ) 为 ( x_t = x_t - e_t )，其中 ( x_0 = x_0 )。然后 ( {x_t}{t \geq 0} ) 满足递归关系：

[ x_{t+1} = x_t - \frac{\gamma}{n} \sum_{i=1}^{n} \sum_{k=0}^{K-1} g_{i, t, k}. ]

引理2 和 引理3 对于约束中间项非常有用。

引理2. 我们有：

[ E_t \left[ \left| \frac{1}{n} \sum_{i=1}^{n} \sum_{k=0}^{K-1} g_{i, t, k} \right|^2 \right] \leq \frac{1}{n} \sum_{i=1}^{n} \sum_{k=0}^{K-1} \left( K + \frac{M}{n} \right) |\nabla f(y_{i, t, k})|^2 + \frac{K \sigma^2}{n}, ]

其中 ( E_t [\cdot] ) 表示在迭代 ( x_t ) 上的期望，即 ( E[\cdot | x_t] )。

引理3. 对于常数步长 ( \gamma \leq \frac{1}{2L} \sqrt{\frac{\tau K (n \tau K + M)}{n K}} )，我们有：

[ \sum_{t=0}^{T-1} \frac{1}{n} \sum_{i=1}^{n} \sum_{k=0}^{K-1} E[|x_t - y_{i, t, k}|^2] \leq \frac{1}{4L^2} \sum_{t=0}^{T-1} \frac{1}{n} \sum_{i=1}^{n} \sum_{k=0}^{K-1} E[|\nabla f(y_{i, t, k})|^2] + \frac{\gamma^2 \tau K^2 \sigma^2}{n} T. ]

引理4. 设假设1, 2 和 3 成立。若 ( {x_t}_{t \geq 0} ) 表示算法2的迭代，对于常数步长 ( \gamma \leq \min \left{ \frac{1}{2L} \sqrt{\frac{\tau K (n \tau K + M)}{n K}}, \frac{n}{2L (n K + M)} \right} )，则：

[ \frac{1}{nT K} \sum_{t=0}^{T-1} \sum_{i=1}^{n} \sum_{k=0}^{K-1} E[|\nabla f(y_{i, t, k})|^2] \leq \frac{8}{\gamma T K} (f(x_0) - f^*) + \frac{4\gamma L \sigma^2}{n} + \frac{4\gamma^2 L^2 \tau K \sigma2}{n}. ]

以上结果通过选择适当的参数得出我们所述的定理。


我们实现了 ( O(1/\sqrt{n T K}) ) 的渐近速率，这个速率随着 ( K ) （每轮的本地步数）的增加而改善。相比之下，[65] 的异步算法并不会随着本地步数的增加而改善。此外，异步性（由 ( \tau ) 捕获）仅影响更快衰减的 ( O(1/T) ) 项。因此，过期同步FedAvg具有与同步FedAvg [54] 相同的渐近收敛速率，从而在异步性方面

没有额外开销。此外，在实践中，过期同步FedAvg的渐近速率更好，因为随着 ( n ) （贡献更新的学习者总数）的增加，速率会提高，且时效放宽应导致更多学习者贡献更新。

4.2.3 缓解时效增加的影响

我们注意到，第4.2.1节中的收敛保证取决于最大回合延迟 ( \tau )，而大的回合延迟可能会对收敛产生负面影响，必须加以缓解。为缓解这一影响，以往关于分布式异步训练的研究提出在聚合之前对过期更新的权重进行缩放 [13, 24, 69]。我们将回合中的新鲜和过期更新集合分别表示为 ( F ) 和 ( S )。令 ( n_F ) 为新鲜更新的数量， ( u_F ) 为新鲜更新的平均值。此外，令 ( n_S ) 为过期更新的数量，对于一个延迟更新者 ( s \in S )， ( u_s ) 为过期更新， ( \tau_s ) 为延迟的回合数。文献中提出的缩放规则如下：

  1. 等同：与新鲜更新相同的权重（即， ( w_s = 1 )）；
  2. 动态SGD：延迟回合数的线性逆值 ( w_s = \frac{1}{\tau_s + 1} ) [24]；
  3. 自适应SGD：延迟回合数的指数衰减 ( w_s = e^{-(\tau_s + 1)} ) [13]。

自适应SGD还提出了一个增强乘数，以增加对过期更新的权重，从而考虑到那些数据分布更显著偏离全局数据分布的学习者。自适应SGD表明，增强重要的过期更新的权重是关键的，因为延迟更新者可能拥有比快速学习者更有价值（不同）的数据。然而，这种方法可能违反隐私规定，因为计算增强因子需要学习者共享其数据的信息。

因此，我们提出了一种隐私保护的增强因子，并将其与动态SGD的时效衰减规则相结合 [24]。提出的增强因子根据过期更新相对于新鲜更新平均值的偏离程度来调整权重，因此不需要任何关于学习者数据的信息。设 ( \Lambda_s = \frac{| u_F - \frac{u_s + n_F u_F}{n_F + 1} |2}{| u_F |2} ) 为过期更新 ( u_s ) 相对于新鲜更新平均值 ( u_F ) 的偏离度。设 ( \Lambda{\text{max}} = \max{s \in S} \Lambda_s )。增强因子项按 ( 1 - e^{-\frac{\Lambda_s}{\Lambda_{\text{max}}}} ) 的比例缩放过期更新 ( s )。最终，我们计算缩放因子的规则为：

[ w_s = (1 - \beta) \frac{1}{\tau_s + 1} + \beta (1 - e^{-\frac{\Lambda_s}{\Lambda_{\text{max}}}}) ]

其中，( \beta ) 是一个可调权重用于平衡平均值。

对于每个新鲜更新 ( f \in F )，我们选择缩放值为1，即 ( w_f = 1 )。加权平均的最终系数为归一化的权重。即，对于一个更新 ( i \in F \cup S )，最终系数为：

[ \hat{w}i = \frac{w_i}{\sum{i \in F \cup S} w_i} ]

因此，在聚合时，过期更新的权重 ( w_i ) 小于新鲜更新的权重 ( w_f )。这原则上减少了恶意学习者延迟更新以获得任何优势的影响，因为有了增强因子。未来的工作将进一步分析在对抗性环境下的表现。

5.1 实验设置

我们的实验模拟了由使用真实设备配置和可用性痕迹的学习者组成的联邦学习基准测试。我们的实验涵盖了不同的场景、模型、数据集和数据分布。接下来我们将详细说明这些内容。我们使用一组NVIDIA GPU来交替进行模拟学习者的训练。参与者在时间复用的GPU上并行训练，使用的是PyTorch v1.8.0。

实现：我们在FedScale[31]框架中实现了REFL。SAA和IPS组件被作为Python模块实现，并分别集成到FedScale的服务器聚合逻辑和参与者选择程序中。关于部署考虑和与流行FL框架的集成讨论请参见第7节。

仿真环境：我们的结果是通过在FedScale中模拟得到的。该框架包含三个关键组件：

  1. 聚合器（Aggregator）：选择参与者，分配任务，并处理更新的聚合。它使用客户端管理器（Client Manager）来跟踪学习者的可用性，并在每轮中选择目标数量的参与者。它还使用事件监视器（Event Monitor）来处理系统事件并调用相应的事件处理程序。

  2. 执行器（Executor）：运行学习者的逻辑，加载相应的联邦数据集，并使用PyTorch后端训练模型。延迟由样本数量 × 每个样本的延迟来决定，通信的延迟由字节大小 / 带宽决定。这允许使用现实痕迹进行模拟运行时间。

  3. 资源管理器（Resource Manager）：管理可用的计算资源（如GPU）。它使用一个队列来管理等待训练的学习者，并将学习者分配给第一个可用的计算资源 。

基准测试：我们使用了表1中列出的基准测试，这些基准测试涵盖了几种不同规模的常见FL任务，以覆盖各种实际场景。数据集包含数百个到数百万个数据样本，我们参阅 以了解数据集的描述。与 中一样，默认情况下，CIFAR10使用FedAvg 作为聚合算法，其他基准测试使用YoGi 。

数据划分：为了考虑现实中的异构数据映射，我们使用不同的方法在学习者之间划分标记的训练数据集，从简单到复杂。如文献中常见的那样，基线情况是随机均匀映射（IID）。其次，我们采用FedScale的数据到学习者的映射 ，这些映射包括数千到数百万的学习者，其数据分布反映了真实的数据来源 。然而，在分析Google Speech基准测试的FedScale数据映射时（见图6），我们发现大多数标签至少在40%以上的学习者中出现一次，使得这接近于均匀分布，从而简化了训练。对于CV基准测试也观察到了类似的情况。

为了考虑其他现实中的异构数据映射，我们引入了标签限制映射，其中学习者被分配了从随机标签子集抽取的数据样本，如表1所示，每个学习者的数据样本按以下特定分布进行分配。L1) 平衡分布：在每个学习者上使用每个数据标签的相同数量的样本；L2) 均匀分布：在每个学习者上使用均匀随机分配的数据点到标签；L3) Zipf分布：Zipf分布，参数α=1.95，具有较高水平的标签偏斜（受欢迎度）。

学习者的系统性能：学习者的硬件性能是从不同配置文件中随机分配的。

5 评估

我们的评估解决了以下问题：

  • 基于可用性优先选择学习者是否有益？
  • 聚合过期更新是否能减少资源使用并提高模型质量？
  • 过期更新是否应与新鲜更新加权不同？
  • REFL是否具有可扩展性和未来适用性？

我们总结了主要的观察结果如下：

  • REFL相比现有系统，以最多减少2倍资源实现更好的模型质量。
  • REFL在涉及IID和非IID场景的不同情况下均能提高质量。
  • REFL的权重缩放提高了统计效率。
  • REFL具有良好的扩展性，在未来场景中更具鲁棒性。

5.1 Experimental Setup

我们的实验模拟了使用真实世界设备配置和可用性轨迹的学习者的FL基准。我们的实验捕捉了不同的场景、模型、数据集和数据分布，如下所述。我们使用一组NVIDIA GPU来交替训练模拟的学习者。参与者在时间复用的GPU上并行训练，使用PyTorch v1.8.0。

实现： 我们在FedScale [31] 框架内实现了REFL。SAA和IPS组件被实现为Python模块，并分别集成到FedScale的服务器聚合逻辑和参与者选择程序中。我们将在第7节讨论部署注意事项和与流行FL框架的集成。

仿真环境： 我们的结果通过FedScale仿真得到。这个框架包含三个关键组件：

  1. 聚合器（Aggregator）： 选择参与者，分配任务，并处理更新的聚合。它使用一个客户端管理器（Client Manager）来跟踪学习者的可用性，并在每轮选择目标参与者数量。它还使用一个事件监视器（Event Monitor）来处理系统事件并调用适当的事件处理程序。

  2. 执行器（Executor）： 运行学习者的逻辑，加载相应的联邦数据集，并使用PyTorch后端训练模型。计算延迟由样本数量乘以每个样本的延迟决定，通信延迟由字节大小除以带宽决定。这允许使用真实的轨迹进行模拟运行时间。

  3. 资源管理器（Resource Manager）： 管理可用的计算资源（如GPU）。它使用一个队列来管理等待在计算资源上训练的学习者，并将学习者分配给第一个可用的计算资源。6

  4. 该队列不影响模拟时间，模拟时间由事件监视器维护，事件监视器根据事件及其正确的时间顺序推进全局虚拟时钟。

基准测试： 我们实验使用了表1中列出的基准，涵盖了多个不同规模的常见FL任务，以涵盖各种实际场景。数据集包含数百到数百万的数据样本，具体描述见[31, 32]。默认情况下，FedAvg [43] 被用作CIFAR10的聚合算法，YoGi [50] 被用作其他基准。

数据划分： 为考虑现实的异构数据映射，我们使用不同的方法在学习者之间划分标记的训练数据集，从简单到困难。如文献中常见的那样，基线情况是随机均匀映射（IID）。其次，我们采用FedScale的数据到学习者映射[31]，该映射涵盖了数千到数百万个学习者，其数据分布反映了真实数据源。然而，在分析了Google语音基准的FedScale数据映射中标签出现的频率后（见图6），我们发现大多数标签至少在40%的学习者中出现过一次，使其接近均匀分布，从而简化了训练。对计算机视觉（CV）基准的观察结果相似。

为考虑其他现实的异构数据映射，我们引入了标签限制映射，其中学习者被分配从标签随机子集中抽取的数据样本，如表1所列，每个学习者的数据样本遵循特定的分布。L1）平衡分布：每个学习者使用等数量的每个数据标签的样本；L2）均匀分布：每个学习者上每个标签的数据点的均匀随机分配；L3）Zipf分布：使用 ( \alpha = 1.95 ) 的Zipf分布以实现更高水平的标签倾斜（流行度）。

学习者的系统性能： 学习者的硬件性能是从AI [5] 和 MobiPerf [40] 基准的真实设备测量配置文件中随机分配的，分别用于推理时间和移动设备的网络速度。AI Benchmark列出了流行DNN模型（如MobileNet）在各种Android设备（如三星Galaxy S20和华为P40）上的推理时间。配置文件包括至少2GB RAM并使用WiFi的设备，这与FL设置中的常见情况相匹配[6, 32, 68]。

我们展示了如何将AI基准和设备配置文件中的浮点和量化推理时间分布聚类成6种不同的设备配置，显示出显著的设备异质性和长尾分布，如图7a所示。图7b显示了学习者可以根据其计算能力分为6个不同的设备配置集群，表明在训练期间学习者的完成时间可能高度可变。

学习者的可用性动态： 我们使用了来自不同国家的136K移动用户在一周内的轨迹[67]。该轨迹包含约1.8亿条连接WiFi、充电和（解）锁屏等事件的记录。可用性定义为设备连接充电器并连接到网络时，类似于[32, 60]。

我们看到学习者表现出变化（和周期性行为），大多数学习者仅可用几分钟。我们从用户行为轨迹中提取了可用性动态[67]。图7c显示了可用学习者数量随时间显著变化，并在一周的日子里表现出昼夜模式，夜间有大量学习者通常可用（即充电）。图7d显示了学习者可用时段长度的CDF，表现出非常长的尾部。大多数客户端（多达70%）的可用时间少于10分钟。

超参数设置： FL和学习超参数使用FedScale框架设置的默认值，未进行进一步调整。比较中的所有方法使用相同的常见FL超参数。我们使用了评估方法（即Oort [32] 和 SAFA [64]）的推荐参数设置。

REFL参数： 除非另有说明，否则在包含更新时未应用时效的最大阈值。我们将移动平均回合持续时间的 ( \alpha ) 设置为0.25，选择该值是为了更重视最近的回合持续时间值。我们将过期更新权重的 ( \beta ) 设置为0.35，在公式（5）中，以更倾向于衰减过期更新。我们在实验能力范围内测试了不同的值，发现上述值效果良好。详细的敏感性分析和超参数的消融研究留待未来工作进行。

可用性预测模型： 在实验中，我们假设模型对未来可用性的准确率为90%（即，每10次选择中有1次是假阳性），这与训练一个简单线性模型在真实世界轨迹上获得的模型准确率相匹配，如第5.2节详细描述。

实验场景： 我们考虑了文献中使用的两个实验设置：

  1. OC：FL服务器超额提交目标参与者数量 ( N ) 30%，并等待 ( N_t ) 个参与者的更新（如[31,32]所述）；
  2. DL：FL服务器选择目标参与者数量 ( N )，并在预设的报告截止日期前聚合任何数量的更新（如[6, 67]所述）。

除非另有说明，目标参与者数量为10；每个实验用不同的采样种子重复3次，并显示3次运行的平均值。实验使用了约13K小时的GPU时间。

5.2 实验结果

我们评估了为达到某一测试精度而消耗的学习者资源量（和运行时间）（资源越少、运行时间越短越好）。由于我们的结果基于仿真，我们使用每个学习者累积的时间作为资源使用量的替代指标。特别地，每轮的累积资源是所有参与者的计算和通信时间的累积和。

这里，我们重点关注Google语音，并在5.2.8节中呈现其他基准和实验设置的结果。表2显示了在半集中训练环境（即数据并行）下基准的基线精度，其中数据集在每轮训练中均匀分配给10个参与者。

5.2.1 选择算法的性能

我们使用OC+DynAvail实验设置。我们将REFL与Oort、随机选择（Random）和优先选择（Priority）进行了比较。优先选择是REFL的IPS组件（即，SAA组件被禁用）。

图8显示，在FedScale和不同的非IID（标签限制）数据映射下，REFL以最少的资源使用实现了比其他方法（即Oort、随机和优先选择）更好的精度。REFL通过基于可用性的优先选择（图8e）和过期更新的聚合（图8f）实现了卓越的性能。当在标签限制的非IID情况下运行更多轮的FL训练过程时，图9显示REFL在更短的时间和更少的资源使用下收敛到显著更高的精度。

5.2.2 聚合算法的性能

在比较SAFA和REFL时，我们使用DL+DynAvail设置，总共有1000个学习者，轮次截止时间为100秒。我们使用FedAvg作为基础聚合算法。REFL预先选择了100个参与者，目标比例分别为SAFA的10%和REFL的80%。对于这两种方案，我们将时效阈值设置为5轮。

图10的结果显示，SAFA和REFL的运行时间是相当的，但SAFA消耗的资源显著更多。在FedScale映射的情况下（图10a），结果显示REFL以约20%较少的资源实现了更高的精度。在非IID映射的情况下（图10b），REFL以约60%较少的资源显著提高了10个百分点的精度。

基于可用性的优先选择 图8显示的结果表明，优先选择通过优先选择最不易用的学习者实现了更好的模型精度。结果表明，特别是在非IID设置中，选择低可用性的参与者会带来更高比例的独特学习者及其有价值（可能是新的）数据样本，因此达到一定精度所需的资源使用量也会减少。

自适应目标 我们在OC设置下使用DynAvail和AllAvail场景进行了实验，使用标签限制（均匀）映射，每轮50个参与者。

图11显示，在这两种场景中，与Oort和随机选择相比，REFL和REFL+APT具有更高的模型质量和更少的资源使用。此外，通过权衡额外的运行时间（即15小时对28小时），APT可以进一步减少REFL的资源消耗。与AllAvail相比，当REFL优先选择最不易用的客户端时，DynAvail的改进得以保持，并实现了可比的精度。然而，根据基准测试，当目标参与者数量较少（例如， ( N_0 \leq 10 )）时，APT可能没有收益。

过期更新的聚合 我们在OC+AllAvail设置下实验了REFL、Oort和随机选择。

图12显示了达到的测试精度与训练轮次的关系。我们观察到，在不同的数据映射中，REFL由于SAA组件的存在，以较少的资源使用实现了良好的模型质量。值得注意的是，对于非IID分布的好处更为显著。在非IID设置中，延迟参与者的过期更新比IID设置更为重要。这表明过期更新可以提高训练的统计效率。此外，由于学习者的可用性概率设为1（始终可用），REFL实现了与随机选择相似的运行时间，因此REFL回归为随机选择。

过期权重缩放 我们使用OC+DynAvail并将截止时间设置为100秒。我们评估了第4.2.3节的权重缩放规则，并在图13中展示了训练轮次的测试精度结果。

我们观察到，REFL的缩放规则在所有数据分布场景中始终优于其他缩放规则。在IID情况下（图13a和13b），缩放规则之间的差异较小。然而，在非IID情况下（图13c到13e），除了REFL的规则外，性能不一致。这些结果显示了REFL规则在缓解过期更新潜在负面影响方面的好处。同样的观察结果也适用于OC+AllAvail和FedAvg。

可用性预测模型 我们评估了预测模型。该模型在Stunner轨迹上训练[57]，该轨迹包含大量全球移动用户的设备事件。我们使用了在2018年9月收集的至少包含1000个样本（即137个设备）的设备。我们提取了插入和充电状态，使用每个设备样本的前一半来训练每个设备的模型。我们将设备模型在剩余样本上的预测进行比较，后者用作测试数据集。

结果显示，模型可以高精度地预测未来的可用性状态。跨设备平均的决定系数、均方误差和平均绝对误差分别为0.93、0.01和0.028。

其他基准的结果 我们在OC+DynAvail设置下运行了NLP（Reddit和StackOverFlow）和CV（CIFAR10和OpenImage）基准。我们使用YoGi作为OpenImage、Reddit和StackOverFlow基准的聚合算法，使用FedAvg作为CIFAR10基准的聚合算法。为REFL启用了自适应参与者目标（APT）。我们还将NLP数据集大小限制为20%（即约800万样本），如表1所示。

图14直接比较了REFL和Oort的结果。Reddit（图14a）和StackOverFlow（图14b）的结果显示，与Oort相比，REFL显著减少了学习者的资源消耗和最终测试困惑度。我们注意到，在初始轮次中，REFL和Oort的性能相当。然后，Oort的低多样性导致收敛性下降，这可能归因于缺乏新样本（或具有新数据的参与者，这有助于提高模型的收敛性）。类似地，OpenImage（图14c）和CIFAR10（图14d）的结果显示，在学习者之间的数据分布为IID或FedScale数据映射（即接近IID）的情况下，与Oort相比，REFL以较少的资源消耗实现了相同的模型精度。

6 讨论

我们讨论了REFL在未来场景中的影响。

大规模联邦学习： 我们预计未来的FL部署将显著扩大，包含传感器、物联网设备、自动驾驶汽车等学习设备，这些设备可能没有连接到电源，且计算能力有限。REFL在大量资源上实现了高效扩展，而与之对比，诸如SAFA之类在训练后进行选择的FL系统或偏向选择快速设备的FL系统（如Oort）在这方面表现不佳。调用所有设备进行训练将会压垮服务器，并给学习者带来大量的能源消耗，其中大部分会被浪费掉。

我们使用Google语音基准测试和3倍数量的学习者（3,000）展示了大量参与者对资源使用的影响。如图15所示，我们观察到SAFA在IID环境（图15a）和非IID环境（图15b）中浪费了大量资源，非IID环境中浪费更多。

未来硬件进步： 我们预计设备的计算能力将继续提高，因此FL系统应从中受益。因此，像Oort这样偏向快速学习者的方案可能会导致低能力学习者的代表性不足，从而导致模型在大群体中的泛化能力较差。相比之下，REFL通过利用快速学习者的优势，同时不忽视低能力学习者，来应对硬件进步。

我们在4种设置下运行了Google语音基准测试：当前设备配置（HS1）；对于顶层设备的完成时间（即计算和通信）翻倍的设备配置（HS2：25%，HS3：75%，HS4：100%）。如图16a和16b所示，我们观察到在IID环境中，Oort和REFL都从硬件增强中受益。然而，如图16c所示，在现实的标签限制非IID环境中，由于过期更新的聚合和更高的参与者多样性，REFL看到了显著的性能提升。Oort由于选择仍然偏向快速学习者，虽然减少了训练时间，但模型质量没有提升，因此没有从速度的提高中受益。

可用性预测模型的影响： 当新学习者加入FL过程时，他们可能没有用于训练其可用性预测模型的轨迹，从而导致对其预测的信心较低。此外，恶意或对抗性学习者可能试图通过持续报告低的未来可用性来影响系统。为了应对这些情况，并按照[6]的建议，我们在第4.1节中使用了一种过滤机制，防止参与者在接下来的X轮中重新被选择（在我们的实验中为5轮）。

7 与FL框架的集成

REFL的设计轻量级，可以作为在线服务或现有FL框架的插件模块运行。因此，REFL适用于处理成千上万到数百万终端设备的大规模FL部署。

REFL按如下方式选择参与者：

  1. 首先，服务器更新其对当前轮次持续时间 ( \mu_t ) 的估计，并将下一轮次的时间段估计 ( a = (\mu_t, 2\mu_t) ) 发送给学习者；
  2. 学习者维护其充电事件的本地记录，并定期训练预测模型，该模型生成其在未来时间段内充电状态的概率值；
  3. 在接收到可用性查询 ( a ) 后，每个学习者 ( l ) 使用预测模型生成其在时间段 ( a ) 内的可用性概率 ( p_l(a) ) 并将 ( p_l(a) ) 发送给服务器；
  4. 服务器收集这些概率 ( P_t ) 并使用算法1选择参与者；
  5. 服务器向每个选定的参与者发送一个随机哈希ID，该ID编码了当前轮次的时间戳以及FL任务（例如模型）和相关参数配置。

REFL按如下方式处理过期更新：

  1. 服务器收集在当前训练轮次 ( t ) 结束前收到的更新。如果收到的更新的哈希ID的时间戳与当前轮次不匹配，则将其分类为过期更新；
  2. 在轮次结束时，服务器首先聚合新鲜更新以生成 ( \hat{u}_F )；
  3. 对于每个过期更新 ( u_s )，服务器使用过期更新的时间戳计算时效水平 ( \tau_t )；
  4. 对于每个过期更新，服务器计算其与新鲜更新的偏差 ( \Lambda_t )，并使用公式（5）中的规则为过期更新分配缩放权重 ( w_s )；
  5. 服务器使用算法2将缩放后的过期更新与聚合的新鲜更新一起聚合以生成新模型。

要将REFL与PySyft集成，在选择阶段，服务器和学习者之间需要进行最小的交换。服务器发送下一个训练轮次的估计时间段。学习者使用预测模型并发送其可用性概率。因此，学习者无需交换任何有关其数据的敏感信息。FL开发者编程客户端以训练预测模型并响应来自服务器的可用性查询，这会带来最小的内存和通信开销。REFL还可以作为分布式服务运行，使用通信库（例如XML-RPC [14]）建立REFL进程与服务器之间的通信渠道。服务器可以与REFL服务共享参与者的元数据。服务器可以使用PySyft API model.send(participant_id) 调用REFL选定的参与者，并使用 model.get(participant_id) 从参与者收集模型和元数据更新。

8 相关工作

联邦学习 (FL)： FL通常被视为一种机器学习范式，其中服务器将训练过程分布在一组去中心化的参与者上，这些参与者使用从未与其他实体共享的本地数据训练共享的全局模型【27, 43】。FL已被用于增强虚拟键盘的预测质量以及其他应用【6, 68】。许多FL框架促进了该领域的研究【9, 31, 48, 53, 60, 67】。Flash【67】扩展了Leaf【9】，以包含异构性相关参数。FedScale【31】使得使用各种具有挑战性和现实性的基准数据集进行FL实验成为可能；我们在这项工作中将其用作仿真框架。

参与者选择策略： 在每一轮中，FL服务器从在线学习者中抽样，并在选定的参与者（例如，数十个学习者）中训练全局模型，而当前在线的学习者可能有成千上万【32】。许多最近的研究提出了增强的参与者选择策略。有人提出了将选择过程偏向于硬件和网络速度快的学习者【47】。其他工作则试图通过选择具有更好模型更新的参与者来提高统计效率【10, 12, 52】。最近，Oort【32】提出了一种结合系统效率和统计效率的策略。正如我们在这项工作中展示的那样，这些方法要么导致计算浪费，要么导致学习者的覆盖率低。

FL中的异构性： 面临FL系统大规模应用的一个重大挑战是不确定的系统行为，这是由于学习者、系统和数据的异构性【3, 36, 37, 67】。学习者的计算能力可能会限制贡献并延长轮次持续时间【3, 36, 37, 67】。为应对异构性提出了架构和算法解决方案【2, 32, 34, 37, 62】。FL中的异构性尤其具有挑战性，因为参与者的数据分布和可用性以及异构的系统配置是无法控制的【3, 6, 27, 68】。

FL提案： FL系统的更广泛改进包括减少通信成本【6, 11, 28, 51, 55】，改进隐私保证【4, 6, 42, 44, 46】，补偿部分工作【37, 62】，最小化边缘设备的能耗【35】，以及个性化由参与者训练的全局模型【26】。最近的工作试图解决数据异构性的问题【37, 38, 45】。

我们的工作补充了这些旨在优化FL生态系统的努力。我们旨在创建一个资源高效的FL框架，更好地利用学习者的资源，以在不延长训练时间的情况下实现目标模型质量。REFL的设计可以轻松受益于现有的安全聚合或差分隐私技术。

9 结论

我们研究了阻碍FL系统广泛采用的两个关键问题：资源浪费和数据多样性低。我们提出了REFL，通过包含新颖选择和聚合算法的两个核心组件来解决这些问题。与现有系统相比，REFL在理论和实证上均证明能够在减少资源使用的同时提高模型质量，对训练时间的影响较小。REFL是建立资源高效联邦学习的新颖且实用的生态系统的重要一步。