# Coded Machine Unlearning

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

## Key facts

- Cited by 35 papers in the map (data through 7 Oct 2026).
- First posted on arXiv 31 Dec 2020.

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

- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Machine Unlearning of Features and Labels](https://mlsanity.com/paper/2108.11577/) (2021)
- [Fast Yet Effective Machine Unlearning](https://mlsanity.com/paper/2111.08947/) (2021)
- [Towards Adversarial Evaluations for Inexact Machine Unlearning](https://mlsanity.com/paper/2201.06640/) (2022)
- [Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy](https://mlsanity.com/paper/2403.01218/) (2024)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2305.06360/) (2023)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Evaluating Machine Unlearning via Epistemic Uncertainty](https://mlsanity.com/paper/2208.10836/) (2022)
- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2406.16257/) (2024)
- [Efficiently Forgetting What You Have Learned in Graph Representation Learning via Projection](https://mlsanity.com/paper/2302.08990/) (2023)
- [To Be Forgotten or To Be Fair: Unveiling Fairness Implications of Machine Unlearning Methods](https://mlsanity.com/paper/2302.03350/) (2023)
- [An Introduction to Machine Unlearning](https://mlsanity.com/paper/2209.00939/) (2022)
- [An Information Theoretic Evaluation Metric For Strong Unlearning](https://mlsanity.com/paper/2405.17878/) (2024)
- [Towards Reliable Forgetting: A Survey on Machine Unlearning Verification](https://mlsanity.com/paper/2506.15115/) (2025)
- [Machine Unlearning: its nature, scope, and importance for a "delete culture"](https://mlsanity.com/paper/2305.15242/) (2023)
- [Attack and Reset for Unlearning: Exploiting Adversarial Noise toward Machine Unlearning through Parameter Re-initialization](https://mlsanity.com/paper/2401.08998/) (2024)
- [SEPS: A Separability Measure for Robust Unlearning in LLMs](https://mlsanity.com/paper/2505.14832/) (2025)
- [Machine Unlearning Method Based On Projection Residual](https://mlsanity.com/paper/2209.15276/) (2022)
- [How to Forget Clients in Federated Online Learning to Rank?](https://mlsanity.com/paper/2401.13410/) (2024)
- [Unlearning Personal Data from a Single Image](https://mlsanity.com/paper/2407.12069/) (2024)
- [Group-robust Machine Unlearning](https://mlsanity.com/paper/2503.09330/) (2025)
- [Certified Data Removal in Sum-Product Networks](https://mlsanity.com/paper/2210.01451/) (2022)
- ["Forgetting" in Machine Learning and Beyond: A Survey](https://mlsanity.com/paper/2405.20620/) (2024)
- [Sharpness-Aware Parameter Selection for Machine Unlearning](https://mlsanity.com/paper/2504.06398/) (2025)
- [Demystifying Foreground-Background Memorization in Diffusion Models](https://mlsanity.com/paper/2508.12148/) (2025)
- [Inference-time Unlearning Using Conformal Prediction](https://mlsanity.com/paper/2602.03787/) (2026)
- [Erase at the Core: Representation Unlearning for Machine Unlearning](https://mlsanity.com/paper/2602.05375/) (2026)
- [An Investigation on Learning, Polluting, and Unlearning the Spam Emails for Lifelong Learning](https://mlsanity.com/paper/2111.14609/) (2021)

## Abstract (arXiv)

There are applications that may require removing the trace of a sample from the system, e.g., a user requests their data to be deleted, or corrupted data is discovered. Simply removing a sample from storage units does not necessarily remove its entire trace since downstream machine learning models may store some information about the samples used to train them. A sample can be perfectly unlearned if we retrain all models that used it from scratch with that sample removed from their training dataset. When multiple such unlearning requests are expected to be served, unlearning by retraining becomes prohibitively expensive. Ensemble learning enables the training data to be split into smaller disjoint shards that are assigned to non-communicating weak learners. Each shard is used to produce a weak model. These models are then aggregated to produce the final central model. This setup introduces an inherent trade-off between performance and unlearning cost, as reducing the shard size reduces the unlearning cost but may cause degradation in performance. In this paper, we propose a coded learning protocol where we utilize linear encoders to encode the training data into shards prior to the learning phase. We also present the corresponding unlearning protocol and show that it satisfies the perfect unlearning criterion. Our experimental results show that the proposed coded machine unlearning provides a better performance versus unlearning cost trade-off compared to the uncoded baseline.