# Tight Bounds for Machine Unlearning via Differential Privacy

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 16 of its 22 references that are in the map.
- First posted on arXiv 2 Sep 2023.

## Placed in

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

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

- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [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)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [When Machine Unlearning Jeopardizes Privacy](https://mlsanity.com/paper/2005.02205/) (2020)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Updates-Leak: Data Set Inference and Reconstruction Attacks in Online Learning](https://mlsanity.com/paper/1904.01067/) (2019)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Formalizing Data Deletion in the Context of the Right to be Forgotten](https://mlsanity.com/paper/2002.10635/) (2020)
- [Algorithms that Approximate Data Removal: New Results and Limitations](https://mlsanity.com/paper/2209.12269/) (2022)
- [Deletion Inference, Reconstruction, and Compliance in Machine (Un)Learning](https://mlsanity.com/paper/2202.03460/) (2022)

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

- [In-Context Unlearning: Language Models as Few Shot Unlearners](https://mlsanity.com/paper/2310.07579/) (2023)
- [Machine Unlearning of Pre-trained Large Language Models](https://mlsanity.com/paper/2402.15159/) (2024)
- [Position: LLM Unlearning Benchmarks are Weak Measures of Progress](https://mlsanity.com/paper/2410.02879/) (2024)
- [Machine Unlearning Fails to Remove Data Poisoning Attacks](https://mlsanity.com/paper/2406.17216/) (2024)
- [The Utility and Complexity of in- and out-of-Distribution Machine Unlearning](https://mlsanity.com/paper/2412.09119/) (2024)
- [Gone but Not Forgotten: Improved Benchmarks for Machine Unlearning](https://mlsanity.com/paper/2405.19211/) (2024)
- [When to Forget? Complexity Trade-offs in Machine Unlearning](https://mlsanity.com/paper/2502.17323/) (2025)
- [Certification for Differentially Private Prediction in Gradient-Based Training](https://mlsanity.com/paper/2406.13433/) (2024)
- [Position: Bridge the Gaps between Machine Unlearning and AI Regulation](https://mlsanity.com/paper/2502.12430/) (2025)
- [SEPS: A Separability Measure for Robust Unlearning in LLMs](https://mlsanity.com/paper/2505.14832/) (2025)
- [Exploring Nonlinear Pathway in Parameter Space for Machine Unlearning](https://mlsanity.com/paper/2505.10859/) (2025)
- [Fully Decentralized Certified Unlearning](https://mlsanity.com/paper/2512.08443/) (2025)
- [Less Noise, Same Certificate: Retain Sensitivity for Unlearning](https://mlsanity.com/paper/2603.03172/) (2026)
- [Hierarchical Dual-Strategy Unlearning for Biomedical and Healthcare Intelligence Using Imperfect and Privacy-Sensitive Medical Data](https://mlsanity.com/paper/2511.19498/) (2025)
- [Variance-Reduced (varepsilon,δ)-Unlearning using Forget Set Gradients](https://mlsanity.com/paper/2602.14938/) (2026)
- [Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses](https://mlsanity.com/paper/2606.01527/) (2026)
- [Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots](https://mlsanity.com/paper/2608.27782/) (2026)
- [Minimax Gaussian Mechanisms for Continual Machine Unlearning](https://mlsanity.com/paper/2610.11628/) (2026)

## Abstract (arXiv)

We consider the formulation of "machine unlearning" of Sekhari, Acharya, Kamath, and Suresh (NeurIPS 2021), which formalizes the so-called "right to be forgotten" by requiring that a trained model, upon request, should be able to "unlearn" a number of points from the training data, as if they had never been included in the first place. Sekhari et al. established some positive and negative results about the number of data points that can be successfully unlearnt by a trained model without impacting the model's accuracy (the "deletion capacity"), showing that machine unlearning could be achieved by using differentially private (DP) algorithms. However, their results left open a gap between upper and lower bounds on the deletion capacity of these algorithms: our work fully closes this gap, obtaining tight bounds on the deletion capacity achievable by DP-based machine unlearning algorithms.