Remember What You Want to Forget: Algorithms for Machine Unlearning

By Ayush Sekhari, Jayadev Acharya, Gautam Kamath, Ananda Theertha Suresh. 2021

475 citations recorded by the source corpus.

We study the problem of unlearning datapoints from a learnt model. The learner first receives a dataset $S$ drawn i.i.d. from an unknown distribution, and outputs a model $\widehat{w}$ that performs well on unseen samples from the same distribution. However, at some point in the future, any training datapoint $z \in S$ can request to be unlearned, thus prompting the learner to modify its output model while still ensuring the same accuracy guarantees. We initiate a rigorous study of generalization in machine unlearning, where the goal is to perform well on previously unseen datapoints. Our focus is on both computational and storage complexity. For the setting of convex losses, we provide an unlearning algorithm that can unlearn up to $O(n/d^{1/4})$ samples, where $d$ is the problem dimension. In comparison, in general, differentially private learning (which implies unlearning) only guarantees deletion of $O(n/d^{1/2})$ samples. This demonstrates a novel separation between differential privacy and machine unlearning.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Learning with Recoverable Forgetting (2022, positive): “Sekhari et al. [38] initiate a rigorous study of generalization in machine unlearning, where the goal is to perform well on previously unseen datapoints and the focus is on both computational and storage complexity.”
Measuring Forgetting of Memorized Training Examples (2022, background): “Algorithms for machine unlearning have been proposed for k-means [24], empirical risk minimization [29, 35, 59, 76, 67], and deep learning [18, 26, 25, 60, 5].”
SalUn: Empowering Machine Unlearning via Gradient-based Weight Saliency in Both Image Classification and Generation (2023, background): “MU aims at modifying ML models to eliminate the influence of specific data points or classes, initially developed to mitigate potential privacy breaches post-training (Ginart et al., 2019; Neel et al., 2021; Ullah et al., 2021; Sekhari et al., 2021).”
Rethinking machine unlearning for large language models (2024, unknown): “…of MU has expanded to encompass diverse domains, such as image classification Ginart et al. (2019); Golatkar et al. (2020) In the literature, ‘exact’ unlearning, which involves retraining the model from scratch after removing specific training data points, is often considered the gold standard.”
Unrolling SGD: Understanding Factors Influencing Machine Unlearning (2021, methodology): “[10] analogously present privacy leakage for unlearning in the framework of differential privacy (DP): they bound the leakage of information about a particular x∗ (or more generally a set of datapoints to unlearn) with privacy parameters ε, δ and define this as (ε, δ)-unlearning.”
Detecting Pretraining Data from Large Language Models (2023, background): “…has emerged as a solution for purging data from machine learning models, and various machine unlearning methods have been introduced (Ginart et al., 2019; Liu et al., 2020; Wu et al., 2020; Bourtoule et al., 2021; Izzo et al., 2021; Sekhari et al., 2021; Gupta et al., 2021; Ye et al., 2022).”
TOFU: A Task of Fictitious Unlearning for LLMs (2024, unknown): “With unlimited resources, one could test the ( ε , δ ) -unlearning condition of indistinguishability (Bourtoule et al., 2021; Sekhari et al., 2021) by training many models and performing hypothesis tests—and this is done in practice when feasible (Carlini et al., 2022; Pawelczyk et al., 2023).”
Towards Unbounded Machine Unlearning (2023, background): “More recently, Guo et al. [2019], Izzo et al. [2021], Sekhari et al. [2021] built upon this framework and introduced unlearning methods that can provide theoretical guarantees under certain assumptions.”
Ablating Concepts in Text-to-Image Diffusion Models (2023, background): “Another line of work in machine unlearning [9, 21, 23, 22, 42, 8, 67, 60] explores data deletion at user’s request after model training.”
A Survey of Machine Unlearning (2022, unknown): “(Bounded/Certified Unlearning) Definition 1 ( 𝜖 -Approximate Unlearning). algorithm 𝐴 if ∀T ⊆ H ,𝐷 ∈ 𝑍 ∗ ,𝑧 ∈ 𝐷 :”
Erasing Concepts from Diffusion Models (2023, background): “The possibility of such exact memorization has driven privacy and copyright concerns and has led to work in machine unlearning [40, 4, 15], which aims to modify a model to behave as if particular training data had not been present.”
Negative Preference Optimization: From Catastrophic Collapse to Effective Unlearning (2024, methodology): “Since its proposal by Cao & Yang (2015), machine unlearning has been extensively studied in the classification literature (Bourtoule et al., 2021; Golatkar et al., 2020; Ginart et al., 2019; Thudi et al., 2022; Izzo et al., 2021; Koh & Liang, 2017; Guo et al., 2019; Sekhari et al., 2021).”
Fast Yet Effective Machine Unlearning (2021, background): “Several other notable works include [39], [40], [41], [42].”
Adaptive Machine Unlearning (2021, methodology): “This includes techniques that ﬁnd an approximately optimal solution to a strongly convex problem and then perturb the solution to obscure the optimizer within a small radius e.g. Guo et al. [2019], Neel et al. [2021], Sekhari et al. [2021].”