MobiSys22-FedBalancer: Data and Pace Control for Efficient Federated Learning on Heterogeneous Clients

收获：

该优化方法精心设计了在客户端中进行数据选择的策略，Oort精心设计了进行device选择的策略，Hermes精心设计了在本地Model上进行的剪枝操作（相当于考虑到了本地的数据），FedNAS运用神经搜索的方法搜索最优的结构。

疑问：

是否缺少对模型本身和FL的特点都进行优化的工作？
FL如何流水线化？当前的工作是否流水线化？client-server的结构是client等server还是server等client？
FL每个阶段的方法划分？
这些论文用的数据集和评测结果。

摘要：

经典的FL训练方案：把所有数据同等对待，导致计算资源的浪费，降低了全局的学习过程。
FedBalancer：主动选择clients’的训练样本，兼顾算力和隐私的同时prioritize more “informative” data。介绍了自适应的deadline control scheme去预测每一个轮次的optimal deadline。
评测结果：五个数据集、三个不同的domain，FedBalancer提升了time-to-accuracy的性能1.20~~4.48x，提升了模型的精度1.1~~5.0%。FedBalancer可以和其它的FL approach集成到一块。

FedBalancer：

prioritize more “informative” samples去高效的利用他们的computational effort。这使得low-end devices在round-deadline内对global training产生贡献，因为low-end devices聚焦于更小的但是更重要的training samples。
为了获得更高的time-to-accuracy performance，the sample selection被设计为在FL rounds的sample utility measurement的时候operate without additional forward or backward pass。
FedBalancer能够和其它的FL approach一起使用。

解决的挑战：

简单的随机采样会导致模型精度的下降，因为训练数据的statistical utility会下降，因此要根据数据的statistical utility measurement去选择samples。
sample selection时候收集sample-level的statistical utility会打破FL的privacy guarantee。提出了client-sever coordination的方法去维护一个loss threshold，这允许clients去高效的选择重要的samples同时只暴露他们differentially-private的数据。
当FL的round deadline固定的时候，光样本选择可能不会导致time-to-accuracy的性能提升。为了formulate the benefit of selecting different deadlines，我们提出了一个metric deadline efficiency (DDL-E)的方法，该方法计算每次计算完成round的clients的数量。

在FLASH上实现（FLASH是一个基于LEAF实现的框架）。FLASH提供了从135k手机收集到的算力和真实世界轨迹的数据集，涉及千种设备，2062行代码实现，使用的aggregation算法是PROX。

Background（当前有什么问题）

优化time-to-accuracy的性能十分重要。

对用户来说：FL花费了边端用户设备的巨大的计算和网络资源。
对模型的开发者来说：在几千到几百万的设备上快速的收敛对高效的测试多个模型架构和超参很有用。
对于服务的提供者来说：不断地模型地更新要求减小用户的overhead，同时带来更高的time-to-accuracy的性能。

异构性带来的问题：

centralized learning采用importance sampling去优化训练的过程，但是FL中还很少采用。
Preliminary study显示the ratio of informative samples随着FL训练过程的推进从93.2%减小到20%，硬件的异构性会导致这种状况进一步恶化，因为low-end的clients可能输送模型更新失败。

Motivation（Fedbalancer的灵感来源）

很少有人这么干。
样本的GN（Gradient Norm）在FL的开始都很高，但是在FL训练的后期，只有很少的样本有很高的GN。
这启发FedBalancer开始用所有的样本训练，之后不再使用模型已经学到的样本。

尽管获得最短训练事件的optimal的deadline已被证明存在（见原文引文），为high time-to-accuracy控制deadline没有被研究过。
图显示：deadline对取得最快的收敛速度和更高的精度很重要。没有任何一个方法在各种任务上能够完胜别的方法。
找到一个最优的deadline十分重要。

FEDBALANCER（模型的具体的设计）

FL的每一个round，FedBalancer自适应的选择client的训练数据，控制deadline，以取得更高的time-to-accuracy的性能。

Fedbalancer主动控制**(1) loss threshold (lt)** 和**(2) deadline (ddl)**。
(1) loss threshold：决定每一个client的训练数据。
(2) deadline决定the round的终止事件。
①：服务器首先把当前的模型的权重$W_R$，loss的threshold $lt_R$，deadline $ddl_R$（R代表第R个轮次）传送到该轮次被选定的clients。
②：device上的sample selection模块选择在loss threshold的部分的训练数据。
③：device上训练received model。
④：client奖模型的更新和sample selection收集到的metadata输送给服务器。
⑤：服务器聚合来自所有clients的responses。
⑥：根据clients的metadata，loss threshold selection module和deadline selection module分别选择下一个round的$lt_{R+1}$和deadline $ddl_{R+1}$。

Sample selection module（样本选择模块的具体算法）

不想让clients暴露自己的隐私就需要client使用本地数据中对样本的重要性进行分类，而不暴露任何的信息，需要解决的难点就是clients很难在不知道global data的前提下确定什么样本重要什么样本不重要。于是FedBalancer就搞了个client-server coordination维护一个loss threshold $lt_R$。假设client i的样本选择模块工作在round R，有一个给定的loss threshold $lt_R$。

流程：

首先module这个轮次是否需要sample selection，也即是判断这个client是否可以在给定的$ddl_R$内训练完他完整的数据集。给予client一定的自主权，如果这个client可以飞快的训完，那么就不管他的sample重要不重要了。
于是可以计算出client i在deadline之前的最大的样本数量S，验证其是否大于client dataset的大小$D^i$。（2-4行）。由于client的计算能力可能会根据device的runtime condition改变（见原文引文），FedBalancer收集batch训练的延迟，也就是$B^i$，使用平均延迟来估计他能够处理的最大的样本数。为了在第一个round计算平均的延迟，FedBalancer要求clients在FL开始前采样k次，这次k设置为10.
如果client i可以训练完整的数据集，sample selection模块就会使用the list of sample loss ($loss^i$)来决定用什么样本去训练。the loss list展示了当前模型所有样本的statistical utility，这个loss list可以通过推导所有样本在每个轮次的最新模型得到，这样的推导会带来额外的forward pass latency，可能会降低time-to-accuracy的性能。因此，FedBalancer的clients只做整个数据集的forward pass一次，也就是在这个client被第一次选中的时候做一次。每当他们训练数据的subset的时候，就会更新选中的sample的loss value。
然后FedBalancer根据the list of sample loss选择client sample。
如何选择client samples？首先将client i’s samples划分为两个groups，一个是Under-Threshold ($UT^i$)，一个是Over-Threshold ($OT^i$)，样本根据threshold分别放入$UT^i$和$OT^i$。总共从$OT^i$中采样$L\cdot p$个样本，从$UT^i$中采样$L\cdot (1-p)$个样本，$p$在$[35,78]$之间取值。要采样点的样本数$L$，也就是$len(OT^i)$. Loss的threshold会慢慢的增加。如果S大于$len(OT^i)$，改用S去最大化statistical utility within the deadline。
FedBalancer是在Prox的基础上做出来的，允许clients训练的epoch数量少一些，因此clients with S less than $len(OT^i)$任然可以对模型的更新起作用。

Loss threshold selection module（Loss的阈值选择模块）

Loss值的分布会随着训练的变化而变化，module对当前分布知晓是十分重要的。为了了解这种分布的变化，服务器会在每个round结束后从loss list of clients收集一些metadata，也就是client i在第R个轮次的$LLow^i_R$和$LHigh^i_R$80%分位数（防止异常噪声）。在这个值上加上高斯噪声保护用户隐私。这些值在server上经过进一步的aggregation得到$LLow_R$和$LHigh$。