Towards Making Systems Forget with Machine Unlearning

Venue: IEEE Symposium on Security and Privacy (S&P) 2015, pp. 463–480 · DOI: 10.1109/SP.2015.35 · arXiv: none (verified absent) Affiliation: Columbia University. Verification: verified_fetched — dblp for venue; PDF obtained from the official IEEE S&P 2015 archive at ieee-security.org/TC/SP2015/papers-archived/6949a463.pdf, and confirmed from the PDF's own header ("2015 IEEE Symposium on Security and Privacy") and page numbering (paper begins at 463).

Read status: pp. 2–4 read from page images — Fig. 1 (the unlearning idea), §I-B Machine Unlearning, §I-C Contributions, §II-A Machine Learning Background, §II-B Adversarial Model. §III–§XII and all case studies not read.

The paper that coined "machine unlearning". Everything else in this project's reading descends from it, and it is worth reading precisely because its framing is broader than what the field later narrowed to.

1. The idea: convert learning into a summation form

From Figure 1's caption:

"Instead of making a model directly depend on each training data sample, we convert the learning algorithm into a summation form. Specifically, each summation is the sum of transformed data samples, where the transformation functions g_i are efficiently computable. There are only a small number of summations, and the learning algorithm depends only on summations. To forget a data sample, we simply update the summations and then compute the updated model. This approach is asymptotically much faster than retraining from scratch."

The generality claim rests on statistical query (SQ) learning: "the summation form is from statistical query learning. Many machine learning algorithms, such as naïve Bayes classifiers, support vector machines, and k-means clustering, can be implemented as SQ learning. Our approach also applies to all stages of machine learning, including feature selection and modeling."

That last clause is worth noting — this is the only paper in our reading that treats feature selection as something requiring unlearning. The modern literature assumes a fixed architecture and unlearns only weights.

2. Completeness and timeliness — the original two metrics

"The usefulness of forgetting systems can be evaluated with two metrics: how completely they can forget data (completeness) and how quickly they can do so (timeliness). The higher these metrics, the better the systems at restoring privacy, security, and usability."

This is the ancestor of every forgetting-quality-versus-efficiency trade-off in the literature — including Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition's final score, which multiplies a forgetting term by utility ratios under a hard runtime gate, and When to Forget? Complexity Trade-offs in Machine Unlearning's complexity ratio.

3. Why unlearning is not differential privacy — stated in 2015

"Differential privacy preserves the privacy of each individual item in a data set equally and invariably by restricting accesses only to the whole data set's statistics fuzzed with noise. This restriction is at odds with today's systems such as Facebook and Google Search which, authorized by billions of users, routinely access personal data for accurate results. Unsurprisingly, it is impossible to strike a balance between utility and privacy in state-of-the-art implementations. In contrast, forgetting systems aim to restore privacy on select data."

DP protects everything uniformly and in advance; unlearning restores privacy selectively and on request. Ten years before Remember What You Want to Forget: Algorithms for Machine Unlearning formalised the separation as a \Theta(d^{1/4}) gap in deletion capacity, the qualitative distinction is already stated cleanly here.

4. The motivation was never only privacy

This is the observation most worth carrying into the review. §I and §II-B give three motivations, and GDPR is not among them (the paper predates it):

• Privacy — system inference attacks (their term, used "instead of model inversion"). Cited examples: Calandrino et al. inferred six book purchases per user with 90% accuracy for over a million LibraryThing users from item-item collaborative filtering; Fredrikson et al. inferred genetic markers from a personalized warfarin dosing model "with accuracy as high as 75%."
• Security — training data pollution attacks. "An attacker injects carefully crafted data samples into a learning system, misleading the algorithms to compute an incorrect feature set and model… the detector must forget the injected data to regain security." They note 3% mislabeled training data "turned out to significantly decrease detection efficacy."
• Usability — removing noise, or data a user no longer wants influencing recommendations.

🔎 A framing point for the literature review

The field's definitions narrowed to privacy over the following years. Cao & Yang evaluate completeness and timeliness across all three motivations above; by contrast Making AI Forget You: Data Deletion in Machine Learning Def. 3.1, Certified Data Removal from Machine Learning Models §2 and Remember What You Want to Forget: Algorithms for Machine Unlearning Def. 2 each define success purely as proximity to a retrain-on-\mathcal{D}_r reference, with no counterpart to security or usability.

⚠️ An earlier version of this note added that "most post-2020 papers open with the right to be forgotten." That is withdrawn — eight of this project's notes record the introduction as unread, so we cannot characterise those papers' motivating rhetoric. See VERIFICATION_REPORT.md correction 9. The claim about definitions stands, because those sections were read.

But Towards Unbounded Machine Unlearning's three-application framing — RB (removing biases), RC (resolving confusion from mislabelled data), UP (user privacy) — is much closer to Cao & Yang's original breadth than to the intervening privacy-only literature. SCRUB's RC scenario is recovery from label pollution; its RB scenario is the usability/correctness motivation.

So SCRUB's claim to be "the first to argue that the definition of 'forgetting' is application-dependent" is fair with respect to the evaluation literature, but the underlying breadth was present in the field's founding paper and was subsequently lost. That is a genuinely interesting arc for timeline.md, and it strengthens rather than undercuts SCRUB's framing.

5. Results and cost

Evaluated on four real systems: LensKit (recommendation), Zozzle (JavaScript malware detector, "adopted by Microsoft Bing"), an open-source OSN spam filter, and PJScan (PDF malware detector), with real workloads including >100K JavaScript malware samples.

Headline: Zozzle takes over a day to retrain but "less than a second" to unlearn. Adoption cost: "we modified from 20–300 lines of code, less than 1% of the system."

They also claim analytical completeness: "we show analytically that, for all these algorithms, our approach is both complete (completely removing a data sample's lineage) and timely (asymptotically much faster than retraining)."

6. Why it does not apply to deep networks

The paper does not claim it does. Machine Unlearning §III.D makes the limitation explicit, and the reasoning is sound given the SQ framing:

"their approach is not general and does not easily scale to more complex models … these models are trained using adaptive statistical query algorithms which make queries that depend on all queries previously made. In this setting, the approach of Cao et al. diverges in an unbounded fashion unless the number of queries made is small, which is not the case for the deep neural networks we experiment with."

SGD on a deep network is adaptive by construction — each minibatch gradient depends on the parameters produced by every prior step. That is precisely the incremental-training difficulty SISA §III.A lists as reason (3) that unlearning is hard, and it is why the summation form cannot be applied here.

7. What the paper does not do (from sections read)

• §III–§XII, including the formal backbone (§IV), the case studies (§VI–§IX), and the discussion of limitations (§X–§XI), are unread. No analytical claim beyond those quoted above is recorded.
• No deep networks; the algorithm classes are naïve Bayes, SVM, k-means, normalized cosine similarity, one-class SVM.
• "Completeness" is defined operationally against their systems, not as a distributional indistinguishability notion — that arrives with Making AI Forget You: Data Deletion in Machine Learning and Machine Unlearning.

8. Links

• Coined the term; the origin point for Machine Unlearning, Making AI Forget You: Data Deletion in Machine Learning and everything downstream.
• Dismissed as insufficiently general by Machine Unlearning §III.D on the adaptive-SQ grounds above.
• Its completeness/timeliness pair is the ancestor of the forgetting-versus-efficiency trade-off formalised by When to Forget? Complexity Trade-offs in Machine Unlearning and scored by Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition.
• Its security and usability motivations resurface as Towards Unbounded Machine Unlearning's RC and RB applications.
• Not the source of the VGG-Faces dataset, despite Towards Unbounded Machine Unlearning citing it as such — see VERIFICATION_REPORT.md §5a for the author-name collision.

@inproceedings{cao2015forget,
  title     = {Towards Making Systems Forget with Machine Unlearning},
  author    = {Yinzhi Cao and Junfeng Yang},
  year      = {2015},
  booktitle = {IEEE Symposium on Security and Privacy (S\&P) 2015},
  pages     = {463--480},
  doi       = {10.1109/SP.2015.35}
}