Research map / Learning theory and algorithms / Prediction and decision losses
Hessian-Free Online Certified Unlearning
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 a Hessian-free certified unlearning method that stores a per-sample statistical vector from the training trajectory so that each deletion is a single vector addition (plus noise).
Problem
Second-order certified unlearning requires costly Hessian computation and inversion, assumes convex objectives and that the learned model is an empirical risk minimizer, which fails for non-convex deep models and online/sequential deletion.
Approach
Maintain a per-sample approximator vector computed by an affine stochastic recursion over the training trajectory (using Hessian-vector products, never inverting the Hessian), so unlearning a sample requires only adding its stored vector to the learned model, with Gaussian noise for (epsilon, delta)-certification.
Key results
- On LR at 30% deletion, the proposed method's approximation error is 0.2097 versus 0.246554 (NS) and 0.246557 (IJ) in the convex setting.
- On LR with 20% forgetting, HF unlearning takes 0.0073 s (about 93,376x speedup over retraining) and reaches 87.50% test accuracy versus 86.25% for NS/IJ; on CNN HF reaches 91.50% accuracy with 0.0268 s unlearning runtime.
- In the non-convex CNN setting at 30% deletion, the approximation error is 0.90 with Spearman 0.81 and Pearson 0.74 for loss-change correlation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use HF instead of IJ | MNIST LR unlearning · MNIST, LR, 20% forgotten | test accuracy (%): 86.25 (-1.50) -> 87.50 (-0.25) | Helped |
| Use HF instead of IJ | MNIST CNN unlearning · MNIST, CNN, 20% forgotten | test accuracy (%): 82.75 (-11.00) -> 91.50 {(-2.25)} | Helped |
| Use HF instead of IJ | MNIST LR unlearning · MNIST, LR, 20% forgotten | unlearning runtime (Sec): 0.23×10^2 -> 0.0073 | Helped |
| Use HF instead of IJ | MNIST CNN unlearning · MNIST, CNN, 20% forgotten | unlearning runtime (Sec): 1.91×10^2 -> 0.0268 | Helped |
| Use HF instead of IJ | MNIST LR unlearning · MNIST, LR, 20% forgotten | storage (GB): 0.23 -> 0.03 | Helped |
| Use HF instead of IJ | MNIST CNN unlearning · MNIST, CNN, 20% forgotten | storage (GB): 1.78 -> 0.08 | Helped |
| Use HF instead of NS and IJ | HF approximator · MNIST LR, 30% deletion | approximation error: 0.2097; NS 0.246554; IJ 0.246557 | Helped |
| Use HF instead of NS and IJ | HF approximator · MNIST LR, 30% deletion | Pearson correlation: 0.96 | Helped |
| Use HF instead of NS and IJ | HF approximator · MNIST LR, 30% deletion | Spearman correlation: 0.95 | Helped |
| Use HF instead of NS and IJ | HF approximator · MNIST CNN, 30% deletion | approximation error: 0.90 | Helped |
| Use HF instead of NS and IJ | HF approximator · MNIST CNN, 30% deletion | Spearman correlation: 0.81 | Helped |
| Use HF instead of NS and IJ | HF approximator · MNIST CNN, 30% deletion | Pearson correlation: 0.74 | Helped |
Surprising findings
- The unlearned model's test accuracy exceeds that of NS and IJ, which the authors attribute to enhanced generalization of the method, though it is still below retraining on CNN.
Limitations
- Precomputation O(n^2 d) and storage O(nd) remain costly for large datasets and models.
- Highly sensitive to training stability and Hessian conditioning in non-convex settings; large step sizes cause large approximation error.
- Most theoretical results still rely on convexity; the non-convex analysis covers only unlearning guarantees.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: L2 approximation error Pearson correlation Spearman correlation test accuracy unlearning runtime pre-computation runtime storage (GB) membership inference AUC
Baselines: Newton Step (NS) Infinitesimal Jackknife (IJ) Retrain
Builds on: Newton step unlearning infinitesimal jackknife unlearning certified unlearning (Guo et al.) linear scaling rule
Closest papers by meaning
- Towards Source-Free Machine Unlearning (CVPR 2025 · similarity 0.91)
- Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions (NeurIPS 2025 · similarity 0.91)
- Certified Machine Unlearning via Noisy Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.90)
- When to Forget? Complexity Trade-offs in Machine Unlearning (ICML 2025 · similarity 0.90)
- Machine Unlearning under Overparameterization (NeurIPS 2025 · similarity 0.90)
- The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning (ICLR 2025 · similarity 0.89)
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.