mlsanityData to 14 Oct 2026

Fast convergence of a Federated Expectation-Maximization Algorithm

arXiv 2408.05819 ↗First posted 11 Aug 2024stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Data heterogeneity has been a long-standing bottleneck in studying the convergence rates of Federated Learning algorithms. In order to better understand the issue of data heterogeneity, we study the convergence rate of the Expectation-Maximization (EM) algorithm for the Federated Mixture of K Linear Regressions model (FMLR). We completely characterize the convergence rate of the EM algorithm under all regimes of number of clients and number of data points per client, with partial limits in the number of clients. We show that with a signal-to-noise-ratio (SNR) that is atleast of order √K, the well-initialized EM algorithm converges to the ground truth under all regimes. We perform experiments on synthetic data to illustrate our results. In line with our theoretical findings, the simulations show that rather than being a bottleneck, data heterogeneity can accelerate the convergence of iterative federated algorithms.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 36 of its 51 references that are in the map. First posted on arXiv 11 Aug 2024.

Builds on

36 of 51 references.

References · 36

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,669
  2. 2019Advances and Open Problems in Federated Learningcited by 3,046
  3. 2018Federated Optimization in Heterogeneous Networkscited by 2,987
  4. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,229
  5. 2017Federated Multi-Task Learningcited by 672
  6. 2020Ditto: Fair and Robust Federated Learning Through Personalizationcited by 672
  7. 2020Personalized Federated Learning with Moreau Envelopescited by 618
  8. 2018Federated Learning for Mobile Keyboard Predictioncited by 572
  9. 2021FedBN: Federated Learning on Non-IID Features via Local Batch Normalizationcited by 571
  10. 2020An Efficient Framework for Clustered Federated Learningcited by 511
  11. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 367
  12. 2020Three Approaches for Personalization with Applications to Federated Learningcited by 325
24 more
  1. 2020Personalized Federated Learning: A Meta-Learning Approachcited by 312
  2. 2020Personalized Cross-Silo Federated Learning on Non-IID Datacited by 283
  3. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  4. 2021Federated Multi-Task Learning under a Mixture of Distributionscited by 192
  5. 2023Heterogeneous Federated Learning: State-of-the-art and Research Challengescited by 161
  6. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  7. 2014Statistical guarantees for the EM algorithm: From population to sample-based analysiscited by 133
  8. 2019Overcoming Forgetting in Federated Learning on Non-IID Datacited by 120
  9. 2021Multi-Center Federated Learning: Clients Clustering for Better Personalizationcited by 113
  10. 2023FedDisco: Federated Learning with Discrepancy-Aware Collaborationcited by 67
  11. 2022FedCorr: Multi-Stage Federated Learning for Label Noise Correctioncited by 61
  12. 2016Ten Steps of EM Suffice for Mixtures of Two Gaussianscited by 40
  13. 2023Personalized Federated Learning under Mixture of Distributionscited by 37
  14. 2020Continual Local Training for Better Initialization of Federated Modelscited by 34
  15. 2022Multi-Level Branched Regularization for Federated Learningcited by 34
  16. 2022On the Convergence of Clustered Federated Learningcited by 31
  17. 2019EM Converges for a Mixture of Many Linear Regressionscited by 27
  18. 2016Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimizationcited by 26
  19. 2018Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regressioncited by 25
  20. 2022Gradient Masked Averaging for Federated Learningcited by 22
  21. 2017Estimating the Coefficients of a Mixture of Two Linear Regressions by Expectation Maximizationcited by 19
  22. 2023Provably Personalized and Robust Federated Learningcited by 11
  23. 2022Global Convergence of Federated Learning for Mixed Regressioncited by 6
  24. 2023EM for Mixture of Linear Regression with Clustered Datacited by 1

Built on by

Not cited yet.