Towards Unbounded Machine Unlearning

Venue: NeurIPS 2023, Main Conference Track (Advances in NeurIPS 36) arXiv: 2302.09880 · Code: https://github.com/Meghdad92/SCRUB Verification: verified_fetched — proceedings page, arXiv abs, and the full proceedings PDF. All content below is from the NeurIPS proceedings PDF unless marked.

Read status: main body §1–6 and appendix §7–9 (including Algorithms 1–3, Table 3, and the baselines paragraph) read from page images. Appendix §10–16 not yet read in full; Tables 7–8 read.

This file is the single deep read of SCRUB. It feeds docs/specs/scrub.md directly — the objective is written out once, here, and referenced there.

1. Problem framing

Given a model f(\cdot; w^o) trained on \mathcal{D}, a forget set \mathcal{D}_f \subset \mathcal{D} of N_f examples, and retain set \mathcal{D}_r = \mathcal{D} \setminus \mathcal{D}_f of N_r examples, produce w^u that has "forgotten" \mathcal{D}_f without hurting utility on \mathcal{D}_r and on held-out data.

The paper's central framing claim is that "forgetting" is application-dependent, and it is the first to evaluate against three applications with distinct desiderata:

The RB/UP tension is the crux: RB wants maximal forget error, UP wants oracle-matched forget error. SCRUB targets the first and SCRUB+R rewinds to hit the second.

Critique of prior work (§1, §4). Approximate-unlearning methods aim for indistinguishability from a retrained model in weight space. SCRUB argues this rests on assumptions deep networks violate — SGD stability and "small enough" forget sets (Golatkar et al. 2020a,b) — and that those methods scale poorly, since the forgetting step in Golatkar et al. 2020a,b grows quadratically with training set size. §4 also cites Thudi et al. 2022b (arbitrarily similar weights from disjoint datasets ⇒ weight proximity is not sufficient for unlearning) and Goel et al. 2022 (not necessary either).

2. The objective

Teacher w^o frozen throughout; student w^u initialised to w^o.

Per-example divergence between student and teacher output distributions:

Equation 1 — pure max-step. Rejected: degrades retain performance.

Equation 2 — contrastive: stay close to teacher on retain, move away on forget.

Equation 3 — final objective, adding the task loss on retain:

where l is cross-entropy and \alpha, \gamma are scalar hyperparameters.

Symbol table

Note the asymmetry: the forget term carries no coefficient — it is implicitly 1.

3. Optimisation: alternating min/max

Equation 3 is hard to optimise directly; the paper reports oscillation, and draws the GAN analogy explicitly (§3.1, citing Goodfellow et al. 2014). SCRUB alternates a max-epoch over the forget set with a min-epoch over the retain set, then runs additional min-epochs at the end to restore retain performance.

Algorithm 1 — SCRUB (verbatim)

Require: Teacher weights w^o
Require: Total max steps MAX-STEPS
Require: Total steps STEPS
Require: Learning rate ε
  w^u ← w^o
  i ← 0
  repeat
    if i < MAX-STEPS then
      w^u ← DO-MAX-EPOCH(w^u)
    end if
    w^u ← DO-MIN-EPOCH(w^u)
  until i < STEPS

Algorithm 2 — DO-MAX-EPOCH (verbatim)

Require: Student weights w^u, learning rate ε, batch size B, forget set D_f, NEXT-BATCH
  b ← NEXT-BATCH(D_f, B)
  repeat
    w^u ← w^u + ε ∇_{w^u} (1/|b|) Σ_{x_f ∈ b} d(x_f; w^u)
    b ← NEXT-BATCH(D_f, B)
  until b

Gradient ascent on the KL — maximising divergence from the teacher on forget data.

Algorithm 3 — DO-MIN-EPOCH (verbatim)

Require: Student weights w^u, learning rate ε, batch size B, retain set D_r, NEXT-BATCH
  b ← NEXT-BATCH(D_r, B)
  repeat
    w^u ← w^u - ε ∇_{w^u} (1/|b|) Σ_{(x_r,y_r) ∈ b} [ α d(x_r; w^u) + γ l(f(x_r;w^u), y_r) ]
    b ← NEXT-BATCH(D_r, B)
  until b

Loss reduction is settled: both inner loops use \frac{1}{|b|} — a batch mean, not a sum. This is one of the ambiguities the brief flagged, and the pseudocode resolves it explicitly.

4. Rewinding (SCRUB+R)

By construction SCRUB drives forget error high, which is right for RB/RC but makes forget examples identifiable and so vulnerable to MIA — bad for UP. §3.2:

1. Build a validation set of the same distribution as the forget set (if the forget set is only class 0, keep only class 0 in the validation set).
2. Train SCRUB as usual, checkpointing every epoch.
3. At the end of training — where forget error is typically highest — measure error on that constructed validation set. This is the reference point.
4. Rewind to the checkpoint whose forget error is closest to the reference.

The stated intuition: the last step approximates "maximal forgetting", so error on an identically-distributed held-out set approximates the error of a model that never saw the forget examples — any correct predictions there come only from generalisation.

Limitation the paper itself states (§8): rewinding can fail in both directions. Forget error "too high" is the case it fixes; forget error "too low" at the end of training also occurs, because hyperparameters are tuned not to harm retain/validation performance, and this can cause "premature stopping" before forget error reaches the reference level.

5. Experimental setup

Datasets. CIFAR-10 (60000 images 32×32; train/test/val = 40000/10000/10000) and Lacuna-10 (derived from VGG-Faces; 10 celebrities with ≥500 samples, 100 per class held out for test, rest train, resized to 32×32). Built following Golatkar et al. 2020a.

Small-scale (CIFAR-5 / Lacuna-5). First 5 classes of each; 100 images sampled per class for train and test; 25 samples per class from train form the validation set. Forget set is 25 examples of class 0 (5%).

Large-scale. All 10 classes. Two scenarios: class unlearning (all of class 5, 10%) and selective unlearning (100 examples of class 5 — 0.25% of CIFAR, 2% of Lacuna).

Pretraining. CIFAR models pretrained on CIFAR-100, Lacuna on Lacuna-100. 30 epochs, SGD, fixed lr 0.1, cross-entropy, weight decay 0.0005, momentum 0.9, batch size 128.

Models. Same as Golatkar et al. 2020a,b. All-CNN with reduced layer count and BatchNorm added before each non-linearity; ResNet-18. Small-scale reduces the number of filters by 60% in each block; large-scale uses the exact architecture.

⚠️ Directly affects unlearn/models/architectures.py. Our current ResNet-18/ All-CNN are the standard forms. The 60% filter reduction for small-scale, and the BatchNorm-before-nonlinearity All-CNN variant, must be implemented before Phase 1.

No data augmentation is used anywhere in the experiments. Stated explicitly in the appendix Datasets paragraph.

Seeds. 3 random seeds; mean and standard deviation reported.

Hardware. Python 3.8, Ubuntu 20, 40 CPU cores, Nvidia GTX 2080, 256 GB RAM.

Table 3 — SCRUB's hyperparameters (transcribed from page image)

Our targets: ResNet/CIFAR-5/selective = 32, 32, 10, 10; All-CNN/CIFAR-5/selective = 16, 32, 5, 10; ResNet/CIFAR-10/selective = 16, 64, 5, 5.

Optimiser (appendix, "SCRUB pseudocode and parameters"). Same optimiser for min and max steps. Adam works better small-scale; both Adam and SGD usable large-scale. LR initialised at 0.0005, decayed by 0.1 "after a number of min and max steps". Weight decay 0.1 small-scale, 0.0005 large-scale. Momentum 0.9.

6. Baselines — exact settings

Equation 4 — NegGrad+ objective:

with \beta \in [0,1]. The paper warns: "small \beta result in explosion quickly."

7. Implementation ambiguities

Numbered for docs/specs/scrub.md. Each needs a CHOICE + RATIONALE, and where possible a check against the official repo.

A1 — Algorithm 1 does not terminate as printed. i ← 0, and i is never incremented anywhere in Algorithms 1–3. The termination condition reads until i < STEPS, which is inverted (a repeat…until should exit when the condition holds; here it holds at i=0 for any positive STEPS, or never advances). We inferred: increment i once per outer iteration, run a max-epoch while i < MAX-STEPS, always run a min-epoch, and stop when i \ge STEPS. Settled against the repository, and the inference was right — a plain for epoch in range(1, sgda_epochs+1), max-steps while epoch <= msteps, min-steps every epoch. Resolved.

A2 — What "max steps" / "min steps" in Table 3 count. They align with MAX-STEPS and STEPS in Algorithm 1, i.e. epochs of the outer loop, not gradient steps. If STEPS is the total outer iterations, then rows where min = max (e.g. ResNet/CIFAR-5: 10, 10) run no trailing min-only epochs, contradicting §3.1's "additional min-steps at the end". Rows where min > max (e.g. Lacuna-5: 5, 10) do. Settled against the repository: they are outer-loop epochs, msteps counts max-step epochs and sgda_epochs the total, and min-steps run on every epoch including the max-step ones — so a row with min = max does indeed perform no trailing min-only epoch. Resolved.

A3 — \alpha and \gamma are never given numerically. They appear in Eq. 3 and Algorithm 3 but not in Table 3 or the appendix text read so far. Settled against the repository: both weight only the minimise step (loss = gamma*loss_cls + alpha*loss_div + beta*loss_kd); the maximise step is unweighted, loss = -loss_div. So the ambiguity was not only a missing value but a missing scope. Resolved.

A4 — LR decay schedule. "Decay it by 0.1 after a number of min and max steps" — the number is unspecified. Settled against the repository: cumulative step decay applied per epoch, lr = sgda_learning_rate * lr_decay_rate ** (entries in lr_decay_epochs already passed). Resolved.

A5 — Optimiser choice at large scale. "Both Adam and SGD could be used" — the paper does not say which produced the reported numbers. Momentum 0.9 is stated, which implies SGD at least somewhere. Settled against the repository: selected by args.optim, and committed as Adam small-scale, SGD large-scale, consistent with the paper's own remark that Adam works better at small scale. One trap comes with it — weight_decay under Adam is L2 added to the gradient, not decoupled AdamW. Resolved.

A6 — Rewinding checkpoint granularity and tie-breaking. "Store a model checkpoint every epoch" and rewind to the closest forget error; ties unspecified. Also unspecified: whether the reference is recomputed per seed. This is the one item the repository cannot settle — it does not implement rewinding at all: the string rewind appears in no .py file and none of the seven notebooks. The small-scale notebook records and plots per-epoch retain/forget error, which is the raw material for choosing an epoch by eye, but no code selects one. docs/REPRODUCTION.md §4 records our choice for each half, marked as a decision rather than a finding. Still open.

A7 — BatchNorm handling. Not discussed by SCRUB. Strong external evidence now available: both Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks §5 and Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations §5.2 state that during fine-tuning they do not update the running mean and variance of the BatchNorm parameters. SCRUB says it uses "the same models with the same architectural modifications in [Golatkar et al. 2020a,b]", so two independent sources point to frozen BN running statistics. Settled against the repository, and the answer splits. Original and oracle training pass --disable-bn, and set_batchnorm_mode(model, train=False) puts every BN module in eval() — running statistics frozen, matching Golatkar. But SCRUB's own loop calls module.train() on the student, so BN statistics do update during both max and min steps. The previously-open half of A7 is therefore answered too, and the answer is the opposite of the training-time convention. Resolved.

A11 — weight decay may be applied toward the initialisation, not toward zero. Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations §5.2: "While applying weight decay we bias the weights with respect to the initialization." That is a penalty \frac{\lambda}{2}\|w - \theta_0\|^2, not the \frac{\lambda}{2}\|w\|^2 that torch.optim.SGD(weight_decay=...) implements. SCRUB reports weight decay 0.1 for small-scale — a value that would be strongly destructive applied toward zero, and exactly Golatkar's fine-tuning weight decay. Strongly suggests SCRUB inherits the convention.

The one ambiguity that reached backwards into Stage 5 — now settled. Every other item here affects a Stage 7 method. This one affects how the original models and retrain oracles are trained, the foundation everything else is measured against.

The repository answers it by phase. Small-scale originals and oracles decay toward the initialisation: main.py adds l2_penalty(model, model_init, wd) = (wd/2)·||w − w_init||² to the loss and sets the optimiser's own weight_decay to 0.0. Large-scale training uses the optimiser's decay, toward zero. SCRUB's own unlearning step decays toward zero. The ~200× magnitude anomaly is explained: the large value appears exactly where the target is the initialisation, and the two are a matched pair rather than independent settings.

Stage 5 is unblocked. The resolution has since been confirmed by running it; see docs/REPRODUCTION.md §2 for the evidence and §3e for the empirical check, including a warning that one of the two ways to get this wrong is undetectable from the metrics alone.

A8 — Teacher freezing. Stated in §3.1: teacher weights w^o treated as a constant. Unambiguous. Resolved.

A9 — Loss reduction. Batch mean \frac{1}{|b|}, explicit in Algorithms 2 and 3. Resolved from the paper — and the repository adds something the paper does not state: DistillKL computes a batch mean of per-example summed KL, scaled by T^2. The batch-mean reading is confirmed; the T^2 scaling must be implemented and was not in our reading.

A10 — Whether the retain-side KL and CE use the same batch. Algorithm 3 sums both terms over the same batch b. Resolved.

8. Validation targets (Phase 1)

From Table 7, small-scale, ResNet, CIFAR-5, RB application. Forget set = 25 examples of class 0. Mean ± std over 3 seeds. Lower is better for test/retain error; for RB, higher forget error is better.

Table 8 (All-CNN, same setting) was also read but its text extraction is column-shifted; transcribe it from the page image before using it as a target.

Two things to note about these targets. The standard deviations are large relative to the gaps — Retrain's forget error is 28.8 ± 5.9 over 3 seeds — which is direct evidence for the Stage 5 concern that 5 seeds may not resolve differences between methods at CIFAR-5 scale. And CF-k and Finetune both sit at exactly 0.0 forget error, i.e. they do not forget at all in this setting; SCRUB's own §5.5 says CF-k "maintains utility but forgets poorly".

8b. How SCRUB's MIAs are actually computed

Found while verifying a claim about SCRUB's reporting; both details are spec-grade and neither is in the main body.

Basic MIA — fully specified in the appendix

"we use the default LogisticRegression() classifier of the Python's scikit-learn library as our attack model, and perform a cross-validation with 5 random splits. We report the average accuracy of the evaluation part of each of the 5 folds as the MIA score. Ideally (for a perfect defense), this score is closest to 50%."

Together with §5.4's description — train the attacker on the unlearned model's losses for forget versus test examples, then predict on held-out balanced losses — this is precise enough to reimplement without guessing:

• Features: the unlearned model's losses (not logits, not full softmax).
• Positives: forget-set examples. Negatives: test-set examples.
• Balanced between the two sets.
• Attack model: sklearn.linear_model.LogisticRegression() at defaults. (The defaults matter and are version-dependent — L2 penalty, C=1.0, lbfgs. Pin the sklearn version in the spec; it is not currently in our TRACKED_LIBRARIES.)
• Protocol: 5-fold cross-validation with random splits; report mean accuracy over the 5 evaluation folds.

SCRUB does apply Carlini's low-FPR standard — but only to LiRA

Worth recording precisely, because it would be unfair and wrong to say otherwise. Figure 4 plots log-scale ROC curves with AUC in the legend for the LiRA-for-unlearning attack, and §11 states:

"A successful defense is associated with a smaller Area Under the Curve (AUC) … Carlini et al. [2022] however advocate that the AUC is not a [sufficient summary, pointing to the] region of the ROC curve associated with very small False Positive Rates … We are primarily interested in the area of small False Positive Rate [Carlini et al., 2022]."

So the honest characterisation is: SCRUB adopts the low-FPR reporting standard for its strong attack and not for its basic attack. Tables 2 and 21–28 — including Table 23, our Phase 2 target — report basic-MIA accuracy only. Our Stage 6 addition is therefore not a correction of the paper but an extension of a standard the paper already endorses.

The LiRA experiments used 5 seeds, not 3

Figure 4's caption: "we trained the target unlearned model 5 times for each unlearning method, using different random seeds, and different forget sets." The main text's "3 random seeds" (§5.1) applies to the RB/RC/UP error tables; the LiRA figure used 5.

Two consequences: quote the right seed count for the right result, and note that varying the forget set across seeds — not just the training seed — is a stronger protocol than holding one split fixed. Our SplitSpec already supports this (the seed feeds _spec_rng), so matching it costs nothing; it just has to be a deliberate choice in the Stage 5 config rather than an accident.

9. What the paper does not test

• No theoretical guarantees. §8 states this as the primary limitation, and §6 notes methods that do have guarantees "either aren't applicable to deep networks, or … perform poorly and don't scale beyond small datasets". This is precisely the gap the thesis's theory section must engage with.
• No data augmentation anywhere, so robustness of the results under augmentation is untested.
• Only 3 seeds.
• Only ResNet-18 and All-CNN. §8 names Transformers and self-supervised objectives as future work.
• Only 32×32 images, and small datasets by design, to permit comparison with methods that do not scale.
• Min-max instability is acknowledged but not characterised systematically.
• Rewinding's "forget error too low" failure mode is described but not quantified.

10. Reproduction notes for this project

• Lacuna is dropped (VGG-Faces availability). Phase 1/2 are CIFAR-only, so 6 of Table 3's 12 rows are out of scope.
• Batch 512 — measured, and the earlier prediction was wrong in an interesting way. It does not OOM on the 4 GB RTX 3050. At ResNet-18 full width it runs, but throughput collapses from 1043 to 299 images/s (2599 MiB allocated), a 3.5x penalty from allocator pressure rather than a clean failure. At the small-scale width (0.4) batch 512 is fine — 2466 img/s, 1256 MiB. So the constraint is a slowdown, not an impossibility, and it only bites at full width. Class unlearning is out of Phase 2's default scope anyway, and any deviation gets documented before running.
• Architecture work is required before Phase 1: 60% filter reduction for small-scale, and All-CNN with BatchNorm before each non-linearity.
• No augmentation simplifies the data pipeline and removes one determinism variable.
• Their hardware was a GTX 2080 (8 GB). We have an RTX 3050 Laptop (4 GB) and an RTX 5050 (8 GB), so the 8 GB card matches their memory budget. Note docs/DETERMINISM.md guarantees bitwise reproducibility only within a device, so results from the two cards cannot be pooled and every run records which one it used.

@inproceedings{kurmanji2023scrub,
  title         = {Towards Unbounded Machine Unlearning},
  author        = {Meghdad Kurmanji and Peter Triantafillou and Jamie Hayes and Eleni Triantafillou},
  year          = {2023},
  booktitle     = {Advances in Neural Information Processing Systems 36 (NeurIPS 2023), Main Conference Track},
  eprint        = {2302.09880},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2302.09880}
}