# Certifiable Machine Unlearning for Linear Models

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

## Key facts

- Cited by 42 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 17 of its 34 references that are in the map.
- First posted on arXiv 29 Jun 2021.

## Placed in

- LLM safety and security / [Machine unlearning](https://mlsanity.com/safety/machine-unlearning/)

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://mlsanity.com/paper/1911.04933/) (2019)
- [Certified Data Removal from Machine Learning Models](https://mlsanity.com/paper/1911.03030/) (2019)
- [New insights and perspectives on the natural gradient method](https://mlsanity.com/paper/1412.1193/) (2014)
- [Amnesiac Machine Learning](https://mlsanity.com/paper/2010.10981/) (2020)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations](https://mlsanity.com/paper/2003.02960/) (2020)
- [Mixed-Privacy Forgetting in Deep Networks](https://mlsanity.com/paper/2012.13431/) (2020)
- [DeltaGrad: Rapid retraining of machine learning models](https://mlsanity.com/paper/2006.14755/) (2020)
- [Machine Unlearning for Random Forests](https://mlsanity.com/paper/2009.05567/) (2020)
- [Variational Bayesian Unlearning](https://mlsanity.com/paper/2010.12883/) (2020)
- [PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models](https://mlsanity.com/paper/2002.11791/) (2020)

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

- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Forget-Me-Not: Learning to Forget in Text-to-Image Diffusion Models](https://mlsanity.com/paper/2303.17591/) (2023)
- [Fast Yet Effective Machine Unlearning](https://mlsanity.com/paper/2111.08947/) (2021)
- [Can Bad Teaching Induce Forgetting? Unlearning in Deep Networks using an Incompetent Teacher](https://mlsanity.com/paper/2205.08096/) (2022)
- [Zero-Shot Machine Unlearning](https://mlsanity.com/paper/2201.05629/) (2022)
- [The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining](https://mlsanity.com/paper/2203.07320/) (2022)
- [Fast Model Debias with Machine Unlearning](https://mlsanity.com/paper/2310.12560/) (2023)
- [Learning to Unlearn: Instance-wise Unlearning for Pre-trained Classifiers](https://mlsanity.com/paper/2301.11578/) (2023)
- [Unified Gradient-Based Machine Unlearning with Remain Geometry Enhancement](https://mlsanity.com/paper/2409.19732/) (2024)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Machine Unlearning: A Comprehensive Survey](https://mlsanity.com/paper/2405.07406/) (2024)
- [Deep Regression Unlearning](https://mlsanity.com/paper/2210.08196/) (2022)
- [A Review on Machine Unlearning](https://mlsanity.com/paper/2411.11315/) (2024)
- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Continual Forgetting for Pre-trained Vision Models](https://mlsanity.com/paper/2403.11530/) (2024)
- [Decoupled Distillation to Erase: A General Unlearning Method for Any Class-centric Tasks](https://mlsanity.com/paper/2503.23751/) (2025)
- [Deep Unlearning: Fast and Efficient Gradient-free Approach to Class Forgetting](https://mlsanity.com/paper/2312.00761/) (2023)
- [Learning to Unlearn while Retaining: Combating Gradient Conflicts in Machine Unlearning](https://mlsanity.com/paper/2503.06339/) (2025)
- [SIFU: Sequential Informed Federated Unlearning for Efficient and Provable Client Unlearning in Federated Optimization](https://mlsanity.com/paper/2211.11656/) (2022)
- [Attribute-to-Delete: Machine Unlearning via Datamodel Matching](https://mlsanity.com/paper/2410.23232/) (2024)
- [Are We Truly Forgetting? A Critical Re-examination of Machine Unlearning Evaluation Protocols](https://mlsanity.com/paper/2503.06991/) (2025)
- [ERASER: Machine Unlearning in MLaaS via an Inference Serving-Aware Approach](https://mlsanity.com/paper/2311.16136/) (2023)
- [Machine Unlearning Doesn't Do What You Think: Lessons for Generative AI Policy and Research](https://mlsanity.com/paper/2412.06966/) (2024)
- [An Introduction to Machine Unlearning](https://mlsanity.com/paper/2209.00939/) (2022)
- [Ascent Fails to Forget](https://mlsanity.com/paper/2509.26427/) (2025)
- [The Right to be Forgotten in Pruning: Unveil Machine Unlearning on Sparse Models](https://mlsanity.com/paper/2507.18725/) (2025)
- [LegoNet: A Fast and Exact Unlearning Architecture](https://mlsanity.com/paper/2210.16023/) (2022)
- [Recommendation Unlearning via Matrix Correction](https://mlsanity.com/paper/2307.15960/) (2023)
- [Machine Unlearning: its nature, scope, and importance for a "delete culture"](https://mlsanity.com/paper/2305.15242/) (2023)

## Abstract (arXiv)

Machine unlearning is the task of updating machine learning (ML) models after a subset of the training data they were trained on is deleted. Methods for the task are desired to combine effectiveness and efficiency, i.e., they should effectively "unlearn" deleted data, but in a way that does not require excessive computation effort (e.g., a full retraining) for a small amount of deletions. Such a combination is typically achieved by tolerating some amount of approximation in the unlearning. In addition, laws and regulations in the spirit of "the right to be forgotten" have given rise to requirements for certifiability, i.e., the ability to demonstrate that the deleted data has indeed been unlearned by the ML model. In this paper, we present an experimental study of the three state-of-the-art approximate unlearning methods for linear models and demonstrate the trade-offs between efficiency, effectiveness and certifiability offered by each method. In implementing the study, we extend some of the existing works and describe a common ML pipeline to compare and evaluate the unlearning methods on six real-world datasets and a variety of settings. We provide insights into the effect of the quantity and distribution of the deleted data on ML models and the performance of each unlearning method in different settings. We also propose a practical online strategy to determine when the accumulated error from approximate unlearning is large enough to warrant a full retrain of the ML model.