Certified machine unlearning aims to provably remove the influence of a deletion set U from a model trained on a dataset S, by producing an unlearned output that is statistically indistinguishable from retraining on the retain set R:=S∖U. Many existing certified unlearning methods adapt techniques from Differential Privacy (DP) and add noise calibrated to global sensitivity, i.e., the worst-case output change over all adjacent datasets. We show that this DP-style calibration is often overly conservative: unlike DP, unlearning requires no indistinguishability across different retain sets, only between each deletion output and retraining on the same retain set R. Motivated by this distinction, we define retain sensitivity as the worst-case output change over deletions U′ from R∪U′ while keeping R fixed. While insufficient for DP, retain sensitivity is exactly sufficient for unlearning, allowing for the same certificates with less noise. We validate these reductions in noise theoretically and empirically across several problems, including the weight of minimum spanning trees, PCA, and ERM. Finally, we refine the analysis of two widely used certified unlearning algorithms through the lens of retain sensitivity, leveraging the regularity induced by R to further reduce noise and improve utility.
Figures & tables
Figure 1: Retain vs. global sensitivity (Passive): In all cases, the y -axis is the ratio \nicefrac\RS(m)\GS(m) where smaller value means larger advantage of using \RS(m) compared to \GS(m) ; this gap is largest when the retained data are well-conditioned, while the ratios approach 1 in regimes where worst-case and data-dependent bounds coincide. For details on experiments see Appendix I .
Figure 2: Retain vs. global sensitivity (Active): Test accuracy of active unlearning for a fixed (ε,δ) guarantee, comparing noise calibrated to \GS(1) vs. \RS(1) against retraining. We use LogLoss on MNIST with random projections to dimensions {50,25,20,15} , which control the data-dependent curvature λR . For D2D ( Figure 2(a) ), we vary the number of gradient steps I and calibrate σ to certify unlearning after I steps. For Newton ( Figure 2(b) ), we vary the ℓ2 -regulariser λ after one Newton update. Details and additional D2D utility evaluations can be found in Appendices I , 3 and 4 .
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Loss
\RS\ERM(m)(R)
\GS\ERM(m)
MSE λ=0 MSE λ>0
mL\MSE/nλR\MSE ( 2 )
∞mL\MSE/nλ
Log Loss λ=0 Log Loss λ>0
mLLogL/nλRLogL ( 3 )
∞mLLogL/nλ
Appendix
Table 1: Retain vs. global sensitivity for ERM.
Figure 3: D2D utility comparison: Left block: LogLoss. Right block: MSE. Within each block, columns correspond to noise calibrated to GS and RS for D2D Algorithm 1 , and rows correspond to λ∈{0.1,0.01,0.001,0.0001,0.00001} . We consider a fixed (ε=1,δ=10−9) certified unlearning guarantee, as a function of the iteration budget, for different values of λ . The baseline is exact retraining. Experiments are conducted on MNIST with random projections to dimensions {15,20,25,50} . The plots for log loss with λ=0.0001 are the same as in Figure 2(a) .
Figure 4: Retain vs. global sensitivity (Active), noise: Figures 4(a) and 4(b) show the ratio of iteration counts \nicefracIRI in Descent-to-Delete (D2D) to guarantee (ε,δ) -unlearning for fixed (ε=1,δ=10−9,σ=0.1) . Figure 4(c) shows the ratio \RS(R)/Δ\GS for the Newton-step update. In all cases, smaller is better, and the gap is largest for small regularisation λ . For details on experiments see Appendix I .
Dataset
Full Dataset Size
Min. Eigenvalue
mnist_rpe15
10,000
0.0251
mnist_rpe20
10,000
0.0173
mnist_rpe25
10,000
0.0126
mnist_rpe50
10,000
0.0002
folktables
10,000
0.0048
wine
1,599
0.0007
Appendix
Table 2: Smallest eigenvalue of normalized covariance ( n1XTX ) per Dataset
Dataset
Mean
Min
25%
50%
75%
95%
Max
physics collab
0.1216
0.0132
0.0132
0.0185
0.1111
0.5000
10.8333
soc-sign-bitcoin-otc
12.0120
1
12
12
13
16
21
at_migrations
17.3591
1
1
2
6
40
28,010
openflights
1.8092
1
1
1
2
4
20
Appendix
Table 3: Edge Weight Distribution Across MST Datasets
Dataset
Mean
Min
25%
50%
75%
Max
physics collab
0.3517
0.1287
0.1784
0.3447
0.5548
0.6648
soc-sign-bitcoin-otc
0.1191
0.1002
0.1067
0.1129
0.1271
0.1846
at_migrations
0.7646
0.5180
0.7283
0.7784
0.8109
0.9123
openflights
0.0955
0.0437
0.0801
0.0926
0.1163
0.1359
Appendix
Table 4: Edge Density Distribution Among Sampled Subgraphs
Machine unlearning removes the influence of selected data or concepts from trained models while preserving useful behavior and avoiding full retraining.
Certified machine unlearning can be achieved through noise injection, with differential privacy guarantees obtained by calibrating the noise to worst-case sensitivity. Yet, the influence of individual training points is highly heterogeneous, making such uniform calibration unnecessarily conservative for most deletion requests. We consider certified per-instance unlearning, a data-dependent notion of certified deletion in which the unlearning mechanism and its certificate can adapt to the point being removed. Our framework turns point-specific sensitivity information into formal unlearning guarantees, allowing the amount of noise to reflect the difficulty of the deletion request rather than the worst case. When training is deterministic, we derive explicit per-instance unlearning certificates. For noisy gradient descent, in the case of ridge regression, similar certificates are obtained through high-probability sensitivity bounds. Experiments on NYU-Depth with frozen DINOv2 features show substantial variation in deletion difficulty across points, and demonstrate that per-instance calibration can substantially improve utility over uniform worst-case calibration.
Noise-based certified machine unlearning currently faces a hard ceiling: the noise magnitude required to certify unlearning typically destroys model utility, particularly for large-scale deletion requests. While leveraging public data is a standard technique in differential privacy to relax this tension, its role in unlearning remains unexplored. We address this gap by introducing Asymmetric Langevin Unlearning (ALU), a framework that uses public data to mitigate privacy costs. We prove that public data injection suppresses the unlearning cost by a factor of O(1/npub2), guaranteeing a strict computational advantage over retraining. This establishes a new control mechanism: practitioners can mitigate the need for high noise-and the associated utility loss-by increasing the volume of public data. Crucially, we analyze the realistic setting of distribution mismatch, explicitly characterizing how shifts between public and private sources impact utility. We show that ALU enables mass unlearning of constant dataset fractions -- a regime where standard symmetric methods become impractical -- while maintaining high utility. Empirical evaluations using variational Rényi divergence and membership inference attacks confirm that ALU effectively thwarts privacy attacks while preserving utility under reasonable distribution shifts.
Ahmed Mehdi Inane, Vincent Quirion, Gintare Karolina Dziugaite +1
Universit´e de Montr´eal · Mila, Quebec AI Institute · Google DeepMind
Certified machine unlearning ensures the proximity between the unlearned model and a model retrained without the data to be forgotten. Extending this framework to sequential deletion requests, typically arriving as groups of variable size (e.g., all records of one user or of coordinated users), is challenging. For unlearning methods based on fine-tuning on the retain sets, this leads to either degrading performance or increasing computation as the number of unlearning requests grows. For independent successive requests, we instead certify each model release against a counterfactual unlearning trajectory in which the group being deleted never took part. With a fixed fine-tuning budget per deletion, we show that, for smooth strongly convex objectives, this approach keeps the performance loss bounded, uniformly in the number of requests. Experiments with multiclass logistic regression on FEMNIST show that the resulting algorithm needs fewer corrective steps than existing sequential methods and outperforms training-time differential privacy, particularly when group sizes are heterogeneous.