On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning

Venue: USENIX Security Symposium 2022 · arXiv: 2110.11891 Verification: dblp for venue; PDF fetched.

Read status: pp. 7–10 read from page images — §4.2 Forgeable and Models (Lemmas 1–2, Theorem 1), §4.3 Consequence to Defining Unlearning, §5 Methods for Forging (§5.1 Lemma 3, §5.2 Lemma 4, §5.3 mean sampling), Theorem 2, Corollary 1, Theorem 3, §5.4 Corollary 2. §1–3, §6–§7 and proofs not read.

The strongest negative result in this project's reading, and it applies specifically to minibatch SGD — the algorithm we use.

1. Forging

A forging map B: H_D \to H_{D'} rewrites a training log so that the same parameter trajectory is explained by a different dataset. For a log \{(w_i, x_i)\}_{i\in J}, B(\{(w_i,x_i)\}) = \{(w_i, \tilde x_i)\} \in H_{D'} — same weights at every step, different data points held responsible for them, within reproduction error \varepsilon.

Lemma 1. If D and D' are forgeable with \varepsilon = 0, then H_D(w) = H_{D'}(w) — "the set of all models achieved by training on D using g is the same as the set of all models achieved by training on D' using g."

Lemma 2. \varepsilon = 0 forgeability is an equivalence relation.

Theorem 1 (Characterising \varepsilon = 0 equivalence classes). D and D' are \varepsilon = 0 forgeable iff H_D(W) = H_{D'}(W).

2. §4.3 — why this makes approximate unlearning ill-defined

Suppose a forging map exists from D to D', where D' does not contain the point x^* we are asked to forget. The model owner trained on D and holds the log H_D. Then:

"we can use the forging map B to find some data points in D' to mock the updates made by the data points to be unlearned. This results in a valid … H_{D'}, where the final model parameters are the same as before unlearning, but the data points to be unlearned are not used in the log of training.

Such model parameters satisfy what approximate unlearning defines — they are the same as model parameters obtained by not using the unlearned data points at all. However, no modifications were done to the parameters at all. This means that if the model owner wants to approximately unlearn their model, then by definition they do not need to do anything and can claim the unlearning is done. Thus we come to the conclusion that if there exists a forging map between D and D/x^*, then the approximate unlearning is ill-defined."

And it invalidates proof-of-unlearning too. Proof-of-Learning-style verification fails because "(1) in theory PoL only verifies if the computation from a checkpoint w_i to the next … is plausible, which is essentially what a forging map … does … (2) PoL was originally designed for ownership so it was designed for a threat model where the adversary does not have access to the log. This assumption is not valid in the case of unlearning since the adversary aiming to circumvent unlearning is the model owner themselves."

The conclusion they draw:

"unlearning cannot be defined on the parameter space since the existence of a forging map implies that the effect of a data point can be obtained by considering another one (or few) data point(s). Notably, this means one cannot verify unlearning (exact or approximate) at the model-level as there is no universally verifiable unlearning property of the weights. Therefore, to define and verify unlearning, we need to focus on the process/algorithm the unlearned model was obtained with."

With a specific consequence for certified unlearning: those approaches "have the advantage of providing rigorous guarantees at the model level, [but] our work shows that they need to be combined with a verification at the algorithmic level, e.g. verifying a training algorithm is DP, to ensure that the algorithm used was indeed the certified algorithm."

🔗 This lands directly on SISA's definition

Machine Unlearning Definition III.1 explicitly permits plausible deniability: the owner need not retrain "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."

Forging is precisely the construction of that evidence without doing the work. The two papers should be presented together in the review: SISA defines unlearning by plausible reproducibility, and Thudi et al. show that plausibility is forgeable.

3. §5 — when forging is possible, and Corollary 2

Three routes:

• §5.1, Lemma 3 (similar forgeability). If the update rule g is L-Lipschitz in the data point, then d(x,\tilde x) \le \varepsilon/L suffices to interchange them in the log. Similar data points ⟹ forgeable datasets.
• §5.2, Lemma 4 (densely packed updates). If for all w and x there is x_i \in D' with d(g(w,x), g(w,x_i)) \le \varepsilon, then D' forges every D \subset X. Such a D' "could be dubbed a 'universal' forger."
• §5.3 mean sampling, i.e. minibatch SGD, which is the case that matters.

Theorem 2 (Probabilistic forging). For D, D' sampled i.i.d. from \mathfrak{D} with minibatches of size b and g a mean sampler, D' forges D with probability at least \big((1-\sigma^2_{max}/(b\varepsilon^2))(1-(\sigma^2_{max}/(b\varepsilon^2))^n)\big)^{m\alpha}.

The factors that make forging easier: "increasing |D'| = n, increasing the minibatch sizes b, decreasing the maximum length of a log, or the number of logs."

Corollary 1 (large minibatches). As b \to \infty, D and D' "are forgeable for all \varepsilon > 0 with probability going to 1."

Theorem 3 (existence of a forging adversary). If an adversary controls b and can sample from \mathfrak{D} indefinitely, then for every \varepsilon > 0, for almost every D there is \tilde D \supset D forgeable by a disjoint dataset D'.

Corollary 2 — the paper's main conclusion:

"Unlearning on minibatch SGD is not well-defined over the logs (and thus the models) of finite datasets obtained from a distribution \mathfrak{D}, for any such distribution \mathfrak{D}."

"This is best understood because forgeability implies that models or checkpoints (or distribution of models or checkpoints) are both unlearnt and not unlearnt at the same time."

4. What this means for this project

It does not invalidate what we are doing, and it is important to be precise about why.

The result concerns verifiability against an adversarial model owner. It says a third party cannot audit an unlearning claim from weights or logs alone, because the owner could forge. Our threat model is different: we are the researcher, we control the training, and we are measuring our own pipeline with recorded seeds, config hashes and split hashes. Nobody is trying to deceive us.

What it does change is what the reproduction may claim.

1. "SCRUB's weights match the oracle's" is not, by itself, evidence of unlearning — not because SCRUB is doing anything wrong, but because Theorem 1 says no weight-level property universally certifies unlearning. Our oracle-gap metric is a comparative empirical measure, and the review should say so.
2. Larger minibatches make forging easier (Corollary 1). SCRUB's Table 3 uses forget-set batch sizes up to 512. This is a curiosity rather than a defect for us, but it is a concrete link between a hyperparameter we will actually set and a theoretical result — the kind of connection the review's theory section should be making.
3. The prescription — verify the process, not the artifact — is exactly what our Stage 2 provenance apparatus does. Config hash, git SHA, split hash, seed and library versions recorded per run is algorithmic-level verification. Worth stating explicitly in the review: this project's reproducibility machinery is a direct instantiation of what Thudi et al. argue is necessary, even though we built it for a different reason.

Third independent line converging on the same point. Weight-space matching is neither sufficient (Towards Adversarial Evaluations for Inexact Machine Unlearning Thm. 1), nor auditable from outputs (Machine Unlearning via Information Theoretic Regularization), nor verifiable from logs (here). The review can present these as one coherent argument rather than three scattered objections — and note that all three postdate the definitions they criticise, which is itself a story about how the field matured.

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

• §1–3, §6 (experiments), §7 (proposed ways forward, including "facilitating external scrutiny of the algorithm") unread.
• The results are about definability and verifiability, not about whether any particular unlearning method works empirically.
• The forging adversary of Theorem 3 requires control over b and unbounded sampling — strong powers, though the authors argue they are realistic for a model owner.
• Note the assumption that the verifier "can not use \varepsilon = 0 simply because of floating point precision."

6. Links

• Cited by Towards Unbounded Machine Unlearning §4 as showing weight proximity is not sufficient, alongside Towards Adversarial Evaluations for Inexact Machine Unlearning on necessity.
• Undercuts the plausible-deniability clause in Machine Unlearning Definition III.1.
• Its auditability argument is the one Machine Unlearning via Information Theoretic Regularization extends into a positive proposal (output-space marginal unlearning).
• Companion paper Unrolling SGD: Understanding Factors Influencing Machine Unlearning, not yet read.
• Its "verify the algorithm, not the artifact" prescription is what docs/ARCHITECTURE.md's provenance design implements in practice.

@inproceedings{thudi2022auditable,
  title         = {On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning},
  author        = {Anvith Thudi and Hengrui Jia and Ilia Shumailov and Nicolas Papernot},
  year          = {2022},
  booktitle     = {USENIX Security Symposium 2022},
  pages         = {4007--4022},
  eprint        = {2110.11891},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2110.11891}
}