A Certified Unlearning Approach without Access to Source Data
Authors: Umit Yigit Basaran
Sk Miraj Ahmed
Amit Roy-Chowdhury
Basak Guler
Venue: ICML 2025 poster (2025)
Keywords: Certified machine unlearning
privacy
surrogate data
statistical distance
noise calibration
Primary area: general_machine_learning
TL;DR: We propose a certified unlearning method using surrogate data and noise calibration based on statistical distance between source and surrogate data distributions ensuring privacy compliance with theoretical guarantees

Abstract: With the growing adoption of data privacy regulations, the ability to erase private or copyrighted information from trained models has become a crucial requirement. Traditional unlearning methods often assume access to the complete training dataset, which is unrealistic in scenarios where the source data is no longer available. To address this challenge, we propose a certified unlearning framework that enables effective data removal without access to the original training data samples. Our approach utilizes a surrogate dataset that approximates the statistical properties of the source data, allowing for controlled noise scaling based on the statistical distance between the two. While our theoretical guarantees assume knowledge of the exact statistical distance, practical implementations typically approximate this distance, resulting in potentially weaker but still meaningful privacy guarantees. This ensures strong guarantees on the model's behavior post-unlearning while maintaining its overall utility. We establish theoretical bounds, introduce practical noise calibration techniques, and validate our method through extensive experiments on both synthetic and real-world datasets. The results demonstrate the effectiveness and reliability of our approach in privacy-sensitive settings.

A Certified Unlearning Approach without Access to Source Data
Umit Yigit Basaran"
Sk Miraj Ahmed?
Amit Roy-Chowdhury Başak Güler
Abstract
tion Regulation (GDPR, 2016), California Consumer Pri- vacy Act (CCPA, 2018), the Canadian Consumer Privacy led to a pressing de-
With the growing adoption of data privacy regu- lations, the ability to erase private or copyrighted information from trained models has become a crucial requirement. Traditional unlearning meth- ods often assume access to the complete training dataset, which is unrealistic in scenarios where the source data is longer available. To address this challenge, we propose a certified unlearning framework that enables effective data removal without access to the original training data sam- ples. Our approach utilizes a surrogate dataset that approximates the statistical properties of the source data, allowing for controlled noise scaling based on the statistical distance between the two. While our theoretical guarantees assume knowl- edge of the exact statistical distance, practical im- plementations typically approximate this distance, resulting in potentially weaker but still meaning- ful privacy guarantees. This ensures strong guar- antees on the model's behavior post-unlearning while maintaining its overall utility. We estab- lish theoretical bounds, introduce practical noise calibration techniques, and validate our method through extensive experiments on both synthetic and real-world datasets. The results demonstrate the effectiveness and reliability of our approach in privacy-sensitie settings.
Protection Act (CPPA, mand for mechanisms that allow the removal of specific data points from trained models.
Among these mechanisms, certified unlearning has emerged as comerstone, formalizing data removal with rigorous guarantees. In contrast heuristic methods, certified un- learning ensures that the influence of removed data is prov- ably eliminated from the model, offering both privacy com- pliance and practical utility. This is typically achieved by bounding the statistical discrepancy between a model re- trained without the forget data and an approximated model that simulates this retraining. While fully retraining a model from scratch on the retained data is a straightforward and rigorous solution, it becomes computationally prohibitive for large-scale models and frequent deletion requests. Cer- tified unlearning instead provides a practical alternative: it enables efficient, provably correct data removal without exhaustive retraining (Guo et al., 2019; Neel et al., 2021; Sekhari et al., 2021; Chien et al., 2024; Zhang et al., 2024).
Existing certified unlearning methods generally focus on two key aspects. First, they approximate the retrained model using an efficient technique, often leveraging a single-step Newton update (Guo et al., 2019; Sekhari et al., 2021: Zhang et al., 2024). Second, they inject noise based on differen- tial privacy (Dwork, 2006) Gaussian mechanism to ensure that the retrained and un- learned models are statistically indistinguishable. We adopt this single-step update approach in our work as it strikes a balance between efficiency, theoretical grounding, and em- pirical effectiveness, as supported by prior studies. Despite their promise, these methods often rely on the assumption that the source data remains accessible during unlearning.
concipple--ommmlly via a
1. Introduction
Machine learning models have achieved remarkable success across a wide range of applications by leveraging large-scale datasets. However, growing concerns about data privacy and regulatory requirements-suue as the General Data Protec-
A critical challenge arises when the unlearning mechanism has no access to the source data samples. This limitation may stem from privacy constraints, as the original model may have been trained by a different organization or a third party; resource restrictions, as old data may be deleted due to memory constraints; or regulatory barriers, as data retention policies or security concerns may prohibit storing the source data. As result, existing unlearning methods that rely on access to the source data become impractical or infeasible.
'Department of Electrical and Computer Engineering, University of California, Riverside, CA. USA 'Brookhaven National Laboratory, Upion, NY. USA. Correspondence to: Umit Yigit Basaran <umit, basaaaaaaaaannnnaa wwwwieemmaaiaaaaaa ucr.eduu. Sk Mi- raj Ahmed <sahme047 uee,,edu>, Amit Roy- -howChhyyyrry Camitre@ueredue Bayak Güler <bguler@ccc..u (eguulr@@ccc.urredu>>
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Certified Unlearning Approach without Access to Source Data
Consequently, a key open question emerges:
that uses D, in place of the source dataset D. Throughout the paper, we focus on classification models.
What if the unlearning mechanism has no access to the original training samples, and instead must rely entirely on a surrogate dataset that mimics these statis- tical properties to achieve certified unlearning?
Under typical assumptions (Assumption 4.1) about the loss function used to train the model, we prove that the norm of the difference between the model retrained from scratch over the original retain data, w and the model approximated with our unlearning mechanism using the surrogate dataset, wr, is upper bounded as (Theorem 4.2).
This problem is related to zero-shot unlearning, where no information about the true dataset available during for- getting, beyond the model. While several relevant methods (Foster et al., 2024; Chundawat et al., 2023; Cha et al., 2023) have been proposed, no theoretical guarantees exist.
|| - -0,,-,11 12 A
A more tractable scenario in practice is when the unlearning mechanism has access to a surrogate dataset that mimics the statistical properties of the source data up to a specified level of fidelity. Summary statistics, learned from this surrogate dataset, are then used to guide the unlearning process. For instance, consider a case where a person requests their data to be deleted, but the organization no longer retains the orig- inal training data due to regulatory or resource limitations. Instead, the organization uses publicly available data or pre- viously generated surrogate datasets that closely resemble the source data distribution to facilitate the unlearning pro- cess. Alternatively, the individual may provide new set of data samples (c.g.. images)-distine data but with some statistical cecereaanny-speccffeeee to facilitate the unlearning process.
where A is function of the statistical distance between the two distributions p and v. Then, by carefully scaling the noise as function of the statistical distance between p and v, we achieve certified unlearning without direct access to the retain data. Technical details are provided in Section 4.
Contributions. Our contributions are summarized below.
We propose certified unlearning mechanism to forget samples drawn from given distribution without hav- ing access to the true retain samples (from the source distribution). Instead, it relies on surrogate dataset D, sampled from a different distribution to ensure certified unlearning. This is the first work to provide certified unlearning guarantees when the source data not avail- able, offering a practical solution in scenarios where direct access to the source data is restricted.
from the source
In this work, we address precisely this scenario. We study certified unlearning when the unlearning mechanism has no access to source (retain) samples, but instead relies on samples from a surrogate dataset that mimics the source data up to fidelity criterion. Our goal is to establish formal certified unlearning guarantees during unlearning, and how the unlearning performance changes as a function of the distance between the surrogate and source data.
We establish rigorous certified unlearning guarantees that hinge on the statistical distance between the source data distribution and the surrogate data distribution
V. Our main theorem ensures that the influence of the unlearned data points is effectively removed while preserving provable bound.
For scenarios when the statistical (distance) informa- tion is not readily available between the source and surrogate datasets, we introduce a heuristic to approx- imate the distance between and v. Our approach uses only the model and surrogate dataset, without any information about the source statistics, making it well-suited for resource- limited environments.
Main Result. We propose a certified unlearning framework that does not require access to the original retain data sam- ples. Instead, we leverage surrogate dataset where the samples are generated from distribution that may be differ- ent from the original. By carefully scaling the noise based on the statistical distance between the source and surrogate datasets, we provide rigorous indistinguishabiiiy guaran- tees on how closely the unlearned model mimics the truly retrained model. These guarantees are explicitly dependent on the distance between the source and surrogate data.
We provide an extensive set of experiments, on both synthetic and real-world datasets, to demonstrate the effectiveness of our approach. In particular, we show how our noise-calibration procedure ensures certified unlearning while maintaining utility comparable to methods that assume full access to source data.
Formally, let 'D denote the source dataset drawn from dis- tribution p. whereas D. denotes surrogate dataset drawn from a distribution v. Both distributions share the support X x V. where X' represents the feature space and y repre- sents the label space. Suppose we want to remove set of samples D., from D. We define w. as the model retrained from scratch on the original retain data D,- D'D,, and w. as the model produced by our unlearning mechanism
2. Related Works
Certified Unlearning. Certified unlearning has become a key mechanism for data removal, offering rigorous privacy guarantees while avoiding full retraining costs. Existing methods typically rely on single-step Newton updates, influ- ence functions (Guo et al., 2019; Sekhari et al., 2021; Zhang
2

---

A Certified Unlearning Approach without Access to Source Data
al., 2024), or projected gradient descent algorithms (Neel et al., 2021; Chien et al., 2024) combined with a randomiza- tion mechanism for statistical indistinguishabiiity.
model w" directly the influence of Du is effectively removed. The goal is to construct an updated model w, that closely approximates the retrained model w while ensuring strong statistical indistinguishability guarantees.
Source-Free Unlearning. Zero-shot machine unlearning (Chundawat et al., 2023) removes data influence using only model weights and the forget set, using noise-based er- ror maximization and gated knowledge transfer. Another method (Cha et al., 2023) employs adversarial sample gener- ation to preserve decision boundaries while applying gradi- ent ascent on forget data. JiT unlearning (Foster et al., 2024) fine-tunes models with perturbed samples to reduce reliance on forget instances. Bonato et al. (Bonato et al., 2025) modify feature vectors to align forgotten data with the near- est incorrect class, using a surrogate dataset in source-free settings. Despite some recent work in sero-sho/ssource-fiee unlearning, formal certified guarantees remain an open prob- lem. We address this by ensuring such guarantees using surrogate dataset in the absence of source data.
Most existing certified approximate unlearning methods employ techniques such as influence functions (Guo et al., 2019). second-order Newton updates (Sekhari et al., 2021; Zhang et al., 2024), or other optimization methods (Chien et al., 2024; Neel et al., 2021) efficiently adjust w*. By incorporating carefully calibrated randomness, often through Gaussian mechanism inspired by differential pri- vacy (Dwork, 2006), approximate unlearning ensures that the statistical properties of w,, align with those of w,, up to a specified certification budget. In these approaches, an upper bound is placed on the norm of the difference between w and wr, which in turn determines the required noise variance. Details of the relation between differential privacy and certified unlearning are provided in Appendix B.
Formally, given a model w" trained on dataset D, the sam- ples to be unlearned Du, and additional statistical informa- tion S(D about D, the unlearning mechanism U produces an updated model w,. The mechanism 14 satisfies (e, 6)- certified unlearning if it adheres to the following guarantees.
3. Preliminaries and Problem Formulation
Certified Unlearning. Machine unlearning removes the influence of specific data points from a trained model while preserving its performance on the retained data. Certified unlearning formalizes this concept by offering rigorous prob- abilistic guarantees on the correctness and reliability of the unlearning process. In essence, it ensures that the adjusted model behaves as though it was fully retrained without the removed data, with bounded error relative the fully re- trained model. This contrasts with empirical unlearning techniques, which may be easier to implement but lack any formal assurances about the fidelity of the resulting model.
Definition 3.1 ((c, 8) -)-ertiffe Unlearning (Sekhari et al., 2021)). Given a learning mechanism A defined over the hypothesis space H. an unlearning mechanism If guarantees (e, 5) certified unlearning if and only if VT C H.
Pr ((D)( ET) Pe (CD. Pr P=(M(A,A(D))) ET) se ((D) E T) +
E ET) +6,
Let the original dataset D contain samples {ær y) each sampled from the joint distribution o with the support set X x y) Let the set of samples to be unlearned, D, C D, have size [Pal = m. Then, the retain set D,- = \ D,, has size [D+] = n m. A learning algorithm A takes D input and outputs model w' ADD). which minimizes the expected loss (<..))> [<x y), w)) where C( (z,,)). w) measures the error of the model w on the data sample (æx, v).
where S is a mechanism that returns statistical information about the given dataset to guide unlearning U.
Definition 3.1 ensures that the updated model w, is statis- tically indistinguishable from the retrained model wt. up to the parameters (c, We adopt the unlearning definition from (Sekhari et al., 2021) due to its versatility and practi- cal benefits. Unlike earlier definitions (Ginart et al., 2019), which rely on the unlearning algorithm being inherently randomized even when no deletions occur.
Having the trained model parameters w", unlearning can be examined under exact and approximate approaches:
1. Exact unlearning involves retraining the model from scratch the retained data D, (Bourtoule et al., 2021; Ullah et al., 2021; Dukler et al., 2023), which guarantees complete removal of D,, 's influence but is often computa- tionally infeasible. This motivated approximate unlearning methods to replicate exact unlearning at a reduced cost.
Second-order unlearning. For certified unlearning, S(-) typically represents detailed information about the true data samples (Guo et al., 2019; Neel et al., 2021; Sekhari et al., 2021; Chien et al., 2024; Zhang et al., 2024). A common approach is to utilize the second-order Newton update, for which S()) refers to the Hessian of D, evaluated on the trained model wt (Sekhari et al., 2021; Zhang et al., 2024). These approaches follow a general methodology consisting
2. Certified Approximate Unlearning provides practical approach to certified unlearning by relaxing the requirement of retraining from scratch. Instead, it modifies the trained
3

---

A Certified Unlearning Approach without Access to Source Data
of updating the model with a single-step Newton update,
Details of these assumptions are provided in Appendix A. We next describe our individual steps.
w f w
m
WV",,,""" D.
1. Hessian estimation. Our mechanism approximates the model retrained from scratch, i.e., trained only on the re- tained samples of the source dataset, by using the surrogate dataset and a one-step second-order Newton update.
m
and then injecting noise (commonly Gaussian) to the up- dated model, which is calibrated with respect to an upper bound on the norm difference between W. and Wr. The details on certified unlearning mechanisms utilizing second- order Newton updates are given under Appendix B.I.
The second-order Newton update is the product of the in- verse Hessian and the gradient vector, both evaluated w", the model trained on the training dataset D. If the original retain data D, was available, the update would be, wr = ~ Hp.VL(D, w*). Since D, is unavailable, we approximate its Hessian as
This work. In contrast to the conventional certified un- learning problem, in our scenario the unlearning mechanism only has access to the surrogate dataset a,, opposed to the source dataset D. Our goal is then to develop a certi- fied unlearning mechanism with only access to D,, In the next section, we present a novel approach to address this challenge, where we propose a novel Gaussian mechanism building on second-order Newton update, where the noise calibrated as a function of the statistical distance between the source and surrogate data distributions, without having access to the original training set. In scenarios where the statistical distance is not readily available, we demonstrate a simple methodology to estimate this by using the model. While providing strong theoretical guarantees, our approach versatile and can be applied to a wide range of unlearn- ing algorithms that use single-step second-order Newton update as the approximation method.
Нo. nHo - HH n m
2. Model update. Using the estimated Hessian Hp,, we then update the model. The update also re- quires VL(D,, w²), which we express using the fact that CL(D,, w²) = 0 for the fully trained model and therefore,
VL(DP, w') m
- L( w
(2)
m
Substituting (1) and (2) into the second-orde Newton up- date yields our model update for unlearning,
w = 20
m
H D.
VL(DD, w²)
m
4. Methodology
3. Noise calibration. To ensure certified unlearning, we then introduce Gaussian mechanism with the noise scaled according to: 1) an upper bound on ||w 0, 2) fidelity criterion based on the statistical distance between the source and surrogate data distributions. Specifically, the final model is given by,
Our approach consists of the following key steps:
1. (Hessian estimation.) Our approach builds on second- order unlearning. which requires the Hessian of the source dataset update the model for forgetting. As we do not have access to the source data, we estimate the true Hessian HD using the Hessian of the surrogate dataset Hp,, Using the surrogate Hessian, we estimate the true Hessian HD, of the retain samples D,.
C. +
where n ~ NO, o²I) such that,
2. (Model update.) Using the estimated Hessian HD, of the retain samples, we update the model w* (trained on D) using a single-step second-order Newton update.
o = A
2lm(1.25/8)
(4)
3. (Noise calibration.) Finally, we employ a Gaussian mechanism adding noise n to the updated model w. calibrate the noise using an upper bound on the L2 norm distance between the estimated model w, and the true unlearned model w along with the total variation distance TV(p || p) between the source and surrogate datasets.
and
||., - 0rll2 S
To ensure certified unlearning,
P 2yLm² 2
+ (IVC(D,, w²)l2
a'n
m m(n1 (n] - n2) + 2m (p (nia - mm3)(naa - -m1))
(5)
Before we describe the details of these steps, we first provide useful technical assumption.
to achieve (e, 8)-cetiified unlcarning. Algorithm presents the individual steps for our certified unlearning mechanism U. We next provide the theoretical justification behind (4)
Assumption 4.1. The loss function L used during the train- ing of the model parameters is L-Lipschitz, a-strongly con- vex, f-smooth, and -eessia Lipschitz.
and (5) in Theorem 4.2 and Theorem 4.3.
4

---

A Certified Unlearning Approach without Access to Source Data
Algorithm I Unlearning Mechanism Leveraging Surrogate
introduce a heuristic method approximate this distance (or an upper bound) using only Dz and the trained model w". This enables the implementation of Algorithm I with- out direct access to D, which is crucial for privacy-sensitive applications and real-world deployments.
Data Statistics
Require:
Unlearning dataset Du. trained model parameters w" (from A(D)), data statistics S(D,) : Hp,, upper bound A, privacy parameters e, 5
Ensure: Updated model parameters w³ after unlearning
1: Compute o = 2 (n((21////) 1.25/0)
4.2. From Theory to Practice
2: Compute HD, nHo, -mHp..
In this section, we first propose an upper bound using Kullback-Leibler (KL) divergence. While total variation distance would be preferable, we use KL for efficiency due to no access to D. Next, we approximate KL without direct access to exact samples by training a model on D, and uti- lizing models conditional probabilities. We sample from input marginal distribution using energy-based modeling to compute the KL. Finally, we estimate the KL between input marginal distributions using the Donsker-Varadhan varia- tional representation (Donsker & Varadhan, 1983). The details these steps are explained below.
m
3: Update w, w" " + m
A. V
n-m
4: Sample 12 ~ N(, I
5: Return 80 = in + n
4.1. Theoretical Principles
In this section we provide the theoretical intuition behind our mechanism. In Theorem 4.2, we derive an upper bound on the difference between the true retrained model w,, trained from scratch on the retain data D,., and the approximate model w, which uses the surrogate data D... This bound is formulated in terms of the total variation distance TV(p || v) between the source and surrogate data distributions.
To apply the bound in Theorem 4.2, we require the exact total variation distance TV v) practice, we approximate this bound using the KL diver- gence, leveraging heuristics outlined in this section. In Corollary 4.4, we provide an upper bound based on the KL divergence between surrogate and source data distributions. Corollary 4.4. Under the same assumptions and definitions in Theorem 4.2, the following upper bound holds:
upper bound. In
Theorem 4.2. Consider a loss function L satisfying Assump- tion 4.1, and a surrogate dataset D, with n2 samples drawn from a distribution u, to mimic the source datasel 'D with nn drawn from a distribution p. over the support set X x V. Define the retrained model over the retain samples as w. and the model achieved after unlearning as i.-- Also, as- sume that ny and n2 are sufficiently large and n1, n2 2 m8 Then, the following upper bound holds,
Ly
|IVL(Du, wn) w>)l2
- 0 S
+
a²n²
I!=; - -wrl12 S A
m(n1 - -22) + 2mm2 - eexexp--KL( p))
(n1a mm) m33)
where A is as defined in (5).
Proof. The proof is available in Appendix D.I.
Proof. The proof is provided in Appendix C.
To approximate KL || p). we leverage the model w trained on the entire dataset D. Let f(w, x)) denote the probability simplex over classes parameterized by the model w for a sample æ. with f(ur, x) representing the proba- bility of class y. Assuming w" is the model trained on the surrogate dataset D.,, the KI. divergence can be decomposed as shown in Proposition 4.5.
The next theorem presents our certified unlearning guaran- tees under a given privacy budget e and confidence 8 when noise scaled by A is added to the approximate model in (3). Theorem 4.3. Consider a dataset D where data samples follow the distribution p. and a surrogate dataset DD where data samples follow the distribution v. Given a forget set Di, C C,D, and the hypothesis set H. the unlearning mecha- nism U satisfies (E, (ceertifd unlearning.
Proposition 4.5. Let f(w,x) output probability simplex over classes for data sample x, parameterized by w. Given trained models w and w such that w is trained on 'D and un on Da, where data samples from DD and D follow distributions p and v, the KL divergence KL(v ()) can be decomposed as.
Proof. The proof is provided in Appendix C.I.
Thus, when TV || v) is large, the noise magnitude increases, ensuring certified guarantees even when the sur- rogate distribution significantly differs from the source.
(T
1
Σ (x.)ED
log flw", x), f(w" x)
A key challenge is estimating (or upper bounding) Tv || v) without access to D. In the next section, we
+ (L(v(x) p(x))
5

---

A Certified Unlearning Approach without Access to Source Data
Proof. The derivation is given in Appendix D.2.
can be approximated as,
Proposition 4.5 decomposes the KL divergence into two components: (I) divergence between conditional distribu- tions, which we can approximate using the classifiers, and (2) divergence between input marginal distributions.
(L(v(x) |l ((x)) vo sup
T(x:)
T i=1
log
(xp(T(ā)))
k: j=1
To estimate the latter, we leverage the hidden energy-based model in the classifier w" to sample from the true input marginal distribution p(ar). These samples, combined with the surrogate dataset, enable us approximate the KL di- vergence between marginal distributions. The next section details the technical steps for sampling from p(z) using only the trained model parameters.
Finally, building on this result, we refine the decomposition of the KL divergence from Proposition 4.5 to explicitly account for the approximation of KL(v p) as follows.
Proposition 4.6. Consider the setting from Proposition 4.5 and assume KT.(v || p) is approximated using sampling from p(x) and the Donsker- Varadhan variational representation described in (6). The KL(v || D) can then be expressed as,
Sampling from input marginal distribution. Inspired by (Grathwohl al., 2019), we leverage the implicit energy- based model of the trained model w" to sample from the approximated input marginal distribution p(x² given by:
KL p)
1
Σ
log f(io" x)y
f(w0, x)y
(2.y)ED.
p(x) exp(-E(x))
1 T(x,) - loog
T Σ (ex((((2.)))
+ sup T
where the energy function is defined as E(x) - -log Eyey exp(f(w", x)y)). Here, f(w", x)) denotes the logit score for label y under w", and the summation runs over the label space V
In our experiments, we demonstrate our evaluations with both synthetic and real-world datasets, For the latter, SGLD sampling and Proposition 4.6 will be instrumental in our experiments with real-world datasets.
To sample from p(æ), we employ Stochastic Gradient Langevin Dynamics (SGLD), which iteratively refines sam- ples without explicitly computing the normalization con- stant Z. These samples, combined with the surrogate data, allow us to approximate the input marginal KI. divergence.
5. Experiments
We systematically evaluate our approach on synthetic and real-world datasets to demonstrate its effectiveness in achieving certified unlearning. Unless otherwise noted, we adopt linear training model with forget ratio of 0.1, and an Le regularization constant X 0.01. The loss function is assumed to be a-strongly convex, L-Lipschitz, 3-smooth, and H-Hessian Lipschitz. In line with prior works (Koh & Liang 2017; Wu et al., 2023b;a; Zhang et al., 2024) we tune a, L, B, and y for each experimental setting, which preserves theoretical soundness but may lead to approxi- mate certifications. All details about the parameter study and implementation are given under Appendix E.
In the next section, we present how estimate this diver- gence using variational representation, ensuring a practical approach for our unlearning mechanism. Further details on the energy- based modeling, SGLD sampling procedure, and convergence criteria can be found in Appendix D.3.
Approximating KL Distance Between Input Marginal Dis- tributions. After generating samples from the approximated source distribution p(x) using Langevin dynamics, we ap- proximate the KL divergence between the surrogate dis- tribution and the approximated source distribution á by leveraging the Donsker- Varadhan variational representation,
We now turn to our empirical evaluation. where we assess the effectiveness of our approach through a series of experi- ments. We first provide explanations about the evaluation metrics used to evaluate our unlearning mechanism. Then, we provide synthetic and real- weal-world dataset experiments. In addition to that, we also investigate our methodology over di different setups to demonstrate its effectiveness.
(T(((()) ll (())) = sup Ex~ [T(X)
T
(6)
log Ex~p [exp(T((X)]
where T is variational function, parametrized by neural network, that maps input samples to real-valued scores.
To approximate the expectations in (6), we rely on the sam- ples generated through Langevin dynamics. Given sam- ples sampled from p(z). forming a set { and n sam- ples from v(x)) forming the set ( the KI. divergence
Performance Metrics. We evaluate the performance using train, test, retain, and forget accuracies on their respective data splits. Additionally, we employ the unlearning specific membership inference attack (MIA) (Kurmanji et al., 2023),
6

---

A Certified Unlearning Approach without Access to Source Data
Method
Train
Test
Retain
Forget
MIA
RT
[1
Retrain
77.0 %
72.0 %
77.4% %
73.6 %
47.63 %
10
6.
Unlcarn (+) 77.1 %
72.6 %
77.5 %
74.1 %
47.63 %
10
Fogue Syones
0.02
0.04
Unlearn (-) 77.3 % 72.4 %
Unlearn (+)
77.2 % 72.2 %
77.5 %
77.6 %
74.4 %
74.8 %
48,89 %
48.89 %
10
7
4,0
5.0
10
PRI
0.06
Unlearn (-) 77.3 % 72.2
77.6 %
74.3 %
48.37 %
10
3.8
0.08
Unlearn (-) 77.3 % 72.4
77.6 %
74.4
%
48.15
%
10
30
0.1
Unlearn (-) 77.3 % 72.7
77.7 %
74.1
48.30
%
25
6m
0122
6.04
0.90
0.10
0.1
002
0D1
008
045
0.10
Table 1. Evaluation of unlearning performance while varying the off off-diagonal elements (() of the unit covariance.
(a) Required noise variance σ
(b) Forget scores
Figure I. (a): Required variance o for achieving certified unlearn- ing on synthetic datasets a function of the off- diagonal elements (O). (b): Forget scores achieved for synthetic datasets.
where accuracy of 50% means the attack can not distin- guish whether a specific sample belongs to the forget test dataset. Relearn time (RT) (Golatkar et al., 2020) measures how many additional training iterations are required to re- store the model's performance on the forgotten data after is reintroduced. Intuitively, the unlearned model should give high relearn time scores which indicates the model effectively unlearns the forget dataset. Finally, we report the forget score (FS) (Triantafillou al., 2024), which quan- tifies how closely the predictions of the unlearned model align with those of a model retrained from scratch. A higher forget score indicates stronger unlearning and higher indis- tinguishability between retrained and unlearned models.
(SL(+) X 6:33
3.
FSL C:30
3.8
32
Ricert Scores
28
2.
2.4
22
13
CIFAR
Statinlllags
(a) Required noise variance o
(b) Forget scores
Figure 2. (a): Required variance a for achieving certified unlearn- ing across CIFARIO, StanfordDogs, and Caltech256 datasets as function of the concentration parameter &. (b): Forget scores achieved for CIFARIO, StanfordDogs, and Caltech256.
Overall, we denote our method as "Unlearn (-)" indicating no access the statistical information about the source data, unlearning method utilizing statistical information about the source data as "Unlearn (+)" and the model retrained from scratch over the retain data as "Retrain". Also, we report three FS variants: "FS1 (+)" applies the noise required by Unlearn (+), "FS1 (-)" applics the noise required by our proposed Unlearn (-), and "FS2 (-)" applies the noise from Unlearn (+) Unlearn (-). Comparing these scores demon- strates that our proposed approach is required to achieve certified unlearning while utilizing surrogate dataset.
the others, implying that to achieve similar certification with Unlearn (+), our proposed noise is required. We report addi- tional experiments using different random seeds along with corresponding error bars in Appendix F.
Real- Real-World World Dataset Experiments. We further evaluate method on CIFAR1O (Krizhevsky et al., 2009), Caltech256 (Griffin et al., 2007), and StanfordDogs (Khosla et al., 2011) 1), by dividing each dataset into an source and a surrogate sub- set according to a Dirichlet distribution with concentration Ç. Lower values of & lead to more skewed class splits and thus greater distributional divergences. We show these results in Figure 2(a). We observe that the required noise variance de- creases while increasing the concentration parameter &. We approximate the KL distance between source and surrogate datasets without accessing source data by using Proposi- tion 4.6. We use embeddings from a ResNet18 (He et al., 2016) model, following (Guo et al., 2019).
Synthetic Experiments. We generate an source dataset of 1 15000 samples from a 50-dimensional standard Gaussian, (O I). A corresponding surrogate dataset of the same size drawn from N(0.<1 (< + 1)I), where Ç E [0.01, 0.1] controls the off-diagonal covariance terms. Varying ( mod- ulates the KL divergence between the source and surro- gate distributions, influencing the noise variance needed for certified unlearning. As demonstrated in Figure I(a), the required noise variance is increased following Theorem 4.2.
Table reports train, test, retain, and forget accuracies along- side the MIA score and RT. Despite the required noise in- creasing with larger KL divergence, our method Unlearn (-) achieves utility comparable to other methods. These results underscore that appropriately scaling noise according to dis- tributional distance can preserve model performance while guaranteeing unlearning. From the forget scores given in Figure 1(b), we observe that while FS1 (+) and FS1 (-) can achieve similar forget scores, FS2 (-) is always lower than
In Table 2 we report the train, test, retain, and forget ac- curacies for all datasets. Our method Unlearn (-) achieves comparable accuracy over all data splits similar to other methods while utilizing only the surrogate datasets. We also report the MIA and RT metrics in Table 3 showing that our unlearning performance is close to the other methods. Finally, in Figure 2(b) we demonstrate the forget scores for
7

---

A Certified Unlearning Approach without Access to Source Data
CIFAR-10
StanfordDogs
Caltech256
Method
Train
Test
Retain
Forget
Train
Test
Retain
Forget
Train
Test
Retain
Forget
Retrain
77.6 %
76.2 %
77.8 %
76.0% %
86.1 %
73.7 %
87.3 %
75.2 %
87.1 %
72.0 %
88.8 %
72.2 %
13
Unlearn (+)
77.9 %
76.4 %
78.0 %
76.3% %
84.1 %
71.9 %
85.3 %
73.2 %
86.8 %
70.8 %
88.6 %
71.2 %
Unlearn (-)
77.5 %
76.1 %
77.7 %
75.8 %
84.0 %
72.2 %
85.2 %
73.1 %
87.0 %
71.5 %
88.4 %
74,6 %
Retrain
78.0 %
76.7 %
78.2 %
76.5 %
84,6 %
75.1 %
86.0 %
71.4
84.9 %
74.6 %
86.2 %
73.3 %
36
Unlearn (+)
77.4 %
76.5 %
77.6 %
75.7 %
84.5
75.6 %
85.9 %
71.7
84.7 %
73.2 %
86.0 %
73.8 %
Unlearn
77.3 %
76.4
77.5 %
75.7 %
84.4
75.7 %
85.8 %
72.0
84.9 %
73.5 %
86.0
74.9 %
Retrain
78.0 %
76.9 %
78.0 %
77.8 %
82.9 %
76.0 %
84.2 %
71.1 %
83.5 %
74.1 %
84.7 %
73.3 %
100
Unlearn (+)
78.2 %
77.3 %
78.3 %
77.2 9
83.8 %
75.7 %
85.1 %
72.2 %
82.1 %
73.0 %
83.2 %
72.8 %
Unlearn (-)
78.1 %
77.2 %
78.1 %
77.3 %
83.7 %
75.6 %
85.0 %
72.0 %
82.0 %
72.8 %
83.0 %
72.9 %
Table Train, test, retain, forget accuracies for each method across CIFARIO, StanfordDogs, and Caltech256 datasets while varying the concentration parameter (5) of the Dirichlet distribution.
CIFAR-10
StanfordDogs
C5ltech256
FR
Method
Train
Test
Retain
Forget
MIA
RT
Method
MIA
RT
MIA
RT
MIA
RT
Retrain
87.1 %
73.7 %
87.2 %
73.8 %
52.1 %
10
Retrain
51.14 %
14
51.95 %
70
50.97 %
20
0.01
Unlearn (+)
87.3 %
74.1 %
87.3 %
74.5 %
53.2 %
10
Unlearn (+)
52.68 %
10
51.61 %
15
51.20 %
20
Unlearn (-)
87.1 %
74.1 %
87.2
74.1
53.1
10
Unlearn (+)
52.59 %
51.49 %
15
52.00 %
16
Retrain
82.9 %
76.0 %
84.2 %
71.1 %
52.5 %
19
Retrain
49.97 %
2
50.87 %
20
50.21 %
21
0.1
Unlearn (+)
83.8 %
75.7 %
85.1 %
72.2 %
52.0 %
21
36
Unlearn (+)
50.15 %
10
50.05 %
18
47.39 %
21
Unlearn (-)
83.7 %
75.6 %
85.0 %
72.0
51.9
16
Unlearn (-)
49.80 %
6
50.14 %
19
50.46 %
17
Retrain
85.6 %
72.4 %
88.7 %
73.3 %
50.6 %
40
Retrain
49.76 %
52,49 %
19
48.01 %
17
100
Unlearn (+)
48.90 %
13
52.02 %
21
52.05
%
16
0.2
Unlearn (+) 84.9 %
71.8 %
88.3 %
71.5 %
51.8 %
40
Unlearn (+)
48.83 %
32
51.94 %
16
52.33
%
14
Unlearn (-)
85.0 %
71.4 %
88.0 %
72.6
52.0
40
Table 3. MIA and RT metrics given for each method across CI- FARIO, StanfordDogs, and Caltech256 datasets while varying the concentration parameter (E) of the Dirichlet distribution.
Table 4, Evaluation of unlcarning performance across varying for- get ratios (FR) on StanfordDogs dataset with E = 100.
network using a first-order Taylor expansion. Specifically, the network output is approximated via its Neural Tangent Kernel (Jacot et al., 2018) formulation, transforming the objective into a convex optimization problem. This approxi- mation allows for efficient and tractable unlearning while preserving much of the model's predictive performance.
all datasets and selected concentration parameters. This implies the necessity of our noise scaling approach while using a surrogate dataset to achieve certified unlearning.
Additional experiments with different random seeds, cor- responding error bars, and evaluations of our heuristic KL approximation-ure for noise calibration without access- ing the source data-against KL estimates via the Donsker- Varadhan method (with data access) are reported in Ap- pendix F, highlighting the gap between practical estimation and the exact quantity required for certified unlearning.
In Table 5, we report results on CIFAR-10 under two set- tings using this architecture. One with randomly selecting 10% of the data as forget set and the other with removing all samples belonging to class O. In both cases, our method achieves effective certified unlearning and maintains com- petitive accuracy the retained data, demonstrating that mixed linear networks provide practical and theoretically sound foundation for unlearning in neural models. MIA
Experiments with Different Forget Ratios. We conducted extensive experiments the StanfordDogs dataset with varying forget ratios to assess how forget ratio impacts learning. The results in Table 4 show that our method Un- learn (-) scales well across different forget set ratios. Also, results under the MIA and RT' columns indicate that similar unlearning performance is achieved across different forget ratios with Unlearn (+) and Retrain models. These findings confirm the robustness of our approach.
Method
Train
Test
Retain
Forget
MIA
RT
Retrain
93.6 %
86.4 %
95.6 %
84.7 %
51.2 %
53
0.1
Unleam (+) 93.7 %
86.4 %
94.8 %
87.2 %
51.3 %
54
Unlearn (-)
94.1 %
85.2 %
94.9 %
86.8 %
52.1 %
54
Reirain
81.7 72.3 %
92.7 %
0
142
0
Unleam (+) 82.2 %
72.5 %
93.2 %
4.2 %
135
Hiixed-Linat Network Experiments. While the convexity and smoothness assumptions in Assumption 4.1 may not hold for general neural networks, there exist practical archi- tectures that satisfy these conditions while retaining strong utility. To this end, we adopt the mixed-lineal networks (Golatkar et al., 2021), which linearizes a pre-trained neural
Unlearn (-) 82.4 %
72.4 %
93.5 %
5.1 %
132
Table 5. Evaluation of unlearning performance on CIFAR-10 using mixed-linea -inear networks with & = 100. In this table, "0.1" indicates that 10% of the data is used as the forget set, and "0" denotes the class selected for unlcarning.
8

---

A Certified Unlearning Approach without Access to Source Data
Arch
Method
Train
Test
Retain
Forget
MIA
RT
6. Conclusion
Retrain
78.0 %
76.9 %
78.0 %
77.8 %
49.76 %
7
L
Unlcarn (+)
78.2 %
77.3 %
78.3 %
77.2 %
48,90 %
13
We introduce a certified unlearning framework that enables data removal without requiring access to the original train- ing data statisties. Unlike existing methods, our approach utilizes surrogate dataset and calibrates noise based on sta- tistical distance, ensuring provable guarantees. We establish theoretical bounds, develop a practical noise-scaling mech- anism, and validate our method through experiments on synthetic and weal-world datasets. Our results demonstrate certified unlearning can be achieved by utilizing a surrogate dataset while maintaining utility and privacy guarantees.
Unlearn (-)
78.1 %
77.2 %
78.1 %
77.3 %
48.83 %
32
Retrain
81.6 %
79.8 %
82.1 %
78.4 %
49,94 %
40
C+L
Unlearn (+)
80.8 %
78.4 %
81.3 %
78.1 %
51.32 %
45
Unlearn (-)
80.5 %
78.1
80.9 %
77.5 %
50.71 %
46
Retrain
83.0 %
80.3
83.1 %
81.2
50.86 %
2C+L
Unlearn (+) 84.3 %
81.4
84.3 %
81.7
51.28 %
Unlearn (-) 82.9 % 80.5
83.1 %
81.1 %
50.05 %
22
Table 6. Evaluation of unlearning performance across different model architectures: a single linear layer (L). a convolutional layer followed by a linear layer (C+L., and two convolutional layers followed by a linear layer (2C+Linn).
Software
scores are omitted for class unlearning because the attack is designed to distinguish between test and forget samples; forgetting an entire class greatly increases distinguishability, making the MIA score uninformative.
Our main implementation used for this paper is available at
inmm/inffour////// surr-data, We also im- plemented the mixed-linear networks (Golatkar et al., 2021) from scratch, the code is available at httpp::// /wtue///mxedeeee http:///woouuoooaaoccccceoaaaaap privacy-forgetteeee
Unlearning Across Model Architectures. To evaluate the generality of our approach, we train three different archi- tectures on CIFAR- 10 using a Dirichlet concentration of {=100: a single linear layer ("L"), convolutional layer followed by linear layer ("C+L"), and two convolutional layers with linear layer ("2C+L"), As shown in Table 6, our method maintains accuracy comparable to others, while keeping the MIA score close to 50%. Also, the RT metric implies that the unlearning succeeded in removing the influ- ence of the forget samples. Finally, for the C+L architecture, the observed FS1 (+), FS1 (-), and FS2 (-) values are 0.08, 0.08, and 0.05, respectively, while for 2C+L, they are lower at 0.04, 0.04, and 0.02. These results reinforce that the introduced noise is essential for the unlearning process.
Acknowledgements
This work was supported in part by the NSF CAREER Award CCF-2144927, NSF Award CCF-2008020, DURIP 1000141812252, the UCR OASIS Fellowship, and the Ama- zon Research Award.
Impact Statement
Unlearning is increasingly critical due to evolving privacy regulations, such as GDPR, CCPA and CPPA, which man- date mechanisms to effectively erase private or sensitive data from trained machine learning models. Retraining these models from scratch to remove specific data points is computationally infeasible. Traditional unlearning methods circumvent exhaustive retraining but typically require full access to the original source data, an assumption often unre- alistic in practical scenarios due to privacy concerns, storage limitations, or regulatory restrictions on data retention. Our work directly addresses this crucial gap by proposing a certi- fied unlearning framework that does not rely on the availabil- ity of original training data. Instead, we leverage surrogate datasets that approximate the original data distribution to guide the unlearning process. By carefully calibrating noise injection based on statistical distances between original and surrogate datasets, our method ensures rigorous theoretical guarantees on unlearning performance, thereby providing a principled alternative to heuristic methods. This approach significantly broadens the practical applicability of certified unlearning methods, ensuring compliance with privacy re- quirements even when access to original training data is restricted or completely unavailable.
MNIST-USPS Experiment. To illustrate our contribution in a practical setting, we consider MNIST (Lecun et al., 1998) and USPS (Hull, 1994) datasets and analyze the following cases. First, we train a model on MNIST and apply our unlearning framework by selecting random forget set from MNIST while using USPS as the surrogate dataset (M -> U). Second, we reverse the process, training a model on USPS and unlearning with MNIST as the surrogate (U + M).
As can be seen from Table 7, in both cases the unlearning performance of our method Unlearn (-) is similar to the other methods we are comparing with.
Task Method
Train
Test
Retain
Forget
MIA
RT
Retrain
94.2 % 91.4% %
94.3 %
92.5 %
51.23 %
11
Unleam (+) 94.1 5 91.3 %
94.1 %
90.7 %
50.15 %
13
Unlearn (-)
94.1 %
91.1
94.1 %
91.5
50.54 %
Retrain
95.2 56 91.1 %
95.1 %
92.9 %
50.71 %
21
Unlear (+) 93.7 % 91.3
95.3 %
91.7
$1.93 %
Unlearn (-) 93.5 % 90.4 %
94.9 %
90.9 %
50.60 %
23
Table Evaluation of unicarning performance with MNIST and USPS datasct experiments.
9

---

A Certified Unlearning Approach without Access to Source Data
References
Donsker, M. D. and Varadhan, S. S. Asymptotic evaluation of certain markov process expectations for large time. iv. Communications pure and applied mathematics, 36 (2):183-212, 1983.
Bonato, J.. Cotogni, M., and Sabetta, L. Is Retain Set All You Need in Machine Unlearning? Restoring Perfor- mance of Unlearned Models with Out-of Ditoof-Distribution Images. In Leonardis, A., Ricci, E., Roth, S., Rus- sakovsky, O., Sattler, T., and Varol, G. (eds.), Computer Vision ECCV 2024, pp. 1-19, Cham, 2025. Springer Nature Switzerland. ISBN 978-3-031-73232-4 doi: 10.1007/978-3-031-732222222
Dukler, Y., Bowman, B., Achille, A., Golatkar, A., Swami- nathan, A., and Soatto, S. Safe: Machine unlearning with shard graphs. In Proceedings of the IEEE/CVF Interna- tional Conference on Computer Vision, pp. 17108-17111 2023.
Bourtoule, L.., Chandrasekaran, V., Choquette-Choo, C. A.,
Dwork, C. Differential privacy. In International colloquium automata, languages, and programming, pp. 1-12. Springer, 2006.
Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141-159, 2021. doi: 10. 1109/SP40001.202 0000000...22..000 100019.
Foster, J., Fogarty, K., Schoepf, S., Dugue, Z.., Öztireli, C., and Brintrup, An Information Theoretic Approach Machine Unlearning, December 2024. URL http:// a arxiv. or..orgg//aa httrg/bbs/aa /402 01 01401. arXiv:2402.01401 [cs].
Bretagnolle, and Huber, C. Estimation des densités: risque minimax. Zeitschrifi für Waahrchhennicckeessseeeri und Verwandte Gehiete, 17-7):19-137, Jan 1979. ISSN 1432- 2064. doi: 10.11007/B30005352778 URL https://doi. org/10 1tw.10000//0005575555
GDPR. General Data Protection Regulation (GDPR) Legal Text, 2016. URL https:://cdpp-iinnnn eu/-
CCPA. California Consumer Privacy Act (CCPA), Octo- ber 2018. URL https://oag. ca. gov. /orrpa/ copa.
Ginart, A., Guan, M., Valiant, G., and Zou, Y. Making ai forget you: Data deletion in machine learning. Advances in neural information processing systems, 32, 2019.
Cha, S., Cho, S., Hwang, D., Lee, H., Moon, T., and Lee, M. Learning to Unlearn: Instance-wise Unlearning for Pre-trained Classifiers. Proceedings of the AAAI Con- ference on Artificial Intelligence, 1111)):1188-11144 January 2023. ISSN 23743468.
Golatkar, A., Achille, A., and Soatto, S. Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 9304-9312, 2020. URL https: /opna//cepp.c.sss.eeeeessessssse theevf. http://ccooooottttct//oe 2020 /html/ Golattker_tterma___Snsshiieeee
doi: 10.1609/aaai. v38910.28996. URL https: /ttps:///axxvv //aaiiiv... org/ abs/ 2301 11578v3. arXiv: 2301.11578 Publisher: As- sociation for the Advancement of Artificial Intelligence.
Chien, E., Wang, H., Chen, Z., and Li, P. Langevin Un- learning: New Perspective of Noisy Gradient Descent for Machine Unlearning, February 2024. URL http::ttt// :// arxiv. org/ abs 2401 10371. arXiv:2401.1037 [es].
opotless_Net_Sellccivve___ Deep_cVPR_2020__20 2er__ccr__2020ppppeeehhae
in_
Golatkar, A., Achille, A., Ravichandran, A., Polito, M., and Soatto, S. Mixed-privacy forgetting in deep networks. In
Chundawat, V. S., Tarun, A. K., Mandal, M., and Kankan- halli, M. Zero-Sher Machine Unlearning. IEEE Transac- fions Information Forensics and Security 18:2345- 2354, 2023. ISSN 1556-6021. doi: 10.1109/TIFS. 2023.32 2023.3265506. https: htattps://eeeexploors ieee. org/ htr/abstracch /ww.d/ot//////////c/oo/ooo mattmeennn1009553. Confer- ence Name: IEEE Transactions on Information Forensics and Security.
Proceedings of the IEEF/CVF conference computer vision and pattern recognition, pp. 792-801, 2021.
Grathwohl, W., Wang, K.-C,, Jacobsen, J.-H., Duvenaud, D., Norouzi, M., and Swersky, K. Your classifier is secretly an energy based model and you should treat it like one. In International Conference on Learning Representations, September 2019. URL https:
//oppp/err..eeeeee///aaaeo.oooee utm wtw.caaaaaiigippppeeeeet..e..eee otm_source=RRevvee
CPPA. Consumer Privacy Protection Act, March 2023. URL
canada. consummer-ppivvaayy-poootttttttt
ca/site/ ht/aatee/mmovatooo--etteeeeeeeee
Last
Griffin, G., Holub, A., and Perona, P. Caltech-256 object category dataset. Technical report, California Institute of Technology, 2007.
Modified: 2023-03-13 Publisher: Innovation, Science and Economic Development Canada.
10

---

A Certified Unlearning Approach without Access to Source Data
Guo, C., Goldstein, T., Hannun, A., and der Maaten, L. Certified Data Removal from Machine Learning Models. In 37th International Conference on Machine Learning. ICML 2020, volume PartF168147-5, pp. 3790- 3800, November 2019. ht.p::: //axriiii ..v.oooog/////oooooo.o........ro abs/1911. 03030v5. arXiv: 1911.03030 Publisher: International Machine Learning Society (IMLS) ISBN: 9781713821 120.
Neel, S., Roth, A., and Sharifi-Malvjjerde S. Descent-to- Delete: Gradient-Basee Methods for Machine Unlearn- ing. In Proceedings of the 32nd International Conference on Algorithuic Learning Theory, pp. 931-962. PMLR, March 2021. URL https: http:poiceenng....moom.e....o mmlr. press/v132 httes//v32//eeeeee http//eeeeel..a....m html. ISSN: 2640-3498.
Sekhari, A., Acharya, J., Kamath, G., and Suresh, A. T. Remember What You Want to Forget: Al- gorithms for Machine Unlearning. In Advances in Neural Information Processing Systems, vol- ume 34, pp. 18075-18086. Curran Associates, Inc., 2021. URL https: https://proceeding
He, K., Zhang. X., Ren, S., and Sun, Deep residual learn- ing for image recognition. In Proceedings of the IEEE Conference Computer Vision and Puttern Recognition (CVPR), June 2016.
neurips httppcaaee////2//aaaaaaas 9627c55aff433e11aaa4f444888 aat.aaaaaaaab--b-baaat... Abstract. html.
Hull, J. A database for handwritten text recognition re- search. IEEE Transactions on Pattern Analysis and Ma- chine Intelligence, 1665):550-554, 1994. doi: 10. 109/ 34.291440.
Triantafillou, E., Kairouz, P., Pedregosa, F., Hayes, J., Kurmanji, M., Zhao, K., Dumoulin, V., Junior, J. J., Mitliagkas, I., Wan, J., et al. Are making progress in unlearning? findings from the first neurips unlearning competition. arXiv preprint 2XXv:2406.099773 2024.
Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Process- ing Systems, volume 31. Curran Associates, Inc., neurips.
Ullah, E., Mai, T., Rao, A., Rossi, R. A., and Arora, R. Machine Unlearning via Algorithmii Stabil- ity. In Proceedings of Thirty Fourth Conference PMLR, July on Learning Theory, pp. .gw.mnl..mmm....m....mmmmm..mmm. www..mmrr.pprrrrm press/ 2021. httsttss: http::///o/eediicoocccooc 1/34/ulaah21a.111 html. ISSN: 2640-3498.
2018. URL
cc cc/paper Saapper_fileessppee////e1 5a4bel (aaeeeffeeeeebaaeeeeeee330 Papee. pdf.
Wu, J., Yang. Y., Qian, Y., Sui, Y., Wang, X., and He, X. Gif: A general graph unlearning strategy via influence function. In Proceedings of the ACM Web Conference 2023, WWW '23, pp. 651-661, New York, NY, USA, 2023a. Association for Computing Machinery. ISBN 9781450394161. doi: 10.1145/ 3543507.3583521. URL https://doi. orr//00. 1145/3543507 3583521.
Khosla, A., Jayadevaprakash, N., Yao, B., and Fei-Fei, L. Novel dataset for fine-ge mme-grained image categorization. In First Workshop on Fine-G Grained Visual Categorization, IEEE Conference on Computer Vision and Pattern Recog- nition, Colorado Springs, CO, June 2011.
Koh, P. W. and Liang P. Understanding Black-box Predictions via Influence Functions. In Proceed- ings of the 34th International Conference Ma- chine Learning, pp. 1885-1894. PMLR, July 2017. URL https:tt///c perttp::/prroce http///pccednnnssse/ee mlr. press/v70/ html. koh1 htmml. ISSN: 2640-3498.
Wu, K., Shen, J., Ning, Y., Wang, T., and Wang, W. H. Certified edge unlearning for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, pp. 2606- 2617,2617, New York, NY, USA, 2023b. Association for Computing Machinery. ISBN 9798400701030, doi: 10. 1 144/3588030533599277 URL 10. 10.1145/358000 3599271.
Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images, 2009.
Kurmanji, M., Triantafillou, P., Hayes, J., Deepmind, G., and Triantafillou, Towards Unbounded Machine Un- learning. Advances in Neural Information Processing Systems, 1957 December 2023. URL https: //github. com/ MMt.///ehdddddddeede/ SCRUB.
Zhang. B., Dong, Y., Wang, T., and Li, J. Towards Certified Unlearning for Deep Neural Networks. In Proceedings of the 41st International Conference on Machine Learning, pp. 58800-58818 PMLR, July 2024. htt www.hhhssss/prrcceedieeoe mww...r.........m.mmm..m......mm mll. press/ v235 v235/zhang24 41, html. ISSN: 2640-3498.
Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient- based learning applied to document recognition. Pro- ceedings of the IEEE, 86(11))2278-22 2324, 1998. doi:
10. 10.119

---

A Certified Unlearning Approach without Access to Source Data
A. Assumptions
For the loss function & used to train the model parameters, we have the following assumptions listed in Assumption 4.1. Definition A.1 (L-Lipschitz). The loss function L is L-Lipschitz in the parameter w if (2 E X' x y and Vwi, W2 E H.
[((ar,)) v), w1) v)), w2)1 S L|[w] - W2ll2.
Definition A.2 (a-Strong Convexity). The loss function C a-strong convex if if v) E X' x y and Vei, w2 E H.
(((x,)),w)) 2 [((x, w), w2) + (VL((x) w), w2), wi - w2) + a _ - w2l1
(8)
Definition A.3 (3-Smoothness). The loss function L is 9-soooth if ((n,y) E X' x y and Vun w2 E H.
C((x, v). wi) & L( v), w2) + (VL((x, w)), wi - w2) + B 2 = - w2ll.
(9)
Definition A.4 (7-Hessian Lipschitz). The loss function C is Hessiin Lipschitz in the parameter w (z) X x and vwn, W2 H.
V' v), w1) V² w2)) S >//wr w2l12.
(10)
B. Relationship Between Certified Machine Unlearning and Differential Privacy
Differential privacy (Dwork, 2006) and certified unlearning share a common conceptual foundation. Both concepts aim to provide statistical indistinguishability. However, they focus on achieving indistinguishability in fundamentally different aspects of data handling and model behavior.
In differential privacy, the goal is ensure that the information obtained from a randomized mechanism applied a dataset indistinguishable when a specific data sample is included versus when is excluded. This statistical indistinguishability is achieved by bounding the influence of any single data point the output of the mechanism. Formally, the randomized mechanism M satisfies (e, diffferreti privacy if, for any two neighboring datasets D and DD' differing by at most one data point, and for any measurable set T, the following holds.
Definition B.1 (Differential Privacy). A randomized mechanism M satisfies (e, didffferren privacy if, for any two neighboring datasets D and D' differing in at most one data point, and for any measurable subset T C H:
Pr (M(D) ET) S e Pr (M(D') E TT) + Pr (M(D') E T) < e (M()) E T) T) 8
Thus, DP focuses on controlling the extent which the output of the mechanism reveals information about any individual data sample.
In contrast, certified unlearning ensures statistical indistinguishabiliy between the output of a retrained model and that of an unlearned model. The guarantee provided by certified unlearning, as defined in Definition 3.1, ensures that the behavior of the unlearned model closely approximates the retrained model within (c, 5) bounds.
Certified unlearning often employs DP-inspired techniques like the Gaussian mechanism to achieve guarantees. Specifically, certification requires finding an upper bound for the norm of the difference between model retrained from scratch and one updated via the unlearning mechanism. This bound enables noise scaling according to the Gaussian mechanism ((Dwork, 2006), App. A) satisfy (c, 5) certiiiee unlearning, ensuring statistical indistinguishabiiiy between the unlearned and retrained models (Definition 3.1).
Previous works derive this upper bound based on the unlearning mechanism's 's algorithm. Many certified unlcarning approaches rely on single-step second-order Newton updates under strong convexity assumptions (Guo et al., 2019; Sekhari et al., 2021; Zhang et al., 2024), where the Hessian is computed over the retain dataset D,. at the model trained on the full dataset w²
12

---

A Certified Unlearning Approach without Access to Source Data
B.1. Certified Unlearning Using Newton Updates with Exact Data Samples
Certified unlearning methods often utilize statistical information, S(-), such the Hessian of the full dataset evaluated at w* (Sekhari et al., 2021; Zhang et al., 2024). These methods randomize the unlearning mechanism by adding noise, following the Gaussian mechanism. The upper bound for the norm of the difference between the retrained and unlearned models is derived using retained data samples (Sekhari et al., 2021; Zhang et al., 2024).
Building on this framework, Sekhari et al. (Sekhari et al., 2021) derived an explicit upper bound for the norm difference, leveraging strong convexity and recond-order information. This bound provides critical insights into the statistical guarantees of certified unlearning. In the following the upper bound between
Lemma B.2 ((Sekhari et al., 2021) Lemma 3). Let the loss function C satisfy Assumption 4.1. Suppose the training dataset D contains v samplex, and the forget dataset DD, 'D consists of m samples. The norm of the difference between the model retrained from scratch, w,, and the model obtained using a second-order Newton update on the exact retain dataset D,, Wyr is bounded above by
2m
| wr
(11)
a²nn
Proof. The proof can be found in the Supplementary Material of Sekhari et al. (Sekhari et al., 2021) under C.I.
C. Upper Bound for Norm of Difference Between Unlearning Updates (Proof of Theorem 4.2)
Let us focus the Hessians of the loss function L, calculated at the same model w. for two different distributions, P and The distributions and y share the same support set, X' x y. The Hessians corresponding to each distribution are defined as follows.
The Hessian of the loss function L. under the distribution evaluated at the model w, is given by
H, = E. (2
V V2 y), w)]
(12)
Similarly, the Hessian of the loss function L under the distribution v, evaluated at the model w, is given by
H En,y))~ [)x,(())) w)]
(13)
Next, we focus on the spectral norm of the difference between these two Hessians. The following lemma provides an upper bound.
Lemma C.1. the loss function L satisfies the Assumption 4.1, then the following upper bound holds:
H, Holl2 < (8TV(e11
(14)
Proof.
H, Hy
|| (B((a.y)< y)m V2L((x 2), w)] B(a CVL(( v), w)] ll2
(15)
||
p(z, v) V/ 4) w) Σ
v (x v) V2 L((xx w)ll2
(16)
x yEy
MEX vEy
Σ
Σ
(p(x, v) v( v) v L 3), w)ll2
(17)
x NEY
< Σ
((p(x.)) v) -v(a, M) vV v). 2)
(18)
m wEy
< 3
(p(x, v) - v( v))
(19)
NEN DEY
2.3V (p I)
(20)
13

---

A Certified Unlearning Approach without Access to Source Data
In the above, Equation (18) follows from the sub-muliiplicatiivty and sub-additivity of the matrix norm. Equation (19) holds due to the s-smoothness property of the loss function L. and Equation (20) follows from the definition of the Total Variation distance.
Building on the discussion of the Hessians for the distributions p and V/, now turn our attention their empirical counterparts. The empirical Hessian matrices be represented as follows. Let the training dataset D consist of nı samples drawn from the distribution A, and let D. consist of ni samples drawn from the distribution v. Then, if and n2 are sufficiently large, we can make the following statement based on the law of large numbers.
Hp
Σ
ViL((x,)) w) R B(a,)>> V (2x w)]
(21)
Th (a.))ED
H
1
E v'L((o,)) v), w) v E( V [()
(22)
112
(M.D)ED,
After establishing the empirical Hessian matrices and their dependence on datasets and Dz, we now state the following result, which provides a bound on the spectral norm of their scaled difference. This result directly follows from the assumptions the loss function L and the distributions p and
Lemma C.2. Suppose the loss fanction L satisfies Assumption I. Let the training dataset DD consist of n1 samples drawn from the distribution p. and let the surrogate dataset D, consist of r22 samples drawn from the distribution v. Assuming that n, and ne sufficiently large, the following bound holds.
HD n2 Hp.le. & - -2) 2n,3TV
|| v)
(23)
Proof. Without loss of generality assume that ni 122
|| ngHD 12 [[ n22 HD n2Ho
n2 Hp, ll2
(24)
I (n1 n22) Hy 12 + n2
Hy H l1
(25)
~ (Mi n2) HD la + n2
H H 112
(26)
S (m1 - n2) - 2n v)
(27)
Here, the first inequality uses the triangle inequality for matrix norms. The approximation in the third step relies on the assumption that the empirical Hessian matrices Hp and Hp, converge to their population counterparts H, and H,, respectively, when nj and ny are sufficiently large by the law of large numbers. The last inequality holds because of the Lemma C.I.
To proceed with the main proof, we introduce the following lemma as key tool. This lemma provides an upper bound on the spectral norm of the inverse of the weighted difference of Hessians.
Lemma C.3. Suppose the loss function L satisfies Assumption 4.1. Let the training dataset D consist of samples, and the forget dataset D,, consist of m samples. If > m3 then the following bound holds:
[[nHD mHD.)) na m3
(28)
Proof. By using the reverse triangle inequality we know that,
(nH - mH )l12 2 |n HDl2 H
(29)
If n then the inner term will be positive because the spectral norms Hessians are between a and 3 by the Assumption 4.1 (strong convexity and smoothness). Therefore,
14

---

A Certified Unlearning Approach without Access to Source Data
n
H 12 - m HD, |2| = n: HD m
H Ho.ll
(30)
2 na m33
(31)
Having this lower bound on the spectral norm of [[ mHD. )|,, we can conclude on the following upper bound.
[InHD mHD 1 na m3
(32)
In this section, we focus on quantifying the difference between the models approximated using the exact dataset and the surrogate dataset. By leveraging the previously introduced tools, we can establish an upper bound on the norm of the difference between these two models.
Lemma C.4. Suppose the loss function L satisfies Assumption 4. I. Let w, denote the model approximated using the exact dataset D of size nı and the forget set Du, of size m. Similarly, let w, denote the model approximated using the surrogate dataset D of size no- Also, assume that the n and n2 sufficiently large and n, mg where i {1,2}- Then, the norm the difference between the approximated models is upper bounded as follows:
m(n1 n2)3 + 2mnz3TV || 12)
w.,, w, 112 S
VL(D., w2)12
(33)
(nja ( m33
Proof. Let's start from the applied update to the trained model w" having the exact training data samples and the forget set.
w. = w0 + m
n Hi - mHD. Th1
VL((D,, w²)
(34)
m "" + (n Hp mHpp) VL(D,,,w)
(35)
The model achieved after applying the update with the surrogate dataset D,
M2HH,, mHD,
e =w= 112 m
VL((Dn, w²)
(36)
112 - m
w" + m (n² Hp, - - w²)
(37)
w, 6r 22
mm
(,, mHH.) (nzHp, mHp.) VL(Du,, w')ll2
(38)
(n,Ho mHp.)) -1 (ngHp, mHD.) )-))) /V w') 1|2
$ m
(39)
S m
(ngHp, - mHp
[[n - mHp,) (nzHp, - mH 112
2
(40)
(n mH )
|V w")ll2
(noHo, mHp
[[ n²HD.))l2
(41)
(n, mH )
[V w")l2
m(n1 n2)3 + 2m v)
VL(D,, w²)l
(42)
- mm, m33)
The last inequality holds by using Lemma C.2 and Lemma C.3.
15

---

A Certified Unlearning Approach without Access to Source Data
With all the necessary tools established, we now ready prove the main result, Theorem 4.2. This theorem quantifies the relationship between the retrained model over the retained samples and the model approximated using the surrogate dataset, providing an upper bound on their difference.
Theorem C.5 (Proof of Theorem 4.2), Consider loss function L satisfying Assumption 4. I, and surrogate dataset DD with u2 samples drawn from distribution v. to mimic the true dataset 'D with aı drawn from distribution over the support set X x y. Define the retrained model over the retained samples as w, and the model achieved after unlearning as w. Also, assume that the nn and n2 are sufficiently large and n2 2 mD where E {1,2}- Then, the following upper bound holds,
2yLm²
m(n1 n2)3 + 2mm v) VV[(Du w]) w=)
1,0 iü 112
(43)
a²n2
(n1a mm3) m,8)
Proof. By the triangle inequality,
|
0,
1/w wt w, wr112
(44)
I w. 2l + w,,, 20, ll2
(45)
Then by utilizing the Lemma C.4 and Lemma B.2 the upper bound is proven.
C.1. Proof of Theorem 4.3
Theorem C.6 (Proof of Theorem 4.3). Consider a dataset D where data samples follow the distribution p. and surrogate dataset D, where data samples follow the distribution Given forget set Du C D. and the hypothesis set H. the unlearning mechanism ú (Algorithm 1) satisfies (e, -'eettfie unlearning. For any T C H.
Pr ((D) E T) E ((D)) TT) + 5, E T) S e Pr (UD),,
(46)
Pr
T) 5
Proof. Let wn = A(D) denote the model trained on the whole train dataset D with n, number of samples following the distribution p. .., = A(D,) the model retrained from scratch over the retain dataset D, DDD,, where D. is the forget set with number of samples, and w, the model approximated retrained model after the single step second-order Newton update utilizing the surrogate dataset D. with n2 number of samples following distribution v. Assume that the loss function used is satisfying the Assumption 4.1, ni and n2 are sufficiently large and n: 2 mb where i E 21. Also the support sets of distributions are the same X' V
The W. defined as
w,
w
m 112
[2gH,, D.
-HH.. -1
VL(Du,
(47)
m
m
By applying Theorem C.5 we can observe the following upper bound,
2yLm²
a + m(n - -22)3 + 2mn 1)
- - - <
VL(D,, w')l2 "")D,,w""l: mm) m3)
= A.
(48)
The Algorithm introduces the Gaussian noise to achieve indistinguishability between the model retrained from scratch :. and the model achieved after the unlearning w,. Let's define (w = L0, ((D)), = : + n and w (D., A(D) A(D))
w. + where the Gaussian noise n ~ (O, I² with = (A/c) (1.51.)) Following the proof from Dwork et al. (Dworkk 2006) Theorem A. we can prove that for any set T S H.
Pr (w), T) e Pr (ww))' E T) +
(49)
Pr (ww E T) < e Pr (w) E T) +
16

---

A Certified Unlearning Approach without Access to Source Data
D. Approximating Kullbeck-Leiber Distance
D.I. Proof Corollary 4.4
Corollary D.1 (Proof Corollary 4.4). Under the same assumptions and definitions in Theorem 4.2, the following upper bound holds:
2y1,2²
m(n -12)3 u²)
n²n² +
(nna - (22) m,3)
2mm28 /1 -xp--x-ex-LLLlll11 I1))
(50)
|IVC(D 1l2
(nja - (m) -m3)
Proof. The total variation distance is symmetric therefore,
TV(p I) = TV(p P)
(51)
Also, by the Bretagnolle--uber Inequality (Bretagnolle & Huber, 1979),
TV(p ll p) s v1 e e--e--Lie KL((
(52)
By replacing the total variation distance with this upper bound we prove the Corollary 4.4.
need this upper bound utilizing the KL divergence between surrogate and the exact data distributions because we have the surrogate samples. By having the surrogate samples we can approximate the expected values calculated over surrogate samples utilizing Monte-Carke approximation.
D.2. Derivations for Proposition 4.5
Proposition D.2 (Derivation of Proposition 4.5). Let f(w, output probability simplex over classes for data sample æ. parameterized by w. Given trained models wn and ir", where w" is trained on 'D and ut" DD Also, data samples from D and D, follow distributions p and v, respectively. the KL divergence KL(v || p) can be decomposed as,
1 1l)
log f(="xx), f(w", x) + +L((v(x) || p(z))
KL
(53)
n
(a,y)ED,
Proof. Starting with the definition,
v(x, v) log v(ylar) p(y)x) +
Σ v(x) log v(x)
KL(v P)
Σ (x.))EXxX
(54)
p(x)
(x)EX
The conditional probabilities can be approximated by classifiers. Let's say the classifier model trained on the exact dataset (representing conditional distribution for exact distribution) is w*. This model is already given to us for the unlearning. To represent the nominator we need to have an another model trained on the surrogate dataset provided, let's say after the training on the surrogate dataset achieve the model w". Then can approximate (54)
v(x, log f(w", x) KL(u(x) || p(x)) f(w", x)
KL(U p)
Σ
(55)
(m
and prove the derivation. By using Monte-Cart approximation because we have access to the surrogate data samples we can further approximate (55)
1 n (x,
log f(w" KL(v(x)) || p(x))
KL(F (1))
(56)
f(w x)
17

---

A Certified Unlearning Approach without Access to Source Data
D.3. Energy Based Modeling, Stochastic Gradient Langevin Dynamics and Proposition 4.6
Without direct access to exact samples from the target distribution, we approximate the input marginal KL divergence using energy-basee modeling, introduced in (Grathwohl et al., 2019). Energy-based models (EBMs) provide flexible framework for modeling complex distributions by associating energy score with each input, which corresponds to the unnormalized log- proobbbbbylliyy of the input under the target distribution. The normalized target distribution, denoted as p(æ), can be expressed as:
p(z) = exp( (x())
(57)
Z
Here, Exx) represents the energy function, which defined as follows,
F(x) - log Σ
exp(S(ur" m))y)
(58)
yEY
where f(w", æ)y corresponds to the logit score (or unnormalized log- ogg-pobbability) for the label y given the input under the model w". The summation is taken over the support of the output label space V. The normalization constant Z = exe((EE(x)) dæ ensures that p(x) is a valid probability distribution. However, evaluating Z is computationally intractable due to the high-dimensional integral over the input space.
To circumvent the intractability of computing Z, we employ Stochastic Gradient Langevin Dynamics (SGLD), a popular sampling technique for EBMs. SGLD enables approximate sampling from p(x) by iteratively updating samples based on the gradient of the energy function. Specifically, the update rule for the samples æ at step is given by:
(xx) 8x
T141 I, 2
+E
(59)
where E ~ (0, μ) is Gaussian noise, and μ represents the step size or learning rate. The negative gradient term ..E(z) directs the samples toward regions of lower energy (higher likelihood), while the Gaussian noise ensures exploration of the input space to avoid convergence to local minima. The process begins with initializing æn from prior distribution over the input space, which is often chosen to be uniform for simplicity and generality.
By iteratively applying this update rule, the generated samples approximate the target distribution p(x) without requiring explicit computation of the normalization constant Z. Given the collected samples from the distribution p(ar) along with the surrogate data samples, we then approximate the input marginal KI. divergence using a Donsker- representation (Donsker & Varadhan, 1983) of KL divergence.
Donsker-Varadhan Varadhan variational
E. Parameter Study and Implementation
We systematically evaluate our approach on both synthetic and real-world datasets to demonstrate its effectiveness in achicving certified unlcarning. Unless stated otherwise, we use a linear training model with privacy parameters e = 5e and 5 1, a forget ratio of 0.1, and an L2 regularization constant of À 0.01. The loss function assumed to be a-strongly convex, L-Lipschitz, f-smooth, and H-Hessian Lipschitz. Following prior works (Koh & Liang. 2017: Wu et al., 2023b;a; Zhang al., 2024), we set a, T., B, and y for each experimental setting hyperparameters. We set + X, T. 1, B = and 7 = 1. Even if the added noise does not follows the exact theoretical requirements, it does not affect the theoretical soundness of the paper.
For the sampling from the marginal distribution of the exact data, we used Stochastic Gradient Langevin Dynamics (SGLD) with step size 0.02 and generate 1000 samples. For each sample random update is applied 4000 iteration for each generated sample.
After sampling done to estimate the KL. divergence via Donsker Varadhan variational bound, trained network with three linear layers for 500 epochs with learning rate 0.0001 using Adam optimizer.
F. Additional Synthetic and Real-World Dataset Experiments
We conducted experiments on both synthetic and real datasets to justify the heuristic KL-divergence estimation (Section 4.2) and the corresponding empirical unlearning error Å. In Figures 3 and 4, we plot both the "exact" and "approximated"
18

---

A Certified Unlearning Approach without Access to Source Data
results (our heuristic method) for the KL-divergence and the respective noise a. For the synthetic data experiments, the exact KI. is computed using its closed-form for Gaussians. For real data experiments, since the exact KI divergence was not available, estimated it using the Donsker-Varadhan bound as a reference, leveraging both exact and surrogate data samples. Figure 3, Figure 4, Tables 8 and 9 show our approximations closely match exact values.
<
Method
Train
Test
Retain
Forget
MIA
RT
A
Original
78.2++0.2%
74.0+0.3%
78.2++0.%%
78.6+0.4%
47.6++02%%
Retrain
77.2:10.3%
71.810.2%
77.7
43.2:10.%%
47 47.4210.%%
1041
Unlearn (+)
77.41.06%
72.14007%
76.94..8%
74.14..3%
47.5+:0.%
10:2
0.02
0.02
Unlearn (-)
77.5:10.2%%
72.310.5%
77.810.1%
74.510022%
49.110.4%
9:22
0.23
0.21
0.04
Unlearn (-) 77.4+-0.6%
7..4+003%
77.2+0.4%%
7..3+003%
49.2++0.2%
10:3
0.31
0.35++0.23
0.06
Unlearn (-) 77.4+-0.5%
72.4+0.6%
77.5++02%%
74.2+0.5%
48.7+007%
11+2
0.37
0.38=
0.08
Unlearn (-) 77.5:10.7%
72.310.2%
77.10.7%
74.2110.3%
48.110.5%
9111
0,4
0.39
0.1
Unlearn (-) 77.4:0.4%
72.310.1%
77.710.4%
74.11:0.9%
48.2.10.2%
12:3
0.41
0.41
Table 8. Evaluation of unlearning performance while varying the off off-niagonal elements (C) of the unit covariance synthetic dataset.
1.75
Exacc Apprsiimated
X
1.50
6-
1.25
Forget Scores
5
1.00
1.0
FSI
(+)
PS1
0.75
FS2
0.50
3-
Exael
0.25
2-
Approsimated
0.1g
0.00
0.02
0.04
0.06
Dng
0.10
0.02
0.04
0
0,88
0.10
0.02
0.04
0.06
0.08
0.10
5
(a) Required noise variance (c)
(b) Estimated KI. divergence
(c) Forget Scores
Figure (a) Required noise variance a certified unlearning on synthetic data as a function of the off-diagonal elements of the covariance matrix (c). Both exact and heuristic (approximate) estimates are shown based on KL divergence. (b) Estimated KL divergence vs. ç. Exact values use the closed-form Gaussian KI. divergence, approximate values use our heuristic based on model parameters and surrogate data. (c) Forget scores achieved for synthetic datasets for varying off-diagonal elements of the covariance matrix (g).
Method
Train
Test
Retain
Forget
MIA
RT
A
Á
Original
85.9+0.8%
73.3:t0.1%
85.4+0.5%
84.6:10.2%
Retrain
86.7++0.2%
73.7++0.8%
87.710.5%
75.6::.2%
51.5++0.%
70tt1
Unlearn
84.11..9%
71.7+0.4%
85.2+0.6%
73.2+0.7%
51.4104%
1543
0.02
Unlearn (-)
84.7+0.4%
72.2+0.9%
85.3
73.6:10.5%
51.8+:.3%
1542
0.49=0.03 0.51=0.04
Original
85.5+0.1%
76.2+0.7%
85.6=0.8%
13.1%%
Retrain
84.11.04%
75.110.8%
86.1%0.9%
71.5+1.5%
50.310.1%
20:11
36
Unlearn (+) 84.9:t0.15 1%
75.6+...%%
85.1
0..5%
50.8+4..%
18:11
0.02
Unlearn (-)
84.9
7..31
10.11
1..4%
50.21.0.8
1943
143-0.002
0.41 0.00
Original
84.7++0.5%
7..3+
84.9+0.4%
83.6:20.5%
Retrain
82.940.3%
76.0+0.2%
84.2-1.8%
71.111.5%%
52.510.4%
19:12
100
Unlearn (+)
83.8:10.5%
75.7+0.7%
15.1
72.2+0.8%
52.0+004%
21
0.02
Unlearn (-)
83.7+00.%
75.6
8..0%
7..0...6%
51.99+0.%%
16133 0.25 0.02 0.31 0.07
Table 9, Evaluation of unlearning performance while varying Dirichlet parameters (f) on StanfordDogs dataset.
To address whether the approximate certificate is practically useful, we report both A (exact) and Á. The results confirm that even if the estimated bounds grow, model performance aligns with Unlcarn(+). For completeness, we ran multiple trials with different seeds, included error bars in all figures, and included error margins into the tables demonstrating consistency across repeated experiments. Overall, these findings validate the heuristic's reliability and practical utility in estimating KL divergence and unlearning error.
19

---

A Certified Unlearning Approach without Access to Source Data
Dul
1,60
PSI
X
8:18
FSI
1.40
(-)
1:000
2.8
Forget Scorcs
2.7
0x
2.6
2.5
0.80
2.4
13
36
100
Stanford
(a) Required noise variance (a) (b) Estimated KL divergence
(c) Forget Scores
Figure 4. (a) Required noise variance d for certified unlearning on StanfordDogs as a function of the Dirichlet parameter (E). Both exact and hcuristic (approximate) estimates shown based on KL divergence. (b) Estimated KL divergence vs. Exact values calculated by using the exact and surrogate data samples, approximate values use our heuristic based on model parameters and surrogate data. (c) Forget scores achieved for StanfordDogs dataset for varying Dirichlet parameter (E).
20


Reviews:
[{"review_id": "Dma6eM1sO1", "reviewer": "Reviewer_jhwC", "summary": "This paper proposes a novel certified unlearning framework that enables the unlearning process without requiring access to the original dataset. The authors use an estimated surrogate dataset Hessian to approximate the second-order unlearning process. The surrogate dataset is generated by estimating the model's original target distribution and using SGLD and Donsker-Varadhan techniques to sample and estimate the distribution of the new surrogate dataset. The work also provides a theoretical upper bound proof that supports the theoretical correctness of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments. Please see our responses below.\n\n**Experiments on complex models:** Our main focus in the current work was the theoretical foundations, to explore provable certified unlearning mechanisms in the source-free setting, and provide rigorous theoretical guarantees for certified unlearning using surrogate datasets. To that end, our empirical evaluations ranged - as a proof-of-concept - from simple linear models to networks with one or two convolutional layers (see Table 5 in the paper) that demonstrate that our certified unlearning mechanism maintains competitive performance across various complexity levels.\n\nTo further address the concern about moderately complex architectures, we introduce in this rebuttal a mixed linear network implementation. This model satisfies the strong convexity  assumptions made in our analysis—particularly regarding the loss function—and provides a more expressive and realistic evaluation setting than standard linear models. Despite its increased complexity, it remains analytically tractable and directly reflects the practical applicability of our theory. We gave more details about mixed linear networs in our responses to Reviewer mUHz under “Assumptions on loss functions and practicality”. As shown in the table given under the same response, our certified unlearning mechanism performs effectively in this mixed linear setting. This strengthens our claim that the theoretical results extend meaningfully to models beyond simplistic settings, including those with moderate complexity.\n\nIn response to the reviewer’s comment, we evaluate our method on a ResNet-18 model by computing the full-model Hessian using the Conjugate Gradient method. The results are shown in the table below. We observe a performance drop on the forget set after the unlearning update for both Unlearn (+) (retrained with exact data) and Unlearn (−) (our method). Importantly, Unlearn (−) performs comparably to Unlearn (+), demonstrating that our method achieves similar unlearning behavior without access to the retain dataset, even on complex models like ResNet-18.\n\n|Method|Train|Test|Retain|Forget|MIA|RT|\n|-|-|-|-|-|-|-|\n|Unlearn(+)|96.5%|90.4%|97.1%|94.4%|56.2%|45|\n|Unlearn(-)|96.1%|89.7%|96.2%|94.2%|57.3%|49|\n\n**Noise variance and forget score:**\n\n- Noise Variance ($\\sigma$): Our method derives $\\sigma$ based on the  theoretical bounds provided in Theorems 4.2 and 4.3 using an upper bound on the statistical distance between the true data distribution and the surrogate distribution, which control the term $\\|w_{r}^* - \\hat{w}_r\\|_2$ (see Equation (8)). In practice, when we do not know the exact upper bound on the statistical distance between the two datasets, we estimate it using the heuristic method explained in Sec. 4, and this estimate is then substituted into Equation (6) to compute the calibrated noise variance. To do so, we first sample from the trained model parameters using Langevin dynamics (details in App. D3) and then estimate the KL distance using the Donsker-Varadhan bound (Equation (12)).\n- Forget Scores: To quantify the quality of forgetting, we compute per-example $\\epsilon$ estimates that capture the strength of an optimal attacker's ability to distinguish between the outputs of the unlearned model and a model retrained from scratch. These per-example estimated $\\epsilon$ values are then aggregated into an overall forget score using a binning approach to ensure granularity and robustness. Our forget score methodology and implementation follows along the lines of Triantafillou et al. [R1], and we report three variants: “FS1(+)” (using noise calibrated with the original data), \"FS1(-)” (using noise calibrated with the surrogate data, our method), and “FS2(-)” (adding noise calibrated with the original data but applied without re-calibration to the surrogate data).\n\nWe hope this clarifies how the noise variance and forget scores are computed for the datasets in Figure 2 in our paper.\n\nFinally, we agree with the reviewer’s suggestion on moving the surrogate dataset part earlier, we will present this part earlier in the revised version.\n\n[R1] Triantafillou, E., Kairouz, P., Pedregosa, F., Hayes, J., Kurmanji, M., Zhao, K., Dumoulin, V., Junior, J. J., Mitliagkas, I., Wan, J., et al. Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition,  arXiv:2406.09073, 2024.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "Yes, the authors provides results on various real world datasets and synthetic datasets", "theoretical_claims": "Appear correct", "experimental_designs_or_analyses": "Sufficient validations on various datasets and model architures. Though the test architectures and dataset complexity are very simple.", "relation_to_broader_scientific_literature": "The use of surrogate datasets and second-order unlearning is interesting and promising, can be beneficial to broader context.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Pros:\n1. The paper addresses an important issue by introducing a framework for unlearning without access to the original dataset.\n2. The use of surrogate datasets and second-order unlearning seem novel\n3. The theoretical analysis provides a strong foundation for the proposed method.\n\n\nCons:\n1. The sampling and estimating the surrogate dataset part could be presented earlier. \n2. The network's architecture used in the empirical is too simple. I wonder the effectiveness when apply in models with moderate complexity.", "other_comments_or_suggestions": "No", "questions_for_authors": "How did you compute the noise variance and forget scores for various datasets shown in Figure 2?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SAGJ5iekED", "reviewer": "Reviewer_a1HE", "summary": "This paper studies certified unlearning in a setting where the original training data is inaccessible. Prior work on certified unlearning guarantees that the unlearned model is statistically indistinguishable from a model retrained without the deleted data, however it requires access to the original training data to perform the update. To get around this limitation, the authors of this paper assume access to a surrogate dataset and provide bounds on indistinguishablility based on the total variation (TV) distance between the original training data distribution and surrogate data distribution. This TV distance is also used to calibrate the noise added to the model parameters to ensure indistinguishability. Since the TV distance cannot be computed in practice (as it depends on the unknown training data distribution), the authors propose a heuristic method to estimate it using the original model and a model trained on surrogate data. The approach is evaluated empirically on real and synthetic datasets, where it is found to maintain utility and privacy guarantees.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments.\n\n**Experiments with different forget ratios:** We conducted extensive experiments on the StanfordDogs dataset with varying forget ratios to assess how forget set ratio impacts unlearning. The results in the table below show that our method Unlearn(-) scales well across different forget set ratios (FR). Also, results under the MIA and RT columns indicate that similar unlearning performance is achieved across FR with Unlearn(+) (the model achieved after unlearning with the exact data samples) and Retrain models. These findings confirm the robustness of our approach.\n\n|FR|Method|Train(%)|Test(%)|Retain(%)|Forget(%)|MIA(%)|RT|$\\boldsymbol{\\Delta}$|$\\boldsymbol{\\hat{\\Delta}}$|\n|-|-|-|-|-|-|-|-|-|-|\n|0.01|Original|87.3±0.2|73.7±0.3|87.2±0.2|87.9±0.4|||||\n||Retrain|87.1±0.1|73.7±0.7|87.2±0.3|73.8±0.6|52.1±0.2|10±2|||\n||Unlearn(+)|87.3±0.4|74.1±0.6|87.3±0.1|74.5±0.7|53.2±0.3|10±2|0.0002||\n||Unlearn(-)|87.1±0.6|74.1±0.4|87.2±0.3|74.1±0.6|53.1±0.2|10±1|0.023±0.006|0.032±0.007|\n|0.2|Original|87.3±0.2|73.7±0.3|87.6±0.2|86.4±0.4|||||\n||Retrain|85.6±0.1|72.4±0.6|88.7±0.7|73.3±0.1|50.6±0.8|40±2|||\n||Unlearn(+)|84.9±0.8|71.8±0.5|88.3±0.1|71.5±0.3|51.8±0.2|40±1|0.08||\n||Unlearn(-)|85.0±0.5|71.4±0.2|88.0±0.9|72.6±0.6|52.0±0.1|40±2|0.82±0.06|0.91±0.03|\n\n**Justification of the heuristic method and practicality:** We conducted experiments on both synthetic and real datasets to justify the heuristic KL‐divergence estimation (Sec. 4.2) and the corresponding empirical unlearning error $\\hat{\\Delta}$. In Figs. 1 and 3 [(link)](https://limewire.com/d/a68qm#RoLgJHE3KN), we plot both the “exact” and “approximated” results (our heuristic method) for the KL‐divergence and the respective noise $\\sigma$. For the synthetic data experiments, the exact KL divergence is computed using its closed-form for Gaussians. For real data experiments, since the exact KL divergence was not available, we estimated it using the Donsker-Varadhan bound as a reference, leveraging both exact and surrogate data samples. Figs. 1–4 and Tables 1–2 [(link)](https://limewire.com/d/a68qm#RoLgJHE3KN) show our approximations closely match exact values.\n\nTo address whether the approximate certificate is practically useful, we report both $\\Delta$ (exact) and $\\hat{\\Delta}$. The results confirm that even if the estimated bounds grow, model performance aligns with Unlearn(+). For completeness, we ran multiple trials with different seeds, included error bars in all figures, and included error margins into the tables demonstrating consistency across repeated experiments. Overall, these findings validate the heuristic’s reliability and practical utility in estimating KL‐divergence and unlearning error.\n\n**Non-vacuous upper bound for statistical distances:** While a trivial upper bound on the TV distance is available ($TV(\\rho \\| \\nu) \\leq 2$), extending this to a non-vacuous bound on the KL divergence is challenging without further assumptions on the retained data. Our primary goal was to maintain generality and avoid introducing new restrictions with the assumptions about the data distributions. To that end, we proposed a heuristic method to approximate the KL distance using the model parameters. Using this approximation, showed that as the distance between exact and surrogate distributions increases, achieving certified unlearning requires adding more noise calibrated using Corollary 4.4. Figs. 1 and 3 [(link)](https://limewire.com/d/a68qm#RoLgJHE3KN) further show that our method can approximate the exact KL distance using only the model parameters, without access to the original data samples, making it suitable for source-free unlearning.\n\n**Limitations:** Regarding the assumptions, we build on the mixed linear network which enables us to meet the strong convexity criteria while also achieving competitive accuracy results. We believe that this choice satisfies both the necessary theoretical conditions and provides a solid foundation for our experimental evaluation. Please also see our response to Reviewer mUHz, where we provide further details about this network under \"Assumptions on loss functions and practicality\".\n\nWhile our current formulation focuses on single-batch unlearning for classification models as noted by the reviewer, this also provides an important and tractable first step. Extending our mechanisms to sequential unlearning requires new theoretical insights on the certification budget considering the noise added after each unlearning step [R2, R3]. This is an interesting future direction we are actively exploring.\n\n[R2] E. Chien, H. P. Wang, Z. Chen, and P. Li, ‘Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning’, in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.\n\n[R3] B. Zhang, Y. Dong, T. Wang, and J. Li, ‘Towards Certified Unlearning for Deep Neural Networks’, in Forty-first International Conference on Machine Learning, 2024.", "claims_and_evidence": "- The paper claims that achieving certified unlearning without training data access is an open problem. I agree based on my knowledge of the literature.  \n\n- The paper claims that the proposed method is certified, however this is only true for the method described in Sec 4.1 which is not realizable in practice. While the practical approach described in Sec 4.2 appears to perform well empirically, the bound on the unlearning error $\\hat{\\Delta}$ is not guaranteed to hold. \n\n- The paper claims that extensive experiments demonstrate the effectiveness of the approach, however I have some concerns (see below).", "methods_and_evaluation_criteria": "- The proposed method builds on Sekhari et al. (2021), except that the original training dataset is replaced with a surrogate. This makes sense, provided a close surrogate is available (I’m not sure how reasonable this assumption is). It makes sense to me to account for the error in approximating the training dataset with the surrogate, however, I wonder whether it would be possible to estimate an upper bound on the TV distance, rather than using an estimator with unknown properties. If this were possible, the “practical” method could be certified. \n\n-  The evaluation broadly makes sense. The proposed “practical” method (Unlearn $-$) is compared with two baselines with training data access: Sekhari et al. (2021) and retraining from scratch. A variety of standard metrics for assessing unlearning performance are used across four datasets (three real, one synthetic). Due to strong assumptions on the loss function (Assumption 4.1), the evaluation focuses on linear models or pre-trained encoders with a learned linear head. This is also a limitation in prior work.", "theoretical_claims": "The main theoretical claim is stated in Theorem 4.2 and proved in Appendix C. I did not check the proof, however it seems to make use of the triangle inequality, various assumptions on the loss function, and properties of the Hessian. I don’t have any reason to doubt the correctness.", "experimental_designs_or_analyses": "As stated above (Methods and Evaluation Criteria) the experiments broadly make sense to me. However, I have the following concerns: \n\n \n\n- I couldn’t spot the size of the forget set in Sec 5. I suspect this may have an impact on the performance of Unlearn $-$. It would be great to see results reported as a function of the size of the forget set. \n\n- The error in the estimate of the KL divergence between the training and surrogate data does not seem to be reported. If this information were available, it would be possible to more directly assess the validity of the estimation approach described in Sec 4.2.  \n\n- The empirical estimate of the unlearning error $\\hat{\\Delta}$ (Corollary 4.4) is not reported. As a result, it’s not possible to assess whether the “approximate” certificate is practically useful, or vacuous. \n\n- Fig 1(a): I believe the curve corresponds to the exact estimate of the required variance (assuming training data access)? If so, it would be good to additionally report the heuristic estimate (not assuming training data access). \n\n- For the synthetic experiments, it would be good to repeat the experiment multiple times averaging over multiple synthetic datasets. The results could be reported with error bars.", "relation_to_broader_scientific_literature": "- The paper builds on Sekhari et al. (2021), adopting their definition of certified unlearning and adapting their unlearning method. Sekhari et al.’s formulation of unlearning differs from prior work by Guo et al. (2019) and Neel et al. (2021), in that they focus on ensuring the unlearned model achieves a high (generalization) test error rather than training error. Heuristic approaches for unlearning without access to training set. \n\n- The practical version of the method estimates the KL divergence from the original model and a model trained on surrogate data using: \n\n    - An implicit energy model to estimate the marginal distribution over inputs $P(X)$ (Grathwohl et al. (2019). \n\n    - A Donsker-Varadhan variational representation of the KL divergence (Donsker & Varadhan, 1983). \n\n- The empirical evaluation employs a variety of unlearning metrics by Kurmanki et al. (2023), Golatkar et al., (2020) and Triantafillou et al., (2024).", "essential_references_not_discussed": "I’m not aware of any essential references that were not discussed.", "other_strengths_and_weaknesses": "S1. I found the paper a pleasure to read. \n\nS2. The problem seems well-motivated given the existence of several heuristic approaches that aim to perform unlearning without training data access. \n\nS3. Apart from the suggestions above, the experiments seem well-executed. \n\nW1. The paper focuses on single batch unlearning for classification models, which limits its applicability. However, this also appears to be a limitation of prior work.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "1. How does the method perform for different sized forget sets? \n\n2. How large is the empirical bound on the unlearning error? Is it practically useful? \n\n3. Is it possible to approximate a (non-vacuous) upper bound on the KL divergence?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WiIM3RzTGA", "reviewer": "Reviewer_mUHz", "summary": "In this paper, the authors studied an unlearning problem with the assumption that at the time of unlearning, the model provider lost access to the original training dataset, but has access to a surrogate dataset that’s very close to the original training dataset in terms of distribution. They adapted the second-order Newton update algorithm to perform unlearning and also provide theoretical guarantees for their proposed method. Moreover, they conducted preliminary experiments to demonstrate the performance of their proposed method on synthetic generated datasets and real-world datasets.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments.\n\n**Justification of the motivation:** In our experiments, most surrogate datasets were synthetically generated to provide a controlled environment for evaluating our theoretical results. However, for real-world applications, surrogate datasets need not be generated purely synthetically. In practice, surrogate data can be obtained from publicly available sources or even generated by leveraging the trained model to capture aspects of the original distribution.\n\nRegarding the motivation, there exist numerous real-world scenarios where the original dataset is no longer accessible. For example, regulatory policies may require data deletion after a fixed retention period, while models trained on this data continue to be deployed. Similarly, in collaborative or federated learning settings, data privacy constraints often prevent access to the full original dataset, leaving only a surrogate or limited statistical summary available.\n\nFinally, we clarify the assumption regarding access to the original training dataset. In our framework, we assume that the unlearning mechanism does not have direct access to the retain portion of the original dataset ($\\mathcal{D}_r$). It only has access to the samples to be forgotten ($\\mathcal{D}_u$), which may for instance be provided by a specific user. Although one might expect that having access to the forget samples ($\\mathcal{D}_u$) would simplify approximating the Hessian for the retained data ($\\mathcal{D}_r$), in practice, this is nontrivial. The distribution of $\\mathcal{D}_u$ can differ significantly from that of $\\mathcal{D}_r$ (as in class unlearning), making Hessian estimation challenging when relying solely on the forget samples. This reflects our intent to keep the unlearning framework broadly applicable.\n\n**Assumptions on loss functions and practicality:** Yes, we agree with the reviewer that Assumption 4.1 is indeed strong; while it may not hold for all deep neural network loss functions, it is important for tractability of the theoretical analyses of second-order unlearning methods which is a key first step towards the analysis of the more general setting. To satisfy these conditions while still achieving competitive performance in practice, we leverage a mixed linear network [R4] implementation. Mixed linear networks combine the simplicity and theoretical tractability of linear models with select non-linear components, which enables them to meet the convexity and smoothness criteria. As demonstrated in the table below, our implementation achieves a significant unlearning performance depending on the accuracy metrics while also achieving significant training accuracy. Extending our theoretical guarantees to general non-convex settings in the source-free setting is an important future direction.\n\n[R4] A. Golatkar, A. Achille, A. Ravichandran, M. Polito, and S. Soatto, ‘Mixed-Privacy Forgetting in Deep Networks’, in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021, pp. 792–801.\n\n||Method|Train|Test|Retain|Forget|MIA|RT|$\\Delta$|$\\hat{\\Delta}$|\n|-|-|-|-|-|-|-|-|-|-|\n||Original|94.7±0.2%|88.5±0.3%|95.3±0.2%|95.0±0.4%|||||\n|0.1|Retrain|93.6±0.4%|86.4±0.9%|95.6±0.7%|84.7±0.6%|51.2±0.1%|53±2|||\n||Unlearn(+)|93.7±0.3%|86.4±0.6%|94.8±0.4%|87.2±0.6%|51.3±0.1%|54±3|0.02||\n||Unlearn(-)|94.1±0.3%|85.2±0.3%|94.9±0.7%|86.8±0.1%|52.1±0.8%|54±2|0.31±0.06|0.35±0.03|\n|0|Retrain|81.7±0.4%|72.3±0.1%|92.7±0.1%|0%||142±3|||\n||Unlearn(+)|82.2±0.4%|72.5±0.9%|93.2±0.2%|4.2±0.2%||135±5|0.02||\n||Unlearn(-)|82.4±0.5%|72.4±0.1%|93.5±0.8%|5.1±0.8%||132±6|0.49±0.03|0.52±0.02|\n\n**Class unlearning:** Thanks for raising this interesting question. Yes, it is possible to unlearn an entire class. We conducted experiments to unlearn class 0 from the CIFAR10 dataset, using our mixed linear network implementation, which satisfies the convexity assumptions while maintaining competitive accuracy. We show our results in the second row of the table above. We observe that we can effectively remove the influence of the targeted class while preserving performance on the remaining data. We believe the proposed method not only facilitates class unlearning but also can be extended to tackle scenarios such as unlearning all poisoned samples.\n\n**Original model results:** We added the original model results in every table we provided in this rebuttal (tables under Reviewer a1HE and the table provided above).\n\n**Experiments with different seeds:** To address the inherent randomness introduced by noise calibration, we conducted our experiments over multiple runs and report the averaged values with their error margins (table under Reviewer a1HE, the table provided above, Figure 1-4 and Table 1-2 in [link](https://limewire.com/d/a68qm#RoLgJHE3KN)). This evaluation demonstrates that our method is robust with performance variations well within acceptable margins.\n\n**Typo:** Thanks, we will fix this in the revised version.", "claims_and_evidence": "See my main comments in **Theoretical Claims** and **Experimental Designs Or Analyses** sections.", "methods_and_evaluation_criteria": "1. Most of the surrogate datasets in the experiments are synthetically generated, does it mean that for real-world usecases, surrogate datasets should also be generated in this way? Can we use the train model to understand the original distribution and generate surrogate dataset based on model prediction? \n\n2. Can the authors provide a few usecase examples when one would have accessed or created a surrogate dataset and lost access to the original dataset in real-world scenarios? I think the motivation for this problem setting is not clear.", "theoretical_claims": "I have some questions about the assumptions stated in this paper.\n\n1.\tAssumption 4.1 though may be typical for the second-order type of methods, it is very strong assumption on the loss function. To me, I think common loss functions used for training deep neural networks do not satisfy assumption 4.1, which makes the theoretical result stated in this paper unrealistic.   \n2.\tI am a bit confused about the assumption of not having access to the original training dataset. What I understand is one does not have access to the full original dataset $\\mathcal{D}$, however, it seems like the authors only assume that one does not have access to the retain portion of the original dataset $\\mathcal{D_r}$, \nwhich seems to make the problem easier, at least computing an approximation of $H_{\\mathcal{D}_r}$ is easier under assumption 4.1 and with the knowledge of $\\mathcal{D}_u$.", "experimental_designs_or_analyses": "1. In the experimental results presented in Tab 1, it seems like the model after unlearning performs similarly at test and and forget data splits. In this case, does that means the test data has a distribution shift? Or the original model is not sufficiently trained on the “desired to learn” distribution? Moreover, it would be good to provide the original model performances on those data split, so we have a good understanding of the unlearn algorithms’ performance and also if unlearning makes sense in this setting.\n2.\tSince there is randomness introduced by noise calibration, it is good to repeat the experiments multiple times and report the means and standard deviations for all experiments.\n3.  Instead of unlearning a randomly sampled subset of the original dataset, is it possible to unlearn a certain class from the original dataset, or unlearn all poisoned samples from the original dataset? In these problem settings, it seems to be easier to evaluate the performance of the proposed algorithm.", "relation_to_broader_scientific_literature": "The paper studied unlearning in a specific problem scenario, however, I am not very convinced that the problem setup is realistic, see my comments in **Methods And Evaluation Criteria** section.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Na", "other_comments_or_suggestions": "1.\tPage 3 line 150, \"åthat\" should be  \"that\"?", "questions_for_authors": "See my main comments in **Theoretical Claims** and **Experimental Designs Or Analyses** sections.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "86O3XtRDJ2", "reviewer": "Reviewer_B4Hr", "summary": "This work focuses on certified unlearning when source data are unavailable due to resource limitation or regulation constraints. Instead, this work uses surrogate datasets to guide unlearning process, where the dataset mimics the original set to a certain extent. The indistinguishability guarantee is based on distance between those two datasets, and works for classification problem.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive comments. Please see our responses below. \n\n**About the datasets:** It is worth noting that prior works in certified unlearning have similarly employed datasets such as CIFAR‑10 and StanfordDogs [R5-R7]. Our primary objective in using these datasets was to provide a controlled experimental validation of our theoretical results rather than to claim state‑of‑the‑art empirical performance.The fact that our method performs comparably to fully‑retrained models confirms that our unlearning approach preserves model utility while offering certification guarantees.\n\n[R5] A. Golatkar, A. Achille, A. Ravichandran, M. Polito, and S. Soatto, ‘Mixed-Privacy Forgetting in Deep Networks’, in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021, pp. 792–801.\n\n[R6] E. Chien, H. P. Wang, Z. Chen, and P. Li, ‘Langevin Unlearning: A New Perspective of Noisy Gradient Descent for Machine Unlearning’, in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.\n\n[R7] B. Zhang, Y. Dong, T. Wang, and J. Li, ‘Towards Certified Unlearning for Deep Neural Networks’, in Forty-first International Conference on Machine Learning, 2024.\n\n**Difference between DP and DP-inspired unlearning:** The key difference between DP and DP‑inspired unlearning lies in the nature of their statistical guarantees. In traditional Differential Privacy (DP), the guarantee is based on the statistical distance between the output distributions of an algorithm when run on two adjacent datasets. In contrast, DP‑inspired unlearning focuses on ensuring statistical indistinguishability between the output of a fully‑retrained model and the output of the unlearning mechanism. This distinction means that while both approaches aim to limit the leakage of sensitive information, DP‑inspired unlearning calibrates noise based on the distance between these two different mechanisms rather than on adjacent datasets. We elaborate on this point further in Appendix B.\n\n**Typo:** Thanks for pointing this, we will fix this in the revised version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Proposed method is based on Newton updates and DP noise, which are two important components been used in machine unlearning area, so it makes sense.", "theoretical_claims": "The theoretical claims look good.  Starting from Assumption 4.1 for loss function, this work develops  Hessian estimation, model update (with Newton updates) and Gaussian noise injection. Finally, it defines the bound between true model from the retraining and approximated model, and (epsilon-delta)-certified unlearning.", "experimental_designs_or_analyses": "The datasets (e.g., CIFAR 10 and Stanford dogs) used in this work are quite outdated. Numbers on its method is on par with fully-retrained models.", "relation_to_broader_scientific_literature": "1. This work discusses some popular works on certified unlearning with different approaches. For example, Guo et al., 2019, Sekhari et al., 2021 and Zhang et al., 2024 focus on single-step Newton updates, and Neel et al., 2021 and Chien et al., 2024 focus on projected gradient descent algorithms.\n2. As the closest problem to the proposed problem, authors discuss zero-shot unlearning approaches. Chundawat et al., 2023 requires the forget set, while this work does not need. Similarly, Cha et al., 2023 needs to apply gradient ascent on the forget set. This work also mentions Foster et al., 2024 and Bonato et al., 2025. However, none of them formally provide theoretical guarantee for the problem.", "essential_references_not_discussed": "To my best knowledge, authors covered most essential works related to this topic.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "Typos on Line 150 “athat”.", "questions_for_authors": "I am not sure that the difference between DP and DP-inspired unlearning, even after reading appendix B. Why is the statistical indistinguishability of two approaches different? Can you clarify this point more in the text?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper consider machine unlearning, an important task motivated by the right to erasure present in a number of jurisdictions. While the motivation is connected to privacy and data minimisation, the predominant approach to machine unlearning assumes access to the entire training set, in order to correct for accumulating noise required for indistinguishability. That is, the main benefit delivered by most existing work is computational, and in offering an approach to unlearning, actually requires *greater* access to training data. Given that many companies tend towards data minimisation, this is a significant gap in the practicality of machine unlearning – computational advantage at the expense of privacy. This work develops interesting approaches that don’t require access to training data but instead leverage surrogate data. Noise is then calibrated according to the statistical (TV) distance between training and surrogate data, allowing for rights to privacy and erasure to coexist.

In response to concerns by Reviewer jhwC on simplicity of models evaluated, the authors present convincing experimental evidence in their rebuttal on a ResNet-18 model, showing strong comparable performance against the natural baseline. The other concerns such as estimating of variance by an upper bound on statistical distance between true and surrogate distributions, and forget scores, are fully addressed by the authors highlighting existing explanation in the paper. 

Reviewer mUHz reports a range of concerns spanning the motivation, with most of the critique clarifying in nature: whether surrogate data needs to be synthetic; Assumption 4.1 vs “typical” loss function; clarification of components of training detail retained; interpretation of Table 1. And relatively minor points: repeats to account for randomness in experiments, unlearning classes/other settings.

Reviewer a1HE raises several valid areas for improvement, much of which are addressed by the author rebuttal: size of forget set in Sec 5; error analysis of KL estimate; empirical estimate of unlearning error $\hat{\Delta}$; heuristic estimate vs exact estimate of the required variance; averaging for synthetic experiments to obtain error bars. The authors must implement these improvements and clarifications, I think them for the responses so far.

A key concern highlighted by a1HE is that the unlearning approach, though certified for exact TV distance, loses its guarantees of certified unlearning in practice. This is a fairly important distinction that needs to be highlighted better in the abstract and introduction, to make clear the potential disconnect. That said, the Reviewer ultimately found the work valuable – as indeed much of the literature between practical unlearning and certified unlearning is still addressing this gap, and I believe the work does represent progress towards this goal, as the requirement to retain training data can be seem to undermine the privacy rights ultimately motivating or connected to the right to erasure.
Decision: Accept (poster)