SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Sai Praneeth Karimireddy;Satyen Kale;M. Mohri;Sashank J. Reddi;Sebastian U. Stich;A. Suresh
中科院分区：
文献类型：
--
作者：
Sai Praneeth Karimireddy;Satyen Kale;M. Mohri;Sashank J. Reddi;Sebastian U. Stich;A. Suresh
联邦平均 (FedAvg) 因其简单性和低通信成本而成为联邦学习的首选算法。然而，尽管最近进行了研究工作，但其性能尚未得到充分了解。我们获得了 FedAvg 的严格收敛率，并证明当数据异构（非独立同分布）时，它会受到“客户端漂移”的影响，从而导致不稳定且缓慢的收敛。作为解决方案，我们提出了一种新算法（SCAFFOLD），它使用控制变量（方差减少）来纠正本地更新中的“客户端漂移”。我们证明 SCAFFOLD 需要的通信次数显着减少，并且不受数据异构性或客户端采样的影响。此外，我们还表明（对于二次方程）SCAFFOLD 可以利用客户数据的相似性，从而产生更快的收敛速度。后者是量化分布式优化中局部步骤的有用性的第一个结果。
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.