Making AI Forget You: Data Deletion in Machine Learning

Venue: NeurIPS 2019 · arXiv: 1907.05012 Verification: dblp for venue; PDF fetched.

Read status: pp. 3–4 read from page images — §3 Problem Formulation (Definition 3.1, "A Computational Challenge", "Data Deletion as an Online Problem", Remark 3.1), §3.1 the four design principles, §4–4.1 opening. §1–2, §4.2, §5 experiments, §6 Discussion and all appendices not read; the "Data Deletion and Data Privacy" passage was read from text extraction.

Read specifically to check claims about this paper that I had recorded secondhand from Sekhari, Neel, SISA and SCRUB. The audit is §4 below, and it turned up one nuance worth carrying into the review.

1. Definition 3.1 — and it is exact, not approximate

"Our definition formalizes the intuitive goal that after a specified datapoint x is deleted, the resulting model is updated to be indistinguishable from a model that was trained from scratch on the dataset sans x."

Definition 3.1 (Data Deletion Operation). R_A(D, A(D), i) maps the dataset D, the model A(D), and an index i \in \{1,\dots,n\} to some model in \mathcal{H}. It is a data deletion operation if, for all D and i, the random variables A(D_{-i}) and R_A(D, A(D), i) are equal in distribution:

And immediately after:

"Here we focus on exact data deletion: after deleting a training point from the model, the model should be as if this training point had never been seen in the first place. The above definition can naturally be relaxed to approximate data deletion by requiring a bound on the distance (or divergence) between distributions … Refer to Appendix A for more details on approximate data deletion, especially in connection to differential privacy. We defer a full discussion of this to future work."

🔑 The nuance that matters

Ginart's main-body definition is equality in distribution — exact deletion. The (\varepsilon,\delta)-style approximate relaxation is confined to an appendix and explicitly deferred. So the review must not cite Ginart et al. as the source of an (\varepsilon,\delta)-approximate unlearning definition.

The correct lineage is: Ginart 2019 (exact, distributional) → Certified Data Removal from Machine Learning Models (certified removal, genuinely (\varepsilon,\delta)) → Remember What You Want to Forget: Algorithms for Machine Unlearning and Descent-to-Delete: Gradient-Based Methods for Machine Unlearning (DP-style, with capacity and sequences).

The paper is "probabilistic" in the sense that it compares distributions over models rather than model outputs — which is a real and important step past Towards Making Systems Forget with Machine Unlearning — but that is a different thing from being approximate.

Model metadata is allowed. "We allow models to also include arbitrary metadata that is not necessarily used at inference time. Such metadata could include data structures or partial computations that can be leveraged to help with subsequent deletions." This is the ancestor of Remember What You Want to Forget: Algorithms for Machine Unlearning's T(S) statistics — but without Sekhari's constraint that it be independent of n.

2. The challenge is computational, and there is a lower bound

"Every learning algorithm A supports a trivial data deletion operation corresponding to simply retraining … Because of this, the challenge of data deletion is computational."

Their three questions are worth quoting in the review because they set the field's agenda: can we design A plus data structures allowing efficient deletion; for what A is deletion sublinear in dataset size or in the time to compute A(D); and how does restricting the metadata's memory footprint affect deletion efficiency.

Remark 3.1. "In the online setting, for n datapoints and m deletion requests we establish an asymptotic lower bound of \Omega(n/m) for the amortized computation time of any (sequential) learning algorithm." An algorithm achieving it is deletion efficient.

This is a complexity lower bound for unlearning in 2019, six years before When to Forget? Complexity Trade-offs in Machine Unlearning's minimax analysis, and the two should be presented together in the review's theory section — Ginart bounds amortised time in an online deletion stream, Van Waerebeke bounds the ratio of unlearning to retraining time for a target excess risk. Different quantities, same instinct.

3. §3.1 — four design principles, one of which is SISA a year early

That table is a compact map of the whole field from its second paper, and it belongs in taxonomy.md.

4. ✅ Audit of secondhand characterisations

Every claim I had recorded about this paper from a citing paper, checked against the source:

On that last row — be fair. Read in context, SCRUB is contrasting Ginart with Towards Making Systems Forget with Machine Unlearning, described in the preceding sentence as "successful if deleting an example yields the same outputs on a dataset as if that example had never been inserted." Against that, moving from deterministic output-equality to distributional equality is a relaxation, and "similar" is loose shorthand rather than an error. SCRUB's own second mention states it correctly.

The practical rule for our review: cite Ginart for the distributional indistinguishability goal and for the computational framing, never as the source of an (\varepsilon,\delta) bound.

5. Deletion is not privacy — verified directly

From their "Data Deletion and Data Privacy" passage:

"cryptography … and differential privacy … do not lead to efficient data deletion, but rather attempt to make data private or non-identifiable. Algorithms that support efficient deletion do not have to be private, and algorithms that are private do not have to support efficient deletion. … Even an operation that outputs the entire dataset in the clear could support data deletion, whereas such an operation is certainly not private. In this sense, the challenge of data deletion only arises in the presence of computational limitations."

The dataset-in-the-clear example is the sharpest one-line separation of deletion from privacy anywhere in this reading, and it is worth quoting in the review. It also sets up the tension the rest of the field lives in: When Machine Unlearning Jeopardizes Privacy later shows that the act of deletion can itself leak, so deletion without privacy is not merely unambitious but can be actively harmful.

They do add: "that being said, data deletion has direct connections and consequences in data privacy and security."

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

• The case study is k-means, not deep networks: Quantized k-means and Divide-and-Conquer k-means. "Due to its simplicity we focus on k-means clustering as a case study."
• They are explicit that generality is open: "Obtaining tight upper and lower bounds is an open question for many basic learning paradigms including ridge regression, decision tree models, and settings where A corresponds to the solution to a stochastic optimization problem."
• §5 experiments, §6 Discussion and appendices unread; no reported number recorded.
• SISA §III.D's further criticism — that it is unclear whether Quantized k-Means meets their generality (G5) and overhead (G6) goals — is consistent with this scope.

7. Links

• Second paper in the field after Towards Making Systems Forget with Machine Unlearning; introduces the distributional indistinguishability goal everything downstream relaxes.
• Its Modularity principle is Machine Unlearning two years early.
• Its Quantization/stability principle is the assumption Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks relies on and Towards Unbounded Machine Unlearning attacks.
• Its metadata allowance is the ancestor of Remember What You Want to Forget: Algorithms for Machine Unlearning's T(S), minus the independence-of-n constraint.
• Its \Omega(n/m) amortised lower bound anticipates When to Forget? Complexity Trade-offs in Machine Unlearning.
• Its deletion-is-not-privacy argument is complicated by When Machine Unlearning Jeopardizes Privacy.

@inproceedings{ginart2019deletion,
  title         = {Making {AI} Forget You: Data Deletion in Machine Learning},
  author        = {Antonio Ginart and Melody Y. Guan and Gregory Valiant and James Zou},
  year          = {2019},
  booktitle     = {NeurIPS 2019},
  eprint        = {1907.05012},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/1907.05012}
}