System Aware Unlearning Algorithms: Use Lesser, Forget Faster

We thank the reviewer for their thoughtful feedback. We have addressed writing concerns. We have uploaded an updated paper pdf which incorporates their feedback, and we address their comments below.

The necessity of "system aware unlearning" is not well justified…

There already exist learning algorithms that by design, only rely on a small fraction of the training dataset in order to generate a hypothesis, such as selective sampling algorithms [1], which are discussed in detail in Section 4. For another concrete example, consider a hard margin SVM: only the training points on the margin dictate the decision boundary. Most of the points are not on the margin and do not affect the decision boundary. If a non-margin point is deleted, the decision boundary and hypothesis remain unchanged. Furthermore, the algorithms in the paper demonstrate that when only a small fraction of the training data is used to generate a hypothesis, we can unlearn faster and use less memory. The goal of efficient unlearning motivates the choice of relying on fewer data points. On the information leakage question, it can be shown that Given the state of the system $\textsf{I}(S, U)$, the conditional mutual information between $U$ and $A(S, U)$ is 0. We have added this discussion to the paper in Section 2 in lines 171-183.

The paper claims, " Even if an observer/attacker has access to larger public data sets…

While making this claim, we do not assume that the entire training dataset is exposed to the attackers. We simply claim that the part of the dataset that is not used in training the model, and additionally not exposed to the adversary by other methods, enjoys privacy even if the final state of the system (which again does not contain these samples that were not used in training) is exposed to the attacker. We are happy to clarify further if something is still confusing.

When the system is compromised, we assume that the attacker only gains knowledge of the points in the core set of the model. Now suppose that the attacker had access to some auxiliary dataset of data points, some of which could have appeared in the sample but outside of the core set. The attacker cannot identify which of these points actually appeared in the sample because the output of the model is exactly the same whether or not one of these points actually appeared in the sample of not, since points outside of the core set have no effect on the model. Thus, we maintain privacy with respect to membership in the sample even in the presence of auxiliary information.

The conclusion that models would "not be statistically indistinguishable from each other"…

In the motivating example on page 3, the model owner only uses a small subset $C$ of $S$ and does not use the complete training dataset $S$. The motivating example is specific to the case where the model and system only use a small fraction of the training dataset $S$.

Using only one shard's core set for prediction would likely cause…

Although Algorithm 1 incurs an initial accuracy tradeoff before deletion, as the number of deletions increases, Algorithm 1 is able to maintain much better accuracy compared to algorithms like SISA from [2] under deletion sequences which are label dependent and cause a large distribution shift.

The paper lacks an Evaluation section. Machine unlearning algorithms should be assessed across multiple dimensions…

Our primary contribution is theoretical; we prove theoretical guarantees on model accuracy after unlearning, memory requirements, and computation time. We prove that under the assumption of a weaker adversary, we can design significantly improved memory and computationally efficient exact unlearning algorithms. Exact unlearning algorithms under the previous definition of unlearning all involve some level of retraining from scratch for each deletion and storing the entirety of the dataset, which is expensive and inefficient in memory and time. Under our new definition, we can avoid this retraining; we can design algorithms that provably beat the time to retrain and provably require significantly less memory than the entirety of the dataset, so the comparison and improvement are straightforward. In Appendix A.1, we provide some simple experiments for the linear case to validate our theoretical results. In the final version of the paper, we will bring the experiments to the main body.

The paper lacks a Related Work section.

We discuss related unlearning definitions in Section 2, and we provide a discussion of other related work in unlearning in Appendix A.2. In the final version of the paper, we will bring the discussion of other related work to the main body.

[1] https://arxiv.org/pdf/2307.04998

[2] https://arxiv.org/abs/1912.03817

Why is Algorithm 2 not a valid unlearning algorithm under the prior unlearning definition (Definition 1)?…

Running Algorithm 2 on $S\setminus U$ is not identical to running on $S$ and then removing $U$, and this exactly motivates the reasoning behind this paper and the new definition. Algorithm 2 does not satisfy Definition 1 (prior definition of unlearning), but it still unlearns $U$. The output of Algorithm 2 after running on $S$ and then unlearning $U$ is identical to running Algorithm 2 on $\mathfrak{C}(S)\setminus U$, where $\mathfrak{C}(S)$ is the core set of $S$; this is not equivalent to running Algorithm 2 on $S\setminus U$, since C(S\setminus U) is not equal to $\mathfrak{C}(S \setminus U) \neq \mathfrak{C}(S)\setminus U$. There are points that would have appeared in $\mathfrak{C}(S \setminus U)$and contributed to the outcome of the algorithm that never appeared in the original core set $\mathfrak{C}(S)$. Thus, Algorithm 2 is not a valid unlearning algorithm under Definition 1 (the prior definition of unlearning).

Can you comment on the similarities between Algorithm 1 and SISA [1]?

We provide a detailed comparison between SISA from Bourtoule et al. [3] and Algorithm 1 in Section A of our response to Reviewer sthQ.

[3] https://arxiv.org/abs/1912.03817

We thank the reviewer for their thoughtful feedback. We have addressed writing concerns and typos. We have uploaded an updated paper pdf which incorporates their feedback, and we address their comments below.

“It’s still an open problem how these pieces of legislation”

We acknowledge that the laws are not yet fully formalized, and the field presents ample opportunity for both interpreting and aiding in the formalization of these laws.

“This is evidenced by a dire lack of exact/approximate unlearning algorithms beyond…

Precisely, we mean that there is a dire lack of memory and computationally efficient unlearning algorithms for general model classes. We will clarify this in line 211 of the updated paper pdf.

Our framework leverages the fact that many ML systems do not depend…

Consider selective sampling algorithms which have theoretical upper bounds on the number of points required to learn a good classifier [1]. In this case, only a small subset of points in the sample needs to be used to train the final classifier that still has good accuracy.

“We also provide an improved system-aware unlearning algorithm…

Under the traditional definition of unlearning, existing lower bounds prove that any exact unlearning for linear classification must store the entire dataset in memory. Under system aware unlearning, we show that using Algorithm 1 or Algorithm 2, we can achieve exact unlearning even when storing significantly less than the entire dataset. This shows that we can achieve more efficient unlearning algorithms under system aware unlearning, and this insight could be valuable in the development of unlearning algorithms in more challenging, nonconvex settings. Furthermore, Algorithm 1 works for non-convex function classes, and we have clarified this in the paper in line 211.

I thought that the motivating example in line 118…

The order of operations cannot be reversed. According to the previously proposed definition of unlearning, the model output after unlearning must match the counterfactual trained on $S\setminus U$. The counterfactual model can never gain access to $U$, or else you will be attempting to match a model output that can use the deleted individuals during learning, which leads to no privacy guarantees for the deleted individuals. Thus, the counterfactual model cannot select $C$ from $S$ and then remove $U$; it must select $C’$ from $S\setminus U$. On the other hand, the unlearned model must select $C$ from $S$ initially, and then remove $U$ later on, once the deletion request actually arrives.

For any S\U there exists an S' that is distributionally indistinguishable when trained. Does the existence of S’ imply we can find it efficiently?

Sample compression and selective sampling schemes have a clear selection rule allowing algorithm designers to easily identify which points in the sample have been used to train the final classifier. Beyond sample compression, data attribution techniques [2] can be used to identify which points in the sample influence the final model output.

In Definition 3, taking S’=S\U recovers the original definition…

Consider a classifier on $S$ such that the decision boundary is determined by some set of margin points. Now consider when some of those margin points are deleted, and the new decision boundary is decided by the remaining margin points. However, if one were to learn on $S\setminus U$, a completely different set of margin points would be chosen by the algorithm (since those original margin points never appeared) leading to a completely different classifier. The system-aware unlearning definition is not satisfied by selecting $S’=S\setminus U$, but it is satisfied by some other plausible $S’$. In the paper in lines 378-385, we have a concrete discussion about why $S’=S\setminus U$ is insufficient for the selective sampling case.

”Since the attacker can only gain access to what is used or stored by the model…

As mentioned in this statement, we worry about samples that were either (a) stored by the model (for whatever reason), or (b) were used in training the model. In our definition, the state of the system encapsulates any samples that were stored in the system or used during training. While we agree with the reviewer that the current popular deep learning pipelines do not explicitly store the samples, we wanted a definition that goes beyond the current deep learning settings and includes other possible scenarios such as decision trees, ensembles, nearest neighbors, etc (where storing the samples makes sense).

Some examples of algorithms that only rely on a small subset of the sample are sample compression-based algorithms and selective sampling and active learning methods; these schemes generalize beyond linear models [1].

[1] https://arxiv.org/pdf/2307.04998

[2] https://arxiv.org/pdf/2410.23232

We thank the reviewer for their thoughtful feedback. We have addressed writing concerns and typos. We have uploaded an updated paper pdf which incorporates their feedback, and we address their comments below.

Lack of quantitative comparisons with other methods (theoretically or empirically).

Exact unlearning algorithms under the previous definition of unlearning all involve some level of retraining from scratch for each deletion and storing the entirety of the dataset, which is expensive and inefficient in memory and time. Under our new definition, we can avoid this retraining; we can design algorithms that provably beat the time to retrain and provably require significantly less memory than the entirety of the dataset as long of effective core set algorithms exist. We indicate assumptions or natural conditions (like margin assumption) under which such core-set algorithms exist and so the comparison and improvement are straightforward. In the event no sample compression algorithm exists, our algorithm has the same complexity as existing exact unlearning algorithms. For an explicit comparison, we provide a detailed comparison between SISA from Bourtoule et al. [1] and Algorithm 1 in Section A of our response to Reviewer sthQ. Algorithm 2 is the first exact unlearning algorithm for linear classification that does not require the storage of the entire dataset so the comparison with previous algorithms is straightforward.

The writing of the intuition part in Section 2 is not clear enough. The reviewer is quite confused about the statements on lines 125-128.

The motivating example in lines 125-128 illustrates that there exist unlearning algorithms that satisfy system-aware unlearning but do not satisfy traditional definitions of unlearning. Consider an algorithm that selects a few important points to train a model on: if one of the original important points were deleted, then perhaps the algorithm would have selected a different point that it deemed “important” to include in the model instead. Previous definitions of unlearning require including that new important point which in turn requires access to the entire dataset. In our case, we can simply ignore that point under system aware unlearning. The example in lines 125-128 is the simplest example of this. A more concrete example is the selective sampling case discussed in depth in Section 4.

The author is confused about the “core set deletion capacity $K$” and the "$K$ shards" in Algorithm 1. Are the two $K$s the same parameter?

These two $K$s are the same parameter. The algorithm designer specifies the core set deletion capacity $K$ that they desire, and then Algorithm 1 divides the sample into $K$ shards accordingly, in order to ensure a core set deletion capacity of $K$.

Although this paper mainly focuses on the theoretical part, it would be better to include the experimental results in the main text.

Our primary contribution is the new definition of unlearning which accounts for the attacker’s knowledge. We prove that under the assumption of a weaker adversary, we can design exact unlearning algorithms that are significantly more memory and computationally efficient. In the final version of the paper, we will bring the experiments to the main body.

What is $e$ in $K/e$ on line 275?

The $e$ here refers to the mathematical constant, approximately 2.7182…

What are $\mathcal{T}_P$ and $\mathcal{T}_f$ on line 6 of Algorithm 2?

We have clarified the definition of these two terms in line 5 of Algorithm 2 in the updated paper pdf.

[1] https://arxiv.org/abs/1912.03817

We thank the reviewer for their thoughtful feedback. We have uploaded an updated paper pdf which incorporates their feedback, and we address their comments below.

A. Fundamental differences between this work (Algorithm 1) and SISA from Bourtoule et al. - differences in computational efficiency, memory requirements, model accuracy, etc.

SISA from Bourtoule et al. [4] uses sharding and the storage of intermediate models as a means of speeding up retraining from scratch. Algorithm 1 requires no retraining or computation at the time of deletion. Let $n$ be the size of the sample and let $K$ be the number of shards. In the worst case, SISA requires retraining on a sample of size $n/K$ after each deletion. Algorithm 1 processes each deletion in time $O(1)$; no recomputation or retraining needs to be done at the time of unlearning. Furthermore, SISA requires the storage of all $n$ samples. Let $\mathfrak{C}(n/K)$ be the number of samples in the core set of each shard. Algorithm 1 requires the storage of $K \cdot \mathfrak{C}(n/K) << n$ samples, where $\mathfrak{C}(n/K)$ can be exponentially smaller than $\mathfrak{C}(n/K)$ [1]. SISA requires the storage of $R \cdot K$ models where $R$ is the number of slices within each shard, while Algorithm 1 only requires the storage of $K$ models. As the size of the dataset increases, the memory savings from sample compression in Algorithm 1 become more advantageous over SISA. With regards to model accuracy, SISA provides no theoretical guarantees of accuracy after deletion. In particular, deletion sequences that depend on the label of a data point will quickly degrade the accuracy of SISA; however, Algorithm 1 is robust against such deletion sequences. In general, until the number of core set deletions exceeds $K$, Algorithm 1 is able to maintain model accuracy guarantees.

B. Can you analyze the proposed system-aware unlearning algorithms in the presence of adversaries with continuous observations of models?

Algorithm 1 is robust to adversaries with continuous observations of models because the models before and after deletion are trained on two independent sets of data, so an adversary that has observed the model before and after deletion would be unable to compute the difference and recover the deleted individual. A core set deletion under Algorithm 2 does leak information under an adversary with continuous model observations. Privacy can be preserved by adding appropriately calibrated noise to the model output after unlearning a core set point [2], which is computationally inexpensive. Note that noise only needs to be added for core set deletions; for traditional unlearning algorithms, noise needs to be added after every deletion.

C. What are the limitations of the proposed method? Which threats remain unaddressed, and which types of algorithms are incompatible with this approach?

The primary unaddressed threat is when the attacker has access to the trace of the system over time over the course of learning (rather than simply the state of the system after unlearning). In this case, system-aware unlearning fails; however, it is unclear how an attacker would gain access to this trace if it is not stored by the system (or compromised otherwise). Algorithms that can learn well with a small number of points are most compatible with this approach, such as selective sampling and sample compression algorithms which have theoretical upper bounds on the number of points required to learn a good classifier [1]. However, we can expand this framework beyond sample compression algorithms: after training on the full sample, one can use influence functions or data attribution [3] to identify points that have a small influence on the model, remove these points, and train a model on the smaller set of impactful points. This gives a more general approach to system-aware unlearning. Furthermore, unlearning algorithms under previously proposed definitions continue to be valid under system-aware unlearning, and system-aware unlearning allows for a new class of algorithms (ie. sample compression algorithms) to be easily compatible with unlearning.

[1] https://arxiv.org/abs/2307.04998

[2] https://arxiv.org/pdf/2106.04378

[3] https://arxiv.org/pdf/2410.23232

[4] https://arxiv.org/abs/1912.03817