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

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

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

Federated learning (FL) has emerged as an instance of distributed machine learning paradigm that avoids the transmission of data generated on the users' side. Although data are not transmitted, edge devices have to deal with limited communication bandwidths, data heterogeneity, and straggler effects due to the limited computational resources of users' devices. A prominent approach to overcome such difficulties is FedADMM, which is based on the classical two-operator consensus alternating direction method of multipliers (ADMM). The common assumption of FL algorithms, including FedADMM, is that they learn a global model using data only on the users' side and not on the edge server. However, in edge learning, the server is expected to be near the base station and have direct access to rich datasets. In this paper, we argue that leveraging the rich data on the edge server is much more beneficial than utilizing only user datasets. Specifically, we show that the mere application of FL with an additional virtual user node representing the data on the edge server is inefficient. We propose FedTOP-ADMM, which generalizes FedADMM and is based on a three-operator ADMM-type technique that exploits a smooth cost function on the edge server to learn a global model parallel to the edge devices. Our numerical experiments indicate that FedTOP-ADMM has substantial gain up to 33\% in communication efficiency to reach a desired test accuracy with respect to FedADMM, including a virtual user on the edge server.

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

联合学习（FL）是在分布式的数据上进行的有希望的隐私机器学习范式。在FL中，每个用户在本地保存数据。这样可以保护用户隐私，但也使服务器难以验证数据质量，尤其是在正确标记数据的情况下。用损坏的标签培训对联邦学习任务有害；但是，在标签噪声的情况下，很少关注FL。在本文中，我们专注于这个问题，并提出一种基于学习的重新加权方法，以减轻FL中嘈杂标签的效果。更确切地说，我们为每个训练样本调整了一个重量，以使学习模型在验证集上具有最佳的概括性能。更正式的是，该过程可以作为联合双层优化问题进行配合。二重优化问题是一种优化问题，具有两个纠缠问题的级别。非分布的二聚体问题最近通过新的有效算法见证了显着的进展。但是，解决联合学习设置下的二杆优化问题的研究不足。我们确定高级评估中的高沟通成本是主要的瓶颈。因此，我们建议\ textit {comm-fedbio}解决一般联合的双杆优化问题；更具体地说，我们提出了两个沟通效率的子例程，以估计高级别。还提供了所提出算法的收敛分析。最后，我们应用提出的算法来解决嘈杂的标签问题。与各种基线相比，我们的方法在几个现实世界数据集上表现出了出色的性能。

由于客户端的通信资源有限和大量的模型参数，大规模分布式学习任务遭受通信瓶颈。梯度压缩是通过传输压缩梯度来减少通信负载的有效方法。由于在随机梯度下降的情况下，相邻轮的梯度可能具有高相关，因为他们希望学习相同的模型，提出了一种用于联合学习的实用梯度压缩方案，它使用历史梯度来压缩梯度并且基于Wyner-Ziv编码但没有任何概率的假设。我们还在实时数据集上实现了我们的渐变量化方法，我们的方法的性能优于前一个方案。

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

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.

标准联合优化方法成功地适用于单层结构的随机问题。然而，许多当代的ML问题 - 包括对抗性鲁棒性，超参数调整和参与者 - 批判性 - 属于嵌套的双层编程，这些编程包含微型型和组成优化。在这项工作中，我们提出了\ fedblo：一种联合交替的随机梯度方法来解决一般的嵌套问题。我们在存在异质数据的情况下为\ fedblo建立了可证明的收敛速率，并引入了二聚体，最小值和组成优化的变化。\ fedblo引入了多种创新，包括联邦高级计算和降低方差，以解决内部级别的异质性。我们通过有关超参数\＆超代理学习和最小值优化的实验来补充我们的理论，以证明我们方法在实践中的好处。代码可在https://github.com/ucr-optml/fednest上找到。

One of the crucial issues in federated learning is how to develop efficient optimization algorithms. Most of the current ones require full device participation and/or impose strong assumptions for convergence. Different from the widely-used gradient descent-based algorithms, in this paper, we develop an inexact alternating direction method of multipliers (ADMM), which is both computation- and communication-efficient, capable of combating the stragglers' effect, and convergent under mild conditions. Furthermore, it has a high numerical performance compared with several state-of-the-art algorithms for federated learning.

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

我们考虑开放的联合学习（FL）系统，客户可以在FL过程中加入和/或离开系统。鉴于当前客户端数量的差异，在开放系统中不能保证与固定模型的收敛性。取而代之的是，我们求助于一个新的性能指标，该指标称我们的开放式FL系统的稳定性为量，该指标量化了开放系统中学习模型的幅度。在假设本地客户端的功能强烈凸出和平滑的假设下，我们从理论上量化了两种FL算法的稳定性半径，即本地SGD和本地ADAM。我们观察到此半径依赖于几个关键参数，包括功能条件号以及随机梯度的方差。通过对合成和现实世界基准数据集的数值模拟，我们的理论结果得到了进一步验证。

联邦学习最近在机器学习中迅速发展，引起了各种研究主题。流行的优化算法基于（随机）梯度下降方法的框架或乘数的交替方向方法。在本文中，我们部署了一种确切的惩罚方法来处理联合学习，并提出了一种算法Fedepm，该算法能够解决联合学习中的四个关键问题：沟通效率，计算复杂性，Stragglers的效果和数据隐私。此外，事实证明，它具有收敛性和作证为具有高数值性能。

受到Mishchenko等人（2022）的最新突破的启发，他们首次表明局部梯度步骤可以导致可证明的通信加速，我们提出了一种替代算法，该算法获得了与他们的方法相同的通信加速度（Proxsskip）。但是，我们的方法非常不同：它基于Chambolle和Pock（2011）的著名方法，并具有多种不平凡的修改：i）我们允许通过适当的强烈凸出功能的代理操作员进行不精确的计算。基于梯度的方法（例如，GD，Fast GD或FSFOM），ii）我们对双重更新步骤进行仔细的修改，以保留线性收敛。我们的一般结果为强凸孔座鞍点问题提供了新的最先进率，其双线性耦合为特征，其特征是双重功能缺乏平滑度。当应用于联邦学习时，我们获得了Proxskip的理论上更好的替代方案：我们的方法需要更少的本地步骤（$ O（\ kappa^{1/3}）$或$ o（\ kappa^{1/4}）$，与Proxskip的$ O（\ kappa^{1/2}）$相比，并执行确定性的本地步骤。像Proxskip一样，我们的方法可以应用于连接网络的优化，我们在这里也获得了理论改进。

由于客户端之间标签不平衡的普遍性，联邦对抗域适应是一种独特的分布式Minimax培训任务，每个客户端只看到培训全局模型所需的标签类的子集。为了解决这个问题，我们提出了一个分布式Minimax优化器，称为FEDMM，专为联邦对抗域适应问题而设计。即使在每个客户端具有不同的标签类，某些客户端只有无监督的任务，它也运作良好。我们证明了FEDMM确保将达到域移位无监督数据的静止点收敛。在各种基准数据集中，广泛的实验表明，基于梯度下降升降算法例如，当从头划伤训练时，它以相同的通信回合占据了其他基于GDA的联合平均方法的准确性约为20％;当从预先训练的模型培训时，它始终如一地优于不同网络的5.4 \％$ 9 \％$ 9 \％$。

联合学习（FL）使大量优化的优势计算设备（例如，移动电话）联合学习全局模型而无需数据共享。在FL中，数据以分散的方式产生，具有高异质性。本文研究如何在联邦设置中对统计估算和推断进行统计估算和推理。我们分析所谓的本地SGD，这是一种使用间歇通信来提高通信效率的多轮估计过程。我们首先建立一个{\ IT功能的中央极限定理}，显示了本地SGD的平均迭代弱融合到重新定位的布朗运动。我们接下来提供两个迭代推断方法：{\ IT插件}和{\ IT随机缩放}。随机缩放通过沿整个本地SGD路径的信息构造推断的渐近枢转统计。这两种方法都是通信高效且适用于在线数据。我们的理论和经验结果表明，本地SGD同时实现了统计效率和通信效率。

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

As a novel distributed learning paradigm, federated learning (FL) faces serious challenges in dealing with massive clients with heterogeneous data distribution and computation and communication resources. Various client-variance-reduction schemes and client sampling strategies have been respectively introduced to improve the robustness of FL. Among others, primal-dual algorithms such as the alternating direction of method multipliers (ADMM) have been found being resilient to data distribution and outperform most of the primal-only FL algorithms. However, the reason behind remains a mystery still. In this paper, we firstly reveal the fact that the federated ADMM is essentially a client-variance-reduced algorithm. While this explains the inherent robustness of federated ADMM, the vanilla version of it lacks the ability to be adaptive to the degree of client heterogeneity. Besides, the global model at the server under client sampling is biased which slows down the practical convergence. To go beyond ADMM, we propose a novel primal-dual FL algorithm, termed FedVRA, that allows one to adaptively control the variance-reduction level and biasness of the global model. In addition, FedVRA unifies several representative FL algorithms in the sense that they are either special instances of FedVRA or are close to it. Extensions of FedVRA to semi/un-supervised learning are also presented. Experiments based on (semi-)supervised image classification tasks demonstrate superiority of FedVRA over the existing schemes in learning scenarios with massive heterogeneous clients and client sampling.

联邦学习（FL）已成为一个热门研究领域，以在拥有敏感本地数据的多个客户中对机器学习模型进行协作培训。然而，主要使用随机梯度下降（SGD）研究了不受约束的联邦优化，该梯度下降可能会缓慢收敛，并且限制了联邦优化的优化，这更具挑战性，迄今尚未研究。本文分别研究了基于样本和基于特征的联合优化，并考虑了每个人的无限制和约束非凸问题。首先，我们建议使用随机连续的凸近似（SSCA）和迷你批次技术提出FL算法。这些算法可以充分利用目标和约束函数的结构，并逐步利用样品。我们表明，所提出的FL算法分别收敛到固定点和相应不受约束和约束的非凸问题的固定点和Karush-Kuhn-Tucker（KKT）点。接下来，我们提供算法示例，每回合具有吸引人的计算复杂性和通信负载。我们表明，未约束的联邦优化算法示例与动量SGD相同，与FL算法相同，并在SSCA和动量SGD之间提供分析连接。最后，数值实验证明了在收敛速度，通信和计算成本以及模型规范中提出算法的固有优势。