1 Introduction↩︎

Machine unlearning is the task of removing the influence of specific training samples from an already-trained model, ideally yielding a model that behaves as if those samples had never been seen during training [1]. Simply deleting a data point from the training set does not achieve this: its information remains embedded in the learned parameters and can often be recovered by an adversary with query access, e.g.via membership inference attacks [2], [3]. This motivates exact unlearning, which produces a model with the same distribution as one retrained from scratch on the retained data [4], [5], and approximate unlearning, which relaxes this requirement in exchange for efficiency [6]–[10].

While exact unlearning offers the strongest guarantees, it is largely impractical at scale: existing schemes are either restricted to simple models such as \(k\)-means [5] or rely on data sharding [4], trading utility for cheap deletion. To scale to deep networks, a parallel line of work develops approximate unlearning algorithms, with two kinds of compromise. The first family is heuristic and provides no formal guarantee, including Fisher/Hessian-based parameter scrubbing [9], gradient ascent on the forget set, fine-tuning on the retain set, and interleaved ascent–descent schemes such as SCRUB [10]. The second family adopts the certified \((\varepsilon, \delta)\)-indistinguishability notion of [6], borrowed from differential privacy, which requires the unlearned model to be \((\varepsilon, \delta)\)-indistinguishable [11] from one retrained from scratch. This guarantee bounds the distinguishing advantage of any test operating on the unlearnt model relative to the baseline retrained model. Most certified-unlearning algorithms require (strong) convexity of the loss [6]–[8], [12], [13] or a unique minimiser [14]; only a handful of recent methods provide certified guarantees for genuinely nonconvex losses [15]–[18].

While the bounds above are theoretical, our goal in this paper is to design an auditor that uses empirical evidence to test whether a claimed unlearning guarantee actually holds. Formally, our goal is to reject the hypothesis \(\varepsilon < \varepsilon_{\text{LB}}\) for any certified \((\varepsilon,\delta)\) unlearning algorithm in the spirit of recent work on differential-privacy auditing [19]–[21].

While our audit draws on differential-privacy auditing, the unlearning setting is closer in spirit to group privacy [11]: certified unlearning gives \((\varepsilon,\delta)\)-indistinguishability under deletion of an arbitrary subset of forget points rather than a single point, and the two notions differ by a multiplicative blow-up in \(\varepsilon\). Off-the-shelf DP auditors therefore certify only the weaker single-point neighbouring guarantee and yield loose \(\varepsilon\) bounds in the unlearning setting; our meta-algorithm (2) extends the one-run auditor of [21] with new bounds tailored to subset-level guarantees. Our key contributions are summarised below.

• Threat model. We adopt a strong adversary with black-box knowledge of the learning algorithm, the unlearning algorithm, the data-loading shuffler, and the initial model weights at the start of training. The adversary knows the underlying random mechanism used by these procedures but does not observe its specific random realisation on any given run.

• Auditor. Leveraging the definition of \((\varepsilon,\delta)\)-unlearning with respect to arbitrary forget subsets, we design a hypothesis test that rejects the null hypothesis \(\varepsilon < \varepsilon_{\mathrm{LB}}\) with controlled Type I error for the case of \(\delta=0\) (see 2).

• Empirical evaluation. We develop two instantiations of this auditor in 5 and evaluate them across a range of unlearning algorithms, revealing a sharp separation between certified and uncertified methods: certified unlearning algorithms yield very small \(\varepsilon\) lower bounds, whereas uncertified algorithms produce lower bounds that frequently exceed \(50\)–\(60\).

2 Related work↩︎

Empirically lower-bounding the privacy parameter \(\varepsilon\) of an \((\varepsilon,\delta)\)-DP mechanism has been studied in [19], [20], [22], [23], typically by planting canaries in a pair of neighbouring datasets and converting distinguishing accuracy into an \(\varepsilon\) lower bound via the hypothesis-testing interpretation of DP [24], [25]. These approaches require many independent training runs to drive the audit’s Type I/II error down. More recent work [21], [26] reduces the run cost to a single training run for \((\varepsilon,\delta)\)-DP and \(f\)-DP respectively, by planting many independent canaries and auditing them jointly within one run.

Our auditor borrows the joint-canary idea from [21], but the transfer to unlearning is not direct. As argued above, the subset-level guarantee yields weaker per-canary signal than the single-point neighbouring relation underlying standard DP audits, so we aggregate across multiple runs to obtain tight \(\varepsilon\) lower bounds, and converting the joint canary statistics into a valid bound under this neighbouring relation requires new lemmas. To tighten the resulting bounds further, we replace the loss-difference scoring of [21], [26] with a LiRA-style [3] per-canary likelihood-ratio test on logit-scaled confidences, fitting Gaussians to the canary’s score under the in-forget-set and never-seen hypotheses.

A separate line of work audits unlearning directly rather than DP: backdoor-based verification (e.g.Athena [27], though [28] show such schemes can be gamed by a dishonest provider), output-difference audits such as TAPE [29] that train a reconstructor on the gap between pre- and post-unlearning models, and sample-level audits returning per-example unlearning-completeness scores [30]–[32]. Our auditor instead returns a quantity calibrated to the certified-unlearning parameter \(\varepsilon\) itself, rather than a per-example completeness score: an empirical lower bound on the algorithm’s \(\varepsilon\) that is directly comparable to its claimed \((\varepsilon, \delta)\) guarantee.

Early MIA formulations [2], [33] were sharpened by likelihood-ratio attacks (LiRA [3], RMIA [34]). In the unlearning setting, [35], [36] exploit the difference between original and unlearned models to infer or reconstruct deleted samples. These formulations often assume access to both pre and post unlearning models where as our audit is formulated around access to just the unlearnt model.

3 Problem setup↩︎

3.1 Unlearning definition↩︎

Let \({\mathcal{A}}\) be a training algorithm that, given a dataset \({\mathcal{D}}\), outputs a trained model \({\mathcal{A}}({\mathcal{D}})\). Suppose a subset \({\mathcal{D}}_f \subseteq {\mathcal{D}}\), called the forget set, is requested to be removed. We write \({\mathcal{D}}_r := {\mathcal{D}}\setminus {\mathcal{D}}_f\) for the corresponding retain set.

A natural baseline for unlearning is to retrain the model from scratch on \({\mathcal{D}}_r\). However, full retraining is often computationally expensive. The goal of an unlearning algorithm is therefore to produce, more efficiently, a model whose distribution is close to that of a suitable retraining procedure on the retain set. Formally, an unlearning algorithm \({\mathcal{U}}\) takes as input the trained model, the full dataset, and the forget set, and outputs an unlearned model \(f_u = {\mathcal{U}}\big({\mathcal{A}}({\mathcal{D}}), {\mathcal{D}}, {\mathcal{D}}_f\big)\).

3.2 \((\varepsilon,\delta)\) indistinguishability [11]↩︎

3.3 Certified unlearning↩︎

Informally, an observer cannot distinguish the unlearned model from one produced using only the retain set, except up to \((\varepsilon, \delta)\).

3.4 Threat model↩︎

The general definition above leaves the adversary’s auxiliary information unspecified. To make the audit concrete, we fix the following threat model. We consider a black-box adversary that additionally observes (i) the initial model \(x_o\) at the start of training, and (ii) the shuffling order \(\pi\) of training data-points within each epoch; the adversary has no access to any other sources of randomness used during training or unlearning. These assumptions strengthen the adversary relative to the standard threat model, and crucially do not weaken the certified-unlearning guarantees of certified unlearning algorithms: both the model clipping algorithm (a.k.a.noisy fine-tuning) of [15] and rewind-to-delete (R2D) [16] remain \((\varepsilon,\delta)\)-certified under this stronger adversary.²

Because the adversary observes \(x_o\) and \(\pi\), the indistinguishability requirement must hold conditional on them; the reference algorithm is allowed to depend on \((x_o, \pi)\) as well. Let \({\mathcal{A}}_{x_o, \pi}({\mathcal{D}})\) denote the learning algorithm started at \(x_o\) with shuffling order \(\pi\).

Our goal is to design an auditor (or adversary) that, given black-box access to \({\mathcal{A}}\) and \({\mathcal{U}}\) together with the initial model \(x_o\) and shuffling order \(\pi\) from our threat model, produces a data-dependent lower bound \(\varepsilon_{\mathrm{LB}}\) on the true unlearning parameter \(\varepsilon\). We formalise the audit as a one-sided hypothesis test: for a confidence level \(\zeta \in (0, 1)\), the auditor outputs \(\varepsilon_{\mathrm{LB}}\) such that, under \(H_0 : \varepsilon \le \varepsilon_{\mathrm{LB}}\), the test rejects with probability at most \(\zeta\). Whenever the test rejects, the true parameter exceeds \(\varepsilon_{\mathrm{LB}}\) with confidence \(1 - \zeta\), so a high \(\varepsilon_{\mathrm{LB}}\) is direct evidence that the unlearning guarantee, if any, is weak. The main paper focuses on \(\delta = 0\); see 4.1. A discussion on extension of the test beyond \(\delta=0\) is given in 12.

4 The algorithm↩︎

We now describe the meta-algorithm underlying our audit; pseudocode is given in 2. The auditor has black-box query access to \({\mathcal{A}}\) and \({\mathcal{U}}\), which lets it run training-and-unlearning repeatedly on inputs of its choosing. At a high level, each run samples a balanced sign vector \(S^{(\ell)}\), uses \(S^{(\ell)}\) to decide which candidate batches are placed in the forget set, runs training followed by unlearning, and asks the auditor to predict \(S^{(\ell)}\) from the resulting unlearned model. The construction extends the many-canary auditing paradigm used for differential privacy [20], [21], [37] to the unlearning setting.

4.0.0.1 Setup.

The training dataset is partitioned into \(n\) batches of size \(B\). Let \({\mathcal{B}}\) denote the universe of batches; the candidate forget pool \({\mathcal{D}}_f \subseteq {\mathcal{B}}\) contains \(m\) batches and the retain set \({\mathcal{D}}_r\) contains the remaining \(n - m\). We further partition \({\mathcal{D}}_f\) into \(m\) candidate forget batches \({\mathcal{D}}_f = \bigcup_{j=1}^m {\mathcal{D}}_{f,j}\). Throughout, we fix the initial model \(x_o\) and the batch-shuffling order \(\pi\) (both observed by the auditor under our threat model), and suppress them from notation. We define the set of approximately balanced sign vectors \[{\mathcal{S}}_{m}:= \{\, s \in \{\pm 1\}^m : 0 \le \#\{j : s_j = -1\} - \#\{j : s_j = +1\} \le 1 \,\},\] i.e., vectors with as many \(+1\)s and \(-1\)s as possible (one extra \(-1\) when \(m\) is odd, by convention). For \(S \in {\mathcal{S}}_m\), let \({\mathcal{D}}_f(S) := \bigcup_{j : S_j = +1} {\mathcal{D}}_{f,j}\) be the sampled forget set under \(S\) and \({\mathcal{D}}(S) := {\mathcal{D}}_r \cup {\mathcal{D}}_f(S)\) the corresponding training set.

4.0.0.2 Audit procedure.

Fix an even guess budget \(r\). In each of \(L\) independent runs, the auditor:

1. samples \(S^{(\ell)} \sim \mathrm{Unif}({\mathcal{S}}_m)\) and computes the unlearned model \(f_u^{(\ell)} \gets {\mathcal{U}}\bigl({\mathcal{A}}({\mathcal{D}}(S^{(\ell)})),\; {\mathcal{D}}(S^{(\ell)}),\; {\mathcal{D}}_f(S^{(\ell)})\bigr)\)

2. produces a guess \(\widehat{S}^{(\ell)} \in \{-1, 0, +1\}^m\) with exactly \(r/2\) entries equal to \(+1\) and \(r/2\) equal to \(-1\) (the remaining \(m - r\) entries are \(0\), indicating abstentions);

3. records the overlap score \(V^{(\ell)} := \sum_{j=1}^{m} \max\{0,\; \widehat{S}_j^{(\ell)} S_j^{(\ell)}\}\), which counts the number of correct nonzero guesses (out of \(r\)).

The audit reports a summary statistic (mean or median) of \(\{V^{(\ell)}\}_{\ell=1}^L\), which 2 converts into the lower bound \(\varepsilon_{\mathrm{LB}}\).

For analysis, 2 induces a randomized mechanism \({\mathcal{M}}: {\mathcal{S}}_{m}\to \{-1, 0, +1\}^m\) with \({\mathcal{M}}(S^{(\ell)}) := \widehat{S}^{(\ell)}\). Although \({\mathcal{M}}\) may invoke \({\mathcal{A}}\) and \({\mathcal{U}}\) arbitrarily many times, the only quantities hidden from it are the sampled sign vector \(S^{(\ell)}\) and the internal randomness of \({\mathcal{A}}, {\mathcal{U}}\) within each run (e.g.gradient noise) – the latter being precisely the randomness on which the algorithms’ \((\varepsilon, \delta)\)-certified guarantees rely. Both are accessed only through the unlearned model \(f_u^{(\ell)}\), so \({\mathcal{M}}\)’s output is post-processing of \(f_u^{(\ell)}\) and the certified-unlearning guarantee passes through unchanged. Under strong unlearning, batches in and out of the forget set are nearly indistinguishable, so any overlap score reliably above the random-guessing baseline \(r/2\) is evidence of weak unlearning; 2 converts the mean (or median) of \(\{V^{(\ell)}\}_{\ell=1}^L\) across independent runs into a precise lower bound on \(\varepsilon\), with two instantiations of \({\mathcal{M}}\) given in 5.

4.1 Reduction to local differential privacy↩︎

We now show that the audit reduces to a standard local-differential-privacy (LDP) lower-bound problem, which lets us import existing tools for LDP auditing. Recall from the previous section that, conditional on the fixed dataset \({\mathcal{D}}\), initial model \(x_o\), and shuffling order \(\pi\), the auditor induces a randomized mechanism \({\mathcal{M}}: {\mathcal{S}}_{m}\to \{-1, 0, +1\}^m\) that maps the sampled sign vector \(S\) to a prediction \({\mathcal{M}}(S) := \widehat{S}\). Concretely, for \(S \in {\mathcal{S}}_{m}\), let \({\mathcal{D}}_f(S) \subseteq {\mathcal{D}}_f\) denote the forget subset encoded by \(S\), let \[f_u(S) := {\mathcal{U}}\bigl({\mathcal{A}}({\mathcal{D}}_r \cup {\mathcal{D}}_f(S)),\, {\mathcal{D}}_r \cup {\mathcal{D}}_f(S),\, {\mathcal{D}}_f(S)\bigr),\] and let \(f_r := {\mathcal{A}}({\mathcal{D}}_r)\) denote the retrained reference. The auditor’s prediction \({\mathcal{M}}(S)\) is computed from \(f_u(S)\) alone (with possibly many queries to \({\mathcal{A}}\) and \({\mathcal{U}}\), but no direct access to \(S\) or to the internal randomness of \({\mathcal{A}}, {\mathcal{U}}\)).

4.2 Lower bound on \(\varepsilon\) from overlap score↩︎

Given an observed statistic \(v\) (the empirical mean or median of \(\{V^{(\ell)}\}_{\ell=1}^L\)), we set the right-hand side of the relevant bound from 2 to a target level \(\zeta\), fix \(\delta = 0\), and solve for \(\varepsilon\) to obtain an LDP lower bound; dividing by \(2\) to undo the reduction of 1 yields the reported \(\varepsilon_{\mathrm{LB}}\). To reject \(H_0 : \varepsilon \le \varepsilon_{\mathrm{LB}}\) at level \(\zeta\), it suffices to evaluate the bound at \(\varepsilon = \varepsilon_{\mathrm{LB}}\), since both bounds are monotone non-decreasing in \(\varepsilon\) (1).

5 Two instantiations of the auditor meta-algorithm↩︎

We now instantiate the abstract mechanism \({\mathcal{M}}\) from 2 in two ways, and contrast both with a pairwise baseline adapted from DP auditing. Both instantiations use repeated runs of training and unlearning to calibrate a likelihood-based predictor, but differ in what they predict from the final unlearned model. Instantiation I scores each candidate forget batch independently and is suitable when \(m\) is too large to enumerate \({\mathcal{S}}_{m}\); Instantiation II treats each balanced sign vector as a hypothesis and exploits cross-batch correlations, but is practical only when \(|{\mathcal{S}}_{m}|\) is enumerable.

For a model \(f\), write \(f(x)_y\) for the probability assigned to label \(y\) on input \(x\) and \(\phi(p) := \log\!\left(\tfrac{p}{1-p}\right)\) for the logit transform. We write \(\mathcal{N}(s; \mu, \sigma^2) := \tfrac{1}{\sqrt{2\pi\sigma^2}} \exp\!\left(-\tfrac{(s-\mu)^2}{2\sigma^2}\right)\) for the Gaussian likelihood. Modelling scores as Gaussian is a choice for the attack only; 2 requires no such assumption.

5.0.0.1 Instantiation I: Batchwise inclusion/exclusion prediction.

When \(m\) is large, enumerating \({\mathcal{S}}_{m}\) is infeasible, so we score each batch independently. For every forget example, we fit two Gaussians to the logit scores collected across \(\Gamma\) independent calibration runs \({\mathcal{U}}({\mathcal{A}}({\mathcal{D}}(S)), {\mathcal{D}}, {\mathcal{D}}_f(S))\) with \(S \sim {\mathrm{Unif}}({\mathcal{S}}_{m})\): an in-distribution conditioned on \(S_j = +1\) and an out-distribution conditioned on \(S_j = -1\), in the spirit of LiRA [3].⁴ At evaluation, for each batch we sum per-point log-likelihoods under the in- and out-distributions separately and take their difference to obtain a batch score \(\Lambda_j\). We then predict \(+1\) for the top \(r/2\) batches by \(\Lambda_j\), \(-1\) for the bottom \(r/2\), and \(0\) for the rest. Calibration runs and evaluation runs are drawn independently, which is required for the audit’s lower bound to be valid. See 3 for pseudocode.

5.0.0.2 Instantiation II: Joint sign-vector prediction.

When \(|{\mathcal{S}}_{m}|\) is enumerable, we treat each candidate sign vector as a hypothesis, capturing cross-batch correlations that batchwise scoring ignores. During calibration, for every candidate \(\widetilde{S} \in {\mathcal{S}}_{m}\) and every forget example \((x, y)\), we fit a Gaussian to the logit scores collected from \(\Gamma\) independent runs of \({\mathcal{U}}({\mathcal{A}}({\mathcal{D}}(\widetilde{S})), {\mathcal{D}}, {\mathcal{D}}_f(\widetilde{S}))\). At evaluation, we score each candidate by the cumulative log-likelihood of the observed scores under its fitted Gaussians and return the highest-scoring candidate. Since the auditor commits to a full sign vector, \(r = m\) here. See 4 for pseudocode.

5.0.0.3 Pairwise auditor (baseline).

As a baseline we adapt the pairwise distinguishability auditor of [22], which distinguishes two unlearned models trained on different forget sets and converts true/false positive rates into an \(\varepsilon\) lower bound via [24] with Clopper–Pearson confidence intervals; the full description and exact formula are deferred to 10.3.

6 Datasets and auditor setup↩︎

6.0.0.1 CIFAR-100 [39].

We train a TinyNetCIFAR100 model to \({\sim}55\%\) validation accuracy. The forget set \({\mathcal{D}}_f\) contains \(10\%\) of training points (\(4{,}500\)); we use a uniform split (sampled at random) and an adversarial split (forget and retain drawn from largely disjoint label classes). Audit batch size is \(B=1\) for uncertified and \(B=750\) for certified algorithms; the rationale and full construction are in [sec:appendix_cifar100_dataset] [sec:instantiation95discussion95certified95uncertified].

6.0.0.2 Shakespeare [40].

Following [41] we treat each role as a client, subsample \(300\) roles, and partition at the role level into \(33\) forget roles (\({\sim}10\%\) of training characters) and \(267\) retain roles. The model is a \(2\)-layer character-level LSTM reaching \({\sim}0.53\) accuracy; we evaluate only uncertified methods, using the batchwise inclusion/exclusion auditor with \(B=400\). Full construction, score definition, and model details are in 13.2.

7 Unlearning Algorithms Audited↩︎

For all runs below, \(\varepsilon_{\mathrm{LB}}\) denotes the lower bound obtained from the mean aggregation of overlap scores in 2.⁵ For all experiments, the confidence parameter \(\zeta\) is set to \(0.05\).

We organise the audited algorithms into two groups: certified algorithms with formal \((\varepsilon,\delta)\) guarantees (7.1), and heuristic algorithms without such guarantees (7.2). 7.3 discusses them in detail, and full hyperparameters and per-method experimental details are deferred to 16.

7.1 Certified unlearning algorithms↩︎

7.1.0.1 Model clipping.

We audit the certified unlearning algorithm of [15], which interleaves projected noisy gradient steps on an \(\ell_2\)-ball of radius \(C_2\) with a noiseless retain-set fine-tuning phase. The number of noisy steps is set by Theorem 4.2 of [15] to achieve the target \((\varepsilon,\delta)\) guarantee. Recalling the certified-method auditor configuration of 6.0.0.1—batch size \(B=750\) (\(m=6\) forget batches), joint sign-vector predictor (4) with \(\Gamma=50\) calibration rounds and \(L=100\) runs—we sweep \(\varepsilon\), \(C_2\), and \(\sigma\) across target privacy levels spanning five orders of magnitude (up to \(\varepsilon=10^5\)). At the prescribed stopping time of Theorem 4.2, the audit yields \(\varepsilon_{\mathrm{LB}} \approx 0\) across the entire grid, consistent with the certification holding. As a diagnostic, we additionally compute \(\varepsilon_{\mathrm{LB}}(t)\) at intermediate iterates—treating the algorithm as if it had terminated at step \(t\)—which remains near zero throughout the noisy phase, indicating that the audit gains no traction even between certification checkpoints. Full details are reported in 16.1.

7.1.0.2 Uncertified variant of model clipping.

For this uncertified variant, we set \(C_2=5\) and \(\sigma=10^{-4}\) and truncate the noisy phase to \(10\) epochs, after which the algorithm proceeds to its retain-set fine-tuning phase as in the certified setting. The ratio \(C_2/\sigma\) is far larger than what Theorem 4.2 admits, so the algorithm is no longer certified; we report \(\varepsilon_{\mathrm{LB}}\) as a function of step index \(t\) with \(L=500\) runs to obtain tighter bounds (1 (a)). Further details are given in 16.1.3. We compare both uniform and adversarial splits.

7.1.0.3 Rewind-to-delete.

Rewind-to-delete (R2D) provides certified unlearning in the full-batch setting by adding final-step Gaussian noise calibrated, per Theorem 3.1 of [16], to make the trained and unlearned models \((\varepsilon, \delta)\)-indistinguishable. The noise scale, sensitivity, and other choices are detailed in 16.2. We consider both uniform and adversarial splits, with plots in 1 (c).

7.1.0.4 Observations.

R2D attains tighter lower bounds than model clipping across the sweep, reflecting its single-shot full-batch noise calibration versus model clipping’s per-step noise budget over many iterations. Both methods exhibit the uniform-vs.adversarial split asymmetry discussed in 7.3.

7.2 Uncertified unlearning algorithms↩︎

We audit four heuristic unlearning algorithms on both CIFAR-100 and Shakespeare: Hessian-based unlearning, interleaved descent–ascent retraining, ascent on the forget set, and pure fine-tuning on the retain set. Base-training settings and per-method learning-rate schedules are deferred to [sec:appendix_uncertified_methods] [sec:appendix_ida_retraining] [sec:appendix_ascent_on_forget]. We choose support size \(r=100\) for the Shakespeare dataset (with \(m=400\) forget batches) and support size \(r=3000\) for CIFAR-100 (with \(m=4500\) batches). The number of calibration rounds \(\Gamma\) is set to \(50\) and \(L=10\) evaluation runs.

7.2.0.1 Hessian-based unlearning.

We audit the Hessian-based unlearning algorithm of [13], which performs a Newton-style update on the forget-set gradient followed by addition of Gaussian noise to every parameter. [13] prove certification under loss convexity; we test the algorithm in the nonconvex regime where this assumption is violated. The explicit update rule, the LiSSA approximation of the inverse-Hessian–vector product [42], hyperparameter settings, and an ablation varying the final noise scale are deferred to 16.4.

7.2.0.2 Interleaved descent–ascent (IDA) retraining.

IDA alternates retain-set gradient descent with \(\lambda\)-weighted forget-gradient steps inserted after every \(q\) retain steps, for the first \(E_f\) epochs only; thereafter it reverts to plain retain descent. Update rule and per-dataset \((\lambda, q, E_f)\) are in 16.5.

7.2.0.3 Ascent on the forget set.

In this setup the unlearning phase consists of plain gradient ascent on the forget set, run for a fixed number of epochs (2 epochs for both datasets) and then followed by retain-set fine-tuning (analogous to the second phase of ). Per-dataset learning rates, schedules, and the explicit update rule are given in 16.6.

7.2.0.4 Pure fine-tuning on the retain set.

The unlearning phase consists of pure fine-tuning on the retain set throughout. Equivalently, this is a special case of model clipping with clipping radius \(C_2=\infty\) and noise scale \(\sigma=0\). Learning-rate schedules match the retain-set fine-tuning phase of the corresponding base-training configuration (16.3).

7.3 Comparison of lower bounds across methods↩︎

[tab:lower_bound_comparison_shakespeare,tab:lower_bound_comparison_cifar100] report the lower bounds in detail across hyperparameter configurations.

7.3.0.1 The Hessian-based method’s certification does not transfer to the nonconvex regime.

[13] prove that their Hessian-based update is \((\varepsilon,\delta)\)-certified when the training loss is convex, an assumption violated by the TinyNetCIFAR100 model used here. Empirically, the audit yields \(\varepsilon_{\mathrm{LB}} = 142.5\) on CIFAR-100 under uniform splitting—larger than any bound we observe across heuristic methods, which carry no certification claim at all. We view this as the clearest demonstration of our auditor’s diagnostic value: a method whose advertised certification rests on a precondition that silently fails at deployment is sharply flagged by the hypothesis test, while methods whose certifications hold in the actual training regime (model clipping, R2D) pass the same audit cleanly. The split-dependent gap on CIFAR-100 (\(\varepsilon_{\mathrm{LB}} = 142.5\) uniform vs. \(10\) adversarial) is consistent with the broader uniform-vs.-adversarial pattern discussed below.

7.3.0.2 Pairwise-auditor baseline.

For the pairwise auditor (5.0.0.3) with \(L=10\), even \(\mathrm{FPR}=\mathrm{FNR}=0\) yields a zero lower bound, due to the loose Clopper–Pearson confidence intervals.

7.3.0.3 IDA hyperparameters.

On CIFAR-100 under adversarial splitting, \(\varepsilon_{\mathrm{LB}}\) for IDA increases monotonically with \(q\) (\(0 \to 18 \to 66\) for \(q \in \{1, 2, 4\}\)), indicating that unlearning quality degrades as the interleaving frequency drops.⁶ On Shakespeare, the dependence on \(q\) is mild (\(13.15 \to 13.78 \to 14.42\)), but \(\varepsilon_{\mathrm{LB}}\) decreases as either \(\lambda\) or \(E_f\) increases, as one would expect: larger forget-gradient weight and a longer interleaving phase both translate to more aggressive forgetting and a looser auditor signal.

7.3.0.4 Forget ascent and retain fine-tuning.

Ascent on the forget set is essentially undetectable on Shakespeare (\(\varepsilon_{\mathrm{LB}} = 0.17\)) but readily audited on CIFAR-100 (\(\mathrm{U} = 79.5\), \(\mathrm{A} = 86\)). Pure retain fine-tuning shows similarly large CIFAR-100 bounds in both splits (\(\mathrm{U} = 81.5\), \(\mathrm{A} = 84\)).

7.3.0.5 Uniform vs.adversarial splits.

Across both certified and uncertified methods, \(\varepsilon_{\mathrm{LB}}\) under uniform splitting typically exceeds adversarial (with pure retain fine-tuning and forget ascent on CIFAR-100 as mild exceptions). Uniform splits share feature support between retain and forget, leaving residual memorisation [43] and exploitable semantic adjacency [44]; adversarial splits do not. The pairwise-auditor baseline performs well when bounds are small but saturates quickly otherwise.

8 Unlearning on convex losses↩︎

The certified algorithms audited above yield very loose bounds (\(\varepsilon_{\mathrm{LB}} \approx 0\) for model clipping even at target \(\varepsilon = 10^5\), and tighter but still weak for R2D), raising the question of how much of this gap reflects auditor slack versus genuine unlearning. To probe this, we turn to convex losses, where the mechanism is analytically tractable and a tighter correspondence between \(\varepsilon\) and \(\varepsilon_{\mathrm{LB}}\) is expected. We adopt the stronger certified-unlearning notion of [7] (4), which compares the unlearned output to the same mechanism invoked with an empty forget set; since this compares two outputs of the same procedure, no transitivity step is needed (unlike 4.1), so we audit at the same \(\delta\) as the certified guarantee.

We audit two mechanisms: the Perturbed Newton unlearning of [7] on a bounded cubic loss in dimension \(d=1\) (and a logistic loss in the appendix), and a simple output perturbation mechanism that clips the trained model and adds Gaussian noise. The auditor adapts the pairwise baseline of 5.0.0.3 to fit Gaussians directly on model weights; we also report \(\varepsilon_{\mathrm{LB}}\) from instantiating 2 with \(m=2\), \(r=2\) under \(\delta=0\). Full pipeline, losses, and hyperparameters are in [sec:appendix_convex_unlearning] [sec:appendix_output_perturbation].

¿tbl:tab:combined95unlearning95lower95bounds? reports the bounds. Both saturate near \(10.19\) at \(2L=200{,}000\) test points; the logistic loss yields a \(0\) bound, discussed in 17. As expected, the gap between \(\varepsilon_{\mathrm{LB}}\) and the certified \(\varepsilon\) is much smaller here than for the nonconvex algorithms of 7.1, confirming that the convex setting admits a tighter audit.

9 Conclusion↩︎

We propose an auditor that lower-bounds the unlearning parameter \(\varepsilon\) via membership inference, demonstrating a sharp separation between certified and uncertified unlearning algorithms: certified methods yield very small \(\varepsilon_{\mathrm{LB}}\), whereas heuristic methods regularly yield \(\varepsilon_{\mathrm{LB}}\) in the tens or higher. Our analysis is currently restricted to \(\delta = 0\); extending the audit to \(\delta > 0\), tightening the lower bounds via stronger membership-inference attacks, and designing certified unlearning algorithms whose nominal \(\varepsilon\) is provably close to \(\varepsilon_{\mathrm{LB}}\) are natural directions for future work.

10 Auditor algorithms: pseudocode↩︎

This appendix gives pseudocode for the meta-algorithm of 4 and the two auditor instantiations (batchwise inclusion/exclusion and joint sign vector prediction) of 5; see 2 3 4.

10.1 Meta-algorithm↩︎

10.2 Batchwise inclusion/exclusion prediction (Instantiation I)↩︎

10.3 Pairwise auditor (baseline)↩︎

[22] audit DP by having the adversary distinguish two models trained on neighbouring datasets. We adapt this baseline to unlearning by distinguishing the two unlearned models \(f_u^{(i)} := {\mathcal{U}}\bigl({\mathcal{A}}({\mathcal{D}}_r \cup {\mathcal{D}}_f^{(i)}),\, {\mathcal{D}}_r \cup {\mathcal{D}}_f^{(i)},\, {\mathcal{D}}_f^{(i)}\bigr)\) for \(i \in \{1, 2\}\), corresponding to two distinct forget sets \({\mathcal{D}}_f^{(1)}, {\mathcal{D}}_f^{(2)}\). Calibration and prediction are identical to Instantiation II with \(m = 2\) and \({\mathcal{D}}_{f, j} = {\mathcal{D}}_f^{(j)}\); only the conversion to an \(\varepsilon\) lower bound differs. From the true and false positive rates, the lower bound is computed directly from the confusion matrix using [24] with Clopper–Pearson confidence intervals, rather than via 2. For a given confidence level \(\zeta\) and appropriate \(\delta\), the bound is \[\label{eq:pairwise95auditor95lb} \varepsilon_{\mathrm{LB}} = \max\!\left\{\log \frac{1 - \delta - \mathrm{FP}^{\mathrm{high}}}{\mathrm{FN}^{\mathrm{high}}},\;\; \log \frac{1 - \delta - \mathrm{FN}^{\mathrm{high}}}{\mathrm{FP}^{\mathrm{high}}}\right\},\tag{3}\] where \(\mathrm{FP}^{\mathrm{high}}\) and \(\mathrm{FN}^{\mathrm{high}}\) are the upper Clopper–Pearson bounds on the false-positive and false-negative rates. ¿tbl:tab:combined95unlearning95lower95bounds? compares this baseline with the bounds from 1.

10.4 Joint sign-vector prediction (Instantiation II)↩︎

11 Proof of 2↩︎

We now restate 2 and prove it below.

We now state a corollary showing that the upper bounds for median and mean statistic proven above is monotonic in \(\varepsilon\) and thus, to reject the hypothesis \(\varepsilon \leq \varepsilon_{\text{LB}}\), it is sufficient to evaluate the bound at \(\varepsilon= \varepsilon_{\text{LB}}\) for \(\delta< \frac{M'}{K}\).

12 A discussion on setting \(\delta>0\) in the auditing lower bound↩︎

We now state a version of this auditing lemma 2 under the case of \(\delta>0\).

Additionally, for the test to be meaningful, we need to ensure that the upper bound is monotonically non-decreasing in \(\varepsilon\) (discussed in 4.1) which holds when \(\delta<M'/K\). A discussion on the same is done below.

We now state a corollary showing that the upper bounds for median and mean statistic proven above is monotonic in \(\varepsilon\) and thus, to reject the hypothesis \(\varepsilon \leq \varepsilon_{\text{LB}}\), it is sufficient to evaluate the bound at \(\varepsilon= \varepsilon_{\text{LB}}\) for \(\delta< \frac{M'}{K}\).

13 Datasets, models, and auditor batching↩︎

This appendix gives the full data-construction and model details for the two datasets described in 6.

13.1 CIFAR-100↩︎

13.1.0.1 Forget/retain construction.

For CIFAR-100 [39], we first split the original training set into a training portion (90%) and a validation portion (10%). From the training portion, we designate \(10\%\) of the points as the forget set \({\mathcal{D}}_f\) (\(4{,}500\) points), and use the remaining \(40{,}500\) points as the retain set \({\mathcal{D}}_r\). We consider two types of splits. In the uniform split, the forget and retain sets are formed by sampling points uniformly at random. In the adversarial split, the forget and retain sets are chosen from largely disjoint CIFAR-100 label classes, with overlap allowed in at most one label class. We then independently shuffle the retain and forget sets, and partition both \({\mathcal{D}}_r\) and \({\mathcal{D}}_f\) into batches of size \(B\).

13.1.0.2 Auditor batching.

For uncertified unlearning algorithms we use \(B=1\), while for certified unlearning algorithms we use \(B=750\). Accordingly, we use the batchwise inclusion/exclusion auditor (3) for uncertified methods and the joint sign-vector auditor (4) for certified methods. A discussion of why this split between auditor instantiations is appropriate is given in [sec:instantiation95discussion95certified95uncertified], with a more detailed study in 15.

13.1.0.3 Model.

We use a TinyNetCIFAR100 model, a lightweight CNN that attains around 55% accuracy on the CIFAR-100 test set after \(400\) epochs of training. The architecture consists of two convolutional blocks, each containing two \(3\times3\) convolutional layers (with 64 and 128 filters respectively) with Group Normalization (8 groups) and ReLU activations, followed by \(2\times2\) max pooling. After the two blocks, global average pooling collapses the spatial dimensions, and a single linear layer maps to the 100-class output. All weights are Kaiming-initialized. The model contains no dropout or batch normalization; Group Normalization is used throughout for training stability. We use a cosine or one-cycle learning-rate scheduler with stochastic gradient descent optimizer.

13.2 Shakespeare↩︎

13.2.0.1 Forget/retain construction.

Following [41], we treat each speaking role in each play as a separate client, parsing speaker labels from the text to extract per-role dialogue. Roles with fewer than \(2\) dialogue blocks are discarded, and for our experiments we randomly subsample \(300\) roles. Each role’s dialogue blocks are split chronologically into train (80%), validation (10%), and test (10%); validation and test sets are formed by aggregating across all \(300\) roles. The training data is then partitioned into a retain set \({\mathcal{D}}_r\) and a forget set \({\mathcal{D}}_f\) at the role level — each role is assigned entirely to one set, ensuring zero character overlap between \({\mathcal{D}}_r\) and \({\mathcal{D}}_f\). Roles are randomly shuffled and greedily assigned to \({\mathcal{D}}_f\) until approximately \(10\%\) of training characters are accumulated, yielding \(33\) forget roles (\({\mathcal{D}}_f\), \(135{,}300\) characters, \({\sim}10.0\%\) of train) and \(267\) retain roles (\({\mathcal{D}}_r\), \(1{,}221{,}363\) characters, \({\sim}90.0\%\) of train).

For unlearning experiments, the forget set \({\mathcal{D}}_f\) is further partitioned into \(B=400\) equal batches: the dialogue blocks from all forget roles are shuffled at the block level (preserving within-block coherence) and split into \(400\) contiguous chunks \({\mathcal{D}}_{f,1}, \ldots, {\mathcal{D}}_{f,400}\). For each run, \(200\) forget chunks are sampled uniformly at random from the \(400\). Each chunk and the retain set are independently converted to sliding-window samples of length \(80\) characters, where \(x\) is the input sequence and \(y\) is the target sequence shifted by one character. The retain samples and sampled forget samples are then pooled and shuffled to form the training dataset. The retain and forget datasets used during evaluation are constructed by the same sliding-window procedure applied to the retain and sampled forget text respectively.

13.2.0.2 Auditor batching.

On Shakespeare we evaluate only uncertified unlearning methods (gradient ascent, interleaved ascent–descent, fine-tuning on retain, and Hessian-based unlearning of [13]); we therefore use the batchwise inclusion/exclusion auditor (3) throughout, as on CIFAR-100.

13.2.0.3 Model.

The model is a \(2\)-layer stacked character-level LSTM following [41]. Each input character is embedded into an \(8\)-dimensional space, processed through two LSTM layers each with \(256\) hidden units, and projected to a softmax output layer over the vocabulary of \(|{\mathcal{V}}|=100\) characters. The full model has \(825{,}220\) parameters and is trained with an unroll length of \(L=80\) characters. For the Shakespeare dataset, the score \(\phi(f(x)_y)\) for a sample \((x,y)\) is the mean per-character cross-entropy loss \(-\tfrac{1}{T}\sum_{t=1}^{T}\log p_\theta(y_t \mid x_{\le t})\) assigned by the model \(f\), where \(T=80\) is the sequence length.

14 Robustness of the auditor: alternative score and aggregation↩︎

In this appendix we sanity-check two design choices of our auditor. First, we replace the logit score \(\phi(f(x)_y)\) used throughout the paper with the per-example cross-entropy loss and recompute the lower bounds (14.1). Second, we replace the mean aggregation of overlap scores with the median (14.2). In both cases the directional trends with respect to the support size \(r\) are preserved, indicating that our reported bounds are not artefacts of a particular score function or aggregation rule.

14.1 Logit score versus cross-entropy score↩︎

5pt

1 compares the lower bounds obtained when the auditor’s per-example score is the cross-entropy loss versus the logit score, for pure ascent and interleaved ascent–descent (IDA) at \(q\in\{1,2,4\}\) on both the uniform and adversarial splits. The two scores yield similar directional trends in \(r\), with the logit score giving slightly tighter bounds in most settings.

14.2 Mean versus median aggregation↩︎

5pt

2 compares the lower bounds obtained from the mean and median aggregations of the overlap scores. The two aggregations agree to within a few percent in nearly all settings, and both reproduce the inverted-U dependence on \(r\) noted in 15 — the lower bound first increases with \(r\) and then decreases.

15 Varying batch sizes \(B\) (and equivalently \(m\)) and reported support size \(r\)↩︎

This appendix gives the detailed analysis of how the lower bound \(\varepsilon_{\mathrm{LB}}\) depends on the number of forget batches \(m\) (equivalently the audit batch size \(B\), since \(m=|{\mathcal{D}}_f|/B\)) and the reported support size \(r\). The compact takeaways are summarised in 1.

15.1 Maximum attainable bound under perfect prediction (in \(m\))↩︎

The maximum lower bound on \(\varepsilon\) implied by a perfect prediction — overlap score \(m\) with support size \(r=m\) — grows with \(m\). For instance, applying 1 with \(\Gamma=10\) independent runs yields \(\varepsilon_{\mathrm{LB}} \ge 4.00\) at \(m=6\), but \(\varepsilon_{\mathrm{LB}} \ge 67.87\) at \(m=100\). Intuitively, identifying the correct sign vector is harder when \(m\) is large, since the number of candidates \(|{\mathcal{S}}_m|\) grows exponentially in \(m\). A perfect prediction at large \(m\) therefore reflects much stronger distinguishing power, and certifies a correspondingly larger lower bound on \(\varepsilon\).

15.2 Choice of audit batch size \(B\)↩︎

Since \(m=|{\mathcal{D}}_f|/B\), smaller batches enlarge the hypothesis space \({\mathcal{S}}_m\) and raise the attainable lower bound — but only if the adversary can pick the right hypothesis. Uncertified algorithms admit a strong per-batch signal, so small \(B\) (large \(m\)) is preferable. Certified algorithms have tight guarantees and weak per-batch signal; here, large \(m\) leaves the adversary unable to beat random guessing among exponentially many candidates, and one must use a larger \(B\) (smaller \(m\)) to obtain any nonzero bound. In addition, as discussed in 5, we use the joint sign vector prediction for certified unlearning algorithms, which is precisely why having a small batch size (large \(m\)) is computationally infeasible. Thus, in 7 we stick to \(B=1\) for uncertified algorithms and \(B=750\) for certified algorithms on CIFAR-100.

15.3 Dependence on the support size \(r\)↩︎

The support size \(r\) lets the auditor abstain on uncertain batches, improving the overlap on those it does report. Given \(m\), the maximum lower bound conditional on perfect overlap grows with \(r\): at \(m=100\), perfect overlap yields \(\varepsilon_{\mathrm{LB}} \ge 40.83\) at \(r=60\), rising to \(\varepsilon_{\mathrm{LB}} \ge 67.87\) at \(r=100\). In practice, the empirical lower bound traces an inverted-U in \(r\). It first increases for two compounding reasons: the maximum attainable bound at perfect overlap grows with \(r\), and the auditor’s reported predictions remain accurate while there are still confident batches to report. As \(r\) grows further, however, perfect overlap becomes harder to attain — the auditor is forced to commit to low-confidence batches, which dilute the overlap score and pull the bound back down.

In 3, we plot the lower bound against \(r \cdot B\) (equivalently, \(4500\,r/m\), since \(m = |{\mathcal{D}}_f|/B = 4500/B\)) for varying batch sizes \(B \in \{1, 10, 100, 500\}\) on the ascent-on-forget unlearning algorithm. For both \(B=1\) and \(B=10\), the lower bound first increases with \(r\) and then decreases. This inverted-U effect is more pronounced at smaller batch sizes (larger \(m\)).

7pt

15.4 Batchwise inclusion/exclusion versus joint sign-vector prediction↩︎

The choice of auditor instantiation depends on whether the unlearning algorithm is certified. For certified methods such as model clipping [15] and R2D [16], Gaussian noise injected during unlearning makes the in- and out-distributions for a single batch nearly indistinguishable, so per-batch likelihood ratios rarely yield overlap scores above the random baseline of \(r/2\). We therefore use the joint sign-vector predictor, which calibrates a separate Gaussian for every candidate \(\widetilde{S} \in {\mathcal{S}}_{m}\) and aggregates evidence across all forget points before committing to a single sign vector. Since this requires independent calibration runs for each of the \(|{\mathcal{S}}_{m}|\) candidates, we restrict to small \(m\) — concretely, batch size \(B=750\) giving \(m=6\) forget batches. For uncertified methods, the per-batch signal is strong enough that this issue does not arise; we obtain the strongest bounds at large \(m\), where \(|{\mathcal{S}}_{m}|\) is astronomically large and enumeration is infeasible, and so default to the batchwise inclusion/exclusion predictor.

15.4.0.1 Experiment with batchwise inclusion/exclusion.

We also evaluated the batchwise inclusion/exclusion auditor on the uncertified variant of model clipping, with \(C_2 = 5\) and \(\sigma = 10^{-4}\) as in 7.1. We used batch sizes \(B=750\) and \(B=100\), with \(r=6\) and \(r=40\), respectively. The resulting lower bounds were only \(0.112\) and \(0.007\) even just after the first step of unlearning. We believe this is because, after noise is added to the model at each step, the predictions of the resulting models under inclusion and exclusion of a forget batch start to overlap substantially. Once this overlap becomes large, distinguishing the two cases through batchwise membership inference becomes difficult, leading to only a negligible lower bound.

16 Unlearning algorithms: experimental details↩︎

This appendix gives the full setup for each unlearning algorithm audited in 7. [sec:appendix_model_clipping_setup] [sec:appendix_rewind_to_delete] cover the certified algorithms; [sec:appendix_uncertified_methods] [sec:appendix_hessian_unlearning] [sec:appendix_ida_retraining] [sec:appendix_ascent_on_forget] [sec:appendix_pure_finetune] cover the four heuristic algorithms together with their base-training configurations.

16.1 Model clipping↩︎

16.1.1 Algorithm↩︎

Let \(\hat{x}\) denote the trained model produced by \({\mathcal{A}}\) prior to unlearning. The unlearning procedure of [15] consists of two phases.

16.1.1.1 Phase 1: noisy projection.

For \(t = 0, 1, \dots, T_{\mathrm{noisy}} - 1\), the iterate is updated by \[\begin{align} x_0 = \hat{x} + \xi_0, \qquad x_{t+1} = \Pi_{C_2}\!\left(x_t - \gamma\big(g_t + \lambda x_t\big)\right) + \xi_{t+1}, \end{align}\] where \(\Pi_{C_2}\) is projection onto the \(\ell_2\)-ball of radius \(C_2\), \(g_t\) is the gradient of the loss on the retain set evaluated at \(x_t\), \(\gamma\) is the step size, \(\lambda\) is the \(\ell_2\) regularisation strength, and the noise satisfies \(\xi_0 \sim {\mathcal{N}}(0,\sigma_0^2 {\mathbb{I}}_d)\) and \(\xi_{t+1} \sim {\mathcal{N}}(0,\sigma^2 {\mathbb{I}}_d)\) for \(t \geq 0\). The number of noisy steps \(T_{\mathrm{noisy}}\) is set by Theorem 4.2 of [15] so that the iterate \(x_{T_{\mathrm{noisy}}}\) satisfies the target \((\varepsilon,\delta)\) guarantee.

16.1.1.2 Phase 2: fine-tuning.

Starting from \(x_{T_{\mathrm{noisy}}}\), the algorithm runs plain gradient descent on the retain-set loss — with no noise and no projection — until the total step budget is exhausted.

16.1.2 Hyperparameters↩︎

As chosen in [15], we train for a total of \(400\) epochs with a training batch size of \(128\) (\(317\) optimisation steps per epoch), and unlearning is applied for a total of \(50\) epochs. We apply a one-cycle learning schedule with maximum learning rate \(10^{-3}\) and regulariser \(5\times 10^{-4}\). For unlearning Phase 1, we use a constant learning rate of \(10^{-3}\) for the noisy steps; for Phase 2 we use a one-cycle schedule with maximum \(0.1\) and regulariser \(5\times 10^{-4}\). The initial clipping radius just before unlearning starts is \(C_0=30\). The same regulariser is applied during the retain-set fine-tuning phase. The sweep over the certified \((\varepsilon, C_2, \sigma)\) grid is reported in 4.

16.1.3 Uncertified variant of model clipping↩︎

For the uncertified experiment of 1 (a) we set \(C_2 = 5\) and \(\sigma = 10^{-4}\), terminate the clipping/noise-addition phase after \(10\) epochs (\(3{,}170\) update steps), and then fine-tune as above. The ratio \(C_2/\sigma\) is far larger than what Theorem 4.2 of [15] admits, so no certified \((\varepsilon,\delta)\) guarantee applies; we still report \(\varepsilon_{\mathrm{LB}}\) at every step \(t\) as defined above. To obtain tighter bounds in this regime we use \(L=500\) runs. For context, \(1\) epoch corresponds to \(317\) steps in this setup, so 1 (a) effectively covers up to roughly \(2\) epochs.

16.2 Rewind-to-delete↩︎

We take \(T = 40\) training epochs and \(K = 5\) rewind epochs. Following [16], the unlearned model \(\theta''_K\) is obtained by loading the checkpoint \(\theta'_{T-K}\) and then training for \(K\) epochs on the retain set; final-step Gaussian noise of scale \(\sigma\) is added to ensure \((\varepsilon, \delta)\)-indistinguishability between the trained model \(\theta'_T\) and \(\theta''_K\). Since we consider \(\varepsilon > 1\), the noise parameter \(\sigma\) ⁷ must satisfy \[\Phi\!\left(-\tfrac{\varepsilon \sigma}{\Delta} + \tfrac{\Delta}{2\sigma}\right) - e^{\varepsilon}\, \Phi\!\left(-\tfrac{\varepsilon \sigma}{\Delta} - \tfrac{\Delta}{2\sigma}\right) \le \delta,\] where \(\Phi\) is the standard Gaussian CDF and \(\Delta = \|\theta'_T - \theta''_K\|\) is the sensitivity. Both \(T\) and \(K\) are kept small because the resulting \(\sigma\) grows exponentially in \(T\) and \(K\). Theoretical guarantees for R2D hold only under full-batch gradient descent, so we use full-batch updates throughout; on CIFAR-100 this yields a base model with poor accuracy of around \(4\%\). In our auditing setup, we use a learning rate of \(0.01\). We swept over \(\{0.1, 0.01, 0.001\}\); the resulting \(\varepsilon_{\mathrm{LB}}\) values were all small and did not differ meaningfully across the sweep, so we report results for \(0.01\) throughout.

16.3 Base training configurations for uncertified methods↩︎

16.3.0.1 Shakespeare.

The base model is trained for \(15\) epochs using SGD with learning rate \(0.1\), batch size \(256\), and gradient clipping of \(1.0\), with no weight decay or learning-rate scheduling. The resulting accuracy is roughly \(0.53\), in line with [41]. Unlearning runs for a total of \(8\) epochs; the retain-set fine-tuning phase uses learning rate \(0.1\).

16.3.0.2 CIFAR-100.

For Hessian-based unlearning, we use a cosine scheduler with learning rate \(0.1\) following [13], training for a total of \(400\) epochs. For the remaining three uncertified methods (IDA, ascent on the forget set, pure fine-tuning), the training configuration matches 16.1; the retain-set fine-tuning phase reverts to a one-cycle schedule with maximum learning rate \(0.1\).

16.4 Hessian-based unlearning↩︎

16.4.0.1 Update rule.

Let \(g_f\) denote the forget-set gradient and \(H\) the (regularised) Hessian. The unlearning step is \[\label{eq:hessian95update} \theta \;\mapsto\; \theta - H^{-1} g_f + \xi, \qquad \xi \sim {\mathcal{N}}(0, \sigma^2 {\mathbb{I}}),\tag{14}\] where \(\sigma\) is the final noise scale and the Gaussian perturbation is added to every parameter.

16.4.0.2 LiSSA approximation.

As in [13], we approximate the inverse-Hessian–vector product \(H^{-1} g\) via the LiSSA algorithm of [42], avoiding explicit construction of the Hessian. The LiSSA approximation is governed by four hyperparameters — depth parameters \(s_1\) and \(s_2\), the scale, and the retain batch size — together with a weight decay applied during the Hessian computation. We describe each below before giving the per-dataset values.

16.4.0.3 Depth parameters \(s_1\) and \(s_2\).

The parameter \(s_1\) controls the number of independent LiSSA estimation runs whose results are averaged to reduce variance, while \(s_2\) controls the depth of the Neumann-series recursion within each run, governing convergence to the true Newton direction.

16.4.0.4 Scale.

The scale parameter must strictly upper-bound the largest eigenvalue of the regularised Hessian to ensure that the Neumann series converges. Too small a value causes divergence, while too large a value slows convergence and undershoots the Newton step.

16.4.0.5 Unlearning batch size.

The unlearning batch size controls the size of the random retain mini-batches sampled at each recursion step, trading off gradient noise against computational cost per LiSSA iteration.

16.4.0.6 Weight decay.

The weight decay enters as a squared \(L_2\) regularisation term added to the loss during the Hessian computation, effectively shifting the Hessian by \(\lambda {\boldsymbol{I}}\) and improving its conditioning for inversion. Crucially, it is applied only in the Hessian computation and not in the gradient \(g\), so that the Newton update approximates \(H^{-1} g\) where \(H\) is the regularised Hessian but \(g\) is the unregularised retain gradient.

16.4.0.7 Per-dataset values.

For both datasets we set the weight decay to \(5 \times 10^{-4}\). For CIFAR-100 we use \(s_1 = 10\), \(s_2 = 1000\), \(\texttt{scale} = 1000\), and an unlearning batch size of \(10\). For Shakespeare we use \(s_1 = 5\), \(s_2 = 700\), \(\texttt{scale} = 5000\), and an unlearning batch size of \(256\) (matching the training batch size); \(s_1\) and \(s_2\) are chosen slightly smaller for Shakespeare for computational efficiency.

16.4.0.8 Final noise.

After the Hessian-based step, Gaussian noise of standard deviation \(10^{-3}\) is added to every parameter, identically in both setups. We additionally perform an experiment below describing how varying the final noise changes the lower bound of unlearning parameter \(\varepsilon\).

16.4.0.9 Audit by varying the final noise step.

We perform two additional experiments on CIFAR-100 (uniform splitting) keeping all parameters unchanged but only tweaking the final noise to \(5\times 10^{-3}\) and \(10^{-2}\) respectively in 5. Trends are along expected lines. Although, we see the computed lower bound gets smaller with noise, the test accuracy also reduces.

10pt

16.5 Interleaved descent–ascent (IDA)↩︎

16.5.0.1 Update rule.

Letting \(g_t^{r}\) and \(g_t^{f}\) denote the retain- and forget-loss gradients at step \(t\), the IDA update for the first \(E_f\) epochs is \[\label{eq:ida95update} x_{t+1} = x_t - \eta_t \bigl(g_t^{r} - \lambda\, \mathbf{1}\{t \equiv 0 \!\!\pmod{q+1}\}\, g_t^{f}\bigr),\tag{15}\] so that the interleaved step (with the forget-gradient term active) fires once per \(q+1\) updates and the remaining \(q\) updates within each cycle reduce to plain retain descent \(x_{t+1} = x_t - \eta_t g_t^{r}\). After \(E_f\) epochs, only the latter (plain retain descent) is used.

16.5.0.2 CIFAR-100.

We fix \(\lambda = 0.75\), vary \(q \in \{1,2,4\}\), and set \(E_f = 10\). The learning rate is held constant at \(10^{-3}\) during the interleaved phase, and reverts to a one-cycle schedule with maximum \(0.1\) during the retain-set fine-tuning phase.

16.5.0.3 Shakespeare.

We vary \(q \in \{1,2,4\}\), \(E_f \in \{5,7\}\), and \(\lambda \in \{0.5, 1.0, 1.5\}\). The learning rate is held constant at \(0.05\) during the interleaved phase and held constant at 0.1 during the retain finetuning phase.

16.6 Ascent on the forget set↩︎

16.6.0.1 Update rule.

The unlearning phase performs gradient ascent on the forget set, \[\label{eq:ascent95update} x_{t+1} = x_t + \eta_t\, g_t^{f},\tag{16}\] where \(g_t^{f}\) is the gradient of the forget loss at step \(t\). After a fixed number of epochs (2 for both CIFAR-100 and Shakespeare), the algorithm switches to plain retain-set fine-tuning.

16.6.0.2 CIFAR-100.

The ascent learning rate is set to \(10^{-3}\) during the unlearning phase, reverting to a one-cycle schedule with maximum \(0.1\) during the retain-set fine-tuning phase.

16.6.0.3 Shakespeare.

The ascent learning rate is held constant at \(0.05\) during the unlearning phase and held at 0.1 during the retain finetuning phase identical to the rate for interleaved ascent-descent.

16.7 Pure fine-tuning on the retain set↩︎

The unlearning phase consists entirely of fine-tuning on the retain set, equivalent to a special case of model clipping with \(C=C_2=\infty\) and \(\sigma=0\). Learning-rate schedules match the corresponding retain-set fine-tuning phases described in 16.3.

17 Convex unlearning: auditor and hyper-parameter details↩︎

This appendix gives the auditor pipeline, the Perturbed Newton unlearning algorithm of [7], the cubic and logistic loss constructions, and the hyper-parameter sweep used in 7.

17.1 Auditor pipeline↩︎

We adapt the pairwise auditor of 5.0.0.3 ([22]-style) to the convex setting, with two changes. First, in line with 4, the auditor distinguishes the unlearned model produced from a non-empty forget set, \({\mathcal{U}}({\mathcal{D}}_f,{\mathcal{A}}({\mathcal{D}}),S({\mathcal{D}}))\), against the model produced from an empty forget set, \({\mathcal{U}}(\emptyset,{\mathcal{A}}({\mathcal{D}}_r),S({\mathcal{D}}_r))\), rather than two unlearned models from different non-empty forget sets. Second, since the unlearned models live in a low-dimensional Euclidean parameter space, we instantiate the pairwise auditor’s predictor directly on the model weights rather than on per-example logit scores: we train \(\Gamma=50\) independent models under each setting, fit Gaussian distributions \(\mathcal{N}(\mu_r,\Sigma_r)\) and \(\mathcal{N}(\mu_f,\Sigma_f)\) to the resulting weight vectors, and at evaluation draw \(2L\) test samples, each independently from one of the two fitted distributions. The auditor predicts the more likely generating distribution under these Gaussians, and the resulting empirical false-positive and false-negative rates are plugged into 3 to obtain \(\varepsilon_{\mathrm{LB}}\). The null hypothesis \(H_0: \varepsilon\le \varepsilon_{\mathrm{LB}}\) is then rejected with probability at most \(\zeta\).

We additionally compute a second lower bound, \(\varepsilon_{\mathrm{LB}}\), by instantiating 2 with \(m=2\) and \(r=2\), so that a per-run overlap score of \(2\) denotes a correct prediction and \(0\) an incorrect one. The induced mechanism \({\mathcal{M}}\) is \((\varepsilon,\delta)\)-DP by post-processing, and no division by \(2\) is needed since no transitivity step is used.

17.1.0.1 Why MSE is excluded.

Mean squared error is somewhat degenerate in this context because its Hessian is constant. Consequently, in Algorithm 1 of [7], the Hessian estimate is exact, and by Lemma 3 therein the Newton-corrected iterate coincides with the model obtained by retraining on the retain set; the only remaining randomness comes from the final Gaussian perturbation step.

17.2 Cubic loss in one dimension↩︎

We instantiate the cubic loss in dimension \(d=1\), so \(w,z\in\mathbb{R}\). The pointwise loss is \[\label{eq:cubic95loss} \ell(w;z) = \tfrac{\lambda_0}{2}w^2 + \tfrac{M}{6}w^3 - zw,\tag{17}\] constrained to the box \(|w|\le B\), on which the loss is \(\mu\)-strongly convex with \(\mu=\lambda_0-MB\). We place the \(n_{\mathrm{pt}}\) retain points at \(z=0\) and the \(m_{\mathrm{pt}}\) forget points at \(z=-R\), where \(R>0\) is a data-radius parameter. Under this construction, the retain-only ERM has closed-form solution \(\hat{w}_r=0\), while the forget points exert a constant gradient pull of magnitude \(R\), pushing the unlearned weight \(\hat{w}_f\) as far from \(\hat{w}_r\) as the box constraint allows. In our experiments we set \(M=0.005\), \(B=2.5\), and \(R=10.0\); the full hyper-parameter sweep over \((\lambda_0,M,B,R)\) is given below.

17.3 Hyper-parameter selection↩︎

Let \(\ell(w;z)\) denote the pointwise loss at sample \(z\), and let \({\mathcal{D}}= {\mathcal{D}}_r \cup {\mathcal{D}}_f\) be the full training set, where \({\mathcal{D}}_r\) and \({\mathcal{D}}_f\) are the retain and forget sets respectively.

Let \[\hat{w}_r \;=\; \mathop{\mathrm{arg\,min}}_w \sum_{z \in {\mathcal{D}}_r} \ell(w;z)\] denote the (noiseless) retain-only ERM, and let \(\hat{w}_f\) denote the unlearned weight, i.e.the weight obtained by first running ERM on the full dataset \({\mathcal{D}}\) to produce a trained model and then applying the Hessian-based Newton unlearning steps of [7] on the forget set \({\mathcal{D}}_f\) (with the Hessian evaluated on the retain set). In particular, \(\hat{w}_f\) is not the model produced by training alone; it is the post-unlearning weight before addition of noise. [7] bounds \[\bigl\| \hat{w}_r - \hat{w}_f \bigr\| \;\le\; \frac{2 M m^2 L^2}{\mu^3 n^2},\] when \(\ell(\cdot)\) is \(\mu\)-strongly convex, \(L\)-Lipschitz, and \(M\)-Hessian-Lipschitz in \(w\). Our objective is to choose hyper-parameters that make the empirical \(\|\hat{w}_r - \hat{w}_f\|\) as close to this theoretical bound as possible, i.e.that drive the ratio \[\rho \;:=\; \frac{\|\hat{w}_r - \hat{w}_f\|_{\text{empirical}}}{2 M m^2 L^2 / (\mu^3 n^2)}\] toward \(1\), since a value close to \(1\) indicates that Lemma 3 is empirically tight on the chosen problem instance. While the cubic loss typically yields values of \(\rho\) around \(0.2\), the logistic loss yields values of \(\rho\) around \(3\times 10^{-5}\), which possibly explains why the lower bound is so low.

17.4 Placement of retain and forget points↩︎

17.4.1 Cubic loss.↩︎

We instantiate the cubic loss in dimension \(d=1\), so \(w, z \in \mathbb{R}\) throughout this subsection. We construct \({\mathcal{D}}= {\mathcal{D}}_r \cup {\mathcal{D}}_f\) as follows. The retain set \({\mathcal{D}}_r\) consists of \(n\) points placed at the origin, \[{\mathcal{D}}_r = \bigl\{(z_i, y_i)\bigr\}_{i=1}^{n}, \qquad z_i = 0,\quad y_i = 0,\] and the forget set \({\mathcal{D}}_f\) consists of \(m\) points placed at \(-R\), \[{\mathcal{D}}_f = \bigl\{(z_i, y_i)\bigr\}_{i=1}^{m}, \qquad z_i = -R,\quad y_i = 0,\] where \(R > 0\) is the data-radius parameter. All labels are zero because the cubic loss \[f(w, z) \;=\; \tfrac{\lambda_0}{2}\, w^2 \;+\; \tfrac{M}{6}\, w^3 \;-\; z\, w\] does not depend on labels. Under this construction, the retain-only ERM admits the closed-form solution \(\hat{w}_r = 0\), since the retain gradient \(\lambda_0 w + \tfrac{M}{2} w^2\) vanishes at \(w = 0\).

The retain points are placed at the origin so that \(\hat{w}_r = 0\) provides a clean reference. The forget points are placed at \(-R\) so as to maximise their gradient contribution to the full-data ERM: from \[\frac{\partial f(w, z)}{\partial w}\bigg|_{z = -R} \;=\; \lambda_0\, w + \tfrac{M}{2}\, w^2 + R,\] the forget set exerts a constant pull of magnitude \(R\) on \(w\) toward \(+B\), pushing the unlearned weight \(\hat{w}_f\) as far from \(\hat{w}_r = 0\) as the box constraint \(|w| \le B\) allows, and producing the tightest empirical Lemma 3 ratio.

For the cubic loss, we sweep \(M \in \{0.001,\, 0.002,\, 0.005\}\), \(B \in \{2.5,\, 3.0,\, 3.5\}\), \(R \in \{4,\, 5,\, 6,\, 7,\, 8,\, 10,\, 12\}\), and \(\lambda_0 \in \{0.10,\, 0.12,\, 0.15,\, 0.18,\, 0.20\}\), and obtain the best (largest) ratio of \(\rho = 0.22\) at \(M = 0.005\), \(B = 2.5\), and \(R = 10.0\). Because for the cubic loss (instantiated below in dimension \(d=1\)) we assume \(|w|\) is bounded by \(B\), which yields the strong-convexity parameter \(\mu = \lambda_0 - M B\), we additionally require the optimum after loss minimisation to lie inside the interval \([-B, B]\); otherwise the first-order optimality condition \(\nabla \ell = 0\) may fail to hold.

17.4.2 Logistic loss (boundary construction).↩︎

The retain set consists of \(n\) points with i.i.d.Gaussian features and labels generated from a fixed direction \(\theta^*\), \[{\mathcal{D}}_r = \bigl\{(x_i, y_i)\bigr\}_{i=1}^{n}, \qquad x_i \overset{\text{i.i.d.}}{\sim} \mathcal{N}\!\left(0,\; \tfrac{1}{d} I_d\right), \quad y_i \mid x_i \;\sim\; \mathrm{Bernoulli}\bigl(f_1(x_i^\top \theta^*)\bigr),\] where \(f_1(z) = \eta \cdot \mathbf{1}[z \ge 0] + (1-\eta)\cdot \mathbf{1}[z < 0]\) is the label-flip function with flip probability \(1-\eta\). The forget set places all \(m\) points at the same fixed boundary location with a fixed label, \[{\mathcal{D}}_f = \bigl\{(x^*, y^*)\bigr\}_{i=1}^{m}, \qquad x^* = -\,\mathrm{sign}(\theta^*) \cdot \rho_f, \quad y^* = 1,\] where \(\rho_f > 0\) is the forget-point norm.

This construction is chosen for two reasons. First, concentrating all forget points at a single location \(x^*\) makes every forget sample exert an identical, unidirectional gradient contribution, maximising the aggregate influence of \({\mathcal{D}}_f\) on the full-data optimum \(\hat{w}_f\) relative to the retain-only optimum \(\hat{w}_r\). Second, placing \(x^*\) in the direction opposite to \(\theta^*\) at distance \(\rho_f\) from the origin ensures that the forget signal directly opposes the retain signal, creating the largest possible shift between \(\hat{w}_f\) and \(\hat{w}_r\), and hence the tightest empirical Lemma 3 ratio \(\rho\). However, the sweep for the logistic loss yielded a maximum ratio of only \(3\times 10^{-5}\), which explains the poor \(\varepsilon\) lower bound, at parameters \(d=2\), \(\eta=0.8\), \(\zeta = 0.7\), and \(\rho_f= 5.0\).

18 Output perturbation: mechanism and point placement↩︎

18.1 Mechanism↩︎

Given a trained model \(\hat{x}\), the output-perturbation mechanism produces the unlearned model \[x_u \;=\; \Pi_{C_0}(\hat{x}) \;+\; \xi_0, \qquad \xi_0 \sim \mathcal{N}(0,\, \sigma^2 \mathbb{I}),\] where \(\Pi_{C_0}\) denotes Euclidean projection onto an \(\ell_2\)-ball of radius \(C_0\) and \(\sigma\) is chosen according to Theorem 3.1 of [16] so as to satisfy \((\varepsilon, \delta)\)-certified unlearning. The auditing pipeline is identical to that of the cubic loss in 17.1 (Gaussian fits on model parameters, Clopper–Pearson lower bound), with an MSE loss and no regulariser.

18.2 Placement of retain and forget points↩︎

The retain set consists of \(n\) points with i.i.d.Gaussian features and continuous labels generated from a fixed direction \(\theta^*\), \[{\mathcal{D}}_r = \bigl\{(x_i, y_i)\bigr\}_{i=1}^{n}, \qquad x_i \overset{\text{i.i.d.}}{\sim} \mathcal{N}\!\left(0,\; \tfrac{1}{d} I_d\right), \quad y_i \mid x_i = f_{\mathrm{lin}}(x_i^\top \theta^*) - \tfrac{1}{2} + \varepsilon_i,\] where \[f_{\mathrm{lin}}(z) \;=\; \mathrm{clip}\!\left(\tfrac{1}{2} + \eta z,\; \tfrac{1}{2} - r,\; \tfrac{1}{2} + r\right)\] is a clipped linear link with slope \(\eta\) and half-range \(r\), and \(\varepsilon_i \sim \mathcal{N}(0, \sigma^2)\) is observation noise (clipped so that \(y_i \in [-r, r]\)) with \(\sigma = 0.05\).

The forget set consists of \(m\) i.i.d.points generated from the opposite direction \[\theta_f \;=\; -\theta^* \cdot \frac{\rho_f}{\|\theta^*\|},\] i.e. \[{\mathcal{D}}_f = \bigl\{(x_j, y_j)\bigr\}_{j=1}^{m}, \qquad x_j \overset{\text{i.i.d.}}{\sim} \mathcal{N}\!\left(0,\; \tfrac{1}{d} I_d\right), \quad y_j \mid x_j = f_{\mathrm{lin}}(x_j^\top \theta_f) - \tfrac{1}{2} + \varepsilon_j,\] with \(\|\theta_f\| = \rho_f \gg \|\theta^*\|\). Because \(\theta_f\) points in the direction opposite to \(\theta^*\), the forget labels are systematically negatively correlated with those in \({\mathcal{D}}_r\), so ERM on \({\mathcal{D}}_r \cup {\mathcal{D}}_f\) is pulled strongly away from \(\theta^*\), maximising the gap between the unlearned model trained with \({\mathcal{D}}_f\) and the one trained with the empty forget set, and therefore tightening the resulting \(\varepsilon_{\text{LB}}\).

The numbers of train samples \(n\) and forget samples \(m\) are \(600\) and \(400\) respectively, with \(r = 10\), \(\eta = 0.5\), \(\zeta = 0.9\), and \(\rho_f = 10\).

19 Computational resources↩︎

All experiments were performed on NVIDIA RTX 4000 GPUs. Each individual run (one train + unlearn cycle for a given configuration) took roughly \(45\) minutes to \(1\) hour. Since we audit several unlearning algorithms with multiple calibration and evaluation runs each, the full set of experiments reported in the paper took on the order of two weeks of wall-clock time.

References↩︎

---

1. Code available at: https://github.com/Sahasrajit123/audit-unlearning-code↩︎

2. R2D is formally analysed only in the full-batch training setting, and our threat model is consistent with that regime.↩︎

3. This reduction does not extend cleanly to \(\delta > 0\). In particular, if \(X \approx_{\varepsilon, \delta} Y\) and \(Y \approx_{\varepsilon, \delta} Z\), then \(X \approx_{2\varepsilon, (1 + e^\varepsilon)\delta} Z\); even for small \(\delta\), this additive slack can be too large for the resulting LDP reduction to be useful.↩︎

4. See 14.1 for a comparison of logit score versus cross-entropy loss; the two yield similar values on most datasets.↩︎

5. Mean and median aggregations show similar trends; a detailed comparison is given in 14.2.↩︎

6. Under uniform splitting we see a slight downward trend.↩︎

7. To compute \(\sigma\), one needs the smoothness constant \(L\) and a uniform bound on the gradient \(G\), both estimated following [16].↩︎