Algorithms that Approximate Data Removal: New Results and Limitations

Vinith Menon Suriyakumar, Ashia Camage WilsonNeurIPS 2022 · OpenReview

Abstract & TL;DR

This paper introduces a highly efficient "online" machine unlearning algorithm based on the Infinitesimal Jackknife (IJ). It significantly reduces the computational cost of deleting user data from trained models—especially those using non-smooth regularizers like $L_1$. Furthermore, the authors expose a critical vulnerability in current unlearning paradigms, proving that existing methods fundamentally fail to unlearn data if the model's hyperparameters were originally selected using cross-validation.

The Machine Unlearning Dilemma

As privacy regulations like GDPR and CCPA grant users the "Right to be Forgotten," machine learning practitioners face a complex dilemma: how do you "delete" a user's data from a model that has already been trained on it?

The gold standard is retraining from scratch, but this is prohibitively expensive in terms of time and compute. "Approximate unlearning" aims to update the model weights to look as if the data was never there without full retraining. However, existing methods have two major gaps:

  1. Efficiency in the Online Setting: Previous Newton-based methods require re-calculating and inverting a massive Hessian matrix for every single deletion request, which is computationally bottlenecked.
  2. Non-Smooth Objectives: Most methods assume the loss function is perfectly smooth, making them incompatible with popular, sparsity-inducing techniques like Lasso ($L_1$ regularization) or Elastic Net.

Methodological Innovations

The authors leverage the Infinitesimal Jackknife, a classic tool from robust statistics, to estimate how model parameters change when specific data points are removed.

  • Hessian Reuse: Unlike prior "Taylor Approximation" (TA) methods that invert a new Hessian for every deletion, the IJ approach computes and inverts the Hessian only once on the full dataset. Subsequent deletion requests are handled using simple matrix-vector multiplications. This reduces the "online" removal of $m$ points from $O(md^3)$ to $O(md^2)$.
  • Proximal Newton Step: To handle non-smooth regularizers (like the $L_1$ penalty), the authors incorporate a proximal operator. This allows the algorithm to maintain the sparsity or structure of the original model while still performing the unlearning update.
  • Certified Removal: The algorithm adds a small amount of Gaussian noise to the updated weights to provide $(\epsilon, \delta)$-unlearning guarantees, ensuring the output is statistically indistinguishable from a model retrained from scratch.

Key Insights and The "Hyperparameter Trap"

  • The "One-and-Done" Hessian: The most surprising insight is that the Hessian calculated on the full dataset is a sufficiently good approximation for many subsequent deletions. This is the secret sauce behind their massive speedups.
  • The Hyperparameter Trap: Perhaps the most important contribution is the "Failure Mode" analysis. The authors prove that if you use cross-validation (CV) to pick your regularization parameter ($\lambda$), the value of $\lambda$ itself leaks information about the data. Even if you "unlearn" the model weights, the fact that you are using a specific $\lambda$ chosen by the old data means you haven't truly removed the user's influence. Unlearning isn't just about the final training step; it’s about the entire data pipeline.

Empirical Results

The authors evaluated their algorithm across distinct scenarios, including smooth $L_2$ regularization (MNIST), non-smooth $L_1$ regularization (Warfarin), and non-convex settings (SVHN with DP feature extractors).

Massive Speedups (MNIST): On the MNIST dataset, the IJ algorithm demonstrated remarkable efficiency. It was 2611x faster than retraining from scratch (RT) and 2045x faster than previous state-of-the-art approximate unlearning methods (TA), while maintaining test set accuracy even under adaptive deletion requests.

MNIST Speedup and Accuracy

Non-Smooth Success (Warfarin): On the Warfarin clinical dataset (using $L_1$ regularization), the algorithm successfully handled the non-smooth objective. It was 30x faster than retraining while maintaining nearly identical test accuracy over hundreds of deletion requests.

Warfarin Speedup and Accuracy

Theoretical Parity: Despite being orders of magnitude faster, the algorithm matches the "deletion capacity" (the number of points you can delete before the model degrades) of much slower existing methods.

Limitations and Future Work

  • Convexity Constraints: The core theoretical guarantees still rely on the objective function being (mostly) convex. While the authors show a workaround using DP feature extractors for deep learning, a direct "unlearning" method for raw deep neural networks remains a challenge.
  • The Pipeline Problem: The paper highlights that we currently have no way to "unlearn" the influence of data on hyperparameter tuning. Future work needs to develop unlearning-compliant versions of cross-validation.
  • Poisoning Vulnerability: Like many online algorithms, this method could potentially be susceptible to poisoning attacks where a user provides malicious data and then requests its deletion to manipulate the model's trajectory.

Summary updated

Abstract

We study the problem of deleting user data from machine learning models trained using empirical risk minimization (ERM). Our focus is on learning algorithms which return the empirical risk minimizer and approximate unlearning algorithms that comply with deletion requests that come in an online manner. Leveraging the infintesimal jacknife, we develop an online unlearning algorithm that is both computationally and memory efficient. Unlike prior memory efficient unlearning algorithms, we target ERM trained models that minimize objectives with non-smooth regularizers, such as the commonly used $\ell_1$, elastic net, or nuclear norm penalties. We also provide generalization, deletion capacity, and unlearning guarantees that are consistent with state of the art methods. Across a variety of benchmark datasets, our algorithm empirically improves upon the runtime of prior methods while maintaining the same memory requirements and test accuracy. Finally, we open a new direction of inquiry by proving that all approximate unlearning algorithms introduced so far fail to unlearn in problem settings where common hyperparameter tuning methods, such as cross-validation, have been used to select models.
BibTeX
@inproceedings{suriyakumar2022algorithms,
  author = {Vinith Menon Suriyakumar and Ashia Camage Wilson},
  title = {{Algorithms that Approximate Data Removal: New Results and Limitations}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=G4VOQPYxBsI},
}
Figure