# Heterogeneous Federated Learning on a Graph

arXiv: https://arxiv.org/abs/2209.08737 · HTML: https://mlsanity.com/paper/2209.08737/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 69 references that are in the map.
- First posted on arXiv 19 Sep 2022.

## Builds on (most cited first, 24 of 24)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Federated Multi-Task Learning](https://mlsanity.com/paper/1705.10467/) (2017)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Three Approaches for Personalization with Applications to Federated Learning](https://mlsanity.com/paper/2002.10619/) (2020)
- [Improving Federated Learning Personalization via Model Agnostic Meta Learning](https://mlsanity.com/paper/1909.12488/) (2019)
- [Federated Evaluation of On-device Personalization](https://mlsanity.com/paper/1910.10252/) (2019)
- [Survey of Personalization Techniques for Federated Learning](https://mlsanity.com/paper/2003.08673/) (2020)
- [FedHome: Cloud-Edge based Personalized Federated Learning for In-Home Health Monitoring](https://mlsanity.com/paper/2012.07450/) (2020)
- [Mobile Edge Computing: A Survey on Architecture and Computation Offloading](https://mlsanity.com/paper/1702.05309/) (2017)
- [Trend Filtering on Graphs](https://mlsanity.com/paper/1410.7690/) (2014)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Communication-Efficient Accurate Statistical Estimation](https://mlsanity.com/paper/1906.04870/) (2019)
- [Distributed linear regression by averaging](https://mlsanity.com/paper/1810.00412/) (2018)
- [Heterogeneity-aware and communication-efficient distributed statistical inference](https://mlsanity.com/paper/1912.09623/) (2019)
- [Real-time End-to-End Federated Learning: An Automotive Case Study](https://mlsanity.com/paper/2103.11879/) (2021)
- [Prediction models for network-linked data](https://mlsanity.com/paper/1602.01192/) (2016)
- [Fast and Flexible ADMM Algorithms for Trend Filtering](https://mlsanity.com/paper/1406.2082/) (2014)
- [Distributed Machine Learning with Sparse Heterogeneous Data](https://mlsanity.com/paper/1912.01417/) (2019)
- [On Structured Filtering-Clustering: Global Error Bound and Optimal First-Order Algorithms](https://mlsanity.com/paper/1904.07462/) (2019)

## Built on by (most cited first, 2 of 2)

- [Advancements in Federated Learning: Models, Methods, and Privacy](https://mlsanity.com/paper/2302.11466/) (2023)
- [Edge Graph Intelligence: Reciprocally Empowering Edge Networks with Graph Intelligence](https://mlsanity.com/paper/2407.15320/) (2024)

## Abstract (arXiv)

Federated learning, where algorithms are trained across multiple decentralized devices without sharing local data, is increasingly popular in distributed machine learning practice. Typically, a graph structure G exists behind local devices for communication. In this work, we consider parameter estimation in federated learning with data distribution and communication heterogeneity, as well as limited computational capacity of local devices. We encode the distribution heterogeneity by parametrizing distributions on local devices with a set of distinct p-dimensional vectors. We then propose to jointly estimate parameters of all devices under the M-estimation framework with the fused Lasso regularization, encouraging an equal estimate of parameters on connected devices in G. We provide a general result for our estimator depending on G, which can be further calibrated to obtain convergence rates for various specific problem setups. Surprisingly, our estimator attains the optimal rate under certain graph fidelity condition on G, as if we could aggregate all samples sharing the same distribution. If the graph fidelity condition is not met, we propose an edge selection procedure via multiple testing to ensure the optimality. To ease the burden of local computation, a decentralized stochastic version of ADMM is provided, with convergence rate O(T-1log T) where T denotes the number of iterations. We highlight that, our algorithm transmits only parameters along edges of G at each iteration, without requiring a central machine, which preserves privacy. We further extend it to the case where devices are randomly inaccessible during the training process, with a similar algorithmic convergence guarantee. The computational and statistical efficiency of our method is evidenced by simulation experiments and the 2020 US presidential election data set.