Research map / Optimization / Optimizers
Certified Machine Unlearning via Noisy Stochastic Gradient Descent
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 certified approximate machine unlearning by running projected noisy mini-batch SGD for learning and unlearning, using a new infinite-Wasserstein tracking analysis to get Rényi unlearning guarantees that beat retraining and extend to sequential/batch requests.
Problem
Efficiently removing the influence of training data points from a model so the result is approximately equal to retraining from scratch, with certified Rényi-divergence guarantees, under mini-batch training for convex ERM.
Approach
Analyze the Rényi divergence between learning/unlearning PNSGD processes via the infinite Wasserstein distance between adjacent learning processes (bounded by O(ηM/b)) rather than the projection diameter 2R, combined with privacy amplification by iteration; this yields tighter guarantees, linear (not exponential) growth in sequential requests via triangle inequality, and support for mini-batch unl
Key results
- PNSGD unlearning uses about 10% of D2D's unlearning epochs for full batch and about 2% of LU's for mini-batch (b=128) under (1,1/n)-unlearning for 100 sequential requests, with similar utility (~0.9 MNIST, ~0.98 CIFAR10).
- Theoretical bound W_inf between adjacent stationary distributions is O(eta M / b), replacing the vacuous 2R bound used in prior DP analysis.
- Sequential unlearning privacy loss grows linearly in the number of requests via the standard triangle inequality of W_inf, versus exponentially via weak triangle inequality of Renyi divergence in LU.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PNSGD rather than full-batch gradient-based unlearning | PNSGD · 100 sequential unlearning requests, full-batch setting | unlearning epochs: 10% | Helped |
| use mini-batch PNSGD with batch size 128 rather than LU | PNSGD · 100 sequential unlearning requests | unlearning epochs: 2% | Helped |
| use PNSGD instead of D2D with a non-private internal state | MNIST and CIFAR10 · one-point unlearning, K=1 | test accuracy | Helped |
| use mini-batch PNSGD instead of LU | MNIST and CIFAR10 · one-point unlearning, K=1 | test accuracy | Mixed |
| reduce batch size from 32 to 1 (ablation) | PNSGD · MNIST, training from scratch, σ=0.03 | test accuracy: 0.87 to 0.64 | Hurt |
| reduce batch size from 32 to 1 (ablation) | PNSGD · CIFAR10, training from scratch, σ=0.03 | test accuracy: 0.97 to 0.81 | Hurt |
| decrease noise standard deviation (ablation) | PNSGD · 100 sequential unlearning requests | test accuracy | Helped |
| decrease noise standard deviation (ablation) | PNSGD · 100 sequential unlearning requests | unlearning epochs | Hurt |
| use smaller mini-batch size (ablation) | PNSGD · 100 sequential unlearning requests | unlearning epochs | Helped |
| use smaller mini-batch size (ablation) | PNSGD · 100 sequential unlearning requests | test accuracy | Hurt |
| use mini-batch PNSGD rather than full-batch PNSGD (ablation) | PNSGD · one-point unlearning, K=1 | test accuracy | Mixed |
| use full-batch PNSGD rather than LU's privacy accounting (ablation) | PNSGD, batch size n · one-point unlearning, K=1 | test accuracy | Hurt |
Surprising findings
- Decreasing batch size from 32 to 1 substantially reduces training accuracy (e.g., MNIST 0.87 to 0.64), so very small batches hurt utility and stability.
- The sampling-without-replacement strategy yields a worse W_inf bound, counter-intuitively, because the essential supremum penalizes any nonzero chance of sampling the modified point each iteration.
Limitations
- Requires strong convexity (or convexity with a conjectured but unproven bound in the convex-only case) and bounded gradients M-Lipschitz.
- Analysis is for non-adaptive unlearning requests only; adaptive setting left as future work.
- Convex-only bound grows linearly in training epochs T, so computational benefit can vanish for large T.
Experimental setup
Datasets: MNIST CIFAR10
Benchmarks: MNIST CIFAR10
Metrics: test accuracy unlearning epochs / gradient computations epsilon at delta=1/n
Baselines: Delete-to-Descent (D2D) Langevin Unlearning (LU) retraining from scratch
Builds on: Altschuler and Talwar privacy amplification by iteration Langevin unlearning Delete-to-Descent DP-SGD
Closest papers by meaning
- Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning (NeurIPS 2024 · similarity 0.94)
- The Utility and Complexity of In- and Out-of-Distribution Machine Unlearning (ICLR 2025 · similarity 0.94)
- Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions (NeurIPS 2025 · similarity 0.92)
- Leveraging Per-Instance Privacy for Machine Unlearning (ICML 2025 · similarity 0.92)
- Certified Unlearning for Neural Networks (ICML 2025 · similarity 0.92)
- Hessian-Free Online Certified Unlearning (ICLR 2025 · similarity 0.90)
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.