# Device Sampling for Heterogeneous Federated Learning: Theory, Algorithms, and Implementation

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 49 references that are in the map.
- First posted on arXiv 4 Jan 2021.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (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)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [FedMD: Heterogenous Federated Learning via Model Distillation](https://mlsanity.com/paper/1910.03581/) (2019)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Robust and Communication-Efficient Federated Learning from Non-IID Data](https://mlsanity.com/paper/1903.02891/) (2019)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Energy Efficient Federated Learning Over Wireless Communication Networks](https://mlsanity.com/paper/1911.02417/) (2019)
- [Scheduling Policies for Federated Learning in Wireless Networks](https://mlsanity.com/paper/1908.06287/) (2019)
- [Federated Learning for Wireless Communications: Motivation, Opportunities and Challenges](https://mlsanity.com/paper/1908.06847/) (2019)
- [Fairness risk measures](https://mlsanity.com/paper/1901.08665/) (2019)
- [Scheduling for Cellular Federated Edge Learning with Importance and Channel Awareness](https://mlsanity.com/paper/2004.00490/) (2020)
- [Fast-Convergent Federated Learning](https://mlsanity.com/paper/2007.13137/) (2020)
- [Deep Learning for IoT Big Data and Streaming Analytics: A Survey](https://mlsanity.com/paper/1712.04301/) (2017)
- [Multi-Armed Bandit Based Client Scheduling for Federated Learning](https://mlsanity.com/paper/2007.02315/) (2020)
- [Device Scheduling with Fast Convergence for Wireless Federated Learning](https://mlsanity.com/paper/1911.00856/) (2019)
- [Multi-Stage Hybrid Federated Learning over Large-Scale D2D-Enabled Fog Networks](https://mlsanity.com/paper/2007.09511/) (2020)
- [Network-Aware Optimization of Distributed Learning for Fog Computing](https://mlsanity.com/paper/2004.08488/) (2020)
- [Dynamic Sampling and Selective Masking for Communication-Efficient Federated Learning](https://mlsanity.com/paper/2003.09603/) (2020)
- [Secure Federated Transfer Learning](https://mlsanity.com/paper/1812.03337/) (2018)
- [A Fast Graph Neural Network-Based Method for Winner Determination in Multi-Unit Combinatorial Auctions](https://mlsanity.com/paper/2009.13697/) (2020)
- [Joint Optimization of Signal Design and Resource Allocation in Wireless D2D Edge Computing](https://mlsanity.com/paper/2002.11850/) (2020)

## Built on by (most cited first, 30 of 40)

- [The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining](https://mlsanity.com/paper/2203.07320/) (2022)
- [Decentralized Federated Learning: A Survey and Perspective](https://mlsanity.com/paper/2306.01603/) (2023)
- [Tackling System and Statistical Heterogeneity for Federated Learning with Adaptive Client Sampling](https://mlsanity.com/paper/2112.11256/) (2021)
- [Semi-Decentralized Federated Learning with Cooperative D2D Local Model Aggregations](https://mlsanity.com/paper/2103.10481/) (2021)
- [Automated Federated Pipeline for Parameter-Efficient Fine-Tuning of Large Language Models](https://mlsanity.com/paper/2404.06448/) (2024)
- [FwdLLM: Efficient FedLLM using Forward Gradient](https://mlsanity.com/paper/2308.13894/) (2023)
- [FedAdapter: Efficient Federated Learning for Modern NLP](https://mlsanity.com/paper/2205.10162/) (2022)
- [Green Edge AI: A Contemporary Survey](https://mlsanity.com/paper/2312.00333/) (2023)
- [Topology-aware Federated Learning in Edge Computing: A Comprehensive Survey](https://mlsanity.com/paper/2302.02573/) (2023)
- [UAV-assisted Online Machine Learning over Multi-Tiered Networks: A Hierarchical Nested Personalized Federated Learning Approach](https://mlsanity.com/paper/2106.15734/) (2021)
- [SplitGP: Achieving Both Generalization and Personalization in Federated Learning](https://mlsanity.com/paper/2212.08343/) (2022)
- [Parallel Successive Learning for Dynamic Distributed Model Training over Heterogeneous Wireless Networks](https://mlsanity.com/paper/2202.02947/) (2022)
- [Federated Few-Shot Learning for Mobile NLP](https://mlsanity.com/paper/2212.05974/) (2022)
- [Enabling Long-Term Cooperation in Cross-Silo Federated Learning: A Repeated Game Perspective](https://mlsanity.com/paper/2106.11814/) (2021)
- [Training Mixed-Domain Translation Models via Federated Learning](https://mlsanity.com/paper/2205.01557/) (2022)
- [Advances in Robust Federated Learning: A Survey with Heterogeneity Considerations](https://mlsanity.com/paper/2405.09839/) (2024)
- [A Survey on Participant Selection for Federated Learning in Mobile Networks](https://mlsanity.com/paper/2207.03681/) (2022)
- [Multi-Edge Server-Assisted Dynamic Federated Learning with an Optimized Floating Aggregation Point](https://mlsanity.com/paper/2203.13950/) (2022)
- [AnycostFL: Efficient On-Demand Federated Learning over Heterogeneous Edge Devices](https://mlsanity.com/paper/2301.03062/) (2023)
- [GA-DRL: Graph Neural Network-Augmented Deep Reinforcement Learning for DAG Task Scheduling over Dynamic Vehicular Clouds](https://mlsanity.com/paper/2307.00777/) (2023)
- [Privacy-Preserving Graph Machine Learning from Data to Computation: A Survey](https://mlsanity.com/paper/2307.04338/) (2023)
- [Delay-Aware Hierarchical Federated Learning](https://mlsanity.com/paper/2303.12414/) (2023)
- [Adaptive Heterogeneous Client Sampling for Federated Learning over Wireless Networks](https://mlsanity.com/paper/2404.13804/) (2024)
- [Multi-Source to Multi-Target Decentralized Federated Domain Adaptation](https://mlsanity.com/paper/2304.12422/) (2023)
- [Communication-Efficient Federated Learning for Neural Machine Translation](https://mlsanity.com/paper/2112.06135/) (2021)
- [Embedding Alignment for Unsupervised Federated Learning via Smart Data Exchange](https://mlsanity.com/paper/2208.02856/) (2022)
- [Boost Decentralized Federated Learning in Vehicular Networks by Diversifying Data Sources](https://mlsanity.com/paper/2209.01750/) (2022)
- [Towards Practical Few-shot Federated NLP](https://mlsanity.com/paper/2212.00192/) (2022)
- [Truthful Incentive Mechanism for Federated Learning with Crowdsourced Data Labeling](https://mlsanity.com/paper/2302.00106/) (2023)
- [Trustworthy Federated Learning: A Survey](https://mlsanity.com/paper/2305.11537/) (2023)

## Abstract (arXiv)

The conventional federated learning (FedL) architecture distributes machine learning (ML) across worker devices by having them train local models that are periodically aggregated by a server. FedL ignores two important characteristics of contemporary wireless networks, however: (i) the network may contain heterogeneous communication/computation resources, while (ii) there may be significant overlaps in devices' local data distributions. In this work, we develop a novel optimization methodology that jointly accounts for these factors via intelligent device sampling complemented by device-to-device (D2D) offloading. Our optimization aims to select the best combination of sampled nodes and data offloading configuration to maximize FedL training accuracy subject to realistic constraints on the network topology and device capabilities. Theoretical analysis of the D2D offloading subproblem leads to new FedL convergence bounds and an efficient sequential convex optimizer. Using this result, we develop a sampling methodology based on graph convolutional networks (GCNs) which learns the relationship between network attributes, sampled nodes, and resulting offloading that maximizes FedL accuracy. Through evaluation on real-world datasets and network measurements from our IoT testbed, we find that our methodology while sampling less than 5% of all devices outperforms conventional FedL substantially both in terms of trained model accuracy and required resource utilization.