提出新框架解决移动端联邦学习中客户端参与相关性导致的偏差问题。
Debiasing Federated Learning with Correlated Client Participation
- 将客户端参与建模为马尔可夫链，分析非均匀、相关参与下的收敛性。
- 证明最小间隔越大，由客户端可用性不均带来的偏差越小。
- 设计可证明收敛的去偏算法，适用于任意最小间隔和未知分布场景。
在拥有数百万移动客户端的跨设备联邦学习中，每轮仅少数客户端参与训练，联邦平均（FedAvg）是主流算法。现有对FedAvg的分析通常假设每轮从均匀分布中独立采样参与客户端，这与现实不符。本文构建一个将客户端参与建模为马尔可夫链的理论框架，研究客户端非均匀且相关参与下的优化收敛性。我们分析一种更普遍实际的情形：每个客户端必须等待至少R轮（最小间隔）后才能重新参与。理论上证明并实证观察到，增大最小间隔可降低由客户端可用性内在不均带来的偏差。此外，我们提出一种有效的去偏算法，可在任意最小间隔及未知客户端可用性分布下，保证FedAvg收敛至无偏最优解。
原文摘要 · Abstract (English)
In cross-device federated learning (FL) with millions of mobile clients, only a small subset of clients participate in training in every communication round, and Federated Averaging (FedAvg) is the most popular algorithm in practice. Existing analyses of FedAvg usually assume the participating clients are independently sampled in each round from a uniform distribution, which does not reflect real-world scenarios. This paper introduces a theoretical framework that models client participation in FL as a Markov chain to study optimization convergence when clients have non-uniform and correlated participation across rounds. We apply this framework to analyze a more general and practical pattern: every client must wait a minimum number of $R$ rounds (minimum separation) before re-participating. We theoretically prove and empirically observe that increasing minimum separation reduces the bias induced by intrinsic non-uniformity of client availability in cross-device FL systems. Furthermore, we develop an effective debiasing algorithm for FedAvg that provably converges to the unbiased optimal solution under arbitrary minimum separation and unknown client availability distribution.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。