# Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions

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

## Key facts

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

## Placed in

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

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

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [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)
- [VGGFace2: A dataset for recognising faces across pose and age](https://mlsanity.com/paper/1710.08092/) (2017)
- [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://mlsanity.com/paper/1911.04933/) (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)
- [Knowledge Unlearning for Mitigating Privacy Risks in Language Models](https://mlsanity.com/paper/2210.01504/) (2022)
- [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://mlsanity.com/paper/2103.03279/) (2021)
- [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)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [When Machine Unlearning Jeopardizes Privacy](https://mlsanity.com/paper/2005.02205/) (2020)
- [Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations](https://mlsanity.com/paper/2003.02960/) (2020)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [Efficient Private ERM for Smooth Objectives](https://mlsanity.com/paper/1703.09947/) (2017)
- [Certified Graph Unlearning](https://mlsanity.com/paper/2206.09140/) (2022)
- [Algorithms that Approximate Data Removal: New Results and Limitations](https://mlsanity.com/paper/2209.12269/) (2022)
- [MAAD-Face: A Massively Annotated Attribute Dataset for Face Images](https://mlsanity.com/paper/2012.01030/) (2020)
- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Breaking the Trilemma of Privacy, Utility, Efficiency via Controllable Machine Unlearning](https://mlsanity.com/paper/2310.18574/) (2023)
- [SIFU: Sequential Informed Federated Unlearning for Efficient and Provable Client Unlearning in Federated Optimization](https://mlsanity.com/paper/2211.11656/) (2022)
- [Hessian-Free Online Certified Unlearning](https://mlsanity.com/paper/2404.01712/) (2024)

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

- [When is Task Vector Provably Effective for Model Editing? A Generalization Analysis of Nonlinear Transformers](https://mlsanity.com/paper/2504.10957/) (2025)
- [Certified Unlearning for Neural Networks](https://mlsanity.com/paper/2506.06985/) (2025)
- [Ascent Fails to Forget](https://mlsanity.com/paper/2509.26427/) (2025)
- [Towards Reliable Forgetting: A Survey on Machine Unlearning Verification](https://mlsanity.com/paper/2506.15115/) (2025)
- [Revisiting the Past: Data Unlearning with Model State History](https://mlsanity.com/paper/2506.20941/) (2025)
- [Online Learning and Unlearning](https://mlsanity.com/paper/2505.08557/) (2025)
- [Efficient Unlearning with Privacy Guarantees](https://mlsanity.com/paper/2507.04771/) (2025)
- [Fully Decentralized Certified Unlearning](https://mlsanity.com/paper/2512.08443/) (2025)
- [Interactionless Inverse Reinforcement Learning: A Data-Centric Framework for Durable Alignment](https://mlsanity.com/paper/2602.14844/) (2026)
- [Less Noise, Same Certificate: Retain Sensitivity for Unlearning](https://mlsanity.com/paper/2603.03172/) (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)
- [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)
- [Certified Per-Instance Unlearning Using Individual Sensitivity Bounds](https://mlsanity.com/paper/2602.15602/) (2026)
- [SoK: Unlearnability and Unlearning for Model Dememorization](https://mlsanity.com/paper/2605.11592/) (2026)
- [State-Space Unlearning for Non-Stationary Bias in Land Surface Forecasting](https://mlsanity.com/paper/2610.02248/) (2026)
- [Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees](https://mlsanity.com/paper/2610.17993/) (2026)

## Abstract (arXiv)

Machine unlearning algorithms aim to efficiently remove data from a model without retraining it from scratch, in order to remove corrupted or outdated data or respect a user's ``right to be forgotten." Certified machine unlearning is a strong theoretical guarantee based on differential privacy that quantifies the extent to which an algorithm erases data from the model weights. In contrast to existing works in certified unlearning for convex or strongly convex loss functions, or nonconvex objectives with limiting assumptions, we propose the first, first-order, black-box (i.e., can be applied to models pretrained with vanilla gradient descent) algorithm for unlearning on general nonconvex loss functions, which unlearns by ``rewinding" to an earlier step during the learning process before performing gradient descent on the loss function of the retained data points. We prove (ε, δ) certified unlearning and performance guarantees that establish the privacy-utility-complexity tradeoff of our algorithm, and we prove generalization guarantees for functions that satisfy the Polyak-Lojasiewicz inequality. Finally, we demonstrate the superior performance of our algorithm compared to existing methods, within a new experimental framework that more accurately reflects unlearning user data in practice.