由于其在数据隐私保护，有效的沟通和并行数据处理方面的好处，联邦学习（FL）近年来引起了人们的兴趣。同样，采用适当的算法设计，可以实现fl中收敛效应的理想线性加速。但是，FL上的大多数现有作品仅限于I.I.D.的系统。数据和集中参数服务器以及与异质数据集分散的FL上的结果仍然有限。此外，在完全分散的FL下，与数据异质性在完全分散的FL下，可以实现收敛的线性加速仍然是一个悬而未决的问题。在本文中，我们通过提出一种称为Net-Fleet的新算法，以解决具有数据异质性的完全分散的FL系统，以解决这些挑战。我们算法的关键思想是通过合并递归梯度校正技术来处理异质数据集，以增强FL（最初旨在用于通信效率）的本地更新方案。我们表明，在适当的参数设置下，所提出的净型算法实现了收敛的线性加速。我们进一步进行了广泛的数值实验，以评估所提出的净化算法的性能并验证我们的理论发现。

当今部署在边缘网络上的联合学习（FL）系统由大量在数据和/或计算能力中具有高度异质性的工人组成，这些工人要求在时间，努力，数据异质性等方面参加灵活的工作者参与为了满足灵活的工人参与的需求，我们考虑了一种新的FL范式，称为“无政府状态联邦学习”（AFL）（AFL）。与常规FL模型形成鲜明对比的是，AFL中的每个工人都可以自由选择i）何时参加FL，ii）根据当前情况（例如，电池，通信，电池级别，通信渠道，隐私问题）。但是，AFL中这种混乱的工人行为在算法设计中引发了许多新的开放问题。特别是，尚不清楚是否可以开发收敛的AFL训练算法，如果是的，则在什么条件下以及可实现的收敛速度的速度下。为此，我们提出了两种无政府状态的联合平均（AFA）算法，分别命名为AFA-CD和AFA-CS的跨设备和跨核心设置的双向学习率。令人惊讶的是，我们表明，在轻度的无政府状态假设下，这两种AFL算法都达到了最著名的收敛速率，作为常规FL的最新算法。此外，它们保留了新的AFL范式中的工人数量和本地步骤，保留了高度可取的{\ em线性加速效应}。我们通过对现实世界数据集进行广泛的实验来验证提出的算法。

近年来，由于它们在对点对点网络上的分散性学习问题（例如，多机构元学习，多机构的多方强化增强学习学习）上，分散的双层优化问题在网络和机器学习社区中引起了越来越多的关注。 ，个性化的培训和拜占庭的弹性学习）。但是，对于具有有限的计算和通信功能的对等网络上的分散式双层优化，如何实现低样本和通信复杂性是迄今为止尚未探索的两个基本挑战。在本文中，我们首次尝试研究了分别与外部和内部子问题相对应的非凸和强结构结构的分散双重优化问题。本文中我们的主要贡献是两倍：i）我们首先提出了一种称为Interact的确定性算法（Inter-gradient-descent-out-outer-tracked-gradeent），需要$ \ Mathcal {o}的样品复杂性（n \ epsilon） ^{ - 1}）$和$ \ mathcal {o}的通信复杂性（\ epsilon^{ - 1}）$解决双重优化问题，其中$ n $和$ \ epsilon> 0 $是样本的数量在每个代理和所需的平稳性差距上。 ii）为了放宽每次迭代中进行全面梯度评估的需求，我们提出了一个随机方差的互动版本（SVR Interact），该版本将样品复杂性提高到$ \ Mathcal {o}（\ sqrt {n} \ epsilon ^{ - 1}）$在达到与确定算法相同的通信复杂性时。据我们所知，这项工作是第一个实现低样本和通信复杂性，以解决网络上的分散双层优化问题。我们的数值实验也证实了我们的理论发现。

To lower the communication complexity of federated min-max learning, a natural approach is to utilize the idea of infrequent communications (through multiple local updates) same as in conventional federated learning. However, due to the more complicated inter-outer problem structure in federated min-max learning, theoretical understandings of communication complexity for federated min-max learning with infrequent communications remain very limited in the literature. This is particularly true for settings with non-i.i.d. datasets and partial client participation. To address this challenge, in this paper, we propose a new algorithmic framework called stochastic sampling averaging gradient descent ascent (SAGDA), which i) assembles stochastic gradient estimators from randomly sampled clients as control variates and ii) leverages two learning rates on both server and client sides. We show that SAGDA achieves a linear speedup in terms of both the number of clients and local update steps, which yields an $\mathcal{O}(\epsilon^{-2})$ communication complexity that is orders of magnitude lower than the state of the art. Interestingly, by noting that the standard federated stochastic gradient descent ascent (FSGDA) is in fact a control-variate-free special version of SAGDA, we immediately arrive at an $\mathcal{O}(\epsilon^{-2})$ communication complexity result for FSGDA. Therefore, through the lens of SAGDA, we also advance the current understanding on communication complexity of the standard FSGDA method for federated min-max learning.

Federated learning has attracted increasing attention with the emergence of distributed data. While extensive federated learning algorithms have been proposed for the non-convex distributed problem, the federated learning in practice still faces numerous challenges, such as the large training iterations to converge since the sizes of models and datasets keep increasing, and the lack of adaptivity by SGD-based model updates. Meanwhile, the study of adaptive methods in federated learning is scarce and existing works either lack a complete theoretical convergence guarantee or have slow sample complexity. In this paper, we propose an efficient adaptive algorithm (i.e., FAFED) based on the momentum-based variance reduced technique in cross-silo FL. We first explore how to design the adaptive algorithm in the FL setting. By providing a counter-example, we prove that a simple combination of FL and adaptive methods could lead to divergence. More importantly, we provide a convergence analysis for our method and prove that our algorithm is the first adaptive FL algorithm to reach the best-known samples $O(\epsilon^{-3})$ and $O(\epsilon^{-2})$ communication rounds to find an $\epsilon$-stationary point without large batches. The experimental results on the language modeling task and image classification task with heterogeneous data demonstrate the efficiency of our algorithms.

Decentralized bilevel optimization has received increasing attention recently due to its foundational role in many emerging multi-agent learning paradigms (e.g., multi-agent meta-learning and multi-agent reinforcement learning) over peer-to-peer edge networks. However, to work with the limited computation and communication capabilities of edge networks, a major challenge in developing decentralized bilevel optimization techniques is to lower sample and communication complexities. This motivates us to develop a new decentralized bilevel optimization called DIAMOND (decentralized single-timescale stochastic approximation with momentum and gradient-tracking). The contributions of this paper are as follows: i) our DIAMOND algorithm adopts a single-loop structure rather than following the natural double-loop structure of bilevel optimization, which offers low computation and implementation complexity; ii) compared to existing approaches, the DIAMOND algorithm does not require any full gradient evaluations, which further reduces both sample and computational complexities; iii) through a careful integration of momentum information and gradient tracking techniques, we show that the DIAMOND algorithm enjoys $\mathcal{O}(\epsilon^{-3/2})$ in sample and communication complexities for achieving an $\epsilon$-stationary solution, both of which are independent of the dataset sizes and significantly outperform existing works. Extensive experiments also verify our theoretical findings.

我们考虑了分布式随机优化问题，其中$ 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的最佳通信策略，并恢复了最新的收敛速率结果。最后，我们通过广泛的数值实验证明我们的理论结果是合理的。

联合学习（FL）是一个蓬勃发展的分布式机器学习框架，其中中心参数服务器（PS）协调许多本地用户以训练全局一致的模型。传统的联合学习不可避免地依赖于具有PS的集中拓扑。因此，一旦PS失败，它将瘫痪。为了缓解如此单点故障，特别是在PS上，一些现有的工作已经提供了CDSGD和D-PSGD等分散的FL（DFL）实现，以便于分散拓扑中的流体。然而，这些方法仍存在一些问题，例如，在CDSGD中的用户最终模型和D-PSGD中的网络范围的模型平均必需品之间存在一些问题。为了解决这些缺陷，本文设计了一种作为DACFL的新DFL实现，其中每个用户使用自己的训练数据列举其模型，并通过对称和双随机矩阵将中间模型与其邻居交换。 DACFL将每个用户本地培训的进度视为离散时间过程，并采用第一个订单动态平均共识（FODAC）方法来跟踪\ Texit {平均模型}在没有PS的情况下。在本文中，我们还提供了DACFL的理论收敛性分析，即在I.I.D数据的前提下，以加强其合理性。 Mnist，Fashion-Mnist和CiFar-10的实验结果验证了我们在几间不变性和时变网络拓扑中的解决方案的可行性，并在大多数情况下声明DACFL优于D-PSGD和CDSGD。

客户端之间的非独立和相同分布（非IID）数据分布被视为降低联合学习（FL）性能的关键因素。处理非IID数据（如个性化FL和联邦多任务学习（FMTL）的几种方法对研究社区有很大兴趣。在这项工作中，首先，我们使用Laplacian正规化制定FMTL问题，明确地利用客户模型之间的关系进行多任务学习。然后，我们介绍了FMTL问题的新视图，首次表明配制的FMTL问题可用于传统的FL和个性化FL。我们还提出了两种算法FEDU和DFEDU，分别解决了通信集中和分散方案中的配制FMTL问题。从理论上讲，我们证明了两种算法的收敛速率实现了用于非凸起目标的强大凸起和载位加速的线性加速。实验，我们表明我们的算法优于FL设置的传统算法FedVG，在FMTL设置中的Mocha，以及个性化流程中的PFEDME和PER-FEDAVG。

A key assumption in most existing works on FL algorithms' convergence analysis is that the noise in stochastic first-order information has a finite variance. Although this assumption covers all light-tailed (i.e., sub-exponential) and some heavy-tailed noise distributions (e.g., log-normal, Weibull, and some Pareto distributions), it fails for many fat-tailed noise distributions (i.e., ``heavier-tailed'' with potentially infinite variance) that have been empirically observed in the FL literature. To date, it remains unclear whether one can design convergent algorithms for FL systems that experience fat-tailed noise. This motivates us to fill this gap in this paper by proposing an algorithmic framework called FAT-Clipping (\ul{f}ederated \ul{a}veraging with \ul{t}wo-sided learning rates and \ul{clipping}), which contains two variants: FAT-Clipping per-round (FAT-Clipping-PR) and FAT-Clipping per-iteration (FAT-Clipping-PI). Specifically, for the largest $\alpha \in (1,2]$ such that the fat-tailed noise in FL still has a bounded $\alpha$-moment, we show that both variants achieve $\mathcal{O}((mT)^{\frac{2-\alpha}{\alpha}})$ and $\mathcal{O}((mT)^{\frac{1-\alpha}{3\alpha-2}})$ convergence rates in the strongly-convex and general non-convex settings, respectively, where $m$ and $T$ are the numbers of clients and communication rounds. Moreover, at the expense of more clipping operations compared to FAT-Clipping-PR, FAT-Clipping-PI further enjoys a linear speedup effect with respect to the number of local updates at each client and being lower-bound-matching (i.e., order-optimal). Collectively, our results advance the understanding of designing efficient algorithms for FL systems that exhibit fat-tailed first-order oracle information.

在联合学习（FL）的新兴范式中，大量客户端（例如移动设备）用于在各自的数据上训练可能的高维模型。由于移动设备的带宽低，分散的优化方法需要将计算负担从那些客户端转移到计算服务器，同时保留隐私和合理的通信成本。在本文中，我们专注于深度，如多层神经网络的培训，在FL设置下。我们提供了一种基于本地模型的层状和维度更新的新型联合学习方法，减轻了非凸起和手头优化任务的多层性质的新型联合学习方法。我们为Fed-Lamb提供了一种彻底的有限时间收敛性分析，表征其渐变减少的速度有多速度。我们在IID和非IID设置下提供实验结果，不仅可以证实我们的理论，而且与最先进的方法相比，我们的方法的速度更快。

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.

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.

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

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

Data heterogeneity across clients is a key challenge in federated learning. Prior works address this by either aligning client and server models or using control variates to correct client model drift. Although these methods achieve fast convergence in convex or simple non-convex problems, the performance in over-parameterized models such as deep neural networks is lacking. In this paper, we first revisit the widely used FedAvg algorithm in a deep neural network to understand how data heterogeneity influences the gradient updates across the neural network layers. We observe that while the feature extraction layers are learned efficiently by FedAvg, the substantial diversity of the final classification layers across clients impedes the performance. Motivated by this, we propose to correct model drift by variance reduction only on the final layers. We demonstrate that this significantly outperforms existing benchmarks at a similar or lower communication cost. We furthermore provide proof for the convergence rate of our algorithm.

为了提高分布式学习的训练速度，近年来见证了人们对开发同步和异步分布式随机方差减少优化方法的极大兴趣。但是，所有现有的同步和异步分布式训练算法都遭受了收敛速度或实施复杂性的各种局限性。这激发了我们提出一种称为\ algname（\ ul {s} emi-as \ ul {yn}的算法} ent \ ul {s} earch），它利用方差减少框架的特殊结构来克服同步和异步分布式学习算法的局限性，同时保留其显着特征。我们考虑分布式和共享内存体系结构下的\ algname的两个实现。我们表明我们的\ algname算法具有\（o（\ sqrt {n} \ epsilon^{ - 2}（ - 2}（\ delta+1）+n）\）\）和\（o（\ sqrt {n} {n} 2}（\ delta+1）d+n）\）用于实现\（\ epsilon \）的计算复杂性 - 分布式和共享内存体系结构分别在非convex学习中的固定点，其中\（n \）表示培训样本的总数和\（\ delta \）表示工人的最大延迟。此外，我们通过建立二次强烈凸和非convex优化的算法稳定性界限来研究\ algname的概括性能。我们进一步进行广泛的数值实验来验证我们的理论发现

在互联网上的多种代理环境中的新兴应用程序，如互联网，网络传感，自主系统和联合学习，呼叫分散算法，以便在计算和通信方面是资源有效的有限总和优化。在本文中，我们考虑了原型设置，其中代理正在协作地工作，以通过在预定的网络拓扑中与其邻居通信来最小化局部损失函数的总和。我们开发了一种新的算法，称为分散的随机递归梯度方法（DESTRess），用于非耦合有限和优化，它与集中式算法的最佳增量一阶Oracle（IFO）复杂性匹配，用于查找一阶静止点，同时保持通信效率。详细的理论和数值比较证实了迭代在广泛的参数制度上提高现有分散算法的资源效率。 Descress利用了多个关键算法设计思路，包括随机激活的随机递增渐变渐变更新，具有用于本地计算的迷你批次，梯度跟踪，梯度跟踪，用于额外混合（即，多个八卦轮），用于偏移通信，以及仔细选择超参数和新的分析框架可证明达到理想的计算 - 通信权衡。

在最近的联邦学习研究中，使用大批量提高了收敛率，但是与使用小批量相比，它需要额外的计算开销。为了克服这一限制，我们提出了一个统一的框架，该框架基于时间变化的概率将参与者分为锚和矿工组。锚点组中的每个客户都使用大批量计算梯度，该梯度被视为其靶心。矿工组中的客户使用串行迷你批次执行多个本地更新，并且每个本地更新也受到客户平均值Bullseyes的平均值的全局目标的间接调节。结果，矿工组遵循了对全球最小化器的近乎最佳更新，该更新适合更新全局模型。通过$ \ epsilon $ - Approximation衡量，FedAmd通过以恒定概率对锚点进行采样锚点，在非convex目标下达到了$ o（1/\ epsilon）$的收敛速率。理论上的结果大大超过了最先进的算法BVR-l-SGD $ O（1/\ Epsilon^{3/2}）$，而FedAmd至少减少了$ O（1/\ Epsilon）$沟通开销。关于现实世界数据集的实证研究验证了FedAmd的有效性，并证明了我们提出的算法的优势。

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.