Unrolling SGD: Understanding Factors Influencing Machine Unlearning

Venue: IEEE European Symposium on Security and Privacy (EuroS&P) 2022 · arXiv: 2109.13398 Affiliations: University of Toronto and Vector Institute; University of Wisconsin-Madison. Verification: dblp for venue; PDF fetched.

Read status: pp. 1–2 read from page images — abstract, §1 Introduction, §2 Primer and Notation, §3 opening (Figure 1 taxonomy). §3.1–§7, all theory and experiments not read.

⚠️ Citation-key warning. Towards Unbounded Machine Unlearning cites this paper as Thudi et al. 2022a and the forging paper On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning as Thudi et al. 2022b. The two are easy to swap — same first author, same year, adjacent topics — and swapping them would misattribute the forging result. Verified against SCRUB's §4 text in both places.

1. What it proposes

Verification error — "the \ell_2 difference between the weights of an approximately unlearned and a naively retrained model" — put forward "as an approximate unlearning metric that should be optimized for as it subsumes a large class of other metrics."

Three contributions, in their words:

1. "A taxonomy of approximate unlearning which concludes with verification error as a metric to study as it subsumes a large class of unlearning criteria."
2. "An analysis of SGD which (a) introduces an inexpensive mechanism for unlearning termed single gradient unlearning, and (b) uncovers the variables impacting verification error."
3. "A way of decreasing this unlearning error (which in turn decreases verification error) by the use of our SD loss with little impact to performance."

Single gradient unlearning "only depends on the initial weights … unlearning is approximate (due to the error term) but inexpensive as it depends on only the initial weights."

Unlearning error is a proxy for verification error whose selling point is that "it does not require computing the retrained model … This makes unlearning error cheaper to compute, and also alleviates the issue of the retrained model being noisy."

SD (standard deviation) loss is a training-time regulariser: "SD loss forces the model to converge with less overall change to the weights. This allows us to unlearn a point from models trained with the SD loss using single gradient unlearning." I.e. train so as to be easier to unlearn later — a distinct category from post-hoc unlearning, and one no other method in our Stage 7 list occupies.

2. §4.1 — what "subsumes a large class of other metrics" actually rests on

The subsumption claim is the paper's headline, and it is worth reading the conditions attached to it, because they are severe and they are stated plainly.

What is proved. Verification error is shown to bound the supremum norm of the difference between two distributions of weights — those from naive retraining and those from approximate unlearning:

"Note that a bound on the L_\infty norm implies bounds on all L_p norms for p \ge 1 … Informally, this allows us to motivate verification error as a metric that bounds a large class of weight space metrics."

They also note it gives something DP-shaped, and immediately bound how far that goes: a sup-norm bound implies "guarantees similar to DP (in particular \varepsilon = 0 and \delta = b where b is the bound on the supremum norm) by the reverse triangle inequality", while the converse fails, and

"in our subsequent analysis, we make several assumptions about the stochasticity of training which does not allow us to derive strict DP-like guarantees."

The four conditions, each of which narrows the result:

1. Batch size 1. "our analysis will focus on unlearning with batch size 1 for simplicity" — the derivation is over SGD, "and not mini-batch SGD".
2. The unlearning method must be of a particular form. Footnote 2: "In our final result we will require the unlearning method to only depend on the initial weights and batch ordering." That is single gradient unlearning by construction, so the theorem is about their method rather than about approximate unlearning generally.
3. Training noise depends only on the step count. They assume "that noise in the final weights for a fixed training sequence is a function of only the number of steps, and changes negligibly when removing a single step from each epoch", written as g = g'.
4. A deterministic decomposition. "if training is deterministic, we have w_{I'} = w_I - d_I where d_I is some constant that only depends on w_0 and the ordering I" — this is what makes a single gradient enough to undo a point.

Condition 3 is an empirical claim, and this project has measured the same thing

The subsumption result leans on an assumption about floating-point noise: that it is a function of step count alone and is unchanged by dropping one step per epoch. That is not a mathematical fact, it is a claim about numerical behaviour, and it is the same phenomenon docs/DETERMINISM.md exists to characterise — where this project measures residuals rather than assuming their form.

This is worth stating carefully in the review. Thudi et al. use training non-determinism twice, in opposite directions: as a reason verification error is a noisy metric (§1: "one can retrain on the same sequence of data from the same initialization and obtain different terminal weights"), and as something well-behaved enough to assume away when proving the subsumption. Both uses may be defensible; they are not obviously consistent, and a project that has instrumented its own determinism is unusually well placed to say so.

Why the batch-size-1 restriction matters here. It is the method-side analogue of the convexity restrictions in the theory track: a result proved for an algorithm nobody trains with. Every original and oracle in this project is trained with mini-batch SGD, so the proof's class does not contain our setting, exactly as When to Forget? Complexity Trade-offs in Machine Unlearning's algorithm class does not contain SCRUB.

3. Their critique of oracle comparison — and how much of it applies to us

This is the passage worth carrying into the review, and it needs care because part of it does not apply to this project:

"Nevertheless, verification error has its own faults. To measure it, one needs to compute the naively retrained model, which begs the question of why not just use the retrained model as the unlearned model? Furthermore, despite discounting randomness associated with training algorithms, training a model is noisy due to numerical instabilities introduced by back-end randomness in floating point computations; comparison with respect to any one retrained model leaves the metric itself noisy. It is also not immediately apparent what one should do then to reduce the verification error."

Three distinct objections, with different force for us:

A point the review can make that is genuinely ours: two of the three objections to oracle-based evaluation dissolve under a deterministic pipeline, and the third is addressable by reporting the oracle's own seed distribution rather than a single draw. That is a small but real contribution of the engineering discipline to the methodological argument — and it is worth stating, because the field tends to treat oracle noise as irreducible.

4. Figure 1 — a 2-D taxonomy worth reusing

Prior post-hoc approximate unlearning is classified along two axes:

• What is being unlearned? — Logits / Weights / Distribution of Weights
• How is successful unlearning measured? — output space: Test Accuracy, Membership Inference, Logits; weight space: Distribution of Weights, Weights

This is a cleaner organising grid than a flat method list, and taxonomy.md should adopt or adapt it. Note it cross-cuts the erase/repair axis from Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition — one describes what is measured, the other what the algorithm does. Two orthogonal axes give a better taxonomy than either alone.

5. SCRUB's criticism of this paper, recorded verbatim

From Towards Unbounded Machine Unlearning §4:

"Thudi et al. [2022a] propose a regularizer to reduce the 'verification error' … The goal is to make unlearning easier in the future. Additionally, they propose a single gradient update that reverses the effect of \mathcal{D}_f. This regularizer, however, may have a negative effect on the model's performance, and the single gradient unlearning step only removes the effect that \mathcal{D}_f has had in the first iteration of training."

The second half is the substantive objection: single gradient unlearning depends only on the initial weights, so it undoes the forget set's influence from the first step, not its accumulated influence across training. Whether that is fatal is not something either paper settles, and this project will not test it — SD loss is a training-time intervention and therefore outside our post-hoc Stage 7 scope.

6. Setup

CIFAR-10, CIFAR-100, and IMDb sentiment analysis. Mini-batch SGD notation: \mathbf{w}_{t+1} = \mathbf{w}_t - \eta \frac{\partial\mathcal{L}}{\partial\mathbf{w}}\big|_{\mathbf{w}_t, \hat{\mathbf{x}}_t}. Cross-entropy loss (their Eq. 1).

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

• §3.1 onward, including the Taylor-series unrolling of SGD, Lemma 1, Corollary 1, the SD loss derivation and all experiments, are unread. No claimed number or bound is recorded.
• Not in scope for Stage 7. SD loss modifies training, so it cannot be applied to our frozen originals — the same structural reason Machine Unlearning is excluded. Single gradient unlearning is post-hoc, but is not in SCRUB's comparison table and so is not a Tier A target.

8. Links

• Companion to On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning; cited by Towards Unbounded Machine Unlearning as 2022a where the forging paper is 2022b.
• Its verification-error critique converges with Machine Unlearning via Information Theoretic Regularization and Towards Adversarial Evaluations for Inexact Machine Unlearning on the inadequacy of oracle-matching, but from the measurement noise direction rather than the definitional one.
• Its Figure 1 taxonomy cross-cuts the erase/repair axis in Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition.
• SD loss belongs to the same "train so as to be easy to unlearn" family as the gradient quantisation and randomised smoothing approach SCRUB §4 attributes to Zhang et al. 2022.

@inproceedings{thudi2022unrolling,
  title         = {Unrolling {SGD:} Understanding Factors Influencing Machine Unlearning},
  author        = {Anvith Thudi and Gabriel Deza and Varun Chandrasekaran and Nicolas Papernot},
  year          = {2022},
  booktitle     = {IEEE European Symposium on Security and Privacy (EuroS\&P) 2022},
  pages         = {303--319},
  eprint        = {2109.13398},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2109.13398}
}