System-Aware Unlearning Algorithms: Use Lesser, Forget Faster
Authors: Linda Lu
Ayush Sekhari
Karthik Sridharan
Venue: ICML 2025 poster (2025)
Keywords: machine unlearning
sample compression
selective sampling
learning theory
Primary area: theory->learning_theory
TL;DR: We present a new definition of unlearning, system aware unlearning, and we demonstrate that we can design more efficient unlearning algorithms under this definition.

Abstract: Machine unlearning addresses the problem of updating a machine learning model/system trained on a dataset $S$ so that the influence of a set of deletion requests $U \subseteq S$ on the unlearned model is minimized. The gold standard definition of unlearning demands that the updated model, after deletion, be nearly identical to the model obtained by retraining. This definition is designed for a worst-case attacker (one who can recover not only the unlearned model but also the remaining data samples, i.e., $S \setminus U$). Such a stringent definition has made developing efficient unlearning algorithms challenging. However, such strong attackers are also unrealistic. In this work, we propose a new definition, *system-aware unlearning*, which aims to provide unlearning guarantees against an attacker that can at best only gain access to the data stored in the system for learning/unlearning requests and not all of $S\setminus U$.  With this new definition, we use the simple intuition that if a system can store less to make its learning/unlearning updates, it can be more secure and update more efficiently against a system-aware attacker. Towards that end, we present an exact system-aware unlearning algorithm for linear classification using a selective sampling-based approach, and we generalize the method for classification with general function classes. We theoretically analyze the tradeoffs between deletion capacity, accuracy, memory, and computation time.

Today's 's large-scale Machine Learning (ML) models are often trained extensive datasets containing sensitive or System-Aware Unlearning Algorithms:
Use Lesser, Forget Faster
Linda Lu
Ayush Sekhari
Karthik Sridharan
Abstract
personal information. Thus, concerns surrounding privacy and data protection have become increasingly prominent (Yao et al., 2024). These models, due to their high capac- ity to memorize patterns in the training data, may inadver- tently retain and expose information about individual data points (Carlini et al., 2021). This presents significant chal- lenges in the context of privacy regulations such as the Eu- ropean Union's 's General Data Protection Regulation (2016) (GDPR), California Consumer Privacy Act (201 8) (CCPA), and Canada's 's proposed Consumer Privacy Protection Act, all of which emphasize the "right to be forgotten". As a result, there is a growing need for methods that enable the selective removal of specific training data from models that have already been trained, a process commonly referred to machine unlearning (Cao & Yang, 2015). Beyond pri- vacy, unlearning can be used to combat undesirable model behavior after deployment, such as copyright violations (Dou et al., 2024).
Machine unlearning addresses the problem of up- dating machine learning model/system trained on a dataset 5 so that the influence of a set of deletion requests U S S on the unlearned model is minimized. The gold standard definition of un- learning demands that the updated model, after deletion, be nearly identical to the model obtained by retraining. This definition is designed for worst-case attacker (one who can recover not only the unlearned model but also the remaining data samples, i.e., 5 > U). Such stringent definition has made developing efficient unlearning algo- rithms challenging. However, such strong attack- ers also unrealistic. In this work, we propose new definition, system-aware unlearning, which aims to provide unlearning guarantees against an attacker that can at best only gain access to the data stored in the system for learning/unlearning requests and not all of S U. With this new definition, we use the simple intuition that if sys- tem can store less make its learning/umlcaming updates, it can be more secure and update more efficiently against system-aware attacker. To- wards that end, we present an exact system- aware unlearning algorithm for linear classification us- ing a selective sampling-bers based approach, and we generalize the method for classification with gen- eral function classes. We theoretically analyze the tradeoffs between deletion capacity, accuracy, memory, and computation time.
Machine unlcarning addresses the need to remove data from a model's s knowledge base without the need to retrain the model from scratch each time there deletion request, since this can be computationally expensive and often im- practical for large-scale systems. The overarching objective is to ensure that, post-unlearning, model "acts" as if the removed data were never part of the training process. Tra- ditionally, this has been defined through notions of exact (or approximate) unlearning, wherein the model's hypothe- sis after unlearning should be identical (or probabilistically equivalent) to the model obtained by retraining from seratch the entire dataset after removing only the deleted points (Sekhari et al., 2021; Ghazi et al., 2023; Guo et al., 2019). While such definitions offer rigorous guarantees even in the most pessimistic scenarios, they often impose stringent requirements, limiting the practical applicability of machine unlearning. This is evidenced by the lack of efficient certi- fied exact approximate unlearning algorithms beyond the simple case of convex loss functions. Furthermore, Cher- apanamjeri et al. (2025) proved that under the traditional definition of unlearning, there exist simple model classes with finite VC dimension, such as linear classifiers, where traditional exact unlearning requires the storage of the entire dataset in order to unlearn. For large datasets, this makes unlearning under the traditional definitions impractical.
1. Introduction
'Comell University Boston University. Correspondence to: Linda Lu <lulinda@ cs.cor.ell.edu>.
Proceedings of the nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

System-Aware Unlearning Algorithms
A
A
Dediton Bounday
A
Deletion Request
Dicidton Banndaa
4
A
A
(a) Hard Margin SVM with Deletion
(b) Traditional Unlearning A(S ~ 2,
(c) System System-Aware Unlearning A(S' U.2)
Figure 1. Consider deletion on a hard margin SVM where the state-of-system U)) is the set of support vectors (in dark blue) and the unlearned model A(S, U). Let S' the set of support vectors Thus, we have A(S, () = A(S', ,2). Under traditional unlearning definitions, when support vector is deleted, need to recover the hypothesis from training new hard margin SVM the remaining data points A(S U, @) (Figure 1(b).. This can lead to new support vectors being selected (ic. the green point in Figure I(b)), which can drastically change the decision boundary. Under system aware unlearning, since the support vectors are the only points in the sample that affect the decision boundary, we can treat the remaining support vectors after deletion as a plausible starting sample S' U and train a new hard margin SVM on the remaining support vectors A(S' () (Figure 1(c)), as if the other points in the sample
existed.
At the core unlearning lies a fundamental question: What does it truly mean to "remove" " a data point from a trained model? And more importantly, when we provide privacy guarantees for deleted points against an outside observer or attacker, what information can this allacker reasonably possess? The current definitions of exact and approximate unlearning take a worst-case perspective here and focus on the output hypothesis being indistinguishable from a retrained model (Sekhari et al., 2021; Ghazi et al., 2023; Guo et al., 2019). However, this approach overlooks a key aspect of the unlearning problem: the observer and their knowledge of the system. In the real world, the feasibility and complexity of unlearning should depend on what the observer can reasonably access, such as model parameters, data retained by the ML system in its memory, data ever encountered by the ML system, etc. For instance, consider a learning algorithm that relies on only a fraction of its training dataset to generate its hypothesis and hence the ML system only stores this data. In such cases, unlearning data point should intuitively be more straightforward. Even if the entire memory of the system is compromised at some point, only the privacy of the stored points is in jeopardy as long as the learned model does not reveal much about points that the model did not use. Even if the observer has access to larger public datasets that might include parts of the training data, we can expect privacy for data that the system does not use directly for building the model to be preserved. Con- versely, if the algorithm utilizes the entire dataset and retains all information in memory, unlearning becomes far more challenging, potentially requiring retraining from scratch, and this is the scenario the current definitions aim to cover.
chine unlearning, which provides unlearning guarantees against an attacker who can observe the entire state of the system after unlearning (including anything the learning system stores uses internally). If the system stores the entire remaining dataset, then system-aware unlearning definition becomes stringent as traditional unlearning, but otherwise relaxes it. Thus, we prove that system- aware unlearning generalizes traditional unlearning. We present a general framework for system-aware un- learning using sample compression based or core set based algorithms. These algorithms leverage the fact that when algorithm relies on less information, less information can be exposed to attacker.
We present an exact system- system-aware aware unlearning algorithm for linear classification using selective sampling for sam- ple compression, thus resulting in the first exact un- learning algorithm for linear classification requiring memory sublinear in the number of samples. We estab- lish theoretical bounds on its computation time, memory requirements, deletion capacity, and excess risk.
We generalize our approach from linear classification to classification with general functions. Thus, providing a novel reduction from (monotonic) selective sampling for general function classes to system-aware unlearning.
The third bullet is particularly interesting because Chera- panamjeri al. (2025) proved that under traditional unlearn- ing, any exact unlearning algorithm for linear classification must store the entire dataset.
2. Setup and Unlearning Definition
Let X' be the space of inputs, y be the space of outputs, D be a distribution over an instance space Z = X xx), F x be model class, and é: y x y R. be a loss function. The
Contributions. Our main contributions are:
We propose a new, system-aware formulation of ma-
2

---

System-Aware Unlearning Algorithms
goal of a learning algorithm is take in a dataset S Z* over the instance space and output a predictor f IF which minimizes the excess risk compared to the best predictor f" < F in the model class, where the excess risk is
will not be statistically indistinguishable from each other. Thus, under Definition 2.1, this is not valid unlearning algorithm. However, this is valid unlearning algorithm from the perspective of an attacker who only observes the model after unlearning and (in the best case) stored samples C x U; here neither of these reveals any information about the deleted samples U. Furthermore, an attacker has no ability gain access to S U and compare what would have happened had the algorithm been trained on S U.
E(f)== = E [((f(())))) (2:0)-D
9)] min E [=(f" JT (x.N)~D
Our goal in machine unlearning is to provide a privacy guar- antee for data samples that request to be deleted, while ensuring that the updated hypothesis post-unlearning still has small excess risk. We first present the standard def- inition of machine unlearning, as stated in Sekhari et al. (2021); Guo et al. (2019), often referred to as certified ma- chine learning. which generalizes the commonly used data deletion g guarantee from Ginart et al. (2019).
The crucial thing to note is that Definition 2.1 considers a worst-case scenario where every point encountered by the unlearning algorithm except for the deletion requests, regardless of whether those points were actually used or stored, are known to the attacker. However, this is unreal- istic; samples that were never used for learning or stored in memory can never be leaked to the attacker. Towards this end, we develop an alternative definition of unlearning. However, we first need to formalize the information that an adversary can compromise from the system post-unlearning. Definition 2.2 Sfaae-of-SSssenn Let I denote some arbi- trary set of all possible states. For an unlearning algorithm A, we use the mapping lA 2" x 2" ~ A(I) to denote what is saved in the system by A after unlearning (e.g. the model, any stored samples, auxiliary data statistics, etc.). That is, (S, U) denotes the state-of-system (what is stored in the system) after learning from sample S and performing the update for unlearning request U.
Definition 2.1 ((e, -unllarrnn For a dataset S 22 ,nd deletions requests U s S, a learning algorithm A: 2" A(F) and an unlearning algorithm A: 2" xFxT - A(F) is (c, -umlearning if for any F F.
sct ((S) F) +F) 85,
and
Pr(A(0,A(5 \ U),T(S>))) ()) F) SE Pr (A(U, A(S), T(S)) +6,
where T(S) denotes any intermediate auxiliary information that is available to Á for unlearning.
For the system to be useful, it is natural to assume that the state-of-system (S,U) either contains the unlearned model A(S, U), or more generally, the unlearned model A(S,U) can be computed as a function of AA U). If algorithm A requires the storage of samples, intermediate models, or auxiliary information in order to learn or unlearn in the future, then those must also be contained in (S, U). Whenever clear from the context, we will drop the subscript A from lA to simplify the notation. Using the state-of- system (s,,U)), we present a system-aware definition of unlearning.
Sekhari et al. (2021) also defined a notion of deletion ca- pacity, which controls the number of samples that can be deleted while satisfying the above definition, and simultane- ously ensuring good excess risk performance. We defer discussion of other related work on unlearning definitions and algorithms to Appendix A.
The above definition implicitly assumes that the attacker, in the worst case, has knowledge of S U and can execute the unlearning algorithm on S U. Although this provides privacy against the most knowledgeable attacker, we argue with very simple motivating example that the above defi- nition may, unfortunately, be an overkill even in some toy scenarios where we want to unlearn. Consider an algorithm that learns by first randomly sampling a small subset C' = 5 of size mn and then uses C' to train a model and discards the rest of the samples in S X C. Now, consider an unlear- ing algorithm that, when given some deletion requests U, simply retrains from scratch on C' A U. This unlearning algorithm is not equivalent to rerunning the algorithm from scratch on S N U which would involve sampling a different subset C" of m samples from S X U and then training a model on C². Since C" contains m samples whereas C x U contains m- - |U] samples, the corresponding hypotheses
Let A be (possibly randomized) learning-unlen unlearning algorithm, that first learns on dataset S 2", then processes set of deletion requests U S S, and after unlearning, has state-of- system (S, We say that A is a system- -wwae--aarr---... (c,8)- 5)- unlcarning algorithm if for all S, there exists a S' c S, such that for all U _ S, for all measurable sets F,
Definition 2.3 (
PI(L, e F) PI(la(S' &
and Pr(la(S' (.,)) (. F) 8
If an unlearning algorithm satisfies Definition 2.3 with == 8 O, then we say that the algorithm is an exact system-
3

---

System-Aware Unlearning Algorithms
aware unlearning algorithm. We further remark that this definition assumes that the selection of U is oblivious to the randomness in A, but can depend on S.
+M((S' UUU),
where the last line holds by non-negativity of mutual infor- mation.
The definition above indicates that for any sample S, there exists a subset S" that one can think of as being a good rep- resentative of S because the state-of-system when trained on S is nearly identical to that when trained on S'. For all unlearning requests U. the state-of-system (A( af- ter processing the set of deletions is statistically similar to the state-of-system (S U, 2) when directly training S' < U. Under system aware unlcarning, we take advan- tage of the fact that the algorithm designer has control over the information that an attacker could compromise after unlearning, specifically, the fact that the state-of-systen is mostly determined by the smaller subset S". Recall that the traditional unlearning definition does not account for this.
Thus, S' U leaks no more information about U than S U. For recovering the suraining-from-scraae hypothesis A(S U, to be reasonable objective for providing privacy, traditional unlearning definitions implicitly assume that the information between the deleted individuals U and the remaining dataset 5 > U is small. Theorem 2.4 implies that if the information between U and S U is small, the information between U and S' U is also small. We note that all of our technical results, including the relative privacy guarantee from Theorem 2.4, hold without any assumptions on the mutual information between S and S s U.
Clearly, taking S" S and (S,U)) US,,U) (the state- of-system to be exactly the unlearned model), we recover the traditional notion of unlearning from Definition 2.1. This corresponds to the scenario where the entire remain- ing dataset S U can be accessed by the adversary. Thus, system-aware unlearning strictly generalizes the traditional definition of unlearning. We point out that the traditional definition of unlearning does not require indistinguishabiliyy for auxiliary information stored in the system outside of the unlearned model; thus, the traditional definition does not account for system- awareness.ss If we wanted to view tradi- tional unlearning through the lens of would consider Definition 2.3 with the additional require- ment that S" S.
2.2. When is the Flexibility of S' S Helpful?
To understand the power of having S' to be different from S, consider the following simple scenario: Suppose the learning algorithm A allows for S to be compressed into small set S S S such that A(S, 2) s A(S", with ofate-of-system (A(S, = S". In this case, under our new definition (Definition 2.3), it is straightforward to handle deletion requests U for which S' n = Ø, by not making any change to the trained model. To see this, observe that for such U, A(S' U, A(S' 20) A(5,2), and thus we will satisfy Definition 2.3 with S' on the right-hand side. In other words, the individuals outside of S' are already unlearned for free, since the original model output did not rely on them much to begin with. On the other hand, such an algorithm will not satisfy the conditions of the classic unlearning definition in Definition 2.1 for such a U (see Section 4 for more details and a concrete example).
awareness, we
2.1. Why is Considering S' > U, Instead of S U, Sufficient to Provide Privacy Guarantees?
Since S' must be fixed ahead of time for all possible deletion requests U, S¹ depends S but not on U. If 5" is only function of S and has no dependence on U, then intuitively, S' > U should not leak any more information about U as compared to S X U. We formalize this intuition through mutual information. Mutual information is a common way to measure the privacy leakage of an algorithm (Mir, 2013; Cuff& & Yu, 2016). Mutual information MI(A; B) quantifies the amount of information one gains about random variable A by observing random variable B.
We can formalize algorithms that only rely on a subset of the training dataset as core set algorithms.
Definition 2.5 (Core Set Algorithm). A learning algorithm
Acs 2" A(F) is said to be a core set algorithm if there exists a mapping e: Z + Z such that for any S E Z", C(S) S, and we have
Aes(S) = Acs(
Theorem 2.4. Let dataset S and set of deletions U S S come frme stochastic process p. Then,
We define C(S) S to be the core set of S.
Many sample compression basodd learning algorithms for classification tasks, such as SVM or selective sampling, are core set algorithms (Hanneke & Kontorovich, 2021; Floyd & Warmuth, 1995). For hard margin SVMs, the core set is the set of support vectors (Cortes & Vapnik, 1995), and for selective sampling, the core set is the set of queried points (see Section& 4 for further details). Typically, the number of samples in C(S) is much smaller than [S].
sup(MI(UU;S' - UD (M((USSU)) sO. S.
Proof. Since S' S. notice that S = ((S' x UU) ((S> S') U)). Consider MI(S U:U), applying chain rule:
MI(S x U:U)
MI(S' x U.U) + +M(((S S') x UU U))
4

---

System-Aware Unlearning Algorithms
Additional Examples. To further highlight the benefit
and,
of system-awareness in unlearning, consider the following additional examples:
(S s s S (S.) 8.
Sample Compression. Going back to our motivating example, an algorithm that first trains a model on a and then retrains on C U would be a valid exact unlearning algorithm under system-aware unlearning with S' CC
Consider the following unlearning algorithm, denoted by Acs: Given a dataset S and unlearning requests U, return the hypothesis IA.. (e(5) U). This procedure enjoys the following guarantee:
small compressed set
Hard Margin SVM. S" can be taken to be the set of support vectors. Figure 1 depicts the key differences be- tween traditional unlearning definitions (Definition 2.1) and system-awas aware unlearning (Definition 2.3) on a hard margin SVM example.' !
Theorem 3.1. The algorithm Acs (defined above) is a (e, -.yt))-ystemaaare unlearning algorithm with S' C(S), with the state-of-system defined as: 1A(5,U) IA, (U)
Approximate Sample Compression. Let f: Z' F be the regularized ERM with regularization of sample and let C' S be small compressed set of the sample. An algorithm that outputs (1 (1-7)-((C) ((C+U)++ + (()) Lap(2*/Ae) is a e-system-aware unlearning algorithm. This follows from differentially private output perturba- tion (Chaudhuri et al., 2011; Dwork et al., 2014). We can interpolate between sample compression scheme and private model trained the full dataset.
Particularly, Acs only needs to make unlearning updates for deletions inside the core set, i.e. when C(S) n U * Ø, otherwise we just return AUN (E(S), Importantly, for most points (which are not in C(S)), nothing needs to be done during unlearning. Furthermore, only C(S) needs to be stored the system. Thus, using core set algorithms, we can unlearn more efficiently in terms of computation time and memory compared traditional unlearning.
4. Efficient Unlearning for Linear Classification via Selective Sampling
Further note that for all of the above examples, we only need to make an unlearning update when the set of deletions falls within the small set S". This automatically gives us a large deletion capacity; points outside of S' can always be deleted for free. Furthermore, the expected deletion time is small because computation only needs to be performed for a small number of points at the time of deletion. This case of unlearning gives us an incentive to learn models that depend on a small number of samples. In Section 3, we exploit the fact that algorithms that rely on fewer samples while training are easier to unlearn.
Linear classification is not only a fundamental problem in learning theory, but its use in practice continues to be widespread. For example, in large foundation models and generative models, the last layers of these models are often fine-tuned using linear probing, which trains a linear classi- fier on representations learned by a deep neural network (Be- linkov, 2022; Kornblith et al., 20.9). As unlearning gains increasing attention for fine-tuned large-scale ML models, the need for efficient unlearning algorithms for linear classi- fication grows significantly. However, Cherapanamjeri et al. (2025) proved that under traditional unlearning definition, exact unlearning for linear classification requires storing the entire dataset. For today's 's large datasets, this makes exact unlearning under the traditional definition impractical, even for the simple setting of linear classification. Furthermore, approximate unlearning algorithms, such as the one from Sekhari et al. (2021), reduce to exact unlearning for linear classification. Our key insight in this section is that by using selective sampling as a core set algorithm, we can design an exact system-aware unlearning algorithm that requires mem- ory that only scales sublinearly in the number of samples; recall that this is theoretically impossible under the tradi- tional unlearning definition Cherapanamjeri et al. (2025). We also prove that the expected deletion time is significantly faster than traditional unlearning. Thus, demonstrating that system-aware unlearning algorithms are more efficient than traditional unlearning algorithms.
3. System-Aware Unlearning Algorithm via Core-Sets
Various learning algorithms rely on core-sets. In this section, we show how traditional unlearning algorithms can build on core-sets to get system-aware unlearning algorithms. Let C be a mapping that satisfies
x)(S))()=C)
U,
for any S and U S S. Furthermore, consider any unlearning algorithm AUN, that induces the state-of-system A and sat- isfies the traditional definition of unlearning (Definition 2.3), iee we have:
Pr(lA,, Pr(IA.. (S,U) ( US.
As seen in Figure 1, depending on the selection of S", system- aware unlearning can lead to very different unlearning objectives compared to traditional unlearning, some of which may be easier to satisfy than the restrictive condition of traditional unlearning.
Selective sampling (Cesa- Dasa--Bannchi et al., 2009; Dekel et al., 2012; Zhu Nowak, 2022; Sekhari et al., 2023; Hanneke
5

---

System-Aware Unlearning Algorithms
et al., 2014) is the problem of finding a classifier with small excess risk using the labels of only few number of points. It has become particularly important as datasets become larger and labeling them becomes more expensive. Typi- cally, selective sampling algorithms query the label of points whose label they are uncertain of and only update the model on points that they query. Thus, selective sampling-bar algorithms can be seen as core set algorithms where the core set is the set of points where the label was queried. Under mild assumptions, selective sampling can achieve the optimal excess risk for linear classification with an exponen- tially small number of samples (Dekel et al., 2012).
Algorithm System-Aware Unlearning Algorithm for Lin-
car Classification using Selective Sampling
Require: Dataset S of size T
Deletion requests U
Deletion capacity K > 0
Sampling parameter 0 S K
1:
Function BBQSAMPLER(S. K))
2: Initialize: À = K, wh 0, AL, by = 0, Q=
3:
for each t = ...., , ,, do
4:
if x. Ar,A,,1 > T then Query label yr. and update
5:
6:
A - A + 2, by + bb- yt
Assumptions. We consider the problem of binary lin- ear classification. Let x e Ied be such that ||x||| s and y E {+1,-1), Furthermore, we assume that there exists a E Rd, |u| s 1 such that E[ xx] x.., This is the re- alizability assumption for binary classification and ensures that the Bayes optimal predictor for y is sign (u' az). In the following sections, let T := |S| and N7 := =[(S))
7:
W/ + A by, Q Qu ( }1
else
Set A₂ AL-1, be + b wc W1-1
10: return Q, AT, bT, WT
11: Function DELETIONUPDATER Q, A, w,,,w,U w,U) U)
12: for (x, U such that (æ, E Q do
13:
Update Q - Q ~ {z}
Our goal in linear classification is to find a hypoth- esis that performs well under 0-1 loss, i.e. we set ((((x),)) 1(f(x)+ + y). With this goal in mind, we define the excess risk for hypothesis w E(w) == E(a,y)-D [1 (sign(""as x)) y} 1 (sign(u x) + y}}-
14:
Update A < A- xxx b c b- yr and w - A-
15: return 2,X,b,u
16: // Learn a predictor via selective sampling //
17: 2, A, b, w BBQSAMPLER(S.. X, k)
18: // Update the predictor for core set deletions //
We use the selective sampling algorithm BBQS from Cesa-Bianchi et al. (2009) to design our unlearning algorithm, given in Algorithm 1. In particular, our algorithm uses BBQSAMPLER to learn a predictor that only depends on small number of queried points Q. Let the core set C(S) be the set of queried points Q when the BBQSAM- PLER executes on S. The final predictor of Algorithm after learning returns an ERM over (()) and stores C(S). Then when unlearning U. Algorithm 1 updates the predictor to be an ERM over ((S) \ U and removes from memory. After unlearning, the model output and everything stored in memory only rely on E(S)* > U.
19: 2, A, b, w + DELETIONUPDATEE A, w. U)
20: return sign x)
The monotonicity of the query condition of the BBQSAM- PLER stems from the fact that the query condition is only x-dependent and does not depend on the labels y at all. We can interpret the query condition as testing if we have al- ready queried many points that lie in the same direction as Tt, because if so, we can be fairly confident of the label of Zy- In particular, we have that if x; A, Iz > T- for some t [T], then x. ATT, Te > T for any j [T]. Intuitively, the monotonicity of the query condition follows from the fact that if a direction was not well queried before deletion, it will not be well queried after deletion. C(S) U only contains queried points, all of which will be re-queried after deletion. Thus, we do not need to re-execute the BBQSAM- PLER at the time of unlearning in order to determine the new set of queried points. We can simply remove the effect of U from the predictor, and we only need to make an update for deletion requests in U that are also in C(S).
Theorem 4.1. Given the set S and deletion requests U, let C(S) denote the subset of points for which the labels were queried by BBQSAMPLER in Algorithm 1, and let A(S,U) denote the unlearned model. Then, Algorithm an exact system-awar unlearning algorithm with S" = C(S) and state-of-system (S, ( (A(S, U), C(S) ((S)>U), U)) In particular, it satisfies Definition 2.3 with = 8 ==20 O.
The proof of Theorem 4.1 relies on a key attribute of the BBQSAMPLER its query condition is monotonic with re- spect to deletion. In particular, monotonic query condition one such that for all datasets S whose set of queried points is Q, and deletions U, the selective sampling algorithm exe- cuted on Q U queries every point in U.
We note that not every selective sampling algorithm has C(C(S) X U) C(S) x U. Various selective sampling algorithms, such as the ones from Dekel al. (2012) or Sekhari et al. (2023), use query condition that depends on the labels y. Due to the noise in these y y's, g-dependent query conditions are not monotonic; points that were queried before deletion can become unqueried after deletion. This makes it computationally expensive to compute the core set
Theorem 4.2. For any dataset S. Algorithm satisfies C(C(S) U)= C(S) U for all U g S.
6

---

System-Aware Unlearning Algorithms
after unlearning. We note that since the BBQSAMPLER uses y-independent query condition, the predictor before unlearning is slightly suboptimal in terms of excess risk. However, we are willing to tolerate a small increase in excess risk in order to unlearn efficiently. Additionally, it is unclear how much the excess risk of y-dependent selective sampling algorithms would suffer after unlearning.
i be the predictor after K core set deletions. We want to ensure that the signs of de and i remain the same for all unqueried points. We do so by first demonstrating that de ex- hibits stability (Bousquet & Elisseeff, 2002; Shalev-Shwartz et al., 2010) on unqueried points. For any unqueried point æ, |w x - w æ < <VK- KK .dlog T' Log T-. Then we show that w has a 5/2 margin on the classification of every unqueried point. Putting these together, we show that for up to K s O [logTHoo((1/6) deletions, we can ensure that the signs of ú and úē agree unqueried points. Thus, after unlearning, we can maintain correct classification on un- queried points with respect to the Bayes optimal predictor.
Algorithm is not valid unlearning algorithm under the traditional definition (Definition 2.1). When queried point is deleted, an unqueried point could become queried, therefore, C(S < U)= # C(S) (.. U. Thus, under traditional unlearning, during DELETIONUPDATE not only would we have to remove the effect of U, but we would also have to add in any unqueried points that would have been queried if U never existed in S. It is computationally inefficient to determine which points would have been queried, and it is unnecessary from a privacy perspective. An attacker could never have known that such an unqueried point existed and should have become queried after deletion since it was never used or stored by the original model. This highlights the need for having our proposed definition of unlearning.
22.7
We cannot make any guarantees on the NT queried points and the Tg margin points, so we assume full classification er- ror on those points. Finally, using generalization bounds for sample compression (Kakade & Tewari, 2008), we convert the empirical classification loss to excess risk bound.
Memory Required for Unlearning. The memory required for unlearning is exactly the number of core set points, Od log T), and the size of the model, Odd)), which is significantly less memory than storing the entirety of S of size T. Under system-aware unlearning, we obtain the first exact unlearning algorithm for linear classification requiring memory sublinear in the size of the dataset.
Theorem 4.3. The memory required by Algorithm I deter- mined by the number of core set points, which is bounded by NT = OdT logT). Furthermore, with probability 1 5, the excess risk of the final predictor sign(w wTo z)) returned by Algorithm I satisfies
Deletion Capacity and Excess Risk. Theorem 4.3 bounds the core set deletion capacity. Since k is free parameter, we can tune it to increase the core set deletion capacity at the cost of increasing the excess risk after deletion. We are trading off deletion capacity at the cost of performance.
E(w) = 0
NN log T' log(1/6)
T T3- Ny
after unlearning up to
T
K K=
4.1. Expected Deletion Capacity
dlog T- -lg (1/0)
Notice that the deletion capacity bound in Theorem 4.1 only applies to core set deletions and does not account for samples in U that are outside C(S). and these can be deleted for free. Thus, we have much larger deletion capacity than what is implied by the bound in Theorem 4.1. Assume that deletions are drawn without replacement from μ: X - [0, 1.. probability weight vector over points in S. This implies that the probability of x requesting for deletion, i.e. ((x). only depends on x and not on its index within S or on other points in S. This assumption is useful for capturing scenarios where the users make requests for deletion solely based on their own data and have no knowledge of where in the sample they appear. Let KTOTAL be the total number of deletions we can process under μ before exhausting the core set deletion capacity K.
many core set deletions, where Tr = ET 1 (lu a se), and E> 0 denotes the minimizing E in the regret bound in Theorem D.8.
We remark that T. represents the number of points where even the Bayes optimal predictor is unsure of the label, which we expect to be small in realistic scenarios. We give a proof sketch of the theorem (full proof in Appendix D).
Proof Sketch. The bound on the number of points queried by BBQSAMPLER is well known and can be derived using standard analysis for selective sampling algorithms from et al. (2009) and Dekel et al. (2012) (see Theorem D.8 for details). The number of queries made by the B BBSSLE is exactly the size of the core set.
Theorem 4.4. Consider any core-sel algorithm A. Let a de- note denote a uniformly random permutation of the samples in S, and let a be a sequence of deletion requests samples from μ. without replacement. Further, let KesD denote the number of core set deletions within the first KTOUA deletion
To bound the excess risk, we first show that the final pre- dictor d = WT from the BBQSAMPLET before unlearning agrees with the Bayes optimal predictor on the classification of all the unqueried points outside the To margin points. Let
7

---

System-Aware Unlearning Algorithms
requests, then for any K2
Updating the predictor of Algorithm for a core set dele- tion takes (d²) time, using the Sherman-Morrison update (Hager, 1989). Thus, for Algorithm 1, under uniform dele- tion distribution, we have E[time per delction] S &T Tog by plugging in KTOTAL from Lemma 4.5. For large T, this significant improvement over an exact traditional unlearn- ing algorithm that requires (d²) time for each deletion.
1
Prs,aro (KesD > >K)
Es
Σ Ex ( C)(T(
K
T
Koona
B. [ (20 Fea }1}
where C. (S)) denotes the coreset resulting from running A the permuted dataset x TS). Instantiating the above bound for Algorithm/ 1, we have
For large d, the update time can be replaced by quantity that depends on the eigenspectrum of the data's ' Gram matrix. Furthermore, since Algorithm 1 updates an ERM on (S) to ERM on C(S)>U, U, we can further speed up the update time for a core set deletion using gradient descent, which takes (c)) time per update.
Remark 4.7.
Pro (Kesv > K) S Kuru Th
Es[Ex-ul Ma]],
K
where M == ++L+ E A and x (0,1) is the sam- pling parameter from Algorithm 1.
Empirical Evaluation. In Appendix B, we compare the performance of Algorithm I to some common unlearning procedures, from Bourtoule et al. (2021) and Sekhari et al. (2021), and exact retraining. Our experiments show that for linear classification, Algorithm I can unlearn significantly faster with significantly less memory resources compared to other methods while maintaining comparable accuracy.
Given the deletion distribution J4, Theorem 4.4 can be used to bound the total number of deletions TOTAL that Algo- rithm I can tolerate while ensuring that the probability of exhausting the core set deletion capacity K is small. This is done by bounding 5 [Eeeu[x' [x' Mæ]] given μ. For dele- tion x drawn from Jr, [ [x [x]] can be interpreted as the expected value of the query condition x Ar x when Algorithm 1 encounters æ during Icarning. The bound on the total number of deletions KOOMAL depends inversely on Es[Ex-p[=" Mx]]. When Es[Ex-p[ [x]]][]]]]]] is small, x is unlikely to be queried, and thus, Algorithm 1 can tolerate a large number of deletions KTOTAL before exhausting its core set deletion capacity K. Furthermore, the query con- dition decreases as it encounters and queries more points. Thus, Es[Eu=pux=* Mx]] is decreasing as the sample size T increases, and we would expect to be small for large T. x Ma is maximized when x lies in a direction which does not occur very often. Deletion distributions which place large weight on uncommon directions in S will maximize Es (Brp. [x' Mx]] and lead to smaller KTOTAL.
5. Extension to Efficient Unlearning for Classification with General Function Classes
Analyzing the structure of Algorithm 1, we can begin to identify a general framework for unlearning for classifica- tion beyond linear functions. We select core set using a monotonic selective sampler and perform regression on the core set to obtain our learned model. Then, during unlearn- ing, if a core set point is deleted, we perform regression on the remaining core set points to obtain our unlearned model.
Algorithm 2 System-Aware Unlearning Algorithm for Gen- eral Classification using Selective Sampling
Require: Dataset S of size T
Lemma 4.5. Let the deletion distribution μ be the uniform distribution. In this case, the bound in Theorem 4.4 implies
Deletion requests U
Function class J
that we can process a total of KTOTAL = dT T deletions while ensuring that the probability of exhausting the core set deletion capacity K is at most c.
GENBRALBBQSAMPLER from Appendix E
1: Function DELETTONUPDATT(((UU.F)))
2: if n Q # Ø then
4.2. Expected Deletion Time
3: Update - Q
We can make a similar argument for the deletion time. At the time of unlearning, we only need to make an update when deleting a core set point. For all other points, there is no computation time for unlearning. Given KIOAA which can be derived using Theorem 4.4, can give expression for the expected time for deletion.
4:
f= frarmmin,es fer E(rswee ( return 2
It
2
f(x)))
5:
6: // Learn a predictor via selective sampling //
7: f GENERALBBBSS
8: // Update the predictor for core set deletions //
9: e - COLLETTOUUDDATE(,,U,,
Theorem 4.6. For a deletion distribution p. if a core set algorithm A can tolerate up to Krown deletions before exhausting the core set deletion capacity K,
10: return ( 1/2)
Assumptions. We consider the problem of binary clas- sification with a general model class. Let x. E X and
E time per deletion] s
K
{time per core set deletion).
Krons
8

---

System-Aware Unlearning Algorithms
y e [+1,-1}. We are given class of models F {f X [], and we assume that there exists l F such that Ely: œr] = (x),, where the Bayes optimal predictor is sign (x1) - 1/2).. We de- fine the excess risk for hypothesis f according to the 0-1 loss as E(f) == (( -)++))+))))) + (f)
et al. (2020); Gentile al. (2022) for examples), we have efficient algorithm for unlearning. For example, linear functions have (FF O(d
Excess Risk. In general, bounding the excess risk after deletion for a generie F is hard. However, if the regression oracle of F is stable, Algorithm 2 maintains small excess risk after deletion. We formally define stability as follows:
It turns out that for general F, we can construct version of the ABQSAMPIERS as shown by Gentile et al. (2022). The GENERALBBQSAMPLLN is described in Appendix E.
Definition 5.4 (Uniform Stability; Bousquet & Elisseeff (2002)), Let fs F be the predictor returned by learning algorithm A on sample S e 2 and let fs F be the predictor returned by A on S {xx)). The learning algorithm A satisfies uniform stability with rate B if for all e [n1] for all (z. v) E Z, (e(fs(=).))
Theorem 5.1. Given the set S and deletion requests U, let ((S) denote the subset of points for which the labels were queried by GENERALBBE QS AMPLER in Algorithm 2, and let A(S,U) denote the unlearned model. Then, Algorithm 2 is an exact system-aware unlearning algorithm with S' =
((fs)()), v) B(n).
Theorem 5.5. If the regression oracle for IF satisfies uni- form stability under the squared loss with rale B, then with probability 1- 6, the excess risk of the final predictor re- turned by Algorithm 2 satisfies
((S) and state-of- system US( (A(S,U), C(S) UU).
Once again, the proof relies on the monotonicity of the GENERALBBQSAMPLER.
E(î) - (T-
1- TT
(Nr log Tog log( log(1/6))
Theorem 5.2. For any dataset S, Algorithm 2 has the prop- erty for all U s S, E(E(S) UU) = =(S) U. U.
after unlearning up
Memory Required for Unlearning. The memory required by Algorithm 2 is determined by the query complexity of eluder-
(T(
K=O
the GENERAL B B QQS AMPLER, which depends dimension-like quantity of F. The dimension D (F, of model class F projected onto sample S is defined as:
/NT. - (((N)
many core set deletions.
L. Thus, the number of core Typically, we have 3(Nr) x NT.
(((x)=((>))
DFF = sup Σ sup 1 f.gef Ex (f(#=()) (Tx(())))
set deletions that we can tolerate looks like /Nr R..,RRTTO00 8). Similarly to the linear case, the proof follows by showing that the predictor after learning agrees with the classification of the Bayes optimal predictor on the unqueried points with some margin and then leveraging uniform stability to ensure that the predictor before and after unlearning continue to agree on the classification of the unqueried points.
where π is permutation on [T] (Gentile al., 2022).
(FF,S) S) is closely related to the eluder dimension (Russo & Van Roy, 2013) and the disagreement coefficient (Foster et al., 2020), two well-studied active learning complexity measures (see Gentile et al. (2022) for details). The connec- tion between the memory complexity of unlearning and the query complexity of active learning has also been demon- strated in Ghazi et al. (2023); Cherapanamjeri et al. (2025).
6. Conclusion
We proposed a new definition for unlearning, called system- aware unlearning, that provides unlearning guarantees against attacker who compromises the system after un- learning. We proved that system-awad aware unlearning general- izes traditional unlearming definitions and demonstrated that core set algorithms are natural way to satisfy system-aware unlearning. By using less information, we expose less infor- mation to a potential attacker, leading to easier unlearning. To highlight the power of this viewpoint of unlearning, we show that selective sampling can be used to design more memory and compuration-tine-efffcieen exact system-awan unlcarning algorithm for classification. Looking forward, it would be interesting to explore how approximate system- aware unlearning (c, 8 0) can lead to even faster and more memory-efficiee unlearning algorithms.
Theorem 5.3. Assume that, with probability 1 66//,, the ERM| f in Algorithm satisfies the bound Ei=1( (x:)) f(x:))² s R(T,O, 8). Then, the memory required by Algo- rithm 2 is bounded by
Te+ Ny = o min (T. R(T,5) ((TT)))D(FFSS) D(F.))
To find bounds on the convergence rate A(T,0 8) for the ERM, one can look into Yang & Barron (1999); Koltchinskii (2006); Liang et al. (2015). We expect R(T, 5) to be small. Thus, Theorem 5.3 implics that if a function class has small dimension D(F,S) () (see Russo& & Van Roy (2013); Foster

---

System-Aware Unlearning Algorithms
Acknowledgements
Cao, Y. and Yang. J. Towards making systems forget with machine unlearning. In 2015 IEEE Symposium Secu- rity and Privacy, pp. 463-480, 2015.
LL acknowledges support from the Cornell Bowers CIS- Linkedin Fellowship. AS thanks Claudio Gentile for helpful discussions. KS acknowledges support from the Cornell Bowers CIS-Linkedin Grant.
Carlini, N., Tramèr, F., Wallace, E., Jagielski, M., Herbert- Voss, A., Lee, K., Roberts, A., Brown, T., Song, D., Er- lingsson, U., Oprea, A., and Raffel, C. Extracting training data from large language models. In 30th USENIX Secu- rity Symposium (USENIX Security 21), pp. 2633-2650. USENIX Association, August 2021. ISBN 978-1-939133 24-3.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Cesa- Dssa-Bianchi, N., Gentile, C., and Orabona, F. Robust bounds for classification via selective sampling. In Pro- ceedings of the 26th Annual International Conference on Machine Learning. ICML '09, pp. 121-128, New York, NY, USA. 2009. Association for Computing Machinery, ISBN 9781605585161. doi: 10.1 10.144//55337441553399
References
Agarwal, A. Selective sampling algorithms for cost- sensitive multiclass prediction. In Proceedings of the 30th International Conference on International Confer- ence on Machine Learning- Volume 28, ICML'13, pp. I11-127-11--35. JMLR.org, 2013.
Chaudhuri, K., Monteleoni, C., and Sarwate, D. Differ- entially private empirical risk minimization, 2011. URL https: /atsss///rxvv... .rgg www.o/////////./////////
Amin, K., Joseph, M., and Mao, J. Pan-private uni- formity testing. In Abernethy, and Agarwal, S. (eds.), Proceedings of Thirty Third Conference on Learn- ing Theory, volume 125 of Proceedings of Machine Learning Research, pp. 183-218. PMLR, 09-12 Jul 2020. URL https:::: /ttp///petedggsss.eeeepppp v1 25/ ami n20 html.
Cherapanamjeri, Y., Garg, S., Rajaraman, N., Sekhari, A., and Shetty, A. The space complexity of learning- unlearning algorithms, 2025.
Cheu, A. and Ullman. J. The limits of pan privacy and shuffle privacy for learning and estimation, 2020. URL https: /arxiiv org/ abw.//0s.ss 08000..
wwt.hnnss.........mm...... mwr.mrr... m.l..press/
Chien, E., Wang, H., Chen, Z., and Li, P. Langevin un- learning: new perspective of noisy gradient descent for machine unlearning, arXiv preprint arXiv:2401.10371, 2024.
Belinkov, Y. Probing classifiers: Promises, shortcomings, and advances. Computational Linguistics, Lingutsss, 48(1):207-219 2022.
Ben-Hamou, A., Peres, Y., and Salez, J. Weighted sampling without replacement. Brazilian Journal of Probability and Statistics, 32(3):557666, 2018. ISSN 01030752, 23176199.
Chourasia, and Shah, N. Forget unlearning: Towards true data-de data-deletion in machine learning. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), Proceedings of the 40th International Conference on Machine Learning, volume 202 of Pro- ceedings of Machine Learning Research, pp. 6028-6073 PMLR, 23-29 Jul 2023.
Bonato, J., Cotogni, M., and Sabetta, L. Is retain set all you need in machine unlearning? restoring performance of unlearned models with out-of-distribution images, 2024.
URL https:://aaatt
org/ abs/ 12922.
Chowdhury, S. B. R., Choromanski, K., Sehanobish, A., Dubey, A., and Chaturvedi, S. Towards scalable exact machine unlearning using parameter-efficien fine-tuning. arXiv preprint (tt::2400.1625511 2024.
Bourtoule, L., Chandrasekaran, V., Choquette-Chove C. A.,
Jia, H.. Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In 202/ IEEE Symposium Security and Privacy (SP), pp. 141-159. IEEE, 2021.
Cortes, C. and Vapnik, V. Support-vector networks. Mach. Learn., 20(3):273-297, September 1995. ISSN 0885- 6125. doi: 10. (0.10233A410022224111111 URL https: 101...00000112222211118000
Bousquet, O. and Elisseeff, A. Stability and generalization. Journal of Machine Learning Research, 2:499-526, mar 2002. ISSN 1532-4435.
Cuff, P. and Yu, L. Differential privacy as a mutual information constraint. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communi- cations Security CCS' ACM, October 2016. doi:
California Consumer Privacy Act. Title 1.81.5. california consumer privacy act of 2018 [1798.100 100 1798.199.100, 2018.
10

---

System-Aware Unlcarning Algorithms
10. 10.11457977744..2978388 URL http://tt// //tp://xx.ooio.oo
Goel, S., Prabhu, A., Sanyal, A., Lim, S.-N., Torr, P., and Kumaraguru, P. Towards adversarial evaluations for inexact machine unlearning, 2023. URL https:
Dekel, O., Gentile, C., and Sridharan, K. Selective sam- pling and active learning from single and multiple teach- ers. Journal of Machine Learning Research, 13(86):2655- 2012.
wla.xii..or/abb///2200 06640.
Golatkar, A., Achille, A., and Soatto, S. Eteraal sunshine of the spotless net: Selective forgetting in deep networks. In Proceedings of the IEEE//CV Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
Dou, G., Liu, Z., Lyu, Q. Ding, K., and Wong, E. Avoiding copyright infringement via large language model unlearn- ing, 2024. URL htw.s: /ttp://aaxvvvv/.....ae www.:/o.rr//////// /206.. 10952.
Guo, C., Goldstein, T., Hanmun, A., and Van Der Maaten, Certified data removal from machine learning models. In International Conference on Machine Learing (ICML), 2019.
Dwork, C.. Naor, M., Pitassi, T., Rothblum, G. N., and Yekhanin, rithms. In International Conference on Supercomputing, 2010. URL https: / htt.pss//ppp.semmaniccscee.. swwanticschol........ccccccccooe 7916594.
Pan-private streaming algo-
Gupta, V., Jung, C., Neel, S., Roth, A., Sharif- S., and Waites, C. Adaptive machine unlearning, 2021. URL www.tttps////o /ttp://aaxiv..// perxiiiorrgro org / aabs//////// abss/210s 04378.
Dwork, C., Roth, A., al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theo- retical Computer Science, 9(3 ((3-4):211-44 2014.
Hager, W. W. Updating the inverse of a matrix. SIAM Rev, 31:221-239, 1989.
Hanneke, and Kontorovich, A. Stable sample compres- sion schemes: New applications and an optimal svm mar- gin bound. In Algorithmic Learning Theory, pp. 697-721. PMLR, 2021.
Floyd, S. and Warmuth, M. Sample compression, learnabil- ity, and the vapnik-chervonente dimension. Machine learning, 21 21632269,304, 1995.
Foster, D. J., Rakhlin, A., Simchi-Levi, D., and Xu, Y. Instance-dependent complexity contextual bandits and reinforcement learning: A disagreement- perspec- tive, 2020. URL https:t/t//.o arxiv. org/ abs//ba0..0000 03104.
Hanneke, S. et al. Theory of disagreement- active learning. Foundations and Trends in Machine Learning. 7(2-3):131-309, 2014.
Hayes, J., Shumailov, I., Triantafillou, E., Khalifa, A., and
Foster, J. Schoepf, S., and Brintrup, A. Fast machine unlearning without retraining through selective synap- tic dampening, 2023. URL abs/2300 07707.
Papernot, N. Inexact unlearning needs more careful eval- uations to avoid a false sense of privacy. arXiv preprint M.Xi::2433.022/6 2024.
Izzo, Z., Smart, M. A., Chaudhuri, K., and Zou, J. Approx- imate data deletion from machine learning models. In International Conference on Artificial Intelligence and Statistics, pp. 2008-2016. PMLR, 2021.
General Data Protection Regulation. Regulation (eu) 2016/679 of the european parliament and of the coun- cil of 27 april 2016, 2016.
Gentile, C., Wang, Z., and Zhang, T. Fast rates in pool-based batch active learning, 2022. URL https: arxiv. org/ brg/abs// 2202.2222222 05448.
Jang, J., Yoon, D., Yang, S., Cha, S., Lee, M., Logeswaran, L., and Seo, M. Knowledge unlearning for mitigat- ing privacy risks in language models. arXiv preprint arXi::2210.01504 2022.
Ghazi, B., Kamath, P., Kumar, R., Manurangsi, P., Sekhari, A., and Zhang, C. Ticketed earning-unlearning schemes. In Neu, and Rosasco, I.. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 5110- 5139. PMLR, 12-15 Jul 2023.
Kakade, S. and Tewari, A. Concentration, erm, and com- pression bounds, 2008. URL https:////mmeee http::s:////.e.ece/ee../ee ttic. hataaarre//eettteeeeetrreeee
Koltchinskii, V.
Local Rademacher complexities and or- acle inequalities in risk minimization. The Annals of Statistics, 34(6):2593 2656, 2006. doi: 10.1214/ 0090536060000010099, URL https: http://oo...gggg// 1214
Ginart, A., Guan, M., Valiant, G., and Zou, J. Y. Making ai forget you: Data deletion in machine learning. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Bue Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Informa- tion Processing Systems, volume 32. Curran Associates, Inc., 2019.
Korbllihh, S., Shlens, J., and Le. Q. V. Do better imagenet models transfer better? In Proceedings of the IEEE/CV

---

System-Aware Unlcarning Algorithms
conference on compuler vision and pallern recognition, pp. 2019.
Yao, Y., Duan, J., Xu, K., Cai, Y., Sun, Z., and Zhang, A survey large language model (Ilm) security and pri- vacy: The good, the bad, and the ugly. Hiih-Confidence Computing, Pp. 100211, 2024.
Kurmanji, M., Triantafillou, P., Hayes, J., and Triantafillou, E. Towards unbounded machine unlearning, 2023. URL https: ptttps://arre //arivv.avvv////aa//aa/eaaaaiiva org/ abs/ 2302. 09880.
Zhu, Y. and Nowak, R. Efficient active learning with ab- stention. Advances in Neural Information Processing Systems, 35:35379-35399 2022.
Liang T., Rakhlin, A., and Sridharan, K. Learning with square loss: Localization through offset rademacher com- plexity. In Grünwald, P., Hazan, E.,, and Kale, S. (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1285, Paris, France, 03-06 Jul 2015. PMLR. URL https:ttp/.....c wwR.hhttss:/pprceeeeeeet peroocediing.... ml press/v4// Liang15. html.
Mir, D. J. information-theoreti foundations of differen- tial privacy. In Garcia-Alfaro, J., Cuppens, F., Cuppens- Boulahia, N., Miri, A., and Tawbi, N. (eds.), Foundations and Practice of Security, pp. 374-381, Berlin, Heidel- berg, 2013. Springer Berlin Heidelberg. ISBN 978-3-642- 37119-6.
Neel, S., Roth, A., and Sharifi- Maliji-Malvaajerdi, Descent-to- delete: Gradient brasee methods for machine unlearning. In Proceedings of the 32nd International Conference Algorithmic Learning Theory (ALT), 2021.
Pawelezyk, M., Di, Z., Lu, Y., Sekhari, A., Kamath, G., and Neel, S. Machine unlearning fails to remove data poisoning attacks, 2025. URL https: /arxiv. org/abs/2ael 2406 17216.
Russo, and Van Roy, Eluder dimension and the sam- ple complexity of optimistic exploration. In Burges, C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
Sckhari, A., Acharya, J., Kamath, G., and Suresh, A. T. Re- member what you want to forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 14:18075-18000 1886, 2021.
Sekhari, A., Sridharan, K., Sun, W., and Wu, R. Selective sampling and imitation learning via online regression. 2023.
Chalev-Shwarte S., Shamir, O., Srebro, N., and Sridharan, K. Learnability, stability and uniform convergence. Jour- nal of Machine Learning Research, 11(90))2635-2670, 2010.
Yang, Y. and Barron, A. Informattin-theeortie determina- tion of minimax rates of convergence. The Annals of Statistics, 2765):1564 - 1599, 1999. doi: 10.1214/aos/ 1017939142. URL https: /ww.ooioooooooooooooo wtw..oogg/...2... bos/1017939142.
12

---

System-Aware Unlearning Algorithms
A. Related Work
Beyond the standard definition of machine unlearning from Sekhari et al. (2021); Guo et al. (2019), some other machine unlearning definitions have been proposed. Gupta et al. (2021) generalizes the machine unlearning definition from Sekhari al. (2021); Guo et al. (2019) handle adaptive requests. Chourasia & Shah (2023) proposes a data deletion definition under adaptive requesters which does not require indistinguishability from retraining from scratch. They require that the model after deletion be indistinguishable from a randomized mapping on S with the deleted individual replaced. This definition assumes that the attacker does not have knowledge of the unlearning algorithm itself. If the data delction requesters are non-adaptive, then π can be replaced by the unlearning algorithm A, and we recover the standard definition of machine unlearning. However, in general, system-aware unlearning does not generalize this definition. Compared to system- aware unlearning, the data deletion definition from Chourasia Shah (2023) makes the stronger assumption that the attacker has knowledge of every remaining individual, but the weaker assumption that the attacker does not have knowledge of the unlearning algorithm.
Neel et al. (2021) proposed distinction between traditional unlearning and "perfect" unlearning. Under perfect unlearning, not only must the observable outputs of the unlearning algorithm be indistinguishable from the model, but the complete internal state of the unlearning algorithm must be indistinguishable from the rerriied-ffrom-scraaee state. We note that system-awas aware unlearning when S' = S is exactly equivalent to perfect unlcarning. Golatkar et al. (2020) proposed a definition of unlearning that requires the existence of certificate of forgetting, where the certificate can be any function that does not depend on the deleted individuals, rather than the fixed certificate of wawraiiinn-foo--rreeeeee is akin to requiring the existence of S = S in the definition of system-aware unlearning. rather than fixing S' = S. We note that our system-aware algorithm is able to leverage the flexibility in S' to achieve more efficient unlearning, while the algorithms in Golatkar et al. (2020) ultimately do attempt to recover hypothesis close to retraining wroning--foo--o from-scratch, however, we find the connections in the definitions interesting to point out.
This
Maintaining privacy under system-aware unlearning is closely related to the goal of pan-privacy (Dwork et al., 2010; Amin et al., 2020; Cheu & Ullman, 2020). In the setting of pan- san-privacy. user data is processed in a streaming fashion, outputs produced in sequence, and adversary may compromise the internal state of the algorithm at any point during the stream. The goal of pan-privacy is provide privacy against adversary who compromises the internal state at any point in the stream and has access to the preceding outputs.
Beyond unlearning definitions, there has been much work in the development of certified unlearning algorithms. The current literature generally falls into two categories: exact unlearning algorithms which exactly reproduce the model from retraining from scratch on S U (Ghazi et al., 2023; Cherapanamjeri et al., 2025; Bourtoule et al., 2021: Cao & Yang, 2015; Chowdhury et al., 2024) or approximate unlearning algorithms which use ideas from differential privacy (Dwork et al., 2014) to probabilistically recover a model that is "essentially indistinguishable" from the model produced from retraining from scratch on S U (Izzo et al., 2021; Sekhari et al., 2021; Chien et al., 2024; Guo et al., 2019). The exact unlearning algorithms are typically memory intensive and require the storage of the entire dataset and multiple models, while the approximate unlearning algorithms tend to be more memory efficient. Certified machine unlearning algorithms meet provable guarantees of unlearning. However, many of the algorithms are limited to the convex setting.
There are a number of (uncertified) unlearning algorithms which have been shown to work well empirically in the nonconvex setting (Goel et al., 2023; Kurmanji et al., 2023; Jang et al., 2022). Furthermore, a number of these empirical methods attempt unlearn in "data-free" manner where the remaining individuals are not stored in memory when unlearning (Foster et al., 2023; Bonato al., 2024). However, recent work has shown that these empirical methods do not unlearn properly and do indeed leak the privacy of the unlearned individuals (Hayes et al., 2024; Pawelczyk et al., 2025).
Furthermore, existing lower bounds prove that there exist simple model classes with finite VC and Littlestone dimension where traditional exact unlearning requires the storage of the entire dataset (Cherapanamjeri et al., 2025). For large datasets, this makes exact unlearning under the traditional definition impractical. Additionally, Cherapanamjeri et al. (2025) proved that even approximate algorithms for certain model classes require the storage of the entire dataset for the hypothesis testing problem after deletion. This provides strong evidence that even approximate learning under the traditional definition requires storing the entire dataset.
13

---

System-Aware Unlcarning Algorithms
0.88
0.5
Accuracy
0.70
0.00
Algarith
0.55
gorrithh 1
SISA
0.50
SISA
Exact Retraining
Exact Retraining
Number of Deletions (in 1000s)
Number of Deletions (in 1000s)
(a) Purchase Dataset
(b) Margin Datasct
Figure The test accuracy of each unlcarning method over the course 80,000 label dependent deletions.
B. Experimental Evaluation
Our theoretical results provide guarantees for the worst case deletions. We experimentally verify our theory, and we demonstrate that in practice, Algorithm can maintain small excess error beyond the core set deletion capacities proven in Theorem 4.1. Furthermore, Algorithm is significantly more memory and computation time efficient compared to other unlearning methods for linear classification.
We compare the accuracy, memory usage, training time, and unlearning time of Algorithm 1 to the following unlearning procedures. Algorithm trains linear model (y Ar + b) on the core set C(S).
SISA from Bourtoule al. (2021): SISA trains models on separate data shards and aggregates them together to produce final model. During the initial training process, SISA stores intermediate models in order to speed up retraining the time of unlearning. We train linear model (y w 2) on each shard and aggregate the models using uniform voting rule.
Exact Retraining: We train a linear model (y = w x)) on the entire dataset and perform an exact retraining update for each deletion.
Unlearning Algorithm from Sekhari al. (2021): For linear regression (y= wTz) this algorithm precisely reduces to exact retraining.
We compare the results on two different datasets.
Purchase Dataset: A binary classification dataset on item purchase data curated by Bourtoule et al. (2021) with 249,215
points in dimension d= 600.
Margin Dataset: synthetic binary classification dataset with 200,000 points in dimension d 100 with hard margin condition 7 = 0.1 (Iu" x| > 0.1, Vx for some underlying u e Rd)).
For each method, we train an initial linear classifier, and then we process sequence of 80,000 deletions (around 40% of the dataset) of points all with class label -1 (we refer to this as sequence of label dependent deletions). Figure compares accuracy of the various unlearning methods over the sequence of deletions, and Table and Table 2 compare the computation time and memory usage of the various methods on the two datasets.
Table 1. Computation and Memory Usage the Purchase Dataset
Initial training time (secs)
Accumulated deletion time (secs) % of data stored in memory
Algorithm 1 SISA Exact Retraining
186.3
58.3
13.15
30.2
1 1174.3
100%
1828.7
579.3
100%
On the Purchase Dataset, first observe that Algorithm 1 can maintain comparable accuracy to exact retraining while dominating exact retraining initial training time, deletion time, and memory usage. SISA has the best initial accuracy, but
14

---

System-Aware Unlcarning Algorithms
Table Computation and Memory Usage the Margin Dataset
Initial training time (secs)
Accumulated deletion time (secs)
% of data stored in memory
Algorithm
1.3
0.5
0.6%
SISA
20.6
697.1
100%
Exact Retraining
67.8
27.1
100%
Algorithm able to maintain significantly better accuracy under a longer sequence of label dependent deletions compared SISA. The sequence of label dependent deletions creates distribution shift in the training data. Algorithm is robust to this shift due theoretical guarantees, but SISA lacks such theoretical guarantees on its accuracy after unlearning. We also note that SISA is training contributing to its improved initial accuracy. Furthermore, Algorithm can maintain comparable accuracy with significantly fewer samples. Algorithm has longer initial training time, but requires significantly less computation time at the time of deletion compared to SISA. The use of sample compression leads to more efficient unlearning.
expressive model compared Algorithm I and exact retraining which could be
When the dataset allows for a more favorable compression scheme, as the Margin Dataset does, the improvements are even more pronounced. Algorithm 1 can match the initial accuracy SISA and exact retraining, despite using much less data, and Algorithm 1 can maintain significantly better accuracy under longer sequence of label dependent deletions. Furthermore, Algorithm requires significantly less memory and significantly less computation time, both at the time of training and the time of deletion, compared to SISA and exact retraining due to increased sample compression. When the dataset allows for significant compression, Algorithm dominates SISA A and exact retraining in accuracy, memory, and computation time.
15

---

System-Aware Unlcarning Algorithms
C. Proofs from Section 3
Theorem 3.1. The algorithm Acs (defined above) is (s, -yytemaaraaa unlearning algorithm with S' = E(S), with the state-of-system defined as: U)) LAn (E()),
Proof. We have U)) Aux ( (E(S),U).
We also have
(S' U,Ø) (,(E(S) U,Ø) LA ( U)
(C(S) U.Ø).
By definition, lA U) and LAx (C(S) U, are (E, indistinguuisabbl, so (S, and lA 2, must be (e, ( indistinggussable Thus, A is an (s, -syttee---aaaaar unlearning algorithm.
D. Proofs from Section 4
D.I. Notation
[n] (1,2......
Ar = + Σt= 225
Ar Al ΣL- T En,ot zia, where U is set of deletions
Xa + ΣT Σt - =zaa
when j
Arsa
AI + Σt st5t
otherwise
for some f [T]
As = Al Enjes T where is a set of points
bT Σt yt
by Σt M&T Ex,eU ViTt where U is a set of deletions
wr = A bt
wr-u = Ark brsu, where U a set deletions
||]|x u Xu, where u e Rd and X Rdxd
Theorem 4.1. Given the set S and deletion requests U, let C(S) denote the subset of points for which the labels were queried by BBQSAMPLER in Algorithm 1, and let A(S,U) denote the unlearned model. Then, Algorithm an exact system-aware unlearning algorithm with S' = C(S) and state-of-systen Is(S,U) (A(S,)), U). particular, satisfies Definition 2.3 with e = 0.
Proof. Fix any sample S and set of deletions U. Define S' C(S) Q. Clearly, S" c S. The core set of the BBQSAMPLER
is exactly the set of points that it queries. Thus, applying Theorem 4.2, we know C(C(S) U) C(S) ~ U. A(S' U. returns a regularized ERM over C(C(S) U), which is exactly C(S) U, and stores that ERM and the set C(S) U. To
process the deletion U, A(S, U) returns regularized ERM over C(S) U and stores that ERM and the set C(S) U. Thus, (x () = (S" U, for U S.
Theorem 4.2. any dataset S, Algorithm satisfies C(E(S) > U) C(S) x U for all S.
16

---

System-Aware Unlearning Algorithms
Proof. Fix any sample S, and consider the deletion of point zy U. Consider executing the BBQSAMPLER on the queried points {az} compared executing on S. First, observe that the removal of all of the unqueried points has no effect any of the query conditions, z A Te x A7 x, T Thus, when zj is unqueried, all of the points in Q { will be queried when executing the BBQSAMPLER on the queried points Q {my}
Next, consider the case that the deleted point zj was queried. Consider a point 2; that was queried at time t. We know xy Ar' xe > T-x We note that any points after time t do not affect the query condition at time so we only focus on deletions of 2, where j t. We have that
2 A ANz, 21 = xi((A, (A₁ 2zx,))=mm Ir
x Ai x Ar'a
A,
1- Ap (x]A7'xa))
2. A It
1 [==] A5
2 x A/ 1t
T
where the second to last line follows because the second term is always positive. Thus, remains queried when executing the BBQSAMPLER on Q x {æz}. We can apply the above argument inductively for each Ij U to conclude that C(E(S) C(S) U.
Theorem 4.3. The memory required by Algorithm I is determined by the number of core set points, which is bounded by NT= OdTT T). Furthermore, with probability 1- 6, the excess risk of the final predictor sign(w" x) returned by Algorithm I satisfies
N7 log T + log(110)
((w) = 0
T- -TTe-A NT
after unlearning up
- dlog T log (1/()/))
K=O
many core sel deletions, where Te = ΣTh 1( xzl se), and & > 0 denotes the minimizing e in the regret bound in Theorem D.8.
Proof. The bound on number points queried by the BBQ sampler [C(S) is given by Theorem D.8 using standard analysis for selective sampling algorithms from Cesa- Bianchi al. (2009); Dekel al. (2012); Agarwal (2013).
First let's set all of the T- margin points aside. Let wr be the last predictor from the BBQSAMPLER.
First we argue that before deletion, whe and u² x agree on the sign of all unqueried points æ (outside of the Te margin points), An unqueried point x, must have margin of E with respect to u, which means |u æ| E. For an unqueried point 2t, we also have
|wf2: u u
wwr ul| AT |
1 WT u|| Ar ||
(using the monotonicity of the query condition)
s / (10))
(applying Proposition G.1 on the first term and the query condition on the second term)
(for sufficiently large T)
Thus, sign(wF.x) = sign("*x) x), so the final predictor after learning wy and the Bayes optimal predictor u agree on the classification of all of the unqueried points. Furthermore, all of the unqueried points x have a margin of with respect to WT.
17

---

System-Aware Unlcarning Algorithms
Thus, in order ensure that wy and wrsU after |0| K deletions continue agree on the classification of all unqueried points, we need to ensure that kej w A < 5. Using the upper bound on A derived using stability analysis in Theorem D.2, we get the following deletion capacity queried points.
A As2ve(K+ - v dlog log(1/6) -
(Theorem D.2)
2
8²
e(K+ + 1) T dlog 7 (1/(1/))
16
15
16c d dlog T (1/6)
T
K s
16e dlog T log( 1/8)
K Ks o
E².
-logTllo(11)))
For up to K deletions on queried points, WT and WTNU are guaranteed to agree on the classification of all unqueried points. Thus after unlearning up to queried points, wrsy and the Bayes optimal predictor agree on the classification on all of the unqueried points. Note that wr a predictor that only used points in U during training, and yet, has good performance on points that it never used during training. In particular, have that
(( (o.N)
E
1 (sign(u' x) + sign(w) s Tg K,
because outside of the Tg margin points, showed that u and wrsu y agree the classification of all of the unqueried points. Furthermore, and WTsU may disagree on the classification of the K deleted queried points.
Through this observation, we can use techniques from generalization for sample compression algorithms (Kakade & Tewari, 2008) to convert the empirical classification loss to an excess risk bound for wrse- First, observe that
(wTrU) [2 (sign(wT y) 11 (sign(u' x) y}] = B<z,y)- x|| 1|- (sign(wT # sign(u"xx)) $ B (1sggnn sign(u' x)}] [}]]
Thus, look to bound the loss of L(wr u) - (sign( 2) sign(u' z)}]. We are interested in the event that there exists Q U S, U such that ( (WT T + K and L(fere) 2
Pr Q U S such that (es (wrsv) s Tx+ K and L(Wr.U) 2c]
s
Pr @ Us 12 U1 such that (s s ST. + + K and L(WTw))
Σ
(e s ST&+ K and ((WT 2e]
1
Σ U.H
(((ssseuu//lsoov(((TT)) ST&+ + K and L(wTs)) 22 @ [J]]]
Let [Q) Ny and let |U| K, where Ny ---K = I. Now for any fixed U, the above probability is just the probability of having true risk greater than and an empirical risk at most Te K on test set of size T - Ny + K. Now for any random variable z [0, 1], if [[22] E then Pr[z = 0] s 1 s. Thus, for a given Q N U,
Te K and L(WrwV E] s (1 (1-E)T-MM) T-N--
Plugging this in above, we have
Pr US 12 U| =]= such that (wN s Te + K and I.Wr.U) 26]
18

---

System-Aware Unlcarning Algorithms
Σ Σ
(1 (I-
Qr DES.)Q
T T (1 e)
T Σ T (1 -
TT
T Σ T -1 (1-))--N)-1
T
Σ T e
-c(T-N7-1t)
T (T-NNr-T:)
We want this probability to at most 6. Setting e appropriately, we have
E T NT -T= ((Nr log +og(1/)))
Thus, with probability at least - 8,
1
M(fOND) S T - ((Nr+ + log log (1/6))
This implies that with probability at least 1-
E(WTSU) T T-N, N₂. - T3 (1N log( log((1))) 1/8)).
Theorem 4.4. Consider any core-set algorithum A. Let denote denote uniformly random permutation of the samples in S, and let a be sequence of deletion requests samples from without replacement. Further, let Kesp denote the number of core set deletions within the first KYOTAL deletion requests, then for any 1,
Pro, (Keso > *K) s K
Es
Σ (xx((())
Kmyu
Eo te sلlll
where C (=))) denotes the coreset resulting from running on the permuted dataset xt (S). Instantiating the above bound for Algorithm 1, we have
Pr (KesD K) Tvnn
Es [xx[E=p [ Mx]],
where M E A;11] and n (0,1) is the sampling parameter from Algorithm
Proof. We begin by considering
1 R Kespl
Prs (Kesp K)
(Markov's Inequality)
K
1
E
Es
Σ 1(x
Σ 1f2t = Noo] =xo=
K
R=1
(C, is the resulting core set after executing on T (TS))
19

---

System-Aware Unlcarning Algorithms
Eg
E [[] e C,]]
E
Bol = 2or
K
h-1
1
Kama
S.o
Σ F [ (34 Cz)]
Σ
1ar = Fool
K
R=1
1
E
S.o
Kuna
R [1 fox
Cnll
K
This proves the first half of the theorem.
Next define s(x) = [1 e J. Consider the case when the deletion distribution satisfies μ((²) > μ(²²) = x())
v(x'.. This is exactly the worst case terms of deletion capacity: points that have high probability of being included in the core set are exactly the points that have high probability of being deleted.
In this case, can apply Theorem G.2 get
Kiavo
Eg [1 E c.11]
Prs (X>K) K)
Es.o
Σ
KyoraL
<
Es
E
Ex [
(where is sampled without replacement from W)
KTOTAL
$
Es
E Ex-p
E [1 Cx]]
K
KTOTAL
T
$
Eg
Σ
x E [A 14.11a 1x
(plugging upper bound for E,, [1 E Cx))
K
T
s=1
KTOTAL -7
$
Es
E
Σ
x
B [A_1] 10
K.T
6=1
KToYAL TN
Es 5 K T
S
E
Ex-p
x
E
Σ A.L 17
E.s [Bxw Mx]],
where M = Ex Ed Arti] for a given sample S.
Lemma D.I. Let the deletion distribution μ be the uniform distribution. this case, the bound in Theorem 4.4 implies that can process lotal of KTOTAL. TT log
cKT deletions while ensuring that the probability of exhausting the set deletion
capacity K is at most c.
Proof. First, we consider
1
Es Ee
Mxx)
E.
5
T 1=1
d log T
$
Eh a.dil s dlog
T
Plugging this into Theorem 4.4 and solving for KTOMAL completes the proof of the lemma.
D.2. Auxiliary Results
Theorem D.2. Let wT be the final predictor after running the BBQSAMPLER from Algorithm with X = K. Let U be sequence of deletions of length K. Let wr-u be the predictor after the sequence U deletions have been applied. Let x be an unqueried point. Then we have
-212 A wT - w/x- 22/e(K - Vdlog T log(1/8)
20

---

System-Aware Unlearning Algorithms
=o(VK. T VdlogT log(1/)))
with probability at least 1 ò.
Proof. Let Ug be the set of the first deletions. Then we have
A w " who
K
Σ (w/ .., w/)
K 2 /eeKK*+ 1x+1) +1
-T-m/2 dllog T- (1/6)
(applying Theorem D.3)
K
2K Ve(K+1) -T-n/2. Vd Tolg//-
K
s 22/e(K + 1)/T///2
Theorem D.3. Let X = K be the regularization parameter. Consider a set U of deletions where |U] < K. Let Wrst be the predictor after the set of U deletions have been applied and let wrs Wr-(Uuz.) be the predictor after the set of U deletions have been applied along with an additional deletion of zy. Let be an unqueried point. Then we have
A "TU(U TTUUE x S 2Vo(K+1) x- Vdlog T log( (1));
K
for x K, with probability least 1-
Proof. Let ATNU AT - Ej æJr] and br by - EjeU Uz Then we have
A = "IT(DUE)) wTAD
(bTSU - ) ( (ATrU - v.xe)) ))
- to A ATt
(ATO -= -1p- yo (ATru xxxe (axaa)/)a -1= 6J AT
- b A7 / 2..e AT
x. A 2000 A7500
W/t! AT- Y/
1 v AThu Ahherman-Morrisoy
1 1- x A A
1- xx A
1 ATeetaa ATL
x A
11 ! A
ATL 20
Yi
1 x.. A
wh 11 _ A
x3 A 1
u F.r. A xc
V 2 20 V/
xt A
x ATheies
wT 1.. A A
x AT
y:o A 20 Vi
(x]AAh S 1 from Lemma D.6)
(A+ 1)(1 X-T
wT. v. A you! A - X Witt A
X+1
WT x. A u (1 (1+2) Uorr Arhox
X=1
1
2 A . (wT-E- 11)
1
(Wi v:) / [ ATATsuss xt ATh
(applying Lemma D.7)
(wT w:) X+1 T
(applying Lemma D.6 and Corollary D.5)
21

---

System-Aware Unlearning Algorithms
1e(A+1) (w y:)
Ve(A+1) 1) (T u xj +i)
V)(A+1) T (1 - - u');;+ + ve(A+1)
Si 7-1/2
A
Ve(A+1 + 1)
T 1 u l ve(2+1)
A
Ve(A+1) 1)
-T WT 1 ve(1+1)
T
(C. < 1)
X
Ve(A+11 1)
-T-m/2 dlog K) log (1)) Ve(A+1) TT-12
(Proposition G.1)
A
2 [((A+11) T /dlogT log(1/6).
Lemma D.4. Let X be the regularization parameter. Let U be set of deletions such that |U] K. Let Arsu denote AT Enzet 3. Then we have
K (K)
A $
Σ
T
1=0 X2
Proof. We prove the claim using induction. First, assume that x A7 Σx= ( . (induction hypothesis). Consider an additional deletion and the effect on the query condition, x (ATrU xIJ;)) - We have
x²
r A A ATLex
x² (AA A
A
1 x.. A ATle
S A
AT S 1 from Lemma D.6)
(1- x
X+1
K
(x] (z)
(o ( S EK (9) x x T from induction hypothesis)
Σ
T
(1- X+11
x ATThu xo. ATh
$ Σ
T
(Lemma D.7)
x
(K)
Σ d
TT
3
(using induction hypothesis and Lemma D.6)
1)( x+1
$ 3
Σ
T
20 X41
K
K-1
$
Σ
T
X
K
(K)
K
K
T
Σ
T
T
X
A
K
(K+1)
T
Σ
.T
K
T
(Pascal's 's Identity)
K-1
1K)
(K+1)
(K+1)
Σ
K+1)
T
1
X
1-1
22

---

System-Aware Unlcarning Algorithms
K+1
(K+1) T
$
1-0 X
Corollary D.5. Let X = K be the regularization parameter. Let U be set of deletions such that |0] K, then x' A
e-T
Proof.
From Lemma D.4, we have
1
(00
x
A
T
10 X
K (*)
Σ
T
100 X
Σ (7)
T
K
1 K
T
S ee Te.
Lemma D.6. xTAg'' S 1 for any set of S points such that 24 & S, where As I + Exis 2127.
Proof.
We want to consider the x, that maximizes x7 A,A5'a xú. Let Asui = 1 Ezies De Then we want to maximize the following,
x Ag x4 = x (Assi x.,a.] ( xx
xo. A Agk
x Ag
1 x Ag Ti
Let = x! A51, T4 Then we have
a² a
x x 24
1ta
l
1 +
We want maximize the above expression where a & (since 0 A s t). The expression is maximized when a }. Thus, x7 A S x(1+)) X+1'
Lemma D.7. (x] Ag x) s As xi x A x, for any set of S points such that x; E S, where As = Al + Enjes T.a..
Proof. We can decompose the terms A5 Ed Aruuy, 24 El 0g4, and x Ed Bau. Using these decompositions, we compute the following two terms,
d
d Σ 3,us
Σ Srass
2
Σ
23

---

System-Aware Unlcarning Algorithms
and
A7 x
d AT
Σ
a
Σ Ananay
[
d u
d Σ
B
Σ
Σ
d
Bru
2
Σ
2313
From Jensen's 's inequality, we know that (Σ p
Ei p. where 0 for all i and Σ. = =1 since f(z) =x² is
convex. Let P; = A,op/()) 2,a3) (note that all X 's 0) and let x, = 3,/0g- This gives us
(E/) 3,)r33)
)²
Σd Xra3
of
S
E \;a?)
Σ El=1 Xia2
Σ A1a;3
< X1a?
Σ 11138
$
1=1
This directly implies that (x. AT] x)2 & x. Arp x A7 Ni.
Theorem D.8. Let X = K T be the regularization parameter and BBQSAMPLER. Then we have the following regret and query complexity bounds the BBQSAMPLER,
be the sampling parameter of the
Rr min TTe o
1 8
K d log T log 7) g//x
Nr N Odd log T).
Proof. Adapted from the analysis in Dekel et al. (2012) and Cesa-Bianchi et al. (2009).
Let A, u o, and Å wi x. We decompose the regret as follows,
T SE. + Σ 2, < 0. + Σ Z <0,4,> >
T
1
E
=T. U, + +c.
(regret decomposition from Dekel al. (2012) Lemma 3)
We define additional term
sign Â.) A
if [
otherwise
Then have
T
Q:
Σ Z,1 A,4, <0)43
T
Σ Z1 AA(AAA,<
(Å, and Â have the same sign)
ml
Σ Z(A,- (4A--1))) 2
(Á < 0 implies A (A. -
T g ((A::-))²- v)² + 144
(Dekel al. (2012) Lemma 23 (i))
4
|Ael 144 T 7) |A,il
Σ Zi (4-1(w",,u ((-") deww", (w) 2log
8
8
(Dekel et al. (2012) Lemma 25 (iv) where de (ww",uu ww) = [2=" T As - -w)
24

---

System-Aware Unlcarning Algorithms
T 8
do (w ww)) + log Arl + 144 log
+ dlog(A + -NT) + 144 T' 8
(Dekel et al. (2012) Lemma 24 (ii))
of 1
( A dlog T log T )
Let 2y Ar rt. Then we have
T
U. S Σ Ze 11 - -,1=e))
T
E
5 Σ
2, exp
(following Cesa-Bianchi et al. (2009) Theorem 1)
8r
T
T
= (2++e) e)
Σ 21 exp
(when Z, 1, < T by the query condition)
8
11
2²
5 ((++)) e)
Σ Zx
exp
1/x
8
<(2+e)
(following Cesa-Bianchi al. (2009) Theorem
1 s
2/KK
Putting the above terms together completes the proof of regret.
Now for the number of queries. Let x. A,AA'x. r.. Consider the following sum,
T Σ
|AN1
Zer
Ze
log
(Lemma 24 from Dekel et al. (2012) where is the determinant)
A1-1
t=1
1=1
Arr
log
AA
log |Arl
d log( X Nr)
s d log()).
We use the above sum to bound the number of queries,
Ny Σ1
$ Σ
It
T
T
Σ Tt
(og"("loggT))
(using the sum above)
25

---

System-Aware Unlearning Algorithms
E. Missing Details of GENERALBBOSAMPLEER
Define
sup (f(z)-((z)) f.eeF - +1
Algorithm 3 GENERALBBQSAMPLER (Slightly Modified Version of Algorithm from Gentile et al. (2022))
Require: Dataset of size T
-Confidence level ó (0, 1]
Initialize: Po= S and Ro- S
2: for 8= 1, do
3: Initialize within stage f: Ex / t= 0, Qr
4:
5: while PA-1 > 2 + Ø and max ((x, 21) > 39 do
6:
[=1+1 Pick Zz,t argmax pr ((, 21)
7:
Update Q Qt (Ze)
9:
10:
Set Ty = 4, the number of queries made in stage f
11:
if Q # Ø then
12:
Query the labels ,e........ De,T, associated with the unlabeled data in Qr and compute
1 ye.t f(22,1)
for = argmin
feF
2
13:
-12) 3 Set = fx Pe-1 2: - else fo = 1/2,C,= =
14:
15:
Set Pe = Pt-1 Qt and R2 R (C/u Q+)
17:
if (F(
2 2- RRy then
18:
Set L= exit for loop
19:
20:
Set Q= Q Q
22: Compute
1 1 1/
(am=-f()p f(x))) 2
fe argmin
Σ
fef
2
return fe. Q
F. Proofs from Section 5
F.1. Notation
[n] -1,,2....
ss ERM computed over set S
fss= ERM computed over set {x:}
(t) the set of points queried stage f up to time
Ee ===2 2==2"///90 2
26

---

System-Aware Unlearning Algorithms
(Fi,...... = sup, rigeF EL (1=)
((())
Theorem 5.1. Given the set S and deletion requests U, let C(S) denote the subset of points for which the labels were queried by AAEERR in Algorithm 2, and let A(S,U) U) denote the unlearned model. Then, Algorithm 2 is an exact system-aware unlearning algorithm with S' = C(S) and state-of-system (s(,U)) (A(S,U), UU)
Proof. Fix any sample S and set of deletions U. Define S' = C(S)= Q. Clearly, S' S. The core set of the GENERALB-
BQSAMPLER exactly the set of points that it queries. Thus, applying Theorem 5.2, we know C(C(S) x ~U) = C(S) N U.
A(S" U, returns an ERM over C(C(S) N U), which is exactly C(S) U, and stores that ERM and the set ((S) \ U. To process the deletion of U, A(S, U) returns an ERM over C(S) U and stores that ERM and the set C(S) U. Thus,
(A U)= = (S U. Ø) for all U s S.
Theorem 5.2. For any dataset S, Algorithm 2 has the property that for all U S, C(E(S) U)) C(S) U.
Proof. Consider the deletion of any Ij E S. Let Q = U2_ Qe be the set of queried points after execut- ing the GENERALBBQSAMPLER on S, and let Q' = U E' be the set of queried points after executing the GENERALBBQS on @ {2z). Note that C(S) = Q and ((((((()(())))))))) (m,)) Q'. We want to show that Q' 2 (x,))
First, note that the deletion of any unqueried point has no effect on the query condition of any other point, so the set of queried points when executing the GENERALBBQSSMPLLE on is exactly Q. If x. Q, then clearly Q' Q {æy). Thus, we focus on the case where x; Q.
Next, note that the query condition of points queried before zj only depends on points in Q > {zj}. Thus, all points queried before Iy will still be queried.
Let E be the stage and 1* be the time at which x, was originally queried. Let Qe(t') be the set of points queried in stage é before time e' in the original run of the GENERALBBQSAMPLER, For each point queried time t' t", we know D² (x, 2 (t')) ez. Now consider
(())-g()))
sup (x, (())
fgeF (f))1) -(x;))²
(f(x)
sup
(fo -(x;; g(x;))
fager
2
> Ex:
Furthermore, observe that
argmax Dee (2,,)) (1)
(x, 2'. (z₂)))
argmax D² 2: (f)))
DEP Cr (1)
where the first term represents what would be queried at time t' when executing @ > {x,} and the second term represents what would be queried at time f' when executing on Q. Thus, we will query the same set of points in both executions after time t in stage é. Thus, at the end of stage E, when executing on dataset S with x, deleted, we have queried every point in 2e {
At the end of stage É the execution on Q, the set of points remaining the pool is exactly Uf 1 Qr. Each of the query conditions in future stages after stage ex only depends on the points U' Qe. These query conditions are unaffected, and all points in U Qe will be queried.
Thus, the set of queried points after executing the GENERALBBQSAMPLER on @ {xr) is exactly @ (zz). We can apply the above argument inductively for each z, é U to conclude that C(C(S) x U) = C(S)
Theorem 5.3, Assume that, with probability 1-8/T, the ERM f in Algorithm 2 satisfies the bound (f))) A(T,6) 8). Then, the memory required by Algorithm 2 is bounded by
R(T,8) D(F,S) (((T8))D(FFSS)
1))
Ny = 0 min T
22
27

---

System-Aware Unlcarning Algorithms
Proof. For points in R2 P> (U/z1 Q Ce). know that lee (x) 1/2| 3-2- by the design of Algorithm 3. We also know that for all x E RR, (z) fe. (x)) s 2- from Lemma F.1. Thus, for all E R2. (x) 4-2 2-1+2
From the design of Algorithm 3, we also know that [R = IP (U'2 Qe Qeu c() - D(F.)) Let
T. = 1 ((=)) sc}
When 2-2+2 e, upper bound [Ry by Tg. Thus, we have
|-1 (FF.))-(TT.)) Te
Otherwise, when 2-L+2 we know that
[R s 1-11 (DF.S)) AT.,6)
(Theorem G.3)
D(F,S) R(T,8)
(24 s 2
Thus, have that
4--1 ((F.S) min Tg 4
((TT8)-((F.S))
From Theorem G.3, we know that
Nr 44t2, (RTTT)).((F
(Theorem G.3)
s 0
mmin
min
Te + 64 8² R(T,8) D(F,
Theorem 5.5. If the regression oracle for F satisfies uniform stability under the squared loss with rate 3, then with probability 6, the excess risk of the final predictor returned by Algorithm 2 satisfies
E(ʃ) =0 ( N-
lNr log(1/8)))
after unlearning up
V)((T,8)
==O 0
VN 3(Nr)
many core deletions.
Proof. From Lemma F.,, we know that the regression oracle satisfies the following, such that for all S 2", for all i [m]. for all ( }
-(ss)
Let Q the set of queried points and let Nr be the number of queried points. Let be a set of K deletions. Let D, be the of the first deletions. Then, we have
E(Jonon
(x:)) Nr. 8(N))
e
28

---

System-Aware Unlearning Algorithms
In stage l of Algorithm 3, we know that for all æ Ce (the of unqueried points for which we confident the label).
have
sup (f(x)- g.e
SE
E(s(x)) -(x:))
90
due to the query condition of stage L. Thus,
Nr.
K
2
Σ
(fe-o(z)-
Σ
Σ -
E1
Nr
K
k
(z)) (1a))
NT
K (()en Se. D;.1 (x+))²
(Jensen's Inequality)
K
(F f. (xx)))
K
(fDD (Ix) - (z)
K
K Σ NT 3(NT)²
(applying Lemma E.3)
K2.
P...Nr.((N)) 3(Nr)
Plugging this in, we have
((())) S E(s(a)) (g(x)))()x)))244111))
sup 1.gE
Q:
s E K²2 Ny. B(N))
for all x Cz.
The above implies that for any e Ce.
( fo(x)) set KN.N, B(N))2 (oo(z))f((zip)) s Et K B(NT) ((NT)((T))
Furthermore, from Lemma F.2, we know that for all stages f, for all r C₁.
and sign - 1/2) sign(f( 1/2). Thus, fe classifies all of the points in UL_ Cs correctly with some margin. (fgn()((=)) After deletion, feLD and fo agree on the sign of when
Ee K Nr. 3(Nr) -
1
2-
K VT 3(Nr) 2
(5t = 2
A(T,6)
K. V.VNN. 3(Nr) $
VR(T,6)
29

---

System-Aware Unlearning Algorithms
V.((T.0 0) INT.3((N)
K
Thus, for up to
K V
VNT 3(Nr)
deletions, sign sign(fenD(x) - 1/2) sign(fe(x) 1/2) sign( (x) 1/2) on all of the points in U Ce.
For points in Rr P (U%2 Qt u C.). we know that e, (1)) 11/2| s 3 3-2 by the design of Algorithm 3. We also
know that for all R2, If (+) (x) s from Lemma F.1. Thus, for all x R2, -1) 4-22 2 L+2 From the design of Algorithm 3, we also know that [Rz] Ip (U Q uuk ) -(F,S))9((TT))
Rr, is the set of points which we did not query but we are unsure of the label. We know from Theorem 5.3 that
Nr o min T 6² ((T.O)
(min
As shown above, for all other unqueried points, foeD agrees with the classification of the Bayes optimal classifier, despite not using these points during training. In particular, have that
(fo)))
E 1(sign(fe 1/2) * sign(f"(2) 1/2)) Nr + K, S:(OND)
because feeD D and (1) may disagree the classification of the K deleted queried points and the points in Nr points in Rr; they must agree all other unqueried points.
Similarly to the linear case, we can use techniques from generalization for sample compression algorithms (Kakade & Tewari, 2008) to convert the empirical classification loss to an excess risk bound for fo.D: First observe that
ε(h) = E (ssn * (1) +1}1
1e (x) 1/2))
s 1/)
We look to bound the loss of n) ( the event that there exists Q > D c S, 2 DJ such that LL)() (/e s N7+ + K and L(fo.n) ze
- 1/2) # -xgn(/(s))11/)) We are interested in
Pr[3 Q S such that [ss. & Ny + K and L(fe)p) 2c]
Σ DES, Q D
Pr[3
1 such that :f Nr K and L(fann) 2 =]
E
Σ
Σ
(f( s N and L(fg.p) 2c]
I= o
DH
T
Σ
Σ
E (ls.s K and 2e
-
Let [2 = Ny and let [D] K, where N₂ K = I. Now for any fixed Q D, the above probability is just the probability of having true risk greater than and empirical risk at most Ny K on test set of size T - -N K. Now for any random variable 2 E [0, 1], if [[x] 2 then Pr[z 0] < 1- e. Thus, for a given Q @ D.
Prs.ee.pgLiivo NT K and L(Se 2 28 S (1 -E) T-2N,
30

---

System-Aware Unlcarning Algorithms
Plugging this in above, have
Pr[3 DES, 12 DJ = such that (/ s Nr+ K and L(2e,)) ()) 26]
$ Σ
Σ
(1-6) ->2-N
1-1 DDD,
T (1 2 T-2NT
TNN K, (1 -1-
T T.N K (T-
Σ T e (T(-2N))
= Nrt1, ((T-2N))
We want this probability to at most 6. Setting e appropriately, we have
1
T-2NT ((Nr log 7 log(1/6))
Thus, with probability at least - 5,
L(feND) S TN2
((Nr+ T log((11))
This implies that with probability at least 1 1-
1
E(h) S T 2
((Nr + 1) log logg((+ooo[[))) (1
F22 Auxiliary Results
Lemma F.I. With probability at least 1 - for all stages f, for all x Pi-1 2b
((t))f(()))) s 2 and 1 (x) fo, (x) 2-
Proof. The following proof is adapted from Gentile et al. (2022, Lemma 16).
For all e, for all x Pe-1 x Ci.
(f* - fe(x))
(f())-f((z)3
f((=))
(f())-fo(z))
[((()))((()t))++
(f(=)
(f(x)-g(z)²
(fr(z)) fe(x)))
sup
figer (f(x))))))) +1
Dx)(x;
- (
2,60
31

---

System-Aware Unlcarning Algorithms
S T)
(2-9)2
where the second to last line holds with probability 1- 8/T. We also have for all e, for all x E Pa-1 Qc.
(2)
(f)))) (0)))
Σ -())))))
ZiER,
(f(x)- (()))
-f())
sup 1.gE En (f(xt) - ((.,))2++
FEEE
= =D<(x; Q1)
Σ fe. +1)
m.
S 6 (66,7)
92
where the second to last line holds with probability 1- 5/T.. Summing over the rest over all stages é < T with a union bound yields the proof.
Lemma F2. For every for every x e Ct. (i)((f(.))) = sigu(((())))) = sign(f" (z)) and (fo(z) 1122 > 2
Proof. Adapted from Lemma from Gentile et al. (2022).
For every stage every x Ct, we know that (fe, 1/2) > 3 2 by the design of Algorithm 3. Putting this together with Lemma F.I, since C, S Pe-1 2e, we must have for every for every e Cr, sign(Je, (x)) sign(fo(x)) = sign (x)).
Furthermore, we have that (x) 1/2] > 2 2 and (fo (x) - 1/2) > 2
Lemma F.3. Let is e F be the predictor returned by a regression oracle on sample S and let fest é F be the predictor returned by a regression oracle on sample S < (. If the regression oracle satisfies uniform stability under the squared loss, E(g.y) = (i- - y)? then for all S = for all i [n]. for all (#1....,
((fsv(z))=fs(z))) Sn B(n)
Proof. Since the regression oracle satisfies uniform stability under the squared loss, f().v) (g 2-) we have for all S E 2", for all i [m], for all (x.,) E Z,
-)f=(((((()))))) 8(n).
Expanding the left hand side, we have
[(fs(x)-)) - -)) (fsse -) -
+2)fs s2l
- =Ifs(x)² - fsu(1) + (x) -
= -[s((0)² [sv(() (z)
(holds for all y, so set y = (-1,+1) accordingly)
(1) fs(())
From uniform stability, we can conclude
( B(m).
32

---

System-Aware Unlcarning Algorithms
Thus,
f())))) 2. 3()²
G. Helpful Theorems
Proposition G.1 (Agarwal (2013), Proposition 1). With probability least for all t E [T],
| - ulla, s -
Theorem G.2 Hem-Haamuu et al. (2018), Theorem 1). Let X be the cumulative value of sequence of length n S N drawn from Ω without replacement,
X= [[I[ +.. vII,,,
and let Y be the cumulative value of sequence of length n N drawn from Q with replacement,
Y= v(]i +... vJJ.).
the value function v and the weight vector W follow the property that
w(1) w(j) = u 2 v()),
then
x s F[Y].
Theorem G.3 (Gentile al. (2022), Theorem 19). For any pool realization P, the label complexity Ny of Algorithm 3 operating on pool P of size T is bounded deterministically as
Nr s 44 44 D(F.P)
33


Reviews:
[{"review_id": "3fOGg6Gj4M", "reviewer": "Reviewer_MJw8", "summary": "This paper introduces system-aware unlearning, a novel framework that generalizes traditional machine unlearning by relaxing privacy guarantees to account for realistic attacker access to the system’s internal data. It proposes a general approach using sample compression or core sets, where reduced algorithmic reliance on stored data inherently limits attack exposure. The authors demonstrate this via the first exact unlearning algorithm for linear classification with sublinear memory in the dataset size, enabled by selective sampling for compression. Theoretical analysis establishes bounds on computation, memory, deletion capacity, and excess risk, balancing efficiency and privacy in practical settings. This framework bridges rigorous unlearning guarantees with feasible resource requirements.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "See Strengths and Weaknesses.", "methods_and_evaluation_criteria": "See Strengths and Weaknesses.", "theoretical_claims": "The reviewer did not conduct a thorough review of the proofs.", "experimental_designs_or_analyses": "There're no experimental designs.", "relation_to_broader_scientific_literature": "This paper presents work whose goal is to advance the field of machine unlearning, which is specifically oriented to improve the trustworthiness of machine learning.", "essential_references_not_discussed": "The paper focuses on the field of certified machine unlearning, but lacks of following papers:\n\n[1] Eli Chien, Chao Pan, and Olgica Milenkovic. “Certified Graph Unlearning”.\n\n[2] Jiaqi Liu, Jian Lou, Zhan Qin, and Kui Ren. “Certified Minimax Unlearning with Generalization Rates and Deletion Capacity”. In NeurIPS 2023.\n\n[3] Binchi Zhang, Yushun Dong, Tianhao Wang, Jundong Li. \"Towards Certified Unlearning for Deep Neural Networks.\" in ICML 2024.", "other_strengths_and_weaknesses": "Strengths\n\n1. Proposes a practical relaxation of traditional unlearning definitions by introducing system-aware unlearning, which accounts for realistic attacker capabilities.\n2. Generalizes traditional unlearning while enabling more efficient algorithms.\n3. Provides the first exact unlearning algorithm for linear classification with sublinear memory, breaking prior lower bounds (Cherapanamjeri et al., 2024) under traditional definitions.\n4. Rigorous analysis of deletion capacity, excess risk, and computational complexity, with tradeoffs controlled by the sampling parameter $\\kappa$.\n\n\n\n\nWeaknesses\n\n1. The use of mathematical symbols is not standardized. The font size of symbol $\\backslash$, $\\in$,  $\\subseteq$ is different from other letter symbols, which causes difficulties for readers to read.\n\n2. Lack of experimental verification. The paper lacks quantification of the unlearning performance, such as F1 score in [3] and the accuracy of the membership inference attack.", "other_comments_or_suggestions": "1. It would be better to palce Eq.(1) and Eq.(2) after Definition 2.2, which makes the logic more coherent before Definition 2.3.\n2. Grammar error. For example, in Definition 2.3, '... there exists a...' should be '... there exists an...'", "questions_for_authors": "1. Why does the input of state-of-system in Definition 3.1 has only one parameters (i.e., $S$) while the input of state-of-system in Eq.(1) & Eq.(2) has 2 input parameters (i.e., $S$ and $U$)? They all use the symbol $\\mathrm{I}$, but the definitions before and after are not coherent.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wdCyp6WkcH", "reviewer": "Reviewer_Hefv", "summary": "The paper introduces a new system-aware unlearning setting, where attackers have access to only a partial dataset stored in the system rather than the entire dataset. The authors argue that this relaxation enables a more efficient and practical unlearning framework for attackers. To address this setting, they propose a selective sampling-based algorithm to identify the core set and provide  theoretical analysis for deletion capacity, risk and etc.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> TC 1 - *Lemma 4.7: Let the deletion distribution μ be the uniform distribution. Is it always valid to ...*\n\nWe agree that assuming the deletion distribution to be uniform is not always valid. Our main theorem (Theorem 4.6) applies to general data-dependent deletion distributions. Lemma 4.7 is an instantiation of Theorem 4.6 with a uniform deletion distribution in order to provide an illustrative example of deletion time savings under system-aware unlearning. For the main Theorem 4.6, the main assumption we make is that deletion requests are not adaptive/adversarial to updates in the system.\n\n> EDA 1 - *The experimental setup is relatively simple and limited. The current study focuses on ...*\n\nWe emphasize that our contributions are primarily theoretical. Our main contribution is to provide a new definition of unlearning that is not as pessimistic as the traditional one and show how this definition can help us obtain much more efficient unlearning algorithms in a principled way. Several works that have used empirical metrics for unlearning have been proven to leak information about deleted data points [3, 4], thus illustrating the dire need for a theoretically sound definition for unlearning. Even under traditional unlearning definitions, it is still unclear how to perform theoretically rigorous and efficient unlearning in simple models like regression.\n\n> EDA 2 - *Regarding the experiments, would it be possible to provide further evaluations on how ...*\n\nIn Theorem 4.6, the bound on the sample size of $S’$ from the selection process holds under any data distribution. The sample size of $S’$ can be tuned by properly setting $\\kappa$ in the BBQSampler. When $\\kappa$ is large, the sample size of $S’$ is large, leading to higher accuracy. When $\\kappa$ is small, the sample size of $S’$ is small, leading to fast expected deletion times and low memory requirements. The exact tradeoffs are characterized by Theorem 4.4 and Theorem 4.6.\n\n> ERND 1 - *There are also related work in [1] and [2] that emphasize the importance of ...*\n\nThese two papers consider unlearning under unique learning architectures, specifically under machine-learning-as-a-service [1] and federated learning [2] settings. Both of these papers work to satisfy the traditional definition of unlearning under these unique learning systems. We agree that it would be interesting to explore how these unique settings could benefit from a system-aware perspective on unlearning.\n\nPlease let us know if you have any additional questions or concerns.\n\n[1] Eraser: Machine unlearning in mlaas via an inference serving-aware approach. Yuke Hu, Jian Lou, Jiaqi Liu, Feng Lin, Zhan Qin, and Kui Ren. ACM SIGSAC 2024. \n\n[2] Federaser: Enabling efficient client-level data removal from federated learning models. Gaoyang Liu, Xiaoqiang Ma, Yang Yang, Chen Wang, and Jiangchuan Liu.  IEEE IWQOS 2021\n\n[3] Machine Unlearning Fails to Remove Data Poisoning Attacks. Martin Pawelczyk, Jimmy Z. Di, Yiwei Lu, Gautam Kamath, Ayush Sekhari, Seth Neel. ICLR 2025.\n\n[4] Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy. Jamie Hayes, Ilia Shumailov, Eleni Triantafillou, Amr Khalifa, Nicolas Papernot. SatML 2025.", "claims_and_evidence": "theoretical contributions: The work rigorously proves that system-aware unlearning generalizes traditional unlearning, providing bounds on deletion capacity, memory requirements, and excess risk.", "methods_and_evaluation_criteria": "Under partial training setting,  the proposed method use selective sampling-based to select core set points where the label was queried make senses to me and provide interesting perspective to save computation time and capacity.", "theoretical_claims": "Lemma 4.7: Let the deletion distribution μ be the uniform distribution. Is it always valid to assume this scenario? Wouldn't there be data-dependent deletion distributions?", "experimental_designs_or_analyses": "* The experimental setup is relatively simple and limited. The current study focuses on linear classification, which, while important, represents a rather basic scenario. How would the method perform on non-convex deep models or, at the very least, on SVMs?\n\n* Regarding the experiments, would it be possible to provide further evaluations on how the selection process performs under different distributions and sample size of S'", "relation_to_broader_scientific_literature": "The paper broadens the scope of machine unlearning from systematic perspective by shifting from the traditional unlearning model to a more practical system-aware framework", "essential_references_not_discussed": "There are also related work in [1] and [2] that emphasize the importance of system-aware perspectives in machine unlearning, the authors are encouraged to investigate relevant works to better describe its contribution in the development of machine unlearning methods through the lens of system-awareness\n\n\n[1] Yuke Hu, Jian Lou, Jiaqi Liu, Feng Lin, Zhan Qin, and Kui Ren. Eraser: Machine unlearning in mlaas via an inference serving-aware\napproach. Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security, 2024.\n[2] Gaoyang Liu, Xiaoqiang Ma, Yang Yang, Chen Wang, and Jiangchuan Liu. Federaser: Enabling efficient client-level data removal from\nfederated learning models. In 2021 IEEE/ACM 29th International Symposium on Quality of Service (IWQOS), pages 1–10. IEEE, 2021", "other_strengths_and_weaknesses": "see above", "other_comments_or_suggestions": "see above", "questions_for_authors": "see above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OGAnSDhNMf", "reviewer": "Reviewer_ZP3T", "summary": "The authors propose a new definition for unlearning that they refer to as “system-aware unlearning” where the aim for the unlearned model is to be indistinguishable from a model that was trained on *any* subset of the training data excluding the forget set (rather than a model specifically trained on exactly the retain set), and where indistinguishability here is with respect to the “internal state” required by the model (e.g. any data that must be stored, any intermediate checkpoints that are required, the unlearned model for that request, or the ingredients required to produce it). The idea is that this definition enables the model developer to control what information is placed in the “internal state” (and that consequently an “attacker” would have access to). One could then design systems that support system-aware unlearning by requiring less information to be stored in the first place. \nThe authors then discuss core set algorithms, and how they facilitate connections between the standard definition of unlearning and system-aware unlearning. Namely, running a standard unlearning algorithm on a coreset S’ of the original dataset S enables system-aware unlearning (assuming only the coreset needs to be stored and not S itself) where for a large number of examples (those not in S’) unlearning is a no-op.\n\nThe authors propose an exact learning / unlearning algorithm for linear classification that uses a particular selective sampling strategy called BBQSampler from prior work to effectively get a coreset. Then, to handle a deletion, interventions are only required if the examples to be deleted is part of the “coreset”, i.e. a set of “queried” examples. These interventions required to unlearn a point are efficient in terms of computing the “new coreset” due to a monotonicity property. They prove bounds on deletion capacity, memory requirements, computation time.\n\n\n########## update after the rebuttal\n\nThe authors have clarified several concerns of mine through extensive discussions (see thread below) and I'm confident that reflecting these discussions in the updated manuscript will improve the paper (I read the latest response, too, and while I didn't have time to reply to it directly earlier, I note here that the clarification w.r.t how the divergences are computed is helpful, thanks again). I maintain my recommendation of weak accept. The reason I don't recommend acceptance more strongly is due to the limitation of being applicable only to linear classifiers. I also agree with other reviewers that adding/strengthening the existing empirical investigation would also lead to a stronger contribution even though I understand the nature of the contribution here is theoretical.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> CE 1\n\nWe acknowledge that there are empirical unlearning algorithms that have demonstrated good performance on nonconvex models; however, recent work [1] has demonstrated that many such empirical methods fail to properly unlearn; thus, we focus on algorithms that meet theoretical guarantees of certified unlearning.\n\n> CE 2, CE 3\n\nOur definition (Definition 2.3) requires that for any S, there exists S’ such that *for any U*, $\\textsf{I}_A(S, U)$ is indistinguishable from $\\textsf{I}_A(S’ \\setminus U, \\emptyset)$. The order of the quantifiers ensures that S’ is chosen before U is selected, and thus the data selection mechanism is independent of U. Thus, S’ \\ U can not reveal additional information about U than S \\ U.\n\n> CE 4\n\nWe remark that this is not a technical assumption used in any of our results. We only mention this to help interpret our results. Indeed, the mutual information (MI) between U and S ∖ U does not need to be small. However, such an assumption is implicitly necessary when considering unlearning for privacy purposes. One can easily construct scenarios where the MI between U and S ∖ U is large; thus, even retraining from scratch (the gold standard) may not preserve the privacy of deleted individuals U (as S \\ U reveals U). Unlearning definitions that compete with retaining-from-scratch only provide meaningful privacy for the deleted individuals when the MI between U and S ∖ U is small. To motivate our definition, we show that the MI between U and S’ ∖ U never exceeds the MI between U and S ∖ U (Theorem 2.4).\n\n> CE 5\n\nThe probabilities are over the outcome space of all possible system-states (model weights, saved gradients, stored samples, etc).\n\n> CE 6\n\nWe thank the reviewer for this reference. We note that perfect unlearning is equivalent to system-aware unlearning when S=S’. We will add this reference.\n\n> ERND 1\n\nUnlearning definitions do not guarantee privacy against adversaries with continuous model observations. One could incorporate the intermediate checkpoints of the model into the state-of-system definition, resulting in a system-aware unlearning definition that would be robust to such adversaries. For Algorithm 1 specifically, since the core set is stored in memory, observing the system state before unlearning will reveal the deleted individuals in the core set. However, we can always provide privacy guarantees for individuals outside of the core set against such adversaries because they are never stored in the system at any point.\n\n> ERND 2\n\nWe thank the reviewer for this reference. We agree that the similarity of the “existence of a certificate of forgetting” is interesting and will be sure to cite Golatkar et al. However, it is important to note that the unlearning algorithm in Golatkar et al. (OQSA) uses a certificate that computes the learning algorithm trained on S \\ U, equivalent to traditional unlearning. Golatkar et al. did not capitalize on the flexibility of such a certificate. Our Algorithm 1 leverages the flexibility in S’ for more efficient unlearning.\n\n> OSAW W1\n\nSystem-aware unlearning is most useful when an accurate model can be learned with a small number of samples, such as models with small eluder dimension or disagreement coefficient [2].\n\n> OSAW W2\n\nEven under the traditional unlearning definition, it is still unclear how to perform theoretically rigorous and efficient unlearning in simple models like regression. We hope to extend our framework to more complex models, but this seems to be a significant challenge in traditional and system-aware unlearning.\n\n> OSAW W3\n\nThis model of deletions can capture correlated deletions. For example, the deletion distribution may be such that users sharing certain characteristics have a higher probability of deletion than other users. We do assume that the deletion requests are not adaptive to system updates.\n\n> QFA 1\n\nTheorem 2.4 states that the information leakage between U and S’ ∖ U never exceeds the information between U and S ∖ U. This gives a relative information leakage guarantee that system-aware unlearning leaks no more information about the deleted individuals than traditional unlearning.\n\n> QFA 2\n\nSo far, we do not know of any practical unlearning algorithms that can do approximate unlearning without storing the entire dataset in memory. In fact, [3] already shows a lower bound that even approximate unlearning (in the traditional definition) needs to store the entire dataset (while they focus on the realizability testing problem, we strongly suspect that their result can be extended to unlearning). \n\nWe will clarify these discussions in the final paper. Please let us know if you have further questions.\n\n[1] Machine Unlearning Fails to Remove Data Poisoning Attacks. Pawelczyk et al. ICLR 2025.\n\n[2] Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective. Foster et al. COLT 2021.\n\n[3] On the unlearnability of the learnable. Cherapanamjeri et al. 2025.", "claims_and_evidence": "- “a dire lack of efficient exact or approximate unlearning algorithms beyond the simple\ncase of convex loss functions” – while indeed there is a dire lack of certified unlearning algorithms for nonconvex models that are well performing, there are various (uncertified) ones that are efficient, and there is work on empirically auditing them, see e.g. Hayes et al. in the references below.\n\n- “only the privacy of the stored points are at jeopardy as long as the learnt model does not reveal much about points that were not used by the model” – this doesn’t seem to be true in general, since not all data selection mechanisms preserve privacy. Even if only a subset of the training dataset is accessible, this may leak privacy about other training data points (that were used, for instance, for selecting which subset to store).\n\n- “Even if an observer or attacker has access to larger public data sets that might include parts of the data the system was trained on, in such a system, we could expect privacy for data that the system does not use directly for building the model to be preserved.” – similarly here, why is this the case? In general, an example can influence the final computation even if it isn’t “directly” used for training. And this influence can translate to privacy vulnerability in general, right?\n\n- “Traditional unlearning definitions that require the unlearned hypothesis to approximately match A(S ∖ U, ∅) implicitly assume that the information between the deleted individuals U and the remaining dataset S ∖ U is small.” I don’t understand why the authors claim that this assumption is needed. The traditional DP-like unlearning definitions are about measuring the difference between the allowed knowledge one would have on U even if having trained just on S ∖ U compared to the *additional* knowledge about U that stems from having trained on U (and not perfectly removed its influence).  But this doesn’t require that the MI between U and S ∖ U is small?\n\n- In the definition of system-aware unlearning, how should I interpret the probability Pr(IA(S, U ) ∈ F )? In the standard definition, the probabilities are over the output of running either the “retraining” or the “unlearning” recipe and in either case, that output is a set of model weights. When we replace this with the  “state of the system” (which can contain a variety of things like model checkpoints, but also data points, etc), it’s less clear to me how to interpret this probability distribution, or what this divergence exactly means in this case.\n\n- “We point out that the traditional definition of unlearning does not require indistinguishability for auxiliary information stored in the system outside of the unlearned model; thus, the traditional definition does not account for system-awarenes” – I agree in general, but see the distinction introduced in Neel et al. about “perfect unlearning” relating to whether a secret state (that the attacker can’t access) can be kept or not which is relevant to discuss here.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I did not check the proofs in the Appendix, but followed the proof sketches in the main paper.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "See below section.", "essential_references_not_discussed": "- “When machine unlearning jeopardizes privacy” (see references below) shows that, with access to intermediate checkpoints of the model (what can be considered as being part of an “internal state” here), an attacker can even succeed against exact unlearning! This would be interesting to incorporate in the discussion of this paper (since it also relates to the relationship between auxiliary information that the attacker can access vis-a-vis privacy claims or guarantees; even in the case of “exact unlearning”). \n\n- Definition 1 in Golatkar et al. (see references below) has a similar flavour of requiring the “existence of a certificate” such that closeness to that verifies an algorithm as successful unlearning (rather than a fixed recipe as a certificate). This is reminiscent of the “there exists an S’ …” modification in the proposed definition. There are various differences between that definition and the one proposed here, but this similarity is interesting to acknowledge.\n\n\nReferences\n==========\n\n- Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy. Hayes et al. SatML 2025.\n\n- Descent-to-Delete: Gradient-Based Methods for Machine Unlearning. Neel et al. 2020.\n\n- When machine unlearning jeopardizes privacy. Chen et al. ACM SIGSAC 2021.\n\n- Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks. Golatkar et al. CVPR 2020.", "other_strengths_and_weaknesses": "Strengths\n\n- The paper is thought-provoking, proposes an interesting alternative definition of unlearning.\n\n- The authors propose an efficient algorithm for unlearning in linear classification that they prove satisfies exact system-aware unlearning. They prove bounds for how many unlearning requests their algorithm can handle without too big a drop in performance (deletion capacity), memory requirements and amount of computation required.\n\n- The paper is for the most part well-written, giving intuition behind various theoretical results that makes it easier to follow. \n\n\nWeaknesses\n\n- It’s unclear to me when is system aware unlearning useful in practice, what application is it most appropriate for? I have concerns (discussed above) about its privacy protection, but maybe the authors can convince me otherwise in the rebuttal. For example, for the compression, if we use all of S as input to a “compression function” that outputs a representative subset S’ on top of which we do further processing, it does not mean that only S’ influenced the final model. S influenced the final model here too and that influence depends on the compression function and whether it is privacy preserving. \n\n- The proposed algorithm is only applicable to linear classification. Can it be extended to neural networks?\n\n- “Assume that deletions are drawn without replacement [...]” – often not a realistic assumption as in practice unlearning requests may be correlated (e.g. groups of users that are unhappy with the model and share various characteristics with each other, would be more likely to request data deletion).", "other_comments_or_suggestions": "Minor:\n\n- Line 196 (right column): “S′ ∖ U should leak any more information about U as compared to S ∖U” – I think the authors here mean “should *not* leak any more information [...]”.\n\n- Initially, e.g. in Definition 2.1, the authors use A to denote a learning algorithm and \\bar A to denote an unlearning algorithm. But later, in various places, A denotes the unlearning algorithm (and A(S,U) the unlearned model). This discrepancy in notation can cause confusion.\n\n- Many new symbols introduced in Algorithm 1, it would be helpful to describe them intuitively. \n\n- In Theorem 4.2, define A (also, the symbol A is overloaded – elsewhere in the paper it denotes a learning or unlearning algorithm, here it appears to be some matrix).", "questions_for_authors": "- “Thus, S′ ∖ U leaks no more information about U than S ∖ U” – what exactly is the privacy guarantee that this implies? Can you help me understand how this statement translates to a privacy guarantee for U which is what subsection 2.1 is trying to argue I think?\n\n- “under traditional unlearning, exact unlearning requires storing the entirety of the dataset” – can’t we be satisfied though with approximate unlearning that stores a random (or not random) subset of the dataset? I don’t quite see why this is impossible under traditional unlearning and we must resort to system aware unlearning here. (I can see it being impossible under *exact* traditional unlearning, but approximate might be okay in practice). What is the benefit of applying a corset algorithm and viewing it as exact system-aware unlearning as opposed to approximate “standard” unlearning?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "syDyxeuPeI", "reviewer": "Reviewer_C9YU", "summary": "The authors propose system-aware machine unlearning, which constitutes unlearning against an attacker who can observe the entire state of the system (including whatever the learning system uses internally). If the system does store the entire remaining dataset, then system-aware unlearning definition becomes as stringent as traditional unlearning, but otherwise is a relaxation constrained only for the data stored by the system. The paper only provides theoretical insights about the proposed system-aware machine unlearning setting.\n\n___\n\n## update after rebuttal\n\nI would like to thank the authors for their response. However, my fundamental concerns still remain -- despite the claim that the work aims to make theoretical contributions in defining system-aware unlearning for linear classifiers, I believe an empirical validation is necessary given that unlearning is a practical problem and existing baselines can be adapted to the system-aware definition. There are also issues in the current version regarding inconsistent phrasing/statements of non-convexity (which the authors mentioned they will rewrite) and the fact that SISA outperforms their method for a significant duration of the deletion phase. While there are minimalistic experiments in the paper, I will keep my score largely given the non-existent evaluation against relevant baselines.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> CE 2 - *To fully verify the claims being made (as unlearning is a task with practical real-world ...*\n\n> MAEC 1 - *There is very limited (and almost non-existent) evaluation...*\n\nWe emphasize that our primary contribution is theoretical. We focus on unlearning algorithms with provable unlearning guarantees. Recent work [1, 2] has demonstrated that many empirical methods fail to properly unlearn. This shows a dire need for algorithms that provide theoretical guarantees of unlearning; thus, we focus on specifically unlearning algorithms that meet theoretical guarantees of certified unlearning. Our paper is a theoretical paper with a focus on developing a new definition for unlearning that is not as pessimistic as the traditional unlearning definition but is still principled. We provably demonstrate that system-aware unlearning algorithms for linear classification are more memory and computation efficient than traditional unlearning algorithms.\n\n> CE 3 - *Given the authors' statement in the Introduction (line 50, right hand column): \"For large ...*\n\nIn this work, we demonstrate that for linear classification, system-aware unlearning leads to algorithms that are provably more efficient. Furthermore, even under the traditional unlearning definition, it is still unclear how to perform theoretically rigorous and efficient unlearning in simple models like regression. Although the exact methods may not translate directly, the flexibility of system-aware unlearning could also lead to significantly more efficient algorithms for more complex model classes. An empirical evaluation of unlearning with larger models and datasets is beyond the scope of this work, as we focus on system-aware unlearning and exact unlearning algorithms for linear classification with rigorous theoretical guarantees.\n\n> CE 4 - *The authors state in the Introduction (line 43, right hand column): \"This is evidenced by ...*\n\nSISA requires the storage of many intermediate models and the entirety of the dataset to facilitate unlearning, which is extremely memory inefficient. We wanted to draw attention to the memory and computation inefficiencies of current unlearning algorithms, particularly those for nonconvex function classes. We will rewrite this statement for clarity.\n\n> ERND 1 - *There are many references that are missing; primarily because the paper is lacking a ...*\n\nIn the final version, we will move the Related Works section to the main text and expand the references and discussions.\n\nPlease let us know if you have any additional questions or concerns.\n\n[1] Machine Unlearning Fails to Remove Data Poisoning Attacks. Martin Pawelczyk, Jimmy Z. Di, Yiwei Lu, Gautam Kamath, Ayush Sekhari, Seth Neel. ICLR 2025.\n\n[2] Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy. Jamie Hayes, Ilia Shumailov, Eleni Triantafillou, Amr Khalifa, Nicolas Papernot. SatML 2025.", "claims_and_evidence": "- Under the definitions/assumptions made by the authors in Section 2 for linear classification, the theoretical claims are well justified. But the overall motivation of this work and the claims in the context of existing work in the machine unlearning domain are unclear, significantly limiting its usefulness.\n- To fully verify the claims being made (as unlearning is a task with practical real-world use-cases), the paper needs extensive evaluation against existing methods and approaches for unlearning. Machine unlearning methods need to be evaluated using both the unlearning efficiency and the utility of the model post unlearning across a number of existing methods. Currently, the few experimental results present are deferred to the appendix and only consider the SISA approach and exact retraining (both over 4 years old). Moreover, SISA seems to perform better than the proposed algorithm for a significant duration of the deletion phase. The paper is basically lacking a Results and Experimental Evaluation section currently.\n- Given the authors' statement in the Introduction (line 50, right hand column): _\"For large datasets, this makes unlearning under\nthe traditional definitions impractical\"_. Yet, there exist approximate methods that work with large datasets and a large number of parameters (e.g. LLMs) that work well while working in the limited data access regime (e.g. [1,2]). The paper focuses on linear classifiers limiting its applicability to models that actually require a very large number of data samples. It would also be good to compare empirically with more recent approximate existing methods along the aforementioned metrics (authors can refer to [3] for more details) and on large datasets. Without these necessary experiments and analyses, the proposed method cannot be fully evaluated from an empirical perspective.\n- The authors state in the Introduction (line 43, right hand column): _\"This is evidenced by a dire lack of efficient exact or approximate unlearning algorithms beyond the simple case of convex loss functions.\"_ I am not sure if this claim is correct. Is the SISA method the authors compare with itself not designed for non-convex losses? And given the large amount of approximate approaches [1-2,4-5] that work with LLMs and deep neural networks (inherently non-convex), I believe the authors need to rewrite this statement to reflect a correct and nuanced perspective. \n\nReferences:\n1. Huang, James Y., et al. \"Offset unlearning for large language models.\" arXiv preprint arXiv:2404.11045 (2024).\n2. Ji, Jiabao, et al. \"Reversing the forget-retain objectives: An efficient llm unlearning framework from logit difference.\" NeurIPS (2024).\n3. Wang, Weiqi, et al. \"Machine unlearning: A comprehensive survey.\" arXiv preprint arXiv:2405.07406 (2024).\n4. Liu, Sijia, et al. \"Rethinking machine unlearning for large language models.\" Nature Machine Intelligence (2025): 1-14.\n5. Liu, Zheyuan, et al. \"Machine unlearning in generative ai: A survey.\" arXiv preprint arXiv:2407.20516 (2024).", "methods_and_evaluation_criteria": "There is very limited (and almost non-existent) evaluation. Please see above (Claims and Evidence) for more issues regarding the claims made in the context of methods and evaluation criteria. At the moment, there are very few experimental results that are present in the appendix and only consider the SISA approach and exact retraining (both over 4 years old). Moreover, SISA seems to perform better than the proposed algorithm for a significant duration of the deletion phase. The paper needs an extensive Evaluation section for a clear evaluation.", "theoretical_claims": "Yes, from a cursory verification of the theoretical proofs, I did not find any errors.", "experimental_designs_or_analyses": "As mentioned in the Methods And Evaluation Criteria section, there is very limited (and almost non-existent) evaluation. Please see above (Claims and Evidence) for more issues regarding the claims made in the context of methods and experiments. At the moment, there are very few experimental results that are present in the appendix and only consider the SISA approach and exact retraining (both over 4 years old). Moreover, SISA seems to perform better than the proposed algorithm for a significant duration of the deletion phase. The paper needs an extensive Evaluation section for a clear evaluation.", "relation_to_broader_scientific_literature": "The paper can be of interest to the machine unlearning community. However, the limited evaluation limits its effectiveness and scope, and could lead to a reduced impact in the field.", "essential_references_not_discussed": "There are many references that are missing; primarily because the paper is lacking a Related Works section in the main text. There is some discussion of related papers in the appendix, but these need to be moved to the main paper and more works should be discussed. This is not an exhaustive list, but some references (as mentioned in above sections), include:\n\n1. Huang, James Y., et al. \"Offset unlearning for large language models.\" arXiv preprint arXiv:2404.11045 (2024).\n2. Ji, Jiabao, et al. \"Reversing the forget-retain objectives: An efficient llm unlearning framework from logit difference.\" NeurIPS (2024).\n3. Wang, Weiqi, et al. \"Machine unlearning: A comprehensive survey.\" arXiv preprint arXiv:2405.07406 (2024).\n4. Liu, Sijia, et al. \"Rethinking machine unlearning for large language models.\" Nature Machine Intelligence (2025): 1-14.\n5. Liu, Zheyuan, et al. \"Machine unlearning in generative ai: A survey.\" arXiv preprint arXiv:2407.20516 (2024).", "other_strengths_and_weaknesses": "While the ideas in this paper have merit, the limited evaluation makes the work somewhat incomplete. For more details, please see the Methods And Evaluation Criteria and Claims and Evidence sections above.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "Please see the Methods And Evaluation Criteria and Claims and Evidence sections above. Each of the points can be considered as questions and points of concern.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gPTCYsO665", "reviewer": "Reviewer_BX2n", "summary": "This paper introduces a system-aware unlearning framework, which is a new definition of machine unlearning that relaxes the unlearning definition by assuming a weaker attacker that has no access to the full training data, i.e., the definition only requires the unlearned model to be indistinguishable from a model trained on a subset of the data (\"core set\" called in the paper).\n\nThe paper mainly focuses on linear classification, and the proposed method employs the selective sampling algorithm BBQSampler to select the core set from the training data to conduct unlearning.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> CE 1 - *The claims in the paper are not convincing to me. The paper claims that the new definition ...*\n\nThe authors disagree with the claim that data-free machine unlearning methods would provide more privacy protection than the proposed method. Data-free machine unlearning methods still attempt to recover a model approximately equivalent to retraining a model from scratch on the remaining dataset S \\ U, which is the traditional definition of unlearning. Furthermore, [1, 2, 3, 4] do not provide any rigorous guarantee that such an unlearning goal is actually being achieved. In fact, [5] has shown that SSD [1] fails to properly unlearn. Recent work [5, 6] has highlighted that many empirical methods for unlearning fail to properly unlearn and do indeed leak information about deleted individuals. This shows a dire need for algorithms that meet theoretical guarantees of unlearning. \n\nAdditionally, we present a new definition of unlearning, system-aware unlearning, which provides privacy guarantees that are provably stronger than traditional unlearning. Then, we provide an algorithm that provably satisfies system-aware unlearning, and we provably demonstrate that system-aware unlearning algorithms for linear classification are more memory and computation efficient than traditional unlearning algorithms.\n\n> MAEC 1 - *The proposed method using partial training data for unlearning makes sense, but the ...*\n\nThe method in our paper does not only have access to partial training data. The system-aware algorithm initially has access to the entire dataset and then uses selective sampling to select the most important points to form a core set in order to facilitate faster and more efficient unlearning in the future. \n\nFurthermore, it is important to note that the core set is computed once during the initial learning phase and fixed before any deletion requests arrive and then never computed again. As various deletion requests arrive, Algorithm 1 performs an unlearning update and does not recompute a new core set for every new set of requests. This method is provably more efficient than traditional unlearning algorithms.\n\n> EDOA 1 - *The paper mainly focuses on linear classification. However, current machine unlearning ...*\n\nEven under the traditional unlearning definition, it is still unclear how to perform theoretically rigorous and efficient unlearning in simple models like regression. We focus on algorithms with theoretically rigorous unlearning guarantees.\n\n> QFA 1 - *In Theorem 2.4, does $S \\setminus U = ((S’ \\setminus U), ((S \\setminus S’) \\setminus U))$ mean $S \\ U =(S’ \\setminus U) \\cap ((S \\setminus S’) \\setminus U))$?*\n\nIn Theorem 2.4, we treat $S \\setminus U$ as a vector that can be tensorized into two parts, $((S’ \\setminus U), ((S \\setminus S’) \\setminus U))$, so that we can apply the chain rule of mutual information. We will clarify this in the final version of the paper.\n\n> QFA 2 - *What does \"measurable sets F\" mean in Definition 2.3?*\n\n$\\mathcal{F}$ is the $\\sigma$-algebra over the outcome space of possible system-states. Measurable sets $F$ can be thought of as all possible events (subsets of outcomes) over the $\\sigma$-algebra $\\mathcal{F}$. We note that this notation is standard for all indistinguishability-style definitions.\n\nPlease let us know if you have any additional questions or concerns.\n\n[1] Foster, J., Schoepf, S., and Brintrup, A. Fast machine unlearning without retraining through selective synaptic dampening. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 12043–12051, 2024.\n\n[2] Tarun, A. K., Chundawat, V. S., Mandal, M., and Kankanhalli, M. Fast yet effective machine unlearning. IEEE Transactions on Neural Networks and Learning Systems, pp. 1–10, 2023.\n\n[3] Bonato, J., Cotogni, M., and Sabetta, L. Is retain set all you need in machine unlearning? restoring performance of unlearned models with out-of-distribution images. In European Conference on Computer Vision, pp. 1–19. Springer, 2025.\n\n[4] Chundawat, V. S., Tarun, A. K., Mandal, M., and Kankanhalli, M. Zero-shot machine unlearning. IEEE Transactions on Information Forensics and Security, pp. 2345– 2354, 2023b.\n\n[5] Machine Unlearning Fails to Remove Data Poisoning Attacks. Martin Pawelczyk, Jimmy Z. Di, Yiwei Lu, Gautam Kamath, Ayush Sekhari, Seth Neel. ICLR 2025.\n\n[6] Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy. Jamie Hayes, Ilia Shumailov, Eleni Triantafillou, Amr Khalifa, Nicolas Papernot. SatML 2025.", "claims_and_evidence": "The claims in the paper are not convincing to me.\n\nThe paper claims that the new definition provides privacy guarantees by ensuring that the unlearned model using the core set reveals no more information than the traditional unlearned model. However, privacy leakage does not happen due to the definition of unlearning, it could arise from the networks or algorithms themselves, such as model inversion attacks. Moreover, with the traditional definition, data-free machine unlearning methods [1-4] were proposed and would provide more protection than the proposed method using partial data.\n\n[1] Foster, J., Schoepf, S., and Brintrup, A. Fast machine unlearning without retraining through selective synaptic dampening. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 12043–12051, 2024.\n\n[2] Tarun, A. K., Chundawat, V. S., Mandal, M., and Kankanhalli, M. Fast yet effective machine unlearning. IEEE Transactions on Neural Networks and Learning Systems, pp. 1–10, 2023.\n\n[3] Bonato, J., Cotogni, M., and Sabetta, L. Is retain set all you need in machine unlearning? restoring performance of unlearned models with out-of-distribution images. In European Conference on Computer Vision, pp. 1–19. Springer, 2025.\n\n[4] Chundawat, V. S., Tarun, A. K., Mandal, M., and Kankanhalli, M. Zero-shot machine unlearning. IEEE Transactions on Information Forensics and Security, pp. 2345– 2354, 2023b.", "methods_and_evaluation_criteria": "The proposed method using partial training data for unlearning makes sense, but the authors are encouraged to investigate relevant works, such as data-free methods [1-4], for better understanding the development of machine unlearning methods.\nTo me, the paper just proposes a method with only access to partial training data, and use selective sampling algorithm to identify the core set. If the paper only focus on exact unlearning with partial training data, what is the advantage of the proposed method to approximate (data-free) unlearning methods? For different deletion requests, the proposed method need to find a core set for the requests, which is impractical in the end.", "theoretical_claims": "I only checked those till Section 4. Please see Claims And Evidence*.", "experimental_designs_or_analyses": "The paper mainly focuses on linear classification. However, current machine unlearning methods mostly examine with deep neural networks such as ResNet, ViT and even large-scale vision-language model CLIP [1-5].\n\n[5] Poppi, Samuele, et al. \"Safe-CLIP: Removing NSFW concepts from vision-and-language models.\" European Conference on Computer Vision. Cham: Springer Nature Switzerland, 2024.", "relation_to_broader_scientific_literature": "The key contribution of this paper is to use the selective sampling algorithm BBQSampler to select the core set from the training data to conduct unlearning for linear classification.", "essential_references_not_discussed": "[1-4], for instance. The authors are encouraged to investigate and check recent machine unlearning papers.", "other_strengths_and_weaknesses": "The core idea of using sample compression for unlearning is interesting but is restricted to linear classification. The argument that it enhances privacy is not convincing (See above).", "other_comments_or_suggestions": "Please see the above sections.", "questions_for_authors": "- In Theorem 2.4, does $S \\setminus U=( (S^{'} \\setminus U), ( (S \\setminus S^{'}) \\setminus U ) )$ mean $S \\setminus U=(S^{'} \\setminus U) \\cup ( (S \\setminus S^{'}) \\setminus U ) $?\n\n- What does \"measurable sets F\" mean in Definition 2.3?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a new machine unlearning framework that accounts for realistic attacker access to the system’s internal data. The paper develops an exact learning/unlearning algorithm for linear classification based on coreset construction. It provides theoretical analysis in terms of bounds on deletion capacity, memory requirements, and computation time.

The reviewers appreciate the following strengths: 1) Proposes a new and interesting generalization of the machine unlearning definition that accounts for realistic attacker access to the system’s internal data;
2) Establishes a series of theoretical results in terms of bounds on deletion capacity, memory requirements, and computation time;
3) Mostly well-written, with intuitive explanations that make it easier to follow.

The reviewers also raise several concerns:
1) Mostly limited to simple models such as linear/convex models;
2) Lacks empirical validation;
3) Misses some related work;
4) Provides insufficient discussion about the practicality and assumptions of the new unlearning definition.

During the discussion, the authors provide detailed feedback and addressed most of the concerns. Three of the reviewers give an overall positive evaluation, while two reviewers still lean towards negative. The remaining concern mainly lies in the lack of empirical results. The area chair aligns with the majority of the reviewers and believes that this paper makes novel and interesting theoretical contributions. Regarded as a pure theoretical paper, and in light of its theoretical merits, the area chair recommends weak acceptance, with the final decision left to the SAC and PCs.
Decision: Accept (poster)