# Certified Minimax Unlearning with Generalization Rates and Deletion Capacity

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

## Key facts

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

## Placed in

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

## Builds on (most cited first, 30 of 47)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [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)
- [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)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Amnesiac Machine Learning](https://mlsanity.com/paper/2010.10981/) (2020)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Approximate Data Deletion from Machine Learning Models](https://mlsanity.com/paper/2002.10077/) (2020)
- [Machine Unlearning of Features and Labels](https://mlsanity.com/paper/2108.11577/) (2021)
- [Fast Yet Effective Machine Unlearning](https://mlsanity.com/paper/2111.08947/) (2021)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations](https://mlsanity.com/paper/2003.02960/) (2020)
- [Mixed-Privacy Forgetting in Deep Networks](https://mlsanity.com/paper/2012.13431/) (2020)
- [DeltaGrad: Rapid retraining of machine learning models](https://mlsanity.com/paper/2006.14755/) (2020)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [Boundary Unlearning](https://mlsanity.com/paper/2303.11570/) (2023)
- [Machine Unlearning for Random Forests](https://mlsanity.com/paper/2009.05567/) (2020)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Variational Bayesian Unlearning](https://mlsanity.com/paper/2010.12883/) (2020)
- [Deep Unlearning via Randomized Conditionally Independent Hessians](https://mlsanity.com/paper/2204.07655/) (2022)
- [Recommendation Unlearning](https://mlsanity.com/paper/2201.06820/) (2022)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [PUMA: Performance Unchanged Model Augmentation for Training Data Removal](https://mlsanity.com/paper/2203.00846/) (2022)
- [Train simultaneously, generalize better: Stability of gradient-based minimax learners](https://mlsanity.com/paper/2010.12561/) (2020)
- [Hidden Poison: Machine Unlearning Enables Camouflaged Poisoning Attacks](https://mlsanity.com/paper/2212.10717/) (2022)

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

- [On Effects of Steering Latent Representation for Large Language Model Unlearning](https://mlsanity.com/paper/2408.06223/) (2024)
- [Towards Scalable Exact Machine Unlearning Using Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2406.16257/) (2024)
- [Certified Unlearning for Neural Networks](https://mlsanity.com/paper/2506.06985/) (2025)
- [Editable Concept Bottleneck Models](https://mlsanity.com/paper/2405.15476/) (2024)
- [IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2407.19398/) (2024)
- [Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions](https://mlsanity.com/paper/2409.09778/) (2024)
- [Rethinking Data Protection in the (Generative) Artificial Intelligence Era](https://mlsanity.com/paper/2507.03034/) (2025)
- [MU-Bench: A Multitask Multimodal Benchmark for Machine Unlearning](https://mlsanity.com/paper/2406.14796/) (2024)
- [Machine Unlearning for Recommendation Systems: An Insight](https://mlsanity.com/paper/2401.10942/) (2024)
- [OpenGU: A Comprehensive Benchmark for Graph Unlearning](https://mlsanity.com/paper/2501.02728/) (2025)
- [Towards Reliable Forgetting: A Survey on Machine Unlearning Verification](https://mlsanity.com/paper/2506.15115/) (2025)
- [Speech Unlearning](https://mlsanity.com/paper/2506.00848/) (2025)
- [The Right to be Forgotten in Pruning: Unveil Machine Unlearning on Sparse Models](https://mlsanity.com/paper/2507.18725/) (2025)
- [MUBox: A Critical Evaluation Framework of Deep Machine Unlearning](https://mlsanity.com/paper/2505.08576/) (2025)
- [Missing-by-Design: Certifiable Modality Deletion for Revocable Multimodal Sentiment Analysis](https://mlsanity.com/paper/2602.16144/) (2026)
- [Provable unlearning in topic modeling and downstream tasks](https://mlsanity.com/paper/2411.12600/) (2024)
- [Module-Aware Parameter-Efficient Machine Unlearning on Transformers](https://mlsanity.com/paper/2508.17233/) (2025)
- [Attributing Data for Sharpness-Aware Minimization](https://mlsanity.com/paper/2507.04059/) (2025)
- [Controllable Concept Bottleneck Models](https://mlsanity.com/paper/2601.00451/) (2026)
- [Inference-time Unlearning Using Conformal Prediction](https://mlsanity.com/paper/2602.03787/) (2026)
- [A Neuro-inspired Interpretation of Unlearning in Large Language Models through Sample-level Unlearning Difficulty](https://mlsanity.com/paper/2504.06658/) (2025)
- [Governing AI Forgetting: Auditing for Machine Unlearning Compliance](https://mlsanity.com/paper/2602.14553/) (2026)
- [Descend or Rewind? Stochastic Gradient Descent Unlearning](https://mlsanity.com/paper/2511.15983/) (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)
- [Unlearning Offline Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/2605.00638/) (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)
- [The Forgetting-Retention Dilemma: Certified Unlearning Theory in Continual Learning](https://mlsanity.com/paper/2606.29832/) (2026)

## Abstract (arXiv)

We study the problem of (ε,δ)-certified machine unlearning for minimax models. Most of the existing works focus on unlearning from standard statistical learning models that have a single variable and their unlearning steps hinge on the direct Hessian-based conventional Newton update. We develop a new (ε,δ)-certified machine unlearning algorithm for minimax models. It proposes a minimax unlearning step consisting of a total-Hessian-based complete Newton update and the Gaussian mechanism borrowed from differential privacy. To obtain the unlearning certification, our method injects calibrated Gaussian noises by carefully analyzing the "sensitivity" of the minimax unlearning step (i.e., the closeness between the minimax unlearning variables and the retraining-from-scratch variables). We derive the generalization rates in terms of population strong and weak primal-dual risk for three different cases of loss functions, i.e., (strongly-)convex-(strongly-)concave losses. We also provide the deletion capacity to guarantee that a desired population risk can be maintained as long as the number of deleted samples does not exceed the derived amount. With training samples n and model dimension d, it yields the order mathcal O(n/d1/4), which shows a strict gap over the baseline method of differentially private minimax learning that has mathcal O(n/d1/2). In addition, our rates of generalization and deletion capacity match the state-of-the-art rates derived previously for standard statistical learning models.