What makes unlearning hard and what to do about it

Authors: kairan  zhao
meghdad  kurmanji
george-octavian  barbulescu
eleni  triantafillou
google  deepmind
peter  triantafillou
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 18:58:33

Abstract: Machine unlearning is the problem of removing the effect of a subset of training data (the ``forget set'') from a trained model without damaging the model's utility e.g. to comply with users' requests to delete their data, or remove mislabeled, poisoned or otherwise problematic data.
With unlearning research still being at its infancy, many fundamental open questions exist: 
Are there interpretable characteristics of forget sets that substantially affect the difficulty of the problem? 
How do these characteristics affect different state-of-the-art algorithms?
With this paper, we present the first investigation aiming to answer these questions. We identify two key factors affecting unlearning difficulty and the performance of unlearning algorithms. Evaluation on forget sets that isolate these identified factors reveals previously-unknown behaviours of state-of-the-art algorithms that don't materialize on random forget sets.
Based on our insights, we develop a framework coined Refined-Unlearning Meta-algorithm (RUM) that encompasses: (i) refining the forget set into homogenized subsets, according to different characteristics; and (ii) a meta-algorithm that employs existing algorithms to unlearn each subset and finally delivers a model that has unlearned the overall forget set. 
We find that RUM substantially improves top-performing unlearning algorithms. 
Overall, we view our work as an important step in (i) deepening our scientific understanding of unlearning and (ii) revealing new pathways to improving the state-of-the-art.

Main paper: 
 introduction: 
 Deep learning models have generated impressive success stories recently by leveraging increasingly large and data-hungry neural networks that are also increasingly expensive to train. This trend has led to reusing previously-trained models for a wide range of tasks more than ever before. However, the heavy reliance of deep models on training data, together with the difficulty of removing data from trained models after-the-fact, has exacerbated concerns on perpetuating harmful or outdated information, violating user privacy and other issues. Specifically, deep networks are highly nonconvex, making it difficult to trace (and thus attempt to remove) the effect of a given subset of training data on the model weights. We are therefore faced with important technical challenges when it comes to building machine learning pipelines that are performant while efficiently supporting deletion requests. Machine unlearning [29] is a growing field that aims to address this important issue.While unlearning is receiving increasing attention [34, 33] , it is still a young area of research and the factors affecting the success of different approaches remain poorly-understood. Understanding what makes an unlearning problem easy or hard is crucial for several reasons. First, knowledge of behaviours of unlearning algorithms on different types of forgetting requests may inform which unlearning method to choose for a given request. In fact, for some requests it may be that all current methods are inadequate, suggesting that one should pay the cost of retraining from scratch rather than opting for "approximate unlearning" that imperfectly removes information after-the-fact. Further, deepening our understanding of unlearning can illuminate pathways for improving both unlearning algorithms as well as evaluation protocols by focusing on relevant factors that affect difficulty.To this end, we present the first investigation into different factors that characterize the difficulty of an unlearning problem. We find that the unlearning problem becomes harder i) the more entangled the retain and forget sets are and ii) the more memorized the forget set examples are. Our investigation reveals that different unlearning algorithms suffer disproportionately as the difficulty level increases and surfaces previously-unknown behaviours and failure modes of state-of-the-art unlearning algorithms. Inspired by our findings, we propose a Refined-Unlearning Meta-algorithm (RUM) for improving unlearning pipelines. RUM contains two steps: i) a refinement procedure that divides the given forget set into subsets that are homogeneous with respect to relevant factors that influence algorithms' behaviours, and ii) a meta-algorithm that dictates how to unlearn each of those subsets and compose the resulting models to arrive at one that has unlearned the entire forget set. Our thorough investigation shows that RUM boosts unlearning performance of several state-of-the-art algorithms and addresses issues that our investigation of unlearning difficulty has uncovered. 
unlearning problem formulation: 
 Let θ o = A(D train ) be the weights obtained by applying a training algorithm A on a training dataset D train . We will refer to θ o as the "original model". Further, let S ⊆ D train denote a subset of the training data referred to as the "forget set". For convenience, we will refer to its complement as the "retain set" R = D train \ S. Informally, the goal of an unlearning algorithm U is to utilize θ o , S and R to produce an unlearned model θ u = U(θ o , S, R) from which the influence of S is removed. This idea has been formalized by considering the distributional similarity between the model θ u produced by U and the model θ r produced by the optimal unlearning approach: retraining from scratch on an adjusted training dataset that excludes the forget set: θ r = A(D train \ S). Note that we refer to distributions here since rerunning U and A with different random seeds (that control e.g. the initialization and the order of mini-batches) will lead to slightly different weights. The ideal unlearning algorithm then, according to this viewpoint, is one that yields the same distribution of weights as retraining from scratch. Of course, for an unlearning algorithm to be practical, we would additionally desire it to be significantly more computationally efficient than retraining the model.The following definition, borrowed from [33] (and similar to [14] ) formalizes this idea in a framework inspired by differential privacy [8] . Definition 2.1. Unlearning. An unlearning algorithm U is an ( , δ)-unlearner (for A, D train and S) if the distributions of A(D train \ S) and U(θ o , S, D train \ S) are ( , δ)-close.where we say two distributions µ, ν are ( , δ)-close if µ(B) ≤ e ν(B) + δ and ν(B) ≤ e µ(B) + δ for all measurable events B.According to the above definition, an unlearning algorithm is said to be exact unlearning if it satisfies the above definition for = δ = 0, i.e., it yields a distribution of models identical to that of retraining from scratch. For neural networks, the only known exact solutions involve retraining, either naively, or in the context of mixtures where one can retrain only a subset of models affected by the deletion request [3] . These approaches unfortunately are inefficient; in the worst-case, even clever schemes suffer inefficiency similar to naive retraining, and may also yield poorer performance. To address this, a plethora of approximate unlearning algorithms have been recently proposed, whose and δ values aren't known in general, but are substantially more efficient and may have higher utility.Evaluating approximate unlearning. Since the success of (most) approximate unlearning algorithms cannot be proved within tight ( , δ) bounds, the community has considered various empirical measurements of success, guided by three desiderata: i) good forgetting quality, 2) high utility, and 3) efficiency. An unlearning algorithm thus is faced with a complex balancing act, as there are well-known trade-offs both between forgetting quality and utility, as well as forgetting quality and efficiency, and a good unlearning metric should capture these nuances.Utility and efficiency are straightforward to measure, and, in the context of classifiers, can be represented by the accuracy on the retain and test sets, and time in seconds, respectively. Measuring forgetting quality, on the other hand, is more complex and several proxies have been proposed. The simplest one is to inspect the accuracy on the forget set, with the goal of matching the accuracy on the forget set that would have been obtained by retraining from scratch. Alternatively, inspired from privacy literature [4, 28] , Membership Inference Attacks (MIAs) have been adopted by the unlearning community [25, 26, 20] to measure forgetting quality. In essence, an MIA is designed to infer from the model's characteristics (e.g. loss, confidence) whether a data point has been used in training, and then unlearned, versus was never trained on in the first place. Intuitively, the failure of an attacker to tell apart unlearned examples from never-seen examples marks a success for the unlearning algorithm in terms of this metric. We will consider both of these proxies in our experimental investigation.To holistically evaluate an unlearning algorithm, we desire a single metric that captures both forgetting quality and utility. We will later introduce a "tug-of-war" metric for this purpose, inspired by [33] .Deep neural networks are known to "memorize" (a subset of) their training data, with a recent theory showing that label memorization is in fact necessary for achieving close-to-optimal generalization error in classifiers [11] when the data distribution is long-tailed. Definition 2.2. Memorization score [11] . The memorization score for an example i ∈ D, with respect to a training dataset D and training algorithm A is mem(A, D, i) = PrEQUATIONwhere x i and y i are the feature and label, respectively, of example i.The first term in the above equation considers models trained on all of D whereas the second term considers models trained on D excluding example i. Intuitively, the memorization score for an example i is high if including it in training yields a different distribution of predictions on that example than excluding it from training would have. Recent works [11, 12, 23] identify atypical examples or outliers of the data distribution as examples that are more highly memorized: if an example has a noisy or incorrect label, the model is required to memorize it in order to predict it correctly. 
related work: 
 Approximate unlearning algorithms. A plethora of algorithms have been proposed that aim to identify effective data scrubbing procedures post-training. We now describe representative methods.Fine-tune [36, 15] relies on catastrophic forgetting to diminish the confidence of the original model θ o on S. Catastrophic forgetting is induced by simply fine-tuning on the retain set D train \ S. On the other hand, NegGrad [15, 17, 31] instead directly maximizes the loss on S. This approach has been found empirically to cause a large drop in the utility of the model. To address this, NegGrad+ [25] combines fine-tuning and gradient ascent, by jointly minimizing the loss function on the retain set, and maximizing the loss function with respect to the forget set. SCRUB, proposed by the same authors as NegGrad+, extends the contrastive learning behind NegGrad+ by framing it as a student-teacher problem. Concretely, SCRUB is a bi-optimization algorithm, where the student aims to mimic the teacher's behaviour on R and to disobey the teacher's output with respect to S. L1-sparse [26] infuses weight "sparsity" into the unlearning algorithm by fine-tuning on the retain set with an L1-penalty, drawing inspiration from the model pruning literature [13, 27] . Influence Unlearning [21, 24] arrives at the important model's weights by estimating how removing a data point affects θ o via influence functions [7] , and draws connections to ( , δ)-forgetting [35, 19] .A different line of work is "relabelling-based" methods that trick the model to learn new labels for S. This can be achieved by finetuning the model with respect to a dataset D relabel = (X S , Y ), where X S are the features and labels Y are sampled from a prior distribution of the label space. Saliency Unlearning (SalUn) [10] learns D relabel by optimising only the salient parameters of the model.Concretely, the authors argue that the model's weights θ o can be decomposed into salient weights and "intact" model weights, by investigating the weight space with respect to the forget set S ala [30, 1] .Difficulty of Unlearning. The closest research to ours is the contemporaneous work of [9] , where the authors study adversarial unlearning cases, i.e. "worst-case" forget sets. [9] arrives at difficult forget sets by solving a bi-level optimization based on fine-tuning (i.e. catastrophic forgetting). Instead, we arrive at difficult partitions through the lens of interpretable factors: the degree of entanglement between the retain and forget set and memorization. While the primary aim of [9] is to construct more pessimistic evaluation benchmarks, our primary aim is to deepen our understanding of unlearning problems and of the behaviour of state-of-the-art algorithms when operating on forget set of different identified characteristics, ultimately improving unlearning pipelines.Catastrophic forgetting, atypical examples and privacy. [22] and [32] study catastrophic forgetting during training. [22] finds that, when training on large datasets, examples that were only seen early in training may enjoy better privacy, in terms of MIAs and extraction attacks, compared to examples seen recently. [32] investigate "forgetting events", where an example that was previously correctly predicted becomes incorrectly predicted later in training. They find that examples with noisy labels witness a larger number of these forgetting events. Further, [5] find that models trained with Differential Privacy (DP) find it primarily hard to correctly predict atypical examples. We build on this literature by studying the difficulty of unlearning after-the-fact, rather than (passive) forgetting during training and draw connections to memorization, a notion closely related to atypicality in the data distribution.4 What Makes Unlearning Hard?In this section, we identify and empirically examine two factors that affect the difficulty of unlearning.Before diving in, we first define a simple proxy for unlearning difficulty that we will use in this section. Our goal is to capture the difficulty of performing the "balancing act" of forgetting S while retaining the ability to perform well on R and generalize well to the test set. We propose a metric to capture this "tug-of-war" (ToW) using the relative difference between the accuracies of the unlearned and the retrained model on the forget, retain and test sets, in a manner inspired by [33] .ToW(θ u , θ r , S, R, D test ) = (1 -da(θ u , θ r , S)) • (1 -da(θ u , θ r , R)) • (1 -da(θ u , θ r , D test ))where a(θ,D) = 1 |D| (x,y)∈D [f (x; θ) = y]is the accuracy on D of a model f parameterized by θ and da(θ u , θ r , D) = |a(θ u , D)a(θ r , D)| is the absolute difference between the accuracy of models θ u and θ r on D. Therefore, ToW rewards unlearned models that match the accuracy of the retrained-from-scratch model, on each of the forget, retain, and test sets. ToW ranges from 0 to 1, with higher values associated with better unlearning.The more entangled the forget and retain sets are, the harder unlearning becomes Prior research (e.g., by Feldman et al [11] and Carlini et al [5] ) has tried to identify prototypical (or atypical) examples and their impact on learning. Primarily, this depended on the position of examples within the overall data space distribution. In contrast, here we focus on the embedding space, as unlearning depends heavily on how the model has learned to represent training data. Furthermore, instead of looking at isolated examples, we delve into how "entangled" the retain and forget sets are in embedding space. We hypothesize that higher "entanglement" leads to harder unlearning: if the two sets are highly entangled, attempting to erase S will cause accidentally erasing R too.We propose to measure entanglement between the retain and forget sets via the below Entanglement Score (ES), inspired by a measure previously introduced in [16] to study learned representations.o ) = 1 |R| i∈R (φ i -µ R ) 2 + 1 |S| j∈S (φ j -µ S ) 2 1 2 (µ R -µ) 2 + (µ S -µ) 2 (2)where φ i = g(x i ; θ o ) is the embedding of example x i according to the "original model" f , parameterized by θ o ; where g denotes the forward pass through f up till the penultimate layer, i.e. excluding the Figure 1 : Uncovering two factors that affect unlearning difficulty according to ToW (where higher is better). Left: the more entangled the retain and forget sets are in the embedding space, the harder it is to unlearn. Right: the less memorized a forget set is (thus having influenced the model less), the easier it is to unlearn (for most algorithms). Error bars correspond to 95% confidence intervals from running each algorithm 3 times (6 times for relabelling-based that had higher variance). classifier layer. Further, µ R = 1 |R| i∈R φ i is the mean embedding of the retain set, and analogously, µ S the mean embedding of the forget set, while µ is the mean embedding over all of D train = R ∪ S.Intuitively, ES measures entanglement between S and R in the embedding space of the original model (before unlearning begins). The numerator measures intra-class variance, capturing the tightness of each of those two sets, independently, while the denominator measures inter-class variance between those two sets. Higher ES score corresponds to higher entanglement in the embedding space.Our investigation hinges on generating three different forget/retain partitions with different degrees of entanglement: low, medium, and high. But, Equation (2) does not directly suggest a procedure for generating retain/forget partitions with a desired ES score. Hence, we achieved this indirectly using a proxy. Specifically, let d(i, µ; θ o ) = ||φ i -µ|| 2 denote the l2-distance in the original model's embedding space between example i and centroid µ, as defined above. We compute this distance for each example in D train and sort those examples according to their d-values. We then form each forget set to contain a contiguous subset of examples from different ranges of that sorted list. We find that this procedure allows us to construct retain/forget partitions of varying ES values. The ES values for our low, medium and high partitions are 309.94±98.56, 1076.99±78.64, 1612.21±110.82 for CIFAR-10, and 963.82±113.53, 2831.24±558.63, and 3876.90±426.92 for CIFAR-100. We include details of this procedure in the Section A.3, along with visualizations and Maximum Mean Discrepancy (MMD) analysis to further validate ES, confirming that the degree of retain/forget entanglement aligns with the computed scores. We experiment with four dataset/architecture settings: CIFAR-10/ResNet-18, CIFAR-100/ResNet-50, Tiny-ImageNet/ResNet-18 and Tiny-ImageNet/VGG-16, using |S| = 3000. Refer to Section A.2 for implementation details and Section A.8 for more detailed results on all datasets. We observe from Figure 1a that it is harder to unlearn when the retain and forget sets are more entangled: all unlearning algorithms have poorer performance for highly-entangled vs lower-entangled settings. Further, we notice that different unlearning algorithms suffer disproportionately as the entanglement increases. Notably, methods based on relabelling (SalUn and Random-label) perform very poorly when the entanglement is high. We hypothesize that this is because, if two examples i and j are close neighbours in embedding space, with i in the forget set and j in the retain set, forcing example i to be confidently predicted as an incorrect class (as relabelling algorithms do) will also cause j to be predicted as that incorrect class, too, thus causing a drop in retain accuracy, which is captured by ToW. This effect will be less pronounced if i and j are far from each other.The more memorized the forget examples are, the harder unlearning becomes Feldman et al [11] have already established that models must memorize some atypical examples in order to perform well. Further, prior literature has also established that noisy examples (that are more likely to be memorized) witness more "forgetting events" during training (their predicted label flips to an incorrect one) [32] and that models trained with Differential Privacy (DP), a procedure where noise is added to the gradients (making it harder to memorize), find it primarily hard to correctly predict atypical examples [5] . In this section, we build upon these prior insights by investigating the connection between the degree of memorization of the forget set and difficulty of unlearning.Let's begin by inspecting Definition 2.2: if an example is not really memorized, the predictions of the model on that example will not change much whether the example was included in training or not. This implies that even the original model (no unlearning) is similar to retrain-from-scratch in terms of predictions on those examples, making unlearning unnecessary or trivial. On the other hand, for highly-memorized examples, the predictions between the original and retrained models will differ significantly, implying that an unlearning algorithm has "more work" to do to turn the original model into one that resembles the retrained one. We now investigate how the level of memorization of the forget set affects the behaviour of state-of-the-art unlearning algorithms. We hypothesize, based on our above intuition, that unlearning is easier when the forget set contains less-memorized examples.To investigate this, we first compute the memorization score mem(A, D train , i) of each example i ∈ D train and we sort all examples according to their scores. We then use that sorted list to create three different forget sets, corresponding to the lowest N scores ("low-mem"), the highest N ("high-mem"), and the N that are nearest to 0.5, i.e. the midpoint of the range of memorization scores ("medium-mem"), where N = 3000. We then apply different unlearning algorithms on each of these forget sets and compute ToW. We perform this experiment on CIFAR-10 using ResNet-18 and on CIFAR-100 using ResNet-50. Refer to Section A.2 for implementation details.We first emphasize two key sets of conclusions. First, in terms of ToW, Figure 1b shows that, indeed, for most algorithms, the lower the memorization level of the forget set, the easier the problem is. In line with our prior discussion, even the original model performs well on "low-mem", but performs very poorly on "high-mem". Interestingly though, the two relabelling-based algorithms (SalUn and Random-label) follow an inverse trend: they perform better for higher-memorized forget sets. Second, breaking down ToW into its parts, we find interesting trends in terms of the forget set accuracy, in Figure 12 . Specifically, for several unlearning algorithms, the forget accuracy for "low-mem" is still very high after unlearning them, as the model can infer the correct labels for such examples even when they weren't included in training; this follows directly by Definition 2.2 if unlearning is done by retraining, and is shown here for the first time for approximate unlearning algorithms. On the other hand, we find that, for "high-mem", different unlearning algorithms can (to varying degrees) cause the forget set accuracy to drop substantially; this is consistent with both [32] and [5] , but shown here for the first time for approximate unlearning algorithms. Notably, we find that relabelling-based algorithms cause a larger drop in the accuracy of the forget set, relative to other approaches. This benefits ToW in the case of "high-mem" forget sets, where retraining has poor accuracy on this set (so they get rewarded by matching it), but it hurts on "low-mem", since it causes a large discrepancy from retraining, which has high accuracy on this set (since it makes similar predictions to the original model on this set, by definition, and the original model has high accuracy on all of D train ).Overall, we have presented the first investigation into the behaviour of unlearning algorithms applied on forget sets of different degrees of memorization. A key finding is that different algorithms outshine others for different forget sets. Most notable is the failure of relabelling-based algorithms on the "low-mem" forget set, which is easy for other algorithms and, in fact, even no unlearning in that case might be an acceptable solution. We intuit that this is due to their aggressive unlearning strategy yielding "overforgetting" (producing a forget set accuracy that is lower than that of retraining from scratch) as discussed above. Furthermore, we observe that different unlearning algorithms work best for the "low-mem", "medium-mem" and "high-mem" forget sets. Concretely, from Figure 1b we note that Finetune is best for "medium-mem", SalUn is best for "high-mem", and a number of algorithms are top-performers for "low-mem" (including no unlearning). This reveals a possible pathway for improving unlearning based on using different algorithms for different forget sets. So, how can one build on these insights to further improve unlearning algorithms performance?5 Refined-Unlearning Meta-algorithm (RUM) for Improved Unlearning Previously, we observed that unlearning algorithms have different behaviours on forget sets with different properties. For example, while "low mem" forget sets are almost trivial to unlearn (and even doing nothing may be acceptable), SalUn and Random-label perform poorly on them. On the other hand, SalUn and Random-label evidently outperform other unlearning algorithms on "high mem". These observations suggest that the optimal unlearning algorithm to use is dependent on the properties of the forget set. One could therefore pick the best unlearning algorithm for each unlearning request, based on these factors. However, in practical scenarios, forget sets may be distributed differently than in our preliminary experiments, that were designed to cleanly separate different factors of interest. Indeed, real-world forget sets would likely contain a mixture of examples from different modes of the data distribution, some rare or highly-memorized while others common and not memorized at all. So, what can be done about these expected heterogeneous forget sets? How can our insights above be leveraged to improve unlearning for such cases? To address this, we first propose a refinement procedure that divides forget sets into homogeneous subsets (with respect to the factors that we have found to affect the difficulty of unlearning and behaviours of existing algorithms). Second, we propose to utilize a pool of state-of-the-art algorithms to unlearn different subsets. Put together, we propose a Refined-Unlearning Metaalgorithm (RUM), comprised of two steps: 1) Refinement and 2) Meta-unlearning. Figure 2 overviews RUM.Step 1: Refinement. We introduce a function F that partitions the forget set S into K subsets: {S i } K i=1 = F(S) such that each forget set example appears in exactly one such subset. The intention of F is to generate homogeneous subsets w.r.t factor(s) that affect difficulty / algorithm's behaviours.Step 2: Meta-Unlearning. Having obtained the subsets {S i } K i=1 of S, we now require a "metaalgorithm" M that dictates how to perform the individual unlearning requests and how to compose the resulting unlearned models to arrive to a model that has unlearned all of S. In this work, we focus on meta-algorithms that tackle unlearning of subsets in a sequence, leaving other designs for future work. It therefore remains for our "meta-algorithm" to decide: i) what unlearning algorithm to apply for each subset, ii) what order should the unlearning requests be executed in.More concretely, we assume access to a pool of existing unlearning algorithms U 1 . . . U N , like the ones described in related work, for instance. Let M U (S i ) denote a procedure that takes as input a subset S i and returns an unlearning algorithm U ∈ {U 1 . . . U N } that will be used for that subset. This selection can be done by leveraging insights such as those in Section 4. Further, let M O denote a procedure that takes as input the K subsets of S and returns a sorted list S = M O (F(S)) containing the K subsets in the desired order of execution.Given the above ingredients, RUM proceeds by executing K unlearning requests in a sequence, with step i of that sequence corresponding to unlearning subset S [i] by applying U i (θ o , S [i], R i ) = θ u i , where θ u i denotes the unlearned model up to step i andU i = M U (S [i]) and R i = R ∪ {S [i + 1], . . . S [K]}is the retain set for step i, containing R as well as all other subsets of S that have not yet been unlearned in the sequence so far. We finally return the unlearned model of the last step θ u K . Our RUM framework is meant as an analysis framework, surfacing new problems to be solved and offering new pathways into future state-of-the-art algorithms. Nonetheless, we contribute below specific top-performing RUM instantiations, with specific choices for F and for M.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [NA] Justification: This paper does not include any theoretical results, hence no assumptions or proofs are required. 
experimental result reproducibility: 
 Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: The paper provides detailed descriptions of the experimental setup, including the datasets used, model architectures, hyperparameters, and evaluation metrics. This ensures that the main experimental results can be reproduced accurately, supporting the paper's claims and conclusions. 
experimenting with rum flavours: 
 We now present RUM instantiations using a refinement strategy based on memorization scores and experimental evaluations answering the following questions: Q1: How useful is refinement alone? That is, for a given unlearning algorithm U, does applying U sequentially on the K homogeneous subsets of S outperform applying U once on all of S? Q2: Can we obtain further gains by additionally selecting the best-performing unlearning algorithm for each forget set subset? Q3: Are there interpetable factors behind the boost obtained by sequential unlearning of homogeneous subsets?Experimental setup We experiment with a refinement strategy based on memorization scores where K = 3. Specifically, we study unlearning a forget set S that is the union of the three sets containing the N lowest, the N closest to 0.5, and the N highest memorized examples in the dataset, Figure 3 : From subplots a and c, we observe that RUM F improves each unlearning algorithm.Vanilla corresponds to unlearning S in one go, whereas Shuffle and RUM F operate sequentially on 3 subsets of S. In the case of RUM F , the 3 subsets are the result of applying F and the order is low → medium → high, whereas Shuffle uses equal-sized random subsets, serving as a control experiment. Further, from subplot b, we observe that full RUM, equipped with the best algorithm for each subset (do nothing → Fine-tune → SalUn), yields the overall best results (note: in CIFAR-100, NegGrad+ is the best algorithm, so full RUM corresponds to the RUM F variant of NegGrad+).where N = 1000, making the overall size of the forget set 3000. We conduct experiments on two different datasets: CIFAR-10 and CIFAR-100, using ResNet-18 and ResNet-50, respectively. We evaluate unlearning algorithms both in terms of ToW, as before, and using a commonly-used MIA [10, 26] that is a binary classifier trained to separate R from D test and then queried on examples from S. Following previous work, we report as "MIA" the fraction of examples from S that were predicted to be held-out. The goal is to match the "MIA" score of retrain-from-scratch. For convenience, we report the "MIA gap": the absolute difference of the MIA score of unlearning from the MIA score of retrain-from-scratch (lower is better). Further details on MIA setup are in Section A.4. We also introduce a new metric"ToW-MIA", which mirrors ToW but replaces its "forget quality" component (i.e., its accuracy on S) with the MIA score. Results for ToW-MIA are presented in Section A.4 and A.8 and largely follow the same trends. To gain a finer understanding of the differences between the unlearned and retrained models, we additionally analyze the number of examples where their predictions disagree (see Section A.7). We also consider and analyze the effect of two different orderings: i) low → medium → high and i) high → medium → low. 1 : Each algorithm U is applied in three ways: i) in one-go ("vanilla"), ii) on a random partition of S into 3 equal-sized subsets, sequentially ("shuffle"), and iii) on three equalsized subsets obtained by F in low → med → high order ("RUM F "). In last row, RUM additionally chooses the best algorithm for each subset: none → Fine-tune → SalUn in CIFAR-10 and NegGrad+ RUM F in CIFAR-100.How useful is refinement alone? To investigate this, we selected a subset of highest-performing algorithms and apply each algorithm U in three ways: i) "vanilla", i.e. applying U(θ o , S, R) as usual, ii) "shuffle" where U is applied sequentially on three equal-sized subsets of S that were determined randomly, and iii) RUM F , where U is applied sequentially on the subsets obtained by F(S), i.e. utilizing only the refinement step of RUM and applying the same U on each subset. We include "shuffle" as a control experiment, so that any gain of RUM F over shuffle is due to homogenization rather than simply reducing the size of the forget set or other effects of sequential unlearning. We observe from Figure 3 and Tables 16a and 16b that, for four different unlearning algorithms and on two different datasets, RUM F significantly outperforms "vanilla" and "shuffle", indicating that operating sequentially on homogenized subsets according to memorization can boost the performance of unlearning algorithms. Interestingly, in most cases, "shuffle" actually performs worse than "vanilla", indicating that the difficulty of the problem may increase rather than decrease given a poor refinement strategy.To answer this, we leverage our findings from Section 4 to identify the best unlearning algorithm for each of the "low- mem", "medium-mem" and "high-mem" scenarios. On CIFAR-10, this corresponds to doing nothing for low-mem (i.e. using the original model directly), using Fine-tune for medium-mem and SalUn for high-mem (based on Figure 1b ). From Figure 3b (and Table 16a ), we observe that we get the overall best results by far, both in terms of ToW and MIA, by applying RUM with "nothing → Fine-tune → SalUn", demonstrating the value of incorporating our insights into unlearning pipelines. In fact, lets revisit our previous observation that SalUn and Random-Label perform uncharacteristically poorly on the "low-mem" forget set. In line with our hypothesis, we notice that "nothing → SalUn → SalUn" outperforms applying SalUn on all three subsets (a.k.a. SalUn RUM F ). Note that, for CIFAR-100, the best algorithm for all subsets is NegGrad+, so full RUM corresponds to NegGrad+ RUM F .Can we obtain similar performance boosts with compute-efficient proxies? Given the computational cost of calculating memorization scores, we aim to find a more efficient proxy to enable practical deployment of RUM. We discuss a confidence-based memorization metric, termed "Cproxy", as a proxy for memorization [23, 32] . Section A.6 provides a detailed explanation of the proxy and the complete results across various datasets and architectures. Figure 4a shows that the observed unlearning difficulty pattern-specifically, that forget examples with higher memorization scores (i.e., lower C-proxy values, as they are negatively correlated; see Table 4 ) are harder to unlearn-remains consistent when using C-proxy, paralleling the results in Figure 1b . This pattern is further confirmed on Tiny-ImageNet with both ResNet-18 and the VGG-16 architectures, as shown in Figure 9 . We then examine whether using C-proxy achieves similar performance gains within RUM as the original memorization score. Figure 4b presents results on CIFAR-10 with ResNet-18, using C-proxy in place of memorization score during the refinement step. This analysis is also extended to Tiny-ImageNet with both ResNet-18 and VGG-16 architectures, as shown in Figure 10 and Table 17 .Together, these results suggest that C-proxy is a practical and compute-efficient alternative, delivering significant performance gains comparable to those achieved with the memorization score. Detailed analysis of the use and appropriateness of various memorization proxies and their effect on RUM can be found in [37] .We report ToW and MIA with different orderings in Tables 16a and 16b . We find that, while ToW is similar for different orderings, MIA can vary. To better understand these dynamics, we inspect the accuracies on S and its subsets after each step in Figure 5 for SalUn F on CIFAR-10 and in Figure 13 for NegGrad+ F CIFAR-100. The former reveals why SalUn F with low → med → high order greatly outperforms vanilla SalUn. Recall that we identified in Section 4.2 that SalUn "overforgets" low-mem examples (its forget accuracy is lower than that of retraining). We observe from Figure 5 that future steps of the sequence neutralize that overforgetting effect on low-mem, leading to better ToW (see Figure 3 ). Interestingly, in line with our previous insights (Section 4.2), we find (from both Figures 5 and 13 ) that it is hard to cause the "low-mem" accuracy to become low and stay low. NegGrad+ does not drop it for any order of execution; SalUn drops it in the first ordering, but that drop is later reversed. We leave it to future work to further study these sequential dynamics and their helpful or harmful effects on Tow and MIA. The fact that MIA results differ based on the sequence may tie in with the recently-identified "privacy onion effect" [6] . 16a ).Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: The experimental setting and details are described in Section 6 in the main paper and in Section A.2. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
discussion and conclusion: 
 We presented the first investigation into interpretable factors that affect the difficulty of unlearning. We found that unlearning gets harder i) the more entangled the forget and retain sets are in embedding space and ii) the more memorized the forget set is. Our investigation led into uncovering previouslyunknown behaviours of state-of-the-art algorithms that were not surfaced when considering random forget sets: when do they fail, when do they excel and when do they exhibit different trends from each other. Notably, we discovered that relabelling-based methods suffer disproportionately as the embedding-space entanglement increases, and exhibit a reverse trend compared to other methods in their behaviour for different memorization levels. Armed with these insights, we then proposed the RUM framework surfacing new (sub)problems within unlearning, whose solution may lead to greater performance. Finally, we derived specific instantiations of RUM and analyzed how its different components can improve performance. We found that sequential unlearning of homogenized forget set subsets improves all considered state-of-the-art unlearning algorithms and investigated the dynamics of sequential unlearning to glean insights as to why that is. We also found that we can further boost performance by selecting the best unlearning algorithm per subset.Efficiency How is this important aspect affected in our sequential framework? We remark that it depends on the unlearning algorithm. For instance, applying Fine-tune three times is much more expensive than applying it once, because Fine-tune performs (at least) one epoch over the entire retain set. But for other algorithms the overall cost does not increase significantly. Further, a key observation from our results is that we can do well by actually doing nothing on a subset of the forget set, which can really boost efficiency (especially since the vast majority of examples are "low mem"). Additionally, our results with the C-proxy demonstrate that significant performance improvements in unlearning can be achieved with minimal computational cost, avoiding the heavy expense of computing memorization scores.Data-space vs embedding-space outliers How does the embedding space entanglement interact with the level of memorization of the forget set? We analyzed this and found in Table 3 that all of our memorization buckets have relatively high ES, indicating that separating out (data-space) outliers in the forget set doesn't lead to lower entanglement between the two sets in the embedding space. We leave it to future work to study the interaction of these factors.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments? Answer: [Yes] Justification: The paper reports the results with 95% confidence intervals and provides error bars, which appropriately reflect the statistical significance and variability of the experimental findings. This ensures that the reliability and significance of the results are clearly communicated.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: The paper provides detailed information on the computational resources used for the experiments in A.2. This ensures that other researchers can accurately reproduce the experiments.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss this is Section A.1.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no significant risks for misuse of data or models. Therefore, specific safeguards are not necessary.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: The paper does not involve crowdsourcing nor research with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We hope future work explores other refinement strategies (e.g. for a notion that captures embedding-space entanglement) and investigates privacy implications of sequential RUM, e.g. in terms of the "privacy onion effect" [6] . We also hope to see how our RUM framework can be adopted and adapted for unlearning in LLMs, especially given the findings from the contemporaneous paper [2] where unlearning is performed only on the highest-memorized examples in the forget set (albeit, memorization is defined differently for LLMs). We hope our framework continues to enable progress in understanding and improving unlearning and that our identified factors of difficulty and associated behaviours of existing algorithms continue to improve the state-of-the-art and inform the development of strong evaluation metrics that consider forget sets that vary in terms of relevant identified characteristics.A Appendix / supplemental material Training details for original models We trained four models across different datasets and architectures: ResNet-18 on CIFAR-10, ResNet-50 on CIFAR-100, ResNet-18 on Tiny-ImageNet, and VGG-16 on Tiny-ImageNet. For CIFAR-10, the ResNet-18 model was trained for 30 epochs using the SGD optimizer. The learning rate was initialized at 0.1 and scheduled with cosine decay. For CIFAR-100, the ResNet-50 model was trained for 150 epochs using the SGD optimizer, with the learning rate initialized at 0.1 and decayed by a factor of 0.2 at epochs 60 and 120. For Tiny-ImageNet, the ResNet-18 model was trained for 80 epochs, and the VGG-16 model was trained for 100 epochs, both using the SGD optimizer with an initial learning rate of 0.1 and cosine decay. All models were trained with a weight decay of 0.0005, a momentum of 0.9, and a batch size of 256. Additionally, data augmentations, including random cropping and random horizontal flipping, were applied during training on CIFAR-100 and Tiny-ImageNet. All training was conducted on Nvidia RTX A5000 GPUs.Training details for machine unlearning To ensure optimal performance, we carefully set the hyperparameters for each unlearning method across different datasets and architectures. For retrainfrom-scratch, we followed the exact same training procedure as the original model, but only trained on the retain set, excluding the forget set. In our experiments with forget / retain set partitions at varied levels of memorization or ES, we tuned the hyperparameters to achieve the best ToW performance for each unlearning algorithm. The results are reported as averages with 95% confidence intervals over 3 runs, except for relabeling-based methods, which had higher variance and were therefore run 6 times. For the RUM experiment, we adjusted the hyperparameters at each step to ensure that the accuracy after each step closely matched the accuracy obtained by retraining from scratch. This procedure was repeated for all algorithms, with results reported as averages over 3 runs with 95% confidence intervals.To create retain / forget partitions with varied levels of ES, we followed a systematic procedure. Initially, we trained the original model θ o on the entire training dataset D train . Using θ o , we then extracted embeddings for each data point in D train . The global centroid for D train , denoted as µ, was determined by calculating the mean of all example embeddings. For each example i in D train , we then computed its l2-distance from the global centroid µ in the original model's embedding space as follows:d(i, µ; θ o ) = ||φ i -µ|| 2We ranked these distances for all data examples in D train and selected the 3000 examples with the highest distances to form the low ES bucket. Subsequently, we moved further down the ranked list, selecting 3000 examples with progressively lower distances to form the medium and high ES buckets, until we achieved the desired levels of ES variation. This approach allowed us to form forget sets, each with a size of 3000, categorized into low, medium, and high ES levels. The rationale behind this selection is that examples with high distances from the global centroid are considered "distant" from the overall data distribution in the embedding space and are therefore less entangled with the rest of the dataset, i.e., the retain set. Various unlearning algorithms were then deployed on θ o across different forget / retain partitions. Their performance was measured using ToW along with forget, retain, and test accuracy, as well as MIA.This procedure enabled us to create retain / forget partitions with varying ES values. The ES values for our low, medium, and high ES partitions are shown in Table 2 . As observed from the table, the ES values increase from low to high ES partitions for both CIFAR-10 and CIFAR-100, confirming the effectiveness of our procedure. We also use Maximum Mean Discrepancy (MMD) [18] , a widely-used metric, to further validate ES. The MMD is computed as follows: Given a pre-trained model θ o (the original model in our case) trained on D train , we first extract features for the forget set S and the retain set R using θ o , denoted as φ(S) and φ(R), respectively. We then apply an RBF kernel to map these features to another space H such that φ (S), φ (R) ∈ H. The MMD between φ(S) and φ(R) is then calculated using the following formula:MMD 2 (φ(S), φ(R)) = 1 |S| i∈S φ i - 1 |R| j∈R φ j 2 HOur experiments reveal a negative correlation between ES and MMD scores, as reported in Table 2 .For CIFAR-10/ResNet-18 and CIFAR-100/ResNet-50, low (high) ES values correspond to high (low) MMD values, supporting the consistency of the ES.Additionally, Figure 6 presents the data representation of low, medium, and high ES partitions, confirming that the degree of entanglement between the retain and forget sets aligns with the computed ES values. As we move from low to high ES partitions, the forget set (yellow) and the retain set (blue) become increasingly entangled. This indicates that higher ES partitions reflect greater complexity in distinguishing between the two sets.We adopted a MIA based on prediction confidence, following the procedure described by [26] . To conduct this attack, we first sampled equal-sized data from the retain set and the test set, using these to train a binary classifier as the MIA model. This model is designed to distinguish whether a data example was involved in the training stage or not.Next, we applied this attack model to the forget set to evaluate unlearning performance during the testing phase, after an unlearning method was implemented. Intuitively, for successful unlearning, we want forget set examples to be classified as "non-training" data. We define "training" data as the positive class and "non-training" data as the negative class, and measured the performance of MIA by calculating the ratio of true negatives (i.e., the number of the forgetting samples predicted as following the same procedure as prior work [26] .EQUATIONIn this context, S ⊆ D train represents the forget set and |S| is the total size of this set. The term T N S denotes the number of true negatives predicted by the MIA model, indicating examples identified as "non-training" data. This metric ranges from 0 to 1, with higher values signifying a larger portion of the forget set predicted as "non-training" data. The ideal MIA score, for an unlearing algorithm, is one that matches the MIA score of retraining-from-scratch. Note that, even if applying this MIA on retrain-from-scratch, some portion of the forget set will be classified as "training data" due to heavily resembling the retain set (e.g. examples that are not really memorized may have similar confidences regardless on whether or not they were trained on). And we want the model confidences of the unlearned model to resemble as closely as possible those of retrain-from-scratch. For this reason, we additionally report the "MIA gap" (the absolute differentce between the MIA score for unlearning compared to that of retrain-from-scratch) as a easier-to-interpret metric, where lower is better, and the ideal score there is 0.Building on the MIA setup above, we introduce another metric "ToW-MIA" to evaluate unlearning performance, similar to ToW described in Section 4. The metric is defined as follows:ToW-MIA(θ u , θ r , S, R, D test ) = (1 -dm(θ u , θ r , S)) • (1 -da(θ u , θ r , R)) • (1 -da(θ u , θ r , D test ))where m(θ, D) represents the MIA performance of the model θ trained on D, as defined in Equation performance on S between the unlearned model θ u and the retrained-from-scratch model θ r . This term is the key distinction between ToW and ToW-MIA, where "forget quality" is measured by MIA (ToW-MIA) rather than accuracy (ToW). The other two terms remain identical to those in ToW (see the equation in Section 4), representing the absolute difference in accuracy between θ u and θ r on R and D test , respectively, which reflect "model utility". Like ToW, ToW-MIA rewards unlearned models that approximate the performance of the retrained model across the forget, retain, and test sets. ToW-MIA ranges from 0 to 1, with higher values indicating better unlearning performance. Figure 7 show the same trends with ToW-MIA as for ToW, both for unlearning difficulty analysis and RUM. More detailed results using ToW-MIA can be found in Table 14 .Building on our discussion in Section 4, we identify two factors that affect the difficulty of unlearning: the entanglement between the forget and retain sets, and the memorization level of the forget examples. This raises the question: how do these two factors interact with each other? Are the outliers in data space the same as those in embedding space? Our findings in this section suggest that these factors are indeed distinct.We analyzed the memorization scores within each forget set categorized by different ES values. Figure 8 shows the distribution and average memorization scores in the forget sets of low, medium, and high ES categories. It can be seen that each ES category's forget set contains a mix of memorization levels. Specifically, while the mean memorization score of forget examples increases from low to high ES categories, the memorization scores still span the entire range from 0 to 1.We examined the ES values for each memorization category to understand the entanglement between the forget and retain sets in the embedding space. Table 3 presents the ES values corresponding to low, medium, and high memorization buckets.The findings reveal that all the memorization bucket exhibits relatively high ES, suggesting that separating outliers in the data space does not reduce the entanglement between the forget and retain sets in the embedding space. These findings demonstrate that embedding space entanglement and the memorization level of the forget set are distinct concepts, not merely different aspects of the same phenomenon.To improve the efficiency of calculating memorization scores, we leverage insights from previous works [23, 32] and introduce a model confidence-based metric, referred to as the C-proxy, which serves as a proxy for the memorization score. The computation of the C-proxy proceeds as follows:For each data point (x i , y i ) ∈ D, we track the softmax probability of the model's prediction θ(x i ) for the ground-truth label y i across all training epochs, as the model θ is trained on D using algorithm A. These probabilities are then averaged over all epochs at the end of training to capture the training dynamics.Table 4 presents the fidelity (measured by Spearman correlation) and efficiency (measured by additional computational cost) of the C-proxy in relation to memorization. This evaluation is conducted on both CIFAR-10 and CIFAR-100 datasets. As shown, the C-proxy demonstrates a strong negative Spearman correlation with memorization scores while significantly reducing computational overhead compared to both computing memorization scores and retraining the model from scratch. This suggests that the C-proxy is an effective proxy for memorization while also offering substantial efficiency gains. Figure 4a and Figure 9 present results across different datasets and model architectures, demonstrating that the pattern identified in Section 4.2 remains consistent when using the C-proxy instead of the memorization score. Specifically, the lower the C-proxy value, the harder it is to unlearn (note that the C-proxy is negatively correlated with memorization). Furthermore, Figure 4b and Figure 10 show the results of RUM F across various datasets and model architectures, using the C-proxy in place of memorization for the refinement step described in Section 5. More detailed results, including accuracy and MIA, are available in Table 17 . These results demonstrate that RUM F still achieves a significant unlearning performance gain when C-proxy is used, comparable to those obtained with the memorization score. A detailed analysis of various memorization proxies, their suitability, and their impact on RUM can be found in [37] .While accuracy is a commonly used metric in the unlearning literature [29] , it reflects an average over a data distribution and may overlook finer details. To gain a more granular understanding of the similarities/differences between the unlearned model and the retrained model, we examine their behavior at the level of individual examples. Specifically, we collect predictions from both models for each example and count the examples where their predictions differ. Table 5 presents these results for a representative setting: CIFAR-10 dataset with ResNet-18 architecture.We observe that, in all cases, the percentage of disagreements between the unlearned and retrained models remains low. For highly memorized data (which typically makes unlearning harder), the disagreement rate increases but stays modest, ranging between ca. [7%, 15%]. For low-memorized data, the disagreement rate is lower, within ca. [3%, 5%].Interestingly, for the vast majority of unlearning algorithms, these per-example disagreement trends align with those observed using ToW: low-memorized examples are generally easier to unlearn, as indicated by both ToW and the lower disagreement rate, while high-memorized examples are harder to unlearn, with higher disagreement rates. A similar trend is observed across different ES levels as well. This consistency between average accuracies (ToW) and per-example disagreements supports the robustness of our findings and underscores the validity of ToW as a measure of unlearning difficulty. In this section, we show the results that were used to construct all figures in the paper, as well as additional results and analyses.The first factor affecting unlearning difficulty, as discussed in Section 4.1, is the degree of entanglement between the forget and retain sets in the embedding space. Specifically, the more entangled these sets are, the harder it becomes to unlearn. We present detailed results on how this factor affects unlearning difficulty in Table 6 , 7, 8, 9, 10 and Figure 11 . Table 6 displays the ToW results for different ES partitions across various settings, including CIFAR-10, CIFAR-100 and Tiny-ImageNet datasets, as well as ResNet and VGG architectures. Additionally, comprehensive data-covering forget, retain, and test accuracy along with MIA performance-are provided in Figure 11 and in Table 7 through Table 10 for these datasets and model architectures. All the results are averaged over 3 runs for each algorithm (6 runs for relabelling-based algorithms due to their higher variance), along with 95% confidence intervals.In Section 4.2, we discussed another critical factor affecting unlearning difficulty: the memorization level of the forget examples. Specifically, when a forget set consists of examples that are more highly memorized by the model, it becomes more difficult to unlearn (for most algorithms). The detailed results that support this observation are presented in Table 11 , Table 12 , Table 13 , and Figure 12 .Table 11 illustrates the ToW for forget sets with varying memorization levels. Additionally, Figure 12 and Table 12 to Table 13 provide extensive data on forget, retain, and test accuracy, as well as MIA performance. For all the experiments, the average results are reported with 95% confidence intervals over 6 runs for relabelling-based algorithms and 3 runs for others.We present the details of our RUM experiment in this section. Figure 11 : Forget, retain, test accuracy and MIA performance for forget / retain partitions with varied ES, for CIFAR-10 using ResNet-18 and CIFAR-100 using ResNet-50. As the ES increases, there is a notable decline in forget accuracy and a significant rise in MIA performance. This trend indicates that as the forget and retain sets become more entangled, more information from the forget set is effectively removed after unlearning.Tables 16 provide detailed results when applying RUM to different unlearning algorithms for CIFAR-10 using ResNet-18 and CIFAR-100 using ResNet-50. We selected the top-performing algorithms from previous experiments (i.e., Fine-tune, L1-sparse, NegGrad+, SalUn) and applied the refinement strategy to each algorithm in three ways: i) "vanilla": unlearning S in one go, ii)"shuffle": sequentially applying the algorithm on 3 equal-sized random subsets, serving as a control experiment, iii)"RUM F ": sequentially applying the algorithm on 3 subsets of S in low → med → high memorization order. Each experiment was conducted 3 times, with average values and 95% confidence intervals reported.Our results indicate that RUM F improves the performance of each unlearning algorithm, and the full RUM approach, which uses the best algorithm for each subset, achieves the overall best results.Furthermore, to gain a deeper understanding of the dynamics involved in applying RUM, we plotted the sequence dynamics for SalUn RUM F on CIFAR-10 (Figure 5 ) and NegGrad+ RUM F on CIFAR-100 (Figure 13 ). These plots show the accuracy of the entire forget set, the retain set, the test set, and subsets of the forget set after each step. They demonstrate that while both orderings (low → med → high and high → med → low memorization) yield similar ToW according to Table 16 , their sequence dynamics during the unlearning phase are different. This phenomenon is discussed in Section 6 in the main paper, specifically in the Analysis of Sequence Dynamics paragraph. Table 16 : RUM results on CIFAR-10 and CIFAR-100. Results obtained by applying RUM with different algorithms, according to ToW (higher is better), its constituent ingredients, and MIA (lower is better for MIA gap). The top section compares applying an unlearning algorithm U in three ways: i) in one-go, as usual (e.g. Fine-tune), ii) on three randomly-determined equal-sized subsets of S, sequentially (e.g. Fine-tune shuffle), and iii) on three equal-sized buckets obtained by refinement F(S) according to memorization scores, in low → med → high order (e.g. Fine-tune RUM F ). The middle section of Table 16a further experiments with picking a different unlearning algorithm for each subset of F(S). Here A → B → C denotes applying algorithm A on the first subset, B on the second subset, and C on the third subset, where the subsets appear in low → medium → high order.The bottom section shows different orderings. Justification: The paper includes a dedicated "Discussion and conclusion" section that discuss the limitations of the work. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Justification: The research adheres to the NeurIPS Code of Ethics, ensuring compliance with ethical standards in terms of data usage, experiment conduct, and the overall research process. Anonymity and confidentiality have been maintained where required, and all ethical considerations have been duly addressed.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 


Decision: This paper looks at the machine unlearning problem — roughly, given a model m and a subset of the data (the “forget set”) used to train that model, efficiently create a new model m’ that does not include information from the forget set but is representative of the family of models that would’ve been trained on the initial data sans the forget set (the “retain set”).  This is a known tricky problem, and a well-motivated one due to so-called “right to forget” capabilities enforced in the EU’s GDPR and other evolving regulatory movements.  The paper finds that if the forget and retain sets are close, in some sense, then the unlearning problem becomes harder.  It also finds that, if elements of the forget set are fundamentally part of the model itself via memorization, then the unlearning problem becomes harder.  Neither of these results are particularly surprising, but the analysis is strong and this is great to have written down.  The paper then provides a new method based on these two insights that arguably improves unlearning over various SotA and SotA-adjacent methods.  Reviewers found issue with the experimental analysis, as well as some nitpicks around the identified sources of hardness, but these were largely assuaged in the rebuttal and post-rebuttal discussion.

Reviews: review: paper_summary: paper_summary: This paper investigates the characteristics of forget data for machine unlearning algorithms and demonstrates their impact on the effectiveness of various unlearning methods. The paper further proposes refining the forget set into subsets based on data characteristics and selecting suitable unlearning algorithms for each subset. The experimental results show that this ensemble method outperforms single baselines.
strength_weakness: strength_weakness: * Despite the significance of the insights about sample embeddings, they appear somewhat limited to classification models, which typically have an embedding space to group different samples. While this may be beyond the scope of this paper, it would be valuable to explore extending these investigations to generative models, such as diffusion models and transformer-based large language models (LLMs).
* The experiments were conducted only on two CIFAR datasets, both involving image classification tasks. Including other tasks or datasets, such as text sentiment or topic classification, would make the paper more comprehensive.
* Although the paper claims the RUM framework is a meta-algorithm framework, the selection of unlearning algorithms for each subset is now based on empirical investigation and human-designed heuristic, which limits the generalizability of this method.

minor: I would recommend refining Figure 2, as some text is misaligned and mixed with the box boundaries.
questions: questions: * What is the model accuracy before unlearning in experiments?
* What's the criteria to group samples into low/medium/high partitions?
limitations: limitations: Authors discussed the limitations.
paper_summary: paper_summary: This paper studies how two properties of “forget sets” make machine unlearning hard: similarity/entanglement between the forget set and an accompanying retain set, and a memorization score for the forget set. The authors hypothesize and experimentally confirm that (1) high entanglement makes unlearning harder, likely due to it being hard to learn a model that forgets data that is so close to retain data, and that (2) more strongly memorized data is harder to forget, because models that memorize such data tend to be quite different from models than models that never see that data. Building on these observations, the authors propose a new algorithm for unlearning that first rank-orders forget data in terms of memorization scores, then selects an unlearning algorithm from a pool of algorithms that achieves the best ToW scores on data with the relevant level of memorization (as determined by previous analysis experiments). Results suggest that sequential forgetting based on forget set memorization achieves immediate improvements over whole-set forgetting, and that leveraging unlearning algorithms with good known ToW scores also improves results.
strength_weakness: strength_weakness: - Important: The ToW metric seems very reasonable at first glance but has some worrying issues on further thought. Mainly, the fact that this metric compares average accuracies across a data distribution is problematic. Consider that two models could disagree on many individual data predictions while achieving the same overall accuracy. Thus, an unlearning algorithm could yield a very different model from $\theta^r$ while still achieving good ToW. I like that the metric balances three different desirable quantities, similar to a harmonic mean, but it seems better to balance existing, accepted metrics from the literature, like empirical measurements of divergence between unlearning/original model predictions, MIA, extraction attack success, and accuracy on retain and held-out test sets. Analysis in the paper is only conducted in terms of ToW (Sec 4).
- Important: Results on MIA could be stronger. It appears that the refinement step accounts for most/all of the gains here, which is basically unexpected given the previous analysis in the paper. Improvements on ToW are positive, which would be good for the paper, if I didn’t have some skepticism around the ToW metric described previously.
- Important: Conducting all experiments with ResNet models on CIFAR datasets limits the generalizability of the results. While a breadth of unlearning methods are considered, I think evaluations should be conducted with other datasets and architectures too to ensure generalizability of the results.
- Of some importance: This is a personal opinion: I find the focus on unlearning in the differential privacy vein to be the wrong approach for many unlearning settings. I think it makes sense for users requesting their data not be used in training, and for model developers assuring approximate compliance with this request. I think it doesn’t make sense for unlearning private or dangerous information from models. The paper mentions extraction attacks once in the related work section, but extractability seems like it should be the core metric for unlearning to me. We either want a model to get a datapoint correct or get the datapoint wrong. Whether or not it was used for training seems inconsequential much of the time (one exception is when model developers owe people money for using their data). Reading this paper, this tension appears often. For instance, lines 242-246 reveal that unlearning algorithms can get worse ToW scores when they lower accuracy on a forget set too much, echoed in L.252-253 (cf. “overforgetting”). How can you overforget a forget set? I don’t like this problem formulation. I prefer defining forget sets as data where we want extraction attacks to fail, with retain sets being data where we want high model accuracy, and whether MIAs work on retain data is a matter of user data *access* (not privacy per se, since low-mem data might be relabeled accurately by models with high confidence, even when users do not grant access for training). All this said, I recognize that DP-based definitions for privacy remain popular in unlearning research, so I factor this point into my final score with less weight.
questions: questions: - Since the retain set is like training data, do you think it would be better to exclude it from ToW? 
- Entanglement score: there might be variance in a direction that seems irrelevant to whether the two distributions overlap. I feel that some MMD or classifier-based score could be better here. What do you think?
- In Fig1b, why is Original so low for medium and high memorization retain sets?
- typo: ln171: will cause accidentally erasing
limitations: limitations: I think it is becoming increasingly important to evaluate methods on settings beyond CIFAR+ResNet. This setting is becoming a bit dated compared to current applications of CV or other ML methods. Of course you can’t evaluate on everything, but if the experimental setting is this specific, it could be noted. 

On broader impacts, a current (negative) dual use scenario for unlearning techniques is to remove the influence of important safety data from finetuned models, e.g. https://arxiv.org/pdf/2310.03693. I think unlearning work should generally be aware of this scenario.
paper_summary: paper_summary: This paper looks at measurable qualities of forget/retain sets in machine unlearning contexts, which can make it difficult to 1) unlearn the forget set at all 2) unlearn the forget set without also unlearning the retain set. The paper puts forward well-reasoned metrics that get at entanglement/homogeneity in the embedding space for the forget and retain set, and also examine memorization as a possible factor for complicating machine unlearning. Based on the lessons from this, the paper suggests a meta-learning algorithm to figure out how to use existing unlearning algorithms to better unlearn the forget set.
strength_weakness: strength_weakness: Overall, I think this paper makes excellent contributions to unlearning science. There is one thing I would have liked to see addressed in  more detail in the main paper, and I have some nit comments (that do not affect my score) that I think would improve readability. I organize my response here according to these distinctions, to (hopefully) make it clear which things could possibly lead to improvements in my score. 

**Affects my score, engaging with this could lead to me increasing my score**

Given how expensive unlearning methods tend to be still, it would be great to see more discussion about efficiency. It is not clear to me entirely from the main paper if there are significant associated costs of using this meta-learning approach. These costs might be entirely worth the benefits presented (depending on the context of use, of course), but it would be really useful to include more on this in the main paper.

However, I also note that this paper packs in so much already in the page count, that I understand why some things had to be cut.  
But this also led to other problems (which I understand are in tension with what I'm saying about including more details about efficiency): the quantity of presented results for a paper of this length has demanded really small (often difficult to read and process) tables and figures. The reason this is important is not just about readability. It takes a lot more time as a reader to unpack and verify the results in relation to the claims being made. 

**Nit comments, do not have an impact on my score**

Math readability: Using different symbol classes for things of different types could help readability of the definitions a lot in this paper. For example, curly braces are used here for both algorithms and sets of datapoints. A simple improvement would be to use visual cues in the format to show they're different (not just with the chosen letter). For example, using bolded capitalization for a matrix of examples. Doing this can also make editing/finding typos more noticeable (e.g., line 60 has an $S$ for the forget set that, with the current style/format, should be $\mathcal{S}$).

Please explicitly define $e$ in the follow-on to Definition 2.1
questions: questions: See weaknesses -- It would be great to understand more about efficiency and if there are interesting trade-offs here with respect to the proposed method
limitations: limitations: See above re: efficiency analysis
paper_summary: paper_summary: This paper studies the difficulty of unlearning with respect to different unlearning sets. Specifically, the authors examine two factors, namely entanglement between forget and retain sets, and memorization. The authors further propose a framework called RUM which first divides the forget set into different subsets according to the memorization score and performs different unlearning algorithms to unlearn each subset.
strength_weakness: strength_weakness: I will merge the weaknesses and my questions in this part such that the authors can easily address each point during the rebuttal:

**[Memorization]**: according to equation (1) and Section 4.2, it appears to me the authors perform "leave-one-out" experiments, where they train a model without a target data sample and calculate the memorization score in (1). This is repeated for every training data point (50000 times for CIFAR-10) and it seems quite expensive (if training until convergence). My questions here are: 
- Did you use any approximation in your experiments? How many epochs did you train? Can you show the computational cost?
- In Section 6, the refinement step is also performed based on memorization scores. Thus I believe the calculation of memorization score should be also considered for "efficiency" in Section 7? Given a large model (e.g., LLMs), and a large forgetting set, this process would be extremely expensive and may decrease the practicality of RUM.

**[MIA and ToW]**: The authors use ToW as the only evaluation in Section 4 and apply both MIA and ToW for Section 5. It is unclear to me why they omit MIA for evaluating unlearning difficulty. Is it because MIA may be a biased evaluation? Sequentially, for step 3 in RUM, will the selection of optimal unlearning algorithm be affected by considering MIA as well?

**[Transferability]**: RUM relies on the observation in Section 4 to select optimal unlearning algorithms. This comes handy as Section 4 and 6 both consider the same datasets. However, in practical scenarios, this is not possible and one needs to rely on the assumption that one unlearning algorithm is optimal across different datasets and model architectures. Is this assumption true? 

**[Title and Section 4]**: The title of this paper and name of Section 4 "what makes unlearning hard" is misleading to me. This presentation suggests that the authors are studying: (1) unlearning is a hard problem; (2) why it is hard. However this is not true and they actually studied "the difficulty of unlearning regarding choice of forgetting sets". Specifically, the memorization subsection actually suggests different behaviors for different unlearning methods. I would suggest a more accurate delivery such as "on the difficulty of unlearning...".

**Overall**, I like the problem of interest in this paper and I appreciate the takeaways from Section 4. I think the observations help the community understand unlearning better. However, I don't believe RUM is a super practical framework based on the tremendous effort needed to perform refinement and the unknown behavior of transferability. If any of my speculations are wrong I would love to hear back from the authors.
questions: questions: See above.
limitations: limitations: Limitations are addressed.

Comments: title: Final communication
Adding onto between-reviewer discussion
Additional reply to rebuttal
Response to rebuttal, other reviewers
Answers to new questions of reviewer 3Cxb
Addressing reviewer 7Yis new questions
Reply to rebuttal
comment: Dear reviewer 7Yis,

As the deadline is approaching, please let us know if there are any other concerns.

Thank you.
I will raise my score if this becomes necessary as a matter of record to advocate for accepting this paper. I hope this is not the case in discussion with the AC, since I think a 7 is fair (I personally would save 8 for the very small % of papers that warrant spotlights/orals).
Dear reviewer 3Xcb

Thank you for your comments.
We assure you we will provide the additional discussion on the issues pertaining to example-level performance and our relevant results. We view this as an issue going beyond our paper - an important issue for future related work to consider going forward, thus affecting the community's research effort.

Thanks!
Dear reviewer HxTF: 

Even though you are not raising your score (as we had hoped), we sincerely appreciate your time, effort, and comments -especially as you tried to tie many together. It is gratifying to see reviewers with this level of dedication and devotion to scientific work!

Thanks a lot!
Thanks HxTF for tying our responses together. Quick note:

>Per-example forgetting results would be interesting and useful, but in my mind are not a blocker for publication of the existing work.

I agree with your assessment of my original review, and following the discussion with the author, I am convinced that the paper does make a reasonable contribution on the methods front (probably improving MIA by 3-5 points following their analysis + new method). My biggest concern remains with the example-level comparison. I basically think that aggregating accuracy across datapoints before comparing between models is clearly flawed, since the ToW metric could look good for models that produce very different distributions in practice (and I think pairs of neural models are often like this in practice). The authors convince me that this doesn't totally undermine their contribution, and I raised my score correspondingly, but I would strongly recommend to sort out this issue with the metric or otherwise provide substantial discussion and results in the appendix if they choose to keep the original formulation in the main body of the paper.
>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.
Thank you for your thoughtful rebuttal. Your comments and results on efficiency address the majority of my concerns. Thank you for providing these details, I think they make for a stronger paper.

I believe that this paper clears the bar for acceptance. I maintain my belief that a score of 7 is appropriate, since I think the work would make for a great poster. I have not assigned a higher score for this reason, but note that I am willing to fight for this paper's acceptance (if necessary, though it seems like it is not tending in that direction).

I would to address some comments from other reviewers, which the authors have also addressed. I want to do so in support of their rebuttal. Forgive me if this is, as a result, a bit repetitive. I want to show places where I agree and disagree. 

*Reviewer Bp7U*

> Despite the significance of the insights about sample embeddings, they appear somewhat limited to classification models, which typically have an embedding space to group different samples. While this may be beyond the scope of this paper, it would be valuable to explore extending these investigations to generative models, such as diffusion models and transformer-based large language models (LLMs).

Machine learning remains about much more than LLMs. While I think the authors have provided a good rebuttal about doing unlearning on classification as being more generally useful (and while I understand why they may have engaged in a rebuttal like this), I don't think this was necessary. Having great results on classification is a contribution on its own. This paper doesn't need to touch LLMs to make useful contributions.

>  The experiments were conducted only on two CIFAR datasets, both involving image classification tasks. Including other tasks or datasets, such as text sentiment or topic classification, would make the paper more comprehensive.

I want to support what the authors have said about this. Having done work in this area, it is tremendously expensive. (Related concerns can also be read in my own questions about efficiency -- this type of work is really expensive to do, so it's good to report on this. It also explains why experiments might be done on CIFAR, as opposed to other things). This probably should be listed as a limitation of the work, but is not in my opinion grounds for rejection.

 *Reviewer 3Cxb*

I think that this reviewer raises important methodological questions about how machine unlearning success is measured in general in the field. In my opinion, the authors have done a good job of contextualizing challenges in the field in their rebuttal, in relation to the presented work. Such discussion is great for the field, and perhaps should go in the Appendix. Nevertheless, based on the comparisons and work done here, I still think that this paper pushes forward the state-of-the-art -- in a field for which there remains a lot of debate about how to measure success for unlearning. 

That is, while Reviewer 3Cxb raises some excellent points, I do think some of them read as critiques of uncertainty in the field of unlearning, and apply more generally than they do for this specific paper. This paper, in the allotted 9 pages, does a lot to try to improve rigor on measuring unlearning. It is, in my opinion, serving to provide more rigor in this still relatively unclear space. This in my mind serves to improve some of the challenges of unlearning, as articulated by this reviewer. 

Per-example forgetting results would be interesting and useful, but in my mind are not a blocker for publication of the existing work.

 *Reviewer 7Yis*

I agree with the assessment that this paper ultimately helps clarify what makes unlearning hard perhaps more than what to do about it. I similarly think this is a sufficient contribution for publication as a poster.
Thank you for engaging with us.

We are glad to see that we have addressed your concerns regarding efficiency.

We are very keen to engage further to resolve your other remaining concerns (regarding our claim that unlearning in LLMs is a substantially different problem with different definitions for the problem itself and for key concepts like memorization, and with different SOTA algorithms).  

Please do get in touch if there is anything else we can do to help alleviate any remaining concerns.

Thanks again.
**“Re: …adjusting the core metric to avoid … bias. …  it seems like a measure of bias could be as high as 15%.”**

We created ToW as a reasonable metric that holistically captures a notion of "difficulty" in a scalar, **to allow for efficient analyses and investigations into unlearning difficulty**. The reviewer’s point about looking at disagreements at the example level rather than average accuracy is a great one! As far as our goals were concerned with respect to using ToW as a tool to measure unlearning difficulty, we actually see the same trends with our initial framing of ToW compared to this example-based disagreement score! 

Concretely, for the vast majority of unlearning algorithms, we find according to ToW that low mem forget sets are easier. Correspondingly, we also observe that for low mem examples, the disagreement rate is also lower. On the other hand, higher mem examples are harder to forget, as shown by average accuracy (in original ToW) and indeed the disagreement rate is also higher. 
Given that our goal is to study trends, 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.

**Re: “To clarify, I was looking at MIA falling from 0.089 (L1 vanilla) to 0.059 (RUM). Is this a strong gain (and is it statistically significant)? Is this the comparison I should be looking at?”**

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). 

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.

**Re: “the paper is focused on how two factors could explain unlearning difficulty”, “a seemingly arbitrary factor (the ordering of data [...]) plays the biggest explanatory role.” and importance of data ordering.**

Thank you for the discussion! What we show with RUM is that operating on **homogenized subsets of the forget set** (obtained in the refinement step) yields big gains (over random subsets as in our Shuffle baseline), and further, that pairing each such subset with the most suitable unlearning algorithm yields further gains. The factors explaining difficulty (that we discover through analyses in Section 4) are what informs both the “refinement”, i.e. how we divide the forget sets into subsets (using memorization levels), as well as how to pick the most suitable unlearning algorithm per subset.

Now, RUM (as presented in the paper) makes the design decision of operating sequentially on refined subsets, which introduces this additional variable of the ordering, as the reviewer points out. 
Our work shows **the existence of orderings** that can yield large gains in unlearning pipelines. We hope future work extends our work to yield even larger gains in RUM, including a thorough investigation of the data ordering which is a very interesting component (but well beyond the scope of this work). 

**Overall and proposed adjustments to the paper:**
We sincerely wish to thank Reviewer 3Cxb: (i) for engaging fruitfully and thoroughly with us and (ii)  for their insightful comments that have already improved our paper.

We are happy that 3Cxb appreciates the results with ToW-MIA, the example disagreement experiments, adding TinyImageNet and VGG-16 and acknowledges that, while unlearning definitions and subproblems may differ, the variant we study here is widely recognized as valuable.

Taking reviewer 3Cxb’s comments to heart, we propose the following: When introducing ToW, we will clarify our motivation behind this metric (studying difficulty via a reasonable and informative scalar value), but we will also discuss variations of it in two axes: (i) per-example disagreement rate (unlearning vs retraining) in addition to average accuracy, and (ii) defining ToW-MIA (using MIA gap for forgetting quality, instead of forget accuracies). We will add sections in the Appendix to each of those points, showing the results of additional investigation in response to the reviewer’s feedback. We note that all of these variants show the same trends, which we will also note in the main paper, and we believe supports the robustness of our conclusions further. 
We thank the reviewer for bringing up these points which (we had not thought of and) strengthen our work.

Please let us know if you would require anything else?

Again, thanks!
Dear reviewer 7Yis, thanks a lot for your meaningful engagement. Please see below for answers to your questions:

**Re: Leave-one-out... and “Can you provide a rough estimate on the CIFAR-10/ResNet experiment?”**

Indeed, with C-proxy, running time is not an issue. Specifically, the running times of the two algorithms are as follows:
- For computing Feldman’s memorization scores, we had to train 450 models! Training one model takes ca. 15 minutes. We used 4 GPUs, with the total time taking ca. **1,500 minutes**.

- Computing C-proxy, on the other hand (which is done during the training of the original model) adds ca. 2.5 seconds per epoch, for a total of ca. **one minute of overhead**!

This is a drastic difference in running times, showing negligible overhead for computing C-proxy, and negligible resource requirements. These facts allow us to claim that our contributions are practicable!

**Re: What makes unlearning hard: I like this clarification … and … about the title**.
 
We hope the above explanations help alleviate the original concerns about the practicability of our contributions (and the resulting concerns about the title). 

Again, thanks a lot for your positive feedback to our rebuttal. Please let us know if you have any other questions.
Thanks for the detailed reply, I have read the rebuttal. My major concern about the efficiency is resolved by the new C-proxy method. I would maintain the current positive rating.
Dear Authors,


Sorry for the late reply, I was pretty occupied for the last few days. I have carefully read your rebuttal and additional experiments. And here are my further comments:

- [**Leave-one-out**]: Leave-k-out makes sense and the new C-proxy experiments look great to me. You mentioned there is an order of magnitude improvement over Feldman's method in terms of efficiency. Still, I am curious about the comparison between the running time of the two algorithms. Can you provide a rough estimate on the CIFAR-10/ResNet experiment?

- [**What makes unlearning hard**]: I like this clarification but I still think the current title could be a bit over-simplified. My suggestion is something like "What properties make data hard to unlearn". This is not critical though and I can also accept the paper with its current title.

In summary, all the other concerns are well addressed. While I still think the contribution of "what makes unlearning hard" is more significant than "what to do about it", I am willing to recommend acceptance. I will adjust my ratings after another round of discussion with the authors.


7Yis
Thanks for the response! Replies below.

> **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.
    
Thanks for the response to (1). I would recommend adjusting the core metric to avoid any possible bias in results. If I’m reading the response correctly, it seems like a measure of bias could be as high as 15%. For (2), I think ToW-MIA is a good idea and appreciate the additional results.
    
> 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.
    
To clarify, I meant unexpected here as in, the paper is focused on how two factors could explain unlearning difficulty, and then the results show that a third and seemingly arbitrary factor (the ordering of data into subsets based on memorization scores) plays the biggest explanatory role. The bulk of the paper does not concern data ordering. Why is data ordering important for unlearning? A whole different paper could be written on this (the paper points to [5] for relevant work). 
    
> 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).
    
To clarify, I was looking at MIA falling from 0.089 (L1 vanilla) to 0.059 (RUM). Is this a strong gain (and is it statistically significant)? Is this the comparison I should be looking at?
    
> **Re: limited to ResNet and CIFAR**. We address this point by adding an additional dataset and architecture. 
    
Adding VGG-16 with Tiny ImageNet is an improvement
    
 >….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.
    
I agree. It’s a minor point I wanted to make. I suspect that as the public learns more about ML + data privacy/deletion, there will be a shift towards extraction attack metrics over DP metrics, but I can’t deny that this is a legitimate and longstanding problem setting.
    
> **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).
    
Thanks for the clarification. The argument makes sense to me. I get the feeling the terminology in the field (not just in the paper) could be tightened up a bit, because it is a little unintuitive to speak of “overforgetting” a forget set. (Forget sets should be forgotten!)
    
> **Re: should we exclude retain set from ToW?** The retain set is important. For instance...
    
Right, that makes sense.
    
> We experimented with MMD and find there exists a (negative) correlation between ES and MMD scores. 
    
Thanks!
    
> **Re: “why is original so low for medium and high memorization retain sets”**...Please let us know if this clarification helps.
    
Got it, thanks!
    
---

Based on the above discussion, I am prepared to increase my score if the authors can (1) reformulate the ToW metric to measure example-level changes in model predictions and not changes in average accuracy alone, and (2) clarify the strength of evidence there is for improved MIA.

I would still point out that there is something confusing to me about this paper regarding the refinement step. The analysis in the paper focuses on memorization and entanglement, not data ordering. But then data ordering turns out to be very important for the improvements in unlearning in the proposed method.