0.序言
联邦学习（FederatedLearning）容许用户在将数据保留在本地端不共享的前提下产生一个联合体训练得到全局模型，进而有效解决数据隐私和安全保护问题。同时，还可以有效应用联合体各方用户所把握的标明数据，解决标明数据欠缺的问题。在联邦学习构架的每一轮学习过程中，中央服务器在当前全部顾客端中选取一些顾客端子集并将全局模型下发给那些顾客端子集。之后，这种顾客端子集在本地运行随机梯度增长（SGD）等优化处理步骤后生成本地模型。最后，顾客端子集将本地模型发送回中央服务器。反复执行训练过程直至模型收敛，生成最终的全局模型。
目前，联邦学习的应用面临四个主要问题：通讯开支问题、隐私保护问题、客户端无状态问题和顾客端中数据非独立同分布问题。其中，通讯开支问题主要是由顾客端和中央服务器之间经由网路联接和传输数据（模型、参数）所导致的。隐私保护问题主要是指经由网路传输时用户信息、模型信息的隐私和安全保护问题。顾客端无状态问题是指通常情况下在多轮训练期间，没有一个顾客端会参与超过一次的训练。顾客端中数据非独立同分布问题则是指不同顾客端，非常是边沿设备，所搜集到的数据一般不是独立的，也不具备相同的数据分布特点。本文重点关注通讯开支问题的最新研究进展。通讯带宽是联邦学习的主要困局，由于大量的设备都将其本地更新发送到中央服务器中。因而，对于一个通讯效率高的联邦学习算法来说，这些更新必须以压缩和不频繁的形式发送。
在实际场景中，非常是在所需的全局模型规模较大的情况下，网路带宽限制和工作节点数目可能会减缓联邦学习的通讯困局，因而导致顾客端设备掉队/退出的问题。在精典的联邦学习框架下，系统会将一些网路带宽受限或访问受限的顾客端排除在训练的轮次之外，即不将全局模型发送给那些顾客端进行本地优化。这些简单的处理方法会大大影响这种顾客端所提供的服务，从而影响用户的使用体验。
针对通讯开支问题最简单直接的解决方案是以牺牲模型确切度为代价、在联邦学习的整体框架中仅训练占用通讯空间较小的低容量模型。从这个角度出发，来自Google的研究人员Koneˇcnýetal.提出了一种增加上行通讯成本（Client-to-ServerFLCommunication）的方式[1]：顾客端只将本地估算得到的模型更新传递到中央服务器，而不是完整的本地模型。很其实，这些方式其实还能减少通讯成本，而且并不能满足复杂场景下业务应用须要。在此基础上，来自同一研究小组的Caldasetal.提出了一种才能有效减少下行通讯成本（ServertoClientCommunication）同时与已有增加上行通讯成本方式无缝集成的方式[2]，具体包括在服务器到顾客端的全局模型上使用有损压缩，以及容许用户在全局模型的较小子集上高效完成本地训练的、能够同时降低顾客端到服务器的通讯成本和本地估算的FederatedDropout。
与这两篇文章的思路类似，Rothchildelal.提出了一种使用CountSketch对顾客端模型更新进行压缩处理的方式FedSGD[3]。因为CountSketch是线性的，可以通过Sketch估算动量和偏差累积，进而将动量和偏差累积的估算任务从顾客端转移到中央服务器，克服了稀疏顾客端参与更新的问题，同时保持高压缩率和良好的收敛性。Reisizadehetal.提出了一种周期平均和量化的处理方式FedPAQ[6]，量化处理本身也是压缩的一种方法。FedPAQ容许网路中的顾客端在与中央服务器同步之前执行本地训练，仅将活跃顾客端的更新发送回中央服务器，且发回的仅为本地信息的量化版本。与上述从压缩角度出发的工作较为不同的是，Hamerelal.提出了一种主要解决下行通讯成本问题的集成方式：FedBoost[4]。集成方式是机器学习中的一种通用技术，用于组合多个基本预测因子或专家来创建一个更精确的模型。FedBoost主要通过学习一组预先训练好的基本预测因子（BasePredictors）实现联邦集成（FederatedEnsembles）。据悉，Malinovskyelal.提出了一种高效通讯的分布式定点优化方式（Fixed-pointoptimization）[5]，从解决优化问题或找寻凹凸函数的鞍点的角度出发限制顾客端本地估算，进而解决联邦学习通讯开支困局问题。
1.解决通讯开支问题的研究进展
1.1通过压缩方式解决通讯开支问题
通过压缩处理减轻联邦学习框架中上行、下行传递的数据量是最直接的解决通讯开支问题的方式。我们首先来看一看这一类技巧的研究进展情况。
1.1.1模型更新上传方式[1]
联邦学习的目标是从储存在大量顾客端的数据小学习包含在真实矩阵W中参数的模型。在第t轮训练过程中，中央服务器将当前模型W_t分发给总共n_t个顾客端的子集S_t。这种顾客端子集按照其本地数据独立训练并更新本地模型。具体介绍，第i个顾客端的更新过程如下式所示：
这种更新可以是在顾客端上估算得到的单个梯度值，也可以是使用更复杂的估算方法得到的结果，比如，在顾客端的本地数据集上执行多个随机梯度增长（StochasticGradientDescent，SGD）处理。选取的顾客端会将更新发送回中央服务器，中央服务器通过聚合所有顾客端更新来估算得到全局模型：
其中，η_t表示中央服务器中的学习速度。
作者介绍两种部份模型更新上传至中央服务器的方式。值得注意的是，本文只关注了顾客端-中央服务器这一段的上行通讯成本。第一种方式为结构更新（StructureUpdate）。令更新(H_t)^i为预先定义的结构。本文具体考虑两种结构：低秩（Low-Rank）和随机掩模（RandomMask）。在低秩情况下，令(H_t)^i=(A_t)^i・(B_t)^i。在后续估算过程中，随机生成(A_t)^i并在本地训练过程上将其考虑为一个常数，只优化(B_t)^i。在实际实现中，可以将(A_t)^i压缩成随机种子的方式，顾客端只须要向中央服务器发送训练后的(B_t)^i。在每一轮次的更新中为每位顾客端重新生成(A_t)^i矩阵。在随机掩模的情况下，令(H_t)^i为一个遵守预定义的随机稀疏模式（即随机掩模）的稀疏矩阵。在每一轮次的更新中每位顾客端独立生成新的掩模。与低秩方式类似，稀疏掩模可以通过一个随机种子生成，因而只须要将(H_t)^i的非零项值与种子一起发送。
第二种方式为草图更新（SketchedUpdate）。首先，在顾客端完整的估算模型更新(H_t)^i。在发送至中央服务器之前，以有损压缩进行编码处理。中央服务器收到编码后解码再进行聚合处理。生成Sketch的方式包括：（1）下取样（Subsampling），取样更新的平均值是真实平均值的无偏恐怕值E[H^_t]=H_t。与随机掩模的结构化更新类似，下取样网段在每轮中也是在每位顾客端独立随机取样的，但是网段本身可以储存为同步种子。（2）机率量化（Probabilisticquantization），正式模型的权重（weights）量化处理。对于更新(H_t)^i，令h=(h_1,...,h_(d1x2d))=vec((H_t)^i)，h_max=max_j(h_j)，h_min=min_j(h_j)。h的压缩更新为：
对于4个字节的浮点数，这些方式实现了32倍的压缩。对于一个比特的量化处理来说，首先均匀分辨[h_min,h_max]为2^b个间隔。h_i落在h’和h’’限定的区间内。量化操作将上述等式的h_min和h_max分别替换为h’和h’’。设定参数b以平衡确切度和通讯成本，并通过随机化旋转改进量化。当尺度在不同维度上近似相等时，上述1比特和多比特量化方式疗效最好。当max=1，min=-1，且大部份值为0时，1比特量化将会造成较大偏差，通常可以通过在量化前对h进行随机旋转（h除以随机正交矩阵）来解决这个问题。在解码阶段，中央服务器须要在聚合所有更新之前执行反向旋转。
作者在实验中对比的是结构更新和草图更新两种方式的模型疗效，如图1CIFAR库和图2REDDIT库中的结果。CIFAR库中使用的模型有9个频域层，其中第一层和最后一层的参数显著多于其他层。在压缩处理过程中只压缩内部7层，每位层都具有相同的参数。图1中使用关键字「mode」表示这些技巧。对于低秩更新，「mode=25%」表示更新的秩被设置为全层变换的秩的1/4，对于随机掩模（RandomMask）或草图勾画（Sketching），「mode=25%」的意思是对25%以外的所有参数进行置零处理。由图1，结构化的随机掩模方式疗效更优。
图1.在CIFAR数据库中结构化随机网段更新和无量化Sketched更新的对比结果。
基于REDDIT数据库，作者训练了一个LSTM词组预测模型。该模型被训练成给定当前词组和前一时间传递的状态向量来预测下一个词组。为了降低更新的规模，除一些显存消耗大于0.01%的微小变量（比如bias）外对所有模型变量进行Sketching处理。图2中使用AccuracyTop1进行评估，即模型赋于最高机率的词组是正确的预测结果。
图2.Sketching比较，在Reddit数据上训练一个LSTM模型，每轮随机抽样50个顾客端。
1.1.2有损压缩方式[2]
在1.1.1节中提出的模型更新传递方式也是一种有损压缩策略，它主要解决的是顾客端-中央服务器的上行通讯开支问题，本节中的方式主要聚焦中央服务器-顾客端的下行通讯开支，同时能够与处理上行通讯开支的方式进行无缝集成。
图3.有损压缩方式整体思路。
该有损压缩方式的整体思路如图3所示。（1）通过FederatedDropout构造子模型，（2）对生成的对象进行无损压缩，来减少通讯模型的大小。之后将这个压缩模型发送给顾客端，（3）顾客端使用本地数据对其进行解压缩和训练，（4）压缩最终的本地更新。将本地更新发送回中央服务器，（5）中央服务器执行解压缩，（6）中央服务器聚合生成全局模型。
在技巧第（2）步中所提及的「无损压缩」借鉴的是节1.1.1中探讨的方式，包括基本变换、下取样、概率量化等。只不过本文将这种压缩应用于中央服务器到顾客端的交换中，这也意味着，这些方式不能借助在中央服务器端通过无损压缩平均噪音解压缩处理（AveragingtheNoisyDecompressions）的改进。关于下取样和机率量化处理本节不再深究。关于基本变换的处理，作者Koneˇcnýetal.在文献[1]中并未详说。实际上文献[1]中的基本变换为随机Hadamard变换（HD），目的是均匀地将向量信息分布在各个维度上。而本文中除随机Hadamard变换外，还考虑了Kashin表征方式（K）因而尽可能在每位维度上传播向量的信息
。
为了进一步减少通讯成本，本文引入FederatedDropout的有损压缩方法，即每位顾客端不须要局部训练全局模型的更新，只是训练一个更小的子模型的更新。在传统的Dropout方式中，使用一个随机的二补码网段除以隐藏单元，便于在每次训练经由网路传输时遗弃一部份期望的神经元。由于每位过程中的网段就会发生变化，所以每一个过程都须要估算相对于不同子模型的梯度。这种子模型可以有不同的大小（结构），具体取决于每层中遗弃多少个神经元。在本文处理中，为了满足节约联邦学习通讯开支的要求，在每位全联接层上都将固定数目的激活归零，这样使所有子模型都具有相同的简化体系结构。如图4所示。
图4.应用于两个全联接层的FederatedDropout。
中央服务器可以将必要的值映射到这个简化的构架中，这意味着只将必要的系数传输到顾客端，重新打包成更小的密集矩阵。顾客端（可能完全不晓得原始模型的构架）训练其子模型并发送其更新，之后中央服务器将其映射回全局模型。对于前馈层来说，将激活归零不会实现任何空间的节省，因而，作者除去了一定比列的检波器。
不仅节约服务器到顾客端的通讯开支外，FederatedDropout还带来了另外两个益处。首先，顾客端到中央服务器更新的规模也降低了。其次，本地训练过程如今只须要运行较少的梯度更新。当前所有的矩阵加法都是较小维度的（相对于全联接层来说），或则是只须要使用较少的混频器（对于前馈层来说）。因而，使用FederatedDropout进一步增加了联邦学习中的本地估算成本。
在实验部份，作者首先分别基于CIFAR-10和EMNIST库验证了压缩处理对本文方式的影响。由图5的实验结果，（1）对于每一个模型，都能找到一组起码与基线方式（nocompression）相抗衡的压缩参数设置；（2）Kashin表征方式对量化处理最为有用；（3）在中央服务器到顾客端的通讯过程中进行下取样处理的疗效并不好。
图5.有损压缩参数对CIFAR-10和EMNIST的影响。
之后，作者通过实验验证FederatedDropout方式对全局模型确切度的影响。图6给出了模型在不同的FederatedDropout率下的收敛情况。在本文模型中，将每层保留的神经元（或频域层的过滤器）的比率定义为FederatedDropout率。将每位实验重复10次，最终报告10次重复实验结果的平均值。由图6，对于每位模型来说都存在大于1.0的FederatedDropout率与基线方式疗效相当。在个别情况下，甚至可以提升模型的最终确切度。据悉，FederatedDropout率为0.75的情况下不同模型都可以获得较好的疗效。这些Dropout率相当于遗弃掉25%的行和全联接层的权重矩阵的列（即，相当于降低了43%），并降低相应比率的混频器。假如FederatedDropout率偏低，常常会减低模型的收敛速率，虽然较高的FederatedDropout率有时可能获得更高的确切度。
图6.FederatedDropout的结果，改变每层保留的神经元比率。
最后，作者进行了实验以验证将两种策略（有损压缩和FederatedDropout）与顾客端到服务器压缩方案（节1.1.1英文献[1]提出的方式）相结合时本文方式的疗效。作者评估了本文模型在3种不同的压缩方案（Aggressive、Moderate和Conservative）和4种不同的FederatedDropout率（0.5、0.625、0.75和0.875）的表现。图7给出了CIFAR-10和EMNIST中的实验结果。重复每位实验5次，最终报告5次重复实验结果的平均值。对于所有三个模型，不仅Aggressive压缩方案外，FederatedDropout率为0.75时在所有压缩方案下都不会导致模型确切度升高。对于MNIST和EMNIST，中央服务器到顾客端的通讯成本节约了14倍，顾客端到中央服务器的通讯成本节约了28倍，本地估算量降低了1.7倍，所有这种通讯开支成本的节省都不会增加最终全局模型的确切性（有时甚至还能否提升确切性）。
图7.压缩和FederatedDropout对CIFAR-10和EMNIST的影响。
1.1.3CountSketch压缩处理[3]
这篇文章中提出的FetchSGD使用CountSketch来压缩模型更新，之后借助Sketches的可合并性来将不同顾客端的模型更新进行合并。FetchSGD设计中的一个关键问题是，因为CountSketch是线性的，动量和偏差累积都可以在CountSketch中进行。这促使该方式才能将动量和偏差累积从顾客端转移到中央服务器中，因而在克服稀疏顾客端参与挑战的同时，确保高压缩率和良好的收敛性。FetchSGD的完整方式见图8：（1）在顾客端本地估算梯度，（2）将梯度的sketches发送到中央服务器中，中央服务器聚合梯度（3）sketches（4）动量和偏差累积（5），（6）提取近似的top-k值，（7）中央服务器将稀疏值更新到参与下一轮训练的顾客端设备中。
图8.FetchSGD完整方式图示。
在FetchSGD的每次迭代中，第i个参与的顾客端使用部份（或全部）本地数据估算随机梯度(g_i)^t，之后使用称为CountSketch的数据结构压缩(g_i)^t。每位顾客端将SketchS((g_i)^t)作为其模型更新发送到聚合器（中央服务器）。CountSketch是一种随机的数据结构，它可以通过将向量多次随机投影到低维空间来压缩向量，便于后续近似地恢复高幅值（High-MagnitudeElements）数据。如下式：
因为CountSketch具备线性特点，中央服务器可以在给定S((g_i)^t)的情况下，估算出每位小批量梯度g^t的sketch：
据悉，CountSketch的另一个有用特点是，对于sketching操作符S()，有一个对应的解压操作符U()返回原始向量的无偏恐怕，进而实现对向量高幅值元素的近似：
相比之下，其他有偏梯度压缩方式在压缩梯度时会给顾客端带来误差，因而顾客端本身必须保持单独的偏差累积向量。这在联邦学习中是很难保证的，这是因为顾客端仅能参与一次更新，这样就没有机会在下一轮中重新引入错误。从另一个角度看，因为S()是线性的，但是偏差累积只包含线性操作，因而在S_e的中央服务器上进行偏差累积相当于在每位顾客端上进行偏差累积，并将结果Sketch上传到中央服务器。更进一步，我们注意到动量也只包含线性操作，因而动量可以等价地在顾客端或中央服务器上执行。推广上述等式可以得到：
完整的FetchSGD估算流程如下：
本文实验主要在大型本地数据集和Non-IID数据上完成，由于作者觉得这是联邦学习中一个重要且相对未解决的问题。精典的梯度稀疏化方式是将每位顾客端的局部top-k梯度元素聚合在一起训练全局模型的，当各个顾客端的本地数据集特别小或互相之间差别十分大时，这些方式在近似全局梯度的真正top-k梯度元素时的表现都会特别差。在这些情况下，与精典方式相比FetchSGD有一个关键的优势：FetchSGD的压缩算子是线性的。在FetchSGD中「只使用具有N个数据的单个顾客端执行一个步骤相当于使用N个顾客端执行一个步骤」，为此，每位顾客端只贡献一次数据，大型顾客端本地数据集不会带来任何问题。独立同分布的问题也可以通过随机选择顾客端得到解决，FetchSGD将参与训练的各个顾客端的数据聚合上去，因而可以得到更完整的数据分布样本。
实验中，作者以上传和下载的总字节数表征相对于未压缩的SGD所实现的压缩疗效。那些数据中没有考虑到的一个重要诱因是，在FedAvg中，顾客端必须在参与之前立刻下载一个完整的模型，由于每位模型的权重在每一轮中就会得到更新。相比之下，局部Top-k和FetchSGD每轮只更新有限数目的参数，因而未参与的顾客端可以相对更新当前模型，进而降低了必须在参与之前立刻下载的新参数的数目。这促使本地Top-k和FetchSGD的上传压缩比下载压缩更重要。下载压缩对于这三种方式（FedAvg、Top-k、FetchSGD）也不这么重要，由于目前边沿设备的互联网联接的下载速率常常远远低于上传速率。作者给出了整体压缩（包括上传和下载）的结果，在图9中把这种图分成单独的上传和下载部份进行展示。FetchSGD在不同的数据集和上传、下载和整体压缩的任务中，表现都较优。
图9.CIFAR10（左）和CIFAR100（右）的上传（底部）、下载（中间）和整体（顶部）压缩疗效比对。为了增强可读性，每位图只显示该图中显示的压缩类型的运行的帕
累托边界。
1.1.4周期平均和量化的压缩处理方式[6]
这篇文章介绍了一种周期平均和量化处理的联邦学习方式（aCommunication-efficientFederatedlearningalgorithmwithPeriodicAveragingandQuantization,FedPAQ）。其中的量化处理也可以看作是一种压缩方法。
在精典联邦学习框架中，为了借助顾客端节点上所有可用的数据样本，参与训练的顾客端在每次训练迭代中通过中央服务器同步其模型，为此，顾客端和中央服务器之间要进行多次通讯，因而引起网路上的通讯争用引起较大通信花销。本文提出的周期平均和量化处理方式令顾客端进行本地更新并定期通过中央服务器进行同步。一旦某顾客端节点从中央服务器中获取到更新的模型，顾客端节点每隔τ次本地SGD就向中央服务器发送更新信息以更新聚合模型。这些周期平均方案减轻了中央服务器和顾客端之间的通讯次数，因而增加了训练模型的总体通讯成本。假如在顾客端中运行T次SGD迭代，则顾客端须要与中央服务器进行K=T/τ轮通讯，因而将总通讯成本增加为原成本的1/τ。这就是「周期平均」的处理思路。
从K=T/τ的估算公式可以直观看出，选择较大的τ值可以降低固定迭代次数T的通讯次数，从而减少通讯成本。并且这些减少是以牺牲模型确切度为代价的。减小τ，会降低系统的噪音，因而顾客端中的局部模型会渐渐收敛到局部最优解，而不是全局最优解。为此，作者考虑运行更多次迭代T来使模型达到特定的确切度。事实上，我们须要解决的一个关键问题是找到最优τ，以使整个过程通讯成本最小化。
在联邦学习网路中，一般有大量的设备（如智能电话）与中央服务器（基站）进行通讯。并且，基站本身的下载带宽有限，因而只有少数设备才能同时将其消息上载到基站。因为这一限制，从顾客端设备发送的消息将在中央服务器基站中进行流水线式的串行传输，这造成训练速率大大减低。另一方面，假如让所有的顾客端设备都参与到整个训练过程中，将会导致巨大的、昂贵的网路通讯开支。据悉，在实际应用中，并不是所有的顾客端都在每一轮训练的过程中发挥作用的。有好多诱因决定顾客端是否参与当前的训练过程：设备需在当前状态下处于中央服务器基站通讯可达的范围内、客户端设备在当前状态下为空闲可用状态、客户端设备通电且联网等等。
考虑到上述诱因，FedPAQ假定，在总共n个顾客端设备中每轮训练中只有r个节点（r≤n）可用，且这r个可用设备在网路上随机且均匀地分布。在第k个训练周期内，中央服务器将其当前模型x_k发送给本轮选取的参与训练的S_k个顾客端子集中的r个顾客端节点，r个顾客端节点在该子集的总共n个顾客端节点之间随机均匀分布。另一方面，联邦学习中的设备上行链路带宽有限，这促使从顾客端到中央服务器的通讯平缓且高昂，这也是后面几节中各类压缩方式所考虑的主要问题。本文所提出的方式是在传输信息中使用量化算子，通过交换量化更新来增加网路通讯花销。
在进行τ轮本地SGD更新后，每位顾客端i∈S_k中拥有本地模型(x_k,τ)^i，其中x_k为最新从中央服务器中获取的全局模型。每位顾客端对x_k和(x_k,τ)^i的差值应用量化算子Q()，并将量化结果Q((x_k,τ)^i-x_k)发送至中央服务器。中央服务器接收到量化结果后进行反量化解码处理，并基于处理结果生成新的全局模型x_k+1。本文使用的量化算子为：
完整的FedPAQ方式如下：
总的来说，FedPAQ通过使用三个模块来减少通讯负载：周期平均、部分顾客端参与和量化处理。但是，这些通讯降低带来了收敛确切度减少的问题，因而须要更多次的训练迭代。作者在原文中还进行了FedPAQ的收敛性剖析，并给出了FedPAQ强凸和非凸损失函数的近似最优理论证明。我们在这儿不再深究。
作者在实验中对比了通讯开支和收敛性的tradeoff的结果剖析。实验以总的训练时间为代价目标，包括通信时间和估算时间。首先，定义网路带宽（Bandwidth，BW），每轮的通信时间为上传的总比特数乘以BW。每轮的总比特数估算为r・|Q(p,s)|，其中|Q(p,s)|表示按照具有s级（slevels）的特定量化算子对p维向量进行量化编码所需的比特数。在本文实验中使用的量化算子中，假设它须要pF位来表示厚度为p的未量化向量，其中F为32位。
之后，借助梯度估算时间的位移指数模型（Shifted-ExponentialModel）确定估算时间。假定对于任何顾客端，估算一个周期内的τ次迭代和批量大小为B的梯度须要确定位移τ・B・scale^(-1)，其中shift和scale分别是位移指数模型的位移和尺度参数，实验中B确定为10。每轮的总估算时间就是r个贡献顾客端节点中最大的本地估算时间。最后，估算通讯-估算比为：
在图10中，前四个图展示了在MNIST数据集（'0'和'8'位）上，T=100次迭代的正则化逻辑回归问题的训练时间。联邦学习网路中共有n=50个顾客端节点，每位节点加载200个样本。设置C_comm/C_comp=100/1来捕获通讯困局。第一列图中曲线显示了在中央服务器上每轮的训练时间与所获得的训练损失之间的关系。第二列图中曲线显示了参与更新的顾客端数目n的影响。第三列论证了周期宽度τ在通讯-估算tradeoff中的作用。最后一列图比较了FedPAQ与其他两个基线方式FedAvg和QSGD的训练时间。后四个图为CIFAR-10数据库中神经网路的实验结果。具体图例与MNIST中结果相同。
图10.训练损失与训练时间：MNIST的Logistic回归剖析（上），CIFAR-10的神经网路结果（下）。
1.2其它处理方式
1.2.1集成方式[4]
针对联邦学习的通讯开支问题，这篇文章提出了借助集成方式（Ensemblemethod）的思路。集成方式是机器学习中的一种通用技术，用于组合多个基本预测因子（Basepredictors）或专家（Experts）来创建一个更精确的模型。作者觉得，联邦学习中的通讯开支问题是由每轮从中央服务器发送到顾客端（下行）和从顾客端发送到中央服务器（上行）的参数数目造成的。在每轮训练过程中，中央服务器将当前模型的迭代状态发送给全部参与的顾客端，直接将集成方式应用于这些联邦学习框架中会因为每轮都须要传递预测值而造成通讯爆燃。本文提出的FedBoost才能在减少通讯成本的同时实现估算加速、收敛保证和隐私保护。这些方式可以通过联邦学习使用顾客端设备上的数据来训练一个本来可能超过顾客端的通讯带宽和储存容量的模型。据悉，FedBoost就能同时增加中央服务器到顾客端（下行）和顾客端到中央服务器（上行）的通讯成本。
集成方式通过联邦学习的框架在中央服务器端只须要学习混和权重，所须要经由顾客端发送给中央服务器的数据量十分小。为此，作者觉得在集成方式中顾客端到中央服务器（上行）的通讯成本可以忽视不计。本文提出了标准（Standard）和任务不可知（Agnostic）的联邦学习集成方式镜像问题是指，以解决中央服务器到顾客端（下行）的通讯困局问题。
首先介绍标准联邦学习集成方式。给定一组预先训练的基本预测因子或假定：H≜{h_1,...,h_q}。在标准集成方式中，将全部的假定都发送给每位参与的顾客端。但是，在实践中，因为中央服务器和顾客端之间的通讯带宽以及顾客端的显存和估算能力的限制，这些处理方法是不可行的。作者提出了一种抽样方式，只将其中一部份假定发送给顾客端。这似乎可以减少通讯复杂度，但同时会带来整体梯度误差的问题以及集成收敛性的不确定性问题。精典的集成方式为：
设C为每轮发送给顾客端的最大基本预测因子数，即C才能表征通讯效率。中央服务器端的目标函数是学习一组针对预先训练的基本恐怕量h_k的系数α：
FedBoost的完整算法流程如下：
在每轮训练中，FedBoost在中央服务器上抽取两个子集：一个预训练假定子集，其中每一个子集以机率γ_k,t抽取得到（用H_t表示）；N个顾客端的随机子集（用S_t表示）。定义以下Bernoulli指标：
其中，L_k(α)为标准联邦学习中域k的经验损失。针对L(α,λ)的优化问题为一个四人博弈问题，找到最小化目标函数和对手的α，同时使用λ最大化目标函数。最终目标是找到给定α_opt的极小极大博弈的均衡，它促使对于混和权重λ_opt的损失最小化。l为凸函数，可以使用通常镜像增长（genericmirrordescent）或其他基于梯度的算法来优化解决这个问题。
作者提出了任务无关的AFLBoost技巧优化上述目标函数。AFLBoost可以看作是FedBoost和针对任务无关损失函数的随机镜像增长算法[7]的结合。AFLBoost的详尽算法流程如下：
作者在实验中证明了FedBoost在不同通讯成本下对密度恐怕（Densityestimation）任务的有效性。具体包括三种方式：（1）无通讯效率处理（无取样）：γ_k,t=1。（2）均匀抽样：γ_k,t=C/q。（3）加权随机抽样：γ_k,t∝α_k,t·C。
作者首先创建了一个p=100的合成数据集，其中每位h_k是单个元素上的点质分布(Point-massdistribution)，初始化每位α_k为1/p，混和权重λ遵守幂律分布(Powerlawdistribution)。实验结果见图11。由图11左，加权抽样的性能优于均匀抽样，两种方式的损失都在逐步回升。由图11中，在通讯预算为64的情况下，不考虑通讯效率均匀抽样和加权抽样的性能与FedBoost相同。据悉，作者还在精典Shakespeare数据集中进行实验。如图11右，加权随机抽样比均匀抽样的表现更好，在这个库中加权抽样的表现甚至优于FedBoost，具有更好的收敛性能。
图11.实验对比图。左：合成数据集的损失曲线比较；中：合成数据集中采样方式的比较；右：Shakespeare联邦学习数据集的损失曲线比较。
1.2.2分布式不动点优化方式[5]
针对联邦学习的通讯开支问题，一些研究人员的解决思路是借助顾客端的本地估算。也就是说，在通讯和模型聚合处理之前，在每位顾客端设备中进行更多的本地估算，进而降低获得全局有意义的解决方案所需的通讯总轮数。在这些思路下，研究人员集中考虑了一些局部梯度增长算法以改进本地估算的疗效。本文就是这些思路的工作之一。并且本文的工作并不局限于通过梯度增长来最小化目标函数，作者引入了估算M个操作算子平均值的不动点的技巧。实际上，大多数迭代方式都属于不动点方式（Fix-Pointmethod），其目的是找寻某个算子的不动点。
为了从不动点方式角度进行剖析，首先介绍精典的分布式不动点优化模型。令分布式系统中共包括M个并行估算节点（顾客端）。每位节点中处理的变量可看作是欧氏空间中的向量。令Τ_i表示欧氏空间的操作算子，平均算子为：
本文方式的核心是找到Τ的不动点，即找到向量x*满足Τ(x*)=x*。可以通过在每位节点重复应用Τ_i，同时进行平均化处理以达到共识来最终获得目标解x*。本文作者考虑镜像问题是指，经过多次迭代后，每位顾客端节点将其变量同步传递到远程中央服务器中。之后中央服务器估算所接收到的向量的平均值并将其广播到所有节点。
本文考虑两种不动点优化策略：第一种策略是对于每位顾客端估算节点，迭代执行若干次某个操作序列（称之为局部步骤，localsteps）。第二种策略是降低通讯步骤的数目，即仅以一定的较低机率到中央服务器中共享信息，但是只在中间过程进行局部估算。
将T定义为欧氏空间中的一个操作算子，令Fix(T)表示T的不动点集合，对于欧氏空间中的每位x和y，假如T满足下式，则称T是χ-Lipschitz连续的：
据悉，假如T是1-Lipschitz连续和χ-收缩的，则称T是非扩张的。假如T是收缩的，则它具有存在且惟一的不动点。对于任意α∈(0,1]，假如对于一些非扩张算子T’，假如存在T=αT’+Id，则称T是α平均的。假如T是1/2平均的，则称T是坚决不扩张的。
令(t_n)_n∈N表示通讯过程中的整数序列。在每次迭代过程中，操作算子Τ_i应用于节点i，并借助参数λ进行松驰。对于一定数目的迭代，M个估算节点全部将其本地向量传输给中央服务器的主节点，主节点估算平均值并将平均值广播给全部节点。全部节点在新的一轮迭代开始时拥有相同的变量(x^)^k。该算法是局部梯度增长法（FederatedAveraging）的推广。
我们把一系列本地迭代称为一个epoch，之后求取平均值。也就是说，第n个epoch是指数k+1=t_(n-1)+1,...,t_n的迭代序列。假定在两个聚合估算平均值步骤之间的每位epoch的迭代次数由某个整数H限定。则对于每位n≥1，有1≤t_n-t_(n-1)≤H。具体，第一种策略的详尽算法流程如下：
接出来，作者提出了第二种策略。第一种策略中的本地处理步骤可以看作是两个通讯步骤之间的二环（InnerLoop），将二环用机率聚合（ProbabilisticAggregation）来取代，即可得到第二种策略。在以下意义上，它是通讯-有效的：在第一种策略中，通讯轮数乘以H（或是非均匀情况下t_n-t_(n-1)的平均值），而在第二种策略中该值减去机率p≤1。第二种策略的详尽算法流程如下：
在原文中，作者对两种策略算法的收敛性能进行了充分的论证，我们在这儿不再深究。
作者选择精典分类问题的逻辑回归进行实验。相应的目标函数如下：
其中，a_i∈R^d，b_i∈{-1,+1}为数据样本。使用LIBSVM库中的「a9a」和「a4a」数据集，并将k设为L/n，其中n是数据集的大小，L是ᐁf第一部份的Lipschitz常数，且没有经过正则化处理。
本文实验高考虑梯度增长（GradientDescent，GD）作为操作算子。也就是说，我们考虑最小化有限和问题：
使用第一种策略的算法1和使用第二种策略的算法2的实验结果见图12和图13。参数H和λ的值越大，初始收敛速率越快，但邻域直径越大。就估算时间而言，该算法没有太大的优势，由于实验是在一台机器上进行的，通讯时间可以忽视不计。并且在通讯速率较慢的分布式环境中，本文的算法就有显著的优势。我们也可以观察到图中实验结果曲线没有出现振荡。因而，当只须要达到有限的确切度时，本文提出的本地方式具有显著的优势。
图12.具有梯度增长步长的算法1在均匀通讯时间t_n=nH下的收敛性，（a）不同H值的通信轮数，λ=0.5，（b）不同H值的估算时间，λ=0.5，（c）不同λ值的估算时间，H=4。
图13.梯度增长步长算法2的收敛性，λ=0.5，（a）梯度步长相怜悯况下，不同p值的通信轮次数目，（b）梯度步长相怜悯况下，不同p值的估算时间，（c）梯度步长与p是成比列的，不同p值的通信轮次数目。
2.总结
我们在这篇文章重点关注了联邦学习框架中的通讯开支研究进展。目前，大多数文章都从压缩的角度出发解决通讯开支问题，这些方式的思路很直观：压缩后须要上行、下行传递的数据量都会降低，进而减少通讯花销。其实，压缩的方式有好多，比如有损压缩、提取sketch、量化等等。据悉，我们也剖析了两篇非压缩思路的文章，作者分别使用了集成方式和强化本地估算的方式。在不同的文章中，作者对比和剖析的实验指标各不相同，这说明目前还没有标准化、统一化、权威性的评判联邦学习通讯开支的指标，虽然通讯开支和估算效率是一对tradeoff的指标。单纯用通讯时间或通讯数据量去评判方式的好坏并不客观。
目前，随着5G技术的发展，5G网路中通讯速度问题显得不再是问题。依托5G，使用边沿设备的应用场景也越来越多，比如校园安全监控、明厨亮灶监控、移动执法等等。在这些情况下，是否还能减轻联邦学习中的通讯开支问题，从而促使联邦学习更快的发展和应用？让我们拭目以待吧！
参考文献
[1]JakubKoneˇcný,HBrendanMcMahan,FelixXYu,PeterRichtárik,AnandaTheerthaSuresh,andDaveBacon。Federatedlearning:Strategiesforimprovingcommunicationefficiency。arXivpreprintarXiv:1610。05492,2016b。[2]Caldas,S。,Koneˇcny,J。,McMahan,H。B。,andTalwalkar,A。Expandingthereachoffederatedlearningbyreducingclientresourcerequirements。arXivpreprintarXiv:1812。07210,2018。[3]Rothchild,D。,Panda,A。,Ullah,E。,Ivkin,N。,Stoica,I。,&Braverman,V。,etal。(2020)。
FetchSGD:communication-efficientfederatedlearningwithsketching,ICML2020,[4]JennyHamer,MehryarMohri,AnandaTheerthaSuresh,FedBoost:ACommunication-EfficientAlgorithmforFederatedLearning,ICML2020。[5]Malinovsky,G。,Kovalev,D。,Gasanov,E。,Condat,L。,&Richtarik,P。。(2020)。Fromlocalsgdtolocalfixedpointmethodsforfederatedlearning,ICML2020,[6]ReisizadehA,MokhtariA,HassaniH,etal。FedPAQ:ACommunication-EfficientFederatedLearningMethodwithPeriodicAveragingandQuantization[J]。arXiv,2019。[7]Mohri,M。,Sivek,G。,andSuresh,A。T。Agnosticfederatedlearning。InInternationalConferenceonMachineLearning,pp。4615–4625,2019。
