摘要

现代移动设备可以接触到大量可供模型学习的数据，这反过来也可以大大增强设备用户体验。例如，语言模型可以实现语音识别和文本输入，图像模型可以帮助自动挑选优良的照片。然而，这些数据往往隐私敏感且数量庞大，所以，把数据记录到数据中心并并行训练的方法不可行。
我们对此作了一些改变–把训练数据分散在移动设备上并通过聚合本地计算更新来实现共享模型的学习。我们把这种分散式的方法称为联邦学习。
我们提出了一种基于迭代模型平均的深度网络联邦学习的实践方法，并在 5 5 5中不同的模型和四个数据集上进行了大量的模型评估。这些实验表明我们的方案对不平衡和非独立同分布的数据分布具有鲁棒性，这是这一场景的决定性特征。
通信成本是主要的约束条件，这种方法与同步随机梯度下降相比，所需的通信轮次有着 10 − 100 10-100 10−100倍的下降。

简介

手机、平板是很多人主要的计算设备。设备上的各种传感器（相机、麦克风、GPS等）可以接触到大量的数据，并且这些数据是私有的。数据的敏感性质表明要如果集中存储就会有承担很多风险和责任。
我们研究了一中学习技术，可以使得用户在不对数据进行集中存储的条件下从训练的模型中集中式地获取收益。我们将此方法称为联邦学习，因为学习任务可以通过多个参与设备（我们称之为client）形成的松散联邦解决，且存在一个中心服务器server对这些设备进行协调。每一个client都会有不会上传至server的本地数据集，然而，每个client会把计算的更新（梯度）上传至server维护的当前全局模型中，并且也只有当上传更新时两者才会进行通信。鉴于这些更新（梯度）是针对于更新当前模型的，所以一旦被采用，就不必要对它们进行存储了。
这种方法的主要优点是将模型训练与直接访问原生数据集相互分离。显然，对于server协调者仍是需要一些信任的。然而，对于可以依据每个客户端可用数据为基础来设定训练目标的应用，联邦学习通过限定攻击面于设备而非设备和云，这就可以显著降低隐私和安全风险。
我们的主要贡献包括：

1. 识别问题：来自移动设备分散化数据的训练问题作为一个重要的研究方向；
2. 选定算法：一个直接了当、实用的，可用于这里场景的算法；
3. 实验评估：对这里所提方法的大量实验评估。

具体地说，我们提出了FedAvg算法，他将每个client中的局部随机梯度下降与server进行聚合，实现了模型平均。我们对此算法做了大量的实验，证明了他对与不平衡和非独立同分布的数据具有鲁棒性，并能够数量级地降低分散化数据上训练深度网络所需的通信轮次。

联邦学习

理想化的联邦学习具有以下属性：

1. 相比于从数据中心的代理数据进行训练来说，从移动设备的原生数据上训练具有明显优势；
2. 鉴于数据隐私敏感或者数量庞大的原因，最好不要为了模型训练而将其上传到数据中心；
3. 对于监督任务，数据标签可以自然地从用户交互中推断出来。

移动设备上很多驱动智能行为的模型都满足以上标准。这些任务潜在的训练数据都可能隐私敏感。

隐私

联邦学习相比于在数据中心训练保存下来的数据来说具有显著的隐私优势。（中心节点保存数据）即便匿名数据，通过与其他数据联合也会将用户数据置于风险之中。相反，联邦学习中传输的信息则是改进特定模型所必须的最小更新（梯度）。更新本身是暂时的。（更新）不会带有相比原生训练数据更多的信息，且一般来说会携带更少的。进一步来说，聚合算法不必知晓更新的来源，所以更新可以不识别元信息而在混合网络中传输或通过一个可信第三方。我们简要讨论了联邦学习与安全多方计算和差分隐私。

联邦优化

我们将联邦学习中隐含的优化问题称之为联邦优化，并将其与分布式优化联系起来。联邦优化有几个可以将其与典型分布式算法相互区分的关键属性：

1. 非独立同分布Non-IID
2. 不平衡性Unbalanced
3. 大规模分布Massively distributed
4. 有限通信Limited communication

我们重点是在优化Non-IID、Unbalanced属性，以及通信约束这个关键本质。部署的联邦优化系统还必须解决无数实际问题：随着数据的增加和删减，客户端数据集也在变化；客户端可用性以复杂的方式与本地数据分布相关；客户端从不响应或发送损毁的更新。
这些问题已超过了当前工作的范围；相反，我们使用了适合实验的受控环境，但仍然搞定了客户端可用性、unbalanced和non-IID data问题。**我们假定在多轮通信中的一个同步更新方案，有一组K个客户端组成的固定集合，每个客户端都有一个固定的本地数据。在每一轮开始，随机的一小部分比例C的客户端被选定，并且服务端把当前全局算法状态（当前的模型参数）发送给被选中的每一个客户端。为了提高效率我们只选中一小部分客户端，因为我们的实验表明超过某一点继续增加客户端的数量回报就会持续衰减。基于全局模型参数以及本地数据集，每一个被选中的客户端开始执行本地计算，并再把更新发送到服务端。而后服务端再把收到的这批更新应用给全局参数，**然后就是不断重复执行这个过程。
当我们聚焦在“非凸”神经网络目标时，我们考虑的算法会是可以应用到（满足）以下形式的任意“有限和”目标的：
min ⁡ w ∈ R d f ( w ) w h e r e f ( w ) = d e f 1 n ∑ i = 1 n f i ( w ) \min\limits_{w\in R^d}f(w)\qquad where \qquad f(w)\overset{def}{=}\dfrac{1}{n}\sum\limits_{i=1}^{n}f_i(w) w∈Rdmin​f(w)wheref(w)=defn1​i=1∑n​fi​(w)
对于机器学习问题，我们一般令 f i ( w ) = l ( x i , y i ; w ) f_i(w)=\mathcal{l}(x_i, y_i; w) fi​(w)=l(xi​,yi​;w)，也就是，在模型参数 w w w上预测样本 ( x i , y i ) (x_i, y_i) (xi​,yi​)的损失。我们假设有 K K K个客户端，也正是对应着数据的 K K K份分区。 P k \mathcal{P_k} Pk​表示客户端 k k k上的数据点索引集， n k = ∣ P k ∣ n_k=|\mathcal{P_k}| nk​=∣Pk​∣。于是我们可以重写上述目标函数：
f ( w ) = ∑ k = 1 K n k n F k ( w ) w h e r e F k ( w ) = 1 n k ∑ i ∈ P k f i ( w ) f(w)=\sum\limits_{k=1}^{K}\dfrac{n_k}{n}F_k(w)\qquad where \qquad F_k(w)=\dfrac{1}{n_k}\sum\limits_{i\in \mathcal{P_k}}f_i(w) f(w)=k=1∑K​nnk​​Fk​(w)whereFk​(w)=nk​1​i∈Pk​∑​fi​(w)
如果分区 P k \mathcal{P_k} Pk​是通过均匀随机地将训练样本分发客户端上形成的，那么就有 E P k [ F k ( w ) ] = f ( w ) E_{\mathcal{P_k}}[F_k(w)]=f(w) EPk​​[Fk​(w)]=f(w)，其中这一套实例上的期望被分配给了固定的客户端 k k k；我们称在这里这个不成立的情形为非独立同分布场景。
在数据中心优化中，通信成本很小，但是计算成本占了很大的比重，最近也在强调使用GPU来降低这些成本。相反，在联邦优化中，通信成本是主导----我们一般会遇到小于 1 1 1MB/s的上传带宽限制。进一步来说，我们预期每天每个客户端只会参与到一小部分更新轮次之中。再从另一方面看，因为任意单个设备级数据集与整体数据集相比都是较小的，并且现代智能手机都有相对较快的处理器（也包括GPU们），与许多模型类型的通信成本相比计算成本基本上快算是免费了。所以，我们的目标就是：使用额外的计算来减少训练一个模型所需的通信轮数。主要有 2 2 2种方法来增加（额外）计算：

1. 增加并行：在每一个通信轮中，使用更多个独立工作的客户端；
2. 增加每一个客户端上的计算：在每一个通信轮次中，每个客户端不是执行一个简单的诸如梯度计算这样的，而是执行一个更复杂的计算。

这 2 2 2种方法我们都做了研究，但达到加速的主要是在每个客户端增加计算量，一旦最低限度的并行已经使用。

FedAvg算法

最近大量的成功的深度学习应用基本都是靠各种各样的随机梯度下降算法来进行优化的。事实上，很多进展也可理解为使模型结构（也包括损失函数）更适于（更可以）被一个简单的基于梯度的方法优化。因此，也很自然的从SGD开始构建联邦优化的算法。
SGD可以单纯地被应用到联邦优化问题上，单轮通信时完成单一批次的梯度计算。这种方法在计算方面是高效的，但为了得到优良的模型需要非常多次的训练轮次。在我们的CIFAR-10实验中，我们以此作为基线。
在联邦场景中，让更多的客户端参与进来几乎没什么时间成本，因此对于我们的基线我们使用大批量同步SGD。Chen的实验证明在数据中心场景中这种方法可以达到sota水准，且超过了异步方法。为了在联邦场景中采用此方法，我们在每一轮选择了 C C C比例的client，并计算了这些client所持有的所有数据的梯度损失。因此， C C C控制着全局批量大小，当 C = 1 C=1 C=1时代表了全批次梯度下降。我们把这样基准算法称为FedSGD。
FedSGD算法的典型应用为：令 C = 1 C=1 C=1且有一个固定的学习率 η \eta η，让每个客户端 k k k计算 g k = ∇ F k ( w t ) g_k=\nabla F_k(w_t) gk​=∇Fk​(wt​)，是在当前模型 w t w_t wt​时他本地数据上的平均梯度，中心的server会聚合这些梯度然后进行更新 w t + 1 ← w t − η ∑ k = 1 K n k n g k w_{t+1}\leftarrow w_t-\eta \sum\limits_{k=1}^K\dfrac{n_k}{n}g_k wt+1​←wt​−ηk=1∑K​nnk​​gk​，因此 ∑ k = 1 K n k n g k = ∇ f ( w t ) \sum\limits_{k=1}^{K}\dfrac{n_k}{n}g_k=\nabla f(w_t) k=1∑K​nnk​​gk​=∇f(wt​)。等效的更新表达式可以写作如下： ∀ k , w t + 1 k ← w t − η g k \forall k, w_{t+1}^k\leftarrow w_t - \eta g_k ∀k,wt+1k​←wt​−ηgk​且 w t + 1 ← ∑ k = 1 K n k n w t + 1 k w_{t+1}\leftarrow \sum\limits_{k=1}^{K}\dfrac{n_k}{n}w_{t+1}^{k} wt+1​←k=1∑K​nnk​​wt+1k​。也就是说，每个client在当前模型上使用它本地的数据执行一步的梯度下降，然后server会对各个结果迷行进行一次加权平均。一旦以这种方式写了算法，我们可以在server的加权平均前，对每个client迭代更多轮次 w k ← w k − η ∇ F k ( w k ) w^k\leftarrow w^k-\eta \nabla F_k(w^k) wk←wk−η∇Fk​(wk)来增加计算量。我们把这种方法称为FedAvg算法。计算量由三个关键参数控制：

1. C C C，每一轮参与计算的client比例；
2. E E E，每一轮每个client在当地数据集上进行训练的次数；
3. B B B，client进行更新时的局部小批量。

当 B = ∞ B=\infty B=∞时代表用当地数据集全体作为单一小批量。因此，在算法簇的端点，我们使用 B = ∞ B=\infty B=∞和 E = 1 E=1 E=1来代表FedSGD算法。对于一个具有 n k n_k nk​个数据样本的client来说，每一轮的局部更新数量 u k u_k uk​是通过 u k = E n k B u_k=E\dfrac{n_k}{B} uk​=EBnk​​给出的。算法完整的伪代码由下表给出：

对于非凸优化的目标函数而言，在参数空间中进行模型平均可能会产生一个随机的坏模型。

实验结果

我们的最初研究是两个数据集上的三个模型簇。

图像模型

前两个模型簇是MNIST数据集上的数字识别任务：

1. 一个简单的MLP，有两个隐藏层，每层有200个单元且使用ReLu激活函数，我们称之为2NN；
2. 一个有两个 5 × 5 5\times 5 5×5卷积层（第一层有32个通道，第二层有64个通道，每一层都是KaTeX parse error: Undefined control sequence: \time at position 2: 2\̲t̲i̲m̲e̲ ̲2最大池化），一个有512个单元的全连接层以及ReLu激活函数和最后的softmax输出层（总共有1663370个参数）的CNN。

为了研究联邦优化，我们也必须要明确如何在各个client之间分发数据集。我们使用了两种方式分发MNIST数据集：

1. 独立同分布IID，数据是随机刷新的，600个client每个都有100个样本
2. 非独立同分布Non-IID，先根据数字对图片进行排序，然后划分为200个样本大小为300的分区，然后对100个client每个都分配2个分区，这样大部分client会只有两种数字的样本。

表1是图像分类任务的实验结果。在2NN中保持 E = 1 E=1 E=1，在CNN中保持 E = 5 E=5 E=5，注意当 C = 1 C=1 C=1时是指每次只选择一个client。因为我们使用了 100 100 100个client，所以表中的每一行分别代表了 1 , 10 , 20 , 50 , 100 1,10,20,50,100 1,10,20,50,100个client。每个表项给出了达到目标精确度（2NN为97%，CNN为99%）所需的通信轮数以及相比于 C = 0 C=0 C=0时的加速倍率。五个表中的横向位置是指在规定时间为未达到目标精确度。

语言模型

语言模型建立的莎士比亚全集的数据集。将剧本中说话行数至少两行的语者的话单独拎出来作为一个client的数据集，这样就有了1146个client，同时是Non-IID的数据集（训练集和测试集比例为4:1）。为了对照实验，也做了IID的数据集。模型采用LSTM簇。得到的结果如下表：

表中内容是FedAvg算法达到目标精确度所需的通信轮数。 u u u列是指每个轮次所需的更新次数（ u = E n K B u=\dfrac{E_n}{KB} u=KBEn​​）。


以上两个图比较直观易懂。
我们还用了CIFAR数据集对FedAvg算法进行了验证，其中有50000张训练样本，10000张测试样本，100个client（每个client有500张训练样本和100张测试样本），只考虑了平衡和独立同分布的场景。

得到的表格结果如上。