Device Sampling for Heterogeneous Federated Learning: Theory, Algorithms, and Implementation
Authors:
- 10 May 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-10
Abstract
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.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Adaptive Federated Learning in Resource Constrained Edge Computing SystemsIEEE Journal on Selected Areas in Communications, 2019
- Deep Learning for IoT Big Data and Streaming Analytics: A SurveyIEEE Communications Surveys & Tutorials, 2018
- When Edge Meets Learning: Adaptive Control for Resource-Constrained Distributed Machine Learning2018
- LEGIoT: A Lightweight Edge Gateway for the Internet of ThingsFuture Generation Computer Systems, 2018
- Fog and IoT: An Overview of Research OpportunitiesIEEE Internet of Things Journal, 2016
- A Survey on Transfer LearningIEEE Transactions on Knowledge and Data Engineering, 2009
- On Divergences and Informations in Statistics and Information TheoryIEEE Transactions on Information Theory, 2006
- Fractional programming: the sum-of-ratios caseOptimization Methods and Software, 2003
- A branch-and-bound algorithm for maximizing the sum of several linear ratiosJournal of Global Optimization, 2002
- New trends in exact algorithms for the 0–1 knapsack problemEuropean Journal of Operational Research, 2000