Global Convergence of Federated Learning for Mixed Regression
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Federated LearningregressionSimilar Papers 제목 키워드 기반
A Wasserstein Minimax Framework for Mixed Linear Regression
Multi-modal distributions are commonly used to model clustered data in statistical learning tasks. In this paper, we consider the Mixed Linear Regression (MLR) problem. We propose an optimal transport-based framework for…
Federated LearningregressionGlobal Convergence of EM Algorithm for Mixtures of Two Component Linear Regression
The Expectation-Maximization algorithm is perhaps the most broadly used algorithm for inference of latent variable problems. A theoretical understanding of its performance, however, largely remains lacking. Recent result…
regressionFederated Latent Class Regression for Hierarchical Data
Federated Learning (FL) allows a number of agents to participate in training a global machine learning model without disclosing locally stored data. Compared to traditional distributed learning, the heterogeneity (non-II…
Federated LearningregressionMix2FLD: Downlink Federated Learning After Uplink Federated Distillation With Two-Way Mixup
This letter proposes a novel communication-efficient and privacy-preserving distributed machine learning framework, coined Mix2FLD. To address uplink-downlink capacity asymmetry, local model outputs are uploaded to a ser…
Federated LearningPrivacy PreservingUnveiling the Cycloid Trajectory of EM Iterations in Mixed Linear Regression
We study the trajectory of iterations and the convergence rates of the Expectation-Maximization (EM) algorithm for two-component Mixed Linear Regression (2MLR). The fundamental goal of MLR is to learn the regression mode…
Interpretable Machine LearningLearning TheoryregressionRepresentation Learning