Research map / Optimization / Nonconvex and smooth optimization
Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Rewind-to-Delete (R2D), a first-order, black-box certified unlearning algorithm for nonconvex losses that rewinds to an earlier GD checkpoint, runs K steps of GD on retained data, and adds Gaussian noise, with a new non-i.i.d. user-based evaluation framework.
Problem
Certified (epsilon, delta) machine unlearning for general nonconvex loss functions, where existing methods are second-order, white-box, or have limiting assumptions, and where evaluation typically removes i.i.d. random samples or whole classes.
Approach
Unlearn by rewinding to an earlier training checkpoint (or recovering it post hoc via a proximal point / backward Euler step) and running gradient descent on the retained-data loss, then adding Gaussian noise; the rewind length K trades privacy against compute, and the approach needs no training-time modifications.
Key results
- On Lacuna-100, R2D at 74% rewind (sigma=0.01) reduces unlearned-set AUC by -0.0995 versus -0.0191 for Hessian-Free and -0.0007 for CNS.
- R2D is reported to be up to 88 times faster during training than the white-box Hessian-Free method.
- On eICU, R2D outperforms all methods under classic MIA and outperforms certified methods under MIA-U.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase rewind from 7-10% to 74% with σ = 0.01 (ablation) | R2D · Lacuna-100 unlearn | AUC: 0.9238 -> 0.8998 | Helped |
| Increase rewind from 7-10% to 74% with σ = 0.01 (ablation) | R2D · Lacuna-100 test | AUC: 0.9478 -> 0.9534 | Hurt |
| Increase rewind from 7-10% to 74% with σ = 0.01 (ablation) | R2D · eICU unlearn | AUC: 0.7444 -> 0.7439 | Helped |
| Increase rewind from 7-10% to 74% with σ = 0.01 (ablation) | R2D · eICU test | AUC: 0.7327 -> 0.7326 | No clear effect |
| Use R2D rather than Constrained Newton Step | eICU unlearning · eICU unlearn | AUC: 0.7848 -> 0.7439 | Helped |
| Use R2D rather than Hessian-Free | Lacuna-100 unlearning · Lacuna-100 unlearn | AUC: 0.9555 -> 0.8998 | Helped |
| Use R2D rather than Constrained Newton Step | Lacuna-100 unlearning · Lacuna-100 unlearn | AUC: 0.9949 -> 0.8998 | Helped |
| Use R2D rather than non-certified methods | unlearning · eICU and Lacuna-100 | AUC on unlearned data | Mixed |
| Increase rewind percent (ablation) | R2D · membership inference attacks | MIA score | Helped |
| Use R2D rather than other methods | eICU unlearning · eICU | classic MIA score | Helped |
| Use R2D rather than other certified methods | eICU unlearning · eICU | MIA-U score | Helped |
| Use R2D rather than all other methods | Lacuna-100 unlearning · Lacuna-100 | MIA-U score | Helped |
Surprising findings
- Certified unlearning methods tend to defend against membership inference more successfully than non-certified methods, even with small perturbation.
- Retraining from scratch on eICU (noiseless 100% rewind) shows only a small unlearned-set drop, while on Lacuna-100 it gives a larger drop than some rewinding variants.
Limitations
- Reconstructing checkpoints via the proximal point method becomes unstable for K beyond T/2 due to compounding approximation errors.
- Experiments use mini-batch GD with large batches rather than full-batch GD, and replace ReLU with SmeLU and remove batch normalization for smoothness.
- Theoretical bounds are loose, requiring sigma choices (e.g., 0.01) that are set heuristically rather than from the bound.
Experimental setup
Datasets: eICU Collaborative Database Lacuna-100 (subset of VGGFace2) MAAD-Face annotations
Benchmarks: eICU Lacuna-100
Metrics: AUC on retain/unlearn/test sets membership inference attack AUC (classic MIA and MIA-U) relative AUC decrease on unlearned set computation time
Baselines: Constrained Newton Step Hessian-Free Unlearning Finetune Fisher Forgetting SCRUB
Builds on: descent-to-delete certified unlearning (Guo et al.) Gaussian mechanism proximal point method SCRUB
Closest papers by meaning
- The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning (ICLR 2025 · similarity 0.93)
- Certified Machine Unlearning via Noisy Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.92)
- Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning (NeurIPS 2024 · similarity 0.92)
- Certified Unlearning for Neural Networks (ICML 2025 · similarity 0.92)
- Leveraging Per-Instance Privacy for Machine Unlearning (ICML 2025 · similarity 0.91)
- Hessian-Free Online Certified Unlearning (ICLR 2025 · similarity 0.91)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.