Machine Unlearning via Information Theoretic Regularization

Venue: arXiv preprint, 8 Feb 2025, 59 pages (67 in the fetched rendering). No journal-ref. arXiv: 2502.05684 Verification: verified_fetched — arXiv abs page and the PDF.

Read status: pp. 11–17 read from page images — Definitions 2.1–2.5, §2.2 Data unlearning, §2.3 Sufficiency, Lemma 2.1, Theorem 2.1, §2.4 Necessity, Lemma 2.2. Not read: §1 (intro/contributions), §3–§5, and — importantly — §6, which the paper says contains a direct implementation on image classification. That section should be read before the review is drafted.

0. Correction to a premise in the project brief

The project brief describes three of its five named papers as "optimization/ information-theory papers about strongly convex settings." That is accurate for When to Forget? Complexity Trade-offs in Machine Unlearning and Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses. It is not accurate for this one.

Xu & Strohmer assume no convexity anywhere in the results read. Their machinery is mutual information, Fano's inequality, the data-processing inequality, and Pinsker's inequality. Theorem 2.1's bound is described by the authors as "dimension- and output-space-agnostic", and Definition 2.5 is said to be "implementation friendly and scalable in practice, hence particularly applicable in deep learning," with §6 giving a direct implementation on image classification.

This is good news for the thesis: one of the three theory-track papers connects to the vision track directly rather than by analogy. It also changes what the "what transfers?" section must argue — for this paper the question is not whether it transfers but whether its criterion is estimable at ResNet scale.

1. Two problems

The paper treats feature unlearning (remove dependence on an attribute) and data unlearning (remove the influence of a subset of training data) in one framework. Only data unlearning is directly in scope for this thesis; feature unlearning is summarised briefly for completeness.

Feature unlearning

Definition 2.1 (Feature unlearning, independence). \hat Y unlearns feature Z w.r.t. p^r if \hat Y \perp Z, equivalently I(\hat Y; Z) = 0.

Definition 2.2 (MI feature unlearning with utility budget). For tolerances (\varepsilon,\delta), f_\theta achieves (\varepsilon,\delta)-feature unlearning if

Two supporting facts they lean on. Binary Fano (Eq. 3): with \pi := \mathbb{P}(Z=1) and P_{\text{acc}} the Bayes accuracy for predicting Z from \hat Y,

so bounding I(\hat Y;Z) quantitatively limits the best possible inference of Z. And the data-processing inequality: I(T(\hat Y);Z) \le I(\hat Y;Z) for any post-processing T. The utility budget \delta exists to rule out trivial "unlearn-by-collapse" solutions such as constant predictors.

2. The central argument: anchor-based unlearning is inauditable

This is the paper's motivating critique, and it lands directly on how this project's Stage 6 harness is designed.

The anchor-based unlearning principle — the standard one:

No observer should be able to distinguish the released model from the model that would have been obtained by training from scratch on the retain set alone.

Their objection, stated plainly: the criterion "depends on a retrained anchor model that is either unknown or not auditable." More sharply —

"if the anchor-based requirement implicitly allows fresh internal randomness on each verification attempt, and there is no mechanism that binds the curator to the original randomness and training procedure, then a curator can, at least in principle, synthesize or sample outputs that pass an indistinguishability check without performing the intended deletion."

And existing verification schemes "either rely on auxiliary instrumentation (e.g., seeds, logs, gradient commitments, hash attestations) or are brittle to minor pipeline changes, making them easy to spoof and difficult to deploy at scale."

They classify existing definitions into three families, all anchored on the unknown stochastic anchor \Theta_r in parameter space, and therefore "inauditable from the released predictor alone": (anchored) exact unlearning (\mathcal{L}(\Theta_u) = \mathcal{L}(\Theta_r)), divergence relaxation (D(\mathcal{L}(\Theta_u),\mathcal{L}(\Theta_r)) \le \varepsilon), and high-probability relaxation ((\varepsilon,\delta)-indistinguishability).

The proposed alternative: the marginal unlearning principle

No observer should be able to infer anything about the marginal information contributed by the unlearn set (beyond the retain set) from the model's outputs, beyond prior knowledge.

Construction. Let p^u be the unlearn-set distribution and p^d := (1-\alpha)p^r + \alpha p^u the mixture, \alpha \in (0,1] reflecting the cardinality ratio. Introduce a latent Z \sim \text{Bernoulli}(\pi) governing the sampling source, with

and \hat Y_{\text{margin}} := f(X_{\text{margin}}). Unlearning becomes: can an observer infer Z from \hat Y_{\text{margin}}?

Definition 2.3 (\varepsilon-marginal unlearning). Under the balanced auditing prior \mathbb{P}(Z{=}0)=\mathbb{P}(Z{=}1)=\tfrac12:

A worst-case posterior-odds guarantee over all measurable events in output space. At \varepsilon = 0 this is \hat Y_{\text{margin}} \perp Z, i.e. I(\hat Y_{\text{margin}}; Z) = 0.

Definition 2.4 (High-probability (\varepsilon,\delta)-marginal unlearning). Eq. 4 restricted to a good set G with \mathbb{P}(\hat Y_{\text{margin}} \in G) \ge 1-\delta. If I(\hat Y_{\text{margin}};Z) \le \mu, then G_\varepsilon := \{\hat y: |\log \frac{\mathbb{P}(Z=0\mid \hat y)}{\mathbb{P}(Z=1 \mid \hat y)}| \le \varepsilon\} satisfies \mathbb{P}(\hat Y_{\text{margin}} \in G_\varepsilon) \ge 1 - \frac{\sqrt{2\mu}}{\tanh(\varepsilon/2)}.

Definition 2.5 (MI marginal unlearning with utility budget) — the implementable one. With retain risk L(f) := \mathbb{E}_{(X,Y)\sim p^r}[\ell(f(X),Y)] and L^\star := \inf_h L(h), f achieves MI-regularised (\mu,\rho)-marginal unlearning if

\mu = \rho = 0 gives exact marginal unlearning with retain optimality.

The auditability claim, which is the point of the whole construction:

"Both depend only on samples of (X_{\text{margin}}, Z, \hat Y_{\text{margin}}); no anchor or training transcript is needed."

3. Sufficiency and necessity

Lemma 2.1 (MI controls output drift). Let \Theta be independent of (X_{\text{margin}}, Z), and \mu^{p^d}_\Theta := \mathcal{L}(f_\Theta(X_{\text{margin}}) \mid Z{=}0), \mu^{p^r}_\Theta := \mathcal{L}(f_\Theta(X_{\text{margin}}) \mid Z{=}1). Then

Theorem 2.1 (Marginal unlearning + utility ⇒ approximate unlearning). With \Theta_u the unlearned model, \Theta_r the retrained anchor, log-loss regret \mathrm{reg}_{\log}(f) := \mathbb{E}_{X\sim p^r}[D_{\mathrm{KL}}(\mathcal{L}(Y\mid X) \,\|\, \mathcal{L}(f(X)\mid X))], and assuming \overline{\mathrm{reg}}_{\log}(f_{\Theta_u}) \le \delta, \overline{\mathrm{reg}}_{\log}(f_{\Theta_r}) \le \delta_g, I(\hat Y_{\text{margin}};Z) \le \varepsilon_u, and \Theta_u \perp (X_{\text{margin}},Z):

So marginal unlearning recovers the anchored guarantee when paired with utility control — without needing the anchor to audit. The authors note the bound is dimension-agnostic because log-loss regret is an expected KL and Pinsker converts KL to TV on general measurable spaces, and that "many standard AI/ML objectives instantiate log-loss (classification cross-entropy, GLMs, likelihood-based deep models, CRFs, etc.), making the theorem broadly applicable."

Lemma 2.2 (Necessity, for "good" retrained models). For a retrained f that is L-Lipschitz with continuous output densities p_0, p_1 and \mathcal{W}_{d_\mathcal{X}}(X_1,X_0) > 0: either the likelihood-ratio bound \operatorname{ess\,sup}_y |\log \frac{p_1(y)}{p_0(y)}| \le \varepsilon holds, or there is a point y^\star where it fails and a local radius \rho_\star(y^\star)>0 with

i.e. inclusion leakage forces a large Lipschitz constant. Informally: a model cannot simultaneously leak inclusion, generalise well, and stay regular.

4. What this means for our evaluation harness

This paper is the one that most directly challenges a design decision already made.

Stage 6's forgetting metric is the gap versus the retrain oracle — precisely the anchor-based criterion Xu & Strohmer argue is inauditable. Their objection does not make our harness wrong, but it sharpens what it can claim:

• Their critique is about third-party auditing, not about scientific measurement. We do control the randomness and the training procedure — the whole determinism apparatus exists for that. The spoofing scenario they describe (a curator synthesising outputs that pass a check) is a threat model that does not apply to a researcher measuring their own pipeline. Our oracle comparison remains valid for our purpose.
• But it identifies a real limitation to state. Any claim of the form "SCRUB matches the retrain oracle, therefore it has unlearned" inherits the anchor's weaknesses: the anchor is one draw from a distribution over retrained models, and our 3–5 seeds estimate that distribution coarsely. The paper's framing is a good argument for reporting the oracle's own seed variance as a first-class quantity rather than treating a single oracle as ground truth.
• Definition 2.5 is estimable and worth considering as a supplementary metric. It needs only samples of (X_{\text{margin}}, Z, \hat Y_{\text{margin}}) — no anchor. A mutual-information estimate between the model's outputs and the source label is computable from artifacts we will already have. Whether MI estimation is reliable at our sample sizes (CIFAR-5 has 500 training images) is the open question, and small-n MI estimation is notoriously biased.

Not a Stage 6 change yet. The harness freezes before methods are implemented, and adding a metric on the strength of a paper whose §6 I have not read would be premature. Recorded here as a candidate, to be decided once §6 is read.

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

• No convexity assumptions — but also no computational complexity results, so it says nothing about whether unlearning is cheaper than retraining.
• No experiments in §2. §6 reportedly implements on tabular data and image classification; unread, and the review must not characterise those results until it is.
• MI estimation difficulty at finite sample sizes is not addressed in the sections read.
• The auditing prior \pi and mixing ratio \alpha are free parameters; how to choose them in practice is not covered in §2.

6. Links

• Directly critiques the anchor-based definitions underlying Machine Unlearning, Making AI Forget You: Data Deletion in Machine Learning, and the reference-unlearning definition used by When to Forget? Complexity Trade-offs in Machine Unlearning.
• Its auditability critique overlaps with On the Necessity of Auditable Algorithmic Definitions for Machine Unlearning, which should be read next to see whether they converge.
• Contrasts with Near-Optimal Pure Machine Unlearning for Smooth Strongly Convex Losses and When to Forget? Complexity Trade-offs in Machine Unlearning: no convexity, no complexity claims, deep learning explicitly in scope.
• Relevant to how Towards Unbounded Machine Unlearning's oracle-gap metrics should be interpreted.

@misc{xu2025infotheoretic,
  title         = {Machine Unlearning via Information Theoretic Regularization},
  author        = {Shizhou Xu and Thomas Strohmer},
  year          = {2025},
  howpublished  = {arXiv preprint (no journal-ref as of verification)},
  eprint        = {2502.05684},
  archiveprefix = {arXiv},
  url           = {https://arxiv.org/abs/2502.05684},
  note          = {Not peer-reviewed}
}