Connectivity-Aware Semi-Decentralized Federated Learning over Time-Varying D2D Networks

Rohit Parasnis, Seyyedali Hosseinalipour, Yun Wei Chu, Mung Chiang, Christopher G. Brinton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Semi-decentralized federated learning blends the conventional device-to-server (D2S) interaction structure of federated model training with localized device-to-device (D2D) communications. We study this architecture over practical edge networks with multiple D2D clusters modeled as time-varying and directed communication graphs. Our investigation results in an algorithm that controls the fundamental trade-off between (a) the rate of convergence of the model training process towards the global optimizer, and (b) the number of D2S transmissions required for global aggregation. Specifically, in our semi-decentralized methodology, D2D consensus updates are injected into the federated averaging framework based on column-stochastic weight matrices that encapsulate the connectivity within the clusters. To arrive at our algorithm, we show how the expected optimality gap in the current global model depends on the greatest two singular values of the weighted adjacency matrices (and hence on the densities) of the D2D clusters. We then derive tight bounds on these singular values in terms of the node degrees of the D2D clusters, and we use the resulting expressions to design a threshold on the number of clients required to participate in any given global aggregation round so as to ensure a desired convergence rate. Simulations performed on real-world datasets reveal that our connectivity-aware algorithm reduces the total communication cost required to reach a target accuracy significantly compared with baselines depending on the connectivity structure and the learning task.

Original languageEnglish (US)
Title of host publicationMobiHoc 2023 - Proceedings of the 2023 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing
PublisherAssociation for Computing Machinery
Pages31-40
Number of pages10
ISBN (Electronic)9781450399265
DOIs
StatePublished - Oct 23 2023
Externally publishedYes
Event2023 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, MobiHoc 2023 - Washington, United States
Duration: Oct 23 2023Oct 26 2023

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)

Conference

Conference2023 International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, MobiHoc 2023
Country/TerritoryUnited States
CityWashington
Period10/23/2310/26/23

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Computer Networks and Communications
  • Software

Keywords

  • connectivity
  • federated learning
  • semi-decentralized

Fingerprint

Dive into the research topics of 'Connectivity-Aware Semi-Decentralized Federated Learning over Time-Varying D2D Networks'. Together they form a unique fingerprint.

Cite this