# Communication Efficient and Provable Federated Unlearning

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Placed in Federated unlearning and poisoning, one of 12 directions in LLM safety and security.
- Builds on 17 of its 30 references that are in the map.
- First posted on arXiv 19 Jan 2024.

## Placed in

- LLM safety and security / [Federated unlearning and poisoning](https://mlsanity.com/safety/federated-unlearning-and-poisoning/)

## Builds on (most cited first, 17 of 17)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification](https://mlsanity.com/paper/1909.06335/) (2019)
- [LEAF: A Benchmark for Federated Settings](https://mlsanity.com/paper/1812.01097/) (2018)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Flower: A Friendly Federated Learning Research Framework](https://mlsanity.com/paper/2007.14390/) (2020)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Unrolling SGD: Understanding Factors Influencing Machine Unlearning](https://mlsanity.com/paper/2109.13398/) (2021)
- [Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning](https://mlsanity.com/paper/1812.00535/) (2018)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining](https://mlsanity.com/paper/2203.07320/) (2022)

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

- [Towards Lifecycle Unlearning Commitment Management: Measuring Sample-level Unlearning Completeness](https://mlsanity.com/paper/2506.06112/) (2025)
- [Privacy-Preserving Federated Unlearning with Certified Client Removal](https://mlsanity.com/paper/2404.09724/) (2024)
- [Understanding Fine-tuning in Approximate Unlearning: A Theoretical Perspective](https://mlsanity.com/paper/2410.03833/) (2024)
- [Poisoning Attacks and Defenses to Federated Unlearning](https://mlsanity.com/paper/2501.17396/) (2025)
- [Towards Reasoning-Preserving Unlearning in Multimodal Large Language Models](https://mlsanity.com/paper/2512.17911/) (2025)
- [Exact Federated Continual Unlearning for Ridge Heads on Frozen Foundation Models](https://mlsanity.com/paper/2603.12977/) (2026)
- [Exploring Incremental Unlearning: Techniques, Challenges, and Future Directions](https://mlsanity.com/paper/2502.16708/) (2025)
- [Certified Unlearning in Decentralized Federated Learning](https://mlsanity.com/paper/2601.06436/) (2026)
- [Parallel Unlearning in Inherited Model Networks](https://mlsanity.com/paper/2408.08493/) (2024)
- [Fully Decentralized Certified Unlearning](https://mlsanity.com/paper/2512.08443/) (2025)
- [Certifying the Right to Be Forgotten: Primal-Dual Optimization for Sample and Label Unlearning in Vertical Federated Learning](https://mlsanity.com/paper/2512.23171/) (2025)
- [A Survey on Federated Unlearning: Challenges and Opportunities](https://mlsanity.com/paper/2403.02437/) (2024)
- [Streamlined Federated Unlearning: Unite as One to Be Highly Efficient](https://mlsanity.com/paper/2412.00126/) (2024)
- [FedShard: Federated Unlearning with Efficiency Fairness and Performance Fairness](https://mlsanity.com/paper/2508.09866/) (2025)
- [FedSGT: Exact Federated Unlearning via Sequential Group-based Training](https://mlsanity.com/paper/2511.23393/) (2025)
- [Lethe: Principled Dual-Stream Update for Persistent Knowledge Erasure in Federated Unlearning](https://mlsanity.com/paper/2601.22601/) (2026)
- [Computation and Communication Efficient Federated Unlearning via On-server Gradient Conflict Mitigation and Expression](https://mlsanity.com/paper/2603.13795/) (2026)
- [FedSubMuon: Communication-Efficient Federated LLM Fine-Tuning via Structured Subspace Muon](https://mlsanity.com/paper/2609.06073/) (2026)

## Abstract (arXiv)

We study federated unlearning, a novel problem to eliminate the impact of specific clients or data points on the global model learned via federated learning (FL). This problem is driven by the right to be forgotten and the privacy challenges in FL. We introduce a new framework for exact federated unlearning that meets two essential criteria: textitcommunication efficiency and textitexact unlearning provability. To our knowledge, this is the first work to tackle both aspects coherently. We start by giving a rigorous definition of textitexact federated unlearning, which guarantees that the unlearned model is statistically indistinguishable from the one trained without the deleted data. We then pinpoint the key property that enables fast exact federated unlearning: total variation (TV) stability, which measures the sensitivity of the model parameters to slight changes in the dataset. Leveraging this insight, we develop a TV-stable FL algorithm called textttFATS, which modifies the classical textttunderlineFedunderlineAvg algorithm for underlineTV underlineStability and employs local SGD with periodic averaging to lower the communication round. We also design efficient unlearning algorithms for textttFATS under two settings: client-level and sample-level unlearning. We provide theoretical guarantees for our learning and unlearning algorithms, proving that they achieve exact federated unlearning with reasonable convergence rates for both the original and unlearned models. We empirically validate our framework on 6 benchmark datasets, and show its superiority over state-of-the-art methods in terms of accuracy, communication cost, computation cost, and unlearning efficacy.