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

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

期望最大化（EM）算法是潜在变量模型推断的默认算法。与任何其他机器学习领域一样，潜在变量模型到非常大的数据集的应用使得使用高级并行和分布式架构。本文介绍了FEDEM，它是EM算法到联合学习背景的第一个扩展。 FEDEM是一种新的通信高效方法，其处理本地设备的部分参与，并且对数据集的异构分布具有稳健。为了缓解通信瓶颈，FedEM压缩适当定义的完整数据足够的统计数据。我们还开发并分析了FEDEM的延伸，以进一步纳入方差减少方案。在所有情况下，我们都会导出有限时间的复杂性范围，以便平滑非凸起问题。提出了数值结果以支持我们的理论发现，以及对生物多样性监测的联合缺失值估算的应用。

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

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.

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

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.

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

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

分布式优化和学习的最新进展表明，沟通压缩是减少交流的最有效手段之一。尽管在通信压缩下的收敛速率有很多结果，但理论下限仍然缺失。通过通信压缩的算法的分析将收敛归因于两个抽象属性：无偏见的属性或承包属性。它们可以通过单向压缩（仅从工人到服务器的消息被压缩）或双向压缩来应用它们。在本文中，我们考虑了分布式随机算法，以最大程度地减少通信压缩下的平滑和非凸目标函数。我们为算法建立了收敛的下限，无论是在单向或双向中使用无偏压缩机还是使用承包压缩机。为了缩小下限和现有上限之间的差距，我们进一步提出了一种新石器时代的算法，该算法在轻度条件下几乎达到了我们的下限（达到对数因素）。我们的结果还表明，使用承包双向压缩可以产生迭代方法，该方法的收敛速度与使用无偏见的单向压缩的方法一样快。实验结果验证了我们的发现。

现代深度学习模型通常在分布式机器集合中并行培训，以减少训练时间。在这种情况下，机器之间模型更新的通信变成了一个重要的性能瓶颈，并且已经提出了各种有损的压缩技术来减轻此问题。在这项工作中，我们介绍了一种新的，简单但理论上和实践上有效的压缩技术：自然压缩（NC）。我们的技术分别应用于要进行压缩的更新向量的所有条目，并通过随机舍入到两个的（负或正）两种功能，可以通过忽略Mantissa来以“自然”方式计算。我们表明，与没有压缩相比，NC将压缩向量的第二刻增加不超过微小因子$ \ frac {9} {8} $，这意味着NC对流行训练算法的收敛速度的影响，例如分布式SGD，可以忽略不计。但是，NC启用的通信节省是可观的，导致$ 3 $ - $ 4 \ times $ $改善整体理论运行时间。对于需要更具侵略性压缩的应用，我们将NC推广到自然抖动，我们证明这比常见的随机抖动技术要好得多。我们的压缩操作员可以自行使用，也可以与现有操作员结合使用，从而产生更具侵略性的结合效果，并在理论和实践中提供新的最先进。

我们考虑分散的优化问题，其中许多代理通过在基础通信图上交换来最大程度地减少其本地功能的平均值。具体而言，我们将自己置于异步模型中，其中只有一个随机部分在每次迭代时执行计算，而信息交换可以在所有节点之间进行，并以不对称的方式进行。对于此设置，我们提出了一种算法，该算法结合了整个网络上梯度跟踪和差异的差异。这使每个节点能够跟踪目标函数梯度的平均值。我们的理论分析表明，在预期混合矩阵的轻度连通性条件下，当局部目标函数强烈凸面时，算法会汇聚。特别是，我们的结果不需要混合矩阵是双随机的。在实验中，我们研究了一种广播机制，该机制将信息从计算节点传输到其邻居，并确认我们方法在合成和现实世界数据集上的线性收敛性。

我们研究了在$ 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）我们考虑了由联邦学习应用激发的异质功能的情况，并通过证明与先前的作品相比对最大延迟的依赖性较弱，并提高收敛率。特别是，我们表明，收敛率的异质性项仅受每个工人内平均延迟的影响。

使用多个计算节点通常可以加速在大型数据集上的深度神经网络。这种方法称为分布式训练，可以通过专门的消息传递协议，例如环形全部减少。但是，以比例运行这些协议需要可靠的高速网络，其仅在专用集群中可用。相比之下，许多现实世界应用程序，例如联合学习和基于云的分布式训练，在具有不稳定的网络带宽的不可靠的设备上运行。因此，这些应用程序仅限于使用参数服务器或基于Gossip的平均协议。在这项工作中，我们通过提出MOSHPIT全部减少的迭代平均协议来提升该限制，该协议指数地收敛于全局平均值。我们展示了我们对具有强烈理论保证的分布式优化方案的效率。该实验显示了与使用抢占从头开始训练的竞争性八卦的策略和1.5倍的加速，显示了1.3倍的Imagenet培训的加速。

We initiate a formal study of reproducibility in optimization. We define a quantitative measure of reproducibility of optimization procedures in the face of noisy or error-prone operations such as inexact or stochastic gradient computations or inexact initialization. We then analyze several convex optimization settings of interest such as smooth, non-smooth, and strongly-convex objective functions and establish tight bounds on the limits of reproducibility in each setting. Our analysis reveals a fundamental trade-off between computation and reproducibility: more computation is necessary (and sufficient) for better reproducibility.

这项工作审查了旨在在通信约束下运行的自适应分布式学习策略。我们考虑一个代理网络，必须从持续观察流数据来解决在线优化问题。代理商实施了分布式合作策略，其中允许每个代理商与其邻居执行本地信息交换。为了应对通信约束，必须不可避免地压缩交换信息。我们提出了一种扩散策略，昵称为ACTC（适应 - 压缩 - 然后组合），其依赖于以下步骤：i）每个代理执行具有恒定步长大小的单独随机梯度更新的适应步骤; ii）一种压缩步骤，它利用最近引入的随机压缩操作员;和III）每个代理组合从其邻居接收的压缩更新的组合步骤。这项工作的区别要素如下。首先，我们专注于自适应策略，其中常数（而不是递减）阶梯大小对于实时响应非间断变化至关重要。其次，我们考虑一般的指导图表和左随机组合政策，使我们能够增强拓扑和学习之间的相互作用。第三，与对所有个人代理的成本职能承担强大的凸起的相关作品相比，我们只需要在网络水平的强大凸起，即使单个代理具有强凸的成本，剩余的代理商也不满足凸起成本。第四，我们专注于扩散（而不是共识）战略。在压缩信息的苛刻设置下，建立ACTC迭代在所需的优化器周围波动，在相邻代理之间交换的比特方面取得了显着的节省。

在分布式或联合的优化和学习中，不同计算单元之间的通信通常是瓶颈和梯度压缩，可广泛用于减少每个迭代方法中每个通信回合中发送的位数。有两类的压缩操作员和单独的算法利用它们。在具有有界方差的无偏随机压缩机（例如Rand-K）的情况下，Mishchenko等人的Diana算法。 （2019年），它实现了一种减少差异技术来处理压缩引入的差异，是当前的最新状态。在偏见和承包压缩机（例如TOP-K）的情况下，Richt \'Arik等人的EF21算法。 （2021）而不是实现错误反馈机制，是当前的最新状态。这两类的压缩方案和算法是不同的，具有不同的分析和证明技术。在本文中，我们将它们统一成一个框架，并提出了一种新算法，将Diana和EF21恢复为特定情况。我们的一般方法与新的，较大的压缩机类别一起使用，该类别具有两个参数，分别是偏见和方差，并包括无偏见和偏见的压缩机作为特定情况。这使我们能够继承两个世界中最好的：例如EF21，与戴安娜（Diana）不同，可以使用偏见的压缩机，例如Top-k，可以使用其在实践中的良好表现。就像戴安娜（Diana）和EF21不同一样，压缩机的独立随机性可以减轻压缩的影响，当平行工人的数量较大时，收敛速率提高。这是第一次提出具有所有这些功能的算法。我们证明其在某些条件下的线性收敛。我们的方法朝着更好地理解两个SO-FAR不同的沟通效率分布式学习的世界迈出了一步。

In large-scale machine learning, recent works have studied the effects of compressing gradients in stochastic optimization in order to alleviate the communication bottleneck. These works have collectively revealed that stochastic gradient descent (SGD) is robust to structured perturbations such as quantization, sparsification, and delays. Perhaps surprisingly, despite the surge of interest in large-scale, multi-agent reinforcement learning, almost nothing is known about the analogous question: Are common reinforcement learning (RL) algorithms also robust to similar perturbations? In this paper, we investigate this question by studying a variant of the classical temporal difference (TD) learning algorithm with a perturbed update direction, where a general compression operator is used to model the perturbation. Our main technical contribution is to show that compressed TD algorithms, coupled with an error-feedback mechanism used widely in optimization, exhibit the same non-asymptotic theoretical guarantees as their SGD counterparts. We then extend our results significantly to nonlinear stochastic approximation algorithms and multi-agent settings. In particular, we prove that for multi-agent TD learning, one can achieve linear convergence speedups in the number of agents while communicating just $\tilde{O}(1)$ bits per agent at each time step. Our work is the first to provide finite-time results in RL that account for general compression operators and error-feedback in tandem with linear function approximation and Markovian sampling. Our analysis hinges on studying the drift of a novel Lyapunov function that captures the dynamics of a memory variable introduced by error feedback.

In large-scale distributed learning, security issues have become increasingly important. Particularly in a decentralized environment, some computing units may behave abnormally, or even exhibit Byzantine failures-arbitrary and potentially adversarial behavior. In this paper, we develop distributed learning algorithms that are provably robust against such failures, with a focus on achieving optimal statistical performance. A main result of this work is a sharp analysis of two robust distributed gradient descent algorithms based on median and trimmed mean operations, respectively. We prove statistical error rates for three kinds of population loss functions: strongly convex, nonstrongly convex, and smooth non-convex. In particular, these algorithms are shown to achieve order-optimal statistical error rates for strongly convex losses. To achieve better communication efficiency, we further propose a median-based distributed algorithm that is provably robust, and uses only one communication round. For strongly convex quadratic loss, we show that this algorithm achieves the same optimal error rate as the robust distributed gradient descent algorithms.

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