Global Convergence of Federated Learning for Mixed Regression
Global Convergence of Federated Learning for Mixed Regression
复制标题
DOI：
10.48550/arxiv.2206.07279
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Lili Su;Jiaming Xu;Pengkun Yang
中科院分区：
文献类型：
--
作者：
Lili Su;Jiaming Xu;Pengkun Yang
本文研究了当客户端呈现集群结构时联邦学习下的模型训练问题。我们将这个问题置于混合回归中，其中每个客户端都具有从 $k$ 未知回归模型之一生成的有限本地数据。我们设计了一种算法，可以从任何初始化中实现全局收敛，并且即使在本地数据量高度不平衡的情况下也能工作——可能存在仅包含 $O(1)$ 数据点的客户端。我们的算法首先在几个锚定客户端（每个都有 $\tilde{\Omega}(k)$ 数据点）上运行矩下降以获得粗略的模型估计。然后，每个客户端交替估计其集群标签，并根据 FedAvg 或 FedProx 细化模型估计。我们分析中的一个关键创新是对聚类误差的统一估计，我们通过基于代数几何理论限制一般多项式概念类的 VC 维来证明这一点。
This paper studies the problem of model training under Federated Learning when clients exhibit cluster structure. We contextualize this problem in mixed regression, where each client has limited local data generated from one of $k$ unknown regression models. We design an algorithm that achieves global convergence from any initialization, and works even when local data volume is highly unbalanced -- there could exist clients that contain $O(1)$ data points only. Our algorithm first runs moment descent on a few anchor clients (each with $\tilde{\Omega}(k)$ data points) to obtain coarse model estimates. Then each client alternately estimates its cluster labels and refines the model estimates based on FedAvg or FedProx. A key innovation in our analysis is a uniform estimate on the clustering errors, which we prove by bounding the VC dimension of general polynomial concept classes based on the theory of algebraic geometry.