Fast Federated Learning in the Presence of Arbitrary Device Unavailability
arXiv:2106.04159
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.
References in corpus (11)
- Communication-Efficient Learning of Deep Networks from Decentralized Data
- Federated Optimization: Distributed Machine Learning for On-Device Intelligence
- Federated Optimization:Distributed Optimization Beyond the Datacenter
- Asynchronous Federated Optimization
- On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization
- Federated Multi-Task Learning
- Analysis and Implementation of an Asynchronous Optimization Algorithm for the Parameter Server
- A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
- Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning
- Taming Convergence for Asynchronous Stochastic Gradient Descent with Unbounded Delay in Non-Convex Learning
- Asynchronous Distributed Optimization with Stochastic Delays