Abstract
Today’s systems produce a rapidly exploding amount of data, and the data further derives more data, forming a complex data propagation network that we call the data’s lineage. There are many reasons that users want systems to forget certain data including its lineage. We present a general, efficient unlearning approach by transforming learning algorithms used by a system into a summation form. To forget a training data sample, our approach simply updates a small number of summations — asymptotically faster than retraining from scratch. Our approach is general, because the summation form is from the statistical query learning in which many machine learning algorithms can be implemented. Our evaluation, on four diverse learning systems and real-world workloads, shows that our approach is general, effective, fast, and easy to use.
Summary
This foundational paper introduces the concept of machine unlearning — the process of making learning systems “forget” specific training data completely and efficiently. The key motivation is threefold: privacy (users want their data forgotten), security (polluted training data must be removed), and usability (incorrect data degrades recommendations).
The core technical insight is converting learning algorithms into a “summation form” based on statistical query (SQ) learning. In this form, the model depends on a small number of summations Σ g_k(x_i, l_{x_i}) rather than individual data points. To unlearn a sample x_p, one simply updates G_k’ = G_k - g_k(x_p, l_{x_p}) and recomputes the model, achieving O(1) per-summation cost versus O(N) for retraining.
Key Contributions
- Introduces the concept and term “machine unlearning” for efficient data forgetting
- Proposes converting learning algorithms to summation form via SQ learning framework
- Handles both non-adaptive SQ learning (naive Bayes, linear regression) and adaptive SQ learning (gradient descent, SVM, k-means)
- Defines completeness (prediction equivalence to retrained model) and timeliness (speedup over retraining)
- Evaluates on four real-world systems: LensKit, Zozzle, OSNSF, PJScan
Methodology
The approach transforms learning algorithms into SQ form: Learn(Σ g₁(x_i), Σ g₂(x_i), …, Σ g_m(x_i)). For non-adaptive SQ algorithms (naive Bayes), all summations are fixed upfront; unlearning subtracts the sample’s contributions. For adaptive SQ algorithms (gradient descent, k-means), the converged state S’ after subtraction is used as initial state, and the algorithm resumes until re-convergence — typically requiring far fewer iterations.
Key Findings
- Unlearning achieves 100% completeness on 3 of 4 systems (LensKit, Zozzle, PJScan), 99.4% on OSNSF
- Speedups: 6.57x (LensKit), 9.5×10⁴ (Zozzle), 8.4×10⁴ (OSNSF), ~1x (PJScan due to small dataset)
- Implementation requires only 20-300 lines of code modification (< 1% of system)
- Practical data pollution attacks exist against all four evaluated systems
- Asymptotic speedup is O(N/m) for non-adaptive and varies for adaptive SQ learning
Important References
- Statistical Query Learning — Chu et al., SQ learning framework underlying the summation approach
- Differential Privacy — Complementary approach preserving privacy of all items equally
- SISA Training — Bourtoule et al. (2021), later exact unlearning via sharding