在联合学习中,跨客户端聚合本地模型的共同方法是完整模型参数的周期性平均。然而,已经知道,不同的神经网络层可以在客户端上具有不同程度的模型差异。传统的全聚合方案不考虑这种差异并立即同步整个模型参数,导致网络带宽消耗效率低下。在增加沟通成本的同时,聚合在客户端中相似的参数不会进行有意义的培训进度。我们提出FedLama,一个用于可扩展联合学习的一层模型模型聚合方案。 FEDLAMA以层式方式自适应地调整聚合间隔,共同考虑模型差异和通信成本。层面聚合方法可以通过对模型精度的显着影响,整理地控制聚合间隔以放宽聚合频率,而不会对模型精度产生重大影响。我们的实证研究表明,Fedlama在IID数据中将通信成本降低至60%,而非IID数据的70%,同时为Fedivg实现了可比的准确性。
translated by 谷歌翻译
具有周期性模型的本地随机梯度下降(SGD)平均(FEDAVG)是联合学习中的基础算法。该算法在多个工人上独立运行SGD,并定期平均所有工人的模型。然而,当本地SGD与许多工人一起运行时,周期性平均导致跨越工人的重大模型差异,使全局损失缓慢收敛。虽然最近的高级优化方法解决了专注于非IID设置的问题,但由于底层定期模型平均而仍存在模型差异问题。我们提出了一个部分模型平均框架,这些框架减轻了联合学习中的模型差异问题。部分平均鼓励本地模型在参数空间上保持彼此接近,并且它可以更有效地最小化全局损失。鉴于固定数量的迭代和大量工人(128),验证精度高达2.2%的验证精度高于周期性的完整平均值。
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 谷歌翻译
The statistical heterogeneity of the non-independent and identically distributed (non-IID) data in local clients significantly limits the performance of federated learning. Previous attempts like FedProx, SCAFFOLD, MOON, FedNova and FedDyn resort to an optimization perspective, which requires an auxiliary term or re-weights local updates to calibrate the learning bias or the objective inconsistency. However, in addition to previous explorations for improvement in federated averaging, our analysis shows that another critical bottleneck is the poorer optima of client models in more heterogeneous conditions. We thus introduce a data-driven approach called FedSkip to improve the client optima by periodically skipping federated averaging and scattering local models to the cross devices. We provide theoretical analysis of the possible benefit from FedSkip and conduct extensive experiments on a range of datasets to demonstrate that FedSkip achieves much higher accuracy, better aggregation efficiency and competing communication efficiency. Source code is available at: https://github.com/MediaBrain-SJTU/FedSkip.
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 谷歌翻译
在联合学习(FL)的新兴范式中,大量客户端(例如移动设备)用于在各自的数据上训练可能的高维模型。由于移动设备的带宽低,分散的优化方法需要将计算负担从那些客户端转移到计算服务器,同时保留隐私和合理的通信成本。在本文中,我们专注于深度,如多层神经网络的培训,在FL设置下。我们提供了一种基于本地模型的层状和维度更新的新型联合学习方法,减轻了非凸起和手头优化任务的多层性质的新型联合学习方法。我们为Fed-Lamb提供了一种彻底的有限时间收敛性分析,表征其渐变减少的速度有多速度。我们在IID和非IID设置下提供实验结果,不仅可以证实我们的理论,而且与最先进的方法相比,我们的方法的速度更快。
translated by 谷歌翻译
数据异构联合学习(FL)系统遭受了两个重要的收敛误差来源:1)客户漂移错误是由于在客户端执行多个局部优化步骤而引起的,以及2)部分客户参与错误,这是一个事实,仅一小部分子集边缘客户参加每轮培训。我们发现其中,只有前者在文献中受到了极大的关注。为了解决这个问题,我们提出了FedVarp,这是在服务器上应用的一种新颖的差异算法,它消除了由于部分客户参与而导致的错误。为此,服务器只是将每个客户端的最新更新保持在内存中,并将其用作每回合中非参与客户的替代更新。此外,为了减轻服务器上的内存需求,我们提出了一种新颖的基于聚类的方差降低算法clusterfedvarp。与以前提出的方法不同,FedVarp和ClusterFedVarp均不需要在客户端上进行其他计算或其他优化参数的通信。通过广泛的实验,我们表明FedVarp优于最先进的方法,而ClusterFedVarp实现了与FedVarp相当的性能,并且记忆要求较少。
translated by 谷歌翻译
在最新的联合学习研究(FL)的研究中,广泛采用了客户选择方案来处理沟通效率的问题。但是,从随机选择的非代表性子集汇总的模型更新的较大差异直接减慢了FL收敛性。我们提出了一种新型的基于聚类的客户选择方案,以通过降低方差加速FL收敛。简单而有效的方案旨在改善聚类效果并控制效果波动,因此,以采样的一定代表性生成客户子集。从理论上讲,我们证明了降低方差方案的改进。由于差异的差异,我们还提供了提出方法的更严格的收敛保证。实验结果证实了与替代方案相比,我们计划的效率超出了效率。
translated by 谷歌翻译
由于参与客户的异构特征,联邦学习往往受到不稳定和缓慢的收敛。当客户参与比率低时,这种趋势加剧了,因为从每个轮的客户收集的信息容易更加不一致。为了解决挑战,我们提出了一种新的联合学习框架,这提高了服务器端聚合步骤的稳定性,这是通过将客户端发送与全局梯度估计的加速模型来引导本地梯度更新来实现的。我们的算法自然地聚合并将全局更新信息与没有额外的通信成本的参与者传达,并且不需要将过去的模型存储在客户端中。我们还规范了本地更新,以进一步降低偏差并提高本地更新的稳定性。我们根据各种设置执行了关于实际数据的全面实证研究,与最先进的方法相比,在准确性和通信效率方面表现出了拟议方法的显着性能,特别是具有低客户参与率。我们的代码可在https://github.com/ninigapa0 / fedagm获得
translated by 谷歌翻译
联合学习(FL)引发了高通信开销,这可以通过压缩模型更新而大大缓解。然而,网络环境中压缩和模型精度之间的权衡仍不清楚,为简单起见,大多数实现仅采用固定压缩率。在本文中,我们首次系统地检查了该权衡,识别压缩误差对最终模型精度的影响,相对于学习率。具体而言,我们将每个全局迭代的压缩误差因其强大凸面和非凸损耗下的收敛速度分析。然后,我们通过策略性地调整每次迭代中的压缩速率来提高最终模型精度来最大化最终模型精度的适应框架。我们讨论了具有代表压缩算法的实用网络中框架的关键实施问题。对流行的MNIST和CIFAR-10数据集的实验证实,我们的解决方案有效地降低了网络流量,但在FL中保持了高模型精度。
translated by 谷歌翻译
可扩展性和隐私是交叉设备联合学习(FL)系统的两个关键问题。在这项工作中,我们确定了FL中的客户端更新的同步流动聚合不能高效地缩放到几百个并行培训之外。它导致ModelPerforce和训练速度的回报递减,Ampanysto大批量培训。另一方面,FL(即异步FL)中的客户端更新的异步聚合减轻了可扩展性问题。但是,聚合个性链子更新与安全聚合不兼容,这可能导致系统的不良隐私水平。为了解决这些问题,我们提出了一种新颖的缓冲异步聚合方法FedBuff,这是不可知的优化器的选择,并结合了同步和异步FL的最佳特性。我们经验证明FEDBuff比同步FL更有效,比异步FL效率更高3.3倍,同时兼容保留保护技术,如安全聚合和差异隐私。我们在平滑的非凸设置中提供理论融合保证。最后,我们显示在差异私有培训下,FedBuff可以在低隐私设置下占FEDAVGM并实现更高隐私设置的相同实用程序。
translated by 谷歌翻译
Federated Learning是一种机器学习培训范式,它使客户能够共同培训模型而无需共享自己的本地化数据。但是,实践中联合学习的实施仍然面临许多挑战,例如由于重复的服务器 - 客户同步以及基于SGD的模型更新缺乏适应性,大型通信开销。尽管已经提出了各种方法来通过梯度压缩或量化来降低通信成本,并且提出了联合版本的自适应优化器(例如FedAdam)来增加适应性,目前的联合学习框架仍然无法立即解决上述挑战。在本文中,我们提出了一种具有理论融合保证的新型沟通自适应联合学习方法(FedCAMS)。我们表明,在非convex随机优化设置中,我们提出的fedcams的收敛率与$ o(\ frac {1} {\ sqrt {tkm}})$与其非压缩的对应物相同。各种基准的广泛实验验证了我们的理论分析。
translated by 谷歌翻译
Federated learning (FL) is a method to train model with distributed data from numerous participants such as IoT devices. It inherently assumes a uniform capacity among participants. However, participants have diverse computational resources in practice due to different conditions such as different energy budgets or executing parallel unrelated tasks. It is necessary to reduce the computation overhead for participants with inefficient computational resources, otherwise they would be unable to finish the full training process. To address the computation heterogeneity, in this paper we propose a strategy for estimating local models without computationally intensive iterations. Based on it, we propose Computationally Customized Federated Learning (CCFL), which allows each participant to determine whether to perform conventional local training or model estimation in each round based on its current computational resources. Both theoretical analysis and exhaustive experiments indicate that CCFL has the same convergence rate as FedAvg without resource constraints. Furthermore, CCFL can be viewed of a computation-efficient extension of FedAvg that retains model performance while considerably reducing computation overhead.
translated by 谷歌翻译
在这项工作中,我们提出了FedSSO,这是一种用于联合学习的服务器端二阶优化方法(FL)。与以前朝这个方向的工作相反,我们在准牛顿方法中采用了服务器端近似,而无需客户的任何培训数据。通过这种方式,我们不仅将计算负担从客户端转移到服务器,而且还消除了客户和服务器之间二阶更新的附加通信。我们为我们的新方法的收敛提供了理论保证,并从经验上证明了我们在凸面和非凸面设置中的快速收敛和沟通节省。
translated by 谷歌翻译
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.
translated by 谷歌翻译
Federated learning (FL) allows multiple clients cooperatively train models without disclosing local data. However, the existing works fail to address all these practical concerns in FL: limited communication resources, dynamic network conditions and heterogeneous client properties, which slow down the convergence of FL. To tackle the above challenges, we propose a heterogeneity-aware FL framework, called FedCG, with adaptive client selection and gradient compression. Specifically, the parameter server (PS) selects a representative client subset considering statistical heterogeneity and sends the global model to them. After local training, these selected clients upload compressed model updates matching their capabilities to the PS for aggregation, which significantly alleviates the communication load and mitigates the straggler effect. We theoretically analyze the impact of both client selection and gradient compression on convergence performance. Guided by the derived convergence rate, we develop an iteration-based algorithm to jointly optimize client selection and compression ratio decision using submodular maximization and linear programming. Extensive experiments on both real-world prototypes and simulations show that FedCG can provide up to 5.3$\times$ speedup compared to other methods.
translated by 谷歌翻译
联合学习(FL)是一个新的分布式机器学习框架,可以在不收集用户的私人数据的情况下获得可靠的协作培训。但是,由于FL的频繁沟通和平均聚合策略,他们会遇到挑战统计多样性数据和大规模模型。在本文中,我们提出了一个个性化的FL框架,称为基于Tensor分解的个性化联合学习(TDPFED),在该框架中,我们设计了一种具有张力的线性层和卷积层的新颖的张力局部模型,以降低交流成本。 TDPFED使用双级损失函数来通过控制个性化模型和张力的本地模型之间的差距来使全球模型学习的个性化模型优化。此外,有效的分布式学习策略和两种不同的模型聚合策略是为拟议的TDPFED框架设计的。理论融合分析和彻底的实验表明,我们提出的TDPFED框架在降低交流成本的同时实现了最新的性能。
translated by 谷歌翻译
我们提出了一个新颖的框架,以研究异步联合学习优化,并在梯度更新中延迟。我们的理论框架通过引入随机聚合权重来表示客户更新时间的可变性,从而扩展了标准的FedAvg聚合方案,例如异质硬件功能。我们的形式主义适用于客户具有异质数据集并至少执行随机梯度下降(SGD)的一步。我们证明了这种方案的收敛性,并为相关最小值提供了足够的条件,使其成为联邦问题的最佳选择。我们表明,我们的一般框架适用于现有的优化方案,包括集中学习,FedAvg,异步FedAvg和FedBuff。这里提供的理论允许绘制有意义的指南,以设计在异质条件下的联合学习实验。特别是,我们在这项工作中开发了FedFix,这是FedAvg的新型扩展,从而实现了有效的异步联合训练,同时保留了同步聚合的收敛稳定性。我们在一系列实验上凭经验证明了我们的理论,表明异步FedAvg以稳定性为代价导致快速收敛,我们最终证明了FedFix比同步和异步FedAvg的改善。
translated by 谷歌翻译
当今部署在边缘网络上的联合学习(FL)系统由大量在数据和/或计算能力中具有高度异质性的工人组成,这些工人要求在时间,努力,数据异质性等方面参加灵活的工作者参与为了满足灵活的工人参与的需求,我们考虑了一种新的FL范式,称为“无政府状态联邦学习”(AFL)(AFL)。与常规FL模型形成鲜明对比的是,AFL中的每个工人都可以自由选择i)何时参加FL,ii)根据当前情况(例如,电池,通信,电池级别,通信渠道,隐私问题)。但是,AFL中这种混乱的工人行为在算法设计中引发了许多新的开放问题。特别是,尚不清楚是否可以开发收敛的AFL训练算法,如果是的,则在什么条件下以及可实现的收敛速度的速度下。为此,我们提出了两种无政府状态的联合平均(AFA)算法,分别命名为AFA-CD和AFA-CS的跨设备和跨核心设置的双向学习率。令人惊讶的是,我们表明,在轻度的无政府状态假设下,这两种AFL算法都达到了最著名的收敛速率,作为常规FL的最新算法。此外,它们保留了新的AFL范式中的工人数量和本地步骤,保留了高度可取的{\ em线性加速效应}。我们通过对现实世界数据集进行广泛的实验来验证提出的算法。
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 谷歌翻译