Less Noise, Same Certificate: Retain Sensitivity for Unlearning
Carolin Heinzler Kasra Malihi Amartya Sanyal ✉ Department of Computer Science, University of Copenhagen · 2026
Read Less Noise, Same Certificate: Retain Sensitivity for Unlearning by Carolin Heinzler Kasra Malihi Amartya Sanyal ✉ Department of Computer Science, University of Copenhagen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-03172.txt.
Introduction
Carolin Heinzler, Kasra Malihi, and Amartya Sanyal prove that deleting data from a model needs less noise than privacy rules suggest. Certified unlearning must make a model statistically indistinguishable from one retrained without the deleted data. Existing methods borrow differential privacy machinery and add noise sized for the worst change over any neighboring dataset.
The key observation is that unlearning never promises to protect the data that stays. A new measure, retain sensitivity, fixes the retained set and only varies what gets deleted, which is exactly what unlearning must hide. Noise calibrated to that smaller quantity keeps the same certificates. Tests on spanning trees, principal components, and standard learning confirm the savings, and two popular algorithms get sharper analyses through the same lens.
Catalog record
| CREATOR | Carolin Heinzler Kasra Malihi Amartya Sanyal ✉ Department of Computer Science, University of Copenhagen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 91162 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.03172
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Less Noise, Same Certificate: Retain Sensitivity for Unlearning Carolin Heinzler Kasra Malihi Amartya Sanyal ✉ Department of Computer Science, University of Copenhagen Abstract Certified machine unlearning aims to provably remove the influence of a deletion set U U from a model trained on a dataset S S , by producing an unlearned output that is statistically indistinguishable from retraining on the retain set R ≔ S ∖ U R\coloneqq 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 for unlearning, based on a key observation: certified unlearning, by definition, does not require protecting the privacy of the retained data R R . Motivated by this distinction, we define retain sensitivity as the worst-case output change over deletions U U while keeping R 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 R to further reduce noise and improve utility. 1 Introduction Machine learning models are increasingly deployed in settings where parts of the training data may later need to be removed. Individuals may exercise deletion rights (e.g., EU GDPR and the right to erasure (Art.17; GDP 16 )), and training pipelines may inadvertently ingest poisoned SFB 24 , copyrighted DLL+ 25 , or otherwise impermissible examples Thi 23 that must subsequently be deleted. While retraining from scratch is the gold standard for deletion, it is often computationally prohibitive or operationally infeasible. These pressures have motivated the study of certified machine unlearning CY 15 : given a model trained on S and a deletion set U\subset S , the goal is to efficiently produce an unlearned model whose distribution is statistically indistinguishable from that of retraining on the retain set R\coloneqq S\setminus U . Certified unlearning is closely connected to Differential Privacy (DP), which requires a learning algorithm’s output distribution to be indistinguishable across all neighbouring datasets DMNS 06 . Many DP mechanisms achieve this by adding noise scaled to the algorithm’s global sensitivity , i.e., the largest possible change in output between datasets that differ in one datapoint. This adjacency-based indistinguishability implies a natural passive route to unlearning: a differentially private model already satisfies the unlearning guarantee for deleting any single sample without any post-hoc update, and extends to the deletion of multiple datapoints by invoking group privacy. Notably, it also avoids releasing a second model, and thus trivially prevents model-differencing attacks, which can recover information about U when both the pre- and post-deletion models are observed CZW+ 21 ; CS 23 ; BTK+ 24 . However, because global sensitivity must account for the worst-case change across all potential datasets, this passive approach often incurs a substantial utility cost due to the injection of excessive noise BST 14 . To improve utility, many active certified unlearning methods perform an explicit update and inject additional noise, often using DP-style sensitivity analyses GGHVDM 20 ; NRSM 21 ; SAKS 21 ; AKGK 25 (see Appendix A for background on passive vs. active unlearning and its connections to DP). Yet, in these works, the noise is still calibrated to global sensitivity. In contrast, certified unlearning has a narrower scope: it must hide the influence of the deleted set U , but the retain set R is fixed and its properties need not be hidden. This suggests that the minimal noise required for certification should be calibrated to the specific properties of R , rather than to a worst-case over all possible datasets. Assuming that the unlearning algorithm has access to the full retain set R , this is exactly the distinction that motivates our central question: Given an algorithm and a fixed retain set R , what is the minimum noise fundamentally required to achieve certified unlearning? To formalize this, we introduce Retain Sensitivity (RS). We define RS as the worst-case change in the algorithm’s output between R and R\cup Z over all possible deletion sets Z , conditioned on the specific set R being retained. By construction, retain sensitivity for a fixed R is always upper-bounded by the global sensitivity and can be significantly smaller; moreover, it is bounded by the dataset-dependent notion of local sensitivity at R . While local-sensitivity calibration is notoriously insufficient for DP NRS 07 ; DL 09 , we show that for certified unlearning (precisely because the guarantee conditions on R ) calibrating noise to the retain sensitivity of R is simultaneously sufficient for the unlearning certificate and can yield significantly less noise. Contributions. Our contributions are threefold: • First, in Section 2 , we formally define retain sensitivity and establish it as a sufficient (and in some cases necessary) quantity for calibrating noise in both passive and active unlearning algorithms. • Second, in Section 3 we derive retain sensitivity bounds for canonical problems (weight of a minimal spanning tree (MST), PCA, SVM and ERM). We prove and empirically demonstrate that these bounds substantially reduce noise compared to global sensitivity, including in the passive setting where noise is added once without a post-hoc update. Across these problems, the gains come from stability around the retained set R : better conditioning (e.g., weight separation, eigengap, margin, curvature) limits how much U can change the output. • Finally, in Section 4 , we adapt two widely used certified active unlearning algorithms, Descent-to-Delete ( NRSM 21 ) and Newton Update ( SAKS 21 ) , to use retain sensitivity calibration. In particular, we replace worst-case strong convexity with data-dependent curvature bounds (e.g., lower bounds on the empirical Hessian over R ), yielding less noise for the same unlearning certificate. 2 Retain Sensitivity 2.1 Preliminaries Let \mathcal{X} be the domain, \mathcal{Y} the label set, and \mathcal{Z}=\mathcal{X}\times\mathcal{Y} . Given a sample S\in\mathcal{Z}^{n+m} , a learning algorithm \mathcal{A}:\mathcal{Z}^{n+m}\to\mathcal{W} outputs \mathcal{A}(S)\in\mathcal{W} . Throughout, \|\cdot\| denotes the norm on the output space under discussion: for vector outputs we take \|\cdot\|=\|\cdot\|_{2} , and for matrix outputs we take \|\cdot\|=\|\cdot\|_{\mathrm{op}} unless stated otherwise. An unlearning mechanism \bar{\mathcal{A}}:\mathcal{Z}^{*}\times\mathcal{W}\times\mathcal{T}\to\mathcal{W} takes a forget set U\subseteq S , the learned output \mathcal{A}(S) , and a set of additional statistics about the dataset S referred to as side information T(S)\in\mathcal{T} , and outputs \bar{\mathcal{A}}(U,\mathcal{A}(S),T(S))\in\mathcal{W} . We set R=S\setminus U for the retain set . We first recall a standard notion of statistical indistinguishability, which will be used to define certified unlearning. Definition 2.1 ( (\varepsilon,\delta) -Indistinguishability) . Let \varepsilon>0 and \delta\in(0,1) . Two distributions \mathcal{M}_{0},\mathcal{M}_{1} over a common support are called (\varepsilon,\delta) -indistinguishable (denoted \mathcal{M}_{0}\approx^{\varepsilon,\delta}\mathcal{M}_{1} ) if for all measurable W\subseteq\mathcal{W} , and i\neq j , i,j\in\{0,1\} , P_{Z\sim\mathcal{M}_{i}}(Z\in W)\ \leq\ e^{\varepsilon}P_{Z\sim\mathcal{M}_{j}}(Z\in W)\ +\ \delta. We use the unlearning guarantee of SAKS 21 , but state it in terms of the retained set R=S\setminus U , to emphasize that the guarantee can be conditioned on R . Definition 2.2 ( (\varepsilon,\delta) -Unlearning