Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations

Venue: ECCV 2020 · arXiv: 2003.02960 Verification: dblp for venue (confirming the ECCV 2020 attribution in the reading list); PDF fetched.

Read status: pp. 8–10 read from page images — §4 An NTK-inspired forgetting procedure (Eqs. 8–9, Prop. 2, Eqs. 10–11), §4.1 Relation between NTK and Fisher forgetting (Eq. 12), §5.1 Datasets, §5.2 Models and Training, §5.3 Baselines. §1–3, Prop. 1, results and supplementary not read.

SCRUB's NTK baseline. Phase 1 only — SCRUB states NTK "doesn't scale beyond" the small-scale setting, and §1 below shows exactly why, quantitatively. SCRUB used the authors' public code "for correctness"; we will too, so the registry entry carries implementation: authors_code.

1. The method, and the scalability wall

Intuition. Networks are fine-tuned from pretrained weights and "the weights do not move much during fine-tuning", so activations can be approximated as a linear function of the weights — the Neural Tangent Kernel regime. Linearising around pretrained \theta_0:

with training dynamics

⚠️ The NTK matrix is c|\mathcal{D}| \times c|\mathcal{D}|

\Theta_0 = \nabla_\theta f(\mathcal{D})\nabla_\theta f(\mathcal{D})^\top, "of size c|\mathcal{D}| \times c|\mathcal{D}|, where c [is] the number of classes."

| Setting | c|\mathcal{D}| | Matrix | Dense float32 | |---|---|---|---| | CIFAR-5 (Phase 1) | 5 \times 500 = 2{,}500 | 2{,}500^2 | ~25 MB — fine | | CIFAR-10 (Phase 2) | 10 \times 40{,}000 = 400{,}000 | 400{,}000^2 | ~640 GB |

And Prop. 2 requires inverting \Theta_{rr}. This is the quantitative content of SCRUB's remark that NTK does not scale, and it is why NTK is structurally excluded from Phase 2 rather than dropped for time. A defensible reason to give a panel.

Proposition 2. Assuming an L_2 regression loss, the optimal scrubbing procedure under the NTK approximation is

where \nabla f_0(\mathcal{D}_f)^\top has as columns the gradients of the samples to forget computed at \theta_0; w = A(\mathcal{D}_r \cup \mathcal{D}_f);

• P = I - \nabla f_0(\mathcal{D}_r)^\top\Theta_{rr}^{-1}\nabla f_0(\mathcal{D}_r) — a projection taking the forget-sample gradients onto the orthogonal complement of the span of the retain-sample gradients;
• M = \big[\Theta_{ff} - \Theta_{rf}^\top\Theta_{rr}^{-1}\Theta_{rf}\big]^{-1};
• V = \big[(Y_f - f_0(\mathcal{D}_f)) + \Theta_{rf}^\top\Theta_{rr}^{-1}(Y_r - f_0(\mathcal{D}_r))\big];

M and V "re-weight each direction before summing them together."

Equation 11 — the full procedure, adding noise as in the Fisher paper:

with F = F(w) the FIM computed at h_{\mathrm{NTK}}(w) using \mathcal{D}_r. The noise "is designed to increase robustness to mistakes due to the linear approximation."

Two caveats stated by the authors: the L_2 assumption "is to keep the expression simple" and the softmax-classification version is in the supplementary (unread — and it is the one that actually applies to our setting); and the linearisation is "misaligned with weights actually learned by SGD", for which they introduce an "isoceles trapezium" trick, also in the supplementary.

2. §4.1 — why NTK differs from Fisher exactly in the overparameterised regime

This is the most theoretically interesting passage read so far in the method literature, and it connects directly to the theory track.

The Newton-update scrubbing shift of the Fisher paper is h(w) = w - H(\mathcal{D}_r)^{-1}\nabla_w L_{\mathcal{D}_r}(w) (Eq. 12). Under an L_2 loss and the NTK model, H(w) = \nabla f_0(\mathcal{D}_r)^\top\nabla f_0(\mathcal{D}_r), which here also coincides with the Fisher matrix. Then:

"If \nabla f_0(\mathcal{D}_r) is a tall matrix (more samples in the dataset than parameters in the network), then the pseudo-inverse is \nabla f_0(\mathcal{D}_r)^+ = H^{-1}\nabla f_0(\mathcal{D}_r)^\top, recovering the scrubbing procedure considered by [16,17]. However, if the matrix is wide (more parameters than samples in the network, as is often the case in Deep Learning), the Hessian is not invertible, and the pseudo-inverse is instead given by \nabla f_0(\mathcal{D}_r)^+ = \nabla f_0(\mathcal{D}_r)^\top\Theta^{-1}, leading to our proposed procedure. In general, when the model is over-parametrized there is a large null-space of weights that do not change the final activations or the loss. The degenerate Hessian is not informative of where the network will converge in this null-space, while the NTK matrix gives the exact point."

So Fisher and NTK forgetting are the same procedure in the underparameterised regime and diverge precisely when d > n — the regime deep networks inhabit, and the same regime where Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses's e^{-2\varepsilon/(d+2)} factor collapses and When to Forget? Complexity Trade-offs in Machine Unlearning's d/n ratio goes the wrong way.

This sharpens the contribution direction flagged in regehr2026nearoptimal.md. The proposal there was that the effective rather than ambient dimension might govern the unlearning penalty. Golatkar §4.1 makes the same structural observation from the empirical side — the ambient parameter count is misleading because most of it is null-space that does not affect the loss — and gives a concrete object, the NTK matrix, that "gives the exact point" where the Hessian is degenerate. A theory-side and a practice-side paper independently pointing at the same gap is exactly the kind of opening a theoretically oriented contribution would want.

3. §5 — the source of SCRUB's experimental setup

§5.1 Datasets. This is SCRUB's small-scale setting, verbatim in substance:

"we randomly sample 500 images (100 images from each of the first 5 classes) from the training/test set of CIFAR-10 and Lacuna-10 … We also sample 125 images from the training set (5 classes × 25 images) to get the validation set. So, in short, we have 500 (5 × 100) examples for training and testing respectively, and 125 (5 × 25) examples for validation. On both the datasets we choose to forget 25 random samples (5% of the dataset) … we choose to forget samples from class 0."

Confirms SCRUB's description independently, and therefore confirms our Phase 1 target setting. Note this paper says Lacuna derives from "the VGG-Faces [8] dataset", whereas Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks §5 says VGGFaces2. The two Golatkar papers appear to cite different sources for the same dataset family; reference [8] here has not been resolved. Recorded, not asserted — see VERIFICATION_REPORT.md.

§5.2 Models and Training — read this closely, because SCRUB inherits it:

• All-CNN "(to which we add batch-normalization before non-linearity)" and ResNet-18.
• Pretrain on CIFAR-100/Lacuna-100, SGD, 30 epochs, lr 0.1, momentum 0.9, wd 0.0005. ("Pre-training helps in improving the stability of SGD while fine-tuning.")
• Fine-tune on CIFAR-10/Lacuna-10, lr 0.01, weight decay 0.1.
• Batch size 128, fine-tune "till zero training error".
• 3 runs, mean and standard deviation.

Two details that are easy to miss and that no reimplementation would guess:

🔑 Resolves SCRUB ambiguity A7 (BatchNorm handling)

"during fine-tuning we do not update the running mean and variance of the batch-normalization parameters to simplify the training dynamics."

Both Golatkar papers say this. SCRUB states it uses "the same models with the same architectural modifications in [Golatkar et al. 2020a,b]" but is silent on BN statistics. Two independent sources now say BN running stats are frozen during fine-tuning, which is strong evidence for what SCRUB did. Still to be confirmed against the SCRUB repo before it goes in the spec as CHOICE rather than ASSUMPTION.

🔑 Weight decay is applied toward the initialisation, not toward zero

"While applying weight decay we bias the weights with respect to the initialization."

This is not standard weight_decay in PyTorch's optimisers, which decays toward zero. Decaying toward \theta_0 is \frac{\lambda}{2}\|w - \theta_0\|^2 instead of \frac{\lambda}{2}\|w\|^2. With wd 0.1 for fine-tuning — a very large value that would be destructive if applied toward zero — this detail is almost certainly load bearing. SCRUB also reports wd 0.1 for small-scale, which strongly suggests it inherits the same convention.

New ambiguity for the SCRUB spec (A11). Our canonical training loop currently uses torch.optim.SGD(weight_decay=...), i.e. decay toward zero. If SCRUB decays toward the pretrained initialisation, our originals and oracles are being trained with a different regulariser than the paper's. Must be checked against the repo, and it affects Stage 5, not just Stage 7.

§5.3 Baselines. Fine-tune, Fisher forgetting, Original, compared against "optimal reference the model w(\mathcal{D}_r) trained from scratch on the retain set … the gold standard for forgetting."

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

• Prop. 2 is derived for L_2 regression loss; the softmax-classification form is in the unread supplementary, as is the "isoceles trapezium" realignment trick. Both are needed for our setting.
• Only the small (500-example) setting in §5.1 — consistent with the c|\mathcal{D}|^2 wall.
• Results and Prop. 1's white-box/black-box bounds unread.

5. Links

• SCRUB's NTK baseline; Phase 1 only, via authors' code (implementation: authors_code).
• Companion to Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks; §4.1 explains exactly when the two coincide.
• §4.1's overparameterisation argument connects to Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses and When to Forget? Complexity Trade-offs in Machine Unlearning and sharpens the effective-dimension contribution idea.
• §5.1–5.2 are the origin of Towards Unbounded Machine Unlearning's small-scale setup and training recipe.
• Reported as infeasible at CIFAR scale by Towards Adversarial Evaluations for Inexact Machine Unlearning, consistent with §1.

@inproceedings{golatkar2020outside,
  title         = {Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from {Input-Output} Observations},
  author        = {Aditya Golatkar and Alessandro Achille and Stefano Soatto},
  year          = {2020},
  booktitle     = {ECCV 2020},
  eprint        = {2003.02960},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2003.02960}
}