Fast Federated Learning in the Presence of Arbitrary Device Unavailability

2021/06/08 by Xinran Gu, Gu, Xinran, Kaixuan Huang +5 · 11 citations
Computer Science · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Mobile Crowdsensing and Crowdsourcing #Optimization and Control (math.OC) #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.2106.04159

arxiv created 2021/06/08 · openalex publication_date 2021/06/08 · arxiv updated 2021/06/09 · openalex created_date 2021/06/22 · openalex updated_date 2026/07/28

Abstract

Federated Learning (FL) coordinates with numerous heterogeneous devices to collaboratively train a shared model while preserving user privacy. Despite its multiple advantages, FL faces new challenges. One challenge arises when devices drop out of the training process beyond the control of the central server. In this case, the convergence of popular FL algorithms such as FedAvg is severely influenced by the straggling devices. To tackle this challenge, we study federated learning algorithms under arbitrary device unavailability and propose an algorithm named Memory-augmented Impatient Federated Averaging (MIFA). Our algorithm efficiently avoids excessive latency induced by inactive devices, and corrects the gradient bias using the memorized latest updates from the devices. We prove that MIFA achieves minimax optimal convergence rates on non-i.i.d. data for both strongly convex and non-convex smooth functions. We also provide an explicit characterization of the improvement over baseline algorithms through a case study, and validate the results by numerical experiments on real-world datasets.

Citations

• Gradient-based learning applied to document recognition
• Federated Optimization:Distributed Optimization Beyond the Datacenter
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• Federated Multi-Task Learning
• Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning
• Advances and Open Problems in Federated Learning
• Learning Multiple Layers of Features from Tiny Images

Cited by

• FedDPC : Handling Data Heterogeneity and Partial Client Participation in Federated Learning
• FedOAED: Federated On-Device Autoencoder Denoiser for Heterogeneous Data under Limited Client Availability
• Dynamic Participation in Federated Learning: Benchmarks and a Knowledge Pool Plugin
• Computation-aware Energy-harvesting Federated Learning: Cyclic Scheduling with Selective Participation
• FedMuon: Federated Learning with Bias-corrected LMO-based Optimization
• Semi-decentralized Federated Time Series Prediction with Client Availability Budgets
• Delayed Momentum Aggregation: Communication-efficient Byzantine-robust Federated Learning with Partial Participation
• Accelerated Training of Federated Learning via Second-Order Methods
• HSplitLoRA: A Heterogeneous Split Parameter-Efficient Fine-Tuning Framework for Large Language Models
• FlexFed: Mitigating Catastrophic Forgetting in Heterogeneous Federated Learning in Pervasive Computing Environments
• Towards Optimal Heterogeneous Client Sampling in Multi-Model Federated Learning
• DG-FedReuse: Proxy-Gradient-Gated Cached-Update Reuse with Matched Sparse Uplink Accounting

Related

• On the Convergence of FedAvg on Non-IID Data
• Fast-Convergent Federated Learning
• FedPrune: Towards Inclusive Federated Learning
• Faster Federated Learning with Decaying Number of Local SGD Steps
• Faster On-Device Training Using New Federated Momentum Algorithm