尽管计算高昂和沟通成本，牛顿型方法仍然是分布式培训的吸引人选择，因为它们对不良条件的凸问题进行了稳健性。在这项工作中，我们研究了通信压缩和曲率信息的聚合机制，以降低这些成本，同时保留理论上优越的局部收敛保证。我们证明了Richtarik等人最近开发的三点压缩机（3PC）类。 [2022]对于梯度交流也可以推广到Hessian通信。该结果开辟了各种各样的沟通策略，例如承包压缩}和懒惰的聚合，可用于压缩过高的成本曲率信息。此外，我们发现了几种新的3PC机制，例如自适应阈值和Bernoulli聚集，这些机制需要减少通信和偶尔的Hessian计算。此外，我们扩展和分析了双向通信压缩和部分设备参与设置的方法，以迎合联合学习中应用的实际考虑。对于我们的所有方法，我们得出了与局部无关的局部线性和/或超线性收敛速率。最后，通过对凸优化问题进行广泛的数值评估，我们说明我们的设计方案与使用二阶信息相比，与几个关键基线相比，我们的设计方案达到了最新的通信复杂性。

分布式优化的最新进展表明，与适当的通信压缩机制的牛顿型方法可以保证与第一订单方法相比的局部速率和低通信成本。我们发现这些方法的通信成本可以进一步减少，有时会急剧下降，有一个令人惊讶的简单技巧：{\ EM基础学习（BL）}。这些想法是通过在矩阵空间中的变化和将压缩工具应用于新的表示来改变当地黑森州的通常代表。为了展示使用自定义基础的潜力，我们设计了一种新的牛顿型方法（BL1），其通过{\ em bl}技术和双向压缩机制来降低通信成本。此外，我们向部分参与提供两个替代扩展（BL2和BL3）以适应联合学习应用。我们证明了局部线性和超连线率无关，无关。最后，我们通过比较多种第一和第二〜订单方法来支持我们的索赔。

牛顿型方法由于其快速收敛而在联合学习中很受欢迎。尽管如此，由于要求将Hessian信息从客户发送到参数服务器（PS），因此他们遭受了两个主要问题：沟通效率低下和较低的隐私性。在这项工作中，我们介绍了一个名为Fednew的新颖框架，其中无需将Hessian信息从客户传输到PS，因此解决了瓶颈以提高沟通效率。此外，与现有的最新技术相比，Fednew隐藏了梯度信息，并导致具有隐私的方法。 Fednew中的核心小说想法是引入两个级别的框架，并在仅使用一种交替的乘数方法（ADMM）步骤更新逆Hessian级别产品之间，然后使用Newton的方法执行全局模型更新。尽管在每次迭代中只使用一个ADMM通行证来近似逆Hessian梯度产品，但我们开发了一种新型的理论方法来显示Fednew在凸问题上的融合行为。此外，通过利用随机量化，可以显着减少通信开销。使用真实数据集的数值结果显示了与现有方法相比，在通信成本方面，Fednew的优越性。

沟通是大规模机器学习模型的分布式培训中的关键瓶颈之一，而交换信息（例如随机梯度或模型）的有损压缩是减轻此问题的最有效工具之一。研究最多的压缩技术之一是无偏压缩操作员的类别，其方差为我们希望压缩的向量的平方规范的倍数界定。根据设计，该方差可能保持较高，并且只有在输入向量接近零时才会减少。但是，除非被训练的模型过度参数化，否则我们希望在经典方法的迭代（例如分布式压缩{\ sf sgd}的迭代术中，我们希望压缩的矢量有A的理由，对收敛产生不利影响速度。由于这个问题，最近提出了一些更详尽且看似截然不同的算法，目的是规避了这个问题。这些方法基于在我们通常希望压缩的向量和一些辅助向量之间压缩{\ em差异}的想法，这些辅助向量会在整个迭代过程中变化。在这项工作中，我们退后一步，并在概念上和理论上开发了研究此类方法的统一框架。我们的框架结合了使用无偏和有偏的压缩机压缩梯度和模型的方法，并阐明了辅助向量的构造。此外，我们的一般框架可以改善几种现有算法，并可以产生新的算法。最后，我们进行了几个数字实验，以说明和支持我们的理论发现。

梯度压缩是一种流行的技术，可改善机器学习模型分布式培训中随机一阶方法的沟通复杂性。但是，现有作品仅考虑随机梯度的替换采样。相比之下，在实践中众所周知，最近从理论上证实，基于没有替代抽样的随机方法，例如随机改组方法（RR）方法，其性能要比用更换梯度进行梯度的方法更好。在这项工作中，我们在文献中缩小了这一差距，并通过梯度压缩和没有替代抽样的方法提供了第一次分析方法。我们首先使用梯度压缩（Q-RR）开发一个随机重新填充的分布式变体，并展示如何通过使用控制迭代来减少梯度量化的方差。接下来，为了更好地适合联合学习应用程序，我们结合了本地计算，并提出了一种称为Q-Nastya的Q-RR的变体。 Q-Nastya使用本地梯度步骤以及不同的本地和全球步骤。接下来，我们还展示了如何在此设置中减少压缩差异。最后，我们证明了所提出的方法的收敛结果，并概述了它们在现有算法上改进的几种设置。

在过去的几年中，各种通信压缩技术已经出现为一个不可或缺的工具，有助于缓解分布式学习中的通信瓶颈。然而，尽管{\ em偏见}压缩机经常在实践中显示出卓越的性能，但与更多的研究和理解的{\ EM无偏见}压缩机相比，非常少见。在这项工作中，我们研究了三类偏置压缩操作员，其中两个是新的，并且它们在施加到（随机）梯度下降和分布（随机）梯度下降时的性能。我们首次展示偏置压缩机可以在单个节点和分布式设置中导致线性收敛速率。我们证明了具有错误反馈机制的分布式压缩SGD方法，享受ergodic速率$ \ mathcal {o} \ left（\ delta l \ exp [ - \ frac {\ mu k} {\ delta l}] + \ frac {（c + \ delta d）} {k \ mu} \右）$，其中$ \ delta \ ge1 $是一个压缩参数，它在应用更多压缩时增长，$ l $和$ \ mu $是平滑性和强凸常数，$ C $捕获随机渐变噪声（如果在每个节点上计算完整渐变，则$ C = 0 $如果在每个节点上计算），则$ D $以最佳（$ d = 0 $ for over参数化模型）捕获渐变的方差）。此外，通过对若干合成和经验的通信梯度分布的理论研究，我们阐明了为什么和通过多少偏置压缩机优于其无偏的变体。最后，我们提出了几种具有有希望理论担保和实际表现的新型偏置压缩机。

我们开发了一种新方法来解决中央服务器中分布式学习问题中的通信约束。我们提出和分析了一种执行双向压缩的新算法，并仅使用uplink（从本地工人到中央服务器）压缩达到与算法相同的收敛速率。为了获得此改进，我们设计了MCM，一种算法，使下行链路压缩仅影响本地模型，而整体模型则保留。结果，与以前的工作相反，本地服务器上的梯度是在干扰模型上计算的。因此，融合证明更具挑战性，需要精确控制这种扰动。为了确保它，MCM还将模型压缩与存储机制相结合。该分析打开了新的门，例如纳入依赖工人的随机模型和部分参与。

在这项工作中，我们提出了FedSSO，这是一种用于联合学习的服务器端二阶优化方法（FL）。与以前朝这个方向的工作相反，我们在准牛顿方法中采用了服务器端近似，而无需客户的任何培训数据。通过这种方式，我们不仅将计算负担从客户端转移到服务器，而且还消除了客户和服务器之间二阶更新的附加通信。我们为我们的新方法的收敛提供了理论保证，并从经验上证明了我们在凸面和非凸面设置中的快速收敛和沟通节省。

我们介绍了一个框架 - Artemis-，以解决分布式或联合设置中的学习问题，并具有通信约束和设备部分参与。几位工人（随机抽样）使用中央服务器执行优化过程来汇总其计算。为了减轻通信成本，Artemis允许在两个方向上（从工人到服务器，相反）将发送的信息与内存机制相结合。它改进了仅考虑单向压缩（对服务器）的现有算法，或在压缩操作员上使用非常强大的假设，并且通常不考虑设备的部分参与。我们在非I.I.D中的随机梯度（仅在最佳点界定的噪声方差）提供了快速的收敛速率（线性最高到阈值）。设置，突出显示内存对单向和双向压缩的影响，分析Polyak-Ruppert平均。我们在分布中使用收敛性，以获得渐近方差的下限，该方差突出了实际的压缩极限。我们提出了两种方法，以解决设备部分参与的具有挑战性的案例，并提供实验结果以证明我们的分析有效性。

我们研究基于{\ em本地培训（LT）}范式的分布式优化方法：通过在参数平均之前对客户进行基于本地梯度的培训来实现沟通效率。回顾田地的进度，我们{\ em识别5代LT方法}：1）启发式，2）均匀，3）sublinear，4）线性和5）加速。由Mishchenko，Malinovsky，Stich和Richt \'{A} Rik（2022）发起的5 $ {}^{\ rm th} $生成，由Proxskip方法发起通信加速机制。受到最近进度的启发，我们通过证明可以使用{\ em差异}进一步增强它们，为5 $ {}^{\ rm th} $生成LT方法的生成。尽管LT方法的所有以前的所有理论结果都完全忽略了本地工作的成本，并且仅根据交流回合的数量而被构成，但我们证明我们的方法在{\ em总培训成本方面都比{\ em em总培训成本}大得多当本地计算足够昂贵时，在制度中的理论和实践中，最先进的方法是proxskip。我们从理论上表征了这个阈值，并通过经验结果证实了我们的理论预测。

从经验上证明，在跨客户聚集之前应用多个本地更新的实践是克服联合学习（FL）中的通信瓶颈的成功方法。在这项工作中，我们提出了一种通用食谱，即FedShuffle，可以更好地利用FL中的本地更新，尤其是在异质性方面。与许多先前的作品不同，FedShuffle在每个设备的更新数量上没有任何统一性。我们的FedShuffle食谱包括四种简单的功能成分：1）数据的本地改组，2）调整本地学习率，3）更新加权，4）减少动量方差（Cutkosky and Orabona，2019年）。我们对FedShuffle进行了全面的理论分析，并表明从理论和经验上讲，我们的方法都不遭受FL方法中存在的目标功能不匹配的障碍，这些方法假设在异质FL设置中，例如FedAvg（McMahan等人，McMahan等， 2017）。此外，通过将上面的成分结合起来，FedShuffle在Fednova上改善（Wang等，2020），以前提议解决此不匹配。我们还表明，在Hessian相似性假设下，通过降低动量方差的FedShuffle可以改善非本地方法。最后，通过对合成和现实世界数据集的实验，我们说明了FedShuffle中使用的四种成分中的每种如何有助于改善FL中局部更新的使用。

与训练数据中心的训练传统机器学习（ML）模型相反，联合学习（FL）训练ML模型，这些模型在资源受限的异质边缘设备上包含的本地数据集上。现有的FL算法旨在为所有参与的设备学习一个单一的全球模型，这对于所有参与培训的设备可能没有帮助，这是由于整个设备的数据的异质性。最近，Hanzely和Richt \'{A} Rik（2020）提出了一种新的配方，以培训个性化的FL模型，旨在平衡传统的全球模型与本地模型之间的权衡，该模型可以使用其私人数据对单个设备进行培训只要。他们得出了一种称为无环梯度下降（L2GD）的新算法，以解决该算法，并表明该算法会在需要更多个性化的情况下，可以改善沟通复杂性。在本文中，我们为其L2GD算法配备了双向压缩机制，以进一步减少本地设备和服务器之间的通信瓶颈。与FL设置中使用的其他基于压缩的算法不同，我们的压缩L2GD算法在概率通信协议上运行，在概率通信协议中，通信不会按固定的时间表进行。此外，我们的压缩L2GD算法在没有压缩的情况下保持与香草SGD相似的收敛速率。为了验证算法的效率，我们在凸和非凸问题上都进行了多种数值实验，并使用各种压缩技术。

Federated Averaging (FEDAVG) has emerged as the algorithm of choice for federated learning due to its simplicity and low communication cost. However, in spite of recent research efforts, its performance is not fully understood. We obtain tight convergence rates for FEDAVG and prove that it suffers from 'client-drift' when the data is heterogeneous (non-iid), resulting in unstable and slow convergence.As a solution, we propose a new algorithm (SCAFFOLD) which uses control variates (variance reduction) to correct for the 'client-drift' in its local updates. We prove that SCAFFOLD requires significantly fewer communication rounds and is not affected by data heterogeneity or client sampling. Further, we show that (for quadratics) SCAFFOLD can take advantage of similarity in the client's data yielding even faster convergence. The latter is the first result to quantify the usefulness of local-steps in distributed optimization.

Federated learning is a distributed framework according to which a model is trained over a set of devices, while keeping data localized. This framework faces several systemsoriented challenges which include (i) communication bottleneck since a large number of devices upload their local updates to a parameter server, and (ii) scalability as the federated network consists of millions of devices. Due to these systems challenges as well as issues related to statistical heterogeneity of data and privacy concerns, designing a provably efficient federated learning method is of significant importance yet it remains challenging. In this paper, we present FedPAQ, a communication-efficient Federated Learning method with Periodic Averaging and Quantization. FedPAQ relies on three key features: (1) periodic averaging where models are updated locally at devices and only periodically averaged at the server; (2) partial device participation where only a fraction of devices participate in each round of the training; and (3) quantized messagepassing where the edge nodes quantize their updates before uploading to the parameter server. These features address the communications and scalability challenges in federated learning. We also show that FedPAQ achieves near-optimal theoretical guarantees for strongly convex and non-convex loss functions and empirically demonstrate the communication-computation tradeoff provided by our method.

非凸优化的马鞍点避免问题在大规模分布式学习框架中非常具有挑战性，例如联邦学习，特别是在拜占庭工作者的存在。 「庆祝的立方规范化牛顿方法\ Cite {Nest}是避免标准集中（非分布式）设置中的马鞍点的最优雅方式之一。在本文中，我们将立方正规化的牛顿方法扩展到分布式框架，同时解决了几种实际挑战，如通信瓶颈和拜占庭攻击。请注意，由于流氓机器可以在丢失功能的鞍点附近创建\ emph {假本地最小值}，因此在丢失函数的鞍点附近，尚未创建拜占机器的存在，避免问题在拜占庭机器的情况下变得更加重要。作为二阶算法，我们的迭代复杂性远低于第一订单对应物。此外，我们使用像$ \ delta $类似的压缩（或稀疏）技术，以便进行通信效率。我们在包括近似（子采样）梯度和黑森州的若干环境下获得理论担保。此外，我们通过使用标准数据集和几种类型的拜占庭攻击进行实验验证了我们的理论调查结果，并在迭代复杂性中获得了25 \％$ 25 \％$的提高。

We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic estimate of the Hessian matrix. The oracle model includes popular algorithms such as Subsampled Newton and Newton Sketch. Despite using second-order information, these existing methods do not exhibit superlinear convergence, unless the stochastic noise is gradually reduced to zero during the iteration, which would lead to a computational blow-up in the per-iteration cost. We propose to address this limitation with Hessian averaging: instead of using the most recent Hessian estimate, our algorithm maintains an average of all the past estimates. This reduces the stochastic noise while avoiding the computational blow-up. We show that this scheme exhibits local $Q$-superlinear convergence with a non-asymptotic rate of $(\Upsilon\sqrt{\log (t)/t}\,)^{t}$, where $\Upsilon$ is proportional to the level of stochastic noise in the Hessian oracle. A potential drawback of this (uniform averaging) approach is that the averaged estimates contain Hessian information from the global phase of the method, i.e., before the iterates converge to a local neighborhood. This leads to a distortion that may substantially delay the superlinear convergence until long after the local neighborhood is reached. To address this drawback, we study a number of weighted averaging schemes that assign larger weights to recent Hessians, so that the superlinear convergence arises sooner, albeit with a slightly slower rate. Remarkably, we show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage, and still exhibits a superlinear convergence rate nearly (up to a logarithmic factor) matching that of uniform Hessian averaging.

我们开发和分析码头：在异构数据集中的非凸分布式学习的新通信高效方法。 Marina采用了一种基于渐变差异的新颖沟通压缩策略，这些差异让人想起，但与Mishchenko等人的Diana方法中所采用的策略不同。 （2019）。与几乎所有竞争对手的分布式一阶方法不同，包括Diana，我们的基于精心设计的偏置渐变估计，这是其卓越理论和实践性能的关键。我们向码头证明的通信复杂性界限明显比以前所有的一阶方法的方式更好。此外，我们开发和分析码头的两种变体：VR-Marina和PP-Marina。当客户所拥有的本地丢失功能是有限和期望形式的局部丢失功能时，第一种方法设计了第一种方法，并且第二种方法允许客户端的部分参与 - 在联合学习中重要的功能。我们所有的方法都优于前面的oracle /通信复杂性的最先进的方法。最后，我们提供了满足Polyak-Lojasiewicz条件的所有方法的收敛分析。

由于分布式和联合学习的高通信成本，依赖压缩通信的方法变得越来越受欢迎。此外，最好的理论上和实际上表演梯度类型方法总是依赖某种形式的加速/动量来减少通信数量（更快的收敛）（更快的收敛），例如，Nesterov的加速梯度下降（Nesterov，1983,2004）和Adam（Kingma和Kingma） BA，2014）。为了结合通信压缩和收敛加速的好处，我们提出了基于Anita（Li，2021）的Anita {压缩和加速}梯度方法进行分布式优化，我们称之为CANITA。我们的Canita实现了\ emph {First加速率} $ o \ bigg（\ sqrt {\ big（1+ \ sqrt {\ frac {\ oomega ^ 3} {n}} \ big）\ frac {l} {\ epsilon }} + \ oomega \ big（\ frac {1} {\ epsilon} \ big）^ {\ frac {1} {3}} {3}} \ bigg）$，从而提高了最先进的非加速RAY $ o \ left（（1+ \ frac {\ oomega} {n}）\ frac {l} {\ epsilon} + \ frac {\ oomega ^ 2 + \ oomega} {\ omega + n} \ frac {1 } {\ epsilon} \右）美元（khaled等，2020）用于分布式一般凸面问题，其中$ \ epsilon $是目标错误，$ l $是目标的平滑参数，$ n $机器/设备的数量和$ \ omega $是压缩参数（较大的$ \ omega $意味着可以应用更多压缩，并且没有压缩意味着$ \ omega = 0 $）。我们的结果表明，只要设备数量为$ n $很大（在分布式/联合学习中经常是真实的），或者压缩$ \ omega $不是很高，Canita达到了更快的收敛速度$ o \ big（\ sqrt {\ frac {l} {\ epsilon}} \ big）$，即通信轮的数量是$ o \ big（\ sqrt {\ frac {l} {\ epsilon}} \ big）$（与$ o \ big（\ frac {l} {\ epsilon} \ big）通过以前的作品实现）。因此，天堂岛享有压缩（每轮压缩通信）和加速度（较少的通信轮）的优点。

由于培训数据集的大小爆炸，分布式学习近年来受到了日益增长的兴趣。其中一个主要瓶颈是中央服务器和本地工人之间的沟通成本。虽然已经证明错误反馈压缩以通过随机梯度下降（SGD）降低通信成本，但在培训大规模机器学习方面广泛用于培训的通信有效的适应性梯度方法楷模。在本文中，我们提出了一种新的通信 - 压缩AMSGRAD，用于分布式非透明的优化问题，可提供有效的效率。我们所提出的分布式学习框架具有有效的渐变压缩策略和工人侧模型更新设计。我们证明所提出的通信有效的分布式自适应梯度方法会聚到具有与随机非凸化优化设置中的未压缩的vanilla amsgrad相同的迭代复杂度的一阶静止点。关于各种基准备份我们理论的实验。

对以联邦学习（FL）的名义进行的分布式优化框架越来越感兴趣。特别是，在通信资源（例如，带宽）和数据分布方面，网络非常异质的情况下，网络是强烈的。在这些情况下，本地机器（代理）和中央服务器（主）之间的通信是主要考虑因素。在这项工作中，我们提出了棚屋，这是一种原始的通信限制在这种异质场景中旨在加速FL的牛顿型（NT）算法。棚子是通过设计强大到非i.i.d.数据分布，处理代理通信资源的异质性（CRS），仅需要零星的Hessian计算，并实现超级线性收敛。这是可能的，这是基于当地Hessian矩阵的特征分配的增量策略，该矩阵（可能）（可能）过时的二阶信息。通过评估（i）收敛所需的通信回合的数量，（ii）传输的数据总量以及（iii）本地Hessian计算的数量，可以在实际数据集上进行彻底验证所提出的解决方案。对于所有这些指标，提出的方法显示出对巨人和FedNL等最新技术的卓越性能。