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

联合学习（FL）是机器学习的一个子领域，在该子机学习中，多个客户试图在通信约束下通过网络进行协作学习模型。我们考虑在二阶功能相似性条件和强凸度下联合优化的有限和联合优化，并提出了两种新算法：SVRP和催化的SVRP。这种二阶相似性条件最近越来越流行，并且在包括分布式统计学习和差异性经验风险最小化在内的许多应用中得到满足。第一种算法SVRP结合了近似随机点评估，客户采样和降低方差。我们表明，当功能相似性足够高时，SVRP是沟通有效的，并且在许多现有算法上取得了卓越的性能。我们的第二个算法，催化的SVRP，是SVRP的催化剂加速变体，在二阶相似性和强凸度下，现有的联合优化算法可实现更好的性能，并均匀地改善了现有的算法。在分析这些算法的过程中，我们提供了可能具有独立关注的随机近端方法（SPPM）的新分析。我们对SPPM的分析很简单，允许进行近似近端评估，不需要任何平滑度假设，并且在通信复杂性上比普通分布式随机梯度下降显示出明显的好处。

联邦学习（FL）是一种越来越受欢迎的机器学习范式，其中多个节点在隐私，通信和多个异质性约束下尝试协同学习。联邦学习中的持续存在问题是，不清楚优化目标应该：监督学习的标准平均风险最小化在处理联合学习的几个主要限制方面是不充分的，例如沟通适应性和个性化控制。我们在联合学习的框架中识别几个关键的Desiderata，并介绍了一个新的框架，Flix，考虑到联合学习所带来的独特挑战。 Flix具有标准的有限和形式，使从业者能够利用分布式优化的现有（潜在非本地）方法的巨大财富。通过不需要任何通信的智能初始化，Flix不需要使用本地步骤，但仍然可以通过本地方法执行不一致的正则化。我们提供了几种用于在通信约束下有效解决FLIX制剂的算法。最后，我们通过广泛的实验证实了我们的理论结果。

我们研究基于{\ 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。我们从理论上表征了这个阈值，并通过经验结果证实了我们的理论预测。

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

从经验上证明，在跨客户聚集之前应用多个本地更新的实践是克服联合学习（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中局部更新的使用。

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

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

我们考虑了分布式随机优化问题，其中$ n $代理想要最大程度地减少代理本地函数总和给出的全局函数，并专注于当代理的局部函数在非i.i.i.d上定义时，专注于异质设置。数据集。我们研究本地SGD方法，在该方法中，代理执行许多局部随机梯度步骤，并偶尔与中央节点进行通信以改善其本地优化任务。我们分析了本地步骤对局部SGD的收敛速率和通信复杂性的影响。特别是，我们允许在$ i $ th的通信回合（$ h_i $）期间允许在所有通信回合中进行固定数量的本地步骤。我们的主要贡献是将本地SGD的收敛速率表征为$ \ {h_i \} _ {i = 1}^r $在强烈凸，convex和nonconvex local函数下的函数，其中$ r $是沟通总数。基于此特征，我们在序列$ \ {h_i \} _ {i = 1}^r $上提供足够的条件，使得本地SGD可以相对于工人数量实现线性加速。此外，我们提出了一种新的沟通策略，将本地步骤提高，优于现有的沟通策略，以突出局部功能。另一方面，对于凸和非凸局局功能，我们认为固定的本地步骤是本地SGD的最佳通信策略，并恢复了最新的收敛速率结果。最后，我们通过广泛的数值实验证明我们的理论结果是合理的。

众所周知，客户师沟通可能是联邦学习中的主要瓶颈。在这项工作中，我们通过一种新颖的客户端采样方案解决了这个问题，我们将允许的客户数量限制为将其更新传达给主节点的数量。在每个通信回合中，所有参与的客户都会计算他们的更新，但只有具有“重要”更新的客户可以与主人通信。我们表明，可以仅使用更新的规范来衡量重要性，并提供一个公式以最佳客户参与。此公式将所有客户参与的完整更新与我们有限的更新（参与客户数量受到限制）之间的距离最小化。此外，我们提供了一种简单的算法，该算法近似于客户参与的最佳公式，该公式仅需要安全的聚合，因此不会损害客户的隐私。我们在理论上和经验上都表明，对于分布式SGD（DSGD）和联合平均（FedAvg），我们的方法的性能可以接近完全参与，并且优于基线，在参与客户均匀地采样的基线。此外，我们的方法与现有的减少通信开销（例如本地方法和通信压缩方法）的现有方法兼容。

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.

由于分布式和联合学习的高通信成本，依赖压缩通信的方法变得越来越受欢迎。此外，最好的理论上和实际上表演梯度类型方法总是依赖某种形式的加速/动量来减少通信数量（更快的收敛）（更快的收敛），例如，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）通过以前的作品实现）。因此，天堂岛享有压缩（每轮压缩通信）和加速度（较少的通信轮）的优点。

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

我们研究了在$ n $工人上的分布式培训的异步随机梯度下降算法，随着时间的推移，计算和通信频率变化。在此算法中，工人按照自己的步调并行计算随机梯度，并在没有任何同步的情况下将其返回服务器。该算法的现有收敛速率对于非凸平的光滑目标取决于最大梯度延迟$ \ tau _ {\ max} $，并表明$ \ epsilon $ stationary点在$ \ mathcal {o} \！\左后达到（\ sigma^2 \ epsilon^{ - 2}+ \ tau _ {\ max} \ epsilon^{ - 1} \ right）$ iterations，其中$ \ sigma $表示随机梯度的方差。在这项工作（i）中，我们获得了$ \ Mathcal {o} \！\ left（\ sigma^2 \ epsilon^{ - 2}+ sqrt {\ tau _ {\ max} \ max} \ tau_ {avg} {avg} } \ epsilon^{ - 1} \ right）$，没有任何更改的算法，其中$ \ tau_ {avg} $是平均延迟，可以大大小于$ \ tau _ {\ max} $。我们还提供（ii）一个简单的延迟自适应学习率方案，在该方案下，异步SGD的收敛速率为$ \ Mathcal {o} \！\ left（\ sigma^2 \ epsilon^{ - 2} { - 2}+ \ tau_ {-2 avg} \ epsilon^{ - 1} \ right）$，并且不需要任何额外的高参数调整或额外的通信。我们的结果首次显示异步SGD总是比迷你批次SGD快。此外，（iii）我们考虑了由联邦学习应用激发的异质功能的情况，并通过证明与先前的作品相比对最大延迟的依赖性较弱，并提高收敛率。特别是，我们表明，收敛率的异质性项仅受每个工人内平均延迟的影响。

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.

数据异构联合学习（FL）系统遭受了两个重要的收敛误差来源：1）客户漂移错误是由于在客户端执行多个局部优化步骤而引起的，以及2）部分客户参与错误，这是一个事实，仅一小部分子集边缘客户参加每轮培训。我们发现其中，只有前者在文献中受到了极大的关注。为了解决这个问题，我们提出了FedVarp，这是在服务器上应用的一种新颖的差异算法，它消除了由于部分客户参与而导致的错误。为此，服务器只是将每个客户端的最新更新保持在内存中，并将其用作每回合中非参与客户的替代更新。此外，为了减轻服务器上的内存需求，我们提出了一种新颖的基于聚类的方差降低算法clusterfedvarp。与以前提出的方法不同，FedVarp和ClusterFedVarp均不需要在客户端上进行其他计算或其他优化参数的通信。通过广泛的实验，我们表明FedVarp优于最先进的方法，而ClusterFedVarp实现了与FedVarp相当的性能，并且记忆要求较少。

为了在带宽洪泛环境（例如无线网络）中启用大规模的机器学习，最近在设计借助通信压缩的帮助下，最近在设计沟通效率的联合学习算法方面取得了重大进展。另一方面，隐私保护，尤其是在客户层面上，是另一个重要的避税，在存在高级通信压缩技术的情况下尚未同时解决。在本文中，我们提出了一个统一的框架，以通过沟通压缩提高私人联邦学习的沟通效率。利用通用压缩操作员和局部差异隐私，我们首先检查了一种简单的算法，该算法将压缩直接应用于差异私密的随机梯度下降，并确定其局限性。然后，我们为私人联合学习提出了一个统一的框架Soteriafl，该框架适应了一般的局部梯度估计剂家庭，包括流行的随机方差减少梯度方法和最先进的变化压缩方案。我们在隐私，公用事业和沟通复杂性方面提供了其性能权衡的全面表征，在这种情况下，Soterafl被证明可以在不牺牲隐私或实用性的情况下实现更好的沟通复杂性，而不是其他私人联合联盟学习算法而没有沟通压缩。

The celebrated FedAvg algorithm of McMahan et al. (2017) is based on three components: client sampling (CS), data sampling (DS) and local training (LT). While the first two are reasonably well understood, the third component, whose role is to reduce the number of communication rounds needed to train the model, resisted all attempts at a satisfactory theoretical explanation. Malinovsky et al. (2022) identified four distinct generations of LT methods based on the quality of the provided theoretical communication complexity guarantees. Despite a lot of progress in this area, none of the existing works were able to show that it is theoretically better to employ multiple local gradient-type steps (i.e., to engage in LT) than to rely on a single local gradient-type step only in the important heterogeneous data regime. In a recent breakthrough embodied in their ProxSkip method and its theoretical analysis, Mishchenko et al. (2022) showed that LT indeed leads to provable communication acceleration for arbitrarily heterogeneous data, thus jump-starting the $5^{\rm th}$ generation of LT methods. However, while these latest generation LT methods are compatible with DS, none of them support CS. We resolve this open problem in the affirmative. In order to do so, we had to base our algorithmic development on new algorithmic and theoretical foundations.

在过去的几年中，各种通信压缩技术已经出现为一个不可或缺的工具，有助于缓解分布式学习中的通信瓶颈。然而，尽管{\ 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参数化模型）捕获渐变的方差）。此外，通过对若干合成和经验的通信梯度分布的理论研究，我们阐明了为什么和通过多少偏置压缩机优于其无偏的变体。最后，我们提出了几种具有有希望理论担保和实际表现的新型偏置压缩机。

In federated optimization, heterogeneity in the clients' local datasets and computation speeds results in large variations in the number of local updates performed by each client in each communication round. Naive weighted aggregation of such models causes objective inconsistency, that is, the global model converges to a stationary point of a mismatched objective function which can be arbitrarily different from the true objective. This paper provides a general framework to analyze the convergence of federated heterogeneous optimization algorithms. It subsumes previously proposed methods such as FedAvg and FedProx and provides the first principled understanding of the solution bias and the convergence slowdown due to objective inconsistency. Using insights from this analysis, we propose Fed-Nova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.