Unrolling SGD: Understanding Factors Influencing Machine Unlearning

Anvith Thudi, Gabriel Deza, Varun Chandrasekaran, Nicolas Papernot

TL;DR

This paper tackles the challenge of "machine unlearning" – making a trained model forget specific data points without the prohibitive cost of retraining from scratch. The authors propose a new metric, "unlearning error," as a computationally cheaper proxy for "verification error" (the difference in weights between an unlearned and a retrained model). They also introduce a novel "standard deviation loss" that, when used during training, significantly reduces this unlearning error, making models easier to unlearn later with minimal performance degradation.

What Problem Does This Paper Address?

As machine learning models become more integrated into our lives, the ability to remove specific data points from their "memory" becomes crucial. This is driven by privacy concerns (like the GDPR's "right to be forgotten") and the fact that models can inadvertently memorize sensitive training data. The most straightforward way to achieve this is by retraining the model from scratch without the offending data point. However, for large deep learning models, this is computationally infeasible. Approximate unlearning methods aim to modify the existing model's weights to achieve a similar effect more efficiently, but they often lack clear metrics for success and can be difficult to optimize. This paper addresses the need for better theoretical understanding, practical metrics, and training strategies for efficient and effective machine unlearning.

Methods

The authors' core contribution lies in their theoretical analysis of Stochastic Gradient Descent (SGD). They expand SGD's update rule using Taylor series to isolate terms that are easily unlearned. This leads to two key developments:

  • Single Gradient Unlearning: A computationally inexpensive method to approximate unlearning by directly reversing the impact of a single data point's gradients.
  • Unlearning Error: A novel, easy-to-compute proxy metric for "verification error." Verification error, defined as the L2 distance between the weights of an approximately unlearned model and a naively retrained model, is identified as a unifying metric for many existing unlearning criteria. However, computing verification error is expensive. Unlearning error aims to capture the same essence without requiring a full retraining.

Furthermore, they propose a new training objective:

  • Standard Deviation (SD) Loss: This regularization term, added to the standard cross-entropy loss, encourages the model's final weights to be closer to the initial weights. This inherently limits the overall weight change during training, making subsequent unlearning operations (like single gradient unlearning) more effective and resulting in lower verification error.

Datasets

The authors evaluated their methods on the following datasets:

  • CIFAR-10: A standard benchmark for image classification.
  • CIFAR-100: A more challenging version of CIFAR with more classes.
  • IMDB sentiment analysis: A dataset for text classification, used with a pre-trained DistilBERT model.

Key Insights and Ideas

  • Verification Error as a Unifying Metric: The paper argues that verification error (L2 weight difference) is a strong metric that subsumes many other proposed unlearning criteria, providing a more principled way to compare different unlearning methods.
  • Unlearning Error as a Practical Proxy: The derived "unlearning error" is a crucial practical advancement, offering a way to estimate unlearning effectiveness without the cost of retraining. This allows for easier optimization and comparison of unlearning strategies.
  • Training Matters for Unlearning: The analysis reveals that the training process itself significantly influences how easily a model can be unlearned. Specifically, limiting the overall weight change during training is key.
  • SD Loss: A Simple Yet Effective Regularizer: The proposed SD loss is a surprisingly simple addition to the training objective that effectively reduces unlearning error and, consequently, verification error, with minimal impact on model accuracy. This suggests that making models "less volatile" during training is beneficial for unlearning.
  • Unlearning Error as a Good Proxy for Verification Error: Empirically, the paper demonstrates a strong correlation between unlearning error and verification error across various models, training setups, and unlearning methods, validating its utility.

Key Results

  • SD Loss Reduces Unlearning Error: Experiments show that training with the SD loss significantly decreases unlearning error. For instance, in some cases, it reduced unlearning error by up to 40x for DistilBERT.
  • Minimal Accuracy Drop: The SD loss achieved these unlearning benefits with only a minor decrease in test accuracy (typically less than 3 percentage points for vision models).
  • Strong Correlation: Unlearning error and verification error were found to be strongly correlated (Pearson coefficients often above 0.9) across different datasets, models, and training configurations.
  • Single Gradient Unlearning Reduces PRS: Applying their single gradient unlearning method consistently reduced Privacy Risk Score (PRS) by roughly 2x on average, indicating improved privacy against membership inference attacks.

Limitations and Future Work

  • Assumptions in Theoretical Analysis: The theoretical analysis of SGD relies on assumptions such as batch size 1 and negligible noise changes between steps, which might not hold for all practical scenarios.
  • Unlearning Error for Other Methods: While unlearning error showed strong correlations with verification error for their proposed method and amnesiac unlearning, its efficacy as a proxy for other unlearning methods needs further investigation.
  • "When is Unlearning Achieved?": The paper acknowledges that defining "when" unlearning is sufficiently achieved remains an application-dependent problem, rather than a purely technical one.
  • Architectural and Domain Dependencies: The authors note that some architectures and domains might be inherently easier to unlearn from, suggesting future work to pinpoint these features.
  • Improving SD Loss: Future work could explore refining the SD loss or developing adaptive regularization schedules.
  • Extending Bounds: Extending the theoretical bounds to cover more complex unlearning methods and relax current assumptions is a promising direction.

Summary updated

Abstract

Machine unlearning is the process through which a deployed machine learning model is made to forget about some of its training data points. While naively retraining the model from scratch is an option, it is almost always associated with large computational overheads for deep learning models. Thus, several approaches to approximately unlearn have been proposed along with corresponding metrics that formalize what it means for a model to forget about a data point. In this work, we first taxonomize approaches and metrics of approximate unlearning. As a result, we identify verification error, i.e., the L2 difference between the weights of an approximately unlearned and a naively retrained model, as an approximate unlearning metric that should be optimized for as it subsumes a large class of other metrics. We theoretically analyze the canonical training algorithm, stochastic gradient descent (SGD), to surface the variables which are relevant to reducing the verification error of approximate unlearning for SGD. From this analysis, we first derive an easy-to-compute proxy for verification error (termed unlearning error). The analysis also informs the design of a new training objective penalty that limits the overall change in weights during SGD and as a result facilitates approximate unlearning with lower verification error. We validate our theoretical work through an empirical evaluation on learning with CIFAR-10, CIFAR-100, and IMDB sentiment analysis.
BibTeX
@inproceedings{thudi2022unrolling,
  author = {Anvith Thudi and Gabriel Deza and Varun Chandrasekaran and Nicolas Papernot},
  title = {{Unrolling SGD: Understanding Factors Influencing Machine Unlearning}},
  booktitle = {EuroS\&P},
  year = {2022},
  doi = {10.1109/eurosp53844.2022.00027},
}
Figure