Auditing of Unlearning Algorithms

# Auditing of Unlearning Algorithms
Source: [https://arxiv.org/html/2607.05898](https://arxiv.org/html/2607.05898)
Sahasrajit SarmasarkarAnastasia KoloskovaStanford UniversityUniversity of Zurichsahasras@stanford\.eduanastasiia\.koloskova@uzh\.chSanmi KoyejoStanford Universitysanmi@cs\.stanford\.edu

###### Abstract

Evaluating whether unlearning algorithms truly remove training data influence remains an open challenge\. We propose a practical auditor that computes data\-dependent lower bounds on the unlearning parameterε\\varepsilonusing membership inference attacks\. Evaluating multiple unlearning algorithms, we find a sharp separation: algorithms with rigorous guarantees, such as model clipping and rewind\-to\-delete, achieve very smallε\\varepsilonbounds that do not falsify their unlearning guarantees, whereas empirical methods such as Hessian\-based unlearning, interleaved ascent–descent, ascent on the forget set, and fine\-tuning on the retain set exhibit large bounds, indicating poor unlearning\. Our auditor provides a practical tool for empirically falsifying unlearning claims through a hypothesis\-testing framework, and we validate it on CIFAR\-100 and Shakespeare text\.111Code available at:[https://github\.com/Sahasrajit123/audit\-unlearning\-code](https://github.com/Sahasrajit123/audit-unlearning-code)\.

## 1Introduction

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 trainingCao and Yang \([2015](https://arxiv.org/html/2607.05898#bib.bib19)\)\. 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 attacksShokriet al\.\([2016](https://arxiv.org/html/2607.05898#bib.bib11)\); Carliniet al\.\([2022](https://arxiv.org/html/2607.05898#bib.bib5)\)\. This motivates*exact*unlearning, which produces a model with the same distribution as one retrained from scratch on the retained dataBourtouleet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib20)\); Ginartet al\.\([2019](https://arxiv.org/html/2607.05898#bib.bib25)\), and*approximate*unlearning, which relaxes this requirement in exchange for efficiencyGuoet al\.\([2020](https://arxiv.org/html/2607.05898#bib.bib26)\); Sekhariet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib12)\); Neelet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib27)\); Golatkaret al\.\([2020](https://arxiv.org/html/2607.05898#bib.bib28)\); Kurmanjiet al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib29)\)\.

While exact unlearning offers the strongest guarantees, it is largely impractical at scale: existing schemes are either restricted to simple models such askk\-meansGinartet al\.\([2019](https://arxiv.org/html/2607.05898#bib.bib25)\)or rely on data shardingBourtouleet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib20)\), 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 scrubbingGolatkaret al\.\([2020](https://arxiv.org/html/2607.05898#bib.bib28)\), gradient ascent on the forget set, fine\-tuning on the retain set, and interleaved ascent–descent schemes such asSCRUBKurmanjiet al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib29)\)\. The second family adopts the*certified*\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishability notion ofGuoet al\.\([2020](https://arxiv.org/html/2607.05898#bib.bib26)\), borrowed from differential privacy, which requires the unlearned model to be\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishableDwork and Roth \([2014](https://arxiv.org/html/2607.05898#bib.bib9)\)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 lossGuoet al\.\([2020](https://arxiv.org/html/2607.05898#bib.bib26)\); Sekhariet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib12)\); Neelet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib27)\); Qiaoet al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib30)\); Zhanget al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib6)\)or a unique minimiserAllouahet al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib45)\); only a handful of recent methods provide certified guarantees for genuinely nonconvex lossesKoloskovaet al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib4)\); Mu and Klabjan \([2025](https://arxiv.org/html/2607.05898#bib.bib7)\); Chienet al\.\([2024](https://arxiv.org/html/2607.05898#bib.bib33)\); Chourasia and Shah \([2023](https://arxiv.org/html/2607.05898#bib.bib34)\)\.

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ε<εLB\\varepsilon<\\varepsilon\_\{\\text\{LB\}\}for any certified\(ε,δ\)\(\\varepsilon,\\delta\)unlearning algorithm in the spirit of recent work on differential\-privacy auditingJagielskiet al\.\([2020](https://arxiv.org/html/2607.05898#bib.bib31)\); Nasret al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib32)\); Steinkeet al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib1)\)\.

While our audit draws on differential\-privacy auditing, the unlearning setting is closer in spirit to*group privacy*Dwork and Roth \([2014](https://arxiv.org/html/2607.05898#bib.bib9)\): 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ε\\varepsilonbounds in the unlearning setting; our meta\-algorithm \([Algorithm1](https://arxiv.org/html/2607.05898#alg1)\) extends the one\-run auditor ofSteinkeet al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib1)\)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ε<εLB\\varepsilon<\\varepsilon\_\{\\mathrm\{LB\}\}with controlled Type I error for the case ofδ=0\\delta=0\(see[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)\)\.
- •Empirical evaluation\.We develop two instantiations of this auditor in[Section5](https://arxiv.org/html/2607.05898#S5)and evaluate them across a range of unlearning algorithms, revealing a sharp separation between certified and uncertified methods: certified unlearning algorithms yield very smallε\\varepsilonlower bounds, whereas uncertified algorithms produce lower bounds that frequently exceed5050–6060\.

## 2Related work

Empirically lower\-bounding the privacy parameterε\\varepsilonof an\(ε,δ\)\(\\varepsilon,\\delta\)\-DP mechanism has been studied inJagielskiet al\.\([2020](https://arxiv.org/html/2607.05898#bib.bib31)\); Nasret al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib8),[2023](https://arxiv.org/html/2607.05898#bib.bib32)\); Annamalai and De Cristofaro \([2024](https://arxiv.org/html/2607.05898#bib.bib35)\), typically by planting canaries in a pair of neighbouring datasets and converting distinguishing accuracy into anε\\varepsilonlower bound via the hypothesis\-testing interpretation of DPKairouzet al\.\([2015](https://arxiv.org/html/2607.05898#bib.bib15)\); Wasserman and Zhou \([2010](https://arxiv.org/html/2607.05898#bib.bib37)\)\. These approaches require many independent training runs to drive the audit’s Type I/II error down\. More recent workSteinkeet al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib1)\); Mahloujifaret al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib36)\)reduces the run cost to a*single*training run for\(ε,δ\)\(\\varepsilon,\\delta\)\-DP andff\-DP respectively, by planting many independent canaries and auditing them jointly within one run\.

Our auditor borrows the joint\-canary idea fromSteinkeet al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib1)\), 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ε\\varepsilonlower 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 ofSteinkeet al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib1)\); Mahloujifaret al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib36)\)with a LiRA\-styleCarliniet al\.\([2022](https://arxiv.org/html/2607.05898#bib.bib5)\)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\. AthenaSommeret al\.\([2022](https://arxiv.org/html/2607.05898#bib.bib39)\), thoughZhanget al\.\([2024](https://arxiv.org/html/2607.05898#bib.bib40)\)show such schemes can be gamed by a dishonest provider\),*output\-difference*audits such as TAPEWanget al\.\([2025b](https://arxiv.org/html/2607.05898#bib.bib41)\)that train a reconstructor on the gap between pre\- and post\-unlearning models, and*sample\-level*audits returning per\-example unlearning\-completeness scoresWanget al\.\([2025a](https://arxiv.org/html/2607.05898#bib.bib42)\); Triantafillouet al\.\([2024](https://arxiv.org/html/2607.05898#bib.bib43)\); Guet al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib44)\)\. Our auditor instead returns a quantity calibrated to the certified\-unlearning parameterε\\varepsilonitself, rather than a per\-example completeness score: an empirical lower bound on the algorithm’sε\\varepsilonthat is directly comparable to its claimed\(ε,δ\)\(\\varepsilon,\\delta\)guarantee\.

Early MIA formulationsShokriet al\.\([2016](https://arxiv.org/html/2607.05898#bib.bib11)\); Yeomet al\.\([2018](https://arxiv.org/html/2607.05898#bib.bib46)\)were sharpened by likelihood\-ratio attacks \(LiRACarliniet al\.\([2022](https://arxiv.org/html/2607.05898#bib.bib5)\), RMIAZarifzadehet al\.\([2024](https://arxiv.org/html/2607.05898#bib.bib49)\)\)\. In the unlearning setting,Chenet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib10)\); Bertranet al\.\([2024](https://arxiv.org/html/2607.05898#bib.bib50)\)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\.

## 3Problem setup

### 3\.1Unlearning 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𝒟f⊆𝒟\{\\mathcal\{D\}\}\_\{f\}\\subseteq\{\\mathcal\{D\}\}, called the*forget set*, is requested to be removed\. We write𝒟r:=𝒟∖𝒟f\{\\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𝒟r\{\\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*modelfu=𝒰​\(𝒜​\(𝒟\),𝒟,𝒟f\)f\_\{u\}=\{\\mathcal\{U\}\}\\big\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\),\{\\mathcal\{D\}\},\{\\mathcal\{D\}\}\_\{f\}\\big\)\.

### 3\.2\(ε,δ\)\(\\varepsilon,\\delta\)indistinguishabilityDwork and Roth \([2014](https://arxiv.org/html/2607.05898#bib.bib9)\)

###### Definition 3\.1\(\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishability\)\.

LetXXandYYbe random variables over a common domainΩ\\Omega\. We say thatXXandYYare\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishable, and writeX≈ε,δYX\\approx\_\{\\varepsilon,\\delta\}Y, if for every measurable setS⊆ΩS\\subseteq\\Omega,Pr⁡\[X∈S\]≤eε​Pr⁡\[Y∈S\]\+δ\\Pr\[X\\in S\]\\leq e^\{\\varepsilon\}\\Pr\[Y\\in S\]\+\\deltaandPr⁡\[Y∈S\]≤eε​Pr⁡\[X∈S\]\+δ\\Pr\[Y\\in S\]\\leq e^\{\\varepsilon\}\\Pr\[X\\in S\]\+\\delta\.

### 3\.3Certified unlearning

###### Definition 3\.2\(\(ε,δ\)\(\\varepsilon,\\delta\)\-certified unlearning,Guoet al\.,[2020](https://arxiv.org/html/2607.05898#bib.bib26); Koloskovaet al\.,[2025](https://arxiv.org/html/2607.05898#bib.bib4)\)\.

We say that𝒰\{\\mathcal\{U\}\}is an\(ε,δ\)\(\\varepsilon,\\delta\)\-certified unlearning algorithm for𝒜\{\\mathcal\{A\}\}if there exists a reference algorithm𝒜¯\\overline\{\{\\mathcal\{A\}\}\}such that for every forget set𝒟f⊆𝒟\{\\mathcal\{D\}\}\_\{f\}\\subseteq\{\\mathcal\{D\}\}with retain set𝒟r:=𝒟∖𝒟f\{\\mathcal\{D\}\}\_\{r\}:=\{\\mathcal\{D\}\}\\setminus\{\\mathcal\{D\}\}\_\{f\}, the random variables𝒰​\(𝒜​\(𝒟\),𝒟,𝒟f\)\{\\mathcal\{U\}\}\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\),\{\\mathcal\{D\}\},\{\\mathcal\{D\}\}\_\{f\}\)and𝒜¯​\(𝒟r\)\\overline\{\{\\mathcal\{A\}\}\}\(\{\\mathcal\{D\}\}\_\{r\}\)are\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishable\.

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

### 3\.4Threat 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 modelxox\_\{o\}at the start of training, and \(ii\) the shuffling orderπ\\piof 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\) ofKoloskovaet al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib4)\)and rewind\-to\-delete \(R2D\)Mu and Klabjan \([2025](https://arxiv.org/html/2607.05898#bib.bib7)\)remain\(ε,δ\)\(\\varepsilon,\\delta\)\-certified under this stronger adversary\.222R2D is formally analysed only in the full\-batch training setting, and our threat model is consistent with that regime\.

Because the adversary observesxox\_\{o\}andπ\\pi, the indistinguishability requirement must hold conditional on them; the reference algorithm is allowed to depend on\(xo,π\)\(x\_\{o\},\\pi\)as well\. Let𝒜xo,π​\(𝒟\)\{\\mathcal\{A\}\}\_\{x\_\{o\},\\pi\}\(\{\\mathcal\{D\}\}\)denote the learning algorithm started atxox\_\{o\}with shuffling orderπ\\pi\.

###### Definition 3\.3\(\(ε,δ\)\(\\varepsilon,\\delta\)\-certified unlearning under our threat model\)\.

We say that𝒰\{\\mathcal\{U\}\}is an\(ε,δ\)\(\\varepsilon,\\delta\)\-certified unlearning algorithm for𝒜\{\\mathcal\{A\}\}if for every initial modelxox\_\{o\}and shuffling orderπ\\pi, there exists a reference algorithm𝒜¯xo,π\\overline\{\{\\mathcal\{A\}\}\}\_\{x\_\{o\},\\pi\}such that for every forget set𝒟f⊆𝒟\{\\mathcal\{D\}\}\_\{f\}\\subseteq\{\\mathcal\{D\}\}, the random variables𝒰​\(𝒜xo,π​\(𝒟\),𝒟,𝒟f\)\{\\mathcal\{U\}\}\(\{\\mathcal\{A\}\}\_\{x\_\{o\},\\pi\}\(\{\\mathcal\{D\}\}\),\{\\mathcal\{D\}\},\{\\mathcal\{D\}\}\_\{f\}\)and𝒜¯xo,π​\(𝒟r\)\\overline\{\{\\mathcal\{A\}\}\}\_\{x\_\{o\},\\pi\}\(\{\\mathcal\{D\}\}\_\{r\}\)are\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishable\.

Our goal is to design an*auditor*\(or adversary\) that, given black\-box access to𝒜\{\\mathcal\{A\}\}and𝒰\{\\mathcal\{U\}\}together with the initial modelxox\_\{o\}and shuffling orderπ\\pifrom our threat model, produces a data\-dependent lower boundεLB\\varepsilon\_\{\\mathrm\{LB\}\}on the true unlearning parameterε\\varepsilon\. We formalise the audit as a one\-sided hypothesis test: for a confidence levelζ∈\(0,1\)\\zeta\\in\(0,1\), the auditor outputsεLB\\varepsilon\_\{\\mathrm\{LB\}\}such that, underH0:ε≤εLBH\_\{0\}:\\varepsilon\\leq\\varepsilon\_\{\\mathrm\{LB\}\}, the test rejects with probability at mostζ\\zeta\. Whenever the test rejects, the true parameter exceedsεLB\\varepsilon\_\{\\mathrm\{LB\}\}with confidence1−ζ1\-\\zeta, so a highεLB\\varepsilon\_\{\\mathrm\{LB\}\}is direct evidence that the unlearning guarantee, if any, is weak\. The main paper focuses onδ=0\\delta=0; see[Section4\.1](https://arxiv.org/html/2607.05898#S4.SS1)\. A discussion on extension of the test beyondδ=0\\delta=0is given in[AppendixC](https://arxiv.org/html/2607.05898#A3)\.

## 4The algorithm

We now describe the meta\-algorithm underlying our audit; pseudocode is given in[Algorithm1](https://arxiv.org/html/2607.05898#alg1)\. 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 vectorS\(ℓ\)S^\{\(\\ell\)\}, usesS\(ℓ\)S^\{\(\\ell\)\}to decide which candidate batches are placed in the forget set, runs training followed by unlearning, and asks the auditor to predictS\(ℓ\)S^\{\(\\ell\)\}from the resulting unlearned model\. The construction extends the many\-canary auditing paradigm used for differential privacySteinkeet al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib1)\); Nasret al\.\([2023](https://arxiv.org/html/2607.05898#bib.bib32)\); Pillutlaet al\.\([2024](https://arxiv.org/html/2607.05898#bib.bib23)\)to the unlearning setting\.

##### Setup\.

The training dataset is partitioned intonnbatches of sizeBB\. Letℬ\{\\mathcal\{B\}\}denote the universe of batches; the*candidate forget pool*𝒟f⊆ℬ\{\\mathcal\{D\}\}\_\{f\}\\subseteq\{\\mathcal\{B\}\}containsmmbatches and the*retain set*𝒟r\{\\mathcal\{D\}\}\_\{r\}contains the remainingn−mn\-m\. We further partition𝒟f\{\\mathcal\{D\}\}\_\{f\}intommcandidate forget batches𝒟f=⋃j=1m𝒟f,j\{\\mathcal\{D\}\}\_\{f\}=\\bigcup\_\{j=1\}^\{m\}\{\\mathcal\{D\}\}\_\{f,j\}\. Throughout, we fix the initial modelxox\_\{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

𝒮m:=\{s∈\{±1\}m:0≤\#​\{j:sj=−1\}−\#​\{j:sj=\+1\}≤1\},\{\\mathcal\{S\}\}\_\{m\}:=\\\{\\,s\\in\\\{\\pm 1\\\}^\{m\}:0\\leq\\\#\\\{j:s\_\{j\}=\-1\\\}\-\\\#\\\{j:s\_\{j\}=\+1\\\}\\leq 1\\,\\\},i\.e\., vectors with as many\+1\+1s and−1\-1s as possible \(one extra−1\-1whenmmis odd, by convention\)\. ForS∈𝒮mS\\in\{\\mathcal\{S\}\}\_\{m\}, let𝒟f​\(S\):=⋃j:Sj=\+1𝒟f,j\{\\mathcal\{D\}\}\_\{f\}\(S\):=\\bigcup\_\{j:S\_\{j\}=\+1\}\{\\mathcal\{D\}\}\_\{f,j\}be the sampled forget set underSSand𝒟​\(S\):=𝒟r∪𝒟f​\(S\)\{\\mathcal\{D\}\}\(S\):=\{\\mathcal\{D\}\}\_\{r\}\\cup\{\\mathcal\{D\}\}\_\{f\}\(S\)the corresponding training set\.

##### Audit procedure\.

Fix an even*guess budget*rr\. In each ofLLindependent runs, the auditor:

1. 1\.samplesS\(ℓ\)∼Unif​\(𝒮m\)S^\{\(\\ell\)\}\\sim\\mathrm\{Unif\}\(\{\\mathcal\{S\}\}\_\{m\}\)and computes the unlearned modelfu\(ℓ\)←𝒰​\(𝒜​\(𝒟​\(S\(ℓ\)\)\),𝒟​\(S\(ℓ\)\),𝒟f​\(S\(ℓ\)\)\)f\_\{u\}^\{\(\\ell\)\}\\leftarrow\{\\mathcal\{U\}\}\\bigl\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\(S^\{\(\\ell\)\}\)\),\\;\{\\mathcal\{D\}\}\(S^\{\(\\ell\)\}\),\\;\{\\mathcal\{D\}\}\_\{f\}\(S^\{\(\\ell\)\}\)\\bigr\)
2. 2\.produces a guessS^\(ℓ\)∈\{−1,0,\+1\}m\\widehat\{S\}^\{\(\\ell\)\}\\in\\\{\-1,0,\+1\\\}^\{m\}with exactlyr/2r/2entries equal to\+1\+1andr/2r/2equal to−1\-1\(the remainingm−rm\-rentries are0, indicating abstentions\);
3. 3\.records the overlap scoreV\(ℓ\):=∑j=1mmax⁡\{0,S^j\(ℓ\)​Sj\(ℓ\)\}V^\{\(\\ell\)\}:=\\sum\_\{j=1\}^\{m\}\\max\\\{0,\\;\\widehat\{S\}\_\{j\}^\{\(\\ell\)\}S\_\{j\}^\{\(\\ell\)\}\\\}, which counts the number of correct nonzero guesses \(out ofrr\)\.

The audit reports a summary statistic \(mean or median\) of\{V\(ℓ\)\}ℓ=1L\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}, which[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)converts into the lower boundεLB\\varepsilon\_\{\\mathrm\{LB\}\}\.

For analysis,[Algorithm1](https://arxiv.org/html/2607.05898#alg1)induces a randomized mechanismℳ:𝒮m→\{−1,0,\+1\}m\{\\mathcal\{M\}\}:\{\\mathcal\{S\}\}\_\{m\}\\to\\\{\-1,0,\+1\\\}^\{m\}withℳ​\(S\(ℓ\)\):=S^\(ℓ\)\{\\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 vectorS\(ℓ\)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 modelfu\(ℓ\)f\_\{u\}^\{\(\\ell\)\}, soℳ\{\\mathcal\{M\}\}’s output is post\-processing offu\(ℓ\)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 baseliner/2r/2is evidence of weak unlearning;[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)converts the mean \(or median\) of\{V\(ℓ\)\}ℓ=1L\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}across independent runs into a precise lower bound onε\\varepsilon, with two instantiations ofℳ\{\\mathcal\{M\}\}given in[Section5](https://arxiv.org/html/2607.05898#S5)\.

### 4\.1Reduction 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 modelxox\_\{o\}, and shuffling orderπ\\pi, the auditor induces a randomized mechanismℳ:𝒮m→\{−1,0,\+1\}m\{\\mathcal\{M\}\}:\{\\mathcal\{S\}\}\_\{m\}\\to\\\{\-1,0,\+1\\\}^\{m\}that maps the sampled sign vectorSSto a predictionℳ​\(S\):=S^\{\\mathcal\{M\}\}\(S\):=\\widehat\{S\}\. Concretely, forS∈𝒮mS\\in\{\\mathcal\{S\}\}\_\{m\}, let𝒟f​\(S\)⊆𝒟f\{\\mathcal\{D\}\}\_\{f\}\(S\)\\subseteq\{\\mathcal\{D\}\}\_\{f\}denote the forget subset encoded bySS, let

fu​\(S\):=𝒰​\(𝒜​\(𝒟r∪𝒟f​\(S\)\),𝒟r∪𝒟f​\(S\),𝒟f​\(S\)\),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 letfr:=𝒜​\(𝒟r\)f\_\{r\}:=\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\_\{r\}\)denote the retrained reference\. The auditor’s predictionℳ​\(S\)\{\\mathcal\{M\}\}\(S\)is computed fromfu​\(S\)f\_\{u\}\(S\)alone \(with possibly many queries to𝒜\{\\mathcal\{A\}\}and𝒰\{\\mathcal\{U\}\}, but no direct access toSSor to the internal randomness of𝒜,𝒰\{\\mathcal\{A\}\},\{\\mathcal\{U\}\}\)\.

###### Lemma 4\.1\.

If\(𝒜,𝒰\)\(\{\\mathcal\{A\}\},\{\\mathcal\{U\}\}\)is\(ε,0\)\(\\varepsilon,0\)\-certified unlearning under our threat model \([Definition3\.3](https://arxiv.org/html/2607.05898#S3.Thmtheorem3)\), thenℳ\{\\mathcal\{M\}\}is\(2​ε,0\)\(2\\varepsilon,0\)\-locally differentially privateBebensee \([2019](https://arxiv.org/html/2607.05898#bib.bib24)\); that is, for allS,S′∈𝒮mS,S^\{\\prime\}\\in\{\\mathcal\{S\}\}\_\{m\}and everyT⊆\{−1,0,\+1\}mT\\subseteq\\\{\-1,0,\+1\\\}^\{m\},Pr⁡\[ℳ​\(S\)∈T\]≤e2​ε​Pr⁡\[ℳ​\(S′\)∈T\]\\Pr\[\{\\mathcal\{M\}\}\(S\)\\in T\]\\leq e^\{2\\varepsilon\}\\,\\Pr\[\{\\mathcal\{M\}\}\(S^\{\\prime\}\)\\in T\]\.

###### Proof\.

Fix anyS1,S2∈𝒮mS\_\{1\},S\_\{2\}\\in\{\\mathcal\{S\}\}\_\{m\}\. Certified unlearning of\(𝒜,𝒰\)\(\{\\mathcal\{A\}\},\{\\mathcal\{U\}\}\)impliesfu​\(S1\)≈ε,0frf\_\{u\}\(S\_\{1\}\)\\approx\_\{\\varepsilon,0\}f\_\{r\}andfu​\(S2\)≈ε,0frf\_\{u\}\(S\_\{2\}\)\\approx\_\{\\varepsilon,0\}f\_\{r\}\. Using the triangle inequality,fu​\(S1\)≈2​ε,0fu​\(S2\)f\_\{u\}\(S\_\{1\}\)\\approx\_\{2\\varepsilon,0\}f\_\{u\}\(S\_\{2\}\)\.333This reduction does not extend cleanly toδ\>0\\delta\>0\. In particular, ifX≈ε,δYX\\approx\_\{\\varepsilon,\\delta\}YandY≈ε,δZY\\approx\_\{\\varepsilon,\\delta\}Z, thenX≈2​ε,\(1\+eε\)​δZX\\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\.Sinceℳ​\(S\)\{\\mathcal\{M\}\}\(S\)depends onSSonly throughfu​\(S\)f\_\{u\}\(S\), it is a post\-processing offu​\(S\)f\_\{u\}\(S\), and post\-processing preserves privacy\. ∎

### 4\.2Lower bound onε\\varepsilonfrom overlap score

###### Lemma 4\.2\.

Letℳ:𝒮m→\{−1,0,\+1\}m\{\\mathcal\{M\}\}:\{\\mathcal\{S\}\}\_\{m\}\\to\\\{\-1,0,\+1\\\}^\{m\}be an\(ε,0\)\(\\varepsilon,0\)\-locally differentially private mechanism\. Let𝒯⊆\{−1,0,\+1\}m\\mathcal\{T\}\\subseteq\\\{\-1,0,\+1\\\}^\{m\}denote the subset of vectors with exactlyr/2r/2entries equal to\+1\+1andr/2r/2entries equal to−1\-1\. SetM′=\(m⌊m/2⌋\)M^\{\\prime\}=\\binom\{m\}\{\\lfloor m/2\\rfloor\}andK:=\|𝒯\|=\(mr/2,r/2,m−r\)K\\;:=\\;\|\\mathcal\{T\}\|\\;=\\;\\binom\{m\}\{r/2,\\,r/2,\\,m\-r\}\. Let\{S\(ℓ\)\}ℓ=1L\\\{S^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}be independent random vectors drawn uniformly from𝒮m\{\\mathcal\{S\}\}\_\{m\}\. For eachℓ∈\[L\]\\ell\\in\[L\], letS^\(ℓ\)=ℳ​\(S\(ℓ\)\)\\widehat\{S\}^\{\(\\ell\)\}=\{\\mathcal\{M\}\}\(S^\{\(\\ell\)\}\), assumeS^\(ℓ\)∈𝒯\\widehat\{S\}^\{\(\\ell\)\}\\in\\mathcal\{T\}almost surely, and defineV\(ℓ\):=∑j=1mmax⁡\{0,S^j\(ℓ\)​Sj\(ℓ\)\}∈\{0,1,…,r\}V^\{\(\\ell\)\}\\;:=\\;\\sum\_\{j=1\}^\{m\}\\max\\\!\\bigl\\\{0,\\,\\widehat\{S\}^\{\(\\ell\)\}\_\{j\}S^\{\(\\ell\)\}\_\{j\}\\bigr\\\}\\;\\in\\;\\\{0,1,\\dots,r\\\}\. For eachu∈\{0,1,…,r\}u\\in\\\{0,1,\\dots,r\\\}, define the pointwise bound

πε​\(u\):=∑α1,α2∈\{0,…,r/2\}α1\+α2=u\(m−r⌈\(m−r\)/2⌉−\(α1−α2\)\)​\(r/2α1\)​\(r/2α2\)⋅eεeε\+M′−1\.\\pi\_\{\\varepsilon\}\(u\)\\;:=\\,\\;\\sum\_\{\\begin\{subarray\}\{c\}\\alpha\_\{1\},\\alpha\_\{2\}\\in\\\{0,\\dots,r/2\\\}\\\\ \\alpha\_\{1\}\+\\alpha\_\{2\}=u\\end\{subarray\}\}\\binom\{m\-r\}\{\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\}\\binom\{r/2\}\{\\alpha\_\{1\}\}\\binom\{r/2\}\{\\alpha\_\{2\}\}\\cdot\\,\\frac\{e^\{\\varepsilon\}\\;\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\.Define the upper tailPε​\(v\):=∑u=vrπε​\(u\)P\_\{\\varepsilon\}\(v\):=\\sum\_\{u=v\}^\{r\}\\pi\_\{\\varepsilon\}\(u\)\. Then for everyv∈ℝv\\in\\mathbb\{R\},

Pr⁡\[1L​∑ℓ=1LV\(ℓ\)≥v\]≤infλ≥0exp⁡\(L​log⁡\(∑u=0reλ​u​πε​\(u\)\)−λ​L​v\)\\Pr\\\!\\left\[\\frac\{1\}\{L\}\\sum\_\{\\ell=1\}^\{L\}V^\{\(\\ell\)\}\\geq v\\right\]\\;\\leq\\;\\inf\_\{\\lambda\\geq 0\}\\exp\\\!\\left\(L\\log\\\!\\Big\(\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\\Big\)\-\\lambda Lv\\right\)\(1\)Pr⁡\(Median​\(\{V\(ℓ\)\}ℓ=1L\)≥v\)≤\(L⌈L/2⌉\)​Pε​\(v\)⌈L/2⌉\.\\Pr\\\!\\left\(\\mathrm\{Median\}\\\!\\left\(\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\\right\)\\geq v\\right\)\\;\\leq\\;\\binom\{L\}\{\\lceil L/2\\rceil\}\\,P\_\{\\varepsilon\}\(v\)^\{\\lceil L/2\\rceil\}\.\(2\)

Given an observed statisticvv\(the empirical mean or median of\{V\(ℓ\)\}ℓ=1L\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\), we set the right\-hand side of the relevant bound from[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)to a target levelζ\\zeta, fixδ=0\\delta=0, and solve forε\\varepsilonto obtain an LDP lower bound; dividing by22to undo the reduction of[Lemma4\.1](https://arxiv.org/html/2607.05898#S4.Thmtheorem1)yields the reportedεLB\\varepsilon\_\{\\mathrm\{LB\}\}\. To rejectH0:ε≤εLBH\_\{0\}:\\varepsilon\\leq\\varepsilon\_\{\\mathrm\{LB\}\}at levelζ\\zeta, it suffices to evaluate the bound atε=εLB\\varepsilon=\\varepsilon\_\{\\mathrm\{LB\}\}, since both bounds are monotone non\-decreasing inε\\varepsilon\([CorollaryB\.2](https://arxiv.org/html/2607.05898#A2.Thmtheorem2)\)\.

##### Choice ofmm\(orBB\)\.

Largermmraises the maximum attainable bound, since identifying the correct sign vector among\|𝒮m\|\|\{\\mathcal\{S\}\}\_\{m\}\|exponentially many candidates is information\-theoretically harder\. But largermmalso means smaller batches and weaker per\-batch leakage, so the right operating point depends on the algorithm: heuristic methods \(e\.g\. gradient ascent on forget, fine\-tuning on retain\) leak strongly per batch and prefer smallBB\(largemm\), while certified methods cap per\-batch influence through their\(ε,δ\)\(\\varepsilon,\\delta\)budget and require largerBB\(smallermm\) for the auditor to beat random guessing\.

##### Choice ofrr\.

The support sizerrlets the auditor abstain on uncertain batches\. The empirical lower bound traces an inverted\-U inrr: it rises withrras the maximum attainable bound grows and confident predictions are still available, then falls once the auditor is forced to commit to low\-confidence batches whose errors dilute the overlap score\. We study these trade\-offs empirically in[AppendixF](https://arxiv.org/html/2607.05898#A6)\.

## 5Two instantiations of the auditor meta\-algorithm

We now instantiate the abstract mechanismℳ\{\\mathcal\{M\}\}from[Algorithm1](https://arxiv.org/html/2607.05898#alg1)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 whenmmis too large to enumerate𝒮m\{\\mathcal\{S\}\}\_\{m\}; Instantiation II treats each balanced sign vector as a hypothesis and exploits cross\-batch correlations, but is practical only when\|𝒮m\|\|\{\\mathcal\{S\}\}\_\{m\}\|is enumerable\.

For a modelff, writef​\(x\)yf\(x\)\_\{y\}for the probability assigned to labelyyon inputxxandϕ​\(p\):=log⁡\(p1−p\)\\phi\(p\):=\\log\\\!\\left\(\\tfrac\{p\}\{1\-p\}\\right\)for the logit transform\. We write𝒩​\(s;μ,σ2\):=12​π​σ2​exp⁡\(−\(s−μ\)22​σ2\)\\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;[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)requires no such assumption\.

##### Instantiation I: Batchwise inclusion/exclusion prediction\.

Whenmmis large, enumerating𝒮m\{\\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Γ\\Gammaindependent calibration runs𝒰​\(𝒜​\(𝒟​\(S\)\),𝒟,𝒟f​\(S\)\)\{\\mathcal\{U\}\}\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\(S\)\),\{\\mathcal\{D\}\},\{\\mathcal\{D\}\}\_\{f\}\(S\)\)withS∼Unif​\(𝒮m\)S\\sim\{\\mathrm\{Unif\}\}\(\{\\mathcal\{S\}\}\_\{m\}\): an*in*\-distribution conditioned onSj=\+1S\_\{j\}=\+1and an*out*\-distribution conditioned onSj=−1S\_\{j\}=\-1, in the spirit of LiRACarliniet al\.\([2022](https://arxiv.org/html/2607.05898#bib.bib5)\)\.444See[SectionE\.1](https://arxiv.org/html/2607.05898#A5.SS1)for a comparison of logit score versus cross\-entropy loss; the two yield similar values on most datasets\.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Λj\\Lambda\_\{j\}\. We then predict\+1\+1for the topr/2r/2batches byΛj\\Lambda\_\{j\},−1\-1for the bottomr/2r/2, and0for the rest\. Calibration runs and evaluation runs are drawn independently, which is required for the audit’s lower bound to be valid\. See[Algorithm2](https://arxiv.org/html/2607.05898#alg2)for pseudocode\.

##### Instantiation II: Joint sign\-vector prediction\.

When\|𝒮m\|\|\{\\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 candidateS~∈𝒮m\\widetilde\{S\}\\in\{\\mathcal\{S\}\}\_\{m\}and every forget example\(x,y\)\(x,y\), we fit a Gaussian to the logit scores collected fromΓ\\Gammaindependent runs of𝒰​\(𝒜​\(𝒟​\(S~\)\),𝒟,𝒟f​\(S~\)\)\{\\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=mr=mhere\. See[Algorithm3](https://arxiv.org/html/2607.05898#alg3)for pseudocode\.

##### Pairwise auditor \(baseline\)\.

As a baseline we adapt the pairwise distinguishability auditor ofNasret al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib8)\), which distinguishes two unlearned models trained on different forget sets and converts true/false positive rates into anε\\varepsilonlower bound via\(Kairouzet al\.,[2015](https://arxiv.org/html/2607.05898#bib.bib15), Thm\. 2\.1\)with Clopper–Pearson confidence intervals; the full description and exact formula are deferred to[SectionA\.3](https://arxiv.org/html/2607.05898#A1.SS3)\.

## 6Datasets and auditor setup

##### CIFAR\-100\(Krizhevsky,[2009](https://arxiv.org/html/2607.05898#bib.bib16)\)\.

We train aTinyNetCIFAR100model to∼55%\{\\sim\}55\\%validation accuracy\. The forget set𝒟f\{\\mathcal\{D\}\}\_\{f\}contains10%10\\%of training points \(4,5004\{,\}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 isB=1B=1for uncertified andB=750B=750for certified algorithms; the rationale and full construction are in[SectionsD\.1](https://arxiv.org/html/2607.05898#A4.SS1)and[F\.4](https://arxiv.org/html/2607.05898#A6.SS4)\.

##### Shakespeare\(Shakespeare,[1997](https://arxiv.org/html/2607.05898#bib.bib17)\)\.

FollowingMcMahanet al\.\([2017](https://arxiv.org/html/2607.05898#bib.bib18)\)we treat each role as a client, subsample300300roles, and partition at the role level into3333forget roles \(∼10%\{\\sim\}10\\%of training characters\) and267267retain roles\. The model is a22\-layer character\-level LSTM reaching∼0\.53\{\\sim\}0\.53accuracy; we evaluate only uncertified methods, using the batchwise inclusion/exclusion auditor withB=400B=400\. Full construction, score definition, and model details are in[SectionD\.2](https://arxiv.org/html/2607.05898#A4.SS2)\.

## 7Unlearning Algorithms Audited

For all runs below,εLB\\varepsilon\_\{\\mathrm\{LB\}\}denotes the lower bound obtained from the mean aggregation of overlap scores in[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)\.555Mean and median aggregations show similar trends; a detailed comparison is given in[SectionE\.2](https://arxiv.org/html/2607.05898#A5.SS2)\.For all experiments, the confidence parameterζ\\zetais set to0\.050\.05\.

We organise the audited algorithms into two groups: certified algorithms with formal\(ε,δ\)\(\\varepsilon,\\delta\)guarantees \([Section7\.1](https://arxiv.org/html/2607.05898#S7.SS1)\), and heuristic algorithms without such guarantees \([Section7\.2](https://arxiv.org/html/2607.05898#S7.SS2)\)\.[Section7\.3](https://arxiv.org/html/2607.05898#S7.SS3)discusses them in detail, and full hyperparameters and per\-method experimental details are deferred to[AppendixG](https://arxiv.org/html/2607.05898#A7)\.

### 7\.1Certified unlearning algorithms

##### Model clipping\.

We audit the certified unlearning algorithm ofKoloskovaet al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib4)\), which interleaves projected noisy gradient steps on anℓ2\\ell\_\{2\}\-ball of radiusC2C\_\{2\}with a noiseless retain\-set fine\-tuning phase\. The number of noisy steps is set by Theorem 4\.2 ofKoloskovaet al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib4)\)to achieve the target\(ε,δ\)\(\\varepsilon,\\delta\)guarantee\. Recalling the certified\-method auditor configuration of[Section6](https://arxiv.org/html/2607.05898#S6.SS0.SSS0.Px1)—batch sizeB=750B=750\(m=6m=6forget batches\), joint sign\-vector predictor \([Algorithm3](https://arxiv.org/html/2607.05898#alg3)\) withΓ=50\\Gamma=50calibration rounds andL=100L=100runs—we sweepε\\varepsilon,C2C\_\{2\}, andσ\\sigmaacross target privacy levels spanning five orders of magnitude \(up toε=105\\varepsilon=10^\{5\}\)\. At the prescribed stopping time of Theorem 4\.2, the audit yieldsεLB≈0\\varepsilon\_\{\\mathrm\{LB\}\}\\approx 0across the entire grid, consistent with the certification holding\. As a diagnostic, we additionally computeεLB​\(t\)\\varepsilon\_\{\\mathrm\{LB\}\}\(t\)at intermediate iterates—treating the algorithm as if it had terminated at steptt—which remains near zero throughout the noisy phase, indicating that the audit gains no traction even between certification checkpoints\. Full details are reported in[SectionG\.1](https://arxiv.org/html/2607.05898#A7.SS1)\.

##### Uncertified variant of model clipping\.

For this uncertified variant, we setC2=5C\_\{2\}=5andσ=10−4\\sigma=10^\{\-4\}and truncate the noisy phase to1010epochs, after which the algorithm proceeds to its retain\-set fine\-tuning phase as in the certified setting\. The ratioC2/σC\_\{2\}/\\sigmais far larger than what Theorem 4\.2 admits, so the algorithm is no longer certified; we reportεLB\\varepsilon\_\{\\mathrm\{LB\}\}as a function of step indexttwithL=500L=500runs to obtain tighter bounds \([Figure1\(a\)](https://arxiv.org/html/2607.05898#S7.F1.sf1)\)\. Further details are given in[SectionG\.1\.3](https://arxiv.org/html/2607.05898#A7.SS1.SSS3)\. We compare both uniform and adversarial splits\.

##### 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 ofMu and Klabjan \([2025](https://arxiv.org/html/2607.05898#bib.bib7)\), to make the trained and unlearned models\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishable\. The noise scale, sensitivity, and other choices are detailed in[SectionG\.2](https://arxiv.org/html/2607.05898#A7.SS2)\. We consider both uniform and adversarial splits, with plots in[Figure1\(c\)](https://arxiv.org/html/2607.05898#S7.F1.sf3)\.

##### 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[Section7\.3](https://arxiv.org/html/2607.05898#S7.SS3)\.

![Refer to caption](https://arxiv.org/html/2607.05898v1/cc_plot_cifar100_chg7.png)\(a\)Uncertified variant of model clipping
![Refer to caption](https://arxiv.org/html/2607.05898v1/plot_uniform_bs750_vs_bs2250.png)\(b\)Comparison with pairwise auditor for uniform splitting
![Refer to caption](https://arxiv.org/html/2607.05898v1/r2d_plot.png)\(c\)Rewind to delete for varyingε\\varepsilon

Figure 1:Rewind to delete and model clipping audits for CIFAR100

### 7\.2Uncertified 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[SectionsG\.3](https://arxiv.org/html/2607.05898#A7.SS3),[G\.5](https://arxiv.org/html/2607.05898#A7.SS5)and[G\.6](https://arxiv.org/html/2607.05898#A7.SS6)\. We choose support sizer=100r=100for the Shakespeare dataset \(withm=400m=400forget batches\) and support sizer=3000r=3000for CIFAR\-100 \(withm=4500m=4500batches\)\. The number of calibration roundsΓ\\Gammais set to5050andL=10L=10evaluation runs\.

##### Hessian\-based unlearning\.

We audit the Hessian\-based unlearning algorithm ofZhanget al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib6)\), which performs a Newton\-style update on the forget\-set gradient followed by addition of Gaussian noise to every parameter\.Zhanget al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib6)\)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 productAgarwalet al\.\([2017](https://arxiv.org/html/2607.05898#bib.bib51)\), hyperparameter settings, and an ablation varying the final noise scale are deferred to[SectionG\.4](https://arxiv.org/html/2607.05898#A7.SS4)\.

##### Interleaved descent–ascent \(IDA\) retraining\.

IDA alternates retain\-set gradient descent withλ\\lambda\-weighted forget\-gradient steps inserted after everyqqretain steps, for the firstEfE\_\{f\}epochs only; thereafter it reverts to plain retain descent\. Update rule and per\-dataset\(λ,q,Ef\)\(\\lambda,q,E\_\{f\}\)are in[SectionG\.5](https://arxiv.org/html/2607.05898#A7.SS5)\.

##### 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[Model clipping\.](https://arxiv.org/html/2607.05898#S7.SS1.SSS0.Px1)\)\. Per\-dataset learning rates, schedules, and the explicit update rule are given in[SectionG\.6](https://arxiv.org/html/2607.05898#A7.SS6)\.

##### 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 radiusC2=∞C\_\{2\}=\\inftyand noise scaleσ=0\\sigma=0\. Learning\-rate schedules match the retain\-set fine\-tuning phase of the corresponding base\-training configuration \([SectionG\.3](https://arxiv.org/html/2607.05898#A7.SS3)\)\.

### 7\.3Comparison of lower bounds across methods

[Tables1\(a\)](https://arxiv.org/html/2607.05898#S7.T1.st1)and[1\(b\)](https://arxiv.org/html/2607.05898#S7.T1.st2)report the lower bounds in detail across hyperparameter configurations\.

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

Zhanget al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib6)\)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εLB=142\.5\\varepsilon\_\{\\mathrm\{LB\}\}=142\.5on 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 \(εLB=142\.5\\varepsilon\_\{\\mathrm\{LB\}\}=142\.5uniform vs\.1010adversarial\) is consistent with the broader uniform\-vs\.\-adversarial pattern discussed below\.

##### Pairwise\-auditor baseline\.

For the pairwise auditor \([Section5](https://arxiv.org/html/2607.05898#S5.SS0.SSS0.Px3)\) withL=10L=10, evenFPR=FNR=0\\mathrm\{FPR\}=\\mathrm\{FNR\}=0yields a zero lower bound, due to the loose Clopper–Pearson confidence intervals\.

##### IDA hyperparameters\.

On CIFAR\-100 under adversarial splitting,εLB\\varepsilon\_\{\\mathrm\{LB\}\}for IDA increases monotonically withqq\(0→18→660\\to 18\\to 66forq∈\{1,2,4\}q\\in\\\{1,2,4\\\}\), indicating that unlearning quality degrades as the interleaving frequency drops\.666Under uniform splitting we see a slight downward trend\.On Shakespeare, the dependence onqqis mild \(13\.15→13\.78→14\.4213\.15\\to 13\.78\\to 14\.42\), butεLB\\varepsilon\_\{\\mathrm\{LB\}\}decreases as eitherλ\\lambdaorEfE\_\{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\.

##### Forget ascent and retain fine\-tuning\.

Ascent on the forget set is essentially undetectable on Shakespeare \(εLB=0\.17\\varepsilon\_\{\\mathrm\{LB\}\}=0\.17\) but readily audited on CIFAR\-100 \(U=79\.5\\mathrm\{U\}=79\.5,A=86\\mathrm\{A\}=86\)\. Pure retain fine\-tuning shows similarly large CIFAR\-100 bounds in both splits \(U=81\.5\\mathrm\{U\}=81\.5,A=84\\mathrm\{A\}=84\)\.

##### Uniform vs\. adversarial splits\.

Across both certified and uncertified methods,εLB\\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 memorisationChenget al\.\([2026](https://arxiv.org/html/2607.05898#bib.bib52)\)and exploitable semantic adjacencyEbrahimpour\-Boroojenyet al\.\([2025](https://arxiv.org/html/2607.05898#bib.bib53)\); adversarial splits do not\. The pairwise\-auditor baseline performs well when bounds are small but saturates quickly otherwise\.

SettingParametersεLB\\varepsilon\_\{\\mathrm\{LB\}\}Varyingqq\(IDA\)q=1q=1,λ=0\.5\\lambda=0\.5,Ef=4E\_\{f\}=413\.15q=4q=4,λ=0\.5\\lambda=0\.5,Ef=4E\_\{f\}=413\.78q=9q=9,λ=0\.5\\lambda=0\.5,Ef=4E\_\{f\}=414\.42Varying\(λ,Ef\)\(\\lambda,E\_\{f\}\),q=1q=1λ=0\.5\\lambda=0\.5,Ef=4E\_\{f\}=413\.15λ=0\.5\\lambda=0\.5,Ef=7E\_\{f\}=710\.38λ=1\.5\\lambda=1\.5,Ef=4E\_\{f\}=49\.97λ=1\.5\\lambda=1\.5,Ef=7E\_\{f\}=70\.17Methodcomp\.Retain fine\-tune16\.06Forget ascent0\.17Hessian\-based4\.18\(a\)Shakespeare\. Nearly every setting has retain/forget accuracy averaged around 0\.56 and test accuracy averaged around 0\.53\. Ascent, Finetune, and IDA all use total 8 unlearning epochs\.
εLB\\varepsilon\_\{\\mathrm\{LB\}\}R/F/T accuracySettingParamsUAUAIDAq=1,Ef=10q=1,E\_\{f\}=10100\.50\.00\.91/0\.59/0\.540\.92/0\.02/0\.51q=2,Ef=10q=2,E\_\{f\}=10100180\.92/0\.59/0\.540\.92/0\.027/0\.51q=4,Ef=10q=4,E\_\{f\}=1095\.5660\.92/0\.59/0\.540\.92/0\.02/0\.51Methodcomp\.Pure Retain FT81\.5840\.93/0\.59/0\.530\.94/0\.03/0\.51Forget ascent79\.5860\.92/0\.59/0\.540\.94/0\.025/0\.51Hessian142\.5100\.69/0\.67/0\.510\.55/0\.09/0\.37\(b\)CIFAR\-100\. Ascent, Finetune, and IDA all use total of 50 unlearning epochs U = uniform split, A = adversarial split; R/F/T = retain/forget/test; FT = Finetuning

Table 1:ε\\varepsilonlower bounds across Shakespeare and CIFAR\-100\.

## 8Unlearning on convex losses

The certified algorithms audited above yield very loose bounds \(εLB≈0\\varepsilon\_\{\\mathrm\{LB\}\}\\approx 0for model clipping even at targetε=105\\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ε\\varepsilonandεLB\\varepsilon\_\{\\mathrm\{LB\}\}is expected\. We adopt the stronger certified\-unlearning notion ofSekhariet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib12)\)\([DefinitionH\.1](https://arxiv.org/html/2607.05898#A8.Thmtheorem1)\), 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[Section4\.1](https://arxiv.org/html/2607.05898#S4.SS1)\), so we audit at the sameδ\\deltaas the certified guarantee\.

We audit two mechanisms: the*Perturbed Newton*unlearning ofSekhariet al\.\([2021](https://arxiv.org/html/2607.05898#bib.bib12), Algorithm 1\)on a bounded cubic loss in dimensiond=1d=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[Section5](https://arxiv.org/html/2607.05898#S5.SS0.SSS0.Px3)to fit Gaussians directly on model weights; we also reportεLB\\varepsilon\_\{\\mathrm\{LB\}\}from instantiating[Algorithm1](https://arxiv.org/html/2607.05898#alg1)withm=2m=2,r=2r=2underδ=0\\delta=0\. Full pipeline, losses, and hyperparameters are in[AppendicesH](https://arxiv.org/html/2607.05898#A8)and[I](https://arxiv.org/html/2607.05898#A9)\.

[Table2](https://arxiv.org/html/2607.05898#S8.T2)reports the bounds\. Both saturate near10\.1910\.19at2​L=200,0002L=200\{,\}000test points; the logistic loss yields a0bound, discussed in[AppendixH](https://arxiv.org/html/2607.05898#A8)\. As expected, the gap betweenεLB\\varepsilon\_\{\\mathrm\{LB\}\}and the certifiedε\\varepsilonis much smaller here than for the nonconvex algorithms of[Section7\.1](https://arxiv.org/html/2607.05898#S7.SS1), confirming that the convex setting admits a tighter audit\.

\(a\)Convex cubic loss \(Perturbed Newton\)\.
\(b\)Output perturbation\.

Table 2:Lower bounds for Perturbed Newton unlearning on the cubic loss \(left\) and for output perturbation on a linear\-regression task \(right\)\.εLB\(p\)\\varepsilon^\{\(p\)\}\_\{\\text\{LB\}\}andεLB\\varepsilon\_\{\\text\{LB\}\}denote the bounds from the*pairwise auditor*\([Section5](https://arxiv.org/html/2607.05898#S5.SS0.SSS0.Px3)\) and the*joint sign\-vector*predictor \(withm=2m=2,r=2r=2\), respectively\.
## 9Conclusion

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

## References

- Second\-order stochastic optimization for machine learning in linear time\.J\. Mach\. Learn\. Res\.18\(1\),pp\. 4148–4187\.External Links:ISSN 1532\-4435Cited by:[§G\.4](https://arxiv.org/html/2607.05898#A7.SS4.SSS0.Px2.p1.3),[§7\.2](https://arxiv.org/html/2607.05898#S7.SS2.SSS0.Px1.p1.1)\.
- Y\. Allouah, J\. Kazdan, R\. Guerraoui, and S\. Koyejo \(2025\)The utility and complexity of in\- and out\-of\-distribution machine unlearning\.InProceedings of the International Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- M\. S\. M\. S\. Annamalai and E\. De Cristofaro \(2024\)Nearly tight black\-box auditing of differentially private machine learning\.InProceedings of the 38th International Conference on Neural Information Processing Systems,NIPS ’24,Red Hook, NY, USA\.External Links:ISBN 9798331314385Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p1.5)\.
- B\. Bebensee \(2019\)Local differential privacy: a tutorial\.arXiv preprint arXiv:1907\.11908\.External Links:[Link](https://arxiv.org/abs/1907.11908)Cited by:[Lemma 4\.1](https://arxiv.org/html/2607.05898#S4.Thmtheorem1.p1.7.7)\.
- M\. Bertran, S\. Tang, M\. Kearns, J\. Morgenstern, A\. Roth, and Z\. S\. Wu \(2024\)Reconstruction attacks on machine unlearning: simple models are vulnerable\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p4.1)\.
- L\. Bourtoule, V\. Chandrasekaran, C\. A\. Choquette\-Choo, H\. Jia, A\. Travers, B\. Zhang, D\. Lie, and N\. Papernot \(2021\)Machine unlearning\.InIEEE Symposium on Security and Privacy \(S&P\),Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- Y\. Cao and J\. Yang \(2015\)Towards making systems forget with machine unlearning\.InIEEE Symposium on Security and Privacy \(S&P\),pp\. 463–480\.Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1)\.
- N\. Carlini, S\. Chien, M\. Nasr, S\. Song, A\. Terzis, and F\. Tramer \(2022\)Membership inference attacks from first principles\.External Links:2112\.03570,[Link](https://arxiv.org/abs/2112.03570)Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§2](https://arxiv.org/html/2607.05898#S2.p2.1),[§2](https://arxiv.org/html/2607.05898#S2.p4.1),[§5](https://arxiv.org/html/2607.05898#S5.SS0.SSS0.Px1.p1.14)\.
- M\. Chen, Z\. Zhang, T\. Wang, M\. Backes, M\. Humbert, and Y\. Zhang \(2021\)When machine unlearning jeopardizes privacy\.InProceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security,CCS ’21,New York, NY, USA,pp\. 896–911\.External Links:ISBN 9781450384544,[Link](https://doi.org/10.1145/3460120.3484756),[Document](https://dx.doi.org/10.1145/3460120.3484756)Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p4.1)\.
- J\. Cheng, P\. Liu, Q\. Li, and C\. Zhang \(2026\)Machine unlearning under retain\-forget entanglement\.External Links:2603\.26569,[Link](https://arxiv.org/abs/2603.26569)Cited by:[§7\.3](https://arxiv.org/html/2607.05898#S7.SS3.SSS0.Px5.p1.1)\.
- E\. Chien, H\. Wang, Z\. Chen, and P\. Li \(2024\)Langevin unlearning: a new perspective of noisy gradient descent for machine unlearning\.InProceedings of the 38th International Conference on Neural Information Processing Systems,NIPS ’24,Red Hook, NY, USA\.External Links:ISBN 9798331314385Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- R\. Chourasia and N\. Shah \(2023\)Forget unlearning: towards true data\-deletion in machine learning\.InProceedings of the 40th International Conference on Machine Learning,ICML’23\.Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- C\. Dwork and A\. Roth \(2014\)The algorithmic foundations of differential privacy\.Found\. Trends Theor\. Comput\. Sci\.9\(3–4\),pp\. 211–407\.External Links:ISSN 1551\-305X,[Link](https://doi.org/10.1561/0400000042),[Document](https://dx.doi.org/10.1561/0400000042)Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p2.3),[§1](https://arxiv.org/html/2607.05898#S1.p4.3),[§3\.2](https://arxiv.org/html/2607.05898#S3.SS2)\.
- A\. Ebrahimpour\-Boroojeny, Y\. Wang, and H\. Sundaram \(2025\)On the necessity of output distribution reweighting for effective class unlearning\.External Links:2506\.20893,[Link](https://arxiv.org/abs/2506.20893)Cited by:[§7\.3](https://arxiv.org/html/2607.05898#S7.SS3.SSS0.Px5.p1.1)\.
- A\. A\. Ginart, M\. Y\. Guan, G\. Valiant, and J\. Zou \(2019\)Making ai forget you: data deletion in machine learning\.InProceedings of the 33rd International Conference on Neural Information Processing Systems,Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- A\. Golatkar, A\. Achille, and S\. Soatto \(2020\)Eternal sunshine of the spotless net: selective forgetting in deep networks\.InIEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\),Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- Y\. Gu, J\. He, and K\. Chen \(2025\)Auditing approximate machine unlearning for differentially private models\.InIEEE International Conference on Data Mining \(ICDM\),Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p3.3)\.
- C\. Guo, T\. Goldstein, A\. Hannun, and L\. Van Der Maaten \(2020\)Certified data removal from machine learning models\.InProceedings of the 37th International Conference on Machine Learning,ICML’20\.Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§1](https://arxiv.org/html/2607.05898#S1.p2.3),[Definition 3\.2](https://arxiv.org/html/2607.05898#S3.Thmtheorem2)\.
- M\. Jagielski, J\. Ullman, and A\. Oprea \(2020\)Auditing differentially private machine learning: how private is private sgd?\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p3.2),[§2](https://arxiv.org/html/2607.05898#S2.p1.5)\.
- P\. Kairouz, S\. Oh, and P\. Viswanath \(2015\)The composition theorem for differential privacy\.InProceedings of the 32nd International Conference on Machine Learning,pp\. 1376–1385\.Cited by:[§A\.3](https://arxiv.org/html/2607.05898#A1.SS3.p1.8),[§2](https://arxiv.org/html/2607.05898#S2.p1.5),[§5](https://arxiv.org/html/2607.05898#S5.SS0.SSS0.Px3.p1.1)\.
- A\. Koloskova, Y\. Allouah, A\. Jha, R\. Guerraoui, and S\. Koyejo \(2025\)Certified unlearning for neural networks\.External Links:2506\.06985,[Link](https://arxiv.org/abs/2506.06985)Cited by:[§F\.4](https://arxiv.org/html/2607.05898#A6.SS4.p1.8),[§G\.1\.1](https://arxiv.org/html/2607.05898#A7.SS1.SSS1.Px1.p1.15),[§G\.1\.1](https://arxiv.org/html/2607.05898#A7.SS1.SSS1.p1.2),[§G\.1\.2](https://arxiv.org/html/2607.05898#A7.SS1.SSS2.p1.11),[§G\.1\.3](https://arxiv.org/html/2607.05898#A7.SS1.SSS3.p1.12),[§1](https://arxiv.org/html/2607.05898#S1.p2.3),[§3\.4](https://arxiv.org/html/2607.05898#S3.SS4.p1.3),[Definition 3\.2](https://arxiv.org/html/2607.05898#S3.Thmtheorem2),[§7\.1](https://arxiv.org/html/2607.05898#S7.SS1.SSS0.Px1.p1.14)\.
- A\. Krizhevsky \(2009\)Learning multiple layers of features from tiny images\.Technical reportUniversity of Toronto\.Cited by:[§D\.1](https://arxiv.org/html/2607.05898#A4.SS1.SSS0.Px1.p1.8),[§6](https://arxiv.org/html/2607.05898#S6.SS0.SSS0.Px1)\.
- M\. Kurmanji, P\. Triantafillou, J\. Hayes, and E\. Triantafillou \(2023\)Towards unbounded machine unlearning\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- S\. Mahloujifar, L\. Melis, and K\. Chaudhuri \(2025\)Auditing f\-differential privacy in one run\.InProceedings of the 42nd International Conference on Machine Learning,ICML’25\.Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p1.5),[§2](https://arxiv.org/html/2607.05898#S2.p2.1)\.
- H\. B\. McMahan, E\. Moore, D\. Ramage, S\. Hampson, and B\. Agüera y Arcas \(2017\)Communication\-efficient learning of deep networks from decentralized data\.InProceedings of the 20th International Conference on Artificial Intelligence and Statistics,pp\. 1273–1282\.Cited by:[§D\.2](https://arxiv.org/html/2607.05898#A4.SS2.SSS0.Px1.p1.17),[§D\.2](https://arxiv.org/html/2607.05898#A4.SS2.SSS0.Px3.p1.11),[§G\.3](https://arxiv.org/html/2607.05898#A7.SS3.SSS0.Px1.p1.7),[§6](https://arxiv.org/html/2607.05898#S6.SS0.SSS0.Px2.p1.7)\.
- S\. Mu and D\. Klabjan \(2025\)Rewind\-to\-delete: certified machine unlearning for nonconvex functions\.External Links:2409\.09778,[Link](https://arxiv.org/abs/2409.09778)Cited by:[§F\.4](https://arxiv.org/html/2607.05898#A6.SS4.p1.8),[§G\.2](https://arxiv.org/html/2607.05898#A7.SS2.p1.11),[§I\.1](https://arxiv.org/html/2607.05898#A9.SS1.p1.6),[§1](https://arxiv.org/html/2607.05898#S1.p2.3),[§3\.4](https://arxiv.org/html/2607.05898#S3.SS4.p1.3),[§7\.1](https://arxiv.org/html/2607.05898#S7.SS1.SSS0.Px3.p1.1),[footnote 7](https://arxiv.org/html/2607.05898#footnote7)\.
- M\. Nasr, J\. Hayes, T\. Steinke, B\. Balle, F\. Tramèr, M\. Jagielski, N\. Carlini, and A\. Terzis \(2023\)Tight auditing of differentially private machine learning\.InUSENIX Security Symposium,pp\. 1631–1648\.Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p3.2),[§2](https://arxiv.org/html/2607.05898#S2.p1.5),[§4](https://arxiv.org/html/2607.05898#S4.p1.5)\.
- M\. Nasr, S\. Song, A\. Thakurta, N\. Papernot, and N\. Carlini \(2021\)Adversary instantiation: lower bounds for differentially private machine learning\.External Links:2101\.04535,[Link](https://arxiv.org/abs/2101.04535)Cited by:[§A\.3](https://arxiv.org/html/2607.05898#A1.SS3.p1.8),[§H\.1](https://arxiv.org/html/2607.05898#A8.SS1.p1.9),[§2](https://arxiv.org/html/2607.05898#S2.p1.5),[§5](https://arxiv.org/html/2607.05898#S5.SS0.SSS0.Px3.p1.1)\.
- S\. Neel, A\. Roth, and S\. Sharifi\-Malvajerdi \(2021\)Descent\-to\-delete: gradient\-based methods for machine unlearning\.InAlgorithmic Learning Theory \(ALT\),pp\. 931–962\.Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- K\. Pillutla, G\. Andrew, P\. Kairouz, H\. B\. McMahan, A\. Oprea, and S\. Oh \(2024\)Unleashing the power of randomization in auditing differentially private ML\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§4](https://arxiv.org/html/2607.05898#S4.p1.5)\.
- X\. Qiao, M\. Zhang, M\. Tang, and E\. Wei \(2025\)Hessian\-free online certified unlearning\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p2.3)\.
- A\. Sekhari, J\. Acharya, G\. Kamath, and A\. T\. Suresh \(2021\)Remember what you want to forget: algorithms for machine unlearning\.InProceedings of the 35th International Conference on Neural Information Processing Systems,NIPS ’21,Red Hook, NY, USA\.External Links:ISBN 9781713845393Cited by:[§H\.1](https://arxiv.org/html/2607.05898#A8.SS1.SSS0.Px1.p1.1),[§H\.3](https://arxiv.org/html/2607.05898#A8.SS3.p2.4),[Appendix H](https://arxiv.org/html/2607.05898#A8.p1.1),[Remark I\.1](https://arxiv.org/html/2607.05898#A9.Thmtheorem1.p1.1),[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§1](https://arxiv.org/html/2607.05898#S1.p2.3),[§8](https://arxiv.org/html/2607.05898#S8.p1.5),[§8](https://arxiv.org/html/2607.05898#S8.p2.5)\.
- W\. Shakespeare \(1997\)The complete works of william shakespeare\.Project Gutenberg\.Note:Project Gutenberg editionExternal Links:[Link](https://www.gutenberg.org/ebooks/100)Cited by:[§6](https://arxiv.org/html/2607.05898#S6.SS0.SSS0.Px2)\.
- R\. Shokri, M\. Stronati, and V\. Shmatikov \(2016\)Membership inference attacks against machine learning models\.CoRRabs/1610\.05820\.External Links:[Link](http://arxiv.org/abs/1610.05820),1610\.05820Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p1.1),[§2](https://arxiv.org/html/2607.05898#S2.p4.1)\.
- D\. M\. Sommer, L\. Song, S\. Wagh, and P\. Mittal \(2022\)Athena: probabilistic verification of machine unlearning\.Proceedings on Privacy Enhancing Technologies \(PoPETs\)2022\(3\),pp\. 268–290\.Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p3.3)\.
- T\. Steinke, M\. Nasr, and M\. Jagielski \(2023\)Privacy auditing with one \(1\) training run\.External Links:2305\.08846,[Link](https://arxiv.org/abs/2305.08846)Cited by:[§1](https://arxiv.org/html/2607.05898#S1.p3.2),[§1](https://arxiv.org/html/2607.05898#S1.p4.3),[§2](https://arxiv.org/html/2607.05898#S2.p1.5),[§2](https://arxiv.org/html/2607.05898#S2.p2.1),[§4](https://arxiv.org/html/2607.05898#S4.p1.5)\.
- E\. Triantafillou, P\. Kairouz, F\. Pedregosa, J\. Hayes, M\. Kurmanji, K\. Zhao, V\. Dumoulin, J\. Jacques Junior, I\. Mitliagkas, J\. Wan, L\. Sun Hosoya, S\. Escalera, G\. K\. Dziugaite, P\. Triantafillou, and I\. Guyon \(2024\)Are we making progress in unlearning? findings from the first NeurIPS unlearning competition\.arXiv preprint arXiv:2406\.09073\.Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p3.3)\.
- C\. Wang, Q\. Li, Z\. Xiang, Y\. Cao, and D\. Wang \(2025a\)Towards lifecycle unlearning commitment management: measuring sample\-level unlearning completeness\.InUSENIX Security Symposium,Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p3.3)\.
- W\. Wang, Z\. Tian, C\. Zhang, and S\. Yu \(2025b\)TAPE: tailored posterior difference for auditing of machine unlearning\.InProceedings of the ACM on Web Conference \(WWW\),Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p3.3)\.
- L\. Wasserman and S\. Zhou \(2010\)A statistical framework for differential privacy\.Journal of the American Statistical Association105\(489\),pp\. 375–389\.External Links:[Document](https://dx.doi.org/10.1198/jasa.2009.tm08651),[Link](https://doi.org/10.1198/jasa.2009.tm08651),https://doi\.org/10\.1198/jasa\.2009\.tm08651Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p1.5)\.
- S\. Yeom, I\. Giacomelli, M\. Fredrikson, and S\. Jha \(2018\)Privacy risk in machine learning: analyzing the connection to overfitting\.InIEEE Computer Security Foundations Symposium \(CSF\),pp\. 268–282\.Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p4.1)\.
- S\. Zarifzadeh, P\. Liu, and R\. Shokri \(2024\)Low\-cost high\-power membership inference attacks\.InInternational Conference on Machine Learning \(ICML\),pp\. 58244–58282\.Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p4.1)\.
- B\. Zhang, Z\. Chen, C\. Shen, and J\. Li \(2024\)Verification of machine unlearning is fragile\.InInternational Conference on Machine Learning \(ICML\),Cited by:[§2](https://arxiv.org/html/2607.05898#S2.p3.3)\.
- B\. Zhang, Y\. Dong, T\. Wang, and J\. Li \(2025\)Towards certified unlearning for deep neural networks\.External Links:2408\.00920,[Link](https://arxiv.org/abs/2408.00920)Cited by:[§D\.2](https://arxiv.org/html/2607.05898#A4.SS2.SSS0.Px2.p1.1),[§G\.3](https://arxiv.org/html/2607.05898#A7.SS3.SSS0.Px2.p1.3),[§G\.4](https://arxiv.org/html/2607.05898#A7.SS4.SSS0.Px2.p1.3),[§1](https://arxiv.org/html/2607.05898#S1.p2.3),[§7\.2](https://arxiv.org/html/2607.05898#S7.SS2.SSS0.Px1.p1.1),[§7\.3](https://arxiv.org/html/2607.05898#S7.SS3.SSS0.Px1.p1.4)\.

## Appendix AAuditor algorithms: pseudocode

This appendix gives pseudocode for the meta\-algorithm of[Section4](https://arxiv.org/html/2607.05898#S4)and the two auditor instantiations \(*batchwise inclusion/exclusion*and*joint sign vector prediction*\) of[Section5](https://arxiv.org/html/2607.05898#S5); see[Algorithms1](https://arxiv.org/html/2607.05898#alg1),[2](https://arxiv.org/html/2607.05898#alg2)and[3](https://arxiv.org/html/2607.05898#alg3)\.

### A\.1Meta\-algorithm

Algorithm 1Meta\-algorithm for auditor0:Batched dataset

𝒟∈ℬn\{\\mathcal\{D\}\}\\in\{\\mathcal\{B\}\}^\{n\}partitioned as

𝒟=𝒟r∪𝒟f\{\\mathcal\{D\}\}=\{\\mathcal\{D\}\}\_\{r\}\\cup\{\\mathcal\{D\}\}\_\{f\}with

\|𝒟f\|=m\|\{\\mathcal\{D\}\}\_\{f\}\|=m
0:Algorithms

\(𝒜,𝒰\)\(\{\\mathcal\{A\}\},\{\\mathcal\{U\}\}\), reported support size

rr, and number of runs

LL
1:for

ℓ=1,2,…,L\\ell=1,2,\\ldots,Ldo

2:Sample

S\(ℓ\)∼Unif​\(𝒮m\)S^\{\(\\ell\)\}\\sim\{\\mathrm\{Unif\}\}\(\{\\mathcal\{S\}\}\_\{m\}\)and unlearnt model

fu\(ℓ\)←𝒰​\(𝒜​\(𝒟​\(S\(ℓ\)\)\),𝒟​\(S\(ℓ\)\),𝒟f​\(S\(ℓ\)\)\)f\_\{u\}^\{\(\\ell\)\}\\leftarrow\{\\mathcal\{U\}\}\\big\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\(S^\{\(\\ell\)\}\)\),\\,\{\\mathcal\{D\}\}\(S^\{\(\\ell\)\}\),\\,\{\\mathcal\{D\}\}\_\{f\}\(S^\{\(\\ell\)\}\)\\big\)\.

3:*Induced mechanismℳ​\(S\(ℓ\)\)\{\\mathcal\{M\}\}\(S^\{\(\\ell\)\}\)*: From

fu\(ℓ\)f\_\{u\}^\{\(\\ell\)\}, output

S^\(ℓ\)∈\{−1,0,\+1\}m\\widehat\{S\}^\{\(\\ell\)\}\\in\\\{\-1,0,\+1\\\}^\{m\}with exactly

r/2r/2entries

\+1\+1and

r/2r/2entries

−1\-1\.

4:Compute overlap score

V\(ℓ\):=∑j=1mmax⁡\{0,S^j\(ℓ\)​Sj\(ℓ\)\}V^\{\(\\ell\)\}:=\\sum\_\{j=1\}^\{m\}\\max\\\{0,\\,\\widehat\{S\}\_\{j\}^\{\(\\ell\)\}S\_\{j\}^\{\(\\ell\)\}\\\}\.

5:endfor

6:Returnsummary statistics of

\{V\(ℓ\)\}ℓ=1L\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\(e\.g\., mean or median\)\.

### A\.2Batchwise inclusion/exclusion prediction \(Instantiation I\)

Algorithm 2Auditor Instantiation I: Batchwise inclusion/exclusion prediction0:Batched dataset

𝒟=𝒟r∪𝒟f\{\\mathcal\{D\}\}=\{\\mathcal\{D\}\}\_\{r\}\\cup\{\\mathcal\{D\}\}\_\{f\}with

\|𝒟f\|=m\|\{\\mathcal\{D\}\}\_\{f\}\|=m; algorithms

\(𝒜,𝒰\)\(\{\\mathcal\{A\}\},\{\\mathcal\{U\}\}\); calibration rounds

Γ\\Gamma; support size

rr
0:Mechanism

ℳ:𝒮m→\{−1,0,\+1\}m\{\\mathcal\{M\}\}:\{\\mathcal\{S\}\}\_\{m\}\\to\\\{\-1,0,\+1\\\}^\{m\}
1:// Calibration phase\(run once, offline\)

2:for

γ=1,…,Γ\\gamma=1,\\dots,\\Gammado

3:

S\(γ\)∼Unif​\(𝒮m\)S^\{\(\\gamma\)\}\\sim\{\\mathrm\{Unif\}\}\(\{\\mathcal\{S\}\}\_\{m\}\),

𝒟\(γ\)←𝒟r∪𝒟f​\(S\(γ\)\)\{\\mathcal\{D\}\}^\{\(\\gamma\)\}\\leftarrow\{\\mathcal\{D\}\}\_\{r\}\\cup\{\\mathcal\{D\}\}\_\{f\}\(S^\{\(\\gamma\)\}\)
4:

f\(γ\)←𝒰​\(𝒜​\(𝒟\(γ\)\),𝒟\(γ\),𝒟f​\(S\(γ\)\)\)f^\{\(\\gamma\)\}\\leftarrow\{\\mathcal\{U\}\}\\big\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}^\{\(\\gamma\)\}\),\\,\{\\mathcal\{D\}\}^\{\(\\gamma\)\},\\,\{\\mathcal\{D\}\}\_\{f\}\(S^\{\(\\gamma\)\}\)\\big\)
5:

sx,y\(γ\)←ϕ​\(f\(γ\)​\(x\)y\)s^\{\(\\gamma\)\}\_\{x,y\}\\leftarrow\\phi\\\!\\left\(f^\{\(\\gamma\)\}\(x\)\_\{y\}\\right\)for all

\(x,y\)∈𝒟f\(x,y\)\\in\{\\mathcal\{D\}\}\_\{f\}
6:endfor

7:For each

j∈\[m\]j\\in\[m\]and

\(x,y\)∈𝒟f,j\(x,y\)\\in\{\\mathcal\{D\}\}\_\{f,j\}, fit Gaussians:

\(μx,y±,σx,y±\)←fit​\(\{sx,y\(γ\):Sj\(γ\)=±1\}γ=1Γ\)\(\\mu^\{\\pm\}\_\{x,y\},\\,\\sigma^\{\\pm\}\_\{x,y\}\)\\;\\leftarrow\\;\\mathrm\{fit\}\\\!\\left\(\\bigl\\\{s^\{\(\\gamma\)\}\_\{x,y\}:S^\{\(\\gamma\)\}\_\{j\}=\\pm 1\\bigr\\\}\_\{\\gamma=1\}^\{\\Gamma\}\\right\)
8:// Mechanismℳ​\(S\)\{\\mathcal\{M\}\}\(S\)\(applied at evaluation\)

9:

f←𝒰​\(𝒜​\(𝒟​\(S\)\),𝒟​\(S\),𝒟f​\(S\)\)f\\leftarrow\{\\mathcal\{U\}\}\\big\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\(S\)\),\\,\{\\mathcal\{D\}\}\(S\),\\,\{\\mathcal\{D\}\}\_\{f\}\(S\)\\big\),

sx,y←ϕ​\(f​\(x\)y\)s\_\{x,y\}\\leftarrow\\phi\\\!\\left\(f\(x\)\_\{y\}\\right\)
10:For each batch

j∈\[m\]j\\in\[m\], compute

Λj←∑\(x,y\)∈𝒟f,jlog⁡𝒩​\(sx,y;μx,y\+,σx,y\+\)𝒩​\(sx,y;μx,y−,σx,y−\)\\Lambda\_\{j\}\\;\\leftarrow\\;\\sum\_\{\(x,y\)\\in\{\\mathcal\{D\}\}\_\{f,j\}\}\\log\\frac\{\{\\mathcal\{N\}\}\\\!\\left\(s\_\{x,y\};\\,\\mu^\{\+\}\_\{x,y\},\\,\\sigma^\{\+\}\_\{x,y\}\\right\)\}\{\{\\mathcal\{N\}\}\\\!\\left\(s\_\{x,y\};\\,\\mu^\{\-\}\_\{x,y\},\\,\\sigma^\{\-\}\_\{x,y\}\\right\)\}
11:

S^j←\+1\\widehat\{S\}\_\{j\}\\leftarrow\+1for top\-

r/2r/2values of

Λj\\Lambda\_\{j\};

−1\\;\-1for bottom\-

r/2r/2;

0\\;0otherwise

12:return

S^∈\{−1,0,\+1\}m\\widehat\{S\}\\in\\\{\-1,0,\+1\\\}^\{m\}

### A\.3Pairwise auditor \(baseline\)

Nasret al\.\[[2021](https://arxiv.org/html/2607.05898#bib.bib8)\]audit DP by having the adversary distinguish two models trained on neighbouring datasets\. We adapt this baseline to unlearning by distinguishing the two unlearned modelsfu\(i\):=𝒰​\(𝒜​\(𝒟r∪𝒟f\(i\)\),𝒟r∪𝒟f\(i\),𝒟f\(i\)\)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\)fori∈\{1,2\}i\\in\\\{1,2\\\}, corresponding to two distinct forget sets𝒟f\(1\),𝒟f\(2\)\{\\mathcal\{D\}\}\_\{f\}^\{\(1\)\},\{\\mathcal\{D\}\}\_\{f\}^\{\(2\)\}\. Calibration and prediction are identical to Instantiation II withm=2m=2and𝒟f,j=𝒟f\(j\)\{\\mathcal\{D\}\}\_\{f,j\}=\{\\mathcal\{D\}\}\_\{f\}^\{\(j\)\}; only the conversion to anε\\varepsilonlower bound differs\. From the true and false positive rates, the lower bound is computed directly from the confusion matrix using\[Kairouzet al\.,[2015](https://arxiv.org/html/2607.05898#bib.bib15), Theorem 2\.1\]with Clopper–Pearson confidence intervals, rather than via[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)\. For a given confidence levelζ\\zetaand appropriateδ\\delta, the bound is

εLB=max⁡\{log⁡1−δ−FPhighFNhigh,log⁡1−δ−FNhighFPhigh\},\\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\\\},\(3\)whereFPhigh\\mathrm\{FP\}^\{\\mathrm\{high\}\}andFNhigh\\mathrm\{FN\}^\{\\mathrm\{high\}\}are the upper Clopper–Pearson bounds on the false\-positive and false\-negative rates\.[Table2](https://arxiv.org/html/2607.05898#S8.T2)compares this baseline with the bounds from[Lemma4\.1](https://arxiv.org/html/2607.05898#S4.Thmtheorem1)\.

### A\.4Joint sign\-vector prediction \(Instantiation II\)

Algorithm 3Auditor Instantiation II: Joint sign\-vector prediction0:Batched dataset

𝒟=𝒟r∪𝒟f\{\\mathcal\{D\}\}=\{\\mathcal\{D\}\}\_\{r\}\\cup\{\\mathcal\{D\}\}\_\{f\}with

\|𝒟f\|=m\|\{\\mathcal\{D\}\}\_\{f\}\|=m; algorithms

\(𝒜,𝒰\)\(\{\\mathcal\{A\}\},\{\\mathcal\{U\}\}\); calibration rounds

Γ\\Gamma
0:Mechanism

ℳ:𝒮m→𝒮m\{\\mathcal\{M\}\}:\{\\mathcal\{S\}\}\_\{m\}\\to\{\\mathcal\{S\}\}\_\{m\}
1:// Calibration phase\(run once, offline\)

2:for all

S~∈𝒮m\\widetilde\{S\}\\in\{\\mathcal\{S\}\}\_\{m\}do

3:for

γ=1,…,Γ\\gamma=1,\\dots,\\Gammado

4:

f\(γ\)←𝒰​\(𝒜​\(𝒟​\(S~\)\),𝒟​\(S~\),𝒟f​\(S~\)\)f^\{\(\\gamma\)\}\\leftarrow\{\\mathcal\{U\}\}\\big\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\(\\widetilde\{S\}\)\),\\,\{\\mathcal\{D\}\}\(\\widetilde\{S\}\),\\,\{\\mathcal\{D\}\}\_\{f\}\(\\widetilde\{S\}\)\\big\)
5:

sx,y\(γ\)​\(S~\)←ϕ​\(f\(γ\)​\(x\)y\)s^\{\(\\gamma\)\}\_\{x,y\}\(\\widetilde\{S\}\)\\leftarrow\\phi\\\!\\left\(f^\{\(\\gamma\)\}\(x\)\_\{y\}\\right\)for all

\(x,y\)∈𝒟f\(x,y\)\\in\{\\mathcal\{D\}\}\_\{f\}
6:endfor

7:For each

\(x,y\)∈𝒟f\(x,y\)\\in\{\\mathcal\{D\}\}\_\{f\}, fit Gaussian:

\(μx,y​\(S~\),σx,y​\(S~\)\)←fit​\(\{sx,y\(γ\)​\(S~\)\}γ=1Γ\)\(\\mu\_\{x,y\}\(\\widetilde\{S\}\),\\,\\sigma\_\{x,y\}\(\\widetilde\{S\}\)\)\\;\\leftarrow\\;\\mathrm\{fit\}\\\!\\left\(\\bigl\\\{s^\{\(\\gamma\)\}\_\{x,y\}\(\\widetilde\{S\}\)\\bigr\\\}\_\{\\gamma=1\}^\{\\Gamma\}\\right\)
8:endfor

9:// Mechanismℳ​\(S\)\{\\mathcal\{M\}\}\(S\)\(applied at evaluation\)

10:

f←𝒰​\(𝒜​\(𝒟​\(S\)\),𝒟​\(S\),𝒟f​\(S\)\)f\\leftarrow\{\\mathcal\{U\}\}\\big\(\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\(S\)\),\\,\{\\mathcal\{D\}\}\(S\),\\,\{\\mathcal\{D\}\}\_\{f\}\(S\)\\big\),

sx,y←ϕ​\(f​\(x\)y\)s\_\{x,y\}\\leftarrow\\phi\\\!\\left\(f\(x\)\_\{y\}\\right\)
11:For each

S~∈𝒮m\\widetilde\{S\}\\in\{\\mathcal\{S\}\}\_\{m\}, compute

Λ​\(S~\)←∑\(x,y\)∈𝒟flog⁡𝒩​\(sx,y;μx,y​\(S~\),σx,y​\(S~\)\)\\Lambda\(\\widetilde\{S\}\)\\;\\leftarrow\\;\\sum\_\{\(x,y\)\\in\{\\mathcal\{D\}\}\_\{f\}\}\\log\{\\mathcal\{N\}\}\\\!\\left\(s\_\{x,y\};\\,\\mu\_\{x,y\}\(\\widetilde\{S\}\),\\,\\sigma\_\{x,y\}\(\\widetilde\{S\}\)\\right\)
12:return

S^←arg⁡maxS~∈𝒮m⁡Λ​\(S~\)\\widehat\{S\}\\;\\leftarrow\\;\\arg\\max\_\{\\widetilde\{S\}\\in\{\\mathcal\{S\}\}\_\{m\}\}\\Lambda\(\\widetilde\{S\}\)

## Appendix BProof of[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)

We now restate[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)and prove it below\.

###### Lemma\(Restatement of[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)\)\.

Letℳ:𝒮m→\{−1,0,\+1\}m\{\\mathcal\{M\}\}:\{\\mathcal\{S\}\}\_\{m\}\\to\\\{\-1,0,\+1\\\}^\{m\}be an\(ε,0\)\(\\varepsilon,0\)\-locally differentially private mechanism\. Let𝒯⊆\{−1,0,\+1\}m\\mathcal\{T\}\\subseteq\\\{\-1,0,\+1\\\}^\{m\}denote the subset of vectors with exactlyr/2r/2entries equal to\+1\+1andr/2r/2entries equal to−1\-1\. SetM′=\(m⌊m/2⌋\)M^\{\\prime\}=\\binom\{m\}\{\\lfloor m/2\\rfloor\}andK:=\|𝒯\|=\(mr/2,r/2,m−r\)K\\;:=\\;\|\\mathcal\{T\}\|\\;=\\;\\binom\{m\}\{r/2,\\,r/2,\\,m\-r\}\. Let\{S\(ℓ\)\}ℓ=1L\\\{S^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}be independent random vectors drawn uniformly from𝒮m\{\\mathcal\{S\}\}\_\{m\}\. For eachℓ∈\[L\]\\ell\\in\[L\], letS^\(ℓ\)=ℳ​\(S\(ℓ\)\)\\widehat\{S\}^\{\(\\ell\)\}=\{\\mathcal\{M\}\}\(S^\{\(\\ell\)\}\), assumeS^\(ℓ\)∈𝒯\\widehat\{S\}^\{\(\\ell\)\}\\in\\mathcal\{T\}almost surely, and defineV\(ℓ\):=∑j=1mmax⁡\{0,S^j\(ℓ\)​Sj\(ℓ\)\}∈\{0,1,…,r\}V^\{\(\\ell\)\}\\;:=\\;\\sum\_\{j=1\}^\{m\}\\max\\\!\\bigl\\\{0,\\,\\widehat\{S\}^\{\(\\ell\)\}\_\{j\}S^\{\(\\ell\)\}\_\{j\}\\bigr\\\}\\;\\in\\;\\\{0,1,\\dots,r\\\}\. For eachu∈\{0,1,…,r\}u\\in\\\{0,1,\\dots,r\\\}, define the pointwise bound

πε​\(u\):=∑α1,α2∈\{0,…,r/2\}α1\+α2=u\(m−r⌈\(m−r\)/2⌉−\(α1−α2\)\)​\(r/2α1\)​\(r/2α2\)⋅eεeε\+M′−1\.\\pi\_\{\\varepsilon\}\(u\)\\;:=\\,\\;\\sum\_\{\\begin\{subarray\}\{c\}\\alpha\_\{1\},\\alpha\_\{2\}\\in\\\{0,\\dots,r/2\\\}\\\\ \\alpha\_\{1\}\+\\alpha\_\{2\}=u\\end\{subarray\}\}\\binom\{m\-r\}\{\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\}\\binom\{r/2\}\{\\alpha\_\{1\}\}\\binom\{r/2\}\{\\alpha\_\{2\}\}\\cdot\\,\\frac\{e^\{\\varepsilon\}\\;\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\.Define the upper tailPε​\(v\):=∑u=vrπε​\(u\)P\_\{\\varepsilon\}\(v\):=\\sum\_\{u=v\}^\{r\}\\pi\_\{\\varepsilon\}\(u\)\. Then for everyv∈ℝv\\in\\mathbb\{R\},

Pr⁡\[1L​∑ℓ=1LV\(ℓ\)≥v\]≤infλ≥0exp⁡\(L​log⁡\(∑u=0reλ​u​πε​\(u\)\)−λ​L​v\)\\Pr\\\!\\left\[\\frac\{1\}\{L\}\\sum\_\{\\ell=1\}^\{L\}V^\{\(\\ell\)\}\\geq v\\right\]\\;\\leq\\;\\inf\_\{\\lambda\\geq 0\}\\exp\\\!\\left\(L\\log\\\!\\Big\(\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\\Big\)\-\\lambda Lv\\right\)\(4\)Pr⁡\(Median​\(\{V\(ℓ\)\}ℓ=1L\)≥v\)≤\(L⌈L/2⌉\)​Pε​\(v\)⌈L/2⌉\.\\Pr\\\!\\left\(\\mathrm\{Median\}\\\!\\left\(\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\\right\)\\geq v\\right\)\\;\\leq\\;\\binom\{L\}\{\\lceil L/2\\rceil\}\\,P\_\{\\varepsilon\}\(v\)^\{\\lceil L/2\\rceil\}\.\(5\)

###### Proof\.

We first establish the pointwise bound

Pr⁡\[V\(ℓ\)=u\]≤πε​\(u\)for every​u∈\{0,1,…,r\}\.\\Pr\[V^\{\(\\ell\)\}=u\\bigr\]\\;\\leq\\;\\pi\_\{\\varepsilon\}\(u\)\\qquad\\text\{for every \}u\\in\\\{0,1,\\dots,r\\\}\.\(6\)Fixℓ\\elland writeS=S\(ℓ\)S=S^\{\(\\ell\)\},S^=S^\(ℓ\)\\widehat\{S\}=\\widehat\{S\}^\{\(\\ell\)\},V=V\(ℓ\)V=V^\{\(\\ell\)\}\.

##### Posterior bound fromε\\varepsilon\-LDP\.

Fix anyt∈𝒯t\\in\\mathcal\{T\}in the support ofS^\\widehat\{S\}and anys∈𝒮ms\\in\{\\mathcal\{S\}\}\_\{m\}\. Pureε\\varepsilon\-LDP givesPr⁡\[S^=t∣S=s\]≤eε​Pr⁡\[S^=t∣S=s′\]\\Pr\[\\widehat\{S\}=t\\mid S=s\]\\leq e^\{\\varepsilon\}\\Pr\[\\widehat\{S\}=t\\mid S=s^\{\\prime\}\]for everys′∈𝒮ms^\{\\prime\}\\in\{\\mathcal\{S\}\}\_\{m\}, hencePr⁡\[S^=t∣S=s′\]≥e−ε​Pr⁡\[S^=t∣S=s\]\\Pr\[\\widehat\{S\}=t\\mid S=s^\{\\prime\}\]\\geq e^\{\-\\varepsilon\}\\Pr\[\\widehat\{S\}=t\\mid S=s\]\. Summing overs′∈𝒮ms^\{\\prime\}\\in\{\\mathcal\{S\}\}\_\{m\}and using the uniform prior on𝒮m\{\\mathcal\{S\}\}\_\{m\},

M′​Pr⁡\[S^=t\]=∑s′∈𝒮mPr⁡\[S^=t∣S=s′\]≥Pr⁡\[S^=t∣S=s\]​\(1\+\(M′−1\)​e−ε\)\.M^\{\\prime\}\\Pr\[\\widehat\{S\}=t\]=\\sum\_\{s^\{\\prime\}\\in\{\\mathcal\{S\}\}\_\{m\}\}\\Pr\[\\widehat\{S\}=t\\mid S=s^\{\\prime\}\]\\;\\geq\\;\\Pr\[\\widehat\{S\}=t\\mid S=s\]\\bigl\(1\+\(M^\{\\prime\}\-1\)e^\{\-\\varepsilon\}\\bigr\)\.Bayes’ rule then yields the pointwise posterior bound

Pr⁡\[S=s∣S^=t\]=Pr⁡\[S^=t∣S=s\]M′​Pr⁡\[S^=t\]≤11\+\(M′−1\)​e−ε=eεeε\+M′−1\.\\Pr\[S=s\\mid\\widehat\{S\}=t\]\\;=\\;\\frac\{\\Pr\[\\widehat\{S\}=t\\mid S=s\]\}\{M^\{\\prime\}\\Pr\[\\widehat\{S\}=t\]\}\\;\\leq\\;\\frac\{1\}\{1\+\(M^\{\\prime\}\-1\)e^\{\-\\varepsilon\}\}\\;=\\;\\frac\{e^\{\\varepsilon\}\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\.\(7\)

##### Counting argument\.

For\(s,t\)∈𝒮m×𝒯\(s,t\)\\in\{\\mathcal\{S\}\}\_\{m\}\\times\\mathcal\{T\}, letα1:=\|\{j:tj=\+1,sj=\+1\}\|\\alpha\_\{1\}:=\|\\\{j:t\_\{j\}=\+1,s\_\{j\}=\+1\\\}\|andα2:=\|\{j:tj=−1,sj=−1\}\|\\alpha\_\{2\}:=\|\\\{j:t\_\{j\}=\-1,s\_\{j\}=\-1\\\}\|, both in\{0,…,r/2\}\\\{0,\\dots,r/2\\\}\. Sincetj≠0t\_\{j\}\\neq 0on exactlyrrcoordinates,

V​\(s,t\)=∑j=1mmax⁡\{0,sj​tj\}=α1\+α2\.V\(s,t\)\\;=\\;\\sum\_\{j=1\}^\{m\}\\max\\\{0,s\_\{j\}t\_\{j\}\\\}\\;=\\;\\alpha\_\{1\}\+\\alpha\_\{2\}\.For each fixedt∈𝒯t\\in\\mathcal\{T\}, the number ofs∈𝒮ms\\in\{\\mathcal\{S\}\}\_\{m\}withV​\(s,t\)=uV\(s,t\)=uis exactlyNuN\_\{u\}: pick theα1\\alpha\_\{1\}agreement positions among ther/2r/2coordinates wheretj=\+1t\_\{j\}=\+1\(\(r/2α1\)\\binom\{r/2\}\{\\alpha\_\{1\}\}ways\) and theα2\\alpha\_\{2\}agreement positions among ther/2r/2coordinates wheretj=−1t\_\{j\}=\-1\(\(r/2α2\)\\binom\{r/2\}\{\\alpha\_\{2\}\}ways\)\. The total\+1\+1/−1\-1imbalance ofssis then2​\(α1−α2\)\+2​β−\(m−r\)2\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\+2\\beta\-\(m\-r\), whereβ\\betais the number of\+1\+1entries ofsson the zero\-block oftt\. The constraints∈𝒮ms\\in\{\\mathcal\{S\}\}\_\{m\}forces this imbalance into\{0,1\}\\\{0,1\\\}, whose unique integer solution inβ\\betaisβ=⌈\(m−r\)/2⌉−\(α1−α2\)\\beta=\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\), contributing the\(m−r⌈\(m−r\)/2⌉−\(α1−α2\)\)\\binom\{m\-r\}\{\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\}factor\.

##### Assembling equation[6](https://arxiv.org/html/2607.05898#A2.E6)\.

Conditioning onS^=t\\widehat\{S\}=tand applying equation[7](https://arxiv.org/html/2607.05898#A2.E7)to each of theNuN\_\{u\}posterior summands,

Pr⁡\[V=u∣S^=t\]=∑s:V​\(s,t\)=uPr⁡\[S=s∣S^=t\]≤Nu⋅eεeε\+M′−1=πε​\(u\)\.\\Pr\[V=u\\mid\\widehat\{S\}=t\]\\;=\\;\\sum\_\{s:\\,V\(s,t\)=u\}\\Pr\[S=s\\mid\\widehat\{S\}=t\]\\;\\leq\\;N\_\{u\}\\cdot\\frac\{e^\{\\varepsilon\}\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\\;=\\;\\pi\_\{\\varepsilon\}\(u\)\.Marginalizing overS^\\widehat\{S\}givesPr⁡\[V=u\]≤πε​\(u\)\\Pr\[V=u\]\\leq\\pi\_\{\\varepsilon\}\(u\), proving equation[6](https://arxiv.org/html/2607.05898#A2.E6)\. Summing overu≥vu\\geq v,

Pr⁡\[V≥v\]≤Pε​\(v\)\.\\Pr\[V\\geq v\]\\;\\leq\\;P\_\{\\varepsilon\}\(v\)\.\(8\)

##### Median bound equation[2](https://arxiv.org/html/2607.05898#S4.E2)\.

The eventMedian​\(\{V\(ℓ\)\}ℓ=1L\)≥v\\mathrm\{Median\}\(\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\)\\geq vimplies the existence of someJ⊆\[L\]J\\subseteq\[L\]with\|J\|=⌈L/2⌉\|J\|=\\lceil L/2\\rceilsuch thatV\(ℓ\)≥vV^\{\(\\ell\)\}\\geq vfor everyℓ∈J\\ell\\in J\. By independence and a union bound over the\(L⌊L/2⌋\)\\binom\{L\}\{\\lfloor L/2\\rfloor\}such subsets, together with equation[8](https://arxiv.org/html/2607.05898#A2.E8),

Pr⁡\(Median​\(\{V\(ℓ\)\}ℓ=1L\)≥v\)≤\(L⌈L/2⌉\)​Pε​\(v\)⌈L/2⌉\.\\Pr\\\!\\left\(\\mathrm\{Median\}\\\!\\left\(\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\\right\)\\geq v\\right\)\\;\\leq\\;\\binom\{L\}\{\\lceil L/2\\rceil\}P\_\{\\varepsilon\}\(v\)^\{\\lceil L/2\\rceil\}\.

##### Chernoff bound equation[1](https://arxiv.org/html/2607.05898#S4.E1)\.

Fixλ≥0\\lambda\\geq 0\. By equation[6](https://arxiv.org/html/2607.05898#A2.E6),

𝔼​\[eλ​V\(ℓ\)\]=∑u=0reλ​u​Pr⁡\[V\(ℓ\)=u\]≤∑u=0reλ​u​πε​\(u\)\.\\mathbb\{E\}\\\!\\left\[e^\{\\lambda V^\{\(\\ell\)\}\}\\right\]\\;=\\;\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\Pr\[V^\{\(\\ell\)\}=u\]\\;\\leq\\;\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\.By independence acrossℓ\\elland Markov’s inequality applied toeλ​∑ℓV\(ℓ\)e^\{\\lambda\\sum\_\{\\ell\}V^\{\(\\ell\)\}\},

Pr⁡\[1L​∑ℓ=1LV\(ℓ\)≥v\]≤e−λ​L​v​\(∑u=0reλ​u​πε​\(u\)\)L=exp⁡\(L​log⁡\(∑u=0reλ​u​πε​\(u\)\)−λ​L​v\)\.\\Pr\\\!\\left\[\\frac\{1\}\{L\}\\sum\_\{\\ell=1\}^\{L\}V^\{\(\\ell\)\}\\geq v\\right\]\\;\\leq\\;e^\{\-\\lambda Lv\}\\Bigg\(\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\\Bigg\)^\{\\\!L\}\\;=\\;\\exp\\\!\\left\(L\\log\\\!\\Big\(\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\\Big\)\-\\lambda Lv\\right\)\.Optimizing overλ≥0\\lambda\\geq 0yields equation[1](https://arxiv.org/html/2607.05898#S4.E1)\. ∎ We now state a corollary showing that the upper bounds for median and mean statistic proven above is monotonic inε\\varepsilonand thus, to reject the hypothesisε≤εLB\\varepsilon\\leq\\varepsilon\_\{\\text\{LB\}\}, it is sufficient to evaluate the bound atε=εLB\\varepsilon=\\varepsilon\_\{\\text\{LB\}\}forδ<M′K\\delta<\\frac\{M^\{\\prime\}\}\{K\}\.

###### Corollary B\.2\(Monotonicity of audit bounds\)\.

Forδ=0\\delta=0, the right\-hand sides of[Equation1](https://arxiv.org/html/2607.05898#S4.E1)and[Equation2](https://arxiv.org/html/2607.05898#S4.E2)in[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)are monotone non\-decreasing inε\\varepsilon\.

###### Proof\.

Forδ=0\\delta=0, the pointwise bound factorises asπε​\(u\)=C​\(u\)⋅g​\(ε\)\\pi\_\{\\varepsilon\}\(u\)=C\(u\)\\cdot g\(\\varepsilon\), where

C​\(u\):=∑α1,α2∈\{0,…,r/2\}α1\+α2=u\(m−r⌈\(m−r\)/2⌉−\(α1−α2\)\)​\(r/2α1\)​\(r/2α2\)≥0C\(u\):=\\sum\_\{\\begin\{subarray\}\{c\}\\alpha\_\{1\},\\alpha\_\{2\}\\in\\\{0,\\dots,r/2\\\}\\\\ \\alpha\_\{1\}\+\\alpha\_\{2\}=u\\end\{subarray\}\}\\binom\{m\-r\}\{\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\}\\binom\{r/2\}\{\\alpha\_\{1\}\}\\binom\{r/2\}\{\\alpha\_\{2\}\}\\;\\geq\\;0is independent ofε\\varepsilon, and

g​\(ε\):=eεeε\+M′−1=11\+\(M′−1\)​e−ε\.g\(\\varepsilon\):=\\frac\{e^\{\\varepsilon\}\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}=\\frac\{1\}\{1\+\(M^\{\\prime\}\-1\)\\,e^\{\-\\varepsilon\}\}\.SinceM′≥1M^\{\\prime\}\\geq 1, the functionggis strictly increasing inε\\varepsilon, and henceπε​\(u\)\\pi\_\{\\varepsilon\}\(u\)is monotone non\-decreasing inε\\varepsilonfor every fixedu∈\{0,1,…,r\}u\\in\\\{0,1,\\dots,r\\\}\.

Median bound \([Equation2](https://arxiv.org/html/2607.05898#S4.E2)\)\.The upper tailPε​\(v\)=∑u=⌈v⌉rπε​\(u\)P\_\{\\varepsilon\}\(v\)=\\sum\_\{u=\\lceil v\\rceil\}^\{r\}\\pi\_\{\\varepsilon\}\(u\)is a non\-negative sum of monotone non\-decreasing functions, and is therefore itself monotone non\-decreasing inε\\varepsilon\. Raising to the power⌈L/2⌉\\lceil L/2\\rceiland multiplying by the positive constant\(L⌊L/2⌋\)\\binom\{L\}\{\\lfloor L/2\\rfloor\}both preserve monotonicity\.

Mean bound \([Equation1](https://arxiv.org/html/2607.05898#S4.E1)\)\.Fix anyλ≥0\\lambda\\geq 0\. The moment generating function∑u=0reλ​u​πε​\(u\)\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)is a non\-negative linear combination of\{πε​\(u\)\}u\\\{\\pi\_\{\\varepsilon\}\(u\)\\\}\_\{u\}, hence monotone non\-decreasing inε\\varepsilon\. Composing withlog\\log\(monotone\), multiplying byL\>0L\>0, subtracting theε\\varepsilon\-independent termλ​L​v\\lambda Lv, and exponentiating all preserve monotonicity\. Therefore, for each fixedλ≥0\\lambda\\geq 0, the function inside the infimum is monotone non\-decreasing inε\\varepsilon\. A pointwise infimum of monotone non\-decreasing functions is itself monotone non\-decreasing: forε1≤ε2\\varepsilon\_\{1\}\\leq\\varepsilon\_\{2\}and anyλ\\lambda,fλ​\(ε1\)≤fλ​\(ε2\)f\_\{\\lambda\}\(\\varepsilon\_\{1\}\)\\leq f\_\{\\lambda\}\(\\varepsilon\_\{2\}\), so taking the infimum overλ\\lambdaon both sides yieldsinfλfλ​\(ε1\)≤infλfλ​\(ε2\)\\inf\_\{\\lambda\}f\_\{\\lambda\}\(\\varepsilon\_\{1\}\)\\leq\\inf\_\{\\lambda\}f\_\{\\lambda\}\(\\varepsilon\_\{2\}\)\. This completes the proof\. ∎

## Appendix CA discussion on settingδ\>0\\delta\>0in the auditing lower bound

We now state a version of this auditing lemma[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)under the case ofδ\>0\\delta\>0\.

###### Lemma C\.1\(Auditing test withδ\>0\\delta\>0\)\.

Letℳ:𝒮m→\{−1,0,\+1\}m\{\\mathcal\{M\}\}:\{\\mathcal\{S\}\}\_\{m\}\\to\\\{\-1,0,\+1\\\}^\{m\}be an\(ε,δ\)\(\\varepsilon,\\delta\)\-locally differentially private mechanism\. Let𝒯⊆\{−1,0,\+1\}m\\mathcal\{T\}\\subseteq\\\{\-1,0,\+1\\\}^\{m\}denote the subset of vectors with exactlyr/2r/2entries equal to\+1\+1andr/2r/2entries equal to−1\-1\. SetM′=\(m⌊m/2⌋\)M^\{\\prime\}=\\binom\{m\}\{\\lfloor m/2\\rfloor\}andK:=\|𝒯\|=\(mr/2,r/2,m−r\)K\\;:=\\;\|\\mathcal\{T\}\|\\;=\\;\\binom\{m\}\{r/2,\\,r/2,\\,m\-r\}\. Let\{S\(ℓ\)\}ℓ=1L\\\{S^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}be independent random vectors drawn uniformly from𝒮m\{\\mathcal\{S\}\}\_\{m\}\. For eachℓ∈\[L\]\\ell\\in\[L\], letS^\(ℓ\)=ℳ​\(S\(ℓ\)\)\\widehat\{S\}^\{\(\\ell\)\}=\{\\mathcal\{M\}\}\(S^\{\(\\ell\)\}\), assumeS^\(ℓ\)∈𝒯\\widehat\{S\}^\{\(\\ell\)\}\\in\\mathcal\{T\}almost surely, and defineV\(ℓ\):=∑j=1mmax⁡\{0,S^j\(ℓ\)​Sj\(ℓ\)\}∈\{0,1,…,r\}V^\{\(\\ell\)\}\\;:=\\;\\sum\_\{j=1\}^\{m\}\\max\\\!\\bigl\\\{0,\\,\\widehat\{S\}^\{\(\\ell\)\}\_\{j\}S^\{\(\\ell\)\}\_\{j\}\\bigr\\\}\\;\\in\\;\\\{0,1,\\dots,r\\\}\. For eachu∈\{0,1,…,r\}u\\in\\\{0,1,\\dots,r\\\}, define the pointwise bound

πε​\(u\):=∑α1,α2∈\{0,…,r/2\}α1\+α2=u\(m−r⌈\(m−r\)/2⌉−\(α1−α2\)\)​\(r/2α1\)​\(r/2α2\)⋅eε\+M′−1M′​K​δeε\+M′−1\.\\pi\_\{\\varepsilon\}\(u\)\\;:=\\,\\;\\sum\_\{\\begin\{subarray\}\{c\}\\alpha\_\{1\},\\alpha\_\{2\}\\in\\\{0,\\dots,r/2\\\}\\\\ \\alpha\_\{1\}\+\\alpha\_\{2\}=u\\end\{subarray\}\}\\binom\{m\-r\}\{\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\}\\binom\{r/2\}\{\\alpha\_\{1\}\}\\binom\{r/2\}\{\\alpha\_\{2\}\}\\cdot\\,\\frac\{e^\{\\varepsilon\}\\;\+\\;\\tfrac\{M^\{\\prime\}\-1\}\{M^\{\\prime\}\}\\,K\\,\\delta\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\.Define the upper tailPε​\(v\):=∑u=vrπε​\(u\)P\_\{\\varepsilon\}\(v\):=\\sum\_\{u=v\}^\{r\}\\pi\_\{\\varepsilon\}\(u\)\. Then for everyv∈ℝv\\in\\mathbb\{R\},

Pr⁡\[1L​∑ℓ=1LV\(ℓ\)≥v\]≤infλ≥0exp⁡\(L​log⁡\(∑u=0reλ​u​πε​\(u\)\)−λ​L​v\)\\Pr\\\!\\left\[\\frac\{1\}\{L\}\\sum\_\{\\ell=1\}^\{L\}V^\{\(\\ell\)\}\\geq v\\right\]\\;\\leq\\;\\inf\_\{\\lambda\\geq 0\}\\exp\\\!\\left\(L\\log\\\!\\Big\(\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\\Big\)\-\\lambda Lv\\right\)\(9\)Pr⁡\(Median​\(\{V\(ℓ\)\}ℓ=1L\)≥v\)≤\(L⌊L/2⌋\)​Pε​\(v\)⌈L/2⌉\.\\Pr\\\!\\left\(\\mathrm\{Median\}\\\!\\left\(\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\\right\)\\geq v\\right\)\\;\\leq\\;\\binom\{L\}\{\\lfloor L/2\\rfloor\}\\,P\_\{\\varepsilon\}\(v\)^\{\\lceil L/2\\rceil\}\.\(10\)

Additionally, for the test to be meaningful, we need to ensure that the upper bound is monotonically non\-decreasing inε\\varepsilon\(discussed in[Section4\.1](https://arxiv.org/html/2607.05898#S4.SS1)\) which holds whenδ<M′/K\\delta<M^\{\\prime\}/K\. A discussion on the same is done below\.

##### Vacuity from theδ\\delta\-slack\.

The pointwise boundπε​\(u\)\\pi\_\{\\varepsilon\}\(u\)contains an additive contribution proportional to\(M′−1\)​K​δM′\\frac\{\(M^\{\\prime\}\-1\)\\,K\\,\\delta\}\{M^\{\\prime\}\}\. SinceM′≥1M^\{\\prime\}\\geq 1, this factor is essentiallyK​δK\\delta, andK=\(mr/2,r/2,m−r\)K=\\binom\{m\}\{r/2,\\,r/2,\\,m\-r\}grows rapidly withmmandrr: form=4500m=4500andr∈\{2000,3000\}r\\in\\\{2000,3000\\\}, Stirling givesln⁡K≈4475\\ln K\\approx 4475, so evenδ=10−10\\delta=10^\{\-10\}leavesK​δK\\deltaorders of magnitude larger than any realisticεLB\\varepsilon\_\{\\mathrm\{LB\}\}\. The audit becomes vacuous in this regime regardless of the monotonicity condition below\.

##### Monotonicity for a valid hypothesis test\.

For the testH0:ε≤εLBH\_\{0\}:\\varepsilon\\leq\\varepsilon\_\{\\mathrm\{LB\}\}to control Type\-I error uniformly over the null, the upper bound must be monotone non\-decreasing inε\\varepsilon– otherwise rejection atε=εLB\\varepsilon=\\varepsilon\_\{\\mathrm\{LB\}\}does not imply rejection for allε≤εLB\\varepsilon\\leq\\varepsilon\_\{\\mathrm\{LB\}\}\. By[CorollaryC\.3](https://arxiv.org/html/2607.05898#A3.Thmtheorem3)this requiresδ<M′/K\\delta<M^\{\\prime\}/K\. Asymptotically,M′≥KM^\{\\prime\}\\geq KiffH2​\(α\)\+α≤1H\_\{2\}\(\\alpha\)\+\\alpha\\leq 1forα=r/m\\alpha=r/m, giving a thresholdα∗≈0\.227\\alpha^\{\\ast\}\\approx 0\.227\. Form=4500m=4500this means anyr≲1020r\\lesssim 1020givesM′≥KM^\{\\prime\}\\geq K, in which caseδ<1\\delta<1trivially suffices; e\.g\.r=1000r=1000is comfortably inside this regime\. The audit is therefore well\-posed across the operating points used in our experiments\.

###### Proof of[LemmaC\.1](https://arxiv.org/html/2607.05898#A3.Thmtheorem1)\.

We first establish the pointwise bound

Pr⁡\[V\(ℓ\)=u\]≤πε​\(u\)for every​u∈\{0,1,…,r\}\.\\Pr\[V^\{\(\\ell\)\}=u\\bigr\]\\;\\leq\\;\\pi\_\{\\varepsilon\}\(u\)\\qquad\\text\{for every \}u\\in\\\{0,1,\\dots,r\\\}\.\(11\)Fixℓ\\elland writeS=S\(ℓ\)S=S^\{\(\\ell\)\},S^=S^\(ℓ\)\\widehat\{S\}=\\widehat\{S\}^\{\(\\ell\)\},V=V\(ℓ\)V=V^\{\(\\ell\)\}\.

##### Marginal joint bound from LDP\.

Fixs∈𝒮s\\in\\mathcal\{S\}andt∈𝒯t\\in\\mathcal\{T\}\. By\(ε,δ\)\(\\varepsilon,\\delta\)\-LDP,Pr⁡\[S^=t∣S=s\]≤eε​Pr⁡\[S^=t∣S=s′\]\+δ\\Pr\[\\widehat\{S\}=t\\mid S=s\]\\leq e^\{\\varepsilon\}\\Pr\[\\widehat\{S\}=t\\mid S=s^\{\\prime\}\]\+\\deltafor everys′∈𝒮s^\{\\prime\}\\in\\mathcal\{S\}\. Averaging this inequality overs′∈𝒮∖\{s\}s^\{\\prime\}\\in\\mathcal\{S\}\\setminus\\\{s\\\}and using∑s′∈𝒮Pr⁡\[S^=t∣S=s′\]=M′​Pr⁡\[S^=t\]\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}\\Pr\[\\widehat\{S\}=t\\mid S=s^\{\\prime\}\]=M^\{\\prime\}\\Pr\[\\widehat\{S\}=t\]\(uniform prior on𝒮\\mathcal\{S\}\),

Pr⁡\[S^=t∣S=s\]​\(1\+eεM′−1\)≤eε​M′M′−1​Pr⁡\[S^=t\]\+δ,\\Pr\[\\widehat\{S\}=t\\mid S=s\]\\Bigl\(1\+\\tfrac\{e^\{\\varepsilon\}\}\{M^\{\\prime\}\-1\}\\Bigr\)\\;\\leq\\;\\tfrac\{e^\{\\varepsilon\}M^\{\\prime\}\}\{M^\{\\prime\}\-1\}\\Pr\[\\widehat\{S\}=t\]\+\\delta,which rearranges to

Pr⁡\[S^=t∣S=s\]≤eε​M′​Pr⁡\[S^=t\]\+\(M′−1\)​δeε\+M′−1\.\\Pr\[\\widehat\{S\}=t\\mid S=s\]\\;\\leq\\;\\frac\{e^\{\\varepsilon\}M^\{\\prime\}\\Pr\[\\widehat\{S\}=t\]\+\(M^\{\\prime\}\-1\)\\delta\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\.Multiplying by the prior1/M′1/M^\{\\prime\}gives the joint bound

Pr⁡\[S=s,S^=t\]≤eε​Pr⁡\[S^=t\]\+M′−1M′​δeε\+M′−1\.\\Pr\[S=s,\\,\\widehat\{S\}=t\]\\;\\leq\\;\\frac\{e^\{\\varepsilon\}\\Pr\[\\widehat\{S\}=t\]\+\\tfrac\{M^\{\\prime\}\-1\}\{M^\{\\prime\}\}\\delta\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\.\(12\)

##### Counting argument\.

For\(s,t\)∈𝒮m×𝒯\(s,t\)\\in\{\\mathcal\{S\}\}\_\{m\}\\times\\mathcal\{T\}, letα1:=\|\{j:tj=\+1,sj=\+1\}\|\\alpha\_\{1\}:=\|\\\{j:t\_\{j\}=\+1,s\_\{j\}=\+1\\\}\|andα2:=\|\{j:tj=−1,sj=−1\}\|\\alpha\_\{2\}:=\|\\\{j:t\_\{j\}=\-1,s\_\{j\}=\-1\\\}\|, both in\{0,…,r/2\}\\\{0,\\dots,r/2\\\}\. ThenV​\(s,t\)=∑jmax⁡\{0,sj​tj\}=α1\+α2V\(s,t\)=\\sum\_\{j\}\\max\\\{0,s\_\{j\}t\_\{j\}\\\}=\\alpha\_\{1\}\+\\alpha\_\{2\}\. For each fixedt∈𝒯t\\in\\mathcal\{T\}, the number ofs∈𝒮ms\\in\{\\mathcal\{S\}\}\_\{m\}withV​\(s,t\)=uV\(s,t\)=uis exactly

Nu=∑α1,α2∈\{0,…,r/2\}α1\+α2=u\(m−r⌈\(m−r\)/2⌉−\(α1−α2\)\)​\(r/2α1\)​\(r/2α2\)\.N\_\{u\}\\;=\\;\\sum\_\{\\begin\{subarray\}\{c\}\\alpha\_\{1\},\\alpha\_\{2\}\\in\\\{0,\\dots,r/2\\\}\\\\ \\alpha\_\{1\}\+\\alpha\_\{2\}=u\\end\{subarray\}\}\\binom\{m\-r\}\{\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\}\\binom\{r/2\}\{\\alpha\_\{1\}\}\\binom\{r/2\}\{\\alpha\_\{2\}\}\.Indeed: pick theα1\\alpha\_\{1\}agreement positions among ther/2r/2coordinates wheretj=\+1t\_\{j\}=\+1\(\(r/2α1\)\\binom\{r/2\}\{\\alpha\_\{1\}\}ways\) and theα2\\alpha\_\{2\}agreement positions among ther/2r/2coordinates wheretj=−1t\_\{j\}=\-1\(\(r/2α2\)\\binom\{r/2\}\{\\alpha\_\{2\}\}ways\)\. The total\+1\+1/−1\-1imbalance ofssis then2​\(α1−α2\)\+2​β−\(m−r\)2\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\+2\\beta\-\(m\-r\), whereβ\\betais the number of\+1\+1entries ofsson the zero block oftt\. The constraints∈𝒮ms\\in\{\\mathcal\{S\}\}\_\{m\}requires this imbalance to lie in\{0,1\}\\\{0,1\\\}, which forcesβ=⌈\(m−r\)/2⌉−\(α1−α2\)\\beta=\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\(and is the unique integer solution in either parity ofm−rm\-r\), giving the\(m−r⌈\(m−r\)/2⌉−\(α1−α2\)\)\\binom\{m\-r\}\{\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\}factor\. By the symmetry ofVVunder coordinate permutations,Nu​\(t\)=NuN\_\{u\}\(t\)=N\_\{u\}does not depend ontt, hence\|\{\(s,t\):V​\(s,t\)=u\}\|=K​Nu\|\\\{\(s,t\):V\(s,t\)=u\\\}\|=K\\,N\_\{u\}\.

##### Assembling equation[11](https://arxiv.org/html/2607.05898#A3.E11)\.

Summing equation[12](https://arxiv.org/html/2607.05898#A3.E12)over the pairs\(s,t\)∈𝒮×𝒯\(s,t\)\\in\\mathcal\{S\}\\times\\mathcal\{T\}withV​\(s,t\)=uV\(s,t\)=u,

Pr⁡\[V=u\]≤eε​∑\(s,t\):V=uPr⁡\[S^=t\]\+M′−1M′​δ⋅\|\{\(s,t\):V=u\}\|eε\+M′−1\.\\Pr\[V=u\]\\;\\leq\\;\\frac\{e^\{\\varepsilon\}\\sum\_\{\(s,t\):V=u\}\\Pr\[\\widehat\{S\}=t\]\\;\+\\;\\tfrac\{M^\{\\prime\}\-1\}\{M^\{\\prime\}\}\\delta\\cdot\\bigl\|\\\{\(s,t\):V=u\\\}\\bigr\|\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\.The first sum equals∑t∈𝒯Pr⁡\[S^=t\]​Nu=Nu\\sum\_\{t\\in\\mathcal\{T\}\}\\Pr\[\\widehat\{S\}=t\]\\,N\_\{u\}=N\_\{u\}\(usingNu​\(t\)=NuN\_\{u\}\(t\)=N\_\{u\}and∑t∈𝒯Pr⁡\[S^=t\]=1\\sum\_\{t\\in\\mathcal\{T\}\}\\Pr\[\\widehat\{S\}=t\]=1\); the second count equalsK​NuKN\_\{u\}\. Hence

Pr⁡\[V=u\]≤Nu⋅eε\+M′−1M′​K​δeε\+M′−1=πε​\(u\),\\Pr\[V=u\]\\;\\leq\\;N\_\{u\}\\cdot\\frac\{e^\{\\varepsilon\}\+\\tfrac\{M^\{\\prime\}\-1\}\{M^\{\\prime\}\}K\\delta\}\{e^\{\\varepsilon\}\+M^\{\\prime\}\-1\}\\;=\\;\\pi\_\{\\varepsilon\}\(u\),proving equation[11](https://arxiv.org/html/2607.05898#A3.E11)\. Summing overu≥vu\\geq vgives the marginal upper tail

Pr⁡\[V≥v\]≤Pε​\(v\)\.\\Pr\[V\\geq v\]\\;\\leq\\;P\_\{\\varepsilon\}\(v\)\.\(13\)

##### Median bound equation[10](https://arxiv.org/html/2607.05898#A3.E10)\.

The eventMedian​\(\{V\(ℓ\)\}ℓ=1L\)≥v\\mathrm\{Median\}\(\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\)\\geq vimplies the existence of someJ⊆\[L\]J\\subseteq\[L\]with\|J\|=⌈L/2⌉\|J\|=\\lceil L/2\\rceilsuch thatV\(ℓ\)≥vV^\{\(\\ell\)\}\\geq vfor everyℓ∈J\\ell\\in J\. By independence and a union bound over the\(L⌈L/2⌉\)\\binom\{L\}\{\\lceil L/2\\rceil\}such subsets, together with equation[13](https://arxiv.org/html/2607.05898#A3.E13),

Pr⁡\(Median​\(\{V\(ℓ\)\}ℓ=1L\)≥v\)≤\(L⌈L/2⌉\)​Pε​\(v\)⌈L/2⌉\.\\Pr\\\!\\left\(\\mathrm\{Median\}\\\!\\left\(\\\{V^\{\(\\ell\)\}\\\}\_\{\\ell=1\}^\{L\}\\right\)\\geq v\\right\)\\;\\leq\\;\\binom\{L\}\{\\lceil L/2\\rceil\}P\_\{\\varepsilon\}\(v\)^\{\\lceil L/2\\rceil\}\.

##### Chernoff bound equation[9](https://arxiv.org/html/2607.05898#A3.E9)\.

Fixλ≥0\\lambda\\geq 0\. By equation[6](https://arxiv.org/html/2607.05898#A2.E6),

𝔼​\[eλ​V\(ℓ\)\]=∑u=0reλ​u​Pr⁡\[V\(ℓ\)=u\]≤∑u=0reλ​u​πε​\(u\)\.\\mathbb\{E\}\\\!\\left\[e^\{\\lambda V^\{\(\\ell\)\}\}\\right\]\\;=\\;\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\Pr\[V^\{\(\\ell\)\}=u\]\\;\\leq\\;\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\.By independence acrossℓ\\elland Markov’s inequality applied toeλ​∑ℓV\(ℓ\)e^\{\\lambda\\sum\_\{\\ell\}V^\{\(\\ell\)\}\},

Pr⁡\[1L​∑ℓ=1LV\(ℓ\)≥v\]≤e−λ​L​v​\(∑u=0reλ​u​πε​\(u\)\)L=exp⁡\(L​log⁡\(∑u=0reλ​u​πε​\(u\)\)−λ​L​v\)\.\\Pr\\\!\\left\[\\frac\{1\}\{L\}\\sum\_\{\\ell=1\}^\{L\}V^\{\(\\ell\)\}\\geq v\\right\]\\;\\leq\\;e^\{\-\\lambda Lv\}\\Bigg\(\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\\Bigg\)^\{\\\!L\}\\;=\\;\\exp\\\!\\left\(L\\log\\\!\\Big\(\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)\\Big\)\-\\lambda Lv\\right\)\.Optimizing overλ≥0\\lambda\\geq 0yields equation[1](https://arxiv.org/html/2607.05898#S4.E1)\. ∎

We now state a corollary showing that the upper bounds for median and mean statistic proven above is monotonic inε\\varepsilonand thus, to reject the hypothesisε≤εLB\\varepsilon\\leq\\varepsilon\_\{\\text\{LB\}\}, it is sufficient to evaluate the bound atε=εLB\\varepsilon=\\varepsilon\_\{\\text\{LB\}\}forδ<M′K\\delta<\\frac\{M^\{\\prime\}\}\{K\}\.

###### Corollary C\.3\(Monotonicity of audit bounds\)\.

Fix anyδ∈\[0,M′/K\)\\delta\\in\[0,M^\{\\prime\}/K\)\. Then the right\-hand sides of[Equation1](https://arxiv.org/html/2607.05898#S4.E1)and[Equation2](https://arxiv.org/html/2607.05898#S4.E2)in[Lemma4\.2](https://arxiv.org/html/2607.05898#S4.Thmtheorem2)are monotone non\-decreasing inε\\varepsilon\.

###### Proof\.

Fixδ∈\[0,M′/K\)\\delta\\in\[0,M^\{\\prime\}/K\)\. The pointwise bound factorises asπε​\(u\)=C​\(u\)⋅g​\(ε\)\\pi\_\{\\varepsilon\}\(u\)=C\(u\)\\cdot g\(\\varepsilon\), where

C​\(u\):=∑α1,α2∈\{0,…,r/2\}α1\+α2=u\(m−r⌈\(m−r\)/2⌉−\(α1−α2\)\)​\(r/2α1\)​\(r/2α2\)≥0C\(u\):=\\sum\_\{\\begin\{subarray\}\{c\}\\alpha\_\{1\},\\alpha\_\{2\}\\in\\\{0,\\dots,r/2\\\}\\\\ \\alpha\_\{1\}\+\\alpha\_\{2\}=u\\end\{subarray\}\}\\binom\{m\-r\}\{\\lceil\(m\-r\)/2\\rceil\-\(\\alpha\_\{1\}\-\\alpha\_\{2\}\)\}\\binom\{r/2\}\{\\alpha\_\{1\}\}\\binom\{r/2\}\{\\alpha\_\{2\}\}\\geq 0is independent ofε\\varepsilon, and

g​\(ε\):=eε\+aeε\+b,a:=M′−1M′​K​δ,b:=M′−1\.g\(\\varepsilon\):=\\frac\{e^\{\\varepsilon\}\+a\}\{e^\{\\varepsilon\}\+b\},\\qquad a:=\\frac\{M^\{\\prime\}\-1\}\{M^\{\\prime\}\}K\\delta,\\quad b:=M^\{\\prime\}\-1\.Differentiating givesg′​\(ε\)=eε​\(b−a\)\(eε\+b\)2g^\{\\prime\}\(\\varepsilon\)=\\dfrac\{e^\{\\varepsilon\}\(b\-a\)\}\{\(e^\{\\varepsilon\}\+b\)^\{2\}\}\. The conditionδ<M′/K\\delta<M^\{\\prime\}/Kis equivalent to

M′−1M′​K​δ<M′−1,i\.e\.,a<b,\\frac\{M^\{\\prime\}\-1\}\{M^\{\\prime\}\}K\\delta\\;<\\;M^\{\\prime\}\-1,\\quad\\text\{i\.e\.,\}\\quad a<b,sog′​\(ε\)\>0g^\{\\prime\}\(\\varepsilon\)\>0for allε≥0\\varepsilon\\geq 0\. Henceggis strictly increasing, andπε​\(u\)=C​\(u\)⋅g​\(ε\)\\pi\_\{\\varepsilon\}\(u\)=C\(u\)\\cdot g\(\\varepsilon\)is monotone non\-decreasing inε\\varepsilonfor every fixedu∈\{0,1,…,r\}u\\in\\\{0,1,\\dots,r\\\}\.

Median bound \([Equation10](https://arxiv.org/html/2607.05898#A3.E10)\)\.The upper tailPε​\(v\)=∑u=⌈v⌉rπε​\(u\)P\_\{\\varepsilon\}\(v\)=\\sum\_\{u=\\lceil v\\rceil\}^\{r\}\\pi\_\{\\varepsilon\}\(u\)is a non\-negative sum of monotone non\-decreasing functions, and is therefore itself monotone non\-decreasing inε\\varepsilon\. Raising to the power⌈L/2⌉\\lceil L/2\\rceiland multiplying by the positive constant\(L⌊L/2⌋\)\\binom\{L\}\{\\lfloor L/2\\rfloor\}both preserve monotonicity\.

Mean bound \([Equation9](https://arxiv.org/html/2607.05898#A3.E9)\)\.Fix anyλ≥0\\lambda\\geq 0\. The moment generating function∑u=0reλ​u​πε​\(u\)\\sum\_\{u=0\}^\{r\}e^\{\\lambda u\}\\pi\_\{\\varepsilon\}\(u\)is a non\-negative linear combination of\{πε​\(u\)\}u\\\{\\pi\_\{\\varepsilon\}\(u\)\\\}\_\{u\}, hence monotone non\-decreasing inε\\varepsilon\. Composing withlog\\log\(monotone\), multiplying byL\>0L\>0, subtracting theε\\varepsilon\-independent termλ​L​v\\lambda Lv, and exponentiating all preserve monotonicity\. Therefore, for each fixedλ≥0\\lambda\\geq 0, the function inside the infimum is monotone non\-decreasing inε\\varepsilon\. A pointwise infimum of monotone non\-decreasing functions is itself monotone non\-decreasing: forε1≤ε2\\varepsilon\_\{1\}\\leq\\varepsilon\_\{2\}and anyλ\\lambda,fλ​\(ε1\)≤fλ​\(ε2\)f\_\{\\lambda\}\(\\varepsilon\_\{1\}\)\\leq f\_\{\\lambda\}\(\\varepsilon\_\{2\}\), so taking the infimum overλ\\lambdaon both sides yieldsinfλfλ​\(ε1\)≤infλfλ​\(ε2\)\\inf\_\{\\lambda\}f\_\{\\lambda\}\(\\varepsilon\_\{1\}\)\\leq\\inf\_\{\\lambda\}f\_\{\\lambda\}\(\\varepsilon\_\{2\}\)\. This completes the proof\. ∎

## Appendix DDatasets, models, and auditor batching

This appendix gives the full data\-construction and model details for the two datasets described in[Section6](https://arxiv.org/html/2607.05898#S6)\.

### D\.1CIFAR\-100

##### Forget/retain construction\.

For CIFAR\-100\[Krizhevsky,[2009](https://arxiv.org/html/2607.05898#bib.bib16)\], we first split the original training set into a training portion \(90%\) and a validation portion \(10%\)\. From the training portion, we designate10%10\\%of the points as the forget set𝒟f\{\\mathcal\{D\}\}\_\{f\}\(4,5004\{,\}500points\), and use the remaining40,50040\{,\}500points as the retain set𝒟r\{\\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𝒟r\{\\mathcal\{D\}\}\_\{r\}and𝒟f\{\\mathcal\{D\}\}\_\{f\}into batches of sizeBB\.

##### Auditor batching\.

For uncertified unlearning algorithms we useB=1B=1, while for certified unlearning algorithms we useB=750B=750\. Accordingly, we use the*batchwise inclusion/exclusion*auditor \([Algorithm2](https://arxiv.org/html/2607.05898#alg2)\) for uncertified methods and the*joint sign\-vector*auditor \([Algorithm3](https://arxiv.org/html/2607.05898#alg3)\) for certified methods\. A discussion of why this split between auditor instantiations is appropriate is given in[SectionF\.4](https://arxiv.org/html/2607.05898#A6.SS4), with a more detailed study in[AppendixF](https://arxiv.org/html/2607.05898#A6)\.

##### Model\.

We use aTinyNetCIFAR100model, a lightweight CNN that attains around 55% accuracy on the CIFAR\-100 test set after400400epochs of training\. The architecture consists of two convolutional blocks, each containing two3×33\\times 3convolutional layers \(with 64 and 128 filters respectively\) with Group Normalization \(8 groups\) and ReLU activations, followed by2×22\\times 2max 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\.

### D\.2Shakespeare

##### Forget/retain construction\.

FollowingMcMahanet al\.\[[2017](https://arxiv.org/html/2607.05898#bib.bib18)\], 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 than22dialogue blocks are discarded, and for our experiments we randomly subsample300300roles\. 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 all300300roles\. The training data is then partitioned into a retain set𝒟r\{\\mathcal\{D\}\}\_\{r\}and a forget set𝒟f\{\\mathcal\{D\}\}\_\{f\}*at the role level*— each role is assigned entirely to one set, ensuring zero character overlap between𝒟r\{\\mathcal\{D\}\}\_\{r\}and𝒟f\{\\mathcal\{D\}\}\_\{f\}\. Roles are randomly shuffled and greedily assigned to𝒟f\{\\mathcal\{D\}\}\_\{f\}until approximately10%10\\%of training characters are accumulated, yielding3333forget roles \(𝒟f\{\\mathcal\{D\}\}\_\{f\},135,300135\{,\}300characters,∼10\.0%\{\\sim\}10\.0\\%of train\) and267267retain roles \(𝒟r\{\\mathcal\{D\}\}\_\{r\},1,221,3631\{,\}221\{,\}363characters,∼90\.0%\{\\sim\}90\.0\\%of train\)\.

For unlearning experiments, the forget set𝒟f\{\\mathcal\{D\}\}\_\{f\}is further partitioned intoB=400B=400equal batches: the dialogue blocks from all forget roles are shuffled at the block level \(preserving within\-block coherence\) and split into400400contiguous chunks𝒟f,1,…,𝒟f,400\{\\mathcal\{D\}\}\_\{f,1\},\\ldots,\{\\mathcal\{D\}\}\_\{f,400\}\. For each run,200200forget chunks are sampled uniformly at random from the400400\. Each chunk and the retain set are independently converted to sliding\-window samples of length8080characters, wherexxis the input sequence andyyis 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\.

##### Auditor batching\.

On Shakespeare we evaluate only uncertified unlearning methods \(gradient ascent, interleaved ascent–descent, fine\-tuning on retain, and Hessian\-based unlearning ofZhanget al\.\[[2025](https://arxiv.org/html/2607.05898#bib.bib6)\]\); we therefore use the*batchwise inclusion/exclusion*auditor \([Algorithm2](https://arxiv.org/html/2607.05898#alg2)\) throughout, as on CIFAR\-100\.

##### Model\.

The model is a22\-layer stacked character\-level LSTM followingMcMahanet al\.\[[2017](https://arxiv.org/html/2607.05898#bib.bib18)\]\. Each input character is embedded into an88\-dimensional space, processed through two LSTM layers each with256256hidden units, and projected to a softmax output layer over the vocabulary of\|𝒱\|=100\|\{\\mathcal\{V\}\}\|=100characters\. The full model has825,220825\{,\}220parameters and is trained with an unroll length ofL=80L=80characters\. For the Shakespeare dataset, the scoreϕ​\(f​\(x\)y\)\\phi\(f\(x\)\_\{y\}\)for a sample\(x,y\)\(x,y\)is the mean per\-character cross\-entropy loss−1T​∑t=1Tlog⁡pθ​\(yt∣x≤t\)\-\\tfrac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\log p\_\{\\theta\}\(y\_\{t\}\\mid x\_\{\\leq t\}\)assigned by the modelff, whereT=80T=80is the sequence length\.

## Appendix ERobustness 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ϕ​\(f​\(x\)y\)\\phi\(f\(x\)\_\{y\}\)used throughout the paper with the per\-example cross\-entropy loss and recompute the lower bounds \([SectionE\.1](https://arxiv.org/html/2607.05898#A5.SS1)\)\. Second, we replace the mean aggregation of overlap scores with the median \([SectionE\.2](https://arxiv.org/html/2607.05898#A5.SS2)\)\. In both cases the directional trends with respect to the support sizerrare preserved, indicating that our reported bounds are not artefacts of a particular score function or aggregation rule\.

### E\.1Logit score versus cross\-entropy score

Table 3:Lower bounds from logit score versus cross\-entropy loss, across pure ascent and interleaved ascent–descent \(IDA\) at varyingqq, for both uniform \(uni\.\) and adversarial \(adv\.\) splits\.[Table3](https://arxiv.org/html/2607.05898#A5.T3)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\) atq∈\{1,2,4\}q\\in\\\{1,2,4\\\}on both the uniform and adversarial splits\. The two scores yield similar directional trends inrr, with the logit score giving slightly tighter bounds in most settings\.

### E\.2Mean versus median aggregation

Table 4:Lower bounds from mean versus median aggregation of overlap scores, across pure ascent and interleaved ascent–descent \(IDA\) at varyingqq, for both uniform \(uni\.\) and adversarial \(adv\.\) splits\.[Table4](https://arxiv.org/html/2607.05898#A5.T4)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 onrrnoted in[AppendixF](https://arxiv.org/html/2607.05898#A6)— the lower bound first increases withrrand then decreases\.

## Appendix FVarying batch sizesBB\(and equivalentlymm\) and reported support sizerr

This appendix gives the detailed analysis of how the lower boundεLB\\varepsilon\_\{\\mathrm\{LB\}\}depends on the number of forget batchesmm\(equivalently the audit batch sizeBB, sincem=\|𝒟f\|/Bm=\|\{\\mathcal\{D\}\}\_\{f\}\|/B\) and the reported support sizerr\. The compact takeaways are summarised in[Remark4\.3](https://arxiv.org/html/2607.05898#S4.Thmtheorem3)\.

### F\.1Maximum attainable bound under perfect prediction \(inmm\)

The maximum lower bound onε\\varepsilonimplied by a perfect prediction — overlap scoremmwith support sizer=mr=m— grows withmm\. For instance, applying[Lemma4\.1](https://arxiv.org/html/2607.05898#S4.Thmtheorem1)withΓ=10\\Gamma=10independent runs yieldsεLB≥4\.00\\varepsilon\_\{\\mathrm\{LB\}\}\\geq 4\.00atm=6m=6, butεLB≥67\.87\\varepsilon\_\{\\mathrm\{LB\}\}\\geq 67\.87atm=100m=100\. Intuitively, identifying the correct sign vector is harder whenmmis large, since the number of candidates\|𝒮m\|\|\{\\mathcal\{S\}\}\_\{m\}\|grows exponentially inmm\. A perfect prediction at largemmtherefore reflects much stronger distinguishing power, and certifies a correspondingly larger lower bound onε\\varepsilon\.

### F\.2Choice of audit batch sizeBB

Sincem=\|𝒟f\|/Bm=\|\{\\mathcal\{D\}\}\_\{f\}\|/B, smaller batches enlarge the hypothesis space𝒮m\{\\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 smallBB\(largemm\) is preferable\. Certified algorithms have tight guarantees and weak per\-batch signal; here, largemmleaves the adversary unable to beat random guessing among exponentially many candidates, and one must use a largerBB\(smallermm\) to obtain any nonzero bound\. In addition, as discussed in[Section5](https://arxiv.org/html/2607.05898#S5), we use the*joint sign vector*prediction for certified unlearning algorithms, which is precisely why having a small batch size \(largemm\) is computationally infeasible\. Thus, in[Section7](https://arxiv.org/html/2607.05898#S7)we stick toB=1B=1for uncertified algorithms andB=750B=750for certified algorithms on CIFAR\-100\.

### F\.3Dependence on the support sizerr

The support sizerrlets the auditor abstain on uncertain batches, improving the overlap on those it does report\. Givenmm, the maximum lower bound*conditional on perfect overlap*grows withrr: atm=100m=100, perfect overlap yieldsεLB≥40\.83\\varepsilon\_\{\\mathrm\{LB\}\}\\geq 40\.83atr=60r=60, rising toεLB≥67\.87\\varepsilon\_\{\\mathrm\{LB\}\}\\geq 67\.87atr=100r=100\. In practice, the empirical lower bound traces an inverted\-U inrr\. It first increases for two compounding reasons: the maximum attainable bound at perfect overlap grows withrr, and the auditor’s reported predictions remain accurate while there are still confident batches to report\. Asrrgrows 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[Table5](https://arxiv.org/html/2607.05898#A6.T5), we plot the lower bound againstr⋅Br\\cdot B\(equivalently,4500​r/m4500\\,r/m, sincem=\|𝒟f\|/B=4500/Bm=\|\{\\mathcal\{D\}\}\_\{f\}\|/B=4500/B\) for varying batch sizesB∈\{1,10,100,500\}B\\in\\\{1,10,100,500\\\}on the ascent\-on\-forget unlearning algorithm\. For bothB=1B=1andB=10B=10, the lower bound first increases withrrand then decreases\. This inverted\-U effect is more pronounced at smaller batch sizes \(largermm\)\.

Table 5:Comparison across batch sizes for the ascent on forget set setting\.
### F\.4Batchwise 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\[Koloskovaet al\.,[2025](https://arxiv.org/html/2607.05898#bib.bib4)\]and R2D\[Mu and Klabjan,[2025](https://arxiv.org/html/2607.05898#bib.bib7)\], 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 ofr/2r/2\. We therefore use the*joint sign\-vector*predictor, which calibrates a separate Gaussian for every candidateS~∈𝒮m\\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\|𝒮m\|\|\{\\mathcal\{S\}\}\_\{m\}\|candidates, we restrict to smallmm— concretely, batch sizeB=750B=750givingm=6m=6forget batches\. For uncertified methods, the per\-batch signal is strong enough that this issue does not arise; we obtain the strongest bounds at largemm, where\|𝒮m\|\|\{\\mathcal\{S\}\}\_\{m\}\|is astronomically large and enumeration is infeasible, and so default to the*batchwise inclusion/exclusion*predictor\.

##### Experiment with batchwise inclusion/exclusion\.

We also evaluated the*batchwise inclusion/exclusion*auditor on the uncertified variant of model clipping, withC2=5C\_\{2\}=5andσ=10−4\\sigma=10^\{\-4\}as in[Section7\.1](https://arxiv.org/html/2607.05898#S7.SS1)\. We used batch sizesB=750B=750andB=100B=100, withr=6r=6andr=40r=40, respectively\. The resulting lower bounds were only0\.1120\.112and0\.0070\.007even 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\.

## Appendix GUnlearning algorithms: experimental details

This appendix gives the full setup for each unlearning algorithm audited in[Section7](https://arxiv.org/html/2607.05898#S7)\.[SectionsG\.1](https://arxiv.org/html/2607.05898#A7.SS1)and[G\.2](https://arxiv.org/html/2607.05898#A7.SS2)cover the certified algorithms;[SectionsG\.3](https://arxiv.org/html/2607.05898#A7.SS3),[G\.4](https://arxiv.org/html/2607.05898#A7.SS4),[G\.5](https://arxiv.org/html/2607.05898#A7.SS5),[G\.6](https://arxiv.org/html/2607.05898#A7.SS6)and[G\.7](https://arxiv.org/html/2607.05898#A7.SS7)cover the four heuristic algorithms together with their base\-training configurations\.

### G\.1Model clipping

#### G\.1\.1Algorithm

Letx^\\hat\{x\}denote the trained model produced by𝒜\{\\mathcal\{A\}\}prior to unlearning\. The unlearning procedure ofKoloskovaet al\.\[[2025](https://arxiv.org/html/2607.05898#bib.bib4)\]consists of two phases\.

##### Phase 1: noisy projection\.

Fort=0,1,…,Tnoisy−1t=0,1,\\dots,T\_\{\\mathrm\{noisy\}\}\-1, the iterate is updated by

x0=x^\+ξ0,xt\+1=ΠC2​\(xt−γ​\(gt\+λ​xt\)\)\+ξt\+1,\\displaystyle 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\},\(14\)whereΠC2\\Pi\_\{C\_\{2\}\}is projection onto theℓ2\\ell\_\{2\}\-ball of radiusC2C\_\{2\},gtg\_\{t\}is the gradient of the loss on the retain set evaluated atxtx\_\{t\},γ\\gammais the step size,λ\\lambdais theℓ2\\ell\_\{2\}regularisation strength, and the noise satisfiesξ0∼𝒩​\(0,σ02​𝕀d\)\\xi\_\{0\}\\sim\{\\mathcal\{N\}\}\(0,\\sigma\_\{0\}^\{2\}\{\\mathbb\{I\}\}\_\{d\}\)andξt\+1∼𝒩​\(0,σ2​𝕀d\)\\xi\_\{t\+1\}\\sim\{\\mathcal\{N\}\}\(0,\\sigma^\{2\}\{\\mathbb\{I\}\}\_\{d\}\)fort≥0t\\geq 0\. The number of noisy stepsTnoisyT\_\{\\mathrm\{noisy\}\}is set by Theorem 4\.2 ofKoloskovaet al\.\[[2025](https://arxiv.org/html/2607.05898#bib.bib4)\]so that the iteratexTnoisyx\_\{T\_\{\\mathrm\{noisy\}\}\}satisfies the target\(ε,δ\)\(\\varepsilon,\\delta\)guarantee\.

##### Phase 2: fine\-tuning\.

Starting fromxTnoisyx\_\{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\.

#### G\.1\.2Hyperparameters

As chosen inKoloskovaet al\.\[[2025](https://arxiv.org/html/2607.05898#bib.bib4)\], we train for a total of400400epochs with a training batch size of128128\(317317optimisation steps per epoch\), and unlearning is applied for a total of5050epochs\. We apply a one\-cycle learning schedule with maximum learning rate10−310^\{\-3\}and regulariser5×10−45\\times 10^\{\-4\}\. For unlearning Phase 1, we use a constant learning rate of10−310^\{\-3\}for the noisy steps; for Phase 2 we use a one\-cycle schedule with maximum0\.10\.1and regulariser5×10−45\\times 10^\{\-4\}\. The initial clipping radius just before unlearning starts isC0=30C\_\{0\}=30\. The same regulariser is applied during the retain\-set fine\-tuning phase\. The sweep over the certified\(ε,C2,σ\)\(\\varepsilon,C\_\{2\},\\sigma\)grid is reported in[Table6](https://arxiv.org/html/2607.05898#A7.T6)\.

Table 6:Lower bounds for model clipping under uniform/adversarial CIFAR\-100 splits, evaluated at the first noisy step and after5050epochs\.
#### G\.1\.3Uncertified variant of model clipping

For the uncertified experiment of[Figure1\(a\)](https://arxiv.org/html/2607.05898#S7.F1.sf1)we setC2=5C\_\{2\}=5andσ=10−4\\sigma=10^\{\-4\}, terminate the clipping/noise\-addition phase after1010epochs \(3,1703\{,\}170update steps\), and then fine\-tune as above\. The ratioC2/σC\_\{2\}/\\sigmais far larger than what Theorem 4\.2 ofKoloskovaet al\.\[[2025](https://arxiv.org/html/2607.05898#bib.bib4)\]admits, so no certified\(ε,δ\)\(\\varepsilon,\\delta\)guarantee applies; we still reportεLB\\varepsilon\_\{\\mathrm\{LB\}\}at every stepttas defined above\. To obtain tighter bounds in this regime we useL=500L=500runs\. For context,11epoch corresponds to317317steps in this setup, so[Figure1\(a\)](https://arxiv.org/html/2607.05898#S7.F1.sf1)effectively covers up to roughly22epochs\.

### G\.2Rewind\-to\-delete

We takeT=40T=40training epochs andK=5K=5rewind epochs\. FollowingMu and Klabjan \[[2025](https://arxiv.org/html/2607.05898#bib.bib7), Theorem 3\.1\], the unlearned modelθK′′\\theta^\{\\prime\\prime\}\_\{K\}is obtained by loading the checkpointθT−K′\\theta^\{\\prime\}\_\{T\-K\}and then training forKKepochs on the retain set; final\-step Gaussian noise of scaleσ\\sigmais added to ensure\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishability between the trained modelθT′\\theta^\{\\prime\}\_\{T\}andθK′′\\theta^\{\\prime\\prime\}\_\{K\}\. Since we considerε\>1\\varepsilon\>1, the noise parameterσ\\sigma777To computeσ\\sigma, one needs the smoothness constantLLand a uniform bound on the gradientGG, both estimated followingMu and Klabjan \[[2025](https://arxiv.org/html/2607.05898#bib.bib7)\]\.must satisfy

Φ​\(−ε​σΔ\+Δ2​σ\)−eε​Φ​\(−ε​σΔ−Δ2​σ\)≤δ,\\Phi\\\!\\left\(\-\\tfrac\{\\varepsilon\\sigma\}\{\\Delta\}\+\\tfrac\{\\Delta\}\{2\\sigma\}\\right\)\-e^\{\\varepsilon\}\\,\\Phi\\\!\\left\(\-\\tfrac\{\\varepsilon\\sigma\}\{\\Delta\}\-\\tfrac\{\\Delta\}\{2\\sigma\}\\right\)\\leq\\delta,whereΦ\\Phiis the standard Gaussian CDF andΔ=‖θT′−θK′′‖\\Delta=\\\|\\theta^\{\\prime\}\_\{T\}\-\\theta^\{\\prime\\prime\}\_\{K\}\\\|is the sensitivity\. BothTTandKKare kept small because the resultingσ\\sigmagrows exponentially inTTandKK\. 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 around4%4\\%\. In our auditing setup, we use a learning rate of0\.010\.01\. We swept over\{0\.1,0\.01,0\.001\}\\\{0\.1,0\.01,0\.001\\\}; the resultingεLB\\varepsilon\_\{\\mathrm\{LB\}\}values were all small and did not differ meaningfully across the sweep, so we report results for0\.010\.01throughout\.

### G\.3Base training configurations for uncertified methods

##### Shakespeare\.

The base model is trained for1515epochs using SGD with learning rate0\.10\.1, batch size256256, and gradient clipping of1\.01\.0, with no weight decay or learning\-rate scheduling\. The resulting accuracy is roughly0\.530\.53, in line with\[McMahanet al\.,[2017](https://arxiv.org/html/2607.05898#bib.bib18)\]\. Unlearning runs for a total of88epochs; the retain\-set fine\-tuning phase uses learning rate0\.10\.1\.

##### CIFAR\-100\.

For Hessian\-based unlearning, we use a cosine scheduler with learning rate0\.10\.1followingZhanget al\.\[[2025](https://arxiv.org/html/2607.05898#bib.bib6)\], training for a total of400400epochs\. For the remaining three uncertified methods \(IDA, ascent on the forget set, pure fine\-tuning\), the training configuration matches[SectionG\.1](https://arxiv.org/html/2607.05898#A7.SS1); the retain\-set fine\-tuning phase reverts to a one\-cycle schedule with maximum learning rate0\.10\.1\.

### G\.4Hessian\-based unlearning

##### Update rule\.

Letgfg\_\{f\}denote the forget\-set gradient andHHthe \(regularised\) Hessian\. The unlearning step is

θ↦θ−H−1​gf\+ξ,ξ∼𝒩​\(0,σ2​𝕀\),\\theta\\;\\mapsto\\;\\theta\-H^\{\-1\}g\_\{f\}\+\\xi,\\qquad\\xi\\sim\{\\mathcal\{N\}\}\(0,\\sigma^\{2\}\{\\mathbb\{I\}\}\),\(15\)whereσ\\sigmais the final noise scale and the Gaussian perturbation is added to every parameter\.

##### LiSSA approximation\.

As inZhanget al\.\[[2025](https://arxiv.org/html/2607.05898#bib.bib6)\], we approximate the inverse\-Hessian–vector productH−1​gH^\{\-1\}gvia the LiSSA algorithm ofAgarwalet al\.\[[2017](https://arxiv.org/html/2607.05898#bib.bib51)\], avoiding explicit construction of the Hessian\. The LiSSA approximation is governed by four hyperparameters — depth parameterss1s\_\{1\}ands2s\_\{2\}, thescale, 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\.

##### Depth parameterss1s\_\{1\}ands2s\_\{2\}\.

The parameters1s\_\{1\}controls the number of independent LiSSA estimation runs whose results are averaged to reduce variance, whiles2s\_\{2\}controls the depth of the Neumann\-series recursion within each run, governing convergence to the true Newton direction\.

##### Scale\.

Thescaleparameter 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\.

##### 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\.

##### Weight decay\.

The weight decay enters as a squaredL2L\_\{2\}regularisation term added to the loss during the Hessian computation, effectively shifting the Hessian byλ​𝑰\\lambda\{\\bm\{I\}\}and improving its conditioning for inversion\. Crucially, it is applied only in the Hessian computation and not in the gradientgg, so that the Newton update approximatesH−1​gH^\{\-1\}gwhereHHis the regularised Hessian butggis the unregularised retain gradient\.

##### Per\-dataset values\.

For both datasets we set the weight decay to5×10−45\\times 10^\{\-4\}\. For CIFAR\-100 we uses1=10s\_\{1\}=10,s2=1000s\_\{2\}=1000,scale=1000\\texttt\{scale\}=1000, and an unlearning batch size of1010\. For Shakespeare we uses1=5s\_\{1\}=5,s2=700s\_\{2\}=700,scale=5000\\texttt\{scale\}=5000, and an unlearning batch size of256256\(matching the training batch size\);s1s\_\{1\}ands2s\_\{2\}are chosen slightly smaller for Shakespeare for computational efficiency\.

##### Final noise\.

After the Hessian\-based step, Gaussian noise of standard deviation10−310^\{\-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\.

##### 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 to5×10−35\\times 10^\{\-3\}and10−210^\{\-2\}respectively in[Table7](https://arxiv.org/html/2607.05898#A7.T7)\. Trends are along expected lines\. Although, we see the computed lower bound gets smaller with noise, the test accuracy also reduces\.

Table 7:ε\\varepsilonlower bound with noise\. R/F/T denotes retain, forget and test accuracy

### G\.5Interleaved descent–ascent \(IDA\)

##### Update rule\.

Lettinggtrg\_\{t\}^\{r\}andgtfg\_\{t\}^\{f\}denote the retain\- and forget\-loss gradients at steptt, the IDA update for the firstEfE\_\{f\}epochs is

xt\+1=xt−ηt​\(gtr−λ​1​\{t≡0\(modq\+1\)\}​gtf\),x\_\{t\+1\}=x\_\{t\}\-\\eta\_\{t\}\\bigl\(g\_\{t\}^\{r\}\-\\lambda\\,\\mathbf\{1\}\\\{t\\equiv 0\\\!\\\!\\pmod\{q\+1\}\\\}\\,g\_\{t\}^\{f\}\\bigr\),\(16\)so that the interleaved step \(with the forget\-gradient term active\) fires once perq\+1q\+1updates and the remainingqqupdates within each cycle reduce to plain retain descentxt\+1=xt−ηt​gtrx\_\{t\+1\}=x\_\{t\}\-\\eta\_\{t\}g\_\{t\}^\{r\}\. AfterEfE\_\{f\}epochs, only the latter \(plain retain descent\) is used\.

##### CIFAR\-100\.

We fixλ=0\.75\\lambda=0\.75, varyq∈\{1,2,4\}q\\in\\\{1,2,4\\\}, and setEf=10E\_\{f\}=10\. The learning rate is held constant at10−310^\{\-3\}during the interleaved phase, and reverts to a one\-cycle schedule with maximum0\.10\.1during the retain\-set fine\-tuning phase\.

##### Shakespeare\.

We varyq∈\{1,2,4\}q\\in\\\{1,2,4\\\},Ef∈\{5,7\}E\_\{f\}\\in\\\{5,7\\\}, andλ∈\{0\.5,1\.0,1\.5\}\\lambda\\in\\\{0\.5,1\.0,1\.5\\\}\. The learning rate is held constant at0\.050\.05during the interleaved phase and held constant at 0\.1 during the retain finetuning phase\.

### G\.6Ascent on the forget set

##### Update rule\.

The unlearning phase performs gradient ascent on the forget set,

xt\+1=xt\+ηt​gtf,x\_\{t\+1\}=x\_\{t\}\+\\eta\_\{t\}\\,g\_\{t\}^\{f\},\(17\)wheregtfg\_\{t\}^\{f\}is the gradient of the forget loss at steptt\. After a fixed number of epochs \(2 for both CIFAR\-100 and Shakespeare\), the algorithm switches to plain retain\-set fine\-tuning\.

##### CIFAR\-100\.

The ascent learning rate is set to10−310^\{\-3\}during the unlearning phase, reverting to a one\-cycle schedule with maximum0\.10\.1during the retain\-set fine\-tuning phase\.

##### Shakespeare\.

The ascent learning rate is held constant at0\.050\.05during the unlearning phase and held at 0\.1 during the retain finetuning phase identical to the rate for interleaved ascent\-descent\.

### G\.7Pure 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 withC=C2=∞C=C\_\{2\}=\\inftyandσ=0\\sigma=0\. Learning\-rate schedules match the corresponding retain\-set fine\-tuning phases described in[SectionG\.3](https://arxiv.org/html/2607.05898#A7.SS3)\.

## Appendix HConvex unlearning: auditor and hyper\-parameter details

###### Definition H\.1\(\(ε,δ\)\(\\varepsilon,\\delta\)\-certified convex unlearning\)\.

Given a dataset𝒟\{\\mathcal\{D\}\}of sizenptn\_\{\\mathrm\{pt\}\}and a forget set𝒟f⊆𝒟\{\\mathcal\{D\}\}\_\{f\}\\subseteq\{\\mathcal\{D\}\}of sizemptm\_\{\\mathrm\{pt\}\}, let𝒟r:=𝒟∖𝒟f\{\\mathcal\{D\}\}\_\{r\}:=\{\\mathcal\{D\}\}\\setminus\{\\mathcal\{D\}\}\_\{f\}\. An unlearning algorithm𝒰\{\\mathcal\{U\}\}is an\(ε,δ\)\(\\varepsilon,\\delta\)\-certified convex unlearning algorithm for𝒜\{\\mathcal\{A\}\}if𝒰​\(𝒟f,𝒜​\(𝒟\),S​\(𝒟\)\)\{\\mathcal\{U\}\}\(\{\\mathcal\{D\}\}\_\{f\},\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\),S\(\{\\mathcal\{D\}\}\)\)and𝒰​\(∅,𝒜​\(𝒟r\),S​\(𝒟r\)\)\{\\mathcal\{U\}\}\(\\emptyset,\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\_\{r\}\),S\(\{\\mathcal\{D\}\}\_\{r\}\)\)are\(ε,δ\)\(\\varepsilon,\\delta\)\-indistinguishable\.

This appendix gives the auditor pipeline, the Perturbed Newton unlearning algorithm ofSekhariet al\.\[[2021](https://arxiv.org/html/2607.05898#bib.bib12), Algorithm 1\], the cubic and logistic loss constructions, and the hyper\-parameter sweep used in[Section7](https://arxiv.org/html/2607.05898#S7)\.

### H\.1Auditor pipeline

We adapt the pairwise auditor of[Section5](https://arxiv.org/html/2607.05898#S5.SS0.SSS0.Px3)\(Nasret al\.,[2021](https://arxiv.org/html/2607.05898#bib.bib8)\-style\) to the convex setting, with two changes\. First, in line with[DefinitionH\.1](https://arxiv.org/html/2607.05898#A8.Thmtheorem1), the auditor distinguishes the unlearned model produced from a non\-empty forget set,𝒰​\(𝒟f,𝒜​\(𝒟\),S​\(𝒟\)\)\{\\mathcal\{U\}\}\(\{\\mathcal\{D\}\}\_\{f\},\{\\mathcal\{A\}\}\(\{\\mathcal\{D\}\}\),S\(\{\\mathcal\{D\}\}\)\), against the model produced from an empty forget set,𝒰​\(∅,𝒜​\(𝒟r\),S​\(𝒟r\)\)\{\\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Γ=50\\Gamma=50independent models under each setting, fit Gaussian distributions𝒩​\(μr,Σr\)\\mathcal\{N\}\(\\mu\_\{r\},\\Sigma\_\{r\}\)and𝒩​\(μf,Σf\)\\mathcal\{N\}\(\\mu\_\{f\},\\Sigma\_\{f\}\)to the resulting weight vectors, and at evaluation draw2​L2Ltest 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[Equation3](https://arxiv.org/html/2607.05898#A1.E3)to obtainεLB\\varepsilon\_\{\\mathrm\{LB\}\}\. The null hypothesisH0:ε≤εLBH\_\{0\}:\\varepsilon\\leq\\varepsilon\_\{\\mathrm\{LB\}\}is then rejected with probability at mostζ\\zeta\.

We additionally compute a second lower bound,εLB\\varepsilon\_\{\\mathrm\{LB\}\}, by instantiating[Algorithm1](https://arxiv.org/html/2607.05898#alg1)withm=2m=2andr=2r=2, so that a per\-run overlap score of22denotes a correct prediction and0an incorrect one\. The induced mechanismℳ\{\\mathcal\{M\}\}is\(ε,δ\)\(\\varepsilon,\\delta\)\-DP by post\-processing, and no division by22is needed since no transitivity step is used\.

##### Why MSE is excluded\.

Mean squared error is somewhat degenerate in this context because its Hessian is constant\. Consequently, in Algorithm 1 ofSekhariet al\.\[[2021](https://arxiv.org/html/2607.05898#bib.bib12)\], 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\.

### H\.2Cubic loss in one dimension

We instantiate the cubic loss in dimensiond=1d=1, sow,z∈ℝw,z\\in\\mathbb\{R\}\. The pointwise loss is

ℓ​\(w;z\)=λ02​w2\+M6​w3−z​w,\\ell\(w;z\)=\\tfrac\{\\lambda\_\{0\}\}\{2\}w^\{2\}\+\\tfrac\{M\}\{6\}w^\{3\}\-zw,\(18\)constrained to the box\|w\|≤B\|w\|\\leq B, on which the loss isμ\\mu\-strongly convex withμ=λ0−M​B\\mu=\\lambda\_\{0\}\-MB\. We place thenptn\_\{\\mathrm\{pt\}\}retain points atz=0z=0and themptm\_\{\\mathrm\{pt\}\}forget points atz=−Rz=\-R, whereR\>0R\>0is a data\-radius parameter\. Under this construction, the retain\-only ERM has closed\-form solutionw^r=0\\hat\{w\}\_\{r\}=0, while the forget points exert a constant gradient pull of magnitudeRR, pushing the unlearned weightw^f\\hat\{w\}\_\{f\}as far fromw^r\\hat\{w\}\_\{r\}as the box constraint allows\. In our experiments we setM=0\.005M=0\.005,B=2\.5B=2\.5, andR=10\.0R=10\.0; the full hyper\-parameter sweep over\(λ0,M,B,R\)\(\\lambda\_\{0\},M,B,R\)is given below\.

### H\.3Hyper\-parameter selection

Letℓ​\(w;z\)\\ell\(w;z\)denote the pointwise loss at samplezz, and let𝒟=𝒟r∪𝒟f\{\\mathcal\{D\}\}=\{\\mathcal\{D\}\}\_\{r\}\\cup\{\\mathcal\{D\}\}\_\{f\}be the full training set, where𝒟r\{\\mathcal\{D\}\}\_\{r\}and𝒟f\{\\mathcal\{D\}\}\_\{f\}are the retain and forget sets respectively\.

Let

w^r=arg​minw​∑z∈𝒟rℓ​\(w;z\)\\hat\{w\}\_\{r\}\\;=\\;\\operatorname\*\{arg\\,min\}\_\{w\}\\sum\_\{z\\in\{\\mathcal\{D\}\}\_\{r\}\}\\ell\(w;z\)denote the \(noiseless\) retain\-only ERM, and letw^f\\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 ofSekhariet al\.\[[2021](https://arxiv.org/html/2607.05898#bib.bib12), Eq\. 8\]on the forget set𝒟f\{\\mathcal\{D\}\}\_\{f\}\(with the Hessian evaluated on the retain set\)\. In particular,w^f\\hat\{w\}\_\{f\}is*not*the model produced by training alone; it is the post\-unlearning weight before addition of noise\.Sekhariet al\.\[[2021](https://arxiv.org/html/2607.05898#bib.bib12), Lemma 3\]bounds

‖w^r−w^f‖≤2​M​m2​L2μ3​n2,\\bigl\\\|\\hat\{w\}\_\{r\}\-\\hat\{w\}\_\{f\}\\bigr\\\|\\;\\leq\\;\\frac\{2Mm^\{2\}L^\{2\}\}\{\\mu^\{3\}n^\{2\}\},whenℓ​\(⋅\)\\ell\(\\cdot\)isμ\\mu\-strongly convex,LL\-Lipschitz, andMM\-Hessian\-Lipschitz inww\. Our objective is to choose hyper\-parameters that make the empirical‖w^r−w^f‖\\\|\\hat\{w\}\_\{r\}\-\\hat\{w\}\_\{f\}\\\|as close to this theoretical bound as possible, i\.e\. that drive the ratio

ρ:=‖w^r−w^f‖empirical2​M​m2​L2/\(μ3​n2\)\\rho\\;:=\\;\\frac\{\\\|\\hat\{w\}\_\{r\}\-\\hat\{w\}\_\{f\}\\\|\_\{\\text\{empirical\}\}\}\{2Mm^\{2\}L^\{2\}/\(\\mu^\{3\}n^\{2\}\)\}toward11, since a value close to11indicates that Lemma 3 is empirically tight on the chosen problem instance\. While the cubic loss typically yields values ofρ\\rhoaround0\.20\.2, the logistic loss yields values ofρ\\rhoaround3×10−53\\times 10^\{\-5\}, which possibly explains why the lower bound is so low\.

### H\.4Placement of retain and forget points

#### H\.4\.1Cubic loss\.

We instantiate the cubic loss in dimensiond=1d=1, sow,z∈ℝw,z\\in\\mathbb\{R\}throughout this subsection\. We construct𝒟=𝒟r∪𝒟f\{\\mathcal\{D\}\}=\{\\mathcal\{D\}\}\_\{r\}\\cup\{\\mathcal\{D\}\}\_\{f\}as follows\. The retain set𝒟r\{\\mathcal\{D\}\}\_\{r\}consists ofnnpoints placed at the origin,

𝒟r=\{\(zi,yi\)\}i=1n,zi=0,yi=0,\{\\mathcal\{D\}\}\_\{r\}=\\bigl\\\{\(z\_\{i\},y\_\{i\}\)\\bigr\\\}\_\{i=1\}^\{n\},\\qquad z\_\{i\}=0,\\quad y\_\{i\}=0,and the forget set𝒟f\{\\mathcal\{D\}\}\_\{f\}consists ofmmpoints placed at−R\-R,

𝒟f=\{\(zi,yi\)\}i=1m,zi=−R,yi=0,\{\\mathcal\{D\}\}\_\{f\}=\\bigl\\\{\(z\_\{i\},y\_\{i\}\)\\bigr\\\}\_\{i=1\}^\{m\},\\qquad z\_\{i\}=\-R,\\quad y\_\{i\}=0,whereR\>0R\>0is the data\-radius parameter\. All labels are zero because the cubic loss

f​\(w,z\)=λ02​w2\+M6​w3−z​wf\(w,z\)\\;=\\;\\tfrac\{\\lambda\_\{0\}\}\{2\}\\,w^\{2\}\\;\+\\;\\tfrac\{M\}\{6\}\\,w^\{3\}\\;\-\\;z\\,wdoes not depend on labels\. Under this construction, the retain\-only ERM admits the closed\-form solutionw^r=0\\hat\{w\}\_\{r\}=0, since the retain gradientλ0​w\+M2​w2\\lambda\_\{0\}w\+\\tfrac\{M\}\{2\}w^\{2\}vanishes atw=0w=0\.

The retain points are placed at the origin so thatw^r=0\\hat\{w\}\_\{r\}=0provides a clean reference\. The forget points are placed at−R\-Rso as to maximise their gradient contribution to the full\-data ERM: from

∂f​\(w,z\)∂w\|z=−R=λ0​w\+M2​w2\+R,\\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 magnitudeRRonwwtoward\+B\+B, pushing the unlearned weightw^f\\hat\{w\}\_\{f\}as far fromw^r=0\\hat\{w\}\_\{r\}=0as the box constraint\|w\|≤B\|w\|\\leq Ballows, and producing the tightest empirical Lemma 3 ratio\.

For the cubic loss, we sweepM∈\{0\.001,0\.002,0\.005\}M\\in\\\{0\.001,\\,0\.002,\\,0\.005\\\},B∈\{2\.5,3\.0,3\.5\}B\\in\\\{2\.5,\\,3\.0,\\,3\.5\\\},R∈\{4,5,6,7,8,10,12\}R\\in\\\{4,\\,5,\\,6,\\,7,\\,8,\\,10,\\,12\\\}, andλ0∈\{0\.10,0\.12,0\.15,0\.18,0\.20\}\\lambda\_\{0\}\\in\\\{0\.10,\\,0\.12,\\,0\.15,\\,0\.18,\\,0\.20\\\}, and obtain the best \(largest\) ratio ofρ=0\.22\\rho=0\.22atM=0\.005M=0\.005,B=2\.5B=2\.5, andR=10\.0R=10\.0\. Because for the cubic loss \(instantiated below in dimensiond=1d=1\) we assume\|w\|\|w\|is bounded byBB, which yields the strong\-convexity parameterμ=λ0−M​B\\mu=\\lambda\_\{0\}\-MB, we additionally require the optimum after loss minimisation to lie inside the interval\[−B,B\]\[\-B,B\]; otherwise the first\-order optimality condition∇ℓ=0\\nabla\\ell=0may fail to hold\.

#### H\.4\.2Logistic loss \(boundary construction\)\.

The retain set consists ofnnpoints with i\.i\.d\. Gaussian features and labels generated from a fixed directionθ∗\\theta^\{\*\},

𝒟r=\{\(xi,yi\)\}i=1n,xi​∼i\.i\.d\.​𝒩​\(0,1d​Id\),yi∣xi∼Bernoulli​\(f1​\(xi⊤​θ∗\)\),\{\\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\),wheref1​\(z\)=η⋅𝟏​\[z≥0\]\+\(1−η\)⋅𝟏​\[z<0\]f\_\{1\}\(z\)=\\eta\\cdot\\mathbf\{1\}\[z\\geq 0\]\+\(1\-\\eta\)\\cdot\\mathbf\{1\}\[z<0\]is the label\-flip function with flip probability1−η1\-\\eta\. The forget set places allmmpoints at the same fixed boundary location with a fixed label,

𝒟f=\{\(x∗,y∗\)\}i=1m,x∗=−sign​\(θ∗\)⋅ρf,y∗=1,\{\\mathcal\{D\}\}\_\{f\}=\\bigl\\\{\(x^\{\*\},y^\{\*\}\)\\bigr\\\}\_\{i=1\}^\{m\},\\qquad x^\{\*\}=\-\\,\\mathrm\{sign\}\(\\theta^\{\*\}\)\\cdot\\rho\_\{f\},\\quad y^\{\*\}=1,whereρf\>0\\rho\_\{f\}\>0is the forget\-point norm\.

This construction is chosen for two reasons\. First, concentrating all forget points at a single locationx∗x^\{\*\}makes every forget sample exert an identical, unidirectional gradient contribution, maximising the aggregate influence of𝒟f\{\\mathcal\{D\}\}\_\{f\}on the full\-data optimumw^f\\hat\{w\}\_\{f\}relative to the retain\-only optimumw^r\\hat\{w\}\_\{r\}\. Second, placingx∗x^\{\*\}in the direction opposite toθ∗\\theta^\{\*\}at distanceρf\\rho\_\{f\}from the origin ensures that the forget signal directly opposes the retain signal, creating the largest possible shift betweenw^f\\hat\{w\}\_\{f\}andw^r\\hat\{w\}\_\{r\}, and hence the tightest empirical Lemma 3 ratioρ\\rho\. However, the sweep for the logistic loss yielded a maximum ratio of only3×10−53\\times 10^\{\-5\}, which explains the poorε\\varepsilonlower bound, at parametersd=2d=2,η=0\.8\\eta=0\.8,ζ=0\.7\\zeta=0\.7, andρf=5\.0\\rho\_\{f\}=5\.0\.

## Appendix IOutput perturbation: mechanism and point placement

### I\.1Mechanism

Given a trained modelx^\\hat\{x\}, the output\-perturbation mechanism produces the unlearned model

xu=ΠC0​\(x^\)\+ξ0,ξ0∼𝒩​\(0,σ2​𝕀\),x\_\{u\}\\;=\\;\\Pi\_\{C\_\{0\}\}\(\\hat\{x\}\)\\;\+\\;\\xi\_\{0\},\\qquad\\xi\_\{0\}\\sim\\mathcal\{N\}\(0,\\,\\sigma^\{2\}\\mathbb\{I\}\),whereΠC0\\Pi\_\{C\_\{0\}\}denotes Euclidean projection onto anℓ2\\ell\_\{2\}\-ball of radiusC0C\_\{0\}andσ\\sigmais chosen according to Theorem 3\.1 ofMu and Klabjan \[[2025](https://arxiv.org/html/2607.05898#bib.bib7)\]so as to satisfy\(ε,δ\)\(\\varepsilon,\\delta\)\-certified unlearning\. The auditing pipeline is identical to that of the cubic loss in[SectionH\.1](https://arxiv.org/html/2607.05898#A8.SS1)\(Gaussian fits on model parameters, Clopper–Pearson lower bound\), with an MSE loss and no regulariser\.

### I\.2Placement of retain and forget points

The retain set consists ofnnpoints with i\.i\.d\. Gaussian features and continuous labels generated from a fixed directionθ∗\\theta^\{\*\},

𝒟r=\{\(xi,yi\)\}i=1n,xi​∼i\.i\.d\.​𝒩​\(0,1d​Id\),yi∣xi=flin​\(xi⊤​θ∗\)−12\+εi,\{\\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

flin​\(z\)=clip​\(12\+η​z,12−r,12\+r\)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η\\etaand half\-rangerr, andεi∼𝒩​\(0,σ2\)\\varepsilon\_\{i\}\\sim\\mathcal\{N\}\(0,\\sigma^\{2\}\)is observation noise \(clipped so thatyi∈\[−r,r\]y\_\{i\}\\in\[\-r,r\]\) withσ=0\.05\\sigma=0\.05\.

The forget set consists ofmmi\.i\.d\. points generated from the opposite direction

θf=−θ∗⋅ρf‖θ∗‖,\\theta\_\{f\}\\;=\\;\-\\theta^\{\*\}\\cdot\\frac\{\\rho\_\{f\}\}\{\\\|\\theta^\{\*\}\\\|\},i\.e\.

𝒟f=\{\(xj,yj\)\}j=1m,xj​∼i\.i\.d\.​𝒩​\(0,1d​Id\),yj∣xj=flin​\(xj⊤​θf\)−12\+εj,\{\\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‖θf‖=ρf≫‖θ∗‖\\\|\\theta\_\{f\}\\\|=\\rho\_\{f\}\\gg\\\|\\theta^\{\*\}\\\|\. Becauseθf\\theta\_\{f\}points in the direction opposite toθ∗\\theta^\{\*\}, the forget labels are systematically negatively correlated with those in𝒟r\{\\mathcal\{D\}\}\_\{r\}, so ERM on𝒟r∪𝒟f\{\\mathcal\{D\}\}\_\{r\}\\cup\{\\mathcal\{D\}\}\_\{f\}is pulled strongly away fromθ∗\\theta^\{\*\}, maximising the gap between the unlearned model trained with𝒟f\{\\mathcal\{D\}\}\_\{f\}and the one trained with the empty forget set, and therefore tightening the resultingεLB\\varepsilon\_\{\\text\{LB\}\}\.

The numbers of train samplesnnand forget samplesmmare600600and400400respectively, withr=10r=10,η=0\.5\\eta=0\.5,ζ=0\.9\\zeta=0\.9, andρf=10\\rho\_\{f\}=10\.

## Appendix JComputational resources

All experiments were performed on NVIDIA RTX 4000 GPUs\. Each individual run \(one train \+ unlearn cycle for a given configuration\) took roughly4545minutes to11hour\. 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\.