A Reliable Cryptographic Framework for Empirical Machine Unlearning Evaluation
Authors: Yiwen Tu
Pingbang Hu
Jiaqi W. Ma
Venue: NeurIPS 2025 poster ()
Keywords: Machine Unlearning
Differential Privacy
Membership Inference Attacks
Cryptography
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We propose the a theoretical-sound machine unlearning evaluation framework with provable properties.

Abstract: Machine unlearning updates machine learning models to remove information from specific training data samples, complying with data protection regulations that allow individuals to request the removal of their personal data. Despite the recent development of numerous unlearning algorithms, reliable evaluation of these algorithms remains an open research question. In this work, we focus on membership inference attack (MIA) based evaluation, one of the most common approaches for evaluating unlearning algorithms, and address various pitfalls of existing evaluation metrics that lack theoretical understanding and reliability. Specifically, by modeling the proposed evaluation process as a cryptographic game between unlearning algorithms and MIA adversaries, the naturally-induced evaluation metric measures the data removal efficacy of unlearning algorithms and enjoys provable guarantees that existing evaluation metrics fail to satisfy. Furthermore, we propose a practical and efficient approximation of the induced evaluation metric and demonstrate its effectiveness through both theoretical analysis and empirical experiments. Overall, this work presents a novel and reliable approach to empirically evaluating unlearning algorithms, paving the way for the development of more effective unlearning techniques.

A Reliable Cryptographic Framework for Empirical Machine Unlearning Evaluation
Yiwen Tu University of Michigan, Ann Arbor evantu@umich. edu
Pingbang Hu"
University of Illinois ttbana-Champaige
pbbeillinois. edu
Jiaqi W. Ma
University of Illinois Jrbana-Chaapaign jiaqimaGilline edu
Abstract
Machine unlearning updates machine learning models remove information from specific training samples, complying with data protection regulations that allow individuals request the removal of their personal data. Despite the recent devel- opment of numerous unlearning algorithms, reliable evaluation of these algorithms remains an open research question. In this work, we focus membership inference attack (MIA) based evaluation, one of the most common approaches for evaluating unlearning algorithms, and address various pitfalls of existing evaluation metrics lacking theoretical understanding and reliability. Specifically, by modeling the proposed evaluation process cryptographic game between unlearning algo- rithms and MIA adversaries, the naturally induced evaluation metric measures the data removal efficacy of unlearning algorithms and enjoys provable guarantees that existing evaluation metrics fail to satisfy. Furthermore, we propose practical and efficient approximation of the induced evaluation metric and demonstrate its effectiveness through both theoretical analysis and empirical experiments. Overall, this work presents a novel and reliable approach to empirically evaluating unlearn- ing algorithms, paving the way for the development of more effective unlearning techniques.
Introduction
Machine unlearning is an emerging research field in artificial intelligence (Al) motivated by the "Right to be Forgotten," " outlined by various data protection regulations such as the General Data Protection Regulation (GDPR) [Mantelero] 2013 and the California Consumer Privacy Act (CCPA) [CCPA] 2018). Specifically, the Right to be Forgotten grants individuals the right to request that an organiza- tion their personal data from its databases, subject to certain exceptions. Consequently, when such data were used for training machine learning models, the organization may be required to update their models to "unlearn" the data to comply with the Right to be Forgotten. A naive solution is retraining the model on the remaining data after removing the requested data points, but this solution computationally prohibitive. Recently, plethora of unlearning algorithms have been developed to efficiently update the model without complete retraining, albeit usually at the price of removing the
requested data information only approximately [Cao and Yang 2015 Bourtoule al. 2021 Guo
et al. 2020 Neel et al. 2021
Sckhari et al. 20innChienn et al. 2023 Kurmanji et al. 2023
'Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Despite the active development of unlearning algorithms, the fundamental problem of properly evalu- ating these methods remains an open research question, as highlighted by the Machine Unlearning Competition held at NeurlPS 2 The unlearning literature has developed variety of evaluation metrics for measuring the data removal efficacy of unlearning algorithms, i.e., to which extent the information of the requested data points are removed from the unlearned model. Existing metrics can be roughly categorized as uttack-based [Graves et al. 2020 Kurmanji et al. 2023 Goel et al.
2023 Hayes et al., 2024, Sommer et al. 20200 Goel et al., [023]. theory-based
Triantafillou and
Kairouz | Becker and Liebig 2022], J. and retraining-
Goolatkar et al. 202 Wu et al. 2020
Izzo et a 2021], respectively. Each metric has its own limitations and there is no consensus
standard evaluation metric for unlearning. Among these metrics, the membership inference attack
(MIA) based metric, which aims to determine whether specific data points were part of the original
training dataset based on the unlearned model, is perhaps the most commonly seen in the literature. MIA is often considered a natural unlearning evaluation metric it directly measures the privacy leakage of the unlearned model, which is a primary concern of unlearning algorithms.
Most existing literature directly uses MIA performance to measure the data removal efficacy of unlearning algorithms. However, such metrics can be unreliable as MIA performance is not a well-calibrated metric when used for unlearning evaluation, leading to counterintuitive results. For example, naively retraining the model is theoretically optimal for data removal efficacy, albeit computationally prohibitive. Nevertheless, retraining is not guaranteed to yield the lowest MIA performance compared to other approximate unlearning algorithms. This discrepancy arises because MIAs themselves are imperfect and can make mistakes in inferring data membership. Furthermore, MIA performance is also sensitive to the composition of data used to conduct MIA and the specific choice of MIA algorithm. Consequently, the results obtained using different MIAs are not directly comparable and can vary significantly, making it difficult to draw definitive conclusions about the efficacy of unlearning algorithms. These limitations render the existing MIA-based evaluation brittle and highlight the need for a more reliable and comprehensive framework for assessing the performance of unlearning algorithms.
In this work, we aim to address the challenges associated with MIA-based unlearning evaluation by introducing theoretccoeetccll framework named the unlearning sample inference game. Within this framework, we gauge the data removal efficacy through a game where, informally, the challenger (model provider) endeavors to produce an unlearned model, while the adversary (MIA adversary) seeks to exploit the unlearned model to determine the membership status of the given samples. By carefully formalizing the game, with controlled knowledge and interaction between both parties, ensure that the success rate of the adversary in the unlearning sample inference game possesses several desirable properties, and thus can be used as an unlearning evaluation metric, circumventing the aforementioned pitfalls of MIA performance. Specifically, it ensures that the adversary's 's success rate towards the retrained model is precisely zero, thereby certifying retraining as the theoretically optimal unlcarning method. Moreover, it provides a provable guarantee for certified machine unlearning algorithms (Guo et al. 2020), aligning the proposed metric with theoretical results in the literature. Lastly, it inherently accommodates the existence of multiple MIA adversaries, resolving the conflict between different choices of MIAs. However, the computational demands of exactly calculating the proposed metric pose practical issue. To mitigate this, we introduce SWAP test as practical approximation, which also inherits many of the desirable properties of the exact metric. Empirically, this test proves robust to changes in random seed and dataset size, enabling model maintainers to conduct small-scale experiments to gauge the quality of their unlearning algorithms.
Finally, we highlight our contributions in this work as follows:
We present formalization of the unlearning sample inference game, establishing a novel unlearning evaluation metric for data removal efficacy.
We demonstrate several provable properties of the proposed metric, cireumventing various pitfalls of existing MIA-based metrics.
We introduce a straightforward and effective SWAP test for efficient empirical analysis. Through thorough theoretical examination and empirical experiments, we show that it exhibits similar desirable properties.
"See hattp:://unlearree challenge, .ithuu. 1o/
For example, the accuracy or the area under the receiver operating characteristic curve (AUC) of the inferred membership.
2

---

In summary, this work offers a same-theoretic framework for reliable empirical evaluation of machine unlearning algorithms, tackling one the most foundational problems this field.
2 Related work
2.1 Machine unlearning
Machine unlearning, as initially introduced by [Cao and Yang 2015], is update machine learning models to remove the influence of selected training data samples, effectively making the models "forget" those samples. Most unlearning methods can be categorized as exact unlearning and ap- proximate unlearning. Exact unlearning requires the unlearned models to be indistinguishable from models that were trained from scratch without the removed data samples. However, can still be computationally expensive, especially for large datasets and complex models. On the other hand, approximate unlearning aims to remove the influence selected data samples while accepting a certain level of deviation from the exactly unlearned model. This allows for more efficient unlearning algorithms, making approximate unlearning increasingly popular practically. While approximate unlearning is more time and space-efficient, it does not guarantee the complete removal of the influence of the removed data samples. We refer the audience to the survey on unlearning methods by 2023 for more comprehensive overview.
Xu et al.
2.2 Machine unlearning evaluation
Evaluating machine unlearning involves considerations of computational efficiency, model utility, and data removal efficacy, Computational efficiency refers to the time and space complexity of the unlearning algorithms, while model utility measures the prediction performance of the unlearned models. These two aspects can be measured relatively straightforwardly through, e.g., computation time, memory usage, or prediction aceuracy. Data removal efficacy, on the other hand, assesses the extent to which the influence of the requested data points has been removed from the unlearned models, which is highly non-trivial measure and has attracted significant research efforts recently. These efforts for evaluating or guaranteeing data removal efficacy can be categorized into several groups. We provide an overview below and refer readers to Appendix A for an in-depth review.
Retraining- Generally, retraining based evaluation measures the parameter posterior difference between unlearned models and retrained models, the gold standard for data removal (oo
latkar et al. 2020 2021 He et al. 2021 I770 al. 2021 Peste et al., 2021 Wu al., 2020). However, they are often unreliable as measures like parameter difference can be sensitive to the randomness led by the training dynamics (Cretu et al. 2023).
Thsory- Another line of work tries to characterize data removal efficacy by requiring strict theoretical guarantee for the unlearned models [Chien et al.) 2023 Guo et al. [220 Neel et al. 2021] or turning to information-theonm strong model assumptions require inefficient white-box access target models, thus limiting their applicability in practice.
analysis [Beckr and Liebig 2022]. However, they have
Attack-based: Since attacks are the most direct way to interpret privacy risks, attack-based evaluation is common metric in unlearning literature [Chen al. [021 Goel et al.) [023 Graves et al. [2020] Hayes et al. [2024] Kurmanji et al. [2023] SSmmer et al. [2020] Song and Mittal 2021
Our work belongs this category and addresses the pitfalls of existing attack-based methods.
3 Proposed evaluation framework
3.1 Preliminaries
To mitigate the limitations of directly using MIA accuracy as the evaluation metric for unlearning algorithms, we draw inspiration from cryptographic games (Katz and Lindell 2007), which are a fundamental tool to define and analyze the security properties of cryptographic protocols. In particular, we leverage the notion of advantage to form more reliable and well-calibrated metric for evaluating the effectiveness of unlearning algorithms. We leave a more detailed description to Appendix B.]
3

---

Retain
10
LR
16
Test? Forget?
Forget
Pick
Dataset
Test
Oracle
Figure 1: The unlearning sample inference game framework for our machine unlearning evaluation.
In the rest of this section, we introduce the proposed unlearning evaluation framework based on carefully designed cryptographic game and an advantage metric associated with the game. We also provide provable guarantees for the soundness of the proposed metric.
3.2 Unlearning sample inference game
We propose the unlearning sample inference game G = (UL,A, a) that characterizes the privacy risk of the unlearned models against an MIA adversary. It involves two players (a challenger named UL and an adversary A), finite dataset with a sensitivity distribution Pp defined over D, and unlearning portion parameter a. Intuitively, the game works follows:
the challenger UL performs unlearning on a "forget set" of data for model trained on the union of the "retain set" and the "forget set," with sizes of two subsets of D subject ratio o;;
the adversary A attacks the challenger's unlearned model by telling whether some random data points (according to IPD) are originally in the "forget set" or an unused set of data called "test set."
An illustration is given in Figure T detailed discussion of various design choices we made can be found in Appendix B.2 Below, we formally introduce the game, starting with the initialization phase.
The game starts by randomly splitting the dataset D into three disjoint sets: retain set R, a forgel set F, and test set T, i.e., D =: U F TU, subject to the following restrictions:
Initialization.
(a) = | U Fl: The unlearning portion a specifies how much data needs to be unlearned with respect the original dataset used by the model.
(b) |F | The sizes of and T are equal to avoid potential inductive biases.
Under restrictions (a) and [b) the size of R. F, and T are determined, depending on a. We denote S., the finite collection of all possible dataset splits satisfying restriction (a) and (b) such that 8 ~ (SS.. F is in the form of s = (R, F, T)) where the tuple is ordered by the retain, forget, and test set. After splitting ' according and the sensitivity distribution Pp. together with a secret bit E {0, 1}. The intuition of this random oracle that it offers the "two scenarios"
s, random oracle O,(b) is then constructed according
mentioned in Section 3.1 respectively specified by b 0 and = 1: when the oracle (b) is called, it emits a data point x ~ O. sampled from 1), where the sampling probability is respect to Pp.
either F (when
0) or T (when
We make some remarks on the role of the sensitivity distribution Pp. as seems opaque at first glance. Intuitively, Pp captures biases stemming from various origins, such that more sensitive data will have greater sampling probability, hence greater privacy risks. For instance, if the forget set comprises data that users request delete, with some being more sensitive than others, a corresponding bias should be incorporated into the game. In particular, we tailor our random oracle (b(b) to sample data according to IPD. so when the adversary engages with the oracle, gains increased exposure more sensitive data, compelling the challenger to unlearn such data more effectively, thereby necessitating heightened level of defense.
Challenger Phase.
The challenger is given the retain set R. the forget set F, and learning algorithm LA (takes dataset and outputs a learned model) and a unlearning algorithm UL (takes the
'Throughout the paper. (4(-) denotes the uniform distribution.

---

original model and a training subset to unlearn, and outputs an unlearned model). For simplicity, we denote the challenger as UL, as the unlearning algorithm the component under evaluation. The goal of the challenger is to unlearn F by UI. from the model trained with I.R on RR U J.F. Intuitively, for an ideal UI., for any x E F U T, accesses to the unlearned model m = (I. (R U F). As both LR and Ut. can be randomized, m follows a distribution (ML, s) depending on the split s and UL, where M denotes the set of all possible models. This distribution P.M (UL, s) summarizes the result of the challenger.
statistically impossible to decide whether x: E or a E T given
Adversary Phase. The adversary A is an (efficient) algorithm that has access to the unlearned model m = UT.(L. (R..F((()))..)))) and the random oracle O = O.(b), where both s and are unknown to A. The goal of the adversary is to guess b E (0. } by interacting with and O, i.e., after interacting with O and m, decide whether the data points from O are from or T. Notation wise, we write A (m) + 10. Note that in one play of the game, O is fixed as either (,()) or (1) but will not switch between = and b 1.
3.3 Advantage and unlearning quality
By viewing the unlearning sample inference game as a cryptographic game, with the discussion in Section 3.1 the corresponding advantage can be defined as follows:
Definition 3.1 (Advantage). Given an unlearning sample inference game G = the advantage of A against UL is defined as
Adv(A, UL)
1
Σ SES. O=0.(0)
P (A (m) (m)= SES.. O=0,(1)
Σ
Pim--P (m) 1)
Sal
To simplify notation, we sometimes omit m (UL s) and substitute (b) to the superscript of A when it's clear, i.e., we can write Pr(AA.(0) (m) = 1). With the definition of advantage, measuring the quality of the challenger UL is standard by considering the worst-case guarantee:
Definition 3.2 (Unlearning Quality). For any unlearning algorithm UL. its Unlearning Quality under an unlearning sample inference game G is defined as
Q(UL)= = 1 supu Adv(A, UL),
where the supermum is over all efficient adversary A.
Our definition of advantage (Unlearning Quality) has several theoretical merits as detailed below.
Zero Grounding for RETRAIN. Consider UL being the gold-standard unlearning method, i.c.. the retraining method RETRAIN where RETRAIN RETRAIN(LR(R U F) F and the test set T are all unforeseen data to retrained models trained only on R. one should expect RETRAIN to defend any adversary A perfectly, leading to zero advantage. The following Theorem 3.3 shows that our definition of advantage in Definition iindedd achieves such desirable zero grounding property.
(RR).. Since the forget set
Theorem 3.3 (Zero Grounding). For any adversary A, Adv(A, RETRAIN) where RETRAIN the retraining method. Hence, Q(RETRAIN) = 1.
The proof of Theorem 3.3 can be found in Appendix B.3
At a high level, the zero grounding property of the advantage is due to its symmetry-we measure the difference between (0( and (, across all possible splits in S., such that each data point has the same chance to appear in both the forget set F and the test set T. In comparison to conventional MIA-based evaluation that only measures the MIA performance on a single data split, this symmetry guarantees that all MIA adversaries have zero advantage RETRAIN even if the MIA is biased for certain data points, as the bias will be canceled out between symmetric splits that put these data points in F and T respectively.
Guarantee Under Certified Removal. We establish an upper bound on the advantage using the well-established notion of certified removal [uoo et al. 2020), which is inspired by differential privacy [Dwork 2006]:
5

---

Definition 3.4 (Certified Removal [Guo et al. 2020]; Informal). For a fixed dataset DD let LR and UL be learning & unlearning algorithm respectively, and denote to be the hypothesis class containing all possible models that can be produced by LR and Ut.. Then, for any e. >> O the unlearning algorithm UL is said to be (,,))certified removal for any W C and for any disjoint R,F D
Pr(UI,LRRRRUF)). E W) S E E W) + PI
E W) ( E W) +
Given its root in differential privacy certified removal has been widely accepted as a rigorous measure of the goodness of approximate unlearning methods (Neel et al., 2021 Chien et al. 2023), where smaller and 5 indicate better unlearning. However, in practice, it is difficult to empirically quantify (e, 6) for most approximate unlearning methods.
In the following Theorem 3.5 we provide a lower bound for the proposed Unlearning Quality for an (e, -certifie removal unlearning algorithm, showing the close theoretical connection between the proposed Unlearning Quality metric and certified removal, while the proposed metric is casier to measure empirically.
Theorem 3.5 (Guarantee Under Certified Removal). Given an -ccettii removal unlearning algorithm UI. with some 6, > 0, for any adversary against Ut, we have Adv(A, UI.) S
2 (1 2-26), Hence, QUU1.) 2 e+41 1.
4-46
The formal definition of certified removal and the proof of Theorem 3.5 can be found in Appendix B.4
B.4
3.4 SWAP test
Direct calculation requires enumerating dataset splits in S., which is computationally infeasible. Hence, we propose simple approximation scheme named the SWAP test, which requires as few as two dataset splits to approximate the advantage and still preserves desirable properties as the original definition. The idea is consider the swap pair between a forget set F and a test set TT. Specifically, pick random split (R, FRFF,T)
T) E Sa and calculate the term corresponding to in Definition 3.1
Adv, (A, UL) == Pr (U
(m) 1) PTm-PP (UL.s) (A4 (1) (m) 1).
Next, swap F and T in s to get s' = (R, F) and calculate its corresponding term in Definition 3.1
Adv (A, Ut. = PTm-FM((UL,)) (A. (4 (0) (m) = 1) - Prm-PP (A00 (m)) 1).
Finally, average the two advantages above and obtain
( (A,UL) Adv, (A, UL) + Adv, (A, UL]
In essence, we approximate Definition 3.1 by replacing S., with (8,8') Note that the SWAP test relies on the restriction (b) be valid, i.c., F [T).
SWAP Test versus Random Splits. The key insight that the SWAP test reserves the symmetry in the original definition of advantage, and as shown in Proposition 3.6 (see Remark proof), still grounds the advantage of any adversary A against RETRAIN to zero, preserving the same theoretical guarantees as Theorem 3.3
Proposition 3.6 (Zero Grounding of SWAP Test (Informal)). For any adversary A and swap splits 8,8 E S., Adv (s,er) (A,, RETRAIN) = O.
On the contrary, naively taking two random splits with non-empty overlap can lead to an adversary with high advantage against RETRAIN:
Proposition 3.7 (High Advantage Under Random Splits). For any two splits 81, 82 E S., satisfying moderate non-degeneracy assumption, there's 's an efficient deterministic adversary A such that Ady (s1,2)) (A, UL) = 1 for any unlearn method UL. Particularly, (d (A, RETRAIN) 1.
"In fact, it has been shown that a model with differential privacy guarantees automatically enjoys certified removal guarantees for any training data point [Guo et al. 2020

---

The full statement and the proof of Proposition 3.7 can be found in Appendix B.5
Remark 3.8 (Offseeting MIA Accuracy/AUC for RETRAIN). One may wonder whether we could achieve zero grounding by simply offsetting the MIA accuracy for RETRAIN zero (or offsetting the MIA AUC to 0.5). In Appendix [..6 we provide a discussion on why this stralegy will lead to pathological cases for measuring unlearning performance.
3.5 Practical implementation
While the proposed SWAP test significantly reduces the computational cost for evaluating the ad- vantage of an adversary, evaluating the Unlearning Quality is still challenging since: 1.) most of the state-of-the-art MIAs do not exploit the covariance between data points; 2.) it is impossible to solve the supremum in Definition 3.2 exactly. We will start by addressing the first challenge.
Weak Adversary. As the current state-of- the-art art MIAs make independent decisions on each data point [Bertran al. 2023 Shokri al. 2017 Carlini et al., 2022] without considering their covariance, therefore, for empirical analysis, we accommodate our unlearning sample inference game by restricting the adversary's 's knowledge such that it can only interact with the oracle once. We call such a adversary as weak adversary Au, which will first learn a binary classifier f(-) by interacting with m, and output its prediction of b [(x) by querying the oracle O (b) exactly once to obtain x ~ O, where both and are unknown to Ag. In this case, its advantage can be defined as
Adv UL)
Σ sES.
Pr (Am () =) mo ((UL,)) x~~O(()
Pr (Am(m, = -) SES, m-PM((U,,s) a~0,(1)
Σ
Sa
and the Unlearning Quality now becomes Q 1 supA, Adv(Aw: UL), analogously to Defini- tions 3.1 and 3.2] These definitions are subsumed under the original paradigm since the only difference is the number of interactions with the oracle.
Approximating the Supremum. While it is impossible to solve the supremum in Definition 3.2 exactly, a plausible interpretation is that the supremum is approximately solved by the adversary. as most of the state-of-the-art MIA adversaries are formulated
end-to-end optimization prob- lems [Bertran et al., 2023]. By assuming these MIA adversaries are trying to maximize the advantage when constructing the final classifier f(() and that the search space is large enough to parameterize all the possible weak adversaries of our interests, we can interpret that the supermum is approximately solved. Moreover, in practice. can refine the estimation of the supremum by selecting the most potent among multiple state-of-the-a MIA adversaries.
Experiment
In this section, we provide empirical evidence of the effectiveness of the proposed evaluation framework. In what follows, for brevity, we will use SWAP test to refer to the proposed practical approximations for calculating the proposed evaluation metric, which in reality a combination of
the SWAP test in Section 3.4[and and other approximations discussed in Section 3.5 We further denote
Q as the proposed metric, Unlearning Quality, calculated by the SWAP test. With these notations established, our goal is to validate the theoretical results, demonstrate additional observed benefits of the proposed Unlearning Quality metric, and ultimately show that it outperforms other attack-baser based evaluation metrics. More details can be found in Appendix C Furthermore, due to space limit, we conduct additional experiments in Appendix C.4 where we compare different unlearning algorithms' Unlearning Quality across different dataset sizes, unlearning portion parameters, datasets, and model architectures, attacks, and also a linear setting with small privacy budgets to verify our theory.
4.1 Experiment settings
We focus one of the most common tasks in the machine unlearning literature, image classification, and perform experiments on the CIFAR 10 dataset (Krizhessky al. [2009), which is licensed under CC-BY 4.0. Moreover, we opt for ResNet (He et 2016) as the target model produced by some learning algorithms LR, whose details can be found in Appendix setup of the unlearning sample inference game G (A, UL, D, PP a for the evaluation experiment:
Finally, the following the
7

---

Initialization: Since some MIA adversaries require training the so-called shadow models using data sampled from the same distribution of the training data used by the target model [Shokni et al. 2017], we start by splitting the whole dataset to accommodate the training of shadow models. In particular, we split the given dataset into two halves, one for training the target model (which we call the target dataset), and the other for training shadow models for some MIAs. The target dataset what we denoted as DD in the game. To initialize the game, we consider a uniform sensitivity distribution PD = (DD since we do not have any prior preference for the data. The unlearning portion parameter set to be a = 0.1 unless specified. This implies (2( = U(F) and O = U(T,, where (R, F) Sa is the split we choose to use for the game.
Challenger Phase: As mentioned at the beginning of the section, we choose the learning algorithm LR which outputs ResNet as the target model. On the other hand, the corresponding unlearning algorithms UL we select for comparison are: 1.) RETRAIN: retrain from scratch (the gold-standard);
2.) FISHER: Fisher forgetting [Golatkar et al., 2020]; 3.) FIFINAL: fine-tuning final layer [Goel
et al. 2023]; 4.) RETRFINAL: retrain final layer [Goel al.] 2023]; 5.) NEGGRAD: negative gradient descent [Golatkar et al. 2020]; 6.) SALUN: saliency unlearning (Fan et al., 2024];
7.) SSD: selective synaptic dampening [Foster et al. [024]; 8.) NONE: identity (no unlearning, dummy baseline). Among them, RETRAIN the gold standard for exact unlearning while NONE is a dummy baseline for reference. All other methods approximate unlearning methods, with SSD being the most recent state-of-the-art methods.
Adversary Phase:
Since we're unaware of any non-weak MIAs, we focus on the following SOTA black-box (weak) MIA adversaries A to approximate the advantage: 1.) shadow mod- el-based (Shokri et al. 2017]; 2.) correctness-based, confidence-based, modified entropy [Song and
Mittal 2021].
4.2 Ablation study
We first provide some empirical evidence that our approximation is reasonable and effective through two lenses: dataset size and a.
Unlearning Quality Versus Dataset Size. We vary the dataset size to assess how the unlearning quality metric Q scales with data. Experiments conducted with 0.1, and results are shown in Table[[ The relative ranking of unlearning methods remains consistent across sizes, indicating that small-scale evaluations can reliably approximate large-scale performance. This scalability makes Q an efficient and practical metric for benchmarking unlearning algorithms. The retraining method maintains Q 1, further confirming the theoretical grounding in Theorem 3.3
Table 1: Unlearning Quality versus dataset size (in percentage). The relative ranking of different unlearning methods with added standard deviations.
UL
n
0.1
0.4
0.8
1.0
RETRFINAL
0.340 = 0.017
0.586 = 0.015
0.621 + 0.014
0.634 0.025
FTFINAL
0.131 0.011
0.585 = 0.016
0.619 0.014
0.63440.022
FISHER
0.751 0.024
0.679 = 0.005
0.734 0.006
0.791
NEGGRAD
0.124 + 0.010
0.564 + 0.018
6603+0000
0.656 + 0.035
SALUN
0.476 + 0.014
0.617 + 0.016
0.689
+ 0.013
0.748+
SSD
0.975 + 0.008
0.939 + 0.025
0.929
+ 0.021
0.928 + 0.015 0.015
RETRAIN
0.999 0.000
0.997 - 0.001
0.993 0.001
0.993 + 0.001
Unlearning Quality Versus a. We further vary the unlearning portion parameter a, defined as the ratio of the forget set to the full training set, to investigate how the unlearning quality metric Q changes. The results are presented in Table We observe that the relative ranking of different unlearning methods remains largely consistent across varying a values. This stability suggests that our metric reliably captures the comparative performance of unlearning algorithms under different data removal proportions.
8

---

Table 2: Unlearning Quality versus a. The relative ranking of different unlearning methods stays mostly consistent across different a.
UL
0.1
0.25
0.4
0.67
RETRFINAL
0,513 = 0.054
0,489 = 0.055
0.413 0.027
0.500 = 0.024
FTFINAL
0.511 0.054
0.484
0.054
0.394 0.041
0.479 0.020
FISHER
0.904+0.00
+ + 0.044
0.908 + 0.038
0.810 = 0.050
NEGGRAD
0.637
0.757
0.631 0.088
SALUN
0.755=0001
0.762
0.895
= 0.047
0.893 = 0.028
SSD
0.944 0.038
0.960 : 0.019
0.837 = 0.054
0.913 0.037
4.3 Validation of theoretical results
We empirically validate Theorems and 3.5 While it is easy to verify grounding, i.e., Q(RETRAIN) = 1, validating the lower-bound of Q for unlearning algorithms with (c, -ccertifiee removal guarantees is challenging since such algorithms However, the model is trained with (c, 8) diifferrenta privacy (DP) guarantees, then even if we do not apply any unlearning on the model (i.e., UI. NONF), the model still automatically satisfies (c, certtffiee removal for any training data point [Guo et al. 2020]. As the DP algorithm exists for non-convex models [Abadi al., 2016), this suggests that one
not known beyond convex models.
analyze the impact of the DP privacy budget on @ of an (e, 0D-DP model. In particular, we fix 8 = 10-5 and consider varying to be 50, 150, 600, and oc (co corresponds no DP training). The corresponding Unlearning Quality results are reported in Table
Firstly, as be from the last of Ta- ble 3 ((RETRAIN) == with high precision for all e, achieving grounding almost perfectly, thus validating Theorem 3.3 Furthermore, The- orem 3.5 suggests that the lower bound of Q should negatively correlate with c. Indeed, em-
Table 3: Unlearning Quality versus DP budgets. We use to indicate that the results' standard error of the mean < 0.01 and use for < 0.005.
50
150
600
oc
pirically, we observe such a trend with high pre- cision, again validating our theoretical findings. Moreover, Table 3 shows that the Unlearning Quality also maintains a consistent relative rank- ing between unlearning algorithms among dif- ferent proving its robustness. Finally, our met- ric suggests that SSD significantly outperforms other unlearning methods, which is consistent with the fact that it is the most recent ofate-of-the-art method among the unlearning methods we evaluate.
NONE
0,972'
0.960'
0.932
0,587'
NEOGRAD
0.980
0.9751
0.953
0.628
RETRFINAL
0,972
0.964
0.939'
0,576
FIFINAL
0.973
0.963'
0.939'
0.574
0.9671
0.709
SALUN
0.979
0.972
0.945
0.689'
SSD
0.996
0.988
0.981
0.888'
RETRAIN
0.998
0.996'
0.997
0.993'
Remark 4.1. From T even for NONE with = cc. the Unlearning Quality Q. is still relatively high (0.587). This partly because the current state-of-the-arl (weak) MIA adversaries are not good enough: if the weak adversary becomes better, our evaluation metric can also benefit from this. Remark 4.2. We distinguish between A) the computation cost of the proposed unlearning evaluation metric and B) the cost of evaluating the metric itself. The latter significantly higher due to DP training and is reported in the appendix. In real applications, only the scalable cost of A) is incurred.
4.4 Comparison to other metrics
We compare our Unlearning Quality metric Q to other existing attack-based evaluation metrics, demonstrating the superiority of the proposed metric. We limit our evaluation to the MIA-based evaluation, and within this category, three MIA -ased evaluation metries are most relevant to our setting ITriantafillou and Kairouz 2023 Golatkar et al.) 2021 Goel et al.] [023). While none of them enjoy the grounding property, in particular, the one proposed by Triantafillou and Kairouz 2023 requires training attacks for every forget data sample, which is extremely tome-consuming. and we leave it out from the comparison and focus on comparing our metric with the other two.
The two metrics we will compare are the pure MIA AUC (Area Under Curve) [Golatkar al. 2021 and the Interclass Confusion (IC) Test Goel et al. 2023 The former is straightforward but falls

---

Table Comparison between IC score and MIA score under different DP budgets. See Table 3 for more context.
(A) IC score versus DP budgets.
(B) MIA score versus DP budgets.
50
150
600
OG
50
150
600)
NONE
0.749'
0.720'
0.717
0.00S
NONE
0.451
0.435'
0.454'
0.380
NEGGRAD
0,925
0.953'
0.946
0.180'
NEGGRAD
0.476
0.482
0,466
0.299
RETRFINAL
0,931
0.958'
0.893
0.053'
RETRFINAL
0.485'
0.485
0.472'
0.248
FIFINAL
0,930
0.957
0.893
0,346
FTFINAL
0.485'
0.485
0.472'
0.247'
FISHER
0.743
0.720!
0.702
0,344
FISHER
0.475'
0.484
0.463'
0.325
SALUN
0,866
0.887"
0.841
0,081
SALUN
0.488
0.491
0.477'
0.268
SSD
0.976
1.000"
0.990
0.174'
SSD
0.480
0.480
0.468'
0.244
RETRAIN
0.962
0.972'
0.976
0.975
RETRAIN
0.479
0.491
0,492
0.488
short in many aspects as discussed in the introduction; the latter, on the other hand, is a more refined metric. In brief, the IC test "confuses" a selected set S of two classes by switching their labels and training a model on the modified dataset. It then requests the unlearning algorithm to unlearn S and measures the inter-class error y E [0, 1] of the unlearned model on S. Similar to the advantage, Y is the "flipped side" of the unlearning performance, which suggests defining the IC score by Similarly, for the sake of clear comparison, we report the MIA score defined as "1 MIA AUC" as the unlearning performance, where the MIA AUC is calculated on the union of the forget set and test set. We leave the details to Appendix
We conduct the comparison experiment by again analyzing the relation between the DP privacy budger versus the evaluation result of an (c, d)- model for the two metries we are comparing with under the same setup as in Table 3 Specifically, we let 6 = 10 and consider varying from 50 to oo, and we look into two aspects: 1) negative correlation with e; 2) consistency w.r.t. e. The results are shown in Table 4 Firstly, we see that according to Table 4(A) the IC test fails to produce a negatively correlated evaluation result with c. For instance, the IC score for NEGGRAD is notably lower at c = 50 than at e = 150, and RETRFINAL and FTFINAL also demonstrate higher IC score at <= 150 than at c 600. Furthermore, in terms of consistency w.r.t. c, we again see that the IC test fails to satisfy this property, unlike the proposed Unlearning Quality metric Q. For example, while NONE better than NEGGRAD at e = 50, this relative ranking is not maintained at co. Such an inconsistency happens multiple times across Table 4(A) A similar story can be told for the MIA AUC, where from Table [ the evaluation results negatively correlated with e. For instance, the MIA scores for NEGGRAD and FISHER are notably higher al e = 150 than at e = 600. Furthermore, in terms of consistency w.r.t. see that while NEGGRAD outperforms FISHER FISHER at c = 150, which is inconsistent. Overall, both the IC test and the MIA AUC fail to satisfy the properties that have established for the Unlearning Quality, demonstrating our superiority.
we see that MIA AUC also fails to produce a similar trend as Q where
50 and 600, it performs worse than
5 Conclusion
In this work, we developed a game-theoretical framework named the unlearning sample inference game and proposed novel metric for evaluating the data removal efficacy of approximate unlearning methods. Our approach is rooted in the concept of "advantage," borrowed from cryptography, to quantify the success of an MIA adversary in differentiating forget data from test data given an unlearned model. This metric enjoys zero grounding for the theoretically optimal retraining method, scales with the privacy budget of certified unlearning methods, and can take advantage (as opposed to suffering from conflicts) of various MIA methods, which are desirable properties that existing MIA-based evaluation metrics fail to satisfy. We also propose practical tool the SWAP test to efficiently approximate the proposed metric. Our empirical findings reveal that the proposed metric effectively captures the nuances of machine unlearning. demonstrating its robustness across varying dataset sizes and its adaptability to the constraints of differential privacy budgets. The ability to maintain a discernible difference and a partial order among unlearning methods, regardless of dataset size, highlights the practical utility of our approach. By bridging theoretical concepts with empirical analysis, our work lays a solid foundation for reliable empirical evaluation of machine unlearning and paves the way for the development of more effective unlearning algorithms.
10

---

References
Martin Abadi, Andy Chu, lan Goodfellow, H. Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS'16. ACM, October 2016. doi: 01155/997744.29783111
Alexander Becker and Thomas Liebig. Evaluating machine unlearning via epistemic uncertainty, 2022.
Martin Andres Bertran, Shuai Tang, Aaron Roth, Michael Kearns, Jamie Heather Morgenstern, and Steven Wu. Scalable membership inference attacks via quantile regression. In Thirty-seventh Conference Neural Information Processing Systems, 2023.
Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette- Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot. Machine unlearning. In 202/ IEEE Symposium on Security and Privacy (SP), pages 141-159. TEEE, 2021.
Brennon Brimhall, Philip Mathew, Neil Fendley, Yinzhi Cao, and Matthew Green. Mirror mirror on the wall, have forgotten it all? new framework for evaluating machine unlearning, 2025. URL https://arxiy: http://xxxiio..//aaa.// abs wwwpr///.b/255.....m 2000 08138
Yinzhi Cao and Junfeng Yang. Towards making systems forget with machine unlearning. 2015
IEEE symposium on security and privacy, pages 463-480 IEEE, 2015.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In 2022 IEEE Symposium on Security and Privacy (SP), pages 1897-1914. IEEE, 2022.
CCPA. California consumer privacy act (cepa), 2018.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. When machine unlearning jeopardizes privacy. In Proceedings of the 2021 ACM SIGSAC conference computer and communications security, pages 896-911, 2021.
Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang Graph unlearning. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS '22. ACM, November 2022. doi: 10.1145//5486003355553
Eli Chien, Chao Pan, and Olgica Milenkovic. Efficient model updates for approximate unlearning of graph-structured data. International Conference on Learning Representations, 2023.
Rishav Chourasia and Neil Shah. Forget unlearning: Towards true data-deletion in machine learning.
In International conference machine learning, pages 0228-603.. PMLR, 2023.
Ana-Maria Cretu, Daniel Jones, Yves-Alexandre de Montjoye, and Shruti Tople. Re-aligning shadow models can improve white-box membership inference attacks. arXiv preprint 230.000300 2023.
Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume (long and short papers), pages 4171-4186, 2019.
Cynthia Dwork. Differential privacy. In International colloquiun automata, languages, and programming, pages 1-12. Springer, 2006.
Chongyu Fan, Jiancheng Liu. Yihua Zhang, Eric Wong, Dennis Wei, and Sijia Liu. Salun: Em- powering machine unlearning via gradient-based weight saliency in both image classification and generation. In The Twelfth International Conference on Learning Representations, 2024.
Jack Foster, Stefan Schoepf, and Alexandra Brintrup. Fast machine unlearning without retraining through selective synaptic dampening. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 2043-12051. 2024.

---

Shashwat Goel, Ameya Prabhu, Amartya Sanyal, Ser-Nam Lim, Philip Torr, and Ponnurangam Kumaraguru. Towards adversarial evaluations for inexact machine unlearning, 2023.
A. Golatkar, A. Achille, and S. Soatto. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9301-9309 Los Alamitos, CA, USA, jun 2020. IEEE Computer Society. doi: 10.100/CVVP42660222000000
Aditya Golatkar, Alessandro Achille, Avinash Ravichandran. Marzia Polito, and Stefano Soatto. Mixed-privant forgetting in deep networks. In 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 792-801, 2021. doi: LL009///VRR44433.222...0000
Laura Graves, Vineel Nagisetty, and Vijay Ganesh. Amnesiac machine learning. In AAAI Conference Artificial Intelligence, 2020.
Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In International Conference on Machine Learning, pages 3832-3842. PMLR, 2020.
Jamie Hayes, Ilia Shumailov, Eleni Triantafillou, Amr Khalifa, and Nicolas Papernot. Inexact unlearning needs more careful evaluations to avoid a false sense of privacy. arXiv preprint arXiv:2403.01228. 2024.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Yingzhe He, Guozhu Meng, Kai Chen, Jinwen He, and Xingbo Hu. Deepobliviate: a powerful charm for erasing data residual memory in deep neural networks. arXiv preprint arXiv:2105.06200 2021.
Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approximate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics, pages 2008-2016. PMLR, 2021.
Jonathan Katz and Yehuda Lindell. Introduction to modern cryptography; principles and protocols. Chapman and hall/CRC, 2007.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. University of Toronto, 2009.
Meghdad Kurmanji, Peter Triantafillou, Jamie Hayes, and Eleni Triantafillou. Towards unbounded machine unlearning. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors,
Aditors,Advancee Advances in Neural Information Processing Systems, volume 36, pages 1957-1987. Curran Associates, Inc., 2023.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist// 1998.
Alessandro Mantelero. The eu proposal for a general data protection regulation and the roots of the 'right be forgotten'. Computer Law & Security Review, 29(3):229-235, 2013. ISSN 0267-3649. doi: https://doi. http://doi.or//1000 10. clr223..ss.2001.033..00
Seth Neel, Aaron Roth, and Saced Charifi-Malvajerdi Descent-to-delete: Gradient-based methods for machine unlearning. In Algorithmic Learning Theory, pages 931-962. PMLR, 2021.
Alexandra Peste, Dan Alistarh, and Christoph H. Lampert. Ssse: Efficiently erasing samples from trained machine learning models, 2021.
Youyang Qu, Xin Yuan, Ming Ding, Wei Ni, Thierry Rakotoarivelo, and David Smith. Learn to unlearn: Insights into machine unlearning. Computer, 57(3):79-99, 2024.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04747, 2016.
12

---

Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh, Remember what you want to forget: Algorithms for machine unlearning. Advances Neural Information Processing Systems, 34: 184418075111 1877--80066 2021.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP). pages 3-18, 2017. doi: 10.1109/SP:017..4..
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng. and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In David Yarowsky, Timothy Baldwin, Anna Korhonen, Karen Livescu, and Steven Bethard, editors, Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1631-1642, Seattle, Washington, USA, October 2013. Association for Computational Linguistics. URL https://aclantbbooogy-.ooo www.ehhoooooooo/11111111111 1170/
David Marco Sommer, Liwei Song, Sameer Wagh, and Prateek Mittal. Towards probabilistic verification machine unlearning. CoRR, abs/2003.04247. 2020.
Liwei Song and Prateek Mittal. Systematic evaluation of privacy risks machine learning models. In 30th USENIX Security Symposium (USENIX Security 2/), pages 2615-2632, 2021.
Eleni Triantafillou and Peter Kairouz. Evaluation for the NeurIPS Machine Unlearning Competition, 2023. [Accessed 10-01-2024).
Yinjun Wu, Edgar Dobriban, and Susan Davidson. Deltagrad: Rapid retraining of machine learning models. In International Conference on Machine Learning, pages 10355-10366. PMLR, 2020.
Heng Xu, Tianqing Zhu, Lefeng Zhang, Wanlei Zhou, and Philip S. Yu. Machine unlearning: survey, 2023.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and llya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109.12298, 2021.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly define the scope of both the theoretical and empirical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Section 5 and in the appendix.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Given the theoretical nature of this paper, we have diligently ensured the accuracy of the theorem statements and proofs.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Our code is included in the supplementary materials.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
Justification:
Our code is included in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ Soa.leees//ooSSeemiissebe
www.SSubmisiooooiiiooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:The details of the experiments are discussed in Section 4.1 and in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We have closely investigated the variance of our experiments by reporting our results with multiple random dataset splits in Section 4] and also comparing the variance of our proposed swapped test with that of random dataset splits in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information on the compute resources is reported in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.c /
Answer: [Yes]
Justification: Every author of this submission has reviewed the code of ethics guidelines and confirms compliance.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: While our work is theoretical nature, it still has an empirical impact as our theory is designed with practical scenarios in mind. We discuss some of the potential societal impacts in the appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We properly cite the datasets and include their licenses in Section 4
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The paper does not involve LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
20

---

A Additional related work
Machine Unlearning. Techniques like data sharding [Bourtoule et al. 2021 Chen et al. 2022] partition the training process in such a way that only portion of the model needs to be retrained when removing subset of the dataset, reducing the computational burden compared retraining the entire model. For example. [uuo et al. [2020), Neel et al. [202T], CCien et al. (2023) analyzed the influence of removed data on linear or convex models and proposed gradient-based updates on model parameters to remove this influence. Chourasia and Shah [023) proposed an unlearning method that appears similar to ours but differs in key aspects, particularly in the definition of advantage, a term whose meaning varies by threat model. Their threat model leads to criterion for unlearning effectiveness, but like theory-based approaches such as certified removal, it is hard to empirically evaluate for most approximate methods lacking guarantees. In contrast, our threat model is tailored to enable a practical and novel evaluation metric, addressing a key gap in unlearning research.
Retraining-based Evaluation. Generally, trraininn-basele evaluation seeks to compare unlearned models to retrained models. As introduced in the works by Golatkar et al. [202] J. He al. [202]], Golatkar et al. 2020]. model accuracy on the forget set should be similar to the accuracy on the test set as if the forget never exists in the training set. |Peste al. [02T]] proposed an evaluation metric
based on the normalized confusion matrix element-wiss difference on selected data samples. Golatkar al.] [202]] proposed using relearn time, which is the additional time use for unlearned models to perform comparably to retrained models. The authors also proposed to measure the L distance between the final activations of the scrubbed weights and the retrained model. /Wu et al.] [2020), Izzo
et al. [021] turned to l distance of weight parameters between unlearned models and retrained models. In general, beyond the need for additional implementation and the lower computational efficiency inherent in retraining- sarainnngg-based evaluations, a more critical issue is the influence of random factors. As discussed by Cretu et al. [023), such random factors, including the sequence of data batches and the initial configuration of models, can lead to the unaligned storage of information within models. This misalignment may foster implicit biases favoring certain retrained models.
Theory-based Evaluation. Some literature tries to characterize data removal efficacy by requiring strict theoretical guarantee for the unlearned models. However, these methods have strong model assumptions, such as convexity or linearity, or require inefficient white-box access to target models, thus limiting their applicability in practice. For example, (uo et al. [2020), Neel et al. [202T). Chien itt al. [2023) focus on the notion of the certified removal (CR), which requires that the unlearned model cannot be statistically distinguished from the retrained model. By definition, CR is parametrized by privacy parameters called privacy budgets, which quantify the level of statistical indistinguishability. Hence, models with CR guarantees will intrinsically satisfy an "evaluation metric" induced by the definition of CR, acting as a form of "evaluation." On the other hand, |Becker and Liebig] [2022] adopted an information anformation-thcoretical theoretical perspective and turned epistemic uncertainty to evaluate the information remaining after unlearning. A concurrent study (Brimhall et al. 2025) that appeared later than this paper proposes a framework for evaluating machine unlearning called computational unlearning, inspired by cryptographic indistinguishability games between retrained models and unlearned models. Their framework shares similar motivations to ours but has different technical assumptions.
Attack-based Evaluation. Since attacks are the most direct way interpret privacy risks, attack- based evaluation is a common metric in unlearning literature. The classical approach is to directly calculate the MIA accuracy using various kinds of MIAS [Graves al. 20200 Kurmanji et al.] 2023). One kind of MIA utilizes shadow models [Shokri et 2017). which are trained with the same model structure as the original models but on shadow dataset sampled with the same data sampling distribution. Moreover, some MIAS calculate membership scores based on correctness and confidence (Song and Mittal [021]. Some evaluation metrics do move beyond the vanilla MIA accuracy. For example, Triantafillou and Kairouz (2023) leveraged hypothesis testing coupled with MIAs compute an estimated privacy budget for each unlearning method, which gives a rather rigorous estimation of unlearning efficacy. Hayes et al. [2224] proposed novel MIA towards machine unlearning based on Likelihood Ratio Attack and evaluated machine unlearning through a combination of the predicted membership probability and the balanced MIA accuracy on test and forget sets. They designed a new MIA attack with similar attack-defense game framework. There are other evaluation metrics also based on MIAs, but with different focuses. However, as they still use MIA accuracy as the evaluation metric, the game itself doesn't bring much for their evaluation framework other than clear experiment procedure. Goel et al. [0033 proposed an Interclass
21

---

Confusion (IC) test that manipulates the input dataset to evaluate both model indistinguishabiiiyy and property generalization. However, their metric is less direct in terms of interpreting real-life privacy risks. Lastly, For example, Chen et al. (202T) proposed novel metric based on MIAs that know both learned and unlearned models with a focus on how much information is deleted rather than how much information is left after the unlearning process. [Sommer et al. (2020) provided backdoor verification mechanism for Machine Learning as a Service (MLaaS), which benefits an individual user valuing his/her privacy to verify the efficacy of unlearning. They focus more on user-level verification rather than model-level evaluation.
B
Omitted details from Section 3
B.1 More details of advantage
In cryptographic games, there are two interacting players: a benign player named challenger rep- resenting the cryptographic protocol under evaluation (corresponding to the unlearning algorithm in our context), and an adversary attempts to compromise the security properties of the challenger. The game proceeds in several phases, including an initialization phase where the game is initialized with specific configuration parameters, a challenger phase where the challenger performs the crypto- graphic protocol, and adversary phase where the adversary queries allowed by the game's rules and generates a guess of the secret protected by the challenger. Finally, the game concludes with a win loss for the adversary, depending on their guess. In the context of machine unlearning, the goal of the adversary is to guess whether certain given data comes from the set to be unlcarned (the forget set) or the set never used in training (the test set), based on access the unlearned model.
The notion of advantage quantifies, in probabilistic terms, how effectively an adversary can win the game when it is played repeatedly. It is often defined the difference in the adversary's 's accepting rate between two distinct scenarios (e.g.. with or without access to information potentially leaked by the cryptographic protocol) [Katz and Lindell 2007]. In the context of machine unlearning, the two scenarios can refer to the data given to the adversary coming from either the forget set or the test set, respectively. The game is constructed such that, if the cryptographic protocol is perfectly secure (i.e., the unlearned model has completely erased the information of the forget set), the adversary's s advantage is expected to be zero, making it well-calibrated measure of the protocol's security.
B.2 Design choices
In this section, we justify some of our design choices when designing the unlearning sample inference game. Most of them are of practical consideration, while some are for the convenience of analysis.
Uniform Splitting. At the initialization phase, choose the split uniformly rather than allowing sampling from an arbitrary distribution. The reason is two-fold: Firstly, since this sampling strategy corresponds to the so-called i...d. unlearning setup [Qu et al. 2024), i.e., the unleamed samples will be drawn from a distribution of DD in an i.i.d. fashion. In this regard, uniformly splitting the dataset corresponds to a uniform distribution of D for the unlearned samples to be drawn from. This the most commonly used sampling strategy when evaluating unlearning algorithms since it's difficult to estimate the probability that data will be requested be unlearned.
Secondly, Qu et al. [2024] acknowledged the significantly greater difficulty of no.-i.i.d unlearning compared to i..dd unlearning empirically. A classic example of non-i.i.d. unlearning is the process of unlearning an entire class of data, where a subset of data shares the same label. Conversely, even non-uniform splitting complicates the analysis, leading to the breakdown of our theoretical results. Specifically, generalizing both Theorem 3.3 and Theorem 3.5]jeommss non-trivial. Overall, non-uniform splitting presents obstacles both empirically and theoretically.
Intrinsic Learning Algorithm for Challenger. The challenger, which we denote as UL, has learning algorithm LR in mind in our formulation. This is because the existing theory- -based unlearn- ing method, such as the certified removal algorithm [Guo et al., 2020) as defined in Definition [B.3] is achieved by combination of the learning algorithm and a corresponding unlearning method to support unlearning request with theoretical guarantees. other words, given an arbitrary learning algorithm LR, it's unlikely to design an efficient unlearning algorithm UL with strong theoretical guarantees, at least this is not captured by the notion of certified removal. Hence, allowing the challenger to choose its learning algorithm accommodates this situation.
22

---

Black-box Adversary v.s. White-box Adversary. By default, we assume that m is given to A in a black-box fashion, ie.. A only has oracle access m. However, our framework can also adapt to white-box adversaries, which requires full model parameters of m. The only difference is that the efficiency definition changes accordingly, i.e., polynomial time in the size of [D] for a black-box adversary or polynomial time in the number of parameters of m for white-box adversary.
Strong adversary in practice. As discussed in Section 3.5 the current state-of-the-art MIA adversaries are all weak. While it is possible to formulate the unlearning sample inference game entirely with the weak adversary, we discuss the rationale behind considering the strong adversary. One of the apparent reasons is simply that the strong adversary encompasses the weak adversary, thereby enhancing the generality of our framework and theory. However, we argue that the strong adversary is practical in many real-world scenarios, and bringing this stronger notion has further practical impacts beyond blindly generalizing our model.
Consider a scenario where an adversary conducts a membership inference attack on large scale. We argue that practice, it more reasonable to aim for high overull membership accuracy of set of carefully chosen data points, rather than the individual membership status of each of them. For example, consider the case where we are interested in images sourced from the internet. this case, it is safe to assume that images within the same webpage are either all included in the model training dataset or none are, if we assume that the training data is collected via some reasonable data mining algorithms. In such case, the ability of an adversary to infer the common membership for group of data points from a particular webpage becomes desirable as is likely to enhance the overall MIA accuracy. We believe that this stronger notion of MIA adversary has more practical impacts and reflects the common practice when deploying the membership inference attack; therefore, we choose to formulate the unlearning sample inference game with it.
B.3 Proof of Theorem 3.
We now prove Theorem 3.3
We repeat the statement for convenience.
Theorem B.1. For any (potentially inefficient) adversary A, its advantage against the retraining method RETRAIN in an unlearning sample inference game G A, a) zero, iee, Adv(A, RETRAIN) = O.
Proof. Firstly, we may partition the collection of all the possible dataset splits S,, by fixing the retain sets R D. Specifically, denote the collection of dataset splits with the retain as [R] = {s E S.: = (R, -.... With the usual convention, when there's no dataset split corresponds R, [R]
be R
Observe that for any E S, [R] we can pair it up with another dataset split that swaps the forget and test sets in s. In other words, for any = (R, F, T) E Sa(R), we see that T. is also SR. since we assume |F = [T], every dataset split will be paired. In addition, since R is fixed in S. RR]. we know that P P [RETRAIN, s) = P. FM((R (R) is the same for all E S. [R] since the unlearning algorithm UL RETRAIN, i... it only depends on R. With these observations, we can then combine the paired dataset splits within the expectation.
Specifically, for any (R). let s' E S., to be s's pair, i.e., if s (R. F, T) for some F and T, then s' = (R, T, F). Finally, for given R, let's denote the collection of all such pairs as
PR = 8( c [R s = (R.F.T). = (R,T,F) for some F, T),
where we use a set rather than an ordered list for the pair 8, s' since we do not want to deal with repetitions. Observe that (O) (1) and (1) (0)(0) since the oracles are constructed
23

---

with respect to the same preference distribution for all data splits, Hence, we have Ad, RETRAIN)
1
Σ
Pr m>PMMRRETRAM 8) (0).(0)
(A0 =1]
Pr
(40
S
m PM (RETRAINN, (10.(1)
sESa
1
Σ
Σ
Pr
(m =
Pr
(A 1)
S
mr (REERAIN,, (=0,(0)
m (R.PANRET (10,(1)
RCD PEP
Pr MOREMMRRTAANN (=0,,(0)
(m) =1
Pr
(m =1)
M 8') (=0,(11
1
Σ
Σ
Pr (R) (=0,(0)
(A (m) =1) (R) 0=0,(1)
Pr
(40 =
Sa
RCD EP
Pr (m)m)= = (>P 0=0,(1)
Pr (1 = =1) =0
m-PM o=0.(0)
Before we end this section, we remark that the above proof implies that the SWAP test also grounds the advantage to zero:
Remark B.2. Consider a pair of swapped splits s and s'. Observe that for RETRAIN, PM (RETRAIN, s) P (RETRAAI,, 8') (RR) since this probability only depends R.
which is the same for and s'. With O, (0) = =O, (1) and 01(1) = (O), we have
Adv (a,00) Adv (A, RETRAIN) =
(m10000(m) =1) Pr M(PM(R
Pr
(40.00) (m)= =1)
Pr (R)
(m0 =1) mRPM(R)
Pr (40.(0) 1) 0.
B.4 Proof of Theorem 3.5
We prove Theorem 3.5 in this section. Before this, we formally introduce the notion of certified removal.
Definition B.3 (Certified Removal [Guo et al. 2020).. For fixed dataset D, let LR and UL be learning and an unlearning algorithm respectively, and denote H := im(LR) U Jimm( (UL 11o to be the hypothesis class containing all possible models that can be produced by LR and UL. Then, for any 8 > O, the unlearning algorithm UL is said to be (c, -eettifie removal for any W C H and for any disjoint R,F C D (do not need to satisfy restriction [a) and (b)..
P E W) - < E W) + + P E W) < ( E W) +
We note that as RETRAIN(LR(RUU)..F = LR((R), the above can be simplified to
P((UL(LR(RUF))FF E W) < c'PP(LR(R) +
Pr(LR(R) E W) < ( +6.
Now, we restate Theorem 3.5 for convenience.
Here, im(+) denote the image of function.
24

---

Theorem B.4. Given an (c, 8) -certffid removal unlearning algorithm UL with some e, > 0. for any (potentially inefficient) adversary A against UL in an unlearning sample inference game we have
2 20 2-20 )
Adv UL) 2
Proof. We start by considering an attack as differentiating between the following two hypotheses: the unlearning and the retraining. In particular, given specific dataset split = (R, F, T) E Sa and an model m, consider
H1: = UT.(LRR(UF))F)) and H2: = (R(R) RETRAIN(LR CIIURUR F).
Alternatively, by writing the distribution of the unlearned models and the retrained models as PM(UL, s) and PM(RETRAIN, s), respectively, we may instead write
H1: - (UL, s). and H2: m PM (RETRAIN, 8).
turns out that by looking at the rype-I enror a and rype-ll error 3, we can control the advantage of the adversary in this game easily. Firstly, denote the model produced under H1 mi, then under = 1 a. Similarly, by denoting
H1, the accuracy of the adversary is PPmm~PM (A(m))
the model produced under H2 as ma,, we have PrmmsPPMl (KETRAINN () (A(m2) = 1) = 3. Therefore, for this specific dataset split s, let's define the advantage of this adversary A for this attack as
Adv. = |1 - -a-a-- 31-
The upshot is that since UL is an (e, 0)-ertiffiedd removal unlearning algorithm (Definition B.3 it is possible to control and 3, hence (A). To achieve this, since from the definition of certified removal, we' re dealing with sub-collections of models, it helps to write a and 3 differently.
Let H (P (P,, M (UL, s)) U supp(IP, M and denote C H to be the collection of models that the adversary A accepts, and B to denote its complement, i.e., the collection of models that the adversary A rejects. We can then re-write the type-I and type-Il eτrоrs as
(erpp((PMMRETRAAI (RETRAIN, 8)) be the collection of all possible models,
Type-I error a: probability of rejecting Hi when H1 is true, i.e., = Pr(mm E B () Pr(m, E {
Type-Il error B: probability of accepting H2 when Hg false, i.e., B == Pr(m2 E B 8).
With this interpretation and the fact that Ut. (c, -eettifie removal, we know that
* Pr(m; E B 8) S e Pr(m2 E B 8) + 8, and
Pr(mm E B < e Pr(m: E B s) + 8.
Combining the above, we have 1 S 3 + 6 and 1 8 S a + Hence,
B max (0,
E aa)-
We then seek to get the minimum of a + 3, we have
2 max (a, 1 - e'a + a, e (1 ö a)) + at)
To get lower bound, consider the minimum among the last two, i.e., consider solving a when 1 8- a (1 - 8 a) a, leading to
= (e- - 1)(1 - = a= (e - 1)(1 - -0) (c= = 8) - (1 - (1-
- e-c-et
Hence, we have
a +++221-0t(1-c)- 1- (c+--1(( 8) (1 (1-c²) 111-111111 (1-6) - -2 -
2 2
=(1-
er "Note that this is different from the advantage we defined before since the attack is different, hence we use different notation.
22c²
25

---

with the elementary identity 1 - e (1+ -e),, we finally get
28
a + 8 e" +
On the other hand, considering the "dual attack" that predicts the opposite the original attack, that is, we flip B and 8 In this case, the type-I error and the type-1l error become and 1 - B, respectively. Following the same procedures, we'll have + 3 < e"+I
2-26
Note that the definition of (e, -certiffe removal is independent of the dataset split s, hence, the above derivation works for all In particular, the advantage of any adversary differentiating H1 and H2 for any s is upper bounded by
2 2 2-
Adv, =1 3-
<
e +1
where we denote to be the upper bound of advantage. This means that any adversaries trying to differentiate between retrain models and certified unlearned models are upper bounded terms of their advantage, and an explicit upper bound is given by
We now show a reduction from the unlearning sample inference game the above. Firstly, construct two attacks based on the adversary A in the unlearning sample inference game, which tries differentiate between the data point x sampled from the forget set F the test T. This can be formulated through the following hypothesis testing:
H3: x E and E.
In this viewpoint, the unlearning sample inference game can be thought of as deciding between H3 and H4. Since the upper bound we get for differentiating between H1 and H2 holds for any efficient adversaries, therefore, we can construct an attack for deciding between H1 and H₂ using adversaries for deciding between H3 and H4. This allows us upper bound the advantage for the latter adversaries.
Given any adversaries A for differentiating H3 and H4, i.e., any adversaries in the unlearning sample inference game, we start by constructing our first adversary A₁ for differentiating H₁ and H2 as follows:
In left world (H)), feed the certified unlearned model to A; in the right world H2, feed the retrained model to A.
We create random oracle (0) for A, i.e., we let the adversary A decide on F. We then let A₁ output as A.
We note that A is deciding on F, the advantage of Ai is
Adv, (AI)=
Pr my (UU.,. O=0,(0)
(49mm)
=
Pr
(A0
=
m2 (RETRAIN)) O=O,(0)
We can also induce the average of the advantage over all dataset splits is upper bounded by the maximal advantage taken over all dataset splits:
Pr mi~F (U).
(m²m))
=) Σ
Pr mg (RETRAINN)) (m0())) = 1)
S
sES,
0=0,(0)
SES,
O=0,(0)
Pr (L~Fx((UL.)) (=0+10)
Pr (40(m)) = P Mo>=FA(RETRAINN.. O=0,10)
(11 1)
S
SES,
< max Adv,(A)) sES.
Similarly, construct a second adversary Ag for differentiating Hi and Hg follows:
26

---

In the left world (H1), feed the certified unlearned model to A. In the right world (H2), feed retrained model A.
We create a random oracle (1(1) for A, i.e., we let the adversary A decide on T. We then let A2 outputs the A.
Since A is deciding on T, the advantage of Ag is
Adv AA2)
Pr mi-PM((UL.)) O=0,(1)
(1(44 (m1) 1))
Pr
(m2) 1)
ma O=0.(1)
Similar to the previous calculation for A., the average of the advantage is also upper bounded by the maximal advantage,
Pr (UL. sES, 0=0,(1)
Σ
(m))==1))
Pr PM sES, 0=0,(1)
Σ
(10(m)) = 1)
Sa
Pr minP(Mi.s) 0=0,(1)
(m) =)
Pr m O=0,(1)
(m)) 1)
Sa
SES.
< max Adv, SES..
Given the above calculation, unlcarning method. Then the advantage Adv(A, UL) of .A the unlcarning sample inference game (i.e., differentiating between H3 and H4) against UL is
bound the advantage of A. Firstly, let UL be any certified
Σ
Pr w (UL.s) (=0,(0)
(m)))))11)
Σ sES,
Pr o (ML. O=0,(1)
(1 = =1) 1)
Sa
SESu
On the other hand, the advantage Adv(A, RETRAIN) A against the retraining method RETRAIN can be written as
Σ
Pr
(A0(m))=11 =1
Σ
Pr
(m2))) = =1)
|Sa
marP (RETRAIN..)
m M (RETRAIN.s) O=0,(1)
SES
O=0,(0)
sES.
27

---

which is indeed 0 from Theorem 3.3 triangle inequality.
Combine this with the calculations above, from the reverse
Adv(A, UL) Adv(A, UL) - Adv(A, RETRAIN)
Σ
Pr
(m0m)) =1)
Pr PMRPMMRRTTRINNN sES, 0=0.(1)
E
(40 1)
Sa
(TRTRARR)) (=0,(0)
SESn
Pr ((L,e( #ESa O=0,(0)
(m))) (ml) =1)+ E
Pr ()LLM(UULs)) sES. 0=0,(1)
(A (m1) 1)
Pr mi (UL.s) O=0,(0)
(40 11)
Pr
(40) 1)
Sa
mg (RETRAIN,)) 0=0,(0)
=ES.
Pr
(m))=
Pr (REERAINN, 010,(1)
(40 1)
Sa
my ThrFae (UL.s)
sES,
O=0,(1)
< max Adv, (A1)) + max Adv (A2) sESa
SES.
< 2T,
i.., the advantage of any adversary against any certified unlearning method bounded by 2r.
B.5 Proof of Proposition 3.7
We now prove Proposition 3.7 We repeat the statement for convenience.
Proposition B.S. For any two dataset splits 81,82 E Sa satisfying non-degeneracy assumption, i.e. both PDl= (FI (22) and PDIT, (T1 n T2) do not vanish polynomially faster in (D), then there exists a deterministic and efficient adversary A such that (A, for any unlearning method Ut.. In particular, AdV ) (A, RETrAIN) 1.
Proof. Consider any unlearning method UL, and design a random oracle O., based on the split 8; for 2 and sensitivity distribution Pd (which for simplicity, assume have full support across D), we see that
1 2
Adv (s1,82)) (A,UL)
Pr mmP ((L.s( o= (0)
(40 (m) =)
Pr mm m o=0,,
(m0 1)
Pr (-L.((UL. O=0,,
(A0(m) 1)
Pr m-PPn(UL..s) O=O,,
(m =
Consider hard-coded adversary A which has look-up table T, defined if Tin N T2;
T(x) = O.
if E F2
otherwise,
where 1 denote undefined output. Then, A predicts the bit used by the oracle as follows: We see that Algorithm with a hard-coded look-up table T has several properties:
Since it neglects entirely,
Pr m-Ppx(UL.se (=),,(b)
(A0 =
Pr (A0 = 1) o=0,,(t)
28

---

Algorithm I: Dummy adversary A against random 2-sets evaluation
Data: An unlearned model m, random oracle O
Result: A one bit prediction
b +
while b = 1.10 do
x ~ O
6 (2)
return b
Under the non-degeneracy assumptions, A will terminate in polynomial time in (D]. This
is because the expected terminating time is inversely proportional to Palæ; (Fi n F2) and
PDlt, (7i n 72), hence if these two probabilities does not vanish polynomially faster in (D) (i.c., the non-degeneracy assumption), then it'll terminate in polynomial time in [D].
Whenever A terminates and outputs an answer, will correct, i.e.,
Adv (2) (A, UL) = 1.
Since the above argument works for every Ur., hence even for the retraining method RETRAIN, we will have Adv (A, RETrAIN) 1. Intuitively, such pathological case can happen since there exists some A which interpolates the "correct answer" for few splits. Though adversaries may not have access to specific dataset splits, learning-bass based attacks could still undesirably learn towards this scenario if evaluated only a few splits. Thus, we should penalize hard-coded adversaries in evaluation.
B.6 Discussion on naive strategy offsetting MIA accuracy
In this section, we consider toy example to illustrate the difference between the proposed advantage- based metric and a naive strategy that simply offsets the MIA accuracy for RETRAIN zero
Let us assume there are data points B,, E, F), and we equally split them into the forget set F and the test set T. Running MIA against RETRAIN retain set R independent of the above 6 data points, the MIA predicts the probability that each data point belongs to the forget set is:
retrained model m trained the
MTA(m", A) 0.7, MIA(m", B) 0.4, MTA ,C) 0.3,
MIA(m", D) = 0.1, MIA(m", , E) 0.6, MIA(m" [[][m"FFFF)FF = 0.8.
Assume that the MIA adversary AA chooses the cutoff of predicting a data point belonging to the forget set be 2 0.5, then the prediction will be
A(A) 1, A(B) = 0, A(C) = 0, A(D)= = A(E) 1,
A(F)
where 1 refers the forget set while refers the test set. Since the retrained model will be the same regardless of the split of the forget set and the test set, the MIA prediction will be the same regardless of the split as well.
Assuming that we have two imperfect unlearning algorithms, Ut., and U1.2. For simplicity, we could assume running MIA on the unlearned model m by UL1 will increase the predicted probability on the forget set by 0.1, while that (denoted as m2) by UL2 will increase it by 0.2. For example, if we F {A, B, C} while T =D, E, F}, then the MIA on UL1 will predict the probability MIA(m;, A) 0.8, MIA B) 0.5.
MIA(m1, C) 0.4,
MIA(m,, D) = 0.1. MIA(m1, E) 0.6,
MIA(m;, F) = 0.8,
while the MIA on UL will predict the probability as
MIA(m2. A) 0.9, MIA(m2, B) = 0.6.
MTA C) 0.5,
MTA MTA(m2, D) 0.1, ATA(m2, F) 0.6,
MTA (m,,, F)= 0.8,
Intuitively, U1.2 worse than UI., in terms unlearning quality. In this simplified setup, we claim the following.
29

---

Claim B.6. The advantage calculated by one SWAP test over RETRAIN is always 0, while the advantage calculated by one SWAP test over UL1 and UL₃ are respectively 1/6 and 1/3, all regardless of the exact split of the data points. Hence, the Unlearning Quality for RETRAIN, UI.1 and U1.g are respectively 1, 5/6, and 2/3, faithfully reflecting the unlearning algorithms' performances.
On the other hand, the "offset MIA accuracy" is dependent on the split of the data. Specifically, when we assign {D, E, F3 as the forget set and {A, B, C) as the test set, the MIA accuracies for all three methods are the same, making the "offset MIAs" all equal to 0.5, failing to capture the unlearning quality.
Proof. Given a split s, denote the predicted MIA result as Y: E 13, and the actual membership as Yf lier for E {A, B, ..,,, FJ. Then, consider simple adversary A: after getting the predicted MIA probability, i.e., Pr(Y?" = 1), we update Y, as if Pr( = 1) 2 1/2, and 0 otherwise. Then, the advantage of a particular split s is Pr, (A40. (m) = 1) - Pr,. (40. = 1) = Pr, = These probabilities are essentially an
1 Y = 0) - (Y; = 1 Y = 1) for i E 1,,,,.... average of indicator variables: for example, (Y, - 0) Σ:: y L / Y 0}|, and since we're re considering equal-size splits, ((:: Y = 0}| = (i: Y, = 1 = 6/2 = 3 in our example.
To see how the calculation works out, we note that for a SWAP split (s. each appears in the forget set and the test set exactly once when calculating the SWAP advantage, i.e., Y, 1 and Y = 0 or Y, 0 and Y 1. Furthermore, suppose Y and Y: are the same, e.g., when considering RETRAIN, then the indicators 1 and 1 yyy=1 =1 will be the same and appear in pair (specifically, with opposite sign, one in Adv, and another in Adv,r), and hence cancel each other out. This is why the advantage is for RETRAIN. This pairing of indicators for under splits s and s' happens for imperfect unlearning algorithms, but the indicator might change: Y," can swap from 0 to 1 due to imperfect unlearning. If this happens, i contributes 1/3 to the denominator of the SWAP advantage formula, hence 1/6 in total (divided by 2 at the end). With this observation, we see that for UL.1, only B's prediction will be flipped from 0 to 1, hence Ut.1 's advantage is 1/6 in the SWAP test. The same argument applies for UL2 where both B and C's predictions are flipped, hence the advantage is 2/6 = 1/3.
C Omitted details from Section 4
C.1
Computational resource and complexity
We conduct our experiment on Intel (R) Xeon (R) Gold 6338 CPU @ 20CHH with 4 A40 NVIDIA GPUs. It takes approximately days to reproduce the experiment of standard deviation com- parison between SWAP test and random dataset splitting. It takes approximately 1 day to reproduce the experiment of dataset size and random seeds. Furthermore, takes approximately 4 days to reproduce the experiment of differential private testing.
C.2 Details of training
For target model training without differential privacy (DP) guarantees, we consider using the ResNet- 20 (He et al. 2016) our target model and train it with Stochastic Gradient Descent (SGD) [Ruder] 2016) optimizer with a MultiStepLR learning rate scheduler with milestones [100, 150) and an initial learning rate of 0.1, momentum 0.9, weight decay 10 Moreover, we train the model with 200 epochs, and we empirically observe that this guarantees convergence. For a given dataset split, we average 3 models to approximate the randomness induced in training and unlearning procedures.
For training DP models, we use DP-SGD [Abadi al.. 2016 provide DP guarantees. Specifically, we adopt the OPACUS implementation (Yousetpour et al. 2021] and use ResNet-18 [He et al.) [016] as our target model. The model is trained with the RMSProp optimizer using a learning rate of 0.01 and of 20 epochs. This ensures convergence as we empirically observe that 20 epochs suffice to yield a comparable model accuracy. Considering the dataset size, we use 5 = 10-5 and tune the max gradient norm individually.
30

---

C.3 IC score and MIA score
One of the two metries we choose to compare against is the Interclass Confusion (IC) Test [Goel et al. 2023]. In brief, the IC test "confuses" " selected set of two classes by switching their labels. This is implemented by picking two classes and randomly selecting half of the data from each class for confusion. Then the IC test proceeds to train the corresponding target models on the new datasets and perform unlearning on the selected set using the unlearning algorithm being tested, and finally measures the inter-class error of the unlearned models on the selected set, which we called the memorization score "y. Similar to the advantage, the memorization score is between [O, 1], and the lower, the better since ideally, the unlearned model should have memorization of the confusion. Given this, to compare the IC test with the Unlearning Quality 2, we consider 1 - 7, and refer to this new score the IC score.
On the other hand, the MIA AUC is a popular MIA- metric to measure the performance of the unlearning. It measures how MIA performs by calculating the AUC (Area Under Curve) of MIA on the union of the test set and the forget set. We note that AUC a widely used evaluation metric in terms of classification models since compared to directly measuring the accuracy, AUC tends to measure how well the model can discriminate against each class. Finally, as defined in Section 4 we let the MIA score be 1 MIA AUC to have a fair comparison.
Model Accuracy versus DP Budgets. We also report the classification accuracy of the original model trained with various DP budgets in Table 5 As can be seen, the classification accuracy increases as the e is relaxed to a larger value, showing the inherent trade-off between DP and utility.
For experiments about Unlearning Quality in Table 3 and MIA score in Table 4 the original
models are shared and thus have the same results (Table 5(B). J. We note that measuring the IC scores requires dataset modifications, so the model accuracy in the experiments of IC score (Table (A))
differs slightly from that in experiments of Unlearning Quality and MIA score (Table
Table 5: Model accuracy versus DP Budgets. See Table 3 for more context.
(A) Results for experiments in Table 4(A)
(B) Results for experiments in Tables 3 and 4(B)
50
150
600
00
50
150
600
00
Accuracy
0.442
0.506
0.540
0.639
Accuracy
0.485
0.520
0.571
0.660
Remark C.1. We would like to clarify the performance difference compared to the common literature. which can be attributed to the dataset split. The original dataset is split evenly into the target and shadow datasets for the purpose of implementing MIA. Within the target dataset, further partitioning is performed to create the retain, forget, and test sets. As result, only about 30% of the full dataset remains available for training the model, significantly reducing the effective training data. Note that the data split is necessary for our experiments, so we cannot get significantly more training data.
We experimented with training on the full datasel and applied data augmentation while keeping all other configurations unchanged. With the full dataset, the model achieved an accuracy of 85.3333% After incorporating data augmentation, the accuracy further improved to 91.13% aligning with the past literature. This simple ablation study validates that the performance difference mainly comes from the difference in data size and the omission of data augmentation.
We select a large in our differential privacy experiments due to the significant drop in accuracy observed when is small, which stems from the same dataset size limitation. We include an additional experiment with smaller in the linear setting, as presented at the end of Appendix C.4
C.4 Additional experiments
In this section, we provide additional ablation experiments on our proposed Unlearning Quality metric by considering varying various parameters and settings.
Unlearning Quality Versus Model Architecture. We provide additional experimental results under different model architectures. The experiment is conducted with the CIFAR10 dataset and a = 0.1. The results are shown in Table 6 Interestingly, we observe once again that the relative ranking of different unlcarning methods stays mostly consistent across different architectures.
31

---

Table 6: Unlearning Quality versus different model architectures. The relative ranking of different unlearning methods stays mostly consistent under different architectures.
UL
ResNet44
ResNet56
ResNet110
RETRFINAL
0.497 = 0.040
0.473 = 0.010
0.476 + 0.036
FTHINAL
0.495 = 0.041
0
0.477 = 0.039
FISHER
0.847 0.051
0.832
0.895 = 0.020
NEGGRAD
0.562 + 0.025
0.537 + 0.016
0.520 + 0.042
SALUN
0.716 + 0.008
0.692 = 0.013
0.672 + 0.033
SSD
0.939 = 0.053
0.935 = 0.056
0.968 + 0.017
Unlearning Quality Versus Dataset. We provide additional experiments on vision datasets CIFARI00 [Krizhevsky al. 2009] and MNIST [LeCun [998]. and natural language dataset SST5 Socher et al.] [013]] The experiment is conducted with the ResNet20 model architecture and a 0.1 CIFARTOO and CI For SST5 dataset, the experiment is conducted
the BERT model [Devlin et al.) 2019) and a = 0.1. We note that CIFAR 100 has 100 classes and 50000 training images, SST5 has 5 classes and 11855 training sentences while MNIST has 10 classes and 60000 training images. CIFAR 100 is considered more challenging than CIFARIO, I0, while MNIST is considered easier than CIFARIO. The results are shown in Table 7
In this experiment, besides the consistency we have observed throughout this section, we in addition observe that the Unlearning Quality reflects the level of difficulties of unlearning different datasets. Specifically, the Unlearning Quality of most unlearning methods is higher on MNIST while lower on CIFAR100, in comparison those CIFARIO and SST5.
Table 7: Unlearning Quality versus different datasets. In addition to the consistency of the Unlearning Quality across unlearning methods, the Unlearning Quality scores are higher on MNIST and SST5 while lower on CIFARI00, in comparison to those on CIFARIO, 10, reflecting the level of difficulties on different datasets.
UL
CIFAR100
MNIST
SST5
RETRFINAL
0.464 0.027
0.976 + 0.020
0.404 0.013
FTFINAL
0.462 + 0.028
0.977 = 0.021
0.40+
FISHER
0.606 0.008
0.990 0.002
0.552 0.014
NEGGRAD
0.669 + 0.016
0.980 = 0.017
SALUN
0.697 0.082
0.995 + 0.002
0.456 0.005
SSD
0.923 + 0.058
0.998 + 0.001
0.592 0.011
Validation of Theorem 3.5 With Linear Models We experimented with method from Guo et al. (2020), which an unlearning algorithm for linear models with (e, d--ertiie removal guarantees. We followed the experimental setup in Guo al. 22020). training linear model on part of the MNIST dataset for binary classification task distinguishing class from class
In their algorithm, the parameter controls budget indicating the extent of data that can be unlearned. During the iterative unlcarning, when the accumulated gradient residual norm is beyond the unlearning budget, the unlcarning guarantee is broken and retraining will kick in. So e cannot be made arbitrarily small. Below, we report the Advantage metric for their unlearning algorithm with different (8 is fixed as Ie 4), as well as the Retrain method as reference:
Table 8: Change of advantage in linear models with respect to decreasing e.
0.8
0.6
0.4
0.3
RETRAIN
Advantage 0.010
0.009
0.005
0.003
0.002
We can see that the Advantage monotonically decreases as 6 decreases, which aligns with our Theorem 3.5)
32


Reviews:
[{"review_id": "pnggpwtpri", "reviewer": "Reviewer_FFru", "summary": "This work introduces a notion of unlearning evaluation defined via a distinguishing game dubbed the “unlearning sample inference game.” Informally, this game asks an adversary to distinguish unlearned data from data never used in training at all, given access to the model. The distinguishing game is presented in the style of cryptographic security games, where the adversary is assumed to be computationally bounded and the quality of unlearning is described as a function of the adversary’s distinguishing advantage. Notably, the “unlearning” method of retraining a model on a dataset from which all unlearned data has been removed guarantees that any adversary will have no advantage at all in the distinguishing game. A test for evaluating the advantage of the adversary without computing it precisely is proposed and empirically evaluated on the CIFAR10 dataset and ResNet model output by LR. Retraining, Fisher forgetting, final layer fine-tuning, final layer retraining, negative gradient descent, saliency unlearning, selective synaptic dampening, and no unlearning are evaluated.", "questions": "See comments on strength and weaknesses", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The distinguishing framework for unlearning evaluation is very natural and I believe captures a very reasonable notion of unlearning. I have some questions about the usefulness of this definition compared to other potential definitions, however. It would be nice to better understand how this definition compares to one where the adversary is computationally unbounded. There have been challenges in separating computational differential privacy from standard (statistical) differential privacy, for instance, and so I’m not sure I appreciate why restricting to computationally bounded adversaries is the right thing to do here, and how this changes the threat model. Some discussion of this restriction would help with interpreting the definition. \n\nThere is significant overlap between this paper and another recent paper [1] up on arxiv, so I’d recommend citing this work as well. I believe this went up after the NeurIPS abstract deadline, however, so I don’t think there’s an obligation to have compared to the work already.\n\n[1] Mirror Mirror on the Wall, Have I Forgotten it All? A New Framework for Evaluating Machine Unlearning. Brennon Brimhall, Philip Mathew, Neil Fendley, Yinzhi Cao, Matthew Green", "was_revised": true, "final_justification": "My appraisal of the paper is positive and I believe the comparison to recent related work will improve the paper. I am maintaining my score.", "rebuttal": "We sincerely thank Reviewer FFru for taking the time to review our paper and for their constructive feedback and recognition of our proposed evaluation framework!\n> On the use of computationally bounded adversaries\n\nWe would like to clarify that our theoretical framework **does not require** the adversary to be computationally bounded. In fact, **Theorem 3.5 holds even for computationally unbounded adversaries**, meaning our Unlearning Quality metric can naturally generalize to a “statistical” notion without needing to assume computational limitations (see main paper, Theorem 3.5 and Appendix B.3). Thus, the core theoretical foundation of our framework remains valid in both settings.\nThat said, we explicitly focus on **computationally bounded adversaries for practical purposes**. As with differential privacy, empirical evaluation and implementation inherently require working with efficient algorithms. Moreover, existing MIA techniques are themselves limited in computational power, and our approximation methods (e.g., the SWAP test) are grounded in this practical setting. In this way, **the use of weak or computationally bounded adversaries serves as a realistic approximation for empirical evaluation**—analogous to the use of efficient distinguishers in applied cryptography.\nWe have updated the discussion in the main text to better articulate the above tradeoff between theoretical generality and practical feasibility. We thank the reviewer again for prompting us to clarify this important point.\n\n> \"There is significant overlap between this paper and another recent paper [1] up on arXiv...\"\n\nWe will cite it in the updated version of our paper. As noted, the timing suggests the work appeared after the NeurIPS abstract deadline, but we agree it is important to acknowledge concurrent developments and position our contributions accordingly."}, {"review_id": "vHzRo52s22", "reviewer": "Reviewer_K1Yg", "summary": "This paper proposes a novel, theoretically grounded framework for evaluating machine unlearning algorithms using a game-theoretic approach inspired by cryptographic games. The authors introduce the Unlearning Sample Inference Game, which models the interaction between an unlearning algorithm and a membership inference attack (MIA) adversary. They define a new metric, Unlearning Quality (Q), based on the adversary’s advantage in distinguishing forgotten from unseen data points. The metric satisfies desirable properties such as zero advantage for retraining (i.e., perfect unlearning) and alignment with certified removal guarantees.\n\nTo make the framework practical, the authors develop an efficient approximation called the SWAP test, which preserves theoretical guarantees while reducing computational cost. Empirical results on CIFAR-10 demonstrate that the proposed metric is more robust and consistent than existing attack-based evaluation metrics, such as MIA AUC and inter-class confusion, especially under varying differential privacy budgets.", "questions": "Have the authors tested the metric’s robustness against white-box MIAs, like gradient-based or loss trajectory attacks? Can the proposed framework incorporate more recent adaptive MIAs (e.g., Carlini’s attacks)?\n\nDo you believe the metric would be stable across different architectures (e.g., transformers, graph models)? Could optimization landscapes affect the adversary’s success, and hence the unlearning score? Another thing is that do you think results would generalize to imbalanced datasets or different modalities? While a more empirical question, would love to hear the authors' thoughts on this.\n\n\nHow sensitive is the unlearning quality metric to non-uniform sensitivity distributions? What happens when the forget and test sets differ in class distribution or sample difficulty?", "limitations": "The evaluation framework assumes that the adversary only queries the oracle once, i.e., a “weak adversary,” yet most real-world attackers may use multiple adaptive queries or exploit correlations.\n\nThe SWAP test depends on careful dataset splits with equal-sized forget/test sets and uniform sensitivity distribution.\n\nOnly black-box or weak MIAs are used, no white-box or shadow-model-free MIAs.", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\n1. The paper introduces the Unlearning Sample Inference Game, inspired by cryptographic games, to model the interaction between an unlearning algorithm and an MIA (Membership Inference Attack) adversary. The paper proposes the concept of \"advantage\" to quantify privacy risk and unlearning efficacy, providing theoretical grounding.\n\n2. The theoretical guarantees provided are strong.\nThe framework satisfies desirable properties:\n\n- Zero Grounding: The retraining baseline achieves 0 adversarial advantage (i.e., Q = 1).\n\n- Certified Removal Guarantee: Strong connection between the metric and differential privacy–inspired certified removal.\n\n- Handles multiple MIA adversaries, addressing inconsistency in existing MIA-based evaluations.\n\n\n3. The SWAP test offers an efficient way to approximate the proposed metric while maintaining symmetry and grounding properties. Empirically shown to be more stable than naive split-based MIA evaluations.\n\n4. The paper has comprehensive experiments. The authors evaluate popular unlearning methods (e.g., Fisher Forgetting, SSD, SALUN) on CIFAR-10 with ResNet. They also benchmark performance across varying DP budgets, showing the proposed metric Q aligns well with theoretical expectations.\n\n5. Robustness and consistency are a strength as they compared existing metrics (MIA AUC and Interclass Confusion), \nThe proposed Unlearning Quality metric maintains monotonic behavior with increasing privacy budget. It also offers a more consistent ranking of unlearning methods across different conditions.\n\n6. The authors also do a thorough review of prior work in attack-based evaluation (e.g., MIA metrics) and theory-based and retraining-based metrics. They effectively position this work as addressing the pitfalls of all three categories using a theoretically justified, attack-based approach.\n\n**Weaknesses / Limitations:**\n1. Assumption of Weak Adversaries: Practical evaluation is restricted to weak MIAs (interact only once with the oracle), limiting full assessment of sophisticated attacks.\nWhile justified by current MIA limitations, this could underestimate real-world risks.\n\n2. No Real-World Dataset in that experiments are confined to CIFAR-10, a toy dataset. Lack of tests on large-scale or sensitive datasets (e.g., medical records, text corpora) limits external validity.\n\n3. There seems to be some reliance on certified removal for bounds. Certified removal parameters (ε, δ) are difficult to compute or guarantee in practice, especially for non-convex or large models.\n\n4. Although the SWAP test reduces cost, full computation of the proposed metric can still be computationally expensive in real-world pipelines.\n\n5. While the authors critique other MIA-based methods for giving false confidence, the possibility that their own metric may also be over-optimistic under strong attacks is not discussed in depth.", "was_revised": true, "final_justification": "The authors provide detailed answers  to address my questions as well as provide additional experiments for the adversaries' usecase I highlighted. I am happy with the discussion and high quality attention to detail to address my review.", "rebuttal": "We sincerely thank Reviewer K1Yg for taking the time to review our paper and for their constructive feedback and strong recognition of our proposed evaluation framework!\n\n> Assumption of Weak Adversaries. Practical evaluation is restricted to weak MIAs (interact only once with the oracle), limiting full assessment of sophisticated attacks.\n\nWe would like to clarify that while our empirical evaluation leverages weak (single-interaction) MIAs due to the limitations of current state-of-the-art adversaries, our framework is not restricted to weak adversaries in theory. As detailed in Appendix B.2, our cryptographic game formulation accommodates arbitrary adversaries, including those with multi-sample or oracle access (e.g., strong, white-box, or adaptive MIAs).\n\nIndeed, we acknowledge that stronger adversaries may yield lower Unlearning Quality, and thus our reported values may be over-optimistic. However, in practice, users are encouraged to instantiate the strongest MIA feasible in their deployment scenario to obtain a meaningful approximation of worst-case privacy risk.\n\nWe will explicitly include this discussion in the revised version to clarify that our metric’s rigor scales with the strength of the employed adversary.\n\n> No Real-World Dataset: Datasets in the experiments are confined to CIFAR-10, a toy dataset.\n\nWe want to clarify that in the appendix, we have already included additional datasets (CIFAR-100 and MNIST) to demonstrate robustness across varying dataset complexities.\n\nWe agree that incorporating a non-vision modality is important. As such, we are in the process of extending our experiments to include a text corpus (SST5) and pretrained models such as BERT.  The results is shown below:\n\n| Method    | 50           | 150          | 600          | ∞             |\n|-----------|--------------|--------------|--------------|---------------|\n| FTFinal   | 0.986 ± 0.001 | 0.960 ± 0.005 | 0.945 ± 0.008 | 0.425 ± 0.017 |\n| RetrFinal | 0.986 ± 0.001 | 0.967 ± 0.007 | 0.944 ± 0.007 | 0.422 ± 0.020 |\n| SalUN     | 0.991 ± 0.001 | 0.984 ± 0.001 | 0.966 ± 0.008 | 0.525 ± 0.018 |\n| Neggrad   | 0.991 ± 0.004 | 0.961 ± 0.005 | 0.932 ± 0.006 | 0.388 ± 0.013 |\n| SSD       | 0.992 ± 0.004 | 0.991 ± 0.005 | 0.965 ± 0.006 | 0.592 ± 0.011 |\n| Fisher    | 0.990 ± 0.001 | 0.988 ± 0.002 | 0.964 ± 0.006 | 0.564 ± 0.010 |\n| None      | 0.985 ± 0.001 | 0.951 ± 0.004 | 0.929 ± 0.007 | 0.370 ± 0.021 |\n| Retrain   | 0.999 ± 0.001 | 0.995 ± 0.000 | 0.993 ± 0.002 | 0.953 ± 0.008 |\n\n\nWe can see that the results also exhibit similar trends as in the vision domain: the proposed metric distinguishes between unlearning methods more clearly as the privacy budget becomes weaker. Moreover, Retrain consistently achieves near-perfect Unlearning Quality, while approximate methods show meaningful variation based on their aggressiveness and design.\n\n> Certified removal parameters are difficult to compute in practice, especially for non-convex or large models.\n\nIt is worth noting that we use certified removal only for the purpose of theoretical analysis, connecting our metric to well-established definitions from the literature. This connection provides formal grounding (see Theorem 3.5), but is not required for implementation or evaluation, since the definition of our metric does not rely on certified removal.\n\n> Full computation of the proposed metric can still be computationally expensive \n\nWe highlight that our metric has comparable costs to existing MIA evaluation pipelines. Concretely, the cost of the SWAP test is approximately 2× that of a standard MIA pipeline—primarily due to evaluating both swapped splits. Therefore, our methods can be applied to scenarios where existing MIA-based evaluations can be used.\n\n> The possibility that the metric may also be over-optimistic under strong attacks is not discussed.\n\nWe agree that our current experimental results may be over-optimistic due to the limitations of available MIAs. We will add a discussion to explicitly acknowledge that Unlearning Quality should be interpreted relative to the strength of the MIA used in practice. In other words, one can always enforce the strongest MIA to date relevant to their application to obtain a practically meaningful measure of Unlearning Quality.\n\nHowever, we also note that our metric is fundamentally different from existing MIA-performance-based scores: it enjoys zero-grounding under retraining, consistency under differential privacy, and is provably upper-bounded by theoretical guarantees (e.g., Theorem 3.5). In particular, the calibration properties of the proposed metric cannot be achieved by merely strengthening the performance of MIAs.\n\n> White-box MIAs. Will white-box MIAs hurt the robustness of the metric?\n\nWhile our empirical evaluation used black-box MIAs for efficiency, we stress that our framework accommodates both black-box and white-box adversaries. This is discussed in Appendix B.2. We have added classic white-box attacks as in [1,2] on SST5 dataset with BERT. The results is shown below:\n\n| Method | 50 | 150 | 600 | ∞ | \n|-----------|--------------|--------------|--------------|---------------| \n| FTFinal | 0.984 ± 0.001 | 0.960 ± 0.005 | 0.943 ± 0.007 | 0.404 ± 0.013 | \n| RetrFinal | 0.986 ± 0.001 | 0.965 ± 0.006 | 0.944 ± 0.007 | 0.405 ± 0.012 |\n | SalUN | 0.986 ± 0.002 | 0.980 ± 0.001 | 0.964 ± 0.011 | 0.456 ± 0.015 |\n | Neggrad | 0.987 ± 0.005 | 0.957 ± 0.007 | 0.932 ± 0.006 | 0.376 ± 0.017 | \n| SSD | 0.989 ± 0.001 | 0.988 ± 0.006 | 0.965 ± 0.006 | 0.592 ± 0.011 | \n| Fisher | 0.984 ± 0.002 | 0.982 ± 0.001 | 0.960 ± 0.007 | 0.552 ± 0.014 |\n | None | 0.983 ± 0.001 | 0.930 ± 0.002 | 0.910 ± 0.004 | 0.368 ± 0.015 | \n| Retrain | 0.997 ± 0.001 | 0.995 ± 0.003 | 0.991 ± 0.003 | 0.948 ± 0.010 | \n\nWe can see that the results remain consistent with those from black-box attacks—the Unlearning Quality is low for the baseline (None), high for exact unlearning (Retrain), and exhibits meaningful variation across approximate methods. This demonstrates that our metric retains its sensitivity and calibration under stronger, white-box adversaries, and further supports the practical robustness and generality of our evaluation framework.\n\nWe will incorporate these results and discussion into the revised version to emphasize that our framework is not limited by the adversary access mode, and can support future advances in attack methodology.\n\n> Generalization across architectures, modalities, or imbalanced datasets.\n\nIt’s worth noting that our framework is model-agnostic and modality-agnostic by design. The cryptographic game only assumes an unlearned model and a forget/test split—it is the MIA’s task to adapt its attack strategy to the data distribution and architecture. Nevertheless, we have added the results of BERT finetuned on SST5. Please refer to the “No real-world dataset” section for experimental results. \n\n> Non-uniform sensitivity distributions\n\nWe have provided a high-level discussion in Appendix B.2, where we define the sensitivity distribution \\$\\mathbb{P}_{\\mathcal{D}}\\$ and allow arbitrary biases toward specific samples. This enables the metric to reflect heightened privacy risk from more sensitive data points, addressing more difficult samples, or accommodating class imbalances.\n\nOur design ensures that such distributions are respected during evaluation via the oracle sampling. As a result, the metric captures the influence of both distributional skew and sample difficulty, offering a more realistic view of privacy risk than uniform sampling alone.\n\n[1] Nasr, Milad, Reza Shokri, and Amir Houmansadr. \"Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.\" 2019 IEEE symposium on security and privacy (SP). IEEE, 2019.\n\n[2] Carlini, Nicholas, et al. \"Membership inference attacks from first principles.\" 2022 IEEE symposium on security and privacy (SP). IEEE, 2022."}, {"review_id": "KIo6eJfVgr", "reviewer": "Reviewer_yVLK", "summary": "This paper proposes a new metric to evaluate the effectiveness of machine unlearning. Machine unlearning is intended to remove the trace of sensitive training data from a model. Existing metrics for unlearning sometimes have counter-intuitive outcome, e.g., assigning low score to models retrained from scratch without the sensitive data. This paper provides a theoretical framework as well as computationally tractable heuristics that instantiate the framework. Empirical evidence shows that the new score is consistent with the expected outcome of DP-guaranteed models across different privacy parameters.", "questions": "As the authors mention in the work, one shortcoming of MIA based evaluation is that score may be low for model retrained without the data to be removed. However, is this behavior expected if there are duplicates in the data set? For example, two individuals may have identical data inputs. Will MIA mistake the remained duplicate as the entry to be removed? How does new framework overcome this problem?", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "This paper is very well written. The problem setting is clearly motivated. The theoretical framework is concisely and formally defined. The heuristics are sound. The experiment designs are also smart: the authors use different levels of DP to overcome the lack of ground truth effectiveness of unlearning. Overall, I believe this paper is of high quality. \n\nThere is no apparent weakness in the work. I do have questions about the expected behavior of unlearning score in some corner cases. I'd appreciate if the authors could clear my doubt.", "was_revised": true, "final_justification": "The authors have addressed my questions. Therefore, I'm maintaining my positive recommendation for this paper.", "rebuttal": "We sincerely thank Reviewer  yVLK for taking the time to review our paper and for their constructive feedback and strong recognition of our proposed evaluation framework!\n\n> Duplicates in datasets.  How does the new framework overcome the case when  two individuals may have identical data inputs. Will MIA mistake the remaining duplicate as the entry to be removed?\n\nThis is an intriguing question, but we would argue that, for the purpose of **evaluating** unlearning algorithms, the scenario where the retain set contains duplicate entries of the forget set is a **pathological** evaluation setting. Specifically, the ground truth for whether a model has “forgotten” the sample from the forget set becomes ambiguous. \n\nThis pathological setting is analogous to evaluating classification accuracy using mislabeled test samples. When the test samples are mislabeled, it is unclear whether one should expect a better classification algorithm should have higher or lower test accuracy on this corrupted test set. Similarly, it is unclear whether a better unlearning algorithm should have higher or lower Unlearning Quality in the pathological setting where the retain set and forget set share duplicates."}, {"review_id": "gTKk5qXp6a", "reviewer": "Reviewer_5sfE", "summary": "This paper introduces a cryptographic game framework based on membership inference attack to evaluate machine unlearning algorithms. It aims to address the unreliability of existing MIA-based evaluation metrics. And the paper proposes a practical tool, the SWAP test, to approximate the proposed evaluation metric. The empirical findings reveal the effectiveness the metric.", "questions": "1. Impact of Varying Sensitivity Distribution ($P_D$): The paper defaults to a uniform sensitivity distribution $P_D=U(D)$. What are the theoretical and empirical implications if $P_D$ is non-uniform, reflecting varying data sensitivities or attack focuses? How would this impact the calculated \"advantage\" and the practical utility of the Unlearning Quality metric?\n2. Distinguishing Unlearning Performance under Low Noise/ High Privacy Budgets: As mentioned in weakness 3, in Table 1, for low noise/high privacy budgets, even when the performance differences among the various unlearning algorithms become more pronounced, the Unlearning Quality for various unlearning methods is consistently high, and the differences between different algorithms appear negligible. How then can one compare the advantages and disadvantages of different algorithms?\n3. Cross-Dataset/Model Performance Variations and Metric Design: In Appendix C.4, the paper attributes significant performance variations across different datasets and model architectures to models’ learning capabilities. Do other existing MIA-based evaluation methods (e.g., MIA AUC, IC Test) exhibit similar magnitudes of performance differences across these diverse settings, or is this variability particularly pronounced with the proposed metric? If the latter, could this variability be influenced by specific aspects of the evaluation framework itself?\n4. Theoretical Bounds for SWAP Test Approximation Error: The paper introduces the SWAP test as a practical approximation method. Are there any theoretical bounds or guarantees on the approximation error of the SWAP test relative to the exact \"advantage\" metric? Could the authors provide more quantitative analysis regarding the precision of this approximation? \n5. Robustness to Advanced MIA Adversaries: If MIA attacks become more powerful, for example, by considering relationships between data and using data covariance for attacks, how could the framework be extended or adapted to incorporate such advanced attack capabilities to ensure its long-term relevance and reliability?", "limitations": "1. Assumption of Uniform Data Distribution: The framework relies on a uniform data splitting strategy for the forget and test sets. Deviations from this i.i.d. setup could complicate theoretical guarantees and empirical analysis.\n2. Reliance on Weak Adversaries: The current empirical evaluation is predicated on state-of-the-art MIA adversaries being \"weak\" and making independent decisions per data point, not exploiting data covariance. This might limit the framework's ability to reflect true privacy risks against more sophisticated future attacks.\n3. Limited Discernment in High Privacy/Low Noise Regimes: The metric struggles to show significant differentiation between unlearning algorithms when differential privacy is applied, even with larger ϵ values, as all methods achieve very high and similar Unlearning Quality scores\n4. Lack of Quantified Approximation Error for SWAP Test: While the SWAP test is proposed as a practical approximation, the paper does not provide theoretical bounds or quantitative analysis of its approximation error for the general \"advantage\" metric.\n5. Variability in Metric Performance Across Diverse Settings: The evaluation metric shows significant variability in performance across different datasets and model architectures. While partly attributed to inherent task difficulty, a deeper discussion on whether this variability is amplified by the evaluation framework itself compared to other metrics is needed.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. Interesting Application of Cryptographic Games: The paper frames the evaluation of unlearning algorithms within the context of cryptographic games, borrowing the concept of \"advantage\" from cryptography. This approach aims to establish a more reliable and theoretically grounded evaluation metric, which is an interesting knowledge transfer.\n2. Practical Feasibility with SWAP Test: Recognizing the computational challenges of exact calculation, the introduction of the SWAP test provides a practical approximation method. \n3. Clear Presentation: The paper is logically structured, and the concepts are presented clearly. Weaknesses:\n1. Domain Transfer: While the application of cryptographic games to unlearning evaluation is interesting, the core methodological contribution appears to be primarily a transfer and adaptation of existing cryptographic concepts rather than the development of fundamentally new algorithmic techniques for unlearning itself. This could be perceived as more of a modeling contribution than a deep algorithmic innovation for the unlearning process\n2. Reliance on \"Weak Adversaries\": The paper acknowledges that current state-of-the-art MIA adversaries are \"weak\". If more sophisticated MIAs emerge that can leverage the relationship of data points, the effectiveness of the current evaluation framework in truly reflecting privacy risks might be compromised. The paper states that if weak adversaries improve, their metric would also benefit, but this doesn't alleviate the current limitation.\n3. Difficulty in Distinguishing Unlearning Performance under Low Noise/High Privacy Budgets: The paper's experimental results (Table 1) show that when differential privacy is applied (even with a relatively large ϵ, representing a weaker privacy guarantee), the Unlearning Quality for different unlearning methods, including \"NONE\" (no unlearning) and \"REMAIN\" (the gold-standard), can be high and quite similar. This implies that the metric might struggle to discern fine-grained differences in unlearning quality with low noise or stringent privacy budgets. However, as the ϵ parameter increases (indicating less stringent privacy), the performance differences among the various unlearning algorithms become more pronounced.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank Reviewer 5sfE for taking the time to review our paper and for their constructive feedback and  valuable suggestions of our proposed evaluation framework!:\n> Domain Transfer. This could be perceived as more of a modeling contribution than a deep algorithmic innovation for the unlearning process…\n\nWe would like to clarify that our work is intended as an **evaluation framework**, instead of a new unlearning algorithm. The lack of rigorous, reliable metrics for assessing unlearning has been a major obstacle in the field, as also highlighted by the recent NeurIPS unlearning competition. Our cryptographic-game-inspired formulation fills this critical gap by providing a theoretically grounded, practically implementable, and empirically robust evaluation metric for unlearning performance. While we draw upon cryptographic principles, we introduce novel modeling and approximation techniques (e.g., the SWAP test and its instantiation under weak MIAs) tailored for the unlearning setting.\n\n> Reliance on Weak Adversaries. If more sophisticated MIAs emerge that can leverage the relationship of data points, the effectiveness and robustness of the current evaluation framework in truly reflecting privacy risks might be compromised…\n\nWe would like to clarify a potential misinterpretation: the reviewer suggested that “If more sophisticated MIAs emerge …, the effectiveness of the current evaluation framework in truly reflecting privacy risks might be compromised”. However, our evaluation framework can in fact be further strengthened when new and stronger MIAs become available. \nAs we clarify in Section 3.5 and Appendix B.2, our theoretical framework is fully general—it supports strong adversaries that interact multiple times with the oracle or reason over multiple data points jointly (e.g., with covariance structure). The Unlearning Quality metric is defined as a worst-case guarantee over all efficient adversaries, which naturally includes both weak and strong ones.\nIn practice, we adopt weak MIAs in our empirical evaluation because all current state-of-the-art MIAs are weak under our definition—they act independently on each data point. When stronger MIAs become available, our framework can seamlessly accommodate them. In fact, stronger adversaries would only lower the empirical Unlearning Quality, yielding more conservative (and more accurate) estimates of privacy risk. Thus, the flexibility of our metric is a strength, not a limitation.\n\nNevertheless, we included white-box attacks [2,3] on SST5 dataset with BERT to show that our metric is robust to stronger adversaries. The results are shown below: \n| Method    | 50           | 150          | 600          | ∞             |\n|-----------|--------------|--------------|--------------|---------------|\n| FTFinal   | 0.984 ± 0.001 | 0.960 ± 0.005 | 0.943 ± 0.007 | 0.404 ± 0.013 |\n| RetrFinal | 0.986 ± 0.001 | 0.965 ± 0.006 | 0.944 ± 0.007 | 0.405 ± 0.012 |\n| SalUN     | 0.986 ± 0.002 | 0.980 ± 0.001 | 0.964 ± 0.011 | 0.456 ± 0.015 |\n| Neggrad   | 0.987 ± 0.005 | 0.957 ± 0.007 | 0.932 ± 0.006 | 0.376 ± 0.017 |\n| SSD       | 0.989 ± 0.001 | 0.988 ± 0.006 | 0.965 ± 0.006 | 0.592 ± 0.011 |\n| Fisher    | 0.984 ± 0.002 | 0.982 ± 0.001 | 0.960 ± 0.007 | 0.552 ± 0.014 |\n| None      | 0.983 ± 0.001 | 0.930 ± 0.002 | 0.910 ± 0.004 | 0.368 ± 0.015 |\n| Retrain   | 0.997 ± 0.001 | 0.995 ± 0.003 | 0.991 ± 0.003 | 0.948 ± 0.010 |\n\nWe can see that the results remain consistent with those from black-box attacks—the Unlearning Quality is low for the baseline (None), high for exact unlearning (Retrain), and exhibits meaningful variation across approximate methods. This demonstrates that our metric retains its sensitivity and calibration under stronger, white-box adversaries, and further supports the practical robustness and generality of our evaluation framework.\nWe will incorporate these results and discussion into the revised version to emphasize that our framework is not limited by the adversary access mode, and can support future advances in attack methodology.\n\n> Difficulty in distinguishing the performance of unlearning algorithms when the model is very private (ε is small) .\n\nWe clarify that the lack of significant differentiation between algorithms when ε is small is not a shortcoming, but rather an expected and desirable outcome. When a model is trained with strong differential privacy (small ε), the influence of individual samples is already well-masked, making unlearning inherently easier. In such scenarios, all unlearning methods—whether approximate or exact—perform similarly well, and our metric reflects this reality.\n\nIt’s worth noting that this behavior in fact validates and justifies the reliability of our metric: it gives high scores to all methods only when the model is already highly private and thus has little need for aggressive unlearning. As ε increases (weaker DP), we see the expected divergence between algorithms, demonstrating the metric’s sensitivity in regimes where unlearning efficacy truly matters.\n\n> Uniform sensitivity distribution. The framework relies on a uniform data splitting strategy for the forget and test sets. Deviations from this i.i.d. setup could complicate theoretical guarantees and empirical analysis.\n\nWe refer to Appendix B.2, where we discuss the role of the sensitivity distribution ​ in shaping oracle responses, as well as the implication of **uniform splitting**. In particular, we highlight that sensitivity distribution models the *privacy risks*, informing the Unlearning Quality to focus/omit particular points with higher probability, while uniform splitting is akin to the standard assumption in the unlearning literature and aligns with the i.i.d. setup of most unlearning setups. \n\nA combination of these two makes our framework flexible, as our framework and theory support arbitrary non-uniform sensitivity distributions to model data sensitivity or adversarial focus. Our experiments consider a uniform sensitivity distribution for simplicity, and exploring this in practice is an exciting direction we plan to pursue in future work, but it is beyond the scope of the current submission.\n\n> Cross-dataset and architecture variability. Do other existing MIA-based evaluation methods (e.g., MIA AUC, IC Test) exhibit similar magnitudes of performance differences across these diverse settings, or is this variability particularly pronounced with the proposed metric?\n\nWe would like to point out that the variability observed across datasets and architectures (Appendix C.4) stems primarily from differences in task difficulty and model learning capacity. For example, CIFAR-100 is a harder task than MNIST, and some unlearning methods degrade more noticeably under harder conditions. This variability is expected and also shown in previous literature(e.g., see  Figure 2, Table 5-7 in IC test [1]). \n\n> Theoretical approximation error bounds. Are there any theoretical bounds or guarantees on the approximation error of the SWAP test relative to the exact \"advantage\" metric? \n\nWhile we do not currently provide tight theoretical bounds on the approximation error of the SWAP test, we would like to highlight several facts:\n\n1. The SWAP test is an unbiased estimator of the true advantage, even under arbitrary sensitivity distributions. This is briefly discussed in Appendix B. Hence, under mild assumptions, it can be shown that the expected error between the average of SWAP estimators and the full Unlearning Quality decreases exponentially fast. \n2. It inherits the zero-grounding property (Proposition 3.6), which is a key theoretical feature of the exact metric.\nEmpirically, we observe that the SWAP test preserves the monotonicity with respect to ε and ranking consistency across datasets and methods (Table 1 and C.4).\nTogether, these properties suggest that the SWAP test is both principled and reliable, even without explicit error bounds. Formal analysis of its variance and concentration is a promising future direction.\n\n[1] Goel, Shashwat, et al. \"Towards adversarial evaluations for inexact machine unlearning.\" arXiv preprint arXiv:2201.06640(2022).\n\n[2] Nasr, Milad, Reza Shokri, and Amir Houmansadr. \"Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning.\" 2019 IEEE symposium on security and privacy (SP). IEEE, 2019.\n\n[3] Carlini, Nicholas, et al. \"Membership inference attacks from first principles.\" 2022 IEEE symposium on security and privacy (SP). IEEE, 2022."}]

Author rebuttal:

Meta-review: This paper introduces a theoretically grounded framework for evaluating machine unlearning through a cryptography-inspired game-theoretic formulation called the Unlearning Sample Inference Game. In this game, an adversary attempts to distinguish between data that has been unlearned and data never used in training, with the quality of unlearning defined by the adversary’s distinguishing advantage. The authors propose a new metric, Unlearning Quality (Q), which satisfies desirable properties such as assigning zero advantage to retraining (i.e., perfect unlearning) and aligning with certified removal guarantees. 

To make evaluation practical, they developed the SWAP test, an efficient approximation that retains theoretical guarantees while reducing computational overhead. Empirical results on CIFAR-10 with ResNet show that this metric is robust and consistent across a range of unlearning methods—including retraining, Fisher forgetting, fine-tuning, and gradient-based approaches—and avoids counterintuitive outcomes observed with existing metrics such as MIA AUC or inter-class confusion, particularly under different differential privacy budgets.

The reviewers agreed on the paper’s technical contributions, noting the theoretically sound results, practical and efficient approximations, and extensive empirical validations.
Decision: Accept (poster)