摘要

联邦学习是一种机器学习设置，其目标是训练高质量的集中模型，同时训练数据仍然分布在大量客户机上，每一个客户机都具备不可靠且相对较慢的网络链接。咱们考虑学习这种设置的算法，在每轮测试中，每一个客户端都根据其本地数据独立计算对当前模型的更新，并将此更新与中央服务器通讯，在中央服务器上聚合客户端更新以计算新的全局模型。在这种状况下，典型的客户是手机，通讯效率是最重要的。web

1介绍

随着数据集愈来愈大，模型愈来愈复杂，训练机器学习模型愈来愈须要在多台机器上分布模型参数的优化。现有的机器学习算法是为高度受控的环境(例如数据中心)设计的，在这种环境中，数据以平衡的、i.i.d.的方式分布在机器之间，而且具备高吞吐量的网络。算法

最近，联邦学习(以及相关的分散方法) (McMahan & Ramage)提出了另外一种设置:一个共享的全球模型在来自参与设备联盟的中央服务器的协调下训练。参与其中的设备(客户机)一般数量很大，而且具备缓慢或不稳定的internet链接。当培训数据来自用户与移动应用程序的交互时，联邦学习的一个主要激励例子就出现了。数据库

联合学习使移动电话可以协做学习共享的预测模型，同时将全部培训数据保存在设备上，从而将机器学习的能力与将数据存储在云中的须要分离开来。培训数据保存在用户的移动设备上，设备被用做对其本地数据执行计算的节点，以便更新全局数据模型。这超出了使用本地模型对移动设备进行预测的范围对设备进行模型训练。上述框架不一样于传统的分布式机器学习,因为客户很是多，高度不平衡和非i.i.d。每一个客户机上可用的数据，以及相对较差的网络链接。在本文中，咱们将重点放在最后一个约束上，由于这些不可靠且不对称的链接对实际的联邦学习构成了特殊的挑战。服务器

在本文中，咱们提出了两种下降上行通讯成本的方法:结构化更新，咱们能够直接从有限的空间中学习更新，使用较少的变量，如低秩或随机掩码;还有草图更新，在那里咱们学习完整的模型更新，而后使用量化、随机旋转和子采样的组合对其进行压缩，而后再将其发送到服务器。在卷积网络和递归网络上的实验代表，该方法能够将通讯成本下降两个数量级。网络

为简单起见，咱们考虑用于联合学习的同步算法，其中典型的轮回包括如下步骤：
1.选择现有客户端的子集，每一个子集都下载当前模型。
2.子集中的每一个客户端根据其本地数据计算更新的模型。
3.模型更新从选定的客户端发送到服务器。
4.服务器聚合这些模型（一般经过平均）来构建一个改进的全局模型。架构

上述框架的简单实现要求每一个客户端在每轮中将完整模型（或完整模型更新）发送回服务器。 对于大型模型，因为多种因素，这一步骤极可能成为联合学习的瓶颈。 一个因素是Internet链接速度的不对称属性：上行链路一般比下行链路慢得多。 美国的平均宽带速度是下载55.0Mbps相对于上传18.9Mbps，一些互联网服务提供商更加不对称，例如Xfinity的下行速度为125Mbps而不是15Mbps。
此外，现有的模型压缩方案能够减小下载当前模型所需的带宽，并采用了加密协议，以确保在平均数百或数千个其余更新以前，没法检查单个客户端的更新，这进一步增长了须要上传的位数。框架

所以，研究可下降上行链路通讯成本的方法很是重要。本文研究了两种通用方法：
•结构化更新，咱们能够直接从受限空间学习更新，该更新可使用较少数量的变量进行参数化。
•草绘的更新，咱们在其中学习完整的模型更新，而后将其压缩后再发送到服务器。
能够结合使用第2节和第3节中详细介绍的这些方法，例如，首先学习结构化更新并将其草绘； 不过，咱们在这项工做中没有对这种组合进行实验。机器学习

在下文中，咱们正式描述问题。== 联邦学习的目标是从存储在大量客户端的数据中学习一个参数包含在一个实矩阵w∈R d1×d2中的模型。==该模型具备包含在实矩阵W∈R d 1×d 2中的参数。
咱们首先提供联合学习的纯沟通版本。 在t≥0的回合中，服务器将当前模型Wt分配给n t个客户端的子集St。 这些客户端根据其本地数据独立更新模型。 让更新的局部模型为Wt1 Wt2…，这样客户端i的更新能够写为。
这些更新多是在客户端上计算的单个梯度，但一般是更复杂的计算的结果，
例如，对客户端的本地数据集采起了多个随机梯度降低（SGD）步骤。 在任何状况下，每一个选定的客户端都将更新发送回服务器，在服务器上经过聚合全部客户端更新计算全局更新:
服务器选择学习速率ηt。 为简单起见，咱们选择ηt = 1。
==在第4节中，咱们描述了神经网络的联合学习，==其中咱们使用单独的2D矩阵W来表示每一层的参数。 咱们假设W右乘，即d1和d2分别表明输出和输入尺寸。
注意，彻底链接的层的参数天然地表示为2D矩阵。 可是，卷积层的内核是形状为＃input×width×height×＃output 的4D张量。 在这种状况下，W从内核重塑为形状（#input×width×height）×#output。分布式

概述和总结。

提升联合学习的通讯效率的目标是减小向服务器发送H的成本，同时学习存储在大量设备上的数据，这些设备的internet链接和计算可用性有限。咱们提出了两类通用方法，即结构化更新和草图更新。在“实验”部分，咱们评估了这些方法在训练深度神经网络中的效果。
在CIFAR数据的模拟实验中，咱们研究了这些技术对联合平均算法的收敛性的影响。收敛速度略有降低的状况下，咱们就能将通讯的数据总量减小两个数量级。这使咱们能够经过全卷积模型得到良好的预测精度，而总的通讯量却少于原始CIFAR数据的大小。在针对用户分区的文本数据进行的较大的实际实验中，咱们证实了咱们甚至能够只使用每一个用户的数据，就可以有效地训练递归神经网络进行下一个单词的预测。最后，咱们注意到咱们得到了最佳结果，包括使用结构化随机轮换对更新进行预处理。此步骤的实际效用在咱们的设置中是独一无二的，由于在典型的SGD并行实现中，应用随机轮转的成本将占主导地位，但与联邦学习中的本地培训相比，这是微不足道的。svg

2 结构化更新

通讯有效更新的第一类型将更新H限制为具备预约结构。 本文考虑了两种类型的结构：低秩和随机掩码。 须要强调的是，咱们直接训练该结构的更新，而不是像第3节中讨论的那样，将通常的更新与特定结构的对象相匹配/绘制草图。

低秩

咱们将对本地模型H的每次更新强制为最多k个秩的低秩矩阵，其中k是一个固定数。为此,咱们将H表示为两个矩阵的乘积。在后续计算中，咱们随机生成A并在局部训练过程当中考虑一个常数，而且仅对B进行优化。注意,在实际的实现中,A能够在这种状况下状况以随机种子的形式进行压缩，只须要将通过训练的B发送到服务器便可。这种方法当即节省了通讯中的d 1 / k因子。
咱们在每一个回合中为每一个客户从新生成矩阵A。咱们还尝试了固定B和培训A，以及同时培训B;二者都表现不佳。对这一现象的直观解释以下。咱们能够把B解释为一个投影矩阵，把A解释为一个重构矩阵。修复A并对B进行优化，相似于问“给定随机重建，可以恢复最多信息的投影是什么?”在这种状况下，若是重构是满秩的，则存在恢复由前k个特征向量张成的空间的投影。然而，若是咱们随机固定投影并搜索重建，咱们可能会很不幸，重要的子空间可能已经被投影出去了，这意味着没有重建能够作得很好，或者很难找到。

随机掩码

遵循预约义的随机稀疏模式（即随机掩码），咱们将更新H限制为稀疏矩阵。 模式在每轮中从新生成，并独立地为每一个客户机生成。 相似于低秩，稀疏模式能够由随机种子彻底指定，所以只须要将H的非零项的值连同种子一块儿发送。

3草图更新

第二种解决通讯成本的更新（咱们称之为草绘），首先在本地训练期间计算完整H，没有任何限制，而后以（有损）压缩形式对更新进行近似或编码，而后将其发送到服务器。 服务器在进行聚合以前对更新进行解码。为了进行草图绘制，咱们尝试了多种工具，这些工具能够相互兼容并能够共同使用：

子采样

每一个客户端只发送矩阵H，而不是发送H，每一个客户端只有通讯矩阵ˆH是由H一个随机的子集(比例)造成的。而后，服务器对子采样的更新取平均值，产生全局更新ˆH。 能够这样作，以使采样更新的平均值是真实平均值的无偏估计量：E [ˆH] = H。 与随机掩码结构化更新相似，掩码在每一个回合中对每一个客户端独立随机化，而且掩码自己能够存储为同步种子。

几率量化

压缩更新的另外一种方法是量化权重。
咱们首先描述将每一个标量量化为一位的算法。
h = (h 1 ,…,h d 1 ×d 2 ) = vec(H ), hmax= maxj (hj ), hmin = minj (hj )
由^h表示的h的压缩更新以下生成：

很容易证实〜h是h的无偏估计量。 与4字节浮点数相比，此方法可提供32倍的压缩率。 分析了这种压缩方案产生的偏差。对于每一个标量，也能够将其推广到1位以上。 对于b位量化，咱们首先将[hmin，hmax]平均分为2 ^ b个区间。 假设hi落在h’和h’‘的范围内。 经过分别用h’和h’'代替上述方程式的hmin和hmax来进行量化。 而后，参数b容许在精度和通讯成本之间进行平衡的简单方法。Alistarh等人最近提出了另外一种量化方法，该方法也经过减小通讯而求平均向量。（2016）。 能够在量化更新设置中相似地分析增量，随机和分布式优化算法（Rabbat＆Nowak，2005； Golovin等，2013； Gamal＆Lai，2016）。

结构化的旋转随机量化

经过结构随机旋转改进量化。当尺度在不一样维度上近似相等时，上面的1位和多位量化方法效果最好。

例如，当max = 1和min = -1且大多数值为0时，1位量化将致使较大的偏差。咱们注意到，在量化以前对h进行随机旋转（将h与随机正交矩阵相乘）能够解决此问题。在该工做中，代表结构化随机旋转能够将量化偏差下降O（d / logd）倍，其中d是h的维数。咱们将在下一部分中显示其实用性。

在解码阶段，服务器须要在聚合全部更新以前执行反向旋转。请注意，在实践中，h的维数很容易高达d = 10^6或更大，而且在计算上禁止生成（O d ^3）和应用（O d ^2）通常旋转矩阵。咱们使用一种结构化旋转矩阵，该矩阵是Walsh-Hadamard矩阵和二进制对角线矩阵的乘积。这下降了生成和应用矩阵到O(d)和O(dlogd)的计算复杂度，这与联合学习中的本地训练相比能够忽略不计。

4实验

咱们使用联邦学习进行了实验，以训练针对两个不一样任务的深层神经网络。首先，咱们使用卷积网络和人工分块数据集对CIFAR-10图像分类任务进行了实验，并详细研究了咱们提出的算法的性质。其次，咱们使用更现实的联邦学习场景——公共Reddit帖子数据，来训练一个循环网络来预测下一个单词。

Reddit数据集对于模拟联邦学习实验特别有用，由于它提供了天然的每一个用户数据分区(根据文章做者)。这包括在实际执行中可能出现的许多特征。例如，许多用户拥有相对较少的数据点，大多数用户使用的单词围绕特定用户感兴趣的特定主题汇集。

在咱们全部的实验中，咱们采用联合平均算法，该算法大大减小了训练一个好的模型所需的通讯次数。 可是，咱们但愿咱们的技术在应用于同步分布式SGD时将显示出相似的通讯成本下降。

对于联合平均，在每一个回合中，咱们随机地均匀选择多个客户端，每一个客户端在其本地数据集上执行几个时期的SGD，学习率为η。

对于结构化更新，SGD被限制为仅在受限空间中进行更新，也就是说，仅B项用于低级别更新，而无掩码项用于随机掩码技术。 从这个更新的模型，咱们计算每一个层H的更新。 在全部状况下，咱们都以各类学习率选择来运行实验，并报告最佳结果。

4.1 CIFAR-10数据集上的卷积模型

在本节中，咱们使用CIFAR-10数据集来研究做为联合平均算法一部分的拟议方法的属性。
CIFAR-10数据集中有50000个训练示例，咱们将其随机分为100个客户端，每一个客户端包含500个训练示例。 咱们使用的模型架构是全卷积模型，该模型来自被称为“模型C”的模型，总共有10 ^ 6个以上的参数。 尽管此模型不是最新的模型，但它足以知足咱们的需求，由于咱们的目标是评估咱们的压缩方法，而不是在此任务上得到最佳的准确性。
该模型有9个卷积层，其中第一个和最后一个具备比其余卷积少得多的参数。 所以，在整个部分中，当咱们尝试减少单个更新的大小时，咱们仅压缩内部的7层，每一个层具备相同的参数3。 对于全部方法，咱们都用关键字“模式”表示。 对于低秩更新 “模式= 25％”是指将更新的秩设置为全层转换的秩的1/4，对于随机蒙版或草绘，这是指除25％之外的全部参数都为零出。
在第一个实验（总结于图1中）中，咱们比较了第2节中介绍的两种：结构化更新、随机掩码更新。 主要信息是，随着咱们减少更新的大小，随机掩码的性能明显优于低秩。 特别地，当以回合数来测量时，随机掩码的收敛速度彷佛基本上不受影响。 所以，如右列所示，若是目标是仅使上传大小最小化(upload size)，那么减少更新大小的版本无疑是赢家。




图1:使用CIFAR数据进行结构化的更新以缩小各类模式的尺寸。
图2中，咱们比较告终构化更新和草绘更新的性能，没有进行任何量化。 因为在上文中，结构化随机掩码更新的执行效果更好，所以为清楚起见，咱们将低秩更新忽略不计。 咱们将其与草绘的更新的性能进行比较，在第3节中介绍了是否使用随机旋转对更新进行预处理以及是否进行预处理，以及两种不一样的模式。 咱们用“ HD”表示随机Hadamard旋转，而用“ I”表示无旋转。


图2:对CIFAR数据进行结构化随机掩码更新和不进行量化的草图更新的比较








图3：比较更新的草图，将更新与CIFAR数据的旋转，量化和二次采样相结合。

直观的指望是，直接学习结构化随机掩码更新要比学习非结构化更新好，后者被素描为用相同数量的参数表示。 这是由于经过草绘，咱们丢弃了训练中得到的一些信息。 经过草绘更新，咱们应该收敛到稍低的精度这一事实在理论上获得了支持，由于草绘更新会增长收敛性分析中直接出现的方差。 咱们在使用结构化随机掩码更新时看到了这种行为，最终咱们能够收敛到稍微更高的精度。 可是，咱们还看到，经过草绘更新，咱们可以稍快地得到适度的准确性（例如85％）。

在对CIFAR数据的最后一次实验中，咱们重点研究了第3节中介绍的全部三个元素的相互做用——子采样、量化和随机旋转。请注意，全部这些工具的组合将实现更高的压缩率。图3中的每对图都关注于特定的模式(子采样)，而且在每对图中，咱们用量化中使用的不一样比特来绘制性能图（有无随机旋转）。咱们在全部的图中均可以看到，随机旋转提升了性能。通常来讲，没有旋转的状况下，算法的性能不太稳定，特别是在量化比特数较少和模式较小的状况下。

为了强调节省通讯的潜力，请注意，经过随机旋转进行预处理，绘制出除了6.25％的更新元素以外的全部元素并使用2位进行量化，咱们在收敛性上只有很小的降低，而节省了256倍 就表示各个层的更新所需的位而言。 最后，若是咱们但愿最大程度地减小上传的数据量，则能够得到必定程度的准确性，例如85％，而总的交流量不到上传原始数据所需的一半。

4.2 LSTM对REDDIT数据的下一个单词预测

咱们构建了用于模拟联邦学习的数据集，该数据基于包含Reddit上公开可用的帖子/评论的数据(谷歌BigQuery)。就咱们的目的而言，数据库中的每一个帖子都由一个做者键控，所以咱们能够根据这些键对数据进行分组，假设每一个做者有一个客户机设备。有些做者有很是多的帖子，可是在每轮FedAvg(联邦平均)中，每一个用户最多处理32000个令牌。咱们省略了少于1600个令牌的做者，由于在模拟中每一个客户机都有固定的开销，并且数据不多的用户对培训贡献不大。这就剩下763430个用户的数据集，每一个用户平均拥有24791个令牌。为了进行评估，咱们使用一个相对较小的测试集，该测试集包含75122个标记，这些标记由随机保留的帖子组成。
基于此数据,咱们创建了LSTM下一词预测模型该模型被训练用于预测给定当前单词的下一个单词，以及从前一个时间步传递的状态向量。 该模型工做以下:经过在10017个单词(令牌)的字典中查找单词，将单词st映射到一个嵌入向量et(∈R^ 96)而后，et与模型在前一个时间步st1(∈R^256)中发出的状态组成一个新的状态向量st和一个“输出嵌入”Ot(∈R ^96)
在经过softmax归一化计算整个词汇表上的几率分布以前，经过内积对输出词表的嵌入项进行评分。与其余标准语言模型同样，咱们将每一个输入序列视为以隐式“BOS”(序列开始)标记开始((令牌开头)，以隐式“EOS”(序列结束)标记结束(令牌结尾)。与标准的LSTM语言模型不一样，咱们的模型对嵌入层和softmax层使用相同的学习嵌入。这使得模型的大小减小了约40%，而模型的质量却略有降低， 这对于移动应用程序来讲是一个有利的折衷。与许多标准LSTM RNN方法不一样的另外一个变化是，咱们 训练了这些模型以将单词嵌入限制为具备固定的L2规范1.0，发现能够缩短收敛时间。该模型总共有1.35M个参数。

为了减少更新的大小，咱们绘制了全部模型变量的草图，但一些小变量（例如误差）消耗的内存少于0.01％。 咱们使用AccuracyTop1进行评估，即模型赋予最高几率的单词是正确的。即便模型中预测为“未知”，即便词典中没有下一个真正的单词，咱们也老是将其视为错误。

在图4中，咱们对Reddit数据运行联邦平均算法，并使用各类参数指定草绘。在每一个迭代中，咱们随机抽样50个用户，这些用户根据本地可用的数据计算更新，并绘制草图，而后对全部更新进行平均。在每一个轮中对十、20和100个客户进行抽样的实验提供了相似的结论，以下所示。

在全部的图中，咱们将这三个组件组合起来，以绘制第3节中介绍的更新。首先，咱们应用随机旋转对本地更新进行预处理。此外，“草图分数”设置为0.1或1，表示更新的元素被子采样的分数。




图4:草图更新的比较，在Reddit数据上训练一个循环的模型，每轮随机抽取50个客户。

在左列中，咱们根据算法的迭代次数来绘制这个图。 首先，咱们能够看到，随机旋转的预处理效果具备显着的正效应，尤为是在量化位数较少的状况下。 有趣的是，对于全部选择的次采样率，将量化为2位的随机Hadamard变换不会形成性能损失。 要强调的一个重要指标是图中显示的回合数为2000。因为咱们每回合对50个用户进行采样，因此这个实验不会接触到大多数用户的数据。这进一步增强了在实际环境中应用联邦学习而不影响用户体验的说法。

在右列中，咱们将相同的数据与客户机须要与服务器通讯的兆字节总数进行比较。从这些图中能够明显看出，若是须要一个主要最小化该指标的工具(若是主要须要最小化这个度量)，那么咱们提出的技术将很是有效。 固然，这些目标都不是咱们在实际应用中要优化的目标。 尽管如此，鉴于当前缺少大规模部署联合学习固有的问题的经验，咱们认为这些是在实际应用中有用的代理。

图5：每轮培训中使用的客户数量的影响。

最后，在图5中，咱们研究了单轮使用的客户数量对收敛性的影响。 咱们对固定数量的回合（500和2500）运行联邦平均算法，每回合使用不一样数量的客户端，将更新量化为1位，并绘制得出的精度。 咱们看到，每轮有足够数量的客户（在本例中是1024个），咱们能够将子采样元素的比例下降到1％，与10%相比，精度只会有微小的降低。在联邦设置中，这是一个重要且实用的权衡:能够在每轮中选择更多的客户机，同时使每一个客户端之间的通讯更少（例如，更主动的子采样），并得到与使用较少客户端相同的精度，可是每一个客户端它们之间通讯更多。 当有许多客户端可用时，前者可能更可取，可是每一个客户端的上传带宽很是有限-这在实践中很常见。