Are we making progress in unlearning? Findings from the first NeurIPS unlearning competition

Venue: arXiv:2406.09073, 13 Jun 2024. No journal-ref — not peer-reviewed. Authors (15, in order): Eleni Triantafillou, Peter Kairouz, Fabian Pedregosa, Jamie Hayes, Meghdad Kurmanji, Kairan Zhao, Vincent Dumoulin, Julio Jacques Junior, Ioannis Mitliagkas, Jun Wan, Lisheng Sun Hosoya, Sergio Escalera, Gintare Karolina Dziugaite, Peter Triantafillou, Isabelle Guyon. Verification: verified_fetched — arXiv abs page (full author list confirmed in order) and the PDF.

Read status: pp. 4–7 read from page images — Eq. 1, §3 evaluation framework, §3.1 forgetting quality via empirical ε, §3.1.1 per-example ε, §3.1.2 aggregation, §4 the accuracy/efficiency setups, §5 unlearning methods. §1–2, §6 experiments, §7 discussion and all appendices not read.

Three of SCRUB's four authors are on this paper — Eleni Triantafillou, Jamie Hayes and Meghdad Kurmanji — as is Peter Triantafillou. Together with Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy this is the same group building the evaluation apparatus they found SCRUB's original metrics lacked.

1. The scoring framework

Equation 1 — empirical ε from an attack's error rates:

where FPR and FNR are estimated "under an instantiated attack that is designed to predict as accurately as possible whether a given model was obtained through recipe \mathcal{U}(\mathcal{A}(\mathcal{D}), \mathcal{S}, \mathcal{D}) or \mathcal{A}(\mathcal{D} \setminus \mathcal{S})" — i.e. unlearned versus retrained.

Equation 2 — the final score, combining forgetting quality \mathcal{F} with utility:

with \text{Acc}(\mathcal{D},\theta) = \frac{1}{|\mathcal{D}|}\sum_{(x,y)\in\mathcal{D}}[f(x;\theta) = y].

The construction "adjusts the forgetting quality \mathcal{F} to take utility in consideration, by penalizing an unlearning algorithm if either its retain or test accuracy is smaller than the corresponding accuracy of retraining-from-scratch."

Note both utility terms are ratios against the retrain oracle, not absolutes. This is a clean way to fold utility into one number without picking an arbitrary weighting — and it is another instance of the oracle-anchored convention Machine Unlearning via Information Theoretic Regularization criticises as inauditable.

Efficiency is handled by a hard gate rather than a scored term: all algorithms studied must be "substantially more efficient than retraining from scratch by enforcing a hard cut-off on the runtime of unlearning (roughly 20% of the time it takes to retrain-from-scratch)."

2. §3.1 — how \mathcal{F} is obtained, and why it is per-example

Two challenges are named explicitly:

• (a) \theta^r and \theta^u are high-dimensional, so running attacks directly on parameters is computationally hard.
• (b) "two unlearning algorithms \mathcal{U}_1, \mathcal{U}_2 may have the same (or similar) estimated \varepsilon overall, but could still behave very differently on many examples s \in \mathcal{S} … requiring a more granular resolution."

Their two answers map exactly onto the critiques already recorded in this project:

• Work with distributions of scalar outputs given inputs from \mathcal{S}, not weight space. Footnote: "Prior work finds that white-box access does not necessarily always translate to an improved attack."
• Estimate \varepsilon per example, then aggregate. This is Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy's per-example concern operationalised into a score.

§3.1.1 — per-example ε. For example s, take outputs h(f(s;\theta^u)) and h(f(s;\theta^r)), where h "applies logit-scaling on the model's 'confidence', i.e. a scalar corresponding to the probability of the correct class. The logit-scaling is designed to make the distribution of that scalar more 'Gaussian'." That is Membership Inference Attacks From First Principles's \phi(w) = \log\frac{w}{1-w} rescaling. Distributions are estimated from N samples of each of \theta^u and \theta^r.

The strongest-attacker principle, stated explicitly:

"we are not interested in the FPR and FNR of any attacker: the failure of a poor attacker at distinguishing the two distributions does not say much about the quality of unlearning. Therefore, we design a procedure that aims to get the strongest attacker for each example … we consider m 'attacks', compute the FPR and FNR of each and associated estimates of \varepsilon and we keep the largest out of those \varepsilon's … The intuition is that, for unlearning to be successful, it must defend against the strongest attack."

Two attack families are swept: single-threshold (predict "unlearned" for values > t, assigned to whichever distribution has the larger median) and double-threshold (t_1 < t_2, values in between assigned to the peakier distribution). Double-threshold attacks matter because "unlearning algorithms produce different forms of distributions, some more peaky than others, and not all are easily separable from the retrain-from-scratch solution using only one threshold."

§3.1.2 — aggregation by binning:

with bin-width = 0.5 and n mapping to a bin index in [1,B]. Smaller per-example \varepsilon (better unlearning of that example) gives smaller n and more points. Rationale: "binning … is more granular than a simple average or computing quantiles and less sensitive to noise compared to directly using estimated \varepsilon's."

3. §4 — the compute taxonomy, and a sobering number for us

Sampling is needed from three distributions: \theta^r = \mathcal{A}(\mathcal{D}\setminus\mathcal{S}), \theta^u = \mathcal{U}(\mathcal{A}(\mathcal{D}),\mathcal{S},\mathcal{D}), and \theta^o = \mathcal{A}(\mathcal{D}). Let N be samples per distribution fed to the framework, and E the number of experiments (each giving one estimate of \mathcal{F}; E>1 gives confidence intervals).

Bootstrapping is offered as an orthogonal saving: from a pool of K triplets (\theta^o,\theta^u,\theta^r), sample N with replacement, compute \mathcal{F}, repeat E times — needing only K models per distribution rather than N\times E. Defaults E = 20 and K = N \times 8.

The competition itself used Setup "Reuse-N-1" with N = 512 and E = 1, on an age predictor trained on facial images from the CASIA-SURF dataset.

🔎 What this means for our seed budget — an important calibration

They needed N = 512 samples of \theta^u and \theta^r to estimate the per-example output distributions, and that was the cheapest setup with no confidence intervals (E=1).

Our Phase 1 plan is 5 seeds. Five samples cannot estimate a distribution well enough to compute a per-example \varepsilon by this method. This framework is therefore out of reach for us on the current compute budget, and that is a fact about our resources, not a judgement about the framework.

Two consequences, both honest rather than convenient:

1. Do not attempt to implement \mathcal{F} with 5 seeds and report it as if comparable to competition numbers. It would be a differently-defined statistic wearing the same name.
2. It independently corroborates the Stage 5 concern (brief item E) that our seed count is small relative to what distribution-level forgetting claims require. SCRUB itself used 3 seeds, so we are in the same regime as the paper we reproduce — but neither is in the regime this framework says is needed.

What is affordable and worth taking from this paper: the strongest-attacker principle (sweep a family of threshold attacks, keep the worst-case \varepsilon) applied to our existing per-example scores. That needs no extra models — only the per-example score storage already proposed under Membership Inference Attacks From First Principles.

4. §5 — the erase/repair taxonomy

A genuinely useful organising idea for taxonomy.md:

"most submitted algorithms can be seen as being comprised of an 'erase' phase, aiming to remove the influence of the forget set, followed by a 'repair' phase, aiming to repair any excess damage to the utility of the model that is caused by imperfect erasing."

Erase implementations seen in submissions: reinitialising a subset of layers (chosen randomly, by gradient, or by parameter norm); adding Gaussian noise to parameters of a heuristically or randomly chosen subset of layers; pulling forget-example predictions toward a uniform distribution; maximising a dot-product contrastive loss between retain and forget predictions.

Repair implementations: minimising cross-entropy on the retain set, sometimes with per-parameter or per-batch learning-rate modulation; weighted cross-entropy plus an MSE term pulling prediction entropy toward the original model's on retain examples; two-phase repair combining KL to the original model's predictions on held-out validation examples with a symmetric KL on retain examples.

With an important caveat in their footnote 7: "unlearning phases cannot always be neatly categorized as one of the two: for instance, finetuning on the retain set still has an indirect erasing effect on the forget set due to catastrophic forgetting."

Baselines they compare against, described in their own words:

"i) NegGrad+ and SCRUB [22], based on gradient ascent on the forget set and descent on the retain set, simultaneously, either using standard cross-entropy (NegGrad+) or distillation from the original model (SCRUB), ii) Random Label that assigns a random label to each example in the forget set and finetunes on that re-labelled forget set; we added a 'repair phase' that finetunes on the retain set, in line with other methods. iii) SalUn based on Random-Label, that enhances that unlearning algorithm by only allowing it to update the 'salient weights', determined based on the magnitude of gradients of a simple unlearning step (gradient ascent on the forget set)."

Two things to carry forward: this is a concise, citable characterisation of SCRUB by its own authors — useful for the review's method section — and it is a compact description of SalUn (a Priority 2 method) that will speed its Stage 4 spec.

5. What is not read

§1–2, §6 (the experimental investigation answering "how do top algorithms compare" and "how do they compare to state-of-the-art"), §7 discussion, and all appendices. No competition result, ranking, or claimed number is recorded anywhere in this project.

6. Links

• Same core authors as Towards Unbounded Machine Unlearning and Inexact Unlearning Needs More Careful Evaluations to Avoid a False Sense of Privacy; operationalises the per-example concern of the latter into a score.
• Adopts Membership Inference Attacks From First Principles's logit rescaling and worst-case-attacker philosophy.
• Its utility terms are ratios against the retrain oracle — the convention Machine Unlearning via Information Theoretic Regularization argues is inauditable.
• Characterises SalUn: Empowering Machine Unlearning via Gradient-based Weight Saliency in Both Image Classification and Generation and SCRUB compactly; useful for Stage 4.
• Its N=512 requirement calibrates what When Machine Unlearning Jeopardizes Privacy-style and per-example distributional claims actually cost.

@misc{triantafillou2024competition,
  title         = {Are we making progress in unlearning? Findings from the first {NeurIPS} unlearning competition},
  author        = {Eleni Triantafillou and Peter Kairouz and Fabian Pedregosa and Jamie Hayes and Meghdad Kurmanji and Kairan Zhao and Vincent Dumoulin and Julio Jacques Junior and Ioannis Mitliagkas and Jun Wan and Lisheng Sun Hosoya and Sergio Escalera and Gintare Karolina Dziugaite and Peter Triantafillou and Isabelle Guyon},
  year          = {2024},
  howpublished  = {arXiv preprint (no journal-ref as of verification)},
  eprint        = {2406.09073},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2406.09073},
  note          = {Not peer-reviewed}
}