Towards Understanding the Feasibility of Machine Unlearning

Thank you very much for your feedback. Below is our response to the concerns and questions you raised.

Regulatory Implications

This paper aims to introduce a new research direction focused on investigating the feasibility of unlearning. to understand the factors that influence the feasibility of unlearning data, specifically in a manner that is agnostic to any particular unlearning algorithm. The main focus is on the evaluating the feasibility of unlearning and understanding the relation through the lens of KSD based scoring, but we didn't invest in designing unlearning algorithm using the KSD scoring even the potential exist. The regulatory implications of "machine unlearning" in relation to the "feasibility of unlearning" are beyond the scope of this research and are left for future exploration. We encourage further research to investigate these aspects in greater detail.

Rigorous Unlearning Objective

To ensure that unlearned data is removed from the model, we explored the Membership Inference Attack efficiency. MIA efficacy is quantified by the ratio of samples predicted as "forgotten samples" (True Negatives TN) to the total number of samples in the forgetting set $|\mathcal{D}_f|$. The MIA-efficacy reflect the effectiveness of unlearning, where higher MIA-efficiency implies less information about samples unlearned $D_f$ , indicating more successful unlearning outcome. This criteria is reported in Table 2., and full statistical analysis in Table 8.

Baseline Comparisons and Additional Techniques

The primary contribution of this paper lies in exploring the "Feasibility of Machine Unlearning" before diving into investigating the unlearning algorithm. Previous works have rushed into providing the new machine unlearning approaches, without solid understanding about the unlearning feasibility of data. However, this research direction has a great potential to invite future research into the feasibility of unlearning, providing a robust basis for algorithm development.

Although the Influence function is one of the most mathematically solid base feature attribution method, it is significantly expensive and incomparable w.r.t the KSD which has great potential for understanding and exploring the data-model distribution.

Impact of Unlearnability Scores

As discussed later, the primary goal of this study is to understand the factors contributing to the feasibility of data unlearning, with particular emphasis on investigating this feasibility challenge independently of specific unlearning algorithms. The practical application of KSD-based scores for implementing unlearning algorithms lies beyond the scope of this research and is left for future exploration. Instead, the focus is directed towards evaluating the feasibility of unlearning and analyzing its relationship through the perspective of KSD-based scoring. While the potential for designing unlearning algorithms using KSD-based scoring exists, our research does not pursue that direction.

Additionally KSD is measured as the $\mathbb{E}_{x, x' \sim q} [\kappa_p(x, x')]$ any changes to the data samples (unlearning and removing any subset of $\kappa_p$ from the data from) damage the calculated KSD. We employ the KSD as the measurement of model distribution, therefore, we can estimate each of their contribution. Removal of any subset of data will significanly damage the KSD meaning. It is not trivial to apply the KSD for unlearning; hwoever, the insight for the potential approach on employing KSD for unlearning is only using the Scoring Heuristic to select the easy and difficult samples for unlearning.

Empirical evaluation

From the literature[1, 2], we noticed that these two methods are most common practice and considered to be the most effective unlearning algorithms. Rather than tailoring our approach to a specific unlearning algorithm, we aimed to highlight an overlooked challenge in previous studies and establish a new research direction. Still as part of our evaluation, we conducted Membership Inference Attack to investigate whether the unlearned model carries the influence of unlearned sample after the unlearning and how it varies between an easy vs difficult to unlearn sample.

We hope that in the future research, the potential of KSD based scoring metric be employed for the evaluation of privacy and adversarial attacks.

[1] Model Sparsity Can Simplify Machine Unlearning. Jinghan Jia et al. NeurIPS 2023.

[2] Gundavarapu, Saaketh Koundinya, et al. "Machine Unlearning in Large Language Models." arXiv preprint arXiv:2405.15152 (2024).

Reference Clarification

For the experimental evaluation and the unlearning algorithms, we adhered strictly to the design framework recommended by [H]. We wanted to ensure that the validity of our experimental evaluations and guarantees that our KSD-based scoring metrics remain entirely independent of the specific unlearning settings.

Overfitting threshold

The overfitting threshold is a mechanism introduced specifically for GradAscent during the unlearning process. Without this control, GradAscent can lead to a significant increase in the error rate, rendering the results invalid. To address this issue, we define a cap on the model's error for the forget set, referred to as the overfitting threshold. This threshold prevents the unlearning loss from becoming excessively high, which mitigates the risk of distorting the unlearned model. In particular, unlearning a single data point with GradAscent requires careful control to ensure the process is effective. By applying this threshold cap, we aim to prevent excessive error growth while preserving the overall quality of the model.

Feasibility of unlearning for NLP

At this stage of our research, we have completed experimental evaluations on the image classification dataset. As a subsequent step, we aim to extend our investigation to examine the feasibility of unlearning in natural language models and their corresponding datasets.

Citations

We are so thankful for your feedback, we addressed them in the revised version of the paper.

References

[A] Towards Unbounded Machine Unlearning. Meghdad Kurmanji, et al. NeurIPS 2023.

[B] SalUn: Empowering Machine Unlearning via Gradient-Based Weight Saliency in Both Image Classification and Generation. Fan, Chongyu, et al. ICLR, 2024.

[C] Can bad teaching induce forgetting? unlearning in deep networks using an incompetent teacher. Vikram S Chundawat et al. AAAI 2023.

[D] Eternal sunshine of the spotless net: Selective forgetting in deep networks. Golatkar et al. CVPR, 2020.

[E] Certified data removal from machine learning models. Chuan Guo, et al. ICML, 2020.

[H] Model Sparsity Can Simplify Machine Unlearning. Jinghan Jia et al. NeurIPS 2023.

[I] Evaluating Machine Unlearning via Epistemic Uncertainty. Alexander Becker et al. ECML 2021.

[J] Machine Unlearning of Pre-trained Large Language Models. Jin Yao et al. ACL 2024.

[K] Gundavarapu, Saaketh Koundinya, et al. "Machine Unlearning in Large Language Models." arXiv preprint arXiv:2405.15152 (2024).

[L] Jamie Hayes, Ilia Shumailov, Eleni Triantafillou, Amr Khalifa, and Nicolas Papernot. Inexact unlearning needs more careful evaluations to avoid a false sense of privacy, 2024.

Thank you very much for your feedback. Below is our response to the concerns and questions you raised.

Experimental results

To assess the effectiveness of the proposed scoring metrics and to explore whether the feasibility of unlearning differs across data points, we selected the top five easiest and the top five most difficult samples to unlearn, as determined by the rankings from each scoring metric. The primary focus of our experimental evaluation is on unlearning individual data points, with the corresponding results presented in Table 1.

We have conducted the GradAsct in very careful and controlled process. The parameter setting are given in the Appendix - Table 4. Also the scoring metrics ranks datapoints based on the closeness to the decision boundary and similar samples which influence on the difficulty of unlearning.

All of unlearning algorithms have been tested on the top 5 easy / difficult samples for 5 times with 5 random seed to avoid any cherry picking. The reported unlearning accuracy in Table.1 are only for individual sample unlearning.

1- Unlearning Accuracy:

• Easy
  • Majority of unlearning algorithms achieved zero accuracy on the forget set $S_F$ (Figure 2, Appendix Table 6.)
  • The Predictive accuracy of model on the remaining $S_R$ and test $S_T$ subsets almost remained similar to the original model [Table 6]
  • Exact unlearning (retraining) of an easy sample is achievable (Table 1, Forget Accuracy)
• Difficult
  • The models' performance was jeopardized (reduction on accuracy by nearly 50 percent on test data for CIFAR10 // Figure. 2., Table. 1. ) or didn't result in successful unlearning (no change to the accuracy of model on the forget set Table 1) (zero difference before and after unlearning )

Additional unlearning baselines

We have conducted the experiments on the Fisher algorithm and the results are reported in the appendix. We also conducted the exact unlearning (retraining from scratch ) to compare the scoring metrics and ensure that our assessments of easy / difficult to unlearn is align with the exact unlearning. From the literature[H, K], we noticed that these two methods are two of the most common practice and effective unlearning algorithms. We didn’t want to engage with tailoring our approach to unlearning algorithm. Our goal is introducing an existing challenge that has been ignored by the previous methods and creating a new branch of research.

We emphasize that the primary contribution of this paper is the investigation of the "feasibility of machine unlearning" before diving into investigating the unlearning algorithm. Previous works have rushed into providing the new machine unlearning approaches, without solid understanding about the feasibility of data. However, this research direction has a great potential to invite the future research on the feasibility of unlearning.

Expansion of Scoring metrics application

This paper focuses on positioning the concept of unlearning within the broader research landscape, and aims to rise the community awareness on the challenges reserved for this problem. We discussed the factors influencing the feasibility of unlearning on data samples and introduce a KSD-based scoring metric that is independent of any specific unlearning algorithm. Also the six factors that are contributing to the unlearning difficulty can also be evaluated for any unlearning algorithms. From the feedback highlighted from reviewers, we can observe the potential for a novel line of research on the feasibility of unlearning. The main contribution of this research is the introduction of feasibility of unlearning for the. Our paper is the baseline for the future research on the feasibility of unlearning and the researchers can employs our scoring metrics to the other methods.

Membership Inference Attack efficacy

We are thankful for your recommendation. We will address your feedback in the revised version. Here is the statement of how we calculated the “MIA efficacy”.

The criteria is quantified by the ratio of samples predicted as "forgotten samples" (True Negatives TN) to the total number of samples in the forgetting set $|\mathcal{D}_f|$. Since the post-unlearning, the model $\theta_u$ should have effectively "forgotten" the information related to the samples in the forgetting set.

Thanks for the authors' responses. I still have some concerns.

• As an experimental work proposing a metric, I remain concerned that focusing only on simple baselines such as Finetune and Gradient Ascent might restrict the applicability of the metric. The author claims, "We didn’t want to engage with tailoring our approach to unlearning algorithms," but conducting experiments only on these simple baselines is already tailoring your approach to the Finetune and Gradient Ascent algorithms. This could limit the paper's contribution to something along the lines of "Towards Understanding the Feasibility of Finetune/Gradient Ascent Unlearning." I believe that incorporating other actively researched methodologies, such as teacher-student frameworks [A], weight saliency [B], and Newton Update [E], would significantly strengthen the experiments. At the very least, like [H], the paper should test Newton Update [E], and the results of these methods should be presented in the main text rather than the appendix.
• The response did not explain why the GradAsct method in the paper achieves such strong performance, even on the most difficult samples to forget (reaching 0% accuracy on the forgetting set of the SVHN dataset while maintaining an accuracy of up to 80% on the test set). The results are too good to be reconciled with my own experience and outperform the results of NegGrad+ proposed by [A]. I would like to express concern that the authors have not conducted randomness experiments to demonstrate that the GradAsct method consistently achieves the claimed results.
• I still have concerns about the paper's literature review. I suggest that the authors carefully refine Section 2.2. I have reviewed the authors' updated paper again and still found some inaccuracies in the description of past literature, which could mislead readers who are not familiar with the machine unlearning field.
  • For example, in line 106, the goal of [D] is not "distinguishing the forget set from the remaining dataset," but rather ensuring that the scrubbing function $S(w)$ produces a model indistinguishable from one that has never seen the forget set (retraining from scratch), by minimizing the KL divergence between their distributions.
  • In line 112, it should not say "ensure a high probabilistic similarity between models before and after unlearning," but rather "ensure a high probabilistic similarity between the retraining-from-the-scratch algorithm and the unlearning algorithm." Please note that these two are fundamentally different definitions.
  • Additionally, Mehta et al. is repeated in line 106, and Izzo is repeated in line 111.
• Lastly, as an optional suggestion, since research on LLM unlearning has recently gained momentum, incorporating NLP tasks into the experiments, whether in the main text or the appendix, could further validate the proposed metric and enhance the paper's contribution and impact. I also suggest the authors will discuss how these ideas can help the machine unlearning community develop algorithms, rather than empirically stating which samples are difficult to forget. Nevertheless, this suggestion will not affect my scoring.

I believe the motivation behind this work is valuable, but the quality of the paper is not sufficient to meet the ICLR acceptance standards, so I maintain my score.

Unlearning difficulty and Scoring metrics

The the unlearning difficulty factors are categorized into two major groups namely 1) data points with/without strong ties (factor 1, 4-6) and 2) predictive confidence (factor 2-3). Our aim is to develop a unlearning difficulty scoring metric that jointly considers these two classes of factors. Two of those factors are purely dependent to the data-model distribution and are determined before unlearning the model.

• MKSD: evaluates both the immediate proximity of neighboring data points and the degree of strong similarities as reflected by elevated Stein Kernel values. A higher MKSD score indicates greater similarity and a larger "resistance set," meaning that a larger portion of the training data would need to be unlearned alongside the target data point. This scenario is typically undesirable as it increases the complexity of unlearning.

• MSKSD: The sum of the Stein Kernel values for each data point generally provides an indication of strong similarities with other samples within the dataset. However, this measurement can sometimes be misleading if negative values from other samples overshadow the positive similarities. This can result in positive and negative values negating each other. For this issue, we employ a standardization approach to the Stein Kernel values for each data point, denoted as $\kappa_{\theta}((\mathbf{x}_i, y_i), (\cdot, \cdot)$. By standardizing these values, we can prevent the negation effect, and sum the exponential values of the standardized Stein Kernels to properly value the positively correlated samples and avoid their cancellation with negative values.

• SSN: We propose that data points with high Stein Score Norms (SSN) are typically located further from the dense centers of their respective classes and closer to the decision boundary. The Stein Score, defined as $\nabla_a \log P_\theta$ is larger for samples near the decision boundary, making such points prime candidates for unlearning. These data points are evaluated and ranked based on the magnitude of their Stein Score vectors, These points are evaluated and ranked based on the magnitude of their Stein Score vectors $\nabla_{\theta} \log P_{\theta}(\mathbf{x}_i, y_i)$ . By identifying and prioritizing data points with the highest Stein Score Norms, we can efficiently target samples that are most susceptible to unlearning due to their proximity to the decision boundary.

• EMKSD In investigating unlearning algorithms, combining the uncertainty of the model's prediction with similarity data points.

Thank you very much for your feedback. Below is our response to the concerns and questions you raised. Also according to your recommendation, the new citation is added in the revised version of paper.

Discussion on Unlearning experimental results

• Accuracy:

  • Easy
    • Majority of unlearning algorithms achieved zero accuracy on the forget set $S_F$ (Figure 2, Appendix Table 6.)
    • The Predictive accuracy of model on the remaining $S_R$ and test $S_T$ subsets almost remained similar to the original model [Table 6]
    • Exact unlearning (retraining) of an easy sample is achievable (Table 1, Forget Accuracy)
  • Difficult
    • The models' performance was jeopardized (reduction on accuracy by nearly 50 percent on test data for CIFAR10 // Figure. 2., Table. 1. ) or didn't result in successful unlearning (no change to the accuracy of model on the forget set Table 1) (zero difference before and after unlearning )

• Unlearning Loss

  • For an easy to unlearn sample

    • The model Error on the forget set has increased Table. 1. & Table 7.
    • A noteworthy observation from comparing accuracy Table 6, and loss Table 7 is that for the easy-to-unlearn cases, when the unlearning process appears to have minimal impact on the model's predictive capability on the forget set. The models maintain the ability to predict these datapoints even after unlearning. However, including unlearned models' loss analysis of the loss table reveals that, despite the sustained accuracy, the unlearning process increases the models' loss on the forget set for easy-to-unlearn datapoints. This suggests that while the model can still predict the forget datapoints, the error threshold for flipping a datapoint’s label remains high.

  • Difficult

    • Unlearning has minimal to no impact on the model's error on the forget set, indicating that these datapoints are more resistant to unlearning. (Table. 7 )
    • For cases the unlearning negatively jeopardized the model accuracy, the unlearned model error is also reflected on the loss

• “Distance of Parameter Shift (DPS)”

  • The layer-wise distance between the original model and the unlearned model is shown in Table 5. Among the scoring metrics, EMSKSD exhibits the smallest distance on the model’s parameters, indicating that it causes less disruption during unlearning. On the other hand, SSN produces the largest gap, as anticipated. This is because SSN tends to select data points near the decision boundary, which typically have larger gradient magnitudes, thereby increasing the distance between the original and unlearned models.

• “Resistance to Membership Inference Attack (MIA)”:

  • The "easy" samples identified by EMSKSD consistently show higher MIA-efficacy, whereas "difficult" samples often with lower MIE-efficacy which clearly indicate the influence of difficult was not unlearned from the model.

Unlearning Feasibility: Insights from Experiments and KSD Scoring

Systemic analysis of easy - difficult samples recommended by KSD-based scores are tied to the six unlearning difficulty factors. How the evaluation of six factors differ between an easy vs difficult to unlearn:

The experimental results:

Predictive “Performance Shift”:

• Accuracy:

  • Easy
    • Majority of unlearning algorithms achieved zero accuracy on the forget set $S_F$ (Figure 2, Appendix Table 6.)
    • The Predictive accuracy of model on the remaining $S_R$ and test $S_T$ subsets almost remained similar to the original model [Table 6]
    • Unlearning by retraining of a single easy datapoint can achieve the zero accuracy on the forget set
  • Difficult
    • The models' performance was jeopardized (reduction on accuracy by nearly 50 percent on test data for CIFAR10 // Figure. 2., Table. 1. ) or didn't result in successful unlearning (no change to the accuracy of model on the forget set Table 1) (zero difference before and after unlearning )

• Unlearning Loss

  • Easy

    • The model Error on the forget set has increased Table. 1. & Table 7.
    • A noteworthy observation from comparing accuracy Table 6, and loss Table 7 is that for the easy-to-unlearn cases, when the unlearning process appears to have minimal impact on the model's predictive capability on the forget set. The models maintain the ability to predict these datapoints even after unlearning. However, including unlearned models' loss analysis of the loss table reveals that, despite the sustained accuracy, the unlearning process increases the models' loss on the forget set for easy-to-unlearn datapoints. This suggests that while the model can still predict the forget datapoints, the error threshold for flipping a datapoint’s label remains high.

  • Difficult

    • Unlearning has minimal to no impact on the model's error on the forget set, indicating that these datapoints are more resistant to unlearning. (Table. 7 )

• “Distance of Parameter Shift (DPS)”

  • The layer-wise distance between the original model and the unlearned model is presented in Table 5. Among the evaluated scoring metrics, EMSKSD demonstrates the smallest distance in the model’s parameters, indicating that it induces minimal disruption during the unlearning process. In contrast, SSN produces the largest distance, as expected. This result is attributed to SSN’s tendency to prioritize data points near the decision boundary, which generally have larger gradient magnitudes. Consequently, this leads to a greater divergence between the original and unlearned models.

• “Resistance to Membership Inference Attack (MIA)”:

  • The "easy" samples identified by EMSKSD consistently show higher MIA-efficacy, whereas "difficult" samples often with lower MIE-efficacy which clearly indicate the influence of difficult was not unlearned from the model.

Unification of unlearning factors

From the unlearning difficulty factors we categorize them into two major groups 1) data points with/without strong ties (factor 1, 4-6) and 2) predictive confidence (factor 2-3).Both of these characteristics are embedded from the original KSD formula (Formula 4.). The KSD formula unifies the raw feature similarity, closeness to the decision boundary (in terms of score similairy) and Mutual Influence of Prediction Shifts. Later the KSD-based scoring metric enhances these factors to ensure that all major controbuting factos for unlearning are considered effectively.

[1] Chen, Min, et al. "Boundary unlearning: Rapid forgetting of deep networks via shifting the decision boundary." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.

[2] Nguyen, Hieu T., and Arnold Smeulders. "Active learning using pre-clustering." Proceedings of the twenty-first international conference on Machine learning. 2004.

[3] Kienitz, Daniel, Ekaterina Komendantskaya, and Michael A Lones. "Comparing Complexities of Decision Boundaries for Robust Training: A Universal Approach." Proceedings of the Asian Conference on Computer Vision. 2022.

[4] Li, Chen, Xiaoling Hu, and Chao Chen. "Confidence estimation using unlabeled data." arXiv preprint arXiv:2307.10440 (2023).

Thank you very much for your feedback. Below is our response to the concerns and questions you raised.

Computational complexity

The computation complexity of MKSD, MSKSD, and EMSKSD is bounded by $O(n \times g^2)$ as aggeragation happens over all data which is multiplied by the complexity of $\kappa_\theta$ if bounded by gradient of $\nabla_a P_\theta$

For SSN, the computation complexity is bounded by the $\nabla_a P_\theta$ => $O(g)$.

For the experimental evaluation, we will conduct the experiments on the samples data and we will report the following experimental results in the revised version.

Difficulty aware unlearning algorithm

In this paper, the main goal is introducing a new research direction for investigating the feasibility of unlearning. Our intention is understanding the contributing factor on the unlearning feasibility of data and more importantly investigating this challenge agnostic to unlearning algorithms. Development of "Difficulty Aware Unlearning algorithm" seems a valubale and most immidiate application of our research, it is out of scope of our work and can be left for the future research. The main focus is on the evaluating the feasibility of unlearning and understanding the relation through the lens of KSD based scoring. We didn't invest in designing unlearning algorithm using the KSD scoring even the potential exist.

Additionally KSD is measured as the $\mathbb{E}_{x, x' \sim q} [\kappa_p(x, x')]$ any changes to the data samples (unlearning and removing any subset of $\kappa_p$ from the data damage the calculated KSD.
We employ the KSD as the measurement of model distribution, which helps us to estimate each of their contribution. Removal of any subset of data will significantly damage the true meaning of KSD. It is not trivial to apply the KSD for unlearning; however, the insight for the potential approach on employing KSD for unlearning can be noted as "employing the Scoring Heuristic to select the easy and difficult samples for unlearning".

Unlearning Feasibility and Scoring Metrics

We categorized the difficulty factors into two major groups namely 1) data points with/without strong ties (factor 1, 4-6) and 2) predictive confidence (factor 2-3). Our aim is to develop a unlearning difficulty scoring metric that jointly considers these two classes of factors.

For example, Size of Unlearning Expansion, as stated in [1] (Section.1 Right Column, 3rd Paragraph) in real world scenarios to forget a requested sample we need to unlearn the whole class. The correlation between similar samples, combined with the generalization strength of deep neural networks, can act as a significant resistance to unlearning a specific sample. The correlation and similarity among samples are inherently dependent on the model's distribution. The Stein Kernel provides a mechanism to quantify these correlations, conditioned on the model distribution. As illustrated in [1] (Section A.2, Figure 3), the pairwise Stein Kernel values between a target data point and its similar samples reveal how related samples are distributed across various classes. Typically, data points exhibit strong Stein Kernel correlations with relevant samples within the same class, while their similarity to samples from other classes diminishes significantly. This ability to distinguish intra-class and inter-class similarities underscores the utility of the Stein Kernel in understanding unlearning dynamics.

Geometric Distance to Decision Boundary: As stated in [1,2] (Section 1, Right Column, 3rd Paragraph) samples with the highest uncertainty are typically located closest to the classification boundary. Building on the ideas presented in [1], we infer that unlearning samples near the decision boundary is relatively easier compared to those situated at the center of clusters, which are more strongly tied to adjacent data points.

In [3] (Section 1, Page 2, 2nd Paragraph), it is discussed that robust classifiers tend to learn geometrically more complex decision boundaries. These robust models often assign significantly lower confidence scores to low-density samples near the boundary (Section 4.2, Page 10). Similarly, [4] highlights that data points farther from the decision boundary tend to have higher confidence, while those closer to the boundary exhibit lower confidence.

The Kernel Stein Discrepancy (KSD) plays a critical role in identifying this phenomenon. According to Formula 4, the Stein Score—defined as the gradient of the log probability density function—exhibits higher values for samples closer to the decision boundary, making it an effective metric for capturing and analyzing this concept.