# When to Forget? Complexity Trade-offs in Machine Unlearning

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

## Key facts

- Cited by 9 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 42 references that are in the map.
- First posted on arXiv 24 Feb 2025.

## Placed in

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

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [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)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [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)
- [Who's Harry Potter? Approximate Unlearning in LLMs](https://mlsanity.com/paper/2310.02238/) (2023)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [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)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [Handbook of Convergence Theorems for (Stochastic) Gradient Methods](https://mlsanity.com/paper/2301.11235/) (2023)
- [Eight Methods to Evaluate Robust Unlearning in LLMs](https://mlsanity.com/paper/2402.16835/) (2024)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [The rising costs of training frontier AI models](https://mlsanity.com/paper/2405.21015/) (2024)
- [Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy](https://mlsanity.com/paper/2403.01218/) (2024)
- [Forget Unlearning: Towards True Data-Deletion in Machine Learning](https://mlsanity.com/paper/2210.08911/) (2022)
- [The opportunities and risks of large language models in mental health](https://mlsanity.com/paper/2403.14814/) (2024)
- [The Utility and Complexity of in- and out-of-Distribution Machine Unlearning](https://mlsanity.com/paper/2412.09119/) (2024)
- [Data Redaction from Pre-trained GANs](https://mlsanity.com/paper/2206.14389/) (2022)
- [SIFU: Sequential Informed Federated Unlearning for Efficient and Provable Client Unlearning in Federated Optimization](https://mlsanity.com/paper/2211.11656/) (2022)
- [Tight Bounds for Machine Unlearning via Differential Privacy](https://mlsanity.com/paper/2309.00886/) (2023)
- [Attribute-to-Delete: Machine Unlearning via Datamodel Matching](https://mlsanity.com/paper/2410.23232/) (2024)
- [Dataset Growth in Medical Image Analysis Research](https://mlsanity.com/paper/1908.07765/) (2019)
- [From Adaptive Query Release to Machine Unlearning](https://mlsanity.com/paper/2307.11228/) (2023)
- [Privacy Policies and Consent Management Platforms: Growth and Users' Interactions over Time](https://mlsanity.com/paper/2402.18321/) (2024)

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

- [Distributional Machine Unlearning via Selective Data Removal](https://mlsanity.com/paper/2507.15112/) (2025)
- [Fully Decentralized Certified Unlearning](https://mlsanity.com/paper/2512.08443/) (2025)
- [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)
- [Mo' Memory, Mo' Problems: Stream-Native Machine Unlearning](https://mlsanity.com/paper/2508.10193/) (2025)
- [Variance-Reduced (varepsilon,δ)-Unlearning using Forget Set Gradients](https://mlsanity.com/paper/2602.14938/) (2026)
- [Certified Per-Instance Unlearning Using Individual Sensitivity Bounds](https://mlsanity.com/paper/2602.15602/) (2026)
- [Near-Optimal Machine Unlearning Utility for Smooth Strongly Convex Losses](https://mlsanity.com/paper/2606.01527/) (2026)
- [SCOPE: Entanglement Frontier Escape for Source-Free Class Unlearning](https://mlsanity.com/paper/2608.02058/) (2026)

## Abstract (arXiv)

Machine Unlearning (MU) aims at removing the influence of specific data points from a trained model, striving to achieve this at a fraction of the cost of full model retraining. In this paper, we analyze the efficiency of unlearning methods and establish the first upper and lower bounds on minimax computation times for this problem, characterizing the performance of the most efficient algorithm against the most difficult objective function. Specifically, for strongly convex objective functions and under the assumption that the forget data is inaccessible to the unlearning method, we provide a phase diagram for the unlearning complexity ratio -- a novel metric that compares the computational cost of the best unlearning method to full model retraining. The phase diagram reveals three distinct regimes: one where unlearning at a reduced cost is infeasible, another where unlearning is trivial because adding noise suffices, and a third where unlearning achieves significant computational advantages over retraining. These findings highlight the critical role of factors such as data dimensionality, the number of samples to forget, and privacy constraints in determining the practical feasibility of unlearning.