Anarchic Federated Learning
Anarchic Federated Learning
复制标题
DOI：
--
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Haibo Yang;Xin Zhang;Prashant Khanduri;Jia Liu
中科院分区：
文献类型：
--
作者：
Haibo Yang;Xin Zhang;Prashant Khanduri;Jia Liu
目前部署在边缘网络上的联邦学习（FL）系统由大量数据和/或计算能力高度异质性的工作人员组成，这需要在时间、工作量、数据异构性等方面灵活的工作人员参与。为了满足灵活的工作人员参与的需求，我们在本文中考虑了一种称为“无政府联邦学习”（AFL）的新的联邦学习范式。与传统的 FL 模型形成鲜明对比的是，AFL 中的每个工作人员都可以根据其当前情况（例如电池电量、通信渠道、隐私问题）自由选择 i）何时参与 FL，以及 ii）每轮执行的本地步骤数。然而，AFL 中这种混乱的工人行为给算法设计带来了许多新的开放性问题。特别是，目前尚不清楚是否可以开发收敛的 AFL 训练算法，如果可以，在什么条件下以及可实现的收敛速度有多快。为此，我们提出了两种无政府联邦平均（AFA）算法，具有跨设备和跨孤岛设置的双边学习率，分别命名为 AFA-CD 和 AFA-CS。有点令人惊讶的是，我们表明，在温和的无政府主义假设下，两种 AFL 算法都实现了作为传统 FL 的最先进算法的最著名的收敛速度。此外，在新的 AFL 范式中，它们在工人数量和本地步骤方面保留了非常理想的{\em线性加速效应}。我们通过对现实世界数据集的大量实验来验证所提出的算法。
Present-day federated learning (FL) systems deployed over edge networks consists of a large number of workers with high degrees of heterogeneity in data and/or computing capabilities, which call for flexible worker participation in terms of timing, effort, data heterogeneity, etc. To satisfy the need for flexible worker participation, we consider a new FL paradigm called"Anarchic Federated Learning"(AFL) in this paper. In stark contrast to conventional FL models, each worker in AFL has the freedom to choose i) when to participate in FL, and ii) the number of local steps to perform in each round based on its current situation (e.g., battery level, communication channels, privacy concerns). However, such chaotic worker behaviors in AFL impose many new open questions in algorithm design. In particular, it remains unclear whether one could develop convergent AFL training algorithms, and if yes, under what conditions and how fast the achievable convergence speed is. Toward this end, we propose two Anarchic Federated Averaging (AFA) algorithms with two-sided learning rates for both cross-device and cross-silo settings, which are named AFA-CD and AFA-CS, respectively. Somewhat surprisingly, we show that, under mild anarchic assumptions, both AFL algorithms achieve the best known convergence rate as the state-of-the-art algorithms for conventional FL. Moreover, they retain the highly desirable {\em linear speedup effect} with respect of both the number of workers and local steps in the new AFL paradigm. We validate the proposed algorithms with extensive experiments on real-world datasets.