What makes unlearning hard and what to do about it

Re: “leave-one-out experiments” and “did you use any approximation?”. Let us clarify the setup. While the reviewer is correct that Feldman's definition of memorisation implies a 'leave-one-out' training, in practice this evaluation is prohibitively expensive, as pointed out. As a more efficient empirical approximation, (Feldman and Zhang, 2020 “What neural networks memorize and why: discovering the long tail via influence estimation”) suggests performing 'leave-k-out' training and repeating it many times (e.g. 4k times). This way, for each data point, one can find a sufficiently large number of models that include that point in the training and a sufficiently large number of models that don’t (in the pool of 4k models). In Feldman's experiments, k is 30% of the training dataset size. We have followed the same recipe to calculate the memorisation scores and our results agree with Feldman's findings. Thank you for pointing this out. We will add these clarifications to a section in the appendix for clarity (and refer to it from the main paper).

Further, in our new experiments in the rebuttal, we have considered using a proxy based on confidences that we find correlates well with memorization scores, leading to an efficient and practical recipe using RUM. Using this proxy is actually key as its computation requires orders of magnitude fewer models than Feldman’s memorization score, making our framework practical while still highly performant! Please see the “common response” for details. We hope that this line of experimentation and our thorough results also alleviate the concern of the reviewer that “the refinement step is also performed based on memorization scores” and “this process may be extremely expensive and may decrease the practicality of RUM”, since our findings using this cheap proxy align with those obtained using the true memorization scores.

Re: “how many epochs did you train? Can you show the computation cost”. We trained for 30 epochs for cifar10. For cifar100, we used the public memorization scores (computed by Feldman et al) and used the same model architecture (resnet50) as Feldman’s for the experiments. Please also see section A.2 in the appendix for additional details.

Re: MIA and ToW. The reviewer is correct that we could have repeated our analysis in Section 4 using MIAs, and accordingly we could have also based RUM’s selection of the unlearning algorithm per subset based on those findings. In our original experiments, we made the design decision of using ToW there due to its simplicity and compute-efficiency. We want to emphasize that, ultimately, we evaluate the algorithms we produce (RUM variants) using both ToW and MIA, and we find improvement on both fronts! We view this general improvement as evidence that ToW is a useful proxy for gauging how behaviours of different algorithms vary according to key characteristics.

However, during the rebuttal, we have expanded our analysis to address this feedback. Specifically, we tried a variant coined “ToW-MIA” that replaces the accuracy gap on the forget set term with the MIA gap (see Section 6). The results shown in Figures 7-9 in the PDF clearly show the same trends with ToW-MIA as for ToW, both for analyses and RUM. We will add these to the paper.

Re: transferability and “one needs to rely on the assumption that one unlearning algorithm is optimal across different datasets and model architectures”. It is true that our findings in this paper don’t inform us about the behaviour of any algorithm on any dataset (a limitation shared by any empirical paper). Understanding behaviours of algorithms across different unlearning problems is actually a major challenge that the community is faced with still, perhaps owing to unlearning being a young area of research. We view our work as a first step in uncovering key factors that practitioners can focus on when attempting to investigate the best algorithms to use in new contexts, which were not previously known.

We also emphasize that, in the context of a single chosen algorithm, even applying only the refinement step of RUM (applying that given algorithm in a sequence on refined subsets of the forget set, according to characteristics we discover) can boost performance significantly. This is very important as it offers a direct way to leverage our findings to get a boost in performance even when in scenarios where we don’t know the optimal algorithm to choose per subset (and rely on using a single pre-chosen algorithm).

Finally, we note that during the rebuttal we have investigated an additional dataset and architecture, showing that our main conclusions hold there too, as evidence for transferability. Please see the “common response” to all reviewers for more details.

Re: title and section 4. When we say “what makes unlearning hard”, the word “what” refers to “what properties of the forget set, or the retain / forget partition”, but that is a little bit of a mouthful, so we simplified it. We believe our paper studies what makes the problem hard, through showing under which circumstances (in terms of ES and memorization scores) different algorithms struggle to perform well; and we view this as largely conveying the same message as “on the difficulty of unlearning”. Does this clarification help, or does the reviewer still feel that the title is a little misleading? We are happy to brainstorm more about this.

Overall, we thank the reviewer for the thoughtful feedback. We actually believe that our new results (with C-proxy; see the “common response”, and with new a new dataset and architecture) as well as the discussion above addresses the reviewer’s central concerns about the practicality and transferability of RUM. We would love to hear the reviewer’s thoughts on this and discuss further if there are remaining concerns. Thanks!

Re: Weaknesses of ToW, we discern two interesting issues raised: 1) using average accuracies, 2) that it might be preferable to base ToW on another metric like MIA.

For 1), we computed for each example the output of the unlearned and retrained models, and we count the number of different predictions made by the two models. We find that in all cases there is only a very small percentage of disagreements and that for highly memorized data (which generally makes unlearning harder) the number of disagreements increases, but remains small. For low-memorized data, across all algorithms tested, the percentage of disagreements is within ca. [3%, 5%], while for highly-memorized data, it ranges between ca. [7%, 15%]. We will add these results to the paper.

For 2) we note:

• There is an ongoing debate for the most appropriate metric for unlearning. An advantage of ToW is the possibility to compare unlearning algorithms “holistically” based on a single scalar.

• ToW does use existing metrics: the “accuracy gap” (between the unlearned and retrained models), is commonly used in the literature!

• While we used ToW for our analyses (for simplicity and efficiency), we did evaluate RUM with MIA too. The fact that RUM improves w.r.t. MIA as well can be seen as an indication that ToW is actually a useful proxy for analyzing factors affecting difficulty that generalizes to other metrics.

• But to address this more concretely, we tried a variant coined “ToW-MIA” that replaces the accuracy gap on the forget set term with the MIA gap (see Section 6). The results shown in Figures 7-9 in the PDF clearly show the same trends with ToW-MIA as for ToW, both for analyses and RUM. We will add these to the paper.

Re: “Results on MIA could be stronger” and “ refinement step accounts for most/all gains”

• Our results in general show that both the refinement and per-subset algorithm choice of RUM play a big role. We do not see why it is “unexpected” to see that, for MIA, the refinement step plays a bigger role. This is actually a nice finding, which may lead to further insights.

• Table 1 in the paper clearly shows that RUM introduces strong MIA gains! For any algorithm there, the RUM version has much better MIA (and ToW). We are thrilled with this result (and frankly surprised to read this criticism).

Re: limited to ResNet and CIFAR. We address this point by adding an additional dataset and architecture. Please see the “common response” to all reviewers. We hope this considerably helps to put at ease doubts about the generalizability of our results.

Re: personal opinion on unlearning, privacy and “whether or not it was used for training seems inconsequential”: We believe different applications require different treatment. Here we are addressing unlearning defined as removing a subset of training data (the forget set). We agree some problems (e.g. preventing harmful generations) are not necessarily formulated as this type of “unlearning” because, as the reviewer said, all we care about there is to prevent those “bad” outputs (regardless of what data was used for training). In that case, retraining from scratch isn’t even the right reference point. However, our formulation is useful in other cases, e.g. enabling data deletion from a vision classifier. In that case, it is reasonable (and common) to adopt this DP-like formulation: ideal “deletion” of a data point leads to a model similar to one that was trained without that point. And in this case, MIAs are a common and convenient tool for measuring “leakage” and success of this type of unlearning. Overall, these are highly debated topics, with subjective opinions, and without consensus. While work is needed to settle these debates, we hope the reviewer agrees beyond doubt that our problem setting is widely considered a valuable one.

Re: “how can you overforget a forget set?” Following from above, our goal is to produce an unlearned model “similar” to that of retrain-from-scratch. So its accuracy on the forget set should be just as low as that of retraining, but no lower. We use the term “overforgetting” to describe the situation where the unlearned model causes a forget set accuracy lower than that of retrain. This is problematic as it can lead to vulnerability to MIA (due to noticeable differences from retraining).

Re: should we exclude retain set from ToW? The retain set is important. For instance, if a user has contributed some data towards training a model, and that user is not in the forget set, the user wants to still benefit from the model performing well for their data. At the same time, we want to preserve the ability to generalize to new users (test performance).

Re: using MMD instead of ES: Interesting point! We experimented with MMD and find there exists a (negative) correlation between ES and MMD scores. For CIFAR10/ResNet18 and CIFAR100/ResNet50, there exists a negative correlation where low(high) ES scores lead to high (low) MMD values.

Re: “why is original so low for medium and high memorization retain sets”. We assume the reviewer means “forget sets” rather than “retain sets” here (please correct us if not). An example that is “low mem” is one that has not influenced the model too much by definition (see Equation 1). So the predictions of the “original model” already look like those of the “retrained” model for this example, making the original model represent “good unlearning” according to the metrics of interest (based on similarity to the retrained model). On the other hand, for higher-mem examples, the original model is more influenced by those examples and therefore it “looks less” like a model that was trained without those examples. In these cases, the original model is a poor solution. Please let us know if this clarification helps.

Re: limitations, we will note these, thank you.

We hope our rebuttal satisfies all key concerns of Reviewer 3Cxb. We look forward to discussing any remaining concerns.

The reviewer’s point about looking at disagreements at the example level rather than average accuracy is a great one…and we see the same trends emerging according to both average accuracies and example-level disagreements, we feel there is no issues of “bias”; we in fact view this agreement of trends as evidence for the robustness of conclusions one would draw when using our contributions. Curious to hear the reviewer’s thoughts on this.

Sure, so it seems like we agree the example level metric would look very different from the dataset level metric. In the limit, accuracy might not change at all while the two models might disagree on most examples, by virtue of trading off similar amounts of false positives vs false negatives.

So, the metric is flawed at its core. It is very possible that two models get similar performance while producing very different predictive distributions. In fact this is common for two comparable NNets trained on a dataset, when the models don’t get near 100% accuracy. The metric would suggest that these models are indistinguishable, when this is not the case.

The fact that, for the few models and datasets examined in this paper, this bias does not seem to exceed 15% (a large number) is not comforting to me. We know in theory it’s wrong. We should just change it.

Note that this example-level disagreement can still become a scalar metric. It being a scalar metric is not the crux here.

We think the comparison that makes sense is to compare L1-sparse vanilla against L1-sparse RUM. Maybe accidentally the reviewer looked at the wrong rows in the table? (comparing L1-sparse vanilla against NegGrad+ RUM, but please correct us if we misunderstood your comparison).

Well, it’s not a “wrong” comparison. There are two ways of doing the comparison. You could control for the underlying method (L1-sparse vs NegGrad) and assess the effect of RUM across such settings. Or you could ask, how good can RUM be across methods, compared to how well we can do across methods without RUM. Two different, valid comparisons. And for what it’s worth, always restricting to within-method comparisons suffers from the risk of multiple testing (https://en.wikipedia.org/wiki/Bonferroni_correction).

In brief, yes they are statistically significant. For L1-sparse in Table 1, the MIA gap falls from 0.089 to 0.033. Specifically, we computed the paired t-test to derive the CIs for the MIA gaps. For the MIA gap for (L1-sparse-vanilla - Retrain) the 95% CI is 0.089 +/- 0.032. For the MIA gap for (L1-sparse-RUM - Retrain) the 95% CI is 0.033 +/- 0.003.

Great! I would recommend including this in the paper. In short, I am willing to believe there is an improvement from RUM, on the order of 3-5 points MIA.

The factors explaining difficulty (that we discover through analyses in Section 4) are what informs both the “refinement”,

Ok, this is a good point. Doing the subsetting/ordering depends on identifying the factors in the first place.

Thanks for the proposed changes. I think they seem adequate. I would overhaul the metric, but if it’s the case that a reader immediately sees a footnote or appendix reference clarifying the average vs. example level difference (and results are also provided in the appendix with an example level metric), that’s ok. I leave it to the authors to include this discussion in the revised manuscript, and I will raise my score to Borderline Accept.

Re: More discussion about efficiency / costs of RUM. This is a great point! Many researchers in this area do not bother with addressing issues of efficiency. Due to space constraints, we may have also been guilty of not paying as much attention as needed on this topic. This is unfortunate as indeed with our contributions we do address many issues about unlearning efficiency issues and those that arise as a result of our RUM framework.

Please note the below, which we will add more thoroughly in the paper too:

1. Our contributions show the importance of memorization, how it affects different SOTA algorithms, and how it can be leveraged with our RUM framework. But computing memorization scores, a la Feldman, is a very computation-heavy process, requiring a large number (100s) of models. We only just alluded in the paper to using proxies for the Feldman memorization score. But we agree this requires more concrete discussion.

In preliminary experiments, we experimented with various memorization score proxies from the literature. We have identified a promising one (C-proxy) and experimented with it in detail during the rebuttal (please see the “common response”). Our results show that: (i) our analyses and trends in Section 4 regarding the impact of memorization on unlearning algorithms continue to hold when using C-proxy instead, with no noticeable differences. (ii) leveraging the c-proxy values instead of the actual (a la Feldman) memorization scores still leads to very large performance gains with our RUM framework, consistent with the ones in the original paper. In the attached PDF, please see Figure 1 and 2, showing the performance of algorithms according to low/medium/high c-proxy values and the performance of RUM when using C-proxy, respectively. As before the gains are large and clear with C-proxy as well!

Please note that computing c-proxy instead of the Feldman’s memorization score enjoys orders of magnitude performance improvement (due to avoiding training a large number of models that are needed to compute Feldman’s memorization scores). This makes our RUM framework practical and efficient to deploy.

2. Our contributions show when it makes sense to apply any of the SOTA algorithms, based on the memorization scores of examples in the forget set. So, a forget set consisting of only low-memorized examples, can be excluded from the unlearning process, saving all unlearning costs: as discussed in the paper, unlearning in this case is at best not needed (and at worse harmful), because even a model retrained without such examples can classify them correctly, so there is no need to modify the model to make it unable to classify those examples. In fact, attempts at doing so may lead to worse unlearning performance, as we discussed in the paper for Random Label and SalUn.

This finding leads directly to efficiency improvements during unlearning. The exact gains are hard to quantify, but one should reasonably expect the efficiency gains to be analogous to the ratio of the size of the low-memorized examples over the overall forget set size.

3. Our results show that often much more efficient unlearning algorithms (like GA and other similar baselines that mainly need access to the examples in the drastically smaller forget set and do not depend heavily on the drastically larger retain set) can be competitive in terms of ToW/MIA performance for at least some partition (low/medium/high) of the forget set. Thus, for these partitions of the forget set, with RUM one could enjoy much higher efficiency without sacrificing ToW/MIA performance. This will obviously reduce the overall time for unlearning.

4. In addition, RUM is also shown to be able to significantly improve the performance of all algorithms studied in terms of ToW/MIA. Hence, consider a practitioner who chooses any algorithm (which e.g., for efficiency reasons may not be the best performing in terms of ToW/MIA). By “RUMifying” it, it also boosts its ToW/MIA performance, having a more acceptable and efficient unlearning solution.

We will gladly reflect these discussions about efficiency issues with respect to our contributions in the paper, since, as HxTF points out these are very important (and strengthen our paper).

Re: the tables and figure are small: We agree! This is actually an important point. We will address this, making figures and table more readable.

Re: nit comments on math readability: great point, we will make this adjustment (and thanks for catching the typo re: the style of S).

Overall, we thank the reviewer for the thoughtful feedback and encouraging remarks. We believe that the discussion above addresses all key elements of efficiency which pertain to our contributions and that our contributions can lead to an efficient and practical deployment (in addition to their contributions to unlearning science). We would love to hear the reviewer’s thoughts on this and discuss further if there are remaining questions. Thanks!

Re: limited to classification models. We agree it is important to study different modalities, discriminative and generative models. However, these settings differ in three key ways.

1. Unlearning definitions: The problem we study is removing the influence of a particular subset of training data (the “forget set”) from the model; success is defined as matching the distribution of retraining from scratch without the forget set. In generative models, unlearning can take different forms: i) remove a ‘concept’ (e.g. nudity, in diffusion models; Fan et al), or harmful content in LLMs, or ii) in LLMs, unlearn memorized text. In both i and ii, the goal is not matching retrain-from-scratch. For case i, the “forget set” may not even contain training images, it may be generated instantiations of unwanted content, and application-dependent metrics are used. Though ii is closer to our problem, computing retrain-from-scratch is not practical in large LLMs (none of the works use that as a reference point) and other definitions or metrics are used.

2. Memorization definitions. According to the definition of label memorization (see equation 1), rare or atypical examples are more highly memorized, as we discussed. Instead, in LLMs, memorization is typically defined as “verbatim memorization” (e.g. see Definition 2 in [1]), capturing the model’s ability to regurgitate training data. Recent works (e.g. [1]) find that the more common a string is (i.e. less rare), the more likely it is to get memorized. This definition is what SOTA methods for memorized-data unlearning [2,3] use (case ii in the above). These notions are clearly distinct (and even seemingly at odds with one another) and an analysis of unlearning difficulty for verbatim memorization would thus require specialized treatment.

3. SOTA methods. For example, the SOTA models for unlearning memorized data from LLMs are based on “simple” Gradient Ascent (GA) (see [2,3]). On the contrary, in computer vision / image classification tasks, (variations of) GA have been shown to be lacking badly. In particular, model utility for image classification suffers largely with GA (and variations thereof), whereas for text generation and reasoning, model utility can remain high with GA (as shown in for example [2,3].

References: [1] Carlini et al, 2021 “extracting training data from large language models”, [2] Jang et al. 2023. “Knowledge unlearning for mitigating privacy risks [...]”, [3] Barbulescu et al. 2024. “To each (textual sequence) its own [...]”.

In summary, unlearning in generative models differs fundamentally. Hence, as the reviewer states, a comprehensive analysis is (well) beyond the scope of this paper. Our work is an important step in advancing knowledge and in-depth understanding of unlearning for image classification.

Re: only CIFAR and image classification. We have added a new dataset and architecture based on this feedback, please see the “common response” for the details. All conclusions remain consistent, supporting the generalizability of our findings. We hope this addresses the reviewer’s concern.

Please also note our answer to the above point for the comment on text generation and reasoning. We leave an investigation of tasks in other modalities and generative models for future work for those reasons.

Re: “human-designed heuristic [...] limits the generalizability of this method.” Thank you for raising this, we believe this is a very important point.

First, our primary goal is a deeper understanding of behaviours of unlearning methods on different forget sets. Crucially, our work shows the potential of such insights leading to better unlearning pipelines: each SOTA algorithm is shown to be improved upon using RUM. And, RUM using different algorithms for different partitions further improves performance. This is already a key contribution that can inform better generalizable approaches in the future.

Of course, repeating our entire analysis on each new dataset or problem setting in order to plug in the “hand-picked” design decisions when using RUM is undesirable. Due to this, we designed our analysis to uncover key factors affecting algorithm behaviours (e.g. how algorithms interact with memorization) that transfer across datasets / architectures (e.g. as long as one knows the memorization scores). Since computing memorization scores for new training datasets is expensive, we show in our new experiments results with a cheap proxy (the “C-proxy”); see the “common response”. Hence, RUM is generalizable / practical: First, uncover key characteristics, for instance, memorization levels (or a cheaper proxy), and then plug them in to RUM to get big performance gains.

Re: minor: thank you, we will fix these.

Re: “What is the model accuracy before unlearning in experiments” – we denote this by “Original” in each experiment. The test accuracy values are 84.353±3.455% for CIFAR-10/ResNet-18 and 75.003±2.809% for CIFAR-100/ResNet-50, with 100% training accuracy for both settings. More detailed accuracy results can be found in the appendix: Table 5,6 for unlearning difficulty vs ES experiments, and Table 8,9 for unlearning difficulty vs memorization experiments.

Re: “What is the criteria to group samples into low/medium/high partitions”. First, we sort in increasing order all examples in the dataset based on the metric of interest (memorization score or embedding distance). Then, say the forget-set size is N. We select the first (lowest value) N/3 examples to be the ‘low partition’, the last N/3 examples to be the ‘high partition’ and the middle N/3 to be the ‘medium partition’.

Overall, we thank the reviewer for the thoughtful critical feedback. We believe the new results (with C-proxy and additional dataset / architecture) and discussion, address the reviewers central concerns. We would love to hear the reviewer’s thoughts and discuss further if there are remaining concerns. Thanks!