# The Utility and Complexity of in- and out-of-Distribution Machine Unlearning

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Placed in Machine unlearning, one of 12 directions in LLM safety and security.
- Builds on 27 of its 41 references that are in the map.
- First posted on arXiv 12 Dec 2024.

## Placed in

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

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

- [Machine Unlearning](https://mlsanity.com/paper/1912.03817/) (2019)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [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)
- [Opacus: User-Friendly Differential Privacy Library in PyTorch](https://mlsanity.com/paper/2109.12298/) (2021)
- [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)
- [Amnesiac Machine Learning](https://mlsanity.com/paper/2010.10981/) (2020)
- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [Towards Unbounded Machine Unlearning](https://mlsanity.com/paper/2302.09880/) (2023)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Fast Machine Unlearning Without Retraining Through Selective Synaptic Dampening](https://mlsanity.com/paper/2308.07707/) (2023)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Mixed-Privacy Forgetting in Deep Networks](https://mlsanity.com/paper/2012.13431/) (2020)
- [Mean estimation and regression under heavy-tailed distributions--a survey](https://mlsanity.com/paper/1906.04280/) (2019)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Towards Adversarial Evaluations for Inexact Machine Unlearning](https://mlsanity.com/paper/2201.06640/) (2022)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Forget Unlearning: Towards True Data-Deletion in Machine Learning](https://mlsanity.com/paper/2210.08911/) (2022)
- [Hard to Forget: Poisoning Attacks on Certified Machine Unlearning](https://mlsanity.com/paper/2109.08266/) (2021)
- [Machine Unlearning Fails to Remove Data Poisoning Attacks](https://mlsanity.com/paper/2406.17216/) (2024)
- [Global Optimality in Low-rank Matrix Optimization](https://mlsanity.com/paper/1702.07945/) (2017)
- [Corrective Machine Unlearning](https://mlsanity.com/paper/2402.14015/) (2024)
- [Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity](https://mlsanity.com/paper/2309.13591/) (2023)
- [Tight Bounds for Machine Unlearning via Differential Privacy](https://mlsanity.com/paper/2309.00886/) (2023)

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

- [Certified Unlearning for Neural Networks](https://mlsanity.com/paper/2506.06985/) (2025)
- [When to Forget? Complexity Trade-offs in Machine Unlearning](https://mlsanity.com/paper/2502.17323/) (2025)
- [Gaussian Certified Unlearning in High Dimensions: A Hypothesis Testing Approach](https://mlsanity.com/paper/2510.13094/) (2025)
- [Distributional Machine Unlearning via Selective Data Removal](https://mlsanity.com/paper/2507.15112/) (2025)
- [The Unseen Threat: Residual Knowledge in Machine Unlearning under Perturbed Samples](https://mlsanity.com/paper/2601.22359/) (2026)
- [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)
- [Statistical Unlearning of Distributions: A Hypothesis Testing Approach](https://mlsanity.com/paper/2605.16645/) (2026)
- [Exact Unlearning in Reinforcement Learning](https://mlsanity.com/paper/2606.04182/) (2026)
- [Auditing of Unlearning Algorithms](https://mlsanity.com/paper/2607.05898/) (2026)
- [Conformal Unlearning: A New Paradigm for Unlearning in Conformal Predictors](https://mlsanity.com/paper/2508.03245/) (2025)
- [Descend or Rewind? Stochastic Gradient Descent Unlearning](https://mlsanity.com/paper/2511.15983/) (2025)
- [Delete and Retain: Efficient Unlearning for Document Classification](https://mlsanity.com/paper/2512.13711/) (2025)
- [Sequential Subspace Noise Injection Prevents Accuracy Collapse in Certified Unlearning](https://mlsanity.com/paper/2601.05134/) (2026)
- [A Robust Certified Machine Unlearning Method Under Distribution Shift](https://mlsanity.com/paper/2601.06967/) (2026)
- [Variance-Reduced (varepsilon,δ)-Unlearning using Forget Set Gradients](https://mlsanity.com/paper/2602.14938/) (2026)
- [SoK: Unlearnability and Unlearning for Model Dememorization](https://mlsanity.com/paper/2605.11592/) (2026)
- [Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses](https://mlsanity.com/paper/2606.01527/) (2026)
- [How Hard Can It Be? Hardness-Aware Multi-Objective Unlearning](https://mlsanity.com/paper/2606.02119/) (2026)
- [InstantForget: Update-Free Backdoor Unlearning with Inference-Time Feature Reset](https://mlsanity.com/paper/2606.15730/) (2026)

## Abstract (arXiv)

Machine unlearning, the process of selectively removing data from trained models, is increasingly crucial for addressing privacy concerns and knowledge gaps post-deployment. Despite this importance, existing approaches are often heuristic and lack formal guarantees. In this paper, we analyze the fundamental utility, time, and space complexity trade-offs of approximate unlearning, providing rigorous certification analogous to differential privacy. For in-distribution forget data -- data similar to the retain set -- we show that a surprisingly simple and general procedure, empirical risk minimization with output perturbation, achieves tight unlearning-utility-complexity trade-offs, addressing a previous theoretical gap on the separation from unlearning "for free" via differential privacy, which inherently facilitates the removal of such data. However, such techniques fail with out-of-distribution forget data -- data significantly different from the retain set -- where unlearning time complexity can exceed that of retraining, even for a single sample. To address this, we propose a new robust and noisy gradient descent variant that provably amortizes unlearning time complexity without compromising utility.