In this work, we explore combining automatic hyperparameter tuning and optimization for federated learning (FL) in an online, one-shot procedure. We apply a principled approach on a method for adaptive client learning rate, number of local steps, and batch size. In our federated learning applications, our primary motivations are minimizing communication budget as well as local computational resources in the training pipeline. Conventionally, hyperparameter tuning methods involve at least some degree of trial-and-error, which is known to be sample inefficient. In order to address our motivations, we propose FATHOM (Federated AuTomatic Hyperparameter OptiMization) as a one-shot online procedure. We investigate the challenges and solutions of deriving analytical gradients with respect to the hyperparameters of interest. Our approach is inspired by the fact that, with the exception of local data, we have full knowledge of all components involved in our training process, and this fact can be exploited in our algorithm impactfully. We show that FATHOM is more communication efficient than Federated Averaging (FedAvg) with optimized, static valued hyperparameters, and is also more computationally efficient overall. As a communication efficient, one-shot online procedure, FATHOM solves the bottleneck of costly communication and limited local computation, by eliminating a potentially wasteful tuning process, and by optimizing the hyperparamters adaptively throughout the training procedure without trial-and-error. We show our numerical results through extensive empirical experiments with the Federated EMNIST-62 (FEMNIST) and Federated Stack Overflow (FSO) datasets, using FedJAX as our baseline framework.

Federated learning is a distributed machine learning paradigm in which a large number of clients coordinate with a central server to learn a model without sharing their own training data. Standard federated optimization methods such as Federated Averaging (FEDAVG) are often difficult to tune and exhibit unfavorable convergence behavior. In non-federated settings, adaptive optimization methods have had notable success in combating such issues. In this work, we propose federated versions of adaptive optimizers, including ADAGRAD, ADAM, and YOGI, and analyze their convergence in the presence of heterogeneous data for general nonconvex settings. Our results highlight the interplay between client heterogeneity and communication efficiency. We also perform extensive experiments on these methods and show that the use of adaptive optimizers can significantly improve the performance of federated learning.

Federated Learning是一种机器学习培训范式，它使客户能够共同培训模型而无需共享自己的本地化数据。但是，实践中联合学习的实施仍然面临许多挑战，例如由于重复的服务器 - 客户同步以及基于SGD的模型更新缺乏适应性，大型通信开销。尽管已经提出了各种方法来通过梯度压缩或量化来降低通信成本，并且提出了联合版本的自适应优化器（例如FedAdam）来增加适应性，目前的联合学习框架仍然无法立即解决上述挑战。在本文中，我们提出了一种具有理论融合保证的新型沟通自适应联合学习方法（FedCAMS）。我们表明，在非convex随机优化设置中，我们提出的fedcams的收敛率与$ o（\ frac {1} {\ sqrt {tkm}}）$与其非压缩的对应物相同。各种基准的广泛实验验证了我们的理论分析。

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

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

我们展示了一个联合学习框架，旨在强大地提供具有异构数据的各个客户端的良好预测性能。所提出的方法对基于SuperQualile的学习目标铰接，捕获异构客户端的误差分布的尾统计。我们提出了一种随机训练算法，其与联合平均步骤交织差异私人客户重新重量步骤。该提出的算法支持有限时间收敛保证，保证覆盖凸和非凸面设置。关于联邦学习的基准数据集的实验结果表明，我们的方法在平均误差方面与古典误差竞争，并且在误差的尾统计方面优于它们。

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

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.

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

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

我们提出了一个新颖的框架，以研究异步联合学习优化，并在梯度更新中延迟。我们的理论框架通过引入随机聚合权重来表示客户更新时间的可变性，从而扩展了标准的FedAvg聚合方案，例如异质硬件功能。我们的形式主义适用于客户具有异质数据集并至少执行随机梯度下降（SGD）的一步。我们证明了这种方案的收敛性，并为相关最小值提供了足够的条件，使其成为联邦问题的最佳选择。我们表明，我们的一般框架适用于现有的优化方案，包括集中学习，FedAvg，异步FedAvg和FedBuff。这里提供的理论允许绘制有意义的指南，以设计在异质条件下的联合学习实验。特别是，我们在这项工作中开发了FedFix，这是FedAvg的新型扩展，从而实现了有效的异步联合训练，同时保留了同步聚合的收敛稳定性。我们在一系列实验上凭经验证明了我们的理论，表明异步FedAvg以稳定性为代价导致快速收敛，我们最终证明了FedFix比同步和异步FedAvg的改善。

可扩展性和隐私是交叉设备联合学习（FL）系统的两个关键问题。在这项工作中，我们确定了FL中的客户端更新的同步流动聚合不能高效地缩放到几百个并行培训之外。它导致ModelPerforce和训练速度的回报递减，Ampanysto大批量培训。另一方面，FL（即异步FL）中的客户端更新的异步聚合减轻了可扩展性问题。但是，聚合个性链子更新与安全聚合不兼容，这可能导致系统的不良隐私水平。为了解决这些问题，我们提出了一种新颖的缓冲异步聚合方法FedBuff，这是不可知的优化器的选择，并结合了同步和异步FL的最佳特性。我们经验证明FEDBuff比同步FL更有效，比异步FL效率更高3.3倍，同时兼容保留保护技术，如安全聚合和差异隐私。我们在平滑的非凸设置中提供理论融合保证。最后，我们显示在差异私有培训下，FedBuff可以在低隐私设置下占FEDAVGM并实现更高隐私设置的相同实用程序。

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

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.

联合学习（FL）是一种新兴学习范例，可以通过确保边缘设备上的客户端数据局部性来保护隐私。由于学习系统的多样性和异质性，FL的优化在实践中具有挑战性。尽管最近的研究努力改善异构数据的优化，但时间不断变化的异构数据在现实世界方案中的影响，例如改变客户数据或在训练期间留下或离开的间歇性客户，并未得到很好地研究。在这项工作中，我们提出了持续的联邦学习（CFL），灵活的框架，以捕获FL的时间不正常性。 CFL涵盖复杂和现实的情景 - 在之前的流派中评估了挑战 - 通过提取过去的本地数据集的信息并近似当地目标函数。从理论上讲，我们证明CFL方法在时间不断发展的场景中实现了比\ FEDAVG更快的会聚率，其中益处依赖于近似质量。在一系列实验中，我们表明数值调查结果与收敛分析相匹配，CFL方法显着优于其他SOTA FL基线。

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

在本文中，我们建议在分散的设置中解决一个正规化的分布鲁棒性学习问题，并考虑到数据分配的变化。通过将Kullback-Liebler正则化功能添加到可靠的Min-Max优化问题中，可以将学习问题降低到修改的可靠最小化问题并有效地解决。利用新配制的优化问题，我们提出了一个强大的版本的分散的随机梯度下降（DSGD），分布在分布方面具有强大的分散性随机梯度下降（DR-DSGD）。在一些温和的假设下，前提是正则化参数大于一个，我们从理论上证明DR-DSGD达到了$ \ MATHCAL {O} \ left的收敛速率$，其中$ k $是设备的数量，而$ t $是迭代次数。仿真结果表明，我们提出的算法可以提高最差的分配测试精度，最高$ 10 \％$。此外，DR-DSGD比DSGD更有效，因为它需要更少的沟通回合（最高$ 20 $ $倍）才能达到相同的最差分配测试准确性目标。此外，进行的实验表明，在测试准确性方面，DR-DSGD会导致整个设备的性能更公平。

Federated learning (FL) is an effective technique to directly involve edge devices in machine learning training while preserving client privacy. However, the substantial communication overhead of FL makes training challenging when edge devices have limited network bandwidth. Existing work to optimize FL bandwidth overlooks downstream transmission and does not account for FL client sampling. In this paper we propose GlueFL, a framework that incorporates new client sampling and model compression algorithms to mitigate low download bandwidths of FL clients. GlueFL prioritizes recently used clients and bounds the number of changed positions in compression masks in each round. Across three popular FL datasets and three state-of-the-art strategies, GlueFL reduces downstream client bandwidth by 27% on average and reduces training time by 29% on average.