Throughput-Optimal Topology Design for Cross-Silo Federated Learning

Abstract

Federated learning usually employs a client-server architecture where an orchestrator iteratively aggregates model updates from remote clients and pushes them back a refined model. This approach may be inefficient in cross-silo settings, as close-by data silos with high-speed access links may exchange information faster than with the orchestrator, and the orchestrator may become a communication bottleneck. In this paper we define the problem of topology design for cross-silo federated learning using the theory of max-plus linear systems to compute the system throughput---number of communication rounds per time unit. We also propose practical algorithms that, under the knowledge of measurable network characteristics, find a topology with the largest throughput or with provable throughput guarantees. In realistic Internet networks with 10 Gbps access links for silos, our algorithms speed up training by a factor 9 and 1.5 in comparison to the master-slave architecture and to state-of-the-art MATCHA, respectively. Speedups are even larger with slower access links.

arXiv comment41 pages, NeurIPS 2020

References in corpus (19)

• Deep Learning with Differential Privacy
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• LEAF: A Benchmark for Federated Settings
• Optimal algorithms for smooth and strongly convex distributed optimization in networks
• Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication
• D${}^2$: Decentralized Training over Decentralized Data
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms
• Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
• Peer-to-peer Federated Learning on Graphs
• Stochastic Gradient Push for Distributed Deep Learning
• ExtraPush for convex smooth decentralized optimization over directed networks
• SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentum
• MATCHA: Speeding Up Decentralized SGD via Matching Decomposition Sampling
• Communication-Efficient Local Decentralized SGD Methods
• Decentralized gradient methods: does topology matter?

Cited by in corpus (4)

• Decentralized Federated Learning: Fundamentals, State of the Art, Frameworks, Trends, and Challenges
• Topology-aware Federated Learning in Edge Computing: A Comprehensive Survey
• Federated Learning Survey: A Multi-Level Taxonomy of Aggregation Techniques, Experimental Insights, and Future Frontiers
• Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data