Instance-Level Difficulty: A Missing Perspective in Machine Unlearning

The gist Machine Unlearning research should pay attention to the instance-level difficulty (or even feasibility) of unlearning, as existing metrics often fail to assess individual data point removal effectiveness

Preliminaries

Machine Unlearning is defined as "the process of removing specific subsets of training data, along with their influence, from a trained model (Cao & Yang, 2015) . Ideally, the unlearned model should perform identically to a model trained from scratch on a pruned dataset. Existing research often measures success through two surrogate indices: Model Utility Retention and 2) Unlearning Effectiveness".

The common expectation for machine unlearning operations involves adjusting parameters to achieve two objectives: 1) Increasing of model’s error on the forget set Lϑ(Df) and "2) Maintaining original model’s error on the remainingset Dr such that ∥Lθ(Dr) − Lϑ(Dr)∥ < ϵ, where ϵ denotes a tolerable performance degradation threshold and L denotes the loss. Various research tracks exist, including Fine-Tuning (Warnecke et al., 2021) and Gradient Ascent (GA)(Graves et al., 2021)".

Factors that Affect Difficulty of Unlearning

The paper identifies four factors that pose challenges to unlearning operations, which are independent of the specific unlearning algorithm but relevant to the target model and its training data. These factors capture different types or definitions of unlearning difficulty, as the challenging samples identified by each factor exhibit notable diversity.

The four factors discussed are:

1. Tolerance of Performance Shift (TPS): This quantifies difficulty by imposing a strict requirement for guaranteed unlearning (Liu et al., 2024a). The analysis shows a strong positive correlation between the TPS and empirical unlearning outcomes, regardless of the unlearning algorithm employed.

2. Distance of Parameter Shift (DPS): This probes the layer-wise and activation-wise parameter shift distances. While it can be a reliable indicator for general gradient-based approaches, it may fail to accurately reflect unlearning difficulty when targeting specific neurons encoding unique properties of certain training data points.

3. Geometric Distance to Decision Boundary (GDDB): This metric measures the data point’s distance to the decision boundary. The analysis reveals no clear correlation between empirical unlearning difficulty and training data’s geometric distance to the decision boundary when removing a single data point.

4. Number of Unlearning Steps (NUS): This evaluates computational efficiency, where the increasing of unlearning epochs is positively correlated with the unlearning difficulty.

Quantifying Performance and Empirical Analysis

The ground-truth unlearning outcome (GT) for an individual data point is defined as a Harmonic average (FP-Score) over model’s performance shift on the forget set and remaining (or test) set in the form GT(A, Df) = λ ∗ U ∗ F. This metric is sensitive to worst-case outcomes, where a larger GT implies U → 1 and F → 1, indicating the unlearning of easy samples.

The empirical analysis focused on GA, NegGrad, SCRUB, and SalUn due to their broad applicability. The Spearman Correlation metric was used to assess the strength and direction of correlation between GT and the factors examined. For example, GA, NegGrad, and SCRUB largely exhibited the expected results, showing a strong positive correlation between test accuracy and GT.

Conclusion

The study concludes that four out of six factors examined can provide guidance on correctly identifying easy and difficult samples, which shows the need for understanding the difficulty of machine unlearning. The paper highlights a critical gap by emphasizing the variability in unlearning difficulty at the instance level. These findings call for more refined evaluation metrics that account for instance-level variability and open up new avenues for developing predictive tools to improve MU effectiveness. The paper suggests that unlearning difficulty is best reflected by post-unlearning model performance.

How it works

The analysis involves logging and analyzing the outcome of unlearning operations on each training data point from a trained model empirically. The study utilized four different unlearning algorithms and three benchmark datasets, including MNIST, CIFAR-10, and SVHN.

The researchers quantified the difficulty using metrics such as TPS, DPS, GDDB, NUE (Number of Unlearning Epochs), and MIA (Membership Inference Attack). The results demonstrated that a strong positive correlation between the TPS and empirical unlearning outcomes was observed across different algorithms.

The analysis also explored the relationship between size of unlearning expansion (SUE) and unlearning difficulty, finding no clear relationship between SUE and unlearning difficulty. The study found that for certain algorithms like SalUn, there is no clear correlation between DPS and GT.

Datasets and Models

The experiments were conducted on a ResNet-18 model trained on the SVHN dataset for some analyses, while other analyses were performed on CIFAR-10 and MNIST datasets. Table 2 details the specific models, layers, and learning rates used across these datasets to provide insight into the computational frameworks employed.

The top-performing and bottom-performing samples were identified for each unlearning algorithm based on metrics like Test Accuracy or Forget Loss Difference. These visualizations show how different algorithms handle easy and difficult samples across the datasets.

Resistance to Membership Inference Attack (MIA)

Resistance to Membership Inference Attack is employed to detect residual imprints of the forgetting set Df in the unlearned model(Chen et al., 2021) . Effectiveness is evaluated by the proportion of samples identified as ”forgotten” (True Negatives, TN) relative to the total size of the forgetting set Df. The results showed a positive correlation with ground truth (GT) where Easier samples, characterized by higher GT values, tend to be unlearned more effectively.

The overall finding is that machine unlearning research should pay attention to the instance-level difficulty (or even feasibility) of unlearning. The four identified factors can quantify unlearning difficulty but are impractical for predicting outcomes before execution, highlighting the need for a unified difficulty index. The impact statement emphasizes that this paper highlights a critical gap in machine unlearning (MU) research by emphasizing the variability in unlearning difficulty at the instance level.

References

Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C. A., Jia, H., Travers, A., Zhang, B., Lie, D., and Papernot, N. Machine unlearning. In 2021 IEEE Symposium on Security and Privacy (SP), pp. 141–159

Cao, Y. and Yang, J. Towards making systems forget with machine unlearning. In 2015 IEEE symposium on security and privacy, pp. 463–480

Chen, H., Zhu, T., Yu, X., and Zhou, W. Machine unlearning via null space calibration.

1. textbfModel Difficulty Prediction Index Development: Implement a unified difficulty index to forecast unlearning results before execution, addressing the research gap that Currently, no proven effective index exists in the literature. This index should combine factors like Tolerance of Performance Shift (TPS) and others to quantify instance-level difficulty for a specific target model and its training data.

2. textbfAdaptive Unlearning Strategy: Develop an unlearning algorithm that dynamically adjusts its approach based on the predicted instance-level difficulty, as suggested by the paper's finding that the four identified factors capture different types or definitions of unlearning difficulty. This system would select appropriate methods (e.g., favoring SalUn for samples with high Forget Predictive Probability Difference) to optimize both forgetting and preservation objectives.

3. textbfCost-Effective Unlearning Scheduling: Integrate the Number of Unlearning Steps (NUS) metric into the deployment pipeline to estimate computational efficiency, as the paper observes that the increasing of unlearning epochs is positively correlated with the unlearning difficulty. This allows for setting realistic time and resource budgets for individual data point removal requests.

4. textbfMembership Inference Attack Resilience: Design models that are intrinsically resistant to Membership Inference Attacks by focusing on minimizing residual imprints, as indicated by the finding that Easier samples, characterized by higher GT values, tend to be unlearned more effectively. This ensures that the unlearned model no longer retains information about the forgetting set.

5. textbfContext-Aware Unlearning Expansion: Implement a mechanism to determine if Size of Unlearning Expansion (SUE) is necessary, as the paper notes that to achieve optimal results, it is essential to process both Dr and Df, even though SUE showed no clear relationship with unlearning difficulty. This guides the system on whether expanding the forget set is required for guaranteed unlearning success.

Current research on deep machine unlearning primarily focuses on improving or evaluating the overall effectiveness of unlearning methods while overlooking the varying difficulty of unlearning individual training samples. As a result, the broader feasibility of machine unlearning remains under-explored. This paper studies the cruxes that make machine unlearning difficult through a thorough instance-level unlearning performance analysis over various unlearning algorithms and datasets. In particular, we summarize four factors that make unlearning a data point difficult, and we empirically show that these factors are independent of a specific unlearning algorithm but only relevant to the target model and its training data. Given these findings, we argue that machine unlearning research should pay attention to the instance-level difficulty of unlearning.