# On the Convergence of Heterogeneous Federated Learning with Arbitrary Adaptive Online Model Pruning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 49 references that are in the map.
- First posted on arXiv 27 Jan 2022.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [Towards Federated Learning at Scale: System Design](https://mlsanity.com/paper/1902.01046/) (2019)
- [SNIP: Single-shot Network Pruning based on Connection Sensitivity](https://mlsanity.com/paper/1810.02340/) (2018)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Rethinking the Value of Network Pruning](https://mlsanity.com/paper/1810.05270/) (2018)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Adaptive Federated Learning in Resource Constrained Edge Computing Systems](https://mlsanity.com/paper/1804.05271/) (2018)
- [Federated Learning in Mobile Edge Networks: A Comprehensive Survey](https://mlsanity.com/paper/1909.11875/) (2019)
- [HeteroFL: Computation and Communication Efficient Federated Learning for Heterogeneous Clients](https://mlsanity.com/paper/2010.01264/) (2020)
- [SplitFed: When Federated Learning Meets Split Learning](https://mlsanity.com/paper/2004.12088/) (2020)
- [Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning](https://mlsanity.com/paper/1807.06629/) (2018)
- [Dynamic Network Surgery for Efficient DNNs](https://mlsanity.com/paper/1608.04493/) (2016)
- [NISP: Pruning Networks using Neuron Importance Score Propagation](https://mlsanity.com/paper/1711.05908/) (2017)
- [Model Pruning Enables Efficient Federated Learning on Edge Devices](https://mlsanity.com/paper/1909.12326/) (2019)
- [Parameter Efficient Training of Deep Convolutional Neural Networks by Dynamic Sparse Reparameterization](https://mlsanity.com/paper/1902.05967/) (2019)
- [Expanding the Reach of Federated Learning by Reducing Client Resource Requirements](https://mlsanity.com/paper/1812.07210/) (2018)
- [Deep Rewiring: Training very sparse deep networks](https://mlsanity.com/paper/1711.05136/) (2017)
- [Dynamic Model Pruning with Feedback](https://mlsanity.com/paper/2006.07253/) (2020)
- [Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms](https://mlsanity.com/paper/1808.07576/) (2018)
- [One ticket to win them all: generalizing lottery ticket initializations across datasets and optimizers](https://mlsanity.com/paper/1906.02773/) (2019)
- [Communication-efficient distributed SGD with Sketching](https://mlsanity.com/paper/1903.04488/) (2019)
- [Adaptive Gradient Sparsification for Efficient Federated Learning: An Online Learning Approach](https://mlsanity.com/paper/2001.04756/) (2020)

## Built on by (most cited first, 4 of 4)

- [Towards a Better Theoretical Understanding of Independent Subnetwork Training](https://mlsanity.com/paper/2306.16484/) (2023)
- [Tackling Computational Heterogeneity in FL: A Few Theoretical Insights](https://mlsanity.com/paper/2307.06283/) (2023)
- [Adaptive pruning-based Newton's method for distributed learning](https://mlsanity.com/paper/2308.10154/) (2023)
- [subMFL: Compatiple subModel Generation for Federated Learning in Device Heterogenous Environment](https://mlsanity.com/paper/2405.20014/) (2024)

## Abstract (arXiv)

One of the biggest challenges in Federated Learning (FL) is that client devices often have drastically different computation and communication resources for local updates. To this end, recent research efforts have focused on training heterogeneous local models obtained by pruning a shared global model. Despite empirical success, theoretical guarantees on convergence remain an open question. In this paper, we present a unifying framework for heterogeneous FL algorithms with em arbitrary adaptive online model pruning and provide a general convergence analysis. In particular, we prove that under certain sufficient conditions and on both IID and non-IID data, these algorithms converges to a stationary point of standard FL for general smooth cost functions, with a convergence rate of O(frac1√Q). Moreover, we illuminate two key factors impacting convergence: pruning-induced noise and minimum coverage index, advocating a joint design of local pruning masks for efficient training.