Machine Unlearning

Venue: IEEE Symposium on Security and Privacy (S&P) 2021 · arXiv: 1912.03817 Verification: verified_fetched — arXiv abs page (venue stated) and the PDF.

Read status: pp. 3–7 read from page images — §III Defining Unlearning (incl. Definition III.1, goals G1–G6, strawman solutions) and §IV The SISA Training Approach (sharding, isolation, slicing, aggregation, Eq. 1, challenges). §V–§IX and the experimental evaluation not read.

1. Definition of unlearning

Definition III.1. Let \mathcal{D} = \{d_i : i \in \mathcal{U}\} be the training set collected from population \mathcal{U}, and \mathcal{D}' = \mathcal{D} \cup d_u. Let \mathbb{D}_\mathcal{M} be the distribution of models learned using mechanism \mathcal{M} on \mathcal{D}' and then unlearning d_u, and \mathbb{D}_{real} the distribution of models learned using \mathcal{M} on \mathcal{D}. \mathcal{M} facilitates unlearning when these two distributions are identical.

The authors draw attention to two aspects, both of which recur throughout the later literature:

1. It is a statement about distributions, not parameters. "it is possible for multiple hypotheses to minimize empirical risk over a training set… two models having different parameters does not imply that they were trained with a different dataset. Conversely, two models trained with a different dataset do not necessarily have different parameters." This is the seed of the critique later formalised by Unrolling SGD: Understanding Factors Influencing Machine Unlearning (weight proximity is not sufficient) and Towards Adversarial Evaluations for Inexact Machine Unlearning (not necessary either), and cited by SCRUB in its §4.
2. Retraining is not required, only plausible deniability. The definition "does not necessarily require that the owner retrain the model M' from scratch … as long as they are able to provide evidence that model M' could plausibly have been trained from scratch on \mathcal{D}' \setminus d_u. In our work, this evidence takes the form of a training algorithm."

Why unlearning is hard (§III.A). Four reasons, worth quoting because they frame the whole field: (1) limited understanding of how each data point impacts the model — influence functions need expensive second-order derivatives and it is unclear how to extend them to DNNs; (2) stochasticity in training — random batching, varying batch order, parallelism without explicit synchronisation making training non-deterministic; (3) training is incremental — any update depends on all prior updates; (4) stochasticity in learning — SGD converges to one of many minima.

Point (2) is the direct justification for this project's determinism apparatus. SISA names non-determinism as a reason unlearning is hard; docs/DETERMINISM.md removes it as a variable for us.

2. Goals G1–G6

Strawman solutions rejected (§III.D) — a useful map of the alternatives:

• Differential privacy. The bound on any single point's influence "remains non-zero. … To guarantee unlearning, we would need to achieve \varepsilon-differential privacy with \varepsilon = 0. This would make it impossible for the algorithm to learn" — fails G2.
• Certified removal mechanisms (Certified Data Removal from Machine Learning Models and a concurrent proposal). One-step Newton update; residual masked by noise. Guarantees are probabilistic; they rely on pretraining on public data or DP feature extractors; "effective for simple models such as linear regression models, which suggest that they fall short of achieving G5."
• Statistical query learning (Towards Making Systems Forget with Machine Unlearning). Not general (G5), does not scale to complex models; "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."
• Decremental learning (Making AI Forget You: Data Deletion in Machine Learning). "deletion and privacy problems are orthogonal, which means deletion capability does not imply privacy nor vice versa." Unclear whether Quantized k-Means meets G5 and G6.

3. The method: Sharded, Isolated, Sliced, Aggregated

Sharding. Partition \mathcal{D} uniformly into S disjoint shards with \bigcap_{k\in[S]}\mathcal{D}_k = \emptyset and \bigcup_{k\in[S]}\mathcal{D}_k = \mathcal{D}; train constituent M_k on each. A deletion touches only the one shard containing d_u, giving an expected S\times speed-up for a single request.

Isolation. No exchange of updates between constituents — gradients are never shared. "This ensures that the influence of a shard (and the data points that form it) is restricted to the model that is being trained using it." The authors call isolation "a subtle, yet powerful construction that enables us to give concrete, provable, and intuitive guarantees."

Slicing. Partition each shard into R disjoint slices and train incrementally, saving the parameter state after each slice:

1. Train from random initialisation on \mathcal{D}_{k,1} for e_1 epochs → M_{k,1}, save.
2. Train M_{k,1} on \mathcal{D}_{k,1}\cup\mathcal{D}_{k,2} for e_2 epochs → M_{k,2}, save.
3. …through step R, giving M_{k,R} = M_k.

To unlearn d_u, locate its slice and restart from the checkpoint saved before that slice was added. Best-case speed-up up to \frac{R+1}{2}\times.

Equation 1 — the epoch accounting that makes the slicing comparison fair. With D = N/S points per shard, e' epochs without slicing, and each slice trained equally long (e_i = e/R):

Combined best-case speed-up: \frac{(R+1)S}{2}\times in retraining time, for one unlearning request.

Aggregation. Label-based majority vote at inference. Constrained by two requirements, the second of which is a nice piece of reasoning: "The aggregation strategy should not involve the training data (otherwise the aggregation mechanism itself would have to be unlearned in some cases)." They evaluated averaging post-softmax vectors and a learned controller model; improvements were "modest and not worth the cost of now having to retrain the controller model if its own training data is the subject of an unlearning request."

Challenge: weak learners. Each constituent trains on 1/S of the data and "could be weak learners… their accuracy will be lower than a single model trained on the entire dataset. This effect is more profound in complex learning tasks."

4. Why SISA is not, and cannot be, in this project's Stage 7 list

SISA is not a post-hoc unlearning method. It is a training-time architecture: to use it you must have trained with sharding, isolation and slicing from the start. Consequently:

• It cannot be applied to our frozen original models. Every method in the Stage 7 list takes an already-trained w^o and modifies it. SISA takes a dataset and a training budget.
• It is absent from SCRUB's comparison table for the same reason — it is not a competitor to SCRUB, it is a different paradigm answering a different question.
• Comparing SISA against SCRUB on forget quality would be close to meaningless: SISA's forget quality is exact by construction (the retrained constituent genuinely never saw the data), so it would trivially match the oracle. The interesting axes for SISA are accuracy degradation and storage/compute overhead, neither of which our Stage 6 harness is built to measure.

SISA belongs in the review, but not in a results table. It is the canonical exact unlearning method and the origin of the definition every later method relaxes, which is why it is read here in depth. It is not implementable as a Stage 7 baseline, and no results table in this project should carry a SISA row.

5. Connection to the theory track

SISA is exactly the class of method that When to Forget? Complexity Trade-offs in Machine Unlearning carves out of its impossibility result. Their Theorem 2 says exact unlearning (\kappa_{\epsilon,\delta} = +\infty) admits no asymptotic gain over retraining — but they immediately add that "most existing exact MU algorithms rely on modifications of the training set and are thus not included in our framework." SISA modifies the training set (by sharding), so it escapes. The review should present these two together: the impossibility result and the method that sidesteps it, and be explicit that the sidestep is bought with the weak-learner accuracy cost SISA itself identifies.

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

• §V–§IX and all experiments unread; accuracy/speed-up trade-offs not yet characterised here beyond the theoretical best case.
• The \frac{(R+1)S}{2}\times figure is explicitly best case and for a single unlearning request; the batched/sequential-request setting is deferred to their §VII.
• Sharding assumes no prior knowledge of which points will be unlearned; the informed case is deferred to their §VIII.

7. Links

• Origin of the definition relaxed by Certified Data Removal from Machine Learning Models, Remember What You Want to Forget: Algorithms for Machine Unlearning, Descent-to-Delete: Gradient-Based Methods for Machine Unlearning, and criticised as inauditable by Machine Unlearning via Information Theoretic Regularization.
• Its own §III.D rejects Towards Making Systems Forget with Machine Unlearning and Making AI Forget You: Data Deletion in Machine Learning as insufficiently general.
• Exempt from the impossibility result in When to Forget? Complexity Trade-offs in Machine Unlearning.
• The "different parameters ≠ different data" observation prefigures Unrolling SGD: Understanding Factors Influencing Machine Unlearning and Towards Adversarial Evaluations for Inexact Machine Unlearning, both cited by Towards Unbounded Machine Unlearning.

@inproceedings{bourtoule2021sisa,
  title         = {Machine Unlearning},
  author        = {Lucas Bourtoule and Varun Chandrasekaran and Christopher A. Choquette-Choo and Hengrui Jia and Adelin Travers and Baiwu Zhang and David Lie and Nicolas Papernot},
  year          = {2021},
  booktitle     = {IEEE Symposium on Security and Privacy (S\&P) 2021},
  eprint        = {1912.03817},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/1912.03817}
}