联合学习(FL)是分布式学习的一种变体,其中Edge设备可以协作学习模型,而无需与中央服务器或彼此共享数据。我们将使用公共客户库作为多模型FL的联合设置中同时培训多个独立模型的过程。在这项工作中,我们提出了用于多模型FL的流行FedAvg算法的两个变体,并具有可证明的收敛保证。我们进一步表明,对于相同数量的计算,多模型FL可以比单独训练每个模型具有更好的性能。我们通过在强凸,凸和非凸面设置中进行实验来补充理论结果。
translated by 谷歌翻译
在最新的联合学习研究(FL)的研究中,广泛采用了客户选择方案来处理沟通效率的问题。但是,从随机选择的非代表性子集汇总的模型更新的较大差异直接减慢了FL收敛性。我们提出了一种新型的基于聚类的客户选择方案,以通过降低方差加速FL收敛。简单而有效的方案旨在改善聚类效果并控制效果波动,因此,以采样的一定代表性生成客户子集。从理论上讲,我们证明了降低方差方案的改进。由于差异的差异,我们还提供了提出方法的更严格的收敛保证。实验结果证实了与替代方案相比,我们计划的效率超出了效率。
translated by 谷歌翻译
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.
translated by 谷歌翻译
联合学习(FL)算法通常在每个圆数(部分参与)大并且服务器的通信带宽有限时对每个轮子(部分参与)进行分数。近期对FL的收敛分析的作品专注于无偏见的客户采样,例如,随机均匀地采样,由于高度的系统异质性和统计异质性而均匀地采样。本文旨在设计一种自适应客户采样算法,可以解决系统和统计异质性,以最小化壁时钟收敛时间。我们获得了具有任意客户端采样概率的流动算法的新的遗传融合。基于界限,我们分析了建立了总学习时间和采样概率之间的关系,这导致了用于训练时间最小化的非凸优化问题。我们设计一种高效的算法来学习收敛绑定中未知参数,并开发低复杂性算法以大致解决非凸面问题。硬件原型和仿真的实验结果表明,与几个基线采样方案相比,我们所提出的采样方案显着降低了收敛时间。值得注意的是,我们的硬件原型的方案比均匀的采样基线花费73%,以达到相同的目标损失。
translated by 谷歌翻译
联合学习是一种分布式学习的形式,具有关键挑战,是参与客户端中数据的非相同分布性质。在本文中,我们将联合学习扩展到多个无相关模型同时培训的设置。具体而言,每个客户端都能够一次训练M个模型中的任何一个,并且服务器维护每个M模型的模型,其通常是由客户端计算的模型的适当平均版本。我们提出了多次将学习任务分配给客户的多项政策。在第一个政策中,我们将广泛研究的FASHVG通过将模型分配给I.I.D中的客户来扩展到多模型学习。随机的方式。此外,我们在多模型联合设置中提出了两个新的客户选择策略,这是基于每个客户模型对的当前本地损失的决策。我们比较涉及合成和现实世界数据的任务的政策的表现,并表征拟议的政策的表现。远离我们的工作的关键是,所提出的多模型政策更好地表现出更好或至少与使用FEDAVG的单一模型培训一样好。
translated by 谷歌翻译
从经验上证明,在跨客户聚集之前应用多个本地更新的实践是克服联合学习(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中局部更新的使用。
translated by 谷歌翻译
数据异构联合学习(FL)系统遭受了两个重要的收敛误差来源:1)客户漂移错误是由于在客户端执行多个局部优化步骤而引起的,以及2)部分客户参与错误,这是一个事实,仅一小部分子集边缘客户参加每轮培训。我们发现其中,只有前者在文献中受到了极大的关注。为了解决这个问题,我们提出了FedVarp,这是在服务器上应用的一种新颖的差异算法,它消除了由于部分客户参与而导致的错误。为此,服务器只是将每个客户端的最新更新保持在内存中,并将其用作每回合中非参与客户的替代更新。此外,为了减轻服务器上的内存需求,我们提出了一种新颖的基于聚类的方差降低算法clusterfedvarp。与以前提出的方法不同,FedVarp和ClusterFedVarp均不需要在客户端上进行其他计算或其他优化参数的通信。通过广泛的实验,我们表明FedVarp优于最先进的方法,而ClusterFedVarp实现了与FedVarp相当的性能,并且记忆要求较少。
translated by 谷歌翻译
我们考虑开放的联合学习(FL)系统,客户可以在FL过程中加入和/或离开系统。鉴于当前客户端数量的差异,在开放系统中不能保证与固定模型的收敛性。取而代之的是,我们求助于一个新的性能指标,该指标称我们的开放式FL系统的稳定性为量,该指标量化了开放系统中学习模型的幅度。在假设本地客户端的功能强烈凸出和平滑的假设下,我们从理论上量化了两种FL算法的稳定性半径,即本地SGD和本地ADAM。我们观察到此半径依赖于几个关键参数,包括功能条件号以及随机梯度的方差。通过对合成和现实世界基准数据集的数值模拟,我们的理论结果得到了进一步验证。
translated by 谷歌翻译
Federated learning (FL) is a decentralized and privacy-preserving machine learning technique in which a group of clients collaborate with a server to learn a global model without sharing clients' data. One challenge associated with FL is statistical diversity among clients, which restricts the global model from delivering good performance on each client's task. To address this, we propose an algorithm for personalized FL (pFedMe) using Moreau envelopes as clients' regularized loss functions, which help decouple personalized model optimization from the global model learning in a bi-level problem stylized for personalized FL. Theoretically, we show that pFedMe's convergence rate is state-of-the-art: achieving quadratic speedup for strongly convex and sublinear speedup of order 2/3 for smooth nonconvex objectives. Experimentally, we verify that pFedMe excels at empirical performance compared with the vanilla FedAvg and Per-FedAvg, a meta-learning based personalized FL algorithm.
translated by 谷歌翻译
与训练数据中心的训练传统机器学习(ML)模型相反,联合学习(FL)训练ML模型,这些模型在资源受限的异质边缘设备上包含的本地数据集上。现有的FL算法旨在为所有参与的设备学习一个单一的全球模型,这对于所有参与培训的设备可能没有帮助,这是由于整个设备的数据的异质性。最近,Hanzely和Richt \'{A} Rik(2020)提出了一种新的配方,以培训个性化的FL模型,旨在平衡传统的全球模型与本地模型之间的权衡,该模型可以使用其私人数据对单个设备进行培训只要。他们得出了一种称为无环梯度下降(L2GD)的新算法,以解决该算法,并表明该算法会在需要更多个性化的情况下,可以改善沟通复杂性。在本文中,我们为其L2GD算法配备了双向压缩机制,以进一步减少本地设备和服务器之间的通信瓶颈。与FL设置中使用的其他基于压缩的算法不同,我们的压缩L2GD算法在概率通信协议上运行,在概率通信协议中,通信不会按固定的时间表进行。此外,我们的压缩L2GD算法在没有压缩的情况下保持与香草SGD相似的收敛速率。为了验证算法的效率,我们在凸和非凸问题上都进行了多种数值实验,并使用各种压缩技术。
translated by 谷歌翻译
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.
translated by 谷歌翻译
联合学习(FL)是一个分布式的机器学习框架,可以减轻数据孤岛,在该筒仓中,分散的客户在不共享其私人数据的情况下协作学习全球模型。但是,客户的非独立且相同分布的(非IID)数据对训练有素的模型产生了负面影响,并且具有不同本地更新的客户可能会在每个通信回合中对本地梯度造成巨大差距。在本文中,我们提出了一种联合矢量平均(FedVeca)方法来解决上述非IID数据问题。具体而言,我们为与本地梯度相关的全球模型设定了一个新的目标。局部梯度定义为具有步长和方向的双向向量,其中步长为局部更新的数量,并且根据我们的定义将方向分为正和负。在FedVeca中,方向受步尺的影响,因此我们平均双向向量,以降低不同步骤尺寸的效果。然后,我们理论上分析了步骤大小与全球目标之间的关系,并在每个通信循环的步骤大小上获得上限。基于上限,我们为服务器和客户端设计了一种算法,以自适应调整使目标接近最佳的步骤大小。最后,我们通过构建原型系统对不同数据集,模型和场景进行实验,实验结果证明了FedVeca方法的有效性和效率。
translated by 谷歌翻译
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.
translated by 谷歌翻译
在这项工作中,我们提出了FedSSO,这是一种用于联合学习的服务器端二阶优化方法(FL)。与以前朝这个方向的工作相反,我们在准牛顿方法中采用了服务器端近似,而无需客户的任何培训数据。通过这种方式,我们不仅将计算负担从客户端转移到服务器,而且还消除了客户和服务器之间二阶更新的附加通信。我们为我们的新方法的收敛提供了理论保证,并从经验上证明了我们在凸面和非凸面设置中的快速收敛和沟通节省。
translated by 谷歌翻译
联合学习(FL)是一种新兴学习范例,可以通过确保边缘设备上的客户端数据局部性来保护隐私。由于学习系统的多样性和异质性,FL的优化在实践中具有挑战性。尽管最近的研究努力改善异构数据的优化,但时间不断变化的异构数据在现实世界方案中的影响,例如改变客户数据或在训练期间留下或离开的间歇性客户,并未得到很好地研究。在这项工作中,我们提出了持续的联邦学习(CFL),灵活的框架,以捕获FL的时间不正常性。 CFL涵盖复杂和现实的情景 - 在之前的流派中评估了挑战 - 通过提取过去的本地数据集的信息并近似当地目标函数。从理论上讲,我们证明CFL方法在时间不断发展的场景中实现了比\ FEDAVG更快的会聚率,其中益处依赖于近似质量。在一系列实验中,我们表明数值调查结果与收敛分析相匹配,CFL方法显着优于其他SOTA FL基线。
translated by 谷歌翻译
我们提出了一个新颖的框架,以研究异步联合学习优化,并在梯度更新中延迟。我们的理论框架通过引入随机聚合权重来表示客户更新时间的可变性,从而扩展了标准的FedAvg聚合方案,例如异质硬件功能。我们的形式主义适用于客户具有异质数据集并至少执行随机梯度下降(SGD)的一步。我们证明了这种方案的收敛性,并为相关最小值提供了足够的条件,使其成为联邦问题的最佳选择。我们表明,我们的一般框架适用于现有的优化方案,包括集中学习,FedAvg,异步FedAvg和FedBuff。这里提供的理论允许绘制有意义的指南,以设计在异质条件下的联合学习实验。特别是,我们在这项工作中开发了FedFix,这是FedAvg的新型扩展,从而实现了有效的异步联合训练,同时保留了同步聚合的收敛稳定性。我们在一系列实验上凭经验证明了我们的理论,表明异步FedAvg以稳定性为代价导致快速收敛,我们最终证明了FedFix比同步和异步FedAvg的改善。
translated by 谷歌翻译
众所周知,客户师沟通可能是联邦学习中的主要瓶颈。在这项工作中,我们通过一种新颖的客户端采样方案解决了这个问题,我们将允许的客户数量限制为将其更新传达给主节点的数量。在每个通信回合中,所有参与的客户都会计算他们的更新,但只有具有“重要”更新的客户可以与主人通信。我们表明,可以仅使用更新的规范来衡量重要性,并提供一个公式以最佳客户参与。此公式将所有客户参与的完整更新与我们有限的更新(参与客户数量受到限制)之间的距离最小化。此外,我们提供了一种简单的算法,该算法近似于客户参与的最佳公式,该公式仅需要安全的聚合,因此不会损害客户的隐私。我们在理论上和经验上都表明,对于分布式SGD(DSGD)和联合平均(FedAvg),我们的方法的性能可以接近完全参与,并且优于基线,在参与客户均匀地采样的基线。此外,我们的方法与现有的减少通信开销(例如本地方法和通信压缩方法)的现有方法兼容。
translated by 谷歌翻译
This study investigates clustered federated learning (FL), one of the formulations of FL with non-i.i.d. data, where the devices are partitioned into clusters and each cluster optimally fits its data with a localized model. We propose a novel clustered FL framework, which applies a nonconvex penalty to pairwise differences of parameters. This framework can automatically identify clusters without a priori knowledge of the number of clusters and the set of devices in each cluster. To implement the proposed framework, we develop a novel clustered FL method called FPFC. Advancing from the standard ADMM, our method is implemented in parallel, updates only a subset of devices at each communication round, and allows each participating device to perform a variable amount of work. This greatly reduces the communication cost while simultaneously preserving privacy, making it practical for FL. We also propose a new warmup strategy for hyperparameter tuning under FL settings and consider the asynchronous variant of FPFC (asyncFPFC). Theoretically, we provide convergence guarantees of FPFC for general nonconvex losses and establish the statistical convergence rate under a linear model with squared loss. Our extensive experiments demonstrate the advantages of FPFC over existing methods.
translated by 谷歌翻译
现有理论预测,数据异质性将降低联邦平均(FedAvg)算法在联合学习中的性能。但是,实际上,简单的FedAvg算法的收敛良好。本文解释了与以前的理论预测相矛盾的FedAvg的看似不合理的有效性。我们发现,在以前的理论分析中,有界梯度差异的关键假设太悲观了,无法表征实际应用中的数据异质性。对于一个简单的二次问题,我们证明存在很大的梯度差异对FedAvg的收敛性没有任何负面影响。在这一观察结果的推动下,我们提出了一个新的数量,最佳的平均漂移,以衡量数据异质性的效果,并明确使用它来提出对FedAvg的新理论分析。我们表明,在许多实际联合训练任务中,最佳的平均漂移几乎为零,而梯度差异可能很大。我们的新分析表明,FedAvg可以在均质和异质数据设置中具有相同的收敛速率,因此可以更好地理解其经验成功。
translated by 谷歌翻译
客户端之间的非独立和相同分布(非IID)数据分布被视为降低联合学习(FL)性能的关键因素。处理非IID数据(如个性化FL和联邦多任务学习(FMTL)的几种方法对研究社区有很大兴趣。在这项工作中,首先,我们使用Laplacian正规化制定FMTL问题,明确地利用客户模型之间的关系进行多任务学习。然后,我们介绍了FMTL问题的新视图,首次表明配制的FMTL问题可用于传统的FL和个性化FL。我们还提出了两种算法FEDU和DFEDU,分别解决了通信集中和分散方案中的配制FMTL问题。从理论上讲,我们证明了两种算法的收敛速率实现了用于非凸起目标的强大凸起和载位加速的线性加速。实验,我们表明我们的算法优于FL设置的传统算法FedVG,在FMTL设置中的Mocha,以及个性化流程中的PFEDME和PER-FEDAVG。
translated by 谷歌翻译