Oort: Efficient Federated Learning via Guided Participant Selection

会议：OSDI’21 (操作系统领域顶会)
文章: osdi21
代码: Github
作者: Fan Lai, Xiangfeng Zhu, Harsha V. Madhyastha, Mosharaf Chowdhury
机构: University of Michigan

研究背景和动机

实际使用联邦学习时，一个基本问题是：选择一个"好"的客户子集作为参与者。每个参与者本地处理自己的数据，中央服务器只收集和汇总它们的结果。

现有的方法在随机选择参与者的情况下，从2个方面进行优化：

  • statistical model efficiency（统计模型效率）：在更少的训练轮次下有更高的训练准确率
  • system efficiency（系统效率）：更少的通信轮次

虽然随机选择参与者在部署的时候很方便，但是当设备速度和数据分布存在较大差异时联邦学习的表现很可能不够理想。更糟糕的是，随机选择参与者会导致有偏的数据集，其结果的可信度大大降低。由此，一般大家认为需要更多的参与者来解决此问题。

这篇文章提出了Oort，实现在联邦学习模型的整个生命周期中进行有指导的参与者选择。只需要开发者提供测试的指标，利用当前的FL方案已有的信息做少量改动即可选出可靠的参与者。

方法

Oort和开发者及FL执行框架的交互（图1）：

  1. job submission：开发者向FL协调器提交并指定参与者选择标准
  2. participant selection：协调器查询满足资格属性(例如,电池电量)的客户端，并将其特征(例如,活跃度)转发给Oort; Oort选择参与者，并把选择通知给协调器
  3. execution: 协调器向参与者分发相关的配置文件(如,模型)，然后每个参与者独立地在本地数据上计算结果(如,模型权重)
  4. aggregation：当参与者完成计算后，协调器进行聚合

在联邦训练过程中，协调器从足够多的参与者中聚合更新后开始下一轮训练，在每一轮通信中，迭代进行步骤2-4。每经过几轮训练后，进行联邦测试判断是否达到了截止精度。

图1. Oort 框架图

Oort提供了2个选择器：

  • Training selector：目的是提升训练过程中的time-to-accuracy表现。为此，它计算客户端在训练中的效用，并在运行时高效地探索和选择高效用的客户端。

  • Test selector：当没有提供单个客户端数据特征(如,分类分布)时，测试选择器决定需要的参与者数量，以限制参与者的数据偏离全局。否则，它挑选参与者服务于开发人员对数据的准确要求，同时最小化测试的持续时间。

联邦模型训练

统计效率与系统效率的权衡

FL训练的 time-to-accuracy 表现依赖于2个方面：（1）统计效率：需要训练的轮次以达到目标的准确度；（2）系统效率：每一轮训练的时长。如图2所示，优化系统效率（Opt-Sys. Efficiency）可以降低每一轮通信的时间（选择最快的客户端），这可能导致比随机选择更多的通信轮次，因为在过去的几轮中，客户端的数据可能已经被其他参与者过度代表了。另一方面，在全局模型聚合中，使用具有高统计效用的(Opt-Stat. Efficiency)客户端但是是系统瓶颈的话可能会导致更长的通信时间。

图2. 现有的FL训练随机选择参与者，而Oort则通过统计和系统效率的平衡来优化 time to accuracy
结果是根据OpenImage数据集使用MobileNet网络得到的

为了改善 time to accuracy 表现，Oort的目标是在权衡中找到一个最优点，将每个客户的效用与优化每一种形式的效率联系起来。由此，产生3个挑战：

  1. 在每一轮通信中，如何在尊重客户隐私的情况下，确定哪些客户的数据最有利于提高训练的统计效率？
  2. 如何考虑客户端的系统性能，以优化全局系统效率？
  3. 如何解释在训练期间没有为所有客户提供最新的效用值？

客户端统计效用

insight: 较大的梯度范数往往会导致较大的损失；当前积累较大损失的客户端对未来的通信更重要

因此，可以用损失（在训练过程中可以直接得到）替代梯度（需要额外计算），客户端ii的统计效用U(i)U(i)可以写成

U(i)=∣Bi∣1∣Bi∣∑k∈BiLoss(k)2U(i) = |B_i|\sqrt{\frac{1}{|B_i|}\sum_{k \in B_i}Loss(k)^2}

优点：可以捕获各种任务的类别和样本之间和内部的异构数据效用

统计与系统效率的权衡

Util(i)=∣Bi∣1∣Bi∣∑k∈BiLoss(k)2×(Tti)1(T<ti)×α⏟StatisticalutilityU(i)⏟GlobalsysutilityUtil(i) = |B_i|\sqrt{\frac{1}{|B_i|}\sum_{k \in B_i}Loss(k)^2} \times (\frac{T}{t_i})^{\mathbf{1}(T<t_i)\times \alpha}\\ \qquad \qquad \underbrace{\qquad\qquad\qquad\qquad\qquad}_{Statistical \quad utility \quad U(i)} \quad \underbrace{\qquad\qquad \quad}_{Global \quad sys \quad utility}

BiB_i 是每个客户端 ii 本地的训练样本；
TT 是每一轮开发人员首选的持续时间，tit_i 是客户端 ii 训练所需的时间（从过去几轮中收集得到）；
1(x)\mathbf{1}(x) 是一个指示函数，当 T<tiT<t_i 时，即可能成为当前轮所需速度瓶颈的客户端的效用将受到开发者指定的因子 α\alpha 的惩罚。

但是实际上仍然有一些需要解决的问题，以便在每一轮训练中选出效用最高的参与者：

  1. 客户的效用只能在其参加训练后才能确定；如何从大规模的客户中进行选择，而不必尝试所有客户？
  2. 由于不是每个客户都参与每一轮，如何解释自上次参与以来客户效用的变化？
  3. 如何在存在corrupted的客户端时对异常值保持健壮？

适应性参与者选择

从众多客户端中选择参与者可以看成是“多臂老虎机问题”，每个客户端可以看成一个“arm”，对应的效用就是“reward”。相比于更复杂的强化学习设计，即使解决方案空间（例如，客户端数量）随时间发生巨大变化，bandit模型也保持很好的可扩展性和灵活性。

图3. “探索-利用”的参与者选择算法

Line 6：参与者选择开始时，Oort会接受上一轮训练的反馈，更新客户端的统计效率和系统表现；为了鲁棒性，再被选中一定次数后，客户端会从参与者中被删除，可消除异常值影响；
Line 9-15：探索过的客户端，计算他们的效用，从高效用的客户端中选择；line 10中如果客户端长期没有被选择，就增加其效用（随时间增加的不确定性）；
Line 16：抽样 ϵ(∈[0,1])\epsilon (\in [0,1]) 未经选择过的参与者（根据模型来推断出谁的系统速度更快）。

联邦模型测试

关注2个方向的问题：

  1. 如何在没有个体客户数据特征的情况下保持测试集的代表性；
  2. 在提供个体信息的情况下如何有效地执行开发人员对特定数据分布的测试标准

注：如果不是要学习一个global model，只是personalized model，对生成的测试集或者选择的测试集要求会大大减少。

实验

在四个CV和NLP数据集上评估了Oort对四个不同ML模型的有效性

  • Oort在时间精度性能上优于现有随机参与者选择1.2×-14.1×，同时最终模型精度提高1.3%-9.8%
  • Oort通过自适应地在统计效率和系统效率之间进行权衡，实现了接近最优的模型效率
  • Oort在广泛的参数范围和不同规模的实验中优于同类框架，同时对异常值具有鲁棒性