# Fast Federated Learning in the Presence of Arbitrary Device Unavailability

arXiv: https://arxiv.org/abs/2106.04159 · HTML: https://mlsanity.com/paper/2106.04159/

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 59 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 30 of 33)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [Federated Multi-Task Learning](https://mlsanity.com/paper/1705.10467/) (2017)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Robust and Communication-Efficient Federated Learning from Non-IID Data](https://mlsanity.com/paper/1903.02891/) (2019)
- [Lower Bounds for Non-Convex Stochastic Optimization](https://mlsanity.com/paper/1912.02365/) (2019)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Asynchronous Federated Optimization](https://mlsanity.com/paper/1903.03934/) (2019)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Federated Optimization:Distributed Optimization Beyond the Datacenter](https://mlsanity.com/paper/1511.03575/) (2015)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations](https://mlsanity.com/paper/1906.02367/) (2019)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization](https://mlsanity.com/paper/1506.08272/) (2015)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [MARINA: Faster Non-Convex Distributed Learning with Compression](https://mlsanity.com/paper/2102.07845/) (2021)
- [Towards Flexible Device Participation in Federated Learning](https://mlsanity.com/paper/2006.06954/) (2020)
- [Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneity](https://mlsanity.com/paper/2012.14453/) (2020)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees](https://mlsanity.com/paper/2006.14591/) (2020)
- [Semi-Cyclic Stochastic Gradient Descent](https://mlsanity.com/paper/1904.10120/) (2019)
- [An Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization](https://mlsanity.com/paper/1505.04824/) (2015)
- [Accelerated Methods for Non-Convex Optimization](https://mlsanity.com/paper/1611.00756/) (2016)
- [Distributed Non-Convex Optimization with Sublinear Speedup under Intermittent Client Availability](https://mlsanity.com/paper/2002.07399/) (2020)

## Built on by (most cited first, 30 of 72)

- [Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning](https://mlsanity.com/paper/2206.08307/) (2022)
- [FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learning](https://mlsanity.com/paper/2207.14130/) (2022)
- [FedLab: A Flexible Federated Learning Framework](https://mlsanity.com/paper/2107.11621/) (2021)
- [A Unified Analysis of Federated Learning with Arbitrary Client Participation](https://mlsanity.com/paper/2205.13648/) (2022)
- [Anarchic Federated Learning](https://mlsanity.com/paper/2108.09875/) (2021)
- [Federated Minimax Optimization: Improved Convergence Analyses and Algorithms](https://mlsanity.com/paper/2203.04850/) (2022)
- [HSplitLoRA: A Heterogeneous Split Parameter-Efficient Fine-Tuning Framework for Large Language Models](https://mlsanity.com/paper/2505.02795/) (2025)
- [Communication-Efficient Device Scheduling for Federated Learning Using Stochastic Optimization](https://mlsanity.com/paper/2201.07912/) (2022)
- [GradMA: A Gradient-Memory-based Accelerated Federated Learning with Alleviated Catastrophic Forgetting](https://mlsanity.com/paper/2302.14307/) (2023)
- [A General Theory for Federated Optimization with Asynchronous and Heterogeneous Clients Updates](https://mlsanity.com/paper/2206.10189/) (2022)
- [Semi-Decentralized Federated Learning with Collaborative Relaying](https://mlsanity.com/paper/2205.10998/) (2022)
- [AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms](https://mlsanity.com/paper/2310.20452/) (2023)
- [On the Role of Server Momentum in Federated Learning](https://mlsanity.com/paper/2312.12670/) (2023)
- [Accelerating Hybrid Federated Learning Convergence under Partial Participation](https://mlsanity.com/paper/2304.05397/) (2023)
- [Anchor Sampling for Federated Learning with Partial Client Participation](https://mlsanity.com/paper/2206.05891/) (2022)
- [Federated Learning with Regularized Client Participation](https://mlsanity.com/paper/2302.03662/) (2023)
- [Towards Federated RLHF with Aggregated Client Preference for LLMs](https://mlsanity.com/paper/2407.03038/) (2024)
- [Taming Fat-Tailed ("Heavier-Tailed'' with Potentially Infinite Variance) Noise in Federated Learning](https://mlsanity.com/paper/2210.00690/) (2022)
- [FedGS: Federated Graph-based Sampling with Arbitrary Client Availability](https://mlsanity.com/paper/2211.13975/) (2022)
- [MimiC: Combating Client Dropouts in Federated Learning by Mimicking Central Updates](https://mlsanity.com/paper/2306.12212/) (2023)
- [Over-the-Air Federated Learning and Optimization](https://mlsanity.com/paper/2310.10089/) (2023)
- [Accelerating Heterogeneous Federated Learning with Closed-form Classifiers](https://mlsanity.com/paper/2406.01116/) (2024)
- [Decentralized Event-Triggered Federated Learning with Heterogeneous Communication Thresholds](https://mlsanity.com/paper/2204.03726/) (2022)
- [Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability](https://mlsanity.com/paper/2409.17446/) (2024)
- [From Deterioration to Acceleration: A Calibration Approach to Rehabilitating Step Asynchronism in Federated Optimization](https://mlsanity.com/paper/2112.09355/) (2021)
- [Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis](https://mlsanity.com/paper/2410.23131/) (2024)
- [FedMuon: Federated Learning with Bias-corrected LMO-based Optimization](https://mlsanity.com/paper/2509.26337/) (2025)
- [Achieving Linear Speedup in Asynchronous Federated Learning with Heterogeneous Clients](https://mlsanity.com/paper/2402.11198/) (2024)
- [Towards Bias Correction of FedAvg over Nonuniform and Time-Varying Communications](https://mlsanity.com/paper/2306.00280/) (2023)
- [Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable](https://mlsanity.com/paper/2503.20117/) (2025)

## Abstract (arXiv)

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.