FedExP: Speeding up Federated Averaging Via Extrapolation
FedExP: Speeding up Federated Averaging Via Extrapolation
复制标题
DOI：
10.48550/arxiv.2301.09604
复制
发表时间：
2023-01
期刊：
影响因子：
--
通讯作者：
Divyansh Jhunjhunwala;Shiqiang Wang;Gauri Joshi
中科院分区：
文献类型：
--
作者：
Divyansh Jhunjhunwala;Shiqiang Wang;Gauri Joshi
联合平均（FedAvg）仍然是联合学习（FL）优化的最流行算法，因为其简单的实施，无状态性质和隐私保证与安全的聚合相结合。最近的工作试图通过将客户更新视为伪级梯度并使用服务器步骤大小，将FedAvg的香草平均概括为广义的梯度下降步骤。尽管已经显示出使用服务器步长的使用可以从理论上提供性能改进，但在大多数现有作品中尚未看到服务器步长的实际好处。在这项工作中，我们提出了FedExp，这是一种基于在整个FL过程中动态变化的伪级梯度，可以自适应地确定FL中的服务器步长的方法。我们首先要考虑过度参数化的凸状态，在该方案中，我们揭示了FedAvg和投影对凸集（POCS）算法的有趣相似性。然后，我们展示如何将FEDEXP作为用于加速POC的外推机制的新型扩展。后来，我们的理论分析还讨论了FedEBL在参数化和非凸面设置中的含义。实验结果表明，FEDEX的收敛速度比FedAvg的收敛速度更快，并且在一系列逼真的FL数据集上收敛速度和竞争基线。
Federated Averaging (FedAvg) remains the most popular algorithm for Federated Learning (FL) optimization due to its simple implementation, stateless nature, and privacy guarantees combined with secure aggregation. Recent work has sought to generalize the vanilla averaging in FedAvg to a generalized gradient descent step by treating client updates as pseudo-gradients and using a server step size. While the use of a server step size has been shown to provide performance improvement theoretically, the practical benefit of the server step size has not been seen in most existing works. In this work, we present FedExP, a method to adaptively determine the server step size in FL based on dynamically varying pseudo-gradients throughout the FL process. We begin by considering the overparameterized convex regime, where we reveal an interesting similarity between FedAvg and the Projection Onto Convex Sets (POCS) algorithm. We then show how FedExP can be motivated as a novel extension to the extrapolation mechanism that is used to speed up POCS. Our theoretical analysis later also discusses the implications of FedExP in underparameterized and non-convex settings. Experimental results show that FedExP consistently converges faster than FedAvg and competing baselines on a range of realistic FL datasets.