SCAFFOLD: 用于联邦学习的斯托卡控制动词 (SCAFFOLD: Stochastic Controlled Averaging for Federated Learning)

from arxiv, v2 contains analysis of FedAvg, non-convex rates of Scaffold, and experimental evaluation. v3 fixes typos, ICML version. v4 slightly improves rate of SCAFFOLD for general convex functions

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.

翻译：联邦融合(FedAvg)由于其简单和通信成本低,已成为联邦学习的首选算法,然而,尽管最近进行了一些研究,但其性能并没有得到完全理解。我们获得了FedAvg的紧密趋同率,并证明当数据(非二d)存在差异时,它会受到“客户驱动”的影响,从而导致不稳定和缓慢的趋同。作为一种解决办法,我们提议一种新的算法(SCAFFOLD),使用控制变量(变量减少)来纠正“客户驱动”在当地更新中的“客户驱动”功能。我们证明,SCAFFFOLD需要的通信周期要少得多,而且不受数据差异性或客户抽样的影响。此外,我们表明(对于四面形体)SCAFFFOLD可以利用客户数据中的相似性,从而更快的趋同。后者是量化分布优化方面地方步骤的效用的第一个结果。

相关内容

联邦学习

关注 198

联邦学习（Federated Learning）是一种新兴的人工智能基础技术，在 2016 年由谷歌最先提出，原本用于解决安卓手机终端用户在本地更新模型的问题，其设计目标是在保障大数据交换时的信息安全、保护终端数据和个人数据隐私、保证合法合规的前提下，在多参与方或多计算结点之间开展高效率的机器学习。其中，联邦学习可使用的机器学习算法不局限于神经网络，还包括随机森林等重要算法。联邦学习有望成为下一代人工智能协同算法和协作网络的基础。