Sample-Grained Approximate Unlearning with Provable Per-Sample Bounds
Organizations: The Hong Kong Polytechnic University · Yunnan University · Huawei Technologies Co., Ltd. · The Hong Kong Polytechnic University Research Centre for Privacy and Security Technologies in Future Smart Systems
Abstract
Machine unlearning aims to erase the influence of a designated forget set from a trained model while preserving strong utility on the retain set. Approximate unlearning methods efficiently achieve this goal without full retraining, but their effectiveness is primarily assessed using dataset-level aggregate metrics. These aggregate metrics can mask deviations from retraining at the level of individual samples. In this work, we focus on per-sample unlearning effectiveness. We introduce SALA (Sample-grained Likelihoods ALignment), a plug-in optimization framework that enables approximate unlearning methods to operate at the level of individual samples by steering each example toward its correct target distribution. To quantitatively assess this behavior, we further propose the sample-grained distribution gap, a metric that captures per-sample discrepancies between approximate unlearning and exact retraining output distributions. We provide theoretical guarantees showing that SALA contracts this gap and yields a bounded per-sample discrepancy to retraining. To make this framework practical, we develop a low-cost estimation method for the member and non-member target distributions. Extensive experiments on classification and generation tasks demonstrate that SALA reduces the sample-grained distribution gap by up to when paired with existing approximate unlearning baselines, while also improving robustness to unlearning hyperparameters.
Figures & tables
| Dataset | Method | Cost | |||||||||
| MSE | Pearson r | MSE | Pearson r | MSE | Pearson r | MSE | Pearson r | ||||
| CIFAR-10 | Laplace + SI | 2.80 | 0.48 | 9.48 | 0.41 | 0.78 | 0.04 | 2.45 | 0.05 | 0.4580 | 1.24 |
| SMSE (Ours) | 1.29 | 0.79 | 1.90 | 0.92 | 0.67 | 0.58 | 0.52 | 0.63 | 0.1801 | 1.00 | |
| ImageNet-1000 | Laplace + SI | 0.74 | 0.90 | 4.23 | 0.45 | 0.92 | 0.03 | 2.72 | 0.04 | 0.4835 | 1.08 |
| SMSE (Ours) | 0.28 | 0.98 | 0.31 | 0.98 | 0.59 | 0.62 | 0.67 | 0.52 | 0.1064 | 1.00 | |
| WikiText-103 | Laplace + SI | 0.15 | 0.92 | 1.56 | 0.48 | 0.85 | 0.05 | 1.14 | -0.08 | 0.3913 | 1.16 |
| Method | TA(%) (T-PPL) | FA(%) (F-PPL) | RA(%) (R-PPL) | ToW | DNO | MIA efficacy (%) | RULI (%) | Time (s) |
| CIFAR-10 (ResNet-18) | ||||||||
| Retrain | 93.84 0.21 | 93.68 0.28 | 100.00 0.01 | 1.00 0.00 | 0.0646 0.0022 | 50.57 0.25 | 50.00 0.00 | 1625.53 5.33 |
| FT | 89.04 1.13 | 92.32 1.20 | 95.84 1.10 | 0.90 0.01 | 0.3388 0.0053 | 52.09 0.22 | 70.01 0.73 | 242.01 42.25 |
| GA | 86.01 1.42 | 85.93 2.10 | 95.13 1.20 | 0.80 0.01 | 0.6228 0.0054 | 51.04 0.52 | 87.69 0.86 | 149.30 2.02 |
| RL | 88.94 0.71 | 87.63 0.90 | 98.08 0.60 | 0.87 0.02 | 0.6875 0.0059 | 55.10 0.21 | 82.35 14.31 | 321.32 7.70 |
| IU | 86.90 5.61 | 93.17 6.25 | 93.52 6.26 | 0.86 0.03 | 0.3982 0.0090 | 52.35 2.13 | 64.52 5.17 | 41.59 0.51 |
Appendix figures & tables17 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Score | Role | Mean | Median | Gaussian reference |
| CIFAR-10 | Log-odds | Member | 0.1098 | 0.1059 | 0.1139 |
| Log-odds | Non-member | 0.1162 | 0.1116 | ||
| Probability | Member | 0.2646 | 0.2606 | ||
| Probability | Non-member | 0.2919 | 0.2888 | ||
| Probability margin | Member | 0.2714 | 0.2680 | ||
| Probability margin | Non-member | 0.2890 | 0.2862 |
| Method | Configuration | 95% interval | DNO | 95% interval | |
| SalUn | No SALA | 0.2740 0.2409 | [-0.0251, 0.5731] | 0.9120 0.0377 | [0.8652, 0.9588] |
| SALA | 0.0322 0.0033 | [0.0280, 0.0364] | 0.1146 0.0076 | [0.1051, 0.1241] | |
| SALA-SMSE | 0.0218 0.0029 | [0.0182, 0.0254] | 0.2060 0.0119 | [0.1912, 0.2208] | |
| SALA w/ only | 0.0100 0.0016 | [0.0080, 0.0120] | 0.2270 0.0135 | [0.2102, 0.2438] | |
| SCRUB | No SALA | 0.3180 0.1561 | [0.1242, 0.5118] | 0.6780 0.1246 | [0.5233, 0.8327] |
| SALA | 0.0322 0.0036 | [0.0278, 0.0366] | 0.1094 0.0075 | [0.1000, 0.1188] |
| Method | TA(%) | FA(%) | RA(%) | ToW | DNO | MIA efficacy (%) | RULI (%) | Time (s) | ||
| SALA | 1 | 0.95 | 94.73 0.23 | 95.59 0.20 | 100.00 0.00 | 0.97 0.01 | 0.13 | 52.13 0.57 | 52.88 0.74 | 163.92 14.67 |
| 1 | 0.99 | 94.73 0.24 | 94.69 0.21 | 100.00 0.00 | 0.98 0.01 | 0.13 | 52.09 0.73 | 53.55 0.68 | 209.64 9.61 | |
| 2 | 0.95 | 94.44 0.28 | 95.58 0.21 | 100.00 0.00 | 0.97 0.01 | 0.12 | 52.42 0.16 | 52.15 1.30 | 53.22 3.21 | |
| 2 | 0.99 | 94.59 0.24 | 95.15 0.23 | 100.00 0.00 | 0.98 0.01 | 0.12 | 52.23 0.49 | 52.56 0.53 | 101.37 10.29 | |
| 3 | 0.95 | 94.57 0.26 | 96.33 0.36 | 100.00 0.00 | 0.95 0.02 | 0.13 | 53.52 0.35 | 51.29 0.72 | 47.67 0.52 | |
| 3 | 0.99 | 94.54 0.27 | 95.82 0.41 | 100.00 0.00 | 0.96 0.02 | 0.13 | 53.44 0.65 | 51.36 0.43 | 55.83 7.60 |
| Dataset | Model | Distribution parameters |
| CIFAR-10 | 42.70 | 0.763 |
| ImageNet-1000 | 97.78 | 19.55 |
| WikiText-103 | 201.94 | 17.78 |
| Method | CIFAR-10 | ImageNet-1000 | WikiText-103 | |||
| Cost | Training time | Cost | Training time | Cost | Training time | |
| Regular training | 23.12 min | 42.50 h | 29.09 h | |||
| Shadow models | 13.21 h ( ) | 307.73 h ( ) | 195.82 h ( ) | |||
| SMSE | 20.72 min ( ) | 45.72 h ( ) | 30.58 h ( ) | |||
| Dataset | Method | Forward inference | Statistics | Total | Time ratio |
| CIFAR-10 | Shadow models | 51.90 s | 1.10 s | 53.00 s | |
| SMSE | 48.70 s | 1.12 s | 49.82 s | ||
| ImageNet-1000 | Shadow models | 1.72 h | 7.12 s | 1.72 h | |
| SMSE | 5.72 h | 26.54 s | 5.73 h | ||
| WikiText-103 | Shadow models | 39.45 min | 6.43 s | 39.56 min | |
| SMSE | 2.19 h | 24.10 s | 2.20 h |
| Method | Sigma Stable | TA (%) | FA (%) | RA (%) | ToW | DNO | MIA efficacy (%) | RULI (%) | Time (s) |
| SALA-SMSE + Salun | ✓ | 94.25 0.27 | 95.13 0.17 | 99.97 0.01 | 0.98 0.01 | 0.21 | 54.28 0.36 | 55.97 0.53 | 56.47 5.35 |
| SALA-SMSE + SCRUB | ✓ | 94.01 0.23 | 94.03 0.16 | 99.97 0.02 | 0.98 0.01 | 0.23 | 54.43 0.16 | 55.25 0.27 | 46.45 2.79 |
| SALA-SMSE + | ✓ | 93.13 0.31 | 93.52 0.42 | 99.99 0.00 | 0.99 0.01 | 0.20 | 53.25 0.27 | 52.93 0.31 | 125.52 9.14 |
| SALA-SMSE + Salun | ✗ | 93.80 0.19 | 94.74 0.22 | 100.00 0.00 | 0.97 0.01 | 0.23 | 54.74 0.25 | 56.00 0.31 | 76.73 7.15 |
| SALA-SMSE + SCRUB | ✗ | 93.76 0.21 | 94.43 0.35 | 99.97 0.02 | 0.97 0.00 | 0.23 | 54.76 0.19 | 56.47 0.21 | 44.35 2.21 |
| SALA-SMSE + sparsity | ✗ | 93.92 0.27 | 94.14 0.31 | 99.99 0.01 | 0.97 0.01 | 0.23 | 54.41 0.08 | 53.16 0.13 | 108.70 9.15 |
| Warmup Epoch Ratio (%) | Merge Epoch Ratio (%) | Final Acc. | |||||||||
| r | MSE | r | MSE | r | MSE | r | MSE | ||||
| 0 | 10 | 0.75 | 1.57 | 0.90 | 2.34 | 0.59 | 0.42 | 0.70 | 0.40 | 0.2464 | 94.87 |
| 10 | 10 | 0.79 | 1.27 | 0.91 | 1.95 | 0.56 | 0.70 | 0.60 | 0.57 | 0.1999 | 94.49 |
| 20 | 10 (Main setup) | 0.79 | 1.29 | 0.92 | 1.90 | 0.58 | 0.67 | 0.63 | 0.52 | 0.1801 | 94.79 |
| 20 | 20 | 0.79 | 0.91 | 0.92 | 2.07 | 0.60 | 1.27 | 0.65 | 0.79 | 0.1822 | 94.78 |
| 20 | 0 | 0.74 | 0.97 | 0.92 | 1.90 | 0.58 | 0.67 | 0.64 | 0.53 | 0.1832 | 83.59 |
| r | MSE | r | MSE | r | MSE | r | MSE | |
| 10 | 0.77 | 1.30 | 0.89 | 2.47 | 0.53 | 1.06 | 0.73 | 2.69 |
| 20 | 0.78 | 1.19 | 0.90 | 2.24 | 0.57 | 0.42 | 0.70 | 1.38 |
| 30 (Main setup) | 0.79 | 1.29 | 0.92 | 1.90 | 0.58 | 0.67 | 0.63 | 0.52 |
| 40 | 0.77 | 1.70 | 0.92 | 2.08 | 0.60 | 0.85 | 0.65 | 0.58 |
| Method | ||||||||
| r | MSE | r | MSE | r | MSE | r | MSE | |
| Checkpoint ensemble (Main setup) | 0.79 | 1.29 | 0.92 | 1.90 | 0.58 | 0.67 | 0.64 | 0.52 |
| Dropout | 0.72 | 1.18 | 0.89 | 2.55 | -0.15 | 0.35 | -0.42 | 1.84 |
| Data augmentation | 0.71 | 1.55 | 0.91 | 2.48 | 0.61 | 0.41 | 0.76 | 1.00 |
| Dataset | Standard Training | SMSE |
| CIFAR-10 (ACC ) | 94.68 0.35 | 94.79 0.13 |
| ImageNet-1000 (ACC ) | 73.55 0.13 | 73.37 0.23 |
| WikiText-103 (PPL ) | 53.36 0.61 | 54.35 1.05 |
| Method | TA (%) | FA (%) | RA (%) | ToW | DNO | MIA efficacy (%) | RULI (%) | Time (s) |
| Retrain | 93.84 0.21 | 93.68 0.28 | 100.00 0.01 | 1.00 0.00 | 0.07 | 50.57 0.25 | 50.00 0.00 | 1625.53 5.33 |
| SalUn | 92.36 0.45 | 95.29 0.57 | 98.61 0.36 | 0.95 0.01 | 0.90 | 51.87 0.21 | 92.38 0.28 | 221.92 96.37 |
| SCRUB | 90.29 2.31 | 94.06 3.15 | 95.74 3.00 | 0.92 0.03 | 0.34 | 52.23 0.57 | 68.67 3.62 | 101.93 11.98 |
| sparsity | 88.18 3.47 | 91.94 4.48 | 95.80 2.98 | 0.88 0.02 | 0.32 | 53.09 2.72 | 70.03 5.24 | 150.28 28.45 |
| SALA + Salun | 94.44 0.28 | 95.58 0.21 | 100.00 0.00 | 0.97 0.02 | 0.12 | 52.42 0.16 | 52.15 1.30 | 53.22 3.21 |
| SALA + SCRUB | 94.35 0.15 | 94.03 0.14 | 99.99 0.00 | 0.99 0.01 | 0.11 | 52.46 0.11 | 52.12 0.07 | 50.31 6.62 |
| Method | TA(%) | FA(%) | RA(%) | ToW | DNO | MIA(%) | RULI(%) | Time(s) |
| Forget ratio: 5% | ||||||||
| Retrain | 94.65 0.37 | 94.33 0.21 | 100.00 0.00 | 1.00 0.00 | 0.06 | 51.15 0.08 | 50.23 0.07 | 1457.39 10.74 |
| SalUn | 94.45 0.08 | 95.72 0.14 | 100.00 0.00 | 0.96 0.01 | 0.56 | 53.15 0.14 | 74.42 0.57 | 94.45 5.47 |
| SALA | 94.10 0.24 | 93.90 0.13 | 100.00 0.00 | 0.99 0.00 | 0.09 | 51.03 0.11 | 52.14 0.29 | 38.49 1.52 |
| SALA-SMSE | 94.05 0.13 | 94.21 0.18 | 100.00 0.00 | 0.97 0.01 | 0.24 | 52.14 0.12 | 59.15 0.75 | 34.08 2.47 |
| SALA w/ only | 93.91 0.15 | 94.33 0.16 | 100.00 0.00 | 0.97 0.01 | 0.25 | 52.28 0.14 | 59.87 0.68 | 35.36 2.21 |
| Method | TA (%) | FA (%) | RA (%) | ToW | DNO | MIA efficacy (%) | RULI (%) | Time (s) |
| Retrain | 91.87 | 0.00 | 100.00 | 1.00 | 0.03 | 50.62 | 50.15 | 1627.24 |
| Salun | 95.79 | 0.02 | 99.78 | 0.96 | 0.45 | 51.15 | 77.90 | 23.43 |
| SCRUB | 94.43 | 0.00 | 97.42 | 0.95 | 0.39 | 51.36 | 69.49 | 73.39 |
| sparsity | 90.57 | 0.00 | 99.92 | 0.99 | 0.27 | 50.35 | 66.45 | 92.92 |
| SALA + Salun | 91.31 | 0.00 | 99.98 | 0.99 | 0.06 | 50.41 | 53.25 | 62.47 |
| SALA + SCRUB | 91.16 | 0.00 | 99.99 | 0.99 | 0.09 | 50.92 | 52.76 | 64.35 |
| Method | |||||||||
| Retrain | 0.00 | 1,264.78 | 2,540.88 | 3,757.28 | 4,930.74 | 6,073.32 | 7,185.72 | 8,274.24 | 9,854.16 |
| SALA | 46,211.80 | 46,418.71 | 46,618.79 | 46,819.77 | 47,020.85 | 47,188.40 | 47,369.07 | 47,546.77 | 47,715.27 |
| SALA-SMSE | 49.82 | 110.61 | 166.30 | 222.20 | 281.67 | 329.76 | 376.10 | 420.77 | 461.09 |
| Method | TA(%) | FA(%) | RA(%) | ToW | DNO | RULI(%) | |
| 1 | Retrain | 94.57 0.19 | 94.45 0.72 | 100.000 0.001 | 1.0000 0.0000 | 0.0000 0.0000 | 50.00 0.00 |
| SALA | 94.44 0.26 | 94.01 0.98 | 99.88 0.02 | 0.9871 0.0057 | 0.1725 0.0641 | 56.72 4.13 | |
| SALA-SMSE | 94.34 0.29 | 94.54 0.39 | 99.96 0.01 | 0.9917 0.0031 | 0.3469 0.0850 | 59.44 7.62 | |
| 8 | Retrain | 93.70 0.25 | 93.77 0.37 | 100.00 0.00 | 1.0000 0.0000 | 0.0000 0.0000 | 50.00 0.00 |
| SALA | 92.57 1.51 | 94.73 1.63 | 99.55 0.43 | 0.9643 0.0144 | 0.1486 0.0791 | 56.93 1.42 | |
| SALA-SMSE | 94.33 0.20 | 96.40 0.21 | 99.97 0.01 | 0.9650 0.0052 | 0.2854 0.0975 | 57.38 0.99 |
Machine Unlearning
Machine unlearning removes the influence of selected data or concepts from trained models while preserving useful behavior and avoiding full retraining.
See all 372 papers