What makes unlearning hard and what to do about it

Kairan Zhao, Meghdad Kurmanji, George-Octavian Bărbulescu, Eleni Triantafillou, Peter Triantafillou

Machine unlearning—the process of scrubbing the influence of specific training data from a model—is increasingly vital for privacy compliance (like GDPR's "right to be forgotten") and removing poisoned data. However, it is notoriously difficult because deep neural networks are highly non-convex; you can't just "subtract" a data point's contribution from the weights.

In their NeurIPS 2024 paper, Zhao et al. move beyond evaluating unlearning on random data subsets. They identify the specific characteristics that make data hard to forget and propose a new meta-algorithm, RUM, to tackle these challenges.

TL;DR

The authors identify two primary factors that make machine unlearning difficult: embedding-space entanglement and data memorization. By partitioning "forget sets" into homogeneous groups based on these factors and applying tailored algorithms sequentially, their Refined-Unlearning Meta-algorithm (RUM) significantly boosts the performance of existing state-of-the-art unlearning methods.

What Problem Does This Paper Address?

Most unlearning research evaluates algorithms on random subsets of data. The authors argue this is a "blind spot" that masks real-world complexity. In practice, a user might request the deletion of a specific, highly unique image (an outlier) or a set of images that are very similar to data the model needs to keep.

The core challenge is the "balancing act": how do you erase the "forget set" ($S$) without damaging the model's performance on the "retain set" ($R$) or its ability to generalize to new test data? The authors seek to understand why certain data is harder to forget and how current algorithms (like Fine-tuning, NegGrad, or SalUn) behave differently depending on the nature of the data being removed.

Methods

The researchers first define two metrics to characterize unlearning difficulty:

  1. Entanglement Score (ES): Measures how "mixed up" the forget and retain sets are in the model's penultimate layer (embedding space). If they are highly entangled, erasing $S$ risks accidentally erasing $R$.
  2. Memorization Score: Quantifies how much the model's prediction on a specific example depends on that example being in the training set. Atypical examples or outliers usually have higher memorization scores.

To evaluate success, they use a "Tug-of-War" (ToW) metric, which rewards models that closely match the accuracy of a model retrained from scratch on the forget, retain, and test sets.

Uncovering two factors that affect unlearning difficulty: Entanglement and Memorization.

The RUM Framework

Based on their findings, they propose the Refined-Unlearning Meta-algorithm (RUM):

  • Step 1: Refinement. Partition the forget set $S$ into $K$ homogeneous subsets based on memorization or entanglement.
  • Step 2: Meta-Unlearning. Apply a sequence of unlearning operations. Crucially, RUM allows for choosing the best algorithm for each specific subset (e.g., doing nothing for low-memorized data and using specialized relabeling for high-memorized data).
Figure 2: Overview of RUM.

Datasets

The authors evaluated their approach using standard image classification benchmarks:

  • CIFAR-10 (ResNet-18)
  • CIFAR-100 (ResNet-50)
  • Tiny-ImageNet (ResNet-18 and VGG-16)

They also utilized Membership Inference Attacks (MIAs) to verify that the unlearned data truly appears "unseen" to an external observer.

Key Insights and Ideas

  • Entanglement is a Trap: When forget and retain sets are entangled in embedding space, unlearning becomes a zero-sum game. Relabeling-based methods (like SalUn) perform particularly poorly here because forcing an incorrect label on a forget-set point causes its "neighbors" in the retain set to be misclassified as well.
  • Memorization is a Double-Edged Sword: Highly memorized examples are harder to unlearn for most methods. However, relabeling-based methods actually excel at removing highly memorized data, while they "overforget" (damage utility) on low-memorized data.
  • Sequential Homogeneity Wins: Simply shuffling the forget set and unlearning in chunks doesn't help. However, unlearning homogenized subsets sequentially (e.g., low-mem $\rightarrow$ medium-mem $\rightarrow$ high-mem) allows the model to stabilize, leading to better final utility.
  • Efficiency via C-proxy: Calculating full memorization scores is expensive. The authors show that C-proxy (average softmax probability of the correct label during training) is a highly effective, low-cost substitute.

Key Results

RUM consistently outperformed "vanilla" versions of every unlearning algorithm tested.

RUM improves the performance of various unlearning algorithms compared to vanilla and shuffle baselines.
  • Performance Boost: On CIFAR-10, RUM improved the ToW score of Fine-tuning from ~0.85 to ~0.94 and SalUn from ~0.73 to ~0.89.
  • Algorithm Selection: The best results came from a "mixed" RUM strategy. For example, on CIFAR-10, using "No Unlearning" for low-mem data, "Fine-tuning" for medium-mem, and "SalUn" for high-mem data achieved a near-perfect ToW score of 0.965.
  • Privacy: RUM significantly reduced the "MIA gap," making the unlearned model nearly indistinguishable from one that had never seen the forget set.

Limitations and Future Work

  • Computational Overhead: While RUM improves quality, sequential unlearning can be more time-consuming than a single-pass approach, especially for methods like Fine-tuning that require multiple epochs.
  • Factor Interaction: The authors found that separating outliers in data space doesn't necessarily reduce entanglement in embedding space, suggesting these two difficulty factors are distinct and require further study on how they interact.
  • Scalability to LLMs: While the framework is general, the specific refinement strategies (like ES) need to be adapted for the massive scale and different architectures of Large Language Models.

Summary updated

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.
BibTeX
@inproceedings{zhao2024what,
  author = {Kairan Zhao and Meghdad Kurmanji and George-Octavian Bărbulescu and Eleni Triantafillou and Peter Triantafillou},
  title = {{What makes unlearning hard and what to do about it}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=QAbhLBF72K},
}
Figure