【解读】通过客户端采样实现高效通信效率联邦学习 Communication-Efficient Federated Learning via Optimal Client Sampling

通过客户端采样实现高效通信效率联邦学习

44 citations (Semantic Scholar/arXiv) [2023-05-19]
arXiv:2007.15197 [cs, stat]

摘要

汇总本地模型需要在客户端和中央服务器之间频繁通信大量信息。本文提出了一种新颖、简单和有效的方法，在通信受限制的情况下基于从具有信息更新的客户端收集模型并估计未传递的本地更新来更新中央模型。特别地，通过奥恩斯坦-乌伦贝克过程对模型权重的进展进行建模，我们可以推导出一种选择具有显着权重更新的客户端子集的最佳采样策略。中央服务器仅从所选客户端收集更新的本地模型，并将其与未被选中进行通信的客户端的估计模型更新相结合。

在逻辑回归的合成数据集、EMNIST的分类任务和使用莎士比亚数据集的现实语言建模任务上测试了该策略。结果表明，与基线相比，所提出的框架在保持竞争力或实现更好性能的同时显著减少了通信。该方法代表了通信高效的FL的新策略线，这与现有的用户本地方法（如量化或稀疏化）是相互独立的，因此是对这些现有方法的补充而不是替代。

引入

模型越来越大，上传成本越来越高，但是有的更新上传以后作用有限，特别是接近收敛的时候。

除了常用的量化和稀疏化方法，我们还可以只上传那些判断为有信息量的更新。

思路：将随机梯度下降（SGD）期间用户权重向量的变化建模为多维随机过程，并让每个用户根据观察到的样本路径部分的信息量（例如，过程距稳态有多远）来决定是否向服务器发送更新。将SGD迭代中的权重解释为离散化基础OU过程样本路径所得到的点。

奥恩斯坦-乌伦贝克过程（OU）- 一种由均值和协方差函数参数化的连续随机过程。

最优策略变为更新的范数阈值。于是问题转化为挑选这个阈值。同时为了保证效果，没有达到阈值的客户端的更新会通过OU过程来估计而不是简单地丢掉或用默认值代替。

相关

联邦学习不用多说，有一些用于其中的减少通信量的方法：

Deterministic approaches such as low” (Ribero 和 Vikalo, 2020, p. 4) rank approximation, sparsification, subsampling, and quantization [Koneˇcn y et al., 2016, Alistarh et al., 2017, Horvath et al., 2019], as well as randomized approaches including random rotations and stochastic rounding [Suresh et al., 2017] and randomized approximation [Koneˇcn y and Richt ́arik, 2018], can be used to reduce the communication while maintaining high accuracy. Note that these methods may be leveraged on the server side as well [Caldas et al., 2018].” (Ribero 和 Vikalo, 2020, p. 5)

1. 低秩近似：低秩近似是一种通过将矩阵或张量分解为低秩矩阵的乘积来减少数据维度并压缩数据的方法
2. 稀疏化：稀疏化是一种通过将模型参数的值设为零来减少数据维度的方法。稀疏化方法可以基于权重、梯度或其他特征进行选择。
3. 子采样：子采样是一种通过随机采样来减少数据大小的方法。在联邦学习中，可以通过在客户端模型参数中随机选择一部分进行传输，来减少通信量并降低数据传输的延迟。
4. 量化：量化是一种通过将模型参数的值映射到有限的离散值来减少数据大小的方法。在联邦学习中，量化可以通过将客户端模型参数的浮点值转换为定点值或其他离散值来减少通信量，并降低数据传输的延迟。量化方法可以基于模型参数的分布、精度等进行选择。
5. 随机旋转和随机舍入：随机旋转和随机舍入是一种通过引入随机性来减少数据大小的方法。在联邦学习中，可以将客户端模型参数随机旋转或舍入，从而减少通信量，并降低数据传输的延迟。这些方法可以根据数据的特性和需求进行选择。
6. 随机逼近：随机逼近是一种通过引入随机性来近似数据的方法。在联邦学习中，可以通过使用随机逼近方法来近似客户端模型参数，从而减少通信量并降低数据传输的延迟。这些方法可以基于模型参数的分布、精度等进行选择。

也有一些方法取消模型更新，比如阈值为相对幅度变化（坏处是近收敛时更新停止“Hsieh et al. [2017]” (Ribero 和 Vikalo, 2020, p. 5)），但是研究发现会导致性能不稳定；也有根据时间更新阈值或者根据服务器判断，但是对于新加入的客户端不友好；也有考虑对参数二值化、模型剪枝和限定规模的做法。

Ornstein-Uhlenbeck（OU）过程是一种连续时间的随机过程，通常用来表示一个系统在存在一定的回归力量（回归力量指系统向其均值回归的趋势）的情况下，随机漂移的行为。OU过程的漂移部分包括一个线性回归项，它将该过程的当前值与其均值之间的差异乘以一个回归系数，表示回归力量。此外，OU过程还包括一个高斯白噪声项，它表示系统中的随机波动。OU过程在金融学、物理学、生物学、工程学等领域有广泛应用，近年来在机器学习中也被用于描述模型参数的随机漂移行为。在文本中提到的OU过程是通过建模SGD迭代中权重向量的变化，来提高联邦学习中通信效率的一种方法。

OU相当于在标准Wiener过程上加入了扰动。Wiener Process 是一种连续时间的随机过程，它的每一时间步的数学表达式可以使用以下方式表示：$W(t)=\sqrt{t}Z$，z是标准正态分布。

如何估计这个过程的参数？首先把他离散化，然后用最小平方法（就是最简单的估计y=ax+b中的a、b的那个方法）计算，所以下一过程的${\theta }_{t+1}=a{\theta }_t+b_t$，这两个数可以根据特定时间点上采样计算

特定时间点可以选用信号幅度增强阈值（OU过程最优采样点）；

同时OU过程和SGD是有联系的（说明可以建模）细节见论文3.1（根据中心极限定理和平滑损失函数得到）

算法与细节

1. 每一轮还是选N个客户端，广播它们模型和阈值；
2. 本地更新后计算更新值，如果达到阈值则上传梯度和范数；否则只上传范数；
3. 服务器计算收到的更新的范数的均值和标准差，然后根据OU过程计算缺失客户端的更新，最后更新全局模型并更新下一轮的阈值。

服务器保留部分参数从而可以动态更新缺失客户端的更新估计值。服务器的阈值第一轮是0（所有人都发送更新），否则是上一轮更新的范数减去上一轮更新范数的标准差。

全过程伪代码

客户端更新比较寻常，唯一的不同是回传更新的2范数

实验

合成的数据集，EMNIST，Shakespeare；

第一个用逻辑回归，第二个用CNN，第三个用RNN

第一个100客户端，数据x和\beta正态分布，标签$y=X_i^T\beta$，10000个样本

第二个3843客户端，每个图片和其用户相关所以是noniid的

第三个725客户端，各代表一个戏剧中的说话角色，最多各有128句并分为训练和验证集；不在词汇表中的词用oov符号代替，每句话最多20词，RNN 1M参数做下一个词预测

每轮10个，100轮。baseline是固定阈值的FedAvg，一种直接不要不到阈值的更新，另一种把不到阈值的更新设置为0.

结论：效果更好，虽然还是比不上全部都选，但是相比ignore更稳定、比zero更快

思考

比较naive的方法，用ou过程估计SGD是个有趣的想法；同时效果也比较稳定，实验够全面、考虑也比较周到。

缺点：OU过程估计不一定准确，会影响准确率；比例仍然固定，没有动态场景下的估计；对于OU过程的计算和估计比较复杂；公平性不确定；

思考：参数变化的2范数真的越大越好吗？