Research map / Optimization / Optimizers
Leveraging Per-Instance Privacy for Machine 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 per-instance privacy losses, estimated from training gradient norms, to predict how many fine-tuning steps are needed to unlearn a forget set, with theory for noisy GD (SGLD) and empirical validation for noiseless SGD.
Problem
Approximate machine unlearning via fine-tuning has worst-case DP guarantees that are loose for non-convex models, and there is no per-data-point theory explaining which forget sets are hard to unlearn.
Approach
Replace the worst-case Rényi-DP bound in the convergence analysis of noisy gradient descent unlearning (Langevin unlearning) with per-instance privacy losses, which are estimated from gradient norms of individual points during a single training run; the number of unlearning steps then scales logarithmically with this per-instance loss, and the same ranking is found to hold for noiseless SGD.
Key results
- Per-instance privacy losses rank forget sets by number of unlearning steps: forget sets with higher average privacy loss take more SGLD and SGD fine-tuning steps to reach 5% of oracle UA/MIA.
- Average gradient norm is the best proxy for privacy loss, but single-checkpoint proxies such as gradient norm and EL2N also correlate strongly; C-Proxy is also correlated with privacy loss.
- Top-ranked hard forget sets by privacy loss take longer to unlearn than those selected by C-Proxy, average gradient norm, or EL2N, across forget set sizes 600, 1000, and 2000.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Rank forget sets by average per-instance privacy loss | Fine-tuning unlearning with SGLD · CIFAR-10, ResNet-18 | Steps to unlearn | Hurt |
| Rank forget sets by average per-instance privacy loss | Fine-tuning unlearning with SGD · Multiple evaluation metrics and datasets | Steps to unlearn | Hurt |
| Rank forget sets by average per-instance privacy loss | L1-Sparse unlearning · Forget sets with different privacy scores | Steps to unlearn | Hurt |
| Use per-instance privacy loss instead of C-Proxy, average gradient norm, or EL2N to select difficult examples | Fine-tuning-based unlearning · Forget sets of size 600, 1000, and 2000 | Steps to unlearn | Helped |
| Use per-instance privacy loss as a proxy for data difficulty | Fine-tuning-based unlearning · Proxy metric comparisons | Correlation with privacy loss | Helped |
| Increase average privacy loss of the forget set | Fine-tuning unlearning · CIFAR-10, loss-barrier analysis | Initial loss barrier to the oracle | Hurt |
| Fine-tune on the retain set to unlearn | Fine-tuning unlearning · CIFAR-10, loss-barrier analysis | Loss barrier after unlearning | Helped |
| Vary the noise assumed when estimating privacy-loss rankings (ablation) | Per-instance privacy loss rankings · SVHN, ResNet-18 | Spearman correlation: 0.70 (p = 0.0); 0.99 (p = 0.0); 0.99 (p = 0.0) | No clear effect |
| Increase forget-set size (ablation) | Privacy-loss-based difficulty ranking · CIFAR-10; forget sets of 100, 5,000, and 10,000 samples | Separation of easy and hard subsets | Mixed |
Surprising findings
- Group privacy bounds from prior work did not change across forget sets that empirically require different numbers of unlearning steps, so existing group unlearning analyses appear too loose.
- Standard noiseless SGD rankings of forget-set difficulty are well predicted by a privacy-loss estimate that assumes a small implicit noise term.
Limitations
- Theory covers noisy GD (SGLD) only; SGD results rely on assuming a small implicit noise level sigma for privacy loss estimation.
- No tight theory for group (multi-point) unlearning; the paper states this remains open.
- Experiments limited to ResNet-18 and ViT-small on CIFAR-10 and SVHN with forget sets of up to 10,000 points.
Experimental setup
Datasets: CIFAR-10 SVHN
Benchmarks: CIFAR-10 SVHN
Metrics: unlearning accuracy (UA) retain accuracy test accuracy (utility) membership inference attack success Gaussian Unlearning Score loss barrier steps to unlearn (5% margin) Spearman correlation
Baselines: C-Proxy average gradient norm EL2N score L1-Sparse
Builds on: Langevin unlearning (Chien et al., 2024) per-instance differential privacy (Thudi et al., 2024) L1-Sparse unlearning EL2N score
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.93)
- Certified Machine Unlearning via Noisy Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.92)
- Certified Unlearning for Neural Networks (ICML 2025 · similarity 0.91)
- Rewind-to-Delete: Certified Machine Unlearning for Nonconvex Functions (NeurIPS 2025 · similarity 0.91)
- Efficient Source-free Unlearning via Energy-Guided Data Synthesis and Discrimination-Aware Multitask Optimization (ICML 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.