# Algorithms that Approximate Data Removal: New Results and Limitations

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

## Key facts

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

## Placed in

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

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Membership Inference Attacks against Machine Learning Models](https://mlsanity.com/paper/1610.05820/) (2016)
- [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)
- [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)
- [Auditing Differentially Private Machine Learning: How Private is Private SGD?](https://mlsanity.com/paper/2006.07709/) (2020)
- [Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning](https://mlsanity.com/paper/2101.04535/) (2021)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Adaptive Machine Unlearning](https://mlsanity.com/paper/2106.04378/) (2021)
- [On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning](https://mlsanity.com/paper/2110.11891/) (2021)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [A Swiss Army Infinitesimal Jackknife](https://mlsanity.com/paper/1806.00550/) (2018)
- [Hard to Forget: Poisoning Attacks on Certified Machine Unlearning](https://mlsanity.com/paper/2109.08266/) (2021)
- [Formalizing Data Deletion in the Context of the Right to be Forgotten](https://mlsanity.com/paper/2002.10635/) (2020)
- [Approximate Cross-validation: Guarantees for Model Assessment and Selection](https://mlsanity.com/paper/2003.00617/) (2020)
- [On Optimal Generalizability in Parametric Learning](https://mlsanity.com/paper/1711.05323/) (2017)

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

- [Machine Unlearning: Solutions and Challenges](https://mlsanity.com/paper/2308.07061/) (2023)
- [Learning to Unlearn: Instance-wise Unlearning for Pre-trained Classifiers](https://mlsanity.com/paper/2301.11578/) (2023)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2406.16257/) (2024)
- [MultiDelete for Multimodal Machine Unlearning](https://mlsanity.com/paper/2311.12047/) (2023)
- [Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions](https://mlsanity.com/paper/2409.09778/) (2024)
- [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)
- [MU-Bench: A Multitask Multimodal Benchmark for Machine Unlearning](https://mlsanity.com/paper/2406.14796/) (2024)
- [LLM Unlearning with LLM Beliefs](https://mlsanity.com/paper/2510.19422/) (2025)
- [Unstable Unlearning: The Hidden Risk of Concept Resurgence in Diffusion Models](https://mlsanity.com/paper/2410.08074/) (2024)
- [Remaining-data-free Machine Unlearning by Suppressing Sample Contribution](https://mlsanity.com/paper/2402.15109/) (2024)
- [Unlearning or Concealment? A Critical Analysis and Evaluation Metrics for Unlearning in Diffusion Models](https://mlsanity.com/paper/2409.05668/) (2024)
- [Ascent Fails to Forget](https://mlsanity.com/paper/2509.26427/) (2025)
- [Ticketed Learning-Unlearning Schemes](https://mlsanity.com/paper/2306.15744/) (2023)
- [Distillation Robustifies Unlearning](https://mlsanity.com/paper/2506.06278/) (2025)
- [UCD: Unlearning in LLMs via Contrastive Decoding](https://mlsanity.com/paper/2506.12097/) (2025)
- [Dropping Just a Handful of Preferences Can Change Top Large Language Model Rankings](https://mlsanity.com/paper/2508.11847/) (2025)
- [Speech Unlearning](https://mlsanity.com/paper/2506.00848/) (2025)
- [Certified Data Removal Under High-dimensional Settings](https://mlsanity.com/paper/2505.07640/) (2025)
- [MUBox: A Critical Evaluation Framework of Deep Machine Unlearning](https://mlsanity.com/paper/2505.08576/) (2025)
- [Rescaled Influence Functions: Accurate Data Attribution in High Dimension](https://mlsanity.com/paper/2506.06656/) (2025)
- [Synthetic Forgetting without Access: A Few-shot Zero-glance Framework for Machine Unlearning](https://mlsanity.com/paper/2511.13116/) (2025)
- [Machine unlearning through fine-grained model parameters perturbation](https://mlsanity.com/paper/2401.04385/) (2024)
- [LMEraser: Large Model Unlearning through Adaptive Prompt Tuning](https://mlsanity.com/paper/2404.11056/) (2024)
- [The Approximate Fisher Influence Function: Faster Estimation of Data Influence in Statistical Models](https://mlsanity.com/paper/2407.08169/) (2024)
- [Efficient Machine Unlearning by Model Splitting and Core Sample Selection](https://mlsanity.com/paper/2505.07026/) (2025)
- [Online Learning and Unlearning](https://mlsanity.com/paper/2505.08557/) (2025)
- [Efficient Unlearning with Privacy Guarantees](https://mlsanity.com/paper/2507.04771/) (2025)
- [On the Accuracy of Newton Step and Influence Function Data Attributions](https://mlsanity.com/paper/2512.12572/) (2025)

## Abstract (arXiv)

We study the problem of deleting user data from machine learning models trained using empirical risk minimization. Our focus is on learning algorithms which return the empirical risk minimizer and approximate unlearning algorithms that comply with deletion requests that come streaming minibatches. Leveraging the infintesimal jacknife, we develop an online unlearning algorithm that is both computationally and memory efficient. Unlike prior memory efficient unlearning algorithms, we target models that minimize objectives with non-smooth regularizers, such as the commonly used ℓ1, elastic net, or nuclear norm penalties. We also provide generalization, deletion capacity, and unlearning guarantees that are consistent with state of the art methods. Across a variety of benchmark datasets, our algorithm empirically improves upon the runtime of prior methods while maintaining the same memory requirements and test accuracy. Finally, we open a new direction of inquiry by proving that all approximate unlearning algorithms introduced so far fail to unlearn in problem settings where common hyperparameter tuning methods, such as cross-validation, have been used to select models.