# Machine Unlearning via Algorithmic Stability

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

## Key facts

- Cited by 130 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 13 of its 30 references that are in the map.
- First posted on arXiv 25 Feb 2021.

## Placed in

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

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [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)
- [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)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)

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

- [SalUn: Empowering Machine Unlearning via Gradient-based Weight Saliency in Both Image Classification and Generation](https://mlsanity.com/paper/2310.12508/) (2023)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [MUSE: Machine Unlearning Six-Way Evaluation for Language Models](https://mlsanity.com/paper/2407.06460/) (2024)
- [Rethinking Machine Unlearning for Large Language Models](https://mlsanity.com/paper/2402.08787/) (2024)
- [Model Sparsity Can Simplify Machine Unlearning](https://mlsanity.com/paper/2304.04934/) (2023)
- [Can Bad Teaching Induce Forgetting? Unlearning in Deep Networks using an Incompetent Teacher](https://mlsanity.com/paper/2205.08096/) (2022)
- [On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning](https://mlsanity.com/paper/2110.11891/) (2021)
- [Measuring Forgetting of Memorized Training Examples](https://mlsanity.com/paper/2207.00099/) (2022)
- [SOUL: Unlocking the Power of Second-Order Optimization for LLM Unlearning](https://mlsanity.com/paper/2404.18239/) (2024)
- [Towards LLM Unlearning Resilient to Relearning Attacks: A Sharpness-Aware Minimization Perspective and Beyond](https://mlsanity.com/paper/2502.05374/) (2025)
- [A Comprehensive Survey of Forgetting in Deep Learning Beyond Continual Learning](https://mlsanity.com/paper/2307.09218/) (2023)
- [Forget Unlearning: Towards True Data-Deletion in Machine Learning](https://mlsanity.com/paper/2210.08911/) (2022)
- [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)
- [UnlearnCanvas: Stylized Image Dataset for Enhanced Machine Unlearning Evaluation in Diffusion Models](https://mlsanity.com/paper/2402.11846/) (2024)
- [Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning](https://mlsanity.com/paper/2401.10371/) (2024)
- [Unified Gradient-Based Machine Unlearning with Remain Geometry Enhancement](https://mlsanity.com/paper/2409.19732/) (2024)
- [Challenging Forgets: Unveiling the Worst-Case Forget Sets in Machine Unlearning](https://mlsanity.com/paper/2403.07362/) (2024)
- [Hidden Poison: Machine Unlearning Enables Camouflaged Poisoning Attacks](https://mlsanity.com/paper/2212.10717/) (2022)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Algorithms that Approximate Data Removal: New Results and Limitations](https://mlsanity.com/paper/2209.12269/) (2022)
- [Evaluating Machine Unlearning via Epistemic Uncertainty](https://mlsanity.com/paper/2208.10836/) (2022)
- [Deep Regression Unlearning](https://mlsanity.com/paper/2210.08196/) (2022)
- [A Review on Machine Unlearning](https://mlsanity.com/paper/2411.11315/) (2024)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Unlearning as multi-task optimization: A normalized gradient difference approach with an adaptive learning rate](https://mlsanity.com/paper/2410.22086/) (2024)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [SAFE: Machine Unlearning With Shard Graphs](https://mlsanity.com/paper/2304.13169/) (2023)

## Abstract (arXiv)

We study the problem of machine unlearning and identify a notion of algorithmic stability, Total Variation (TV) stability, which we argue, is suitable for the goal of exact unlearning. For convex risk minimization problems, we design TV-stable algorithms based on noisy Stochastic Gradient Descent (SGD). Our key contribution is the design of corresponding efficient unlearning algorithms, which are based on constructing a (maximal) coupling of Markov chains for the noisy SGD procedure. To understand the trade-offs between accuracy and unlearning efficiency, we give upper and lower bounds on excess empirical and populations risk of TV stable algorithms for convex risk minimization. Our techniques generalize to arbitrary non-convex functions, and our algorithms are differentially private as well.