MobiCom21-Hermes: An Efficient Federated Learning Framework for Heterogeneous Mobile
- 这种剪枝方法自适应的根据设备数据学习到较好的剪枝方法，基于的假设是：相似的数据进行梯度下降时更新的参数应该也是类似的。个人人为这种方法可能不能很好的学习到设备的异构性。
- 作者没有在真实场景下进行测试，算法的测试规模较小。
Hermes: a communication and inference-efficient FL framework under data heterogeneity.
不去像传统的FL那样去优化base neural network，每个设备运用结构化剪枝找到一个小的子网，这个子网在本地数据上泛化性良好，只有这些子网的更新才在服务器和设备之间传输。服务器只对每个子网的重合的参数做平均。
这样做的假设是：“lottery ticket hypothesis”，即原本网络的最优结构可以通过剪枝出一个子网达到类似的效果。拥有相似local数据的设备共享相似的子网架构和更多的相似参数，找到这些子网的话通信和推理效率都可以被提高，也可以进行个性化的定制。
Hermes achieves as high as 32.17% increase in inference accuracy, 3.48× reduction on the communication cost, 1.83× speedup in inference efficiency, and 1.8× savings on energy consumption.
- 当前很少有考虑推理效率的工作，本篇工作可以提高推理效率。
- 减少通信成本。
- 学习到个性化的模型。
Background（当前存在什么问题）
联邦学习：
解决数据异构性的问题：FL personalization，多数都是two-step的方法，第一步学好一个global model，第二步fine tune globel model，这种两步方法不可避免的会导致额外的计算开销。数据异构性不应该是障碍，而应该是实际的个性化的需求。
- fine-tuning
- multi-task learning
- contextualization
解决通信开销的问题：压缩设备和服务器之间的通信开销。CIFAR-10 500个通信轮次，每次20个参与设备，VGG16和Inception-v4，FedAvg分别产生了10.59TB和32.22TB的数据，LG-FedAvg减少到了8.28TB和2.45TB，还是太大了。
- 量化
- 稀疏化
- 混合方法
有没有既考虑设备算力和通信能力（HeteroFL），又考虑设备上数据量（Hermes）做定制的工作
同时解决数据异构性和通信开销的方法很少：
- LG-FedAvg：结合局部的表示学习和全局的联邦学习，将模型参数分为两个部分，local parameters和global parameters，分两步走，第一步设备使用FedAvg策略和更新和交换整个模型，第二步更新整个模型，但是每次只把部分参数发送给中央服务器。LG-FedAvg只能在第二部减小通信开销，模型的划分用的是启发式的方法而不是数据驱动的方法。LG-FedAvg的评测也不是在真实的FL setting下做的，他的评测每个设备上都具有充足的训练数据。
- HeteroFL：根据设备的算力和通信能力自适应的分配submodel，每个设备只训练和通信submodel，因此通信和计算效率都能提升。但是子模型是根据设备的能力设计的而不是依据本地数据设计的，使得子模型的分配很不灵活。
- SFSL：是为推荐系统设计的安全的联邦子模型推荐框架，子模型由用户在电商平台上的历史数据来确定。每一个设备只需要训练和传输子模型，因此通信和计算效率都能提升。然而这个特定的联邦学习策略是为推荐系统设计的，具有特殊的输入数据的结构，SFSL可能对其它场景并不适用，因为其它场景模型和输入数据的格式都和SFSL不一样。
当前还没有把计算效率考虑进来的研究工作。
Challenges（Hermes设计的挑战和解决挑战的方法）
挑战：
- 第一个挑战是设计一local training方法，使得设备能够学习一个子网，这个子网能把个性化的本地信息数据嵌入，联合提升通信和推理效果：一个novel的本地训练方法，这个方法使用每一个client每一轮通信过程中的的基本模型寻找子网。每一device学习了一个结构化的稀疏子网，在通信阶段只和服务器通信参数。
- 第二个挑战是为服务器设计一个特定的聚合策略去最大化保存每个子网的个性化属性：Hermes在服务器端设计了一个个性化的保存聚合策略。也就是该聚合方法只做subnetworks交叉部分的平均，这样的聚合策略可以阻止每个subnetwork的的个性化参数被其他的参数干扰。
- 还要处理部分设备的数据严重不足的问题。
实验：
- 在手机上三个代表性的深度学习应用上做了实验。
- 对比的方法有：FedAvg、Top-k，Per-FedAvg，LG-FedAvg。
理论上的收敛性证明。
DESIGN OF HERMES（Hermes实际的设计）
Overview（Hermes整体架构）
在每一个通信阶段，一系列的device参与FL的训练。
- ①：Instead of 直接优化本地模型，每一个device在优化局部模型时incorporates a structured sparsity regularization学习一个子网。
- ②：只有这个子网在中央服务器和设备之间传送。
- ③：只有各个设备的子网间相交的参数在服务器计算平均，不处理不相交的参数。例如图3中，设备1、2和N的子网的前两个部分是相交的，其它的部分不重叠。
- ④：然后更新的子网会发布到各个设备。
- 重复以上四个步骤。
- ⑤：最终，每个设备学习到一个个性化的模型。
- $C={C_{1},…,C_{N}}$代表N个devices，$C_{k}$代表第k个设备。
- $S_{c}\subset C$，代表每一个训练轮次选出的设备。
- $W_{k}$代表$C_k$的局部模型参数。
- 每一个设备 $C_k$ 同时学习一个local的mask $M_k \in {\left{0,1\right}}^{|W_k|}$，表示运用了结构化剪枝后的子网。$W_k\odot M_k$表示设备$C_i$的相关的子网参数。
- 设备$C_k$上的数据$D_k$被划分为训练集$D_k^{train}$、验证集$D_k^{val}$和测试集$D_k^{test}$。
- 上标T代表第T个轮次。
Learn Subnetwork for Joint Efficiency and Personalization（学习出一个既有效率又可以个性化的子网）
剪枝就是要找到对在训练上做推理的最有意义的参数。
unstructured pruning
structured pruning
- (a)代表未被剪枝过的模型，(b)代表结构化剪枝被剪枝过的模型，每个设备上的部分的channel被剪掉，(c)代表无结构化的剪枝。
- 结构化剪枝通常是channel-wise或者是filter-wise，相比无结构化剪枝虽然不够灵活但是对硬件却十分友好。
- 无结构化剪枝通常是parameter-wise，又更好的灵活性和压缩能力，但是需要特定的硬件支持。
本次使用结构化剪枝去做优化。不失一般性，以卷积为例，使用SGD优化局部模型的时候，每个device都想在卷积层上获取channel-wise的稀疏性，在全连接层上取得row-wise和column-wise的稀疏性，结构化剪枝：？
- 剪枝后的正则化项如上所示。？
运用结构化剪枝之后，mask optimization的训练的loss是：
- $F_D(W)$是本地数据的loss，$\lambda$是结构化稀疏正则化的系数。
- 通过优化等式（3），每个设备就可以通过判断W中的零值和非零值去derive M，也就是W中的零值和非零值会在M中分别标记为0和1。
第T轮通信轮，每一个参与设备下载相关的子网$W_k^T=W\odot M_k^T$，$M_k^T$由（T-1）th等式3计算得到。首先，设备在本地的验证集$D_k^{val}$上做验证，如果当前子网$W_k^T$的效果比预定义的阈值$acc_{threshold}$好并且当前的剪枝率$r_k^T$没有达到目标的剪枝率$r_{target}$，设备就会使用固定的剪枝率$r_p$剪枝$W_k^T$的low-magnitude的权重。结构化剪枝后，device能够得到$M_k^{T+1}$，$M_k^{T+1}$表示这$W_k^{T+1}$的稀疏结构且嵌入了数据依赖的特征。之后，设备使用数据集$D_k^{train}$基于$W_k^T\odot M_k^{T+1}$进行几个epochs的小批量的训练得到$W_k^{T+1}$。除了把子网参数$W_k^{T+1}$发送给服务器，每个clients也需要把相关的binary mask $M_k^{T+1}$发送给服务器，这个binary mask帮助服务器识别剪枝的位置，根据掩码保留参数。binary mask只使用1bit来表示每一位的参数，额外的通信开销和传输的浮点的模型参数相比可以忽略不记。最终，设备将$W_k^{T+1}$和$M_k^{T+1}$传输给服务器。
Personalization-Preserving Aggregation（中央服务器的聚合）
- 只对相交的参数进行聚合，然后把根据device的需要将聚合后的参数发送给对应的device。
- 具体的算法如下所示：
THEORETICAL ANALYSIS（理论上的分析，证明这样可以收敛）
见原文。
Notations and Terminologies（理论分析相关的术语）
Convergence Analysis（收敛性分析）
EVALUATIONS（实验的评测）
数据集：
- VGG16、EMNIST和CIFAR10做图像分类任务。EMNIST是一个手写数字识别的数据集，自然的将一个人写的数字分布到一个手机上。CIFAR10，每个device保留两个类别的数据，不同设备上的两个类别不一，设备上每个类别的数据量不一致。
- HAR数据集，手机的来自30个人的加速器和陀螺仪的数据，HAR包含6种活动。自然的将每个人的数据分不到一个设备上，我们用了3层全连接来识别人类的活动。
实验的实现：
手机：Google Pixel 3 (CPU) smartphones running Android 9.0，PyTorch 1.5
中央服务器：Intel Xeon E5-2630@2.6GHz and 128G RAM
耗电量检测：Monsoon power monitor [38] to measure the power consumption at runtime
其它配置见附件C的表4：
对比实验设置：
评测指标：
实验结果
Convergence Speed（收敛的速度）
又快又好。
Inference Accuracy vs. Communication Cost（推理精度和通信开销）
Hyper-Parameter Evaluation（超参的评测）
Number of Participating Devices：
Data Volume and Unbalance Rate：
Target Pruning Rate：
Runtime Performance（运行时的性能）
Reduction of Memory footprint：
Inference Speedup：
Reduction on Energy Consumption：
DISCUSSION（讨论）
- Generality of Hermes
- Defending Against Privacy Leakage
RELATED WORK（相关工作）
- Communication-Efficient Distributed Deep Learning
- Personalization for F
