CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
CFedAvg: Achieving Efficient Communication and Fast Convergence in Non-IID Federated Learning
复制标题
DOI：
10.23919/wiopt52861.2021.9589061
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Haibo Yang;Jia Liu;E. Bentley
中科院分区：
文献类型：
--
作者：
Haibo Yang;Jia Liu;E. Bentley
联邦学习（FL）是一种流行的分布式学习范式，其中大量的工作者联合学习模型，而无需共享他们的训练数据。然而，由于大规模（深度）学习模型和带宽受限的连接，FL中可能会出现高通信成本。在本文中，我们介绍了一个通信效率的算法框架，称为CFedAvg FL与非i.i.d.数据集，它与一般（有偏或无偏）SNR约束的压缩器一起工作。我们分析了CFedAvg的收敛速度与常数和衰减学习率的非凸函数。CFedAvg算法可以实现$\mathcal{O}\left（{1/\sqrt {mKT} + 1/T} \right）$收敛速度，具有恒定的学习速率，这意味着随着工人数量的增加，收敛的线性加速，其中K是局部步骤的数量，T是总通信轮数，m是总工人数量。这与分布式/联邦学习的收敛速度相匹配，而无需压缩，从而实现了高通信效率，同时不会牺牲FL中的学习精度。此外，我们将CFedAvg扩展到具有异构本地步骤的情况下，这允许不同的工作人员执行不同数量的本地步骤，以更好地适应自己的情况。一般来说，有趣的观察是压缩器引入的噪声/方差不影响非独立同分布的总体收敛速率阶。我们验证了我们的CFedAvg算法的有效性在三个数据集上的两个梯度压缩方案的不同压缩比。
Federated learning (FL) is a prevailing distributed learning paradigm, where a large number of workers jointly learn a model without sharing their training data. However, high communication costs could arise in FL due to large-scale (deep) learning models and bandwidth-constrained connections. In this paper, we introduce a communication-efficient algorithmic framework called CFedAvg for FL with non-i.i.d. datasets, which works with general (biased or unbiased) SNR-constrained compressors. We analyze the convergence rate of CFedAvg for non-convex functions with constant and decaying learning rates. The CFedAvg algorithm can achieve an $\mathcal{O}\left( {1/\sqrt {mKT} + 1/T} \right)$ convergence rate with a constant learning rate, implying a linear speedup for convergence as the number of workers increases, where K is the number of local steps, T is the number of total communication rounds, and m is the total worker number. This matches the convergence rate of distributed/federated learning without compression, thus achieving high communication efficiency while not sacrificing learning accuracy in FL. Furthermore, we extend CFedAvg to cases with heterogeneous local steps, which allows different workers to perform a different number of local steps to better adapt to their own circumstances. The interesting observation in general is that the noise/variance introduced by compressors does not affect the overall convergence rate order for non-i.i.d. FL. We verify the effectiveness of our CFedAvg algorithm on three datasets with two gradient compression schemes of different compression ratios.