Research map / Learning theory and algorithms / Prediction and decision losses
Towards Certified Unlearning for Deep Neural Networks
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.
Extends certified unlearning (Newton-update plus Gaussian noise) to nonconvex DNNs via local convex approximation, parameter-norm constraint, LiSSA-style inverse Hessian estimation, and extensions to nonconvergence and sequential requests.
Problem
Certified unlearning has strong guarantees for convex models but lacks a sound, efficient theory for nonconvex deep neural networks, where Hessian inverses can be unbounded and convergence is often not reached.
Approach
Adds an l2 regularizer when computing the Hessian (local convex approximation) and a parameter-norm constraint ||w||<=C via projected gradient descent to bound the inverse Hessian and the retrain distance, then uses a recursive LiSSA-style inverse-Hessian estimate and Gaussian noise calibrated to the derived error bound.
Key results
- Certified unlearning achieves over 10x speedup in unlearning time versus retraining on DNNs.
- Inverse Hessian approximation gives about 470x speedup over exact inverse Hessian on MLP/MNIST.
- On CIFAR-10 with AllCNN, the approximation error bound drops from 35077.75 at lambda=0 to 43.81 at lambda=10^4 (approximation error 26.52 to 26.17).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add local convex approximation (increase λ from 0 to 10⁴) (ablation) | Certified unlearning · CIFAR-10 (AllCNN) | approximation error bound: 35077.7545 -> 43.8059 | Helped |
| add local convex approximation (increase λ from 0 to 10⁴) (ablation) | Certified unlearning · CIFAR-10 (AllCNN) | approximation error: 26.5146 -> 26.1688 | Helped |
| add the parameter-norm constraint ||w||₂≤C (ablation) | Certified unlearning · CIFAR-10 (AllCNN) | approximation error: 46.8936 -> 26.5146 | Helped |
| add the parameter-norm constraint ||w||₂≤C (ablation) | Certified unlearning · CIFAR-10 (AllCNN) | approximation error bound | Helped |
| use inverse Hessian approximation instead of computing the exact inverse Hessian (ablation) | Certified unlearning · MNIST (MLP) | speedup: 470 times speedup | Helped |
| use Certified instead of L-CODEC | unlearning on MNIST (MLP) · MNIST | Attack AUC: 95.31 { $\pm$ 0.21} -> 95.28 { $\pm$ 0.50} | No clear effect |
| use Certified instead of the strongest listed baseline, Fine Tune | unlearning on CIFAR-10 (AllCNN) · CIFAR-10 | Attack AUC: 88.13 { $\pm$ 0.66} -> 87.22 { $\pm$ 1.13} | Helped |
| use Certified instead of Neg Grad | unlearning on SVHN (ResNet18) · SVHN | Attack AUC: 92.89 { $\pm$ 0.22} -> 92.18 { $\pm$ 1.16} | Helped |
Surprising findings
- Retraining from scratch is sometimes less effective than other unlearning methods under membership inference attack, because the retrained model is used as the shadow model while the attack model is transferred to the other baselines.
- Under the fixed 1,000-sample unlearning setting, the certified method's unlearned-set F1 is not always the closest to retrain; the paper reports mixed comparisons versus baselines.
Limitations
- Theoretical bounds depend on hyperparameters L, M, lambda_min that are set manually rather than computed, so certification levels may be imprecise.
- Error bound relies on a worst-case parameter-norm constraint ||w||<=C, which may reduce model performance if C is chosen too small.
- Experiments are limited to three image classification datasets and three small architectures.
Experimental setup
Datasets: MNIST CIFAR-10 SVHN
Benchmarks: MNIST CIFAR-10 SVHN
Metrics: micro F1-score on unlearned, retained, and test sets relearn time membership inference attack accuracy membership inference attack AUC unlearning time approximation error approximation error bound
Baselines: Retrain Fine tune Negative gradient Fisher forgetting L-CODEC
Builds on: certified unlearning (Guo et al. 2020) LiSSA differential privacy Gaussian mechanism influence function Newton update
Closest papers by meaning
- Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions (NeurIPS 2025 · similarity 0.90)
- Certified Unlearning for Neural Networks (ICML 2025 · similarity 0.89)
- Hessian-Free Online Certified Unlearning (ICLR 2025 · similarity 0.88)
- Certified Machine Unlearning via Noisy Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.87)
- When to Forget? Complexity Trade-offs in Machine Unlearning (ICML 2025 · similarity 0.86)
- Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning (NeurIPS 2024 · similarity 0.86)
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.