Less Noise, Same Certificate: Retain Sensitivity for Unlearning

Carolin Heinzler; Kasra Malihi; Amartya Sanyal

cs.LGMar 3, 2026

Less Noise, Same Certificate: Retain Sensitivity for Unlearning

Authors: Carolin Heinzler, Kasra Malihi, Amartya Sanyal

Organizations: Department of Computer Science, University of Copenhagen

Abstract

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\setminus 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\cup 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

Panel of Figure 1 — 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 .

Panel of Figure 2 — Figure 2: Retain vs. global sensitivity (Active): Test accuracy of active unlearning for a fixed $(\varepsilon,\delta)$ 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 $\lambda_{R}$ . For D2D ( Figure 2(a) ), we vary the number of gradient steps $I$ and calibrate $\sigma$ to certify unlearning after $I$ steps. For Newton ( Figure 2(b) ), we vary the $\ell_{2}$ -regulariser $\lambda$ 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 $\lambda=0$ MSE $\lambda>0$	$mL^{\MSE}/n\lambda_{R}^{\MSE}$ ( 2 )	$\infty$ $mL^{\MSE}/n\lambda$
Log Loss $\lambda=0$ Log Loss $\lambda>0$	$mL^{\mathrm{LogL}}/n\lambda_{R}^{\mathrm{LogL}}$ ( 3 )	$\infty$ $mL^{\mathrm{LogL}}/n\lambda$

Appendix

Table 1: Retain vs. global sensitivity for ERM.

Panel of Figure 3 — 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 $\lambda\in\{0.1,0.01,0.001,0.0001,0.00001\}$ . We consider a fixed $(\varepsilon=1,\delta=10^{-9})$ certified unlearning guarantee, as a function of the iteration budget, for different values of $\lambda$ . 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 $\lambda=0.0001$ are the same as in Figure 2(a) .

Panel of Figure 4 — Figure 4: Retain vs. global sensitivity (Active), noise: Figures 4(a) and 4(b) show the ratio of iteration counts $\smash{\nicefrac{{I_{R}}}{{I}}}$ in Descent-to-Delete (D2D) to guarantee $\left({\varepsilon,\delta}\right)$ -unlearning for fixed $\left({\varepsilon=1,\delta=10^{-9},\sigma=0.1}\right)$ . Figure 4(c) shows the ratio $\smash{\RS\left({R}\right)/\Delta_{\GS}}$ for the Newton-step update. In all cases, smaller is better, and the gap is largest for small regularisation $\lambda$ . 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 (

\frac{1}{n}X^{T}X

) 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

Machine unlearning removes the influence of selected data or concepts from trained models while preserving useful behavior and avoiding full retraining.

See all 349 papers

Certified Per-Instance Unlearning Using Individual Sensitivity Bounds
Feb 17, 2026Hanna Benarroch, Jamal Atif, Olivier CappéPersonalized Differential Privacy Machine Unlearning
DI-ENS · CMAP
Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data
May 11, 2026Ahmed Mehdi Inane, Vincent Quirion, Gintare Karolina Dziugaite +1Machine Unlearning
Universit´e de Montr´eal · Mila, Quebec AI Institute · Google DeepMind
Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees
Oct 13, 2026Hanna Benarroch, Jamal Atif, Olivier CappéMachine Unlearning
DI-ENS · CMAP

Feb 17, 2026J/K move · Enter open · S save

Certified Per-Instance Unlearning Using Individual Sensitivity Bounds

Hanna Benarroch, Jamal Atif, Olivier Cappé

DI-ENS · CMAP

Personalized Differential Privacy Machine Unlearning Differential Privacy

Open paper AskPDF arXiv

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.

Abstract

Machine Unlearning

Explore similar work

Certified Per-Instance Unlearning Using Individual Sensitivity Bounds

Unlearning with Asymmetric Sources: Improved Unlearning-Utility Trade-off with Public Data

Counterfactual Certification for Sequential Unlearning with Long-Run Performance Guarantees