Auditing of Unlearning Algorithms

Anastasia Koloskova; Sahasrajit Sarmasarkar; Sanmi Koyejo

REVIEW 1 major objections 5 minor 25 references

Auditor catches fake unlearning: heuristic methods leak ε ≥ 50

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

2026-07-08 21:06 UTC pith:PAHVS5GT

load-bearing objection A practical auditor for unlearning guarantees, with clean theory but a real confound in the headline empirical result. the 1 major comments →

arxiv 2607.05898 v1 pith:PAHVS5GT submitted 2026-07-07 cs.LG cs.CR

Auditing of Unlearning Algorithms

Sahasrajit Sarmasarkar , Anastasia Koloskova , Sanmi Koyejo This is my paper

classification cs.LG cs.CR

keywords machine unlearningmembership inferencedifferential privacy auditinghypothesis testinglocal differential privacycertified unlearningdata deletion

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a practical auditor that tests whether a machine unlearning algorithm actually removes the influence of deleted training data. The auditor works by repeatedly training and unlearning models with different subsets of data marked for deletion, then attempting to guess which subset was forgotten based solely on the unlearned model's predictions. If the auditor guesses correctly more often than chance, the unlearning is weak. The authors reduce this to a local differential privacy problem: if an algorithm certifies (ε, 0)-unlearning, then the auditor's prediction mechanism is (2ε, 0)-locally differentially private, and standard tail bounds convert the auditor's overlap score into a valid lower bound ε_LB on the true unlearning parameter ε with controlled Type I error. The central object is this hypothesis test (Theorem 4.2), which takes the mean or median of overlap scores across independent runs and returns a lower bound that, if exceeded, falsifies the algorithm's unlearning guarantee at a chosen confidence level. Applied to CIFAR-100 and Shakespeare, the auditor reveals a sharp separation: certified algorithms (model clipping, rewind-to-delete) yield ε_LB near zero across a wide sweep of privacy parameters, while heuristic methods (Hessian-based, interleaved ascent-descent, gradient ascent, fine-tuning) yield ε_LB in the tens or higher. The most diagnostic result is that Hessian-based unlearning, which carries a formal certification only under convexity, is flagged with ε_LB = 142.5 when run on a nonconvex network where that precondition silently fails.

Core claim

The paper's core discovery is that membership inference attacks can be repurposed into a calibrated, hypothesis-testing auditor that produces a data-dependent lower bound on the unlearning parameter ε. The reduction to local differential privacy (Lemma 4.1) is the bridge: certified unlearning implies the auditor's induced mechanism is locally private, so existing LDP tail bounds apply. The empirical payoff is that this auditor cleanly separates algorithms whose certified guarantees hold in the deployment regime from those whose guarantees rest on violated preconditions or on no formal guarantee at all. The Hessian-based method scoring ε_LB = 142.5 on a nonconvex model—higher than any purelyh

What carries the argument

reduction_to_ldp

Load-bearing premise

The reduction to local differential privacy relies on the triangle inequality for pure (ε, 0)-indistinguishability, which breaks down when δ > 0 because the additive slack becomes (1+e^ε)δ, too large to be useful. This restricts the auditor to pure unlearning (δ = 0), excluding many practical certified algorithms that operate with approximate guarantees.

What would settle it

If an unlearning algorithm with a valid (ε, 0)-certified guarantee consistently produced ε_LB well above ε across many independent audit runs, the test's Type I error control would be violated, falsifying Theorem 4.2's bound. Conversely, if a known-weak unlearning algorithm consistently produced ε_LB near zero, the auditor would lack power.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

If the auditor's separation generalises, practitioners deploying unlearning can run it before trusting a claimed ε, catching cases where a certification's preconditions (e.g., convexity) silently fail at deployment.
The restriction to δ = 0 limits applicability to algorithms certified under approximate (ε, δ)-unlearning with δ > 0; extending the triangle-inequality reduction to δ > 0 is identified by the authors as the key open problem, since the additive slack (1+e^ε)δ becomes too large.
The uniform-vs-adversarial split asymmetry suggests that unlearning quality depends on semantic overlap between retain and forget data, which the auditor can surface as a diagnostic beyond a single ε_LB number.
The pairwise baseline auditor yields zero lower bounds even at perfect accuracy due to loose Clopper-Pearson intervals, suggesting that the joint multi-canary approach is necessary, not merely convenient, for obtaining non-trivial bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The auditor's power depends on the ratio of per-batch leakage to the number of candidate forget batches m; this creates a natural operating-point trade-off that could be tuned adaptively per algorithm rather than fixed a priori, potentially yielding tighter bounds.
The δ = 0 restriction means the auditor cannot currently evaluate many practical certified algorithms that operate with δ > 0; a workaround might audit at δ = 0 for a modified version of the algorithm with δ set to zero, then argue continuity, though the paper does not explore this.
If the auditor were run as part of a regulatory or compliance pipeline, the independence requirement between calibration and evaluation runs would need cryptographic enforcement to prevent a dishonest provider from sharing seeds or initializations across the two phases.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

A practical auditor for unlearning guarantees, with clean theory but a real confound in the headline empirical result.

read the letter

The main thing to know: this paper builds the first auditor that produces a lower bound on the unlearning parameter ε calibrated directly to the certified-unlearning definition, and the theory is clean. The LDP reduction (Lemma 4.1) is a straightforward triangle-inequality argument for δ=0, and Theorem 4.2's counting-argument bound with Chernoff/union bounds is correct and parameter-free. The monotonicity corollary (B.2) ensures the hypothesis test is valid. Code is shipped. This is a genuine contribution to the unlearning evaluation literature — nobody had a tool that directly falsifies ε-claims before this, and the reduction to LDP plus the new bound is non-trivial adaptation, not a port of DP auditing code. The Hessian-based method getting flagged at ε_LB = 142.5 when its convexity precondition silently fails is a nice demonstration of the auditor's diagnostic value. The convex experiments (Section 8) independently show the auditor tracks ε reasonably well in a tractable setting, which is good evidence the framework isn't fundamentally broken. The δ=0 restriction is a real but clearly stated limitation — the paper is upfront that the additive slack blows up for δ>0, and Appendix C shows the authors understand exactly why. Now the soft spot. The stress-test concern about asymmetric auditor configurations lands. Certified methods are audited at m=6, L=100, while uncertified methods use m=4500, L=10. The paper itself notes that perfect prediction at m=6 with L=10 yields only ε_LB ≥ 4.00 — so the near-zero bounds for certified methods are consistent with either genuine certification holding OR the auditor simply lacking power at m=6. The paper's partial defense — the uncertified model-clipping variant at m=6 showing growing ε_LB (Figure 1a) — uses L=500, five times more evaluation runs than the certified experiments. The authors explicitly say L=500 was chosen for 'tighter bounds,' which implies L=100 may be insufficient. This doesn't sink the paper: the theory is sound, the convex experiments provide independent support, and the Hessian result is informative regardless. But the headline 'sharp separation' claim is overstated relative to what the certified-method experiments can actually demonstrate. A referee should ask for either L=500 on certified methods or an explicit power analysis showing L=100 suffices to detect violations at m=6. Who benefits: researchers working on certified unlearning who need a falsification tool, and practitioners evaluating unlearning claims. The paper deserves a serious referee — the framework is right, the bound is new, and the experiments are mostly honest about their limitations. The fix is additional runs, not new theory.

Referee Report

1 major / 5 minor

Summary. This paper proposes a practical auditor for machine unlearning algorithms that computes data-dependent lower bounds on the unlearning parameter $ε$ via membership inference attacks. The core theoretical framework reduces the unlearning audit to a local differential privacy (LDP) lower-bound problem (Lemma 4.1) and derives a hypothesis test with controlled Type I error (Theorem 4.2) via a counting argument and Chernoff/union bounds. The authors instantiate this auditor in two ways (batchwise and joint sign-vector prediction) and evaluate it on CIFAR-100 and Shakespeare across certified (model clipping, rewind-to-delete) and uncertified (Hessian-based, IDA, ascent, fine-tuning) unlearning algorithms. The central empirical finding is a sharp separation: certified methods yield $ε_{LB} ≈ 0$, while uncertified methods yield $ε_{LB}$ in the tens or higher, with the Hessian-based method (whose certification silently fails in the nonconvex regime) flagged at $ε_{LB} = 142.5$.

Significance. The paper makes a solid contribution to the growing area of unlearning verification. The theoretical framework is clean and the lower bound in Theorem 4.2 is derived from first principles (LDP definition + counting argument) with no fitted constants. The reduction to LDP for the subset-level unlearning guarantee is a non-trivial extension of standard DP auditing (which typically handles only single-point neighboring relations). The empirical demonstration that the auditor can distinguish certified from uncertified methods, and specifically flag methods whose preconditions are violated (e.g., Hessian-based unlearning in the nonconvex regime), is a valuable diagnostic tool for the community. The authors provide reproducible code and falsifiable predictions. The restriction to pure ($δ=0$) unlearning is a limitation, but it is clearly stated and the $δ>0$ extension is discussed in Appendix C.

major comments (1)

The central empirical claim of a 'sharp separation' between certified and uncertified methods is confounded by asymmetric auditor configurations. Certified methods are audited at $m=6$ ($B=750$) with $L=100$ evaluation runs using the joint sign-vector predictor, while uncertified methods use $m=4500$ ($B=1$) with $L=10$ runs and the batchwise predictor. As noted in Section F.1, the maximum attainable $ε_{LB}$ at $m=6$ with $L=10$ is only 4.00; even with $L=100$, the cap remains structurally low relative to the bounds reported for uncertified methods (50–142). This means the near-zero bounds for certified methods are consistent with two scenarios: (a) the certification genuinely holds, or (b) the auditor lacks power in the $m=6$, $L=100$ regime to detect any violation. The paper partially addresses this by showing the uncertified variant of model clipping (Figure 1a) yields growing $ε_{LB

minor comments (5)

Section 7.1: The text states 'At the prescribed stopping time of Theorem 4.2, the audit yields $ε_{LB} ≈ 0$ across the entire grid.' It would help to clarify whether this refers to Theorem 4.2 of this paper or Theorem 4.2 of Koloskova et al. [2025], as the numbering is ambiguous.
Table 1b: The Hessian-based method on CIFAR-100 shows a large uniform-vs-adversarial gap ($ε_{LB} = 142.5$ uniform vs. 10 adversarial). The explanation in Section 7.3 attributes the general uniform-vs-adversarial pattern to residual memorization and semantic adjacency, but the Hessian case is extreme. A brief discussion of why the Hessian method specifically exhibits such a large gap would strengthen the analysis.
Section 8, Table 2: The logistic loss yields a 0 bound, attributed to a poor Lemma 3 ratio ($ρ ≈ 3×10^{-5}$). While Section H.3 explains this, it would be useful to note in the main text that the 0 bound for the logistic loss is an artifact of the specific construction rather than a failure of the auditor.
Appendix C, Remark C.2: The discussion of $δ>0$ is valuable but somewhat dense. The condition $δ < M'/K$ for monotonicity is stated, but the practical implications could be made clearer by explicitly noting that for the operating points used in the experiments (e.g., $m=4500$, $r=3000$), $K$ is astronomically large, making the $δ>0$ audit vacuous. This is mentioned but could be more prominent.
Figure 1a: The y-axis label '$ε_{LB}$' could be more informative if it included the range or noted that it is on a log scale (if applicable). The figure caption could also clarify that $L=500$ is used here, unlike the $L=100$ for certified methods.

Simulated Author's Rebuttal

5 responses · 0 unresolved

We thank the referee for a careful reading and for identifying a legitimate concern about the comparability of our certified vs. uncertified audit configurations. The referee is correct that the asymmetric choices of m, L, and auditor instantiation could, in principle, confound the 'sharp separation' claim. Below we address this point-by-point, acknowledge where the manuscript needs revision, and describe the additional experiments and textual changes we will make.

read point-by-point responses

Referee: The central empirical claim of a 'sharp separation' is confounded by asymmetric auditor configurations. Certified methods are audited at m=6 (B=750) with L=100 using the joint sign-vector predictor, while uncertified methods use m=4500 (B=1) with L=10 runs and the batchwise predictor. The maximum attainable ε_LB at m=6 with L=10 is only 4.00; even with L=100, the cap remains structurally low relative to bounds reported for uncertified methods (50–142). Near-zero bounds for certified methods are consistent with either (a) genuine certification or (b) lack of auditor power in the m=6, L=100 regime.

Authors: The referee raises a valid concern. We address it in three parts: (1) why the configurations differ, (2) what control experiments already exist, and (3) what we will add to the revision. revision: partial
Referee: [Sub-point] Why the configurations differ — is this arbitrary?

Authors: The configuration difference is not arbitrary; it is driven by the fundamental signal strength of certified vs. uncertified methods, as discussed in Remark 4.3 and Sections F.2 and F.4. Certified methods inject noise calibrated to their (ε,δ) budget, making the in-forget-set and out-of-forget-set distributions for a single batch nearly indistinguishable. At large m (small B), the per-batch signal is too weak for the auditor to beat random guessing among exponentially many candidate sign vectors, and the joint sign-vector predictor — which requires enumerating |S_m| candidates — is computationally infeasible. We therefore use small m (B=750, m=6) with the joint sign-vector predictor for certified methods. For uncertified methods, the per-batch signal is strong, so large m (B=1, m=4500) with the batchwise predictor yields the tightest bounds. We will make this rationale more prominent in the main text (currently it is split across Remark 4.3 and Appendix F). revision: partial
Referee: [Sub-point] The uncertified variant of model clipping as a control — is it sufficient?

Authors: The referee correctly notes that Figure 1a (uncertified variant of model clipping at C2=5, σ=10^{-4}, B=750) partially addresses the concern. This experiment uses the SAME B=750 (m=6) configuration as the certified variant and the SAME joint sign-vector predictor, and the auditor detects growing ε_LB — demonstrating that the m=6 regime is not inherently powerless when violations exist. However, we acknowledge two gaps: (i) the uncertified variant uses L=500 rather than L=100, and (ii) the maximum attainable bound at m=6 is indeed structurally limited (Section F.1: ε_LB ≤ 4.00 at L=10, and higher but still bounded at L=100). This means our audit cannot rule out small violations of the certified guarantee; it can only confirm that no large violations are detectable. We will revise the language from 'sharp separation' to a more precise statement: certified methods yield ε_LB ≈ 0 (i.e., the audit does not falsify their guarantees), while uncertified methods yield large ε_LB in a regime where the auditor has substantially more power. The separation is real but its magnitude is partly an artifact of the different operating points, and we will state this explicitly. revision: yes
Referee: [Sub-point] What additional experiments will be added?

Authors: We will add the following experiments to strengthen the control: (1) Run the uncertified variant of model clipping (Figure 1a configuration) at L=100 (matching the certified setting) and report ε_LB as a function of step t, to verify that the auditor can still detect violations at the same run budget used for certified methods. (2) Run at least one uncertified method (e.g., forget ascent) at B=750 (m=6) with the joint sign-vector predictor, to show that the m=6 regime can detect large violations when they exist — providing a direct apples-to-apples comparison. (3) Report the maximum attainable ε_LB at m=6, L=100 explicitly in the main text (not just in Appendix F.1) so readers can calibrate the near-zero bounds against the auditor's ceiling in this regime. These additions will be incorporated into Sections 7.1 and 7.3 and a revised Figure 1. revision: yes
Referee: [Sub-point] The convex experiments (Section 8) as additional evidence

Authors: We will also add a cross-reference to Section 8 (convex unlearning) in the main empirical discussion. In the convex setting, where the mechanism is analytically tractable, the gap between the certified ε and ε_LB is much smaller (Table 2), confirming that the auditor can produce tight bounds when the setting permits. This provides indirect evidence that the near-zero bounds for certified methods on CIFAR-100 reflect genuine unlearning rather than pure auditor slack, though we agree it is not a complete substitute for the direct control experiments described above. revision: partial

Circularity Check

0 steps flagged

No significant circularity found. The lower bound is derived from first principles; the one self-citation is a test subject, not a load-bearing premise.

full rationale

The paper's central theoretical result (Theorem 4.2) is a self-contained derivation: it starts from the definition of (ε,0)-LDP, applies Bayes' rule to obtain a pointwise posterior bound (Eq. 7), and combines it with a combinatorial counting argument to bound the overlap-score distribution via Chernoff and median bounds. No fitted constants enter the bound, and the Gaussian modeling in Instantiations I and II is explicitly stated to be a choice for the attack only: 'Modelling scores as Gaussian is a choice for the attack only; Theorem 4.2 requires no such assumption.' The reduction to LDP (Lemma 4.1) uses the standard triangle inequality for pure (ε,0)-indistinguishability, which is textbook DP group privacy, not a self-citation. The one notable self-citation is Koloskova et al. [2025] (model clipping), which shares co-authors with this paper, but it is cited as the algorithm being audited—a test subject—rather than as justification for the auditor's own validity. The audit is adversarial: it attempts to falsify the guarantee, not confirm it. The skeptic's concern about asymmetric auditor configurations (m=6 vs m=4500) is a statistical-power issue, not a circularity issue. The convex-setting results (Section 8) adapt the pairwise baseline with an independent definition from Sekhari et al. [2021], again without circular dependency. I find no step where a prediction reduces to its inputs by construction.

Axiom & Free-Parameter Ledger

5 free parameters · 4 axioms · 0 invented entities

No new entities are postulated. The auditor is a procedure operating on existing algorithms and data.

free parameters (5)

ζ (confidence level) = 0.05
Standard choice for hypothesis testing; controls Type I error rate.
m (number of forget batches) = varies (6 for certified, 4500 for uncertified on CIFAR-100)
Chosen based on algorithm type and per-batch signal strength; discussed in Remark 4.3 and Appendix F.
r (support size) = varies (100 for Shakespeare, 3000 for CIFAR-100 uncertified)
Chosen empirically to maximize the lower bound; traces an inverted-U in r (Appendix F.3).
L (number of evaluation runs) = varies (10–500)
Chosen based on desired tightness of the bound; more runs yield tighter bounds.
Γ (calibration rounds) = 50
Chosen empirically for fitting Gaussian score distributions.

axioms (4)

standard math Post-processing preserves (ε, δ)-indistinguishability
Invoked in Lemma 4.1 to argue that the auditor's mechanism M, which depends on S only through fu(S), inherits the certified-unlearning guarantee.
standard math Triangle inequality for (ε, 0)-indistinguishability: if X ≈_{ε,0} Y and Y ≈_{ε,0} Z then X ≈_{2ε,0} Z
Invoked in the proof of Lemma 4.1 to establish that fu(S1) ≈_{2ε,0} fu(S2) via the reference model fr.
domain assumption Logit scores under in-forget-set and never-seen hypotheses are approximately Gaussian
Used in Instantiations I and II (Section 5) to fit Gaussian likelihoods for the LiRA-style attack. Theorem 4.2 does not require this assumption; it only affects attack power, not bound validity.
domain assumption Calibration runs and evaluation runs are drawn independently
Stated in Section 5: required for the audit's lower bound to be valid. If violated, the bound may not hold.

pith-pipeline@v1.1.0-glm · 32144 in / 4843 out tokens · 259509 ms · 2026-07-08T21:06:44.686343+00:00 · methodology

0 comments

read the original 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 $\varepsilon$ using 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 $\varepsilon$ bounds 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.

Figures

Figures reproduced from arXiv: 2607.05898 by Anastasia Koloskova, Sahasrajit Sarmasarkar, Sanmi Koyejo.

discussion (0)

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages · 8 internal anchors

[2]

Local Differential Privacy: a tutorial

URL https: //arxiv.org/abs/1907.11908. Mart´ın Bertran, Shuai Tang, Michael Kearns, Jamie Morgenstern, Aaron Roth, and Zhiwei Steven Wu. Reconstruction attacks on machine unlearning: Simple models are vulnerable. InAdvances in Neural Information Processing Systems (NeurIPS),

work page internal anchor Pith review Pith/arXiv arXiv 1907
[3]

Membership Inference Attacks From First Principles

URLhttps://arxiv.org/abs/2112.03570. Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. When machine unlearning jeopardizes privacy. InProceedings of the 2021 ACM SIGSAC Conference on Computer and Communica- tions Security, CCS ’21, page 896–911, New York, NY , USA,

work page internal anchor Pith review Pith/arXiv arXiv 2021
[4]

ISBN 9781450384544

Association for Computing Machinery. ISBN 9781450384544. doi: 10.1145/3460120.3484756. URL https://doi.org/10.1145/3460120.3484756. Jingpu Cheng, Ping Liu, Qianxiao Li, and Chi Zhang. Machine unlearning under retain-forget entanglement,

work page doi:10.1145/3460120.3484756
[5]

Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li

URLhttps://arxiv.org/abs/2603.26569. Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li. 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,

work page arXiv
[6]

2014 , issue_date =

ISSN 1551-305X. doi: 10.1561/0400000042. URL https://doi.org/10. 1561/0400000042. Ali Ebrahimpour-Boroojeny, Yian Wang, and Hari Sundaram. On the necessity of output distribution reweighting for effective class unlearning,

work page doi:10.1561/0400000042
[7]

Antonio A

URLhttps://arxiv.org/abs/2506.20893. Antonio A. Ginart, Melody Y . Guan, Gregory Valiant, and James Zou.Making AI forget you: data deletion in machine learning. Curran Associates Inc., Red Hook, NY , USA,

work page internal anchor Pith review arXiv
[8]

Certified Unlearning for Neural Networks

URLhttps://arxiv.org/abs/2506.06985. Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto,

work page internal anchor Pith review Pith/arXiv arXiv
[9]

Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini

URL https://arxiv.org/abs/2409.09778. Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary instantiation: Lower bounds for differentially private machine learning,

work page arXiv
[10]

Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning

URLhttps://arxiv.org/abs/2101.04535. Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tram `er, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. InUSENIX Security Symposium, pages 1631–1648,

work page internal anchor Pith review Pith/arXiv arXiv
[12]

Membership Inference Attacks against Machine Learning Models

URLhttp://arxiv.org/abs/1610.05820. David Marco Sommer, Liwei Song, Sameer Wagh, and Prateek Mittal. Athena: Probabilistic verification of machine unlearning.Proceedings on Privacy Enhancing Technologies (PoPETs), 2022(3):268–290,

work page internal anchor Pith review Pith/arXiv arXiv 2022
[13]

URL https://arxiv.org/abs/2305.08846. Eleni Triantafillou, Peter Kairouz, Fabian Pedregosa, Jamie Hayes, Meghdad Kurmanji, Kairan Zhao, Vincent Dumoulin, Julio Jacques Junior, Ioannis Mitliagkas, Jun Wan, Lisheng Sun Hosoya, Sergio Escalera, Gintare Karolina Dziugaite, Peter Triantafillou, and Isabelle Guyon. Are we making progress in unlearning? findings...

work page internal anchor Pith review Pith/arXiv arXiv
[14]

URL https://doi.org/ 10.1198/jasa.2009.tm08651

doi: 10.1198/jasa.2009.tm08651. URL https://doi.org/ 10.1198/jasa.2009.tm08651. Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. InIEEE Computer Security Foundations Symposium (CSF), pages 268–282,

work page doi:10.1198/jasa.2009.tm08651 2009
[15]

URLhttps://arxiv.org/abs/2408.00920. 12 A Auditor algorithms: pseudocode This appendix gives pseudocode for the meta-algorithm of Section 4 and the two auditor instantiations (batchwise inclusion/exclusionandjoint sign vector prediction) of Section 5; see Algorithms 1 to

work page internal anchor Pith review Pith/arXiv arXiv
[16]

audit DP by having the adversary distinguish two models trained on neighbouring datasets. We adapt this baseline to unlearning by distinguishing the two unlearned models f(i) u :=U A(Dr ∪ D(i) f ),D r ∪ D(i) f ,D (i) f for i∈ {1,2} , corresponding to two distinct forget setsD(1) f ,D (2) f . Calibration and prediction are identical to Instantiation II 13 ...

work page 2015
[17]

16 Define the upper tailP ε(v) :=Pr u=v πε(u)

r/2 α1 r/2 α2 · eε + M ′−1 M ′ K δ eε +M ′ −1 . 16 Define the upper tailP ε(v) :=Pr u=v πε(u). Then for everyv∈R, Pr " 1 L LX ℓ=1 V (ℓ) ≥v # ≤inf λ≥0 exp Llog rX u=0 eλuπε(u) −λLv ! (9) Pr Median {V (ℓ)}L ℓ=1 ≥v ≤ L ⌊L/2⌋ Pε(v)⌈L/2⌉.(10) Additionally, for the test to be meaningful, we need to ensure that the upper bound is monotonically non-decreasing inε...

work page 2000
[18]

From the training portion, we designate 10% of the points as the forget set Df (4,500 points), and use the remaining 40,500 points as the retain set Dr

D.1 CIFAR-100 Forget/retain construction.For CIFAR-100 [Krizhevsky, 2009], we first split the original training set into a training portion (90%) and a validation portion (10%). From the training portion, we designate 10% of the points as the forget set Df (4,500 points), and use the remaining 40,500 points as the retain set Dr. We consider two types of s...

work page 2009
[19]

A discussion of why this split between auditor instantiations is appropriate is given in Section F.4, with a more detailed study in Section F

for certified methods. A discussion of why this split between auditor instantiations is appropriate is given in Section F.4, with a more detailed study in Section F. Model.We use a TinyNetCIFAR100 model, a lightweight CNN that attains around 55% accuracy on the CIFAR- 100 test set after400 epochs of training. The architecture consists of two convolutional...

work page 2017
[20]

The retain samples and sampled forget samples are then pooled and shuffled to form the training dataset

Each chunk and the retain set are independently converted to sliding-window samples of length 80 characters, where x is the input sequence and y is the target sequence shifted by one character. The retain samples and sampled forget samples are then pooled and shuffled to form the training dataset. The retain and forget datasets used during evaluation are ...

work page 2025
[21]

Model.The model is a 2-layer stacked character-level LSTM following McMahan et al

throughout, as on CIFAR-100. Model.The model is a 2-layer stacked character-level LSTM following McMahan et al. [2017]. Each input character is embedded into an 8-dimensional space, processed through two LSTM layers each with 256 hidden units, and projected to a softmax output layer over the vocabulary of|V|= 100 characters. The full model has 825,220 par...

work page 2017
[22]

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

100 17.4945 3.31 N/A N/A 200 29.5805 6.46 0.53 N.A 400 47.8495 13.06 1.21 N.A 1000 80.693 29.74 3.26 0.00 2000 90.1105 51.47 6.64 0.27 3000 79.835 64.08 9.99 0.76 3500 73.21 65.19 N/A N/A 4000 66.631 64.22 13.26 1.29 Table 5: Comparison across batch sizes for the ascent on forget set setting. further, however, perfect overlap becomes harder to attain — th...

work page 2000
[23]

so that the iterate xTnoisy satisfies the target(ε, δ)guarantee. Phase 2: fine-tuning.Starting from xTnoisy, 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.2 Hyperparameters As chosen in Koloskova et al. [2025], we train for a total of 400 epochs with a tra...

work page 2025
[24]

To obtain tighter bounds in this regime we use L= 500 runs

admits, so no certified(ε, δ) guarantee applies; we still report εLB at every step t as defined above. To obtain tighter bounds in this regime we use L= 500 runs. For context, 1 epoch corresponds to 317 steps in this setup, so Figure 1a effectively covers up to roughly2epochs. G.2 Rewind-to-delete We take T= 40 training epochs and K= 5 rewind epochs. Foll...

work page 2025
[25]

Shakespeare.We vary q∈ {1,2,4} , Ef ∈ {5,7} , and λ∈ {0.5,1.0,1.5}

The learning rate is held constant at 10−3 during the interleaved phase, and reverts to a one-cycle schedule with maximum0.1during the retain-set fine-tuning phase. Shakespeare.We vary q∈ {1,2,4} , Ef ∈ {5,7} , and λ∈ {0.5,1.0,1.5} . The learning rate is held constant at 0.05 during the interleaved phase and held constant at 0.1 during the retain finetuni...

work page 2021
[26]

25 H.1 Auditor pipeline We adapt the pairwise auditor of Section 5 (Nasr et al., 2021-style) to the convex setting, with two changes. First, in line with Theorem H.1, the auditor distinguishes the unlearned model produced from a non-empty forget set, U(D f ,A(D), S(D)) , against the model produced from an empty forget set, U(∅,A(D r), S(Dr)), rather than ...

work page 2021
[27]

[2021]); this is because the norm bound (∆) used for the addition of Gaussian noise is closer to what is actually attained empirically

RemarkI.1.One may wonder why output perturbation gives a much tighter lower bound than Perturbed Hessian unlearning (given in Sekhari et al. [2021]); this is because the norm bound (∆) used for the addition of Gaussian noise is closer to what is actually attained empirically. J Computational resources All experiments were performed on NVIDIA RTX 4000 GPUs...

work page 2021

[1] [2]

Local Differential Privacy: a tutorial

URL https: //arxiv.org/abs/1907.11908. Mart´ın Bertran, Shuai Tang, Michael Kearns, Jamie Morgenstern, Aaron Roth, and Zhiwei Steven Wu. Reconstruction attacks on machine unlearning: Simple models are vulnerable. InAdvances in Neural Information Processing Systems (NeurIPS),

work page internal anchor Pith review Pith/arXiv arXiv 1907

[2] [3]

Membership Inference Attacks From First Principles

URLhttps://arxiv.org/abs/2112.03570. Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, and Yang Zhang. When machine unlearning jeopardizes privacy. InProceedings of the 2021 ACM SIGSAC Conference on Computer and Communica- tions Security, CCS ’21, page 896–911, New York, NY , USA,

work page internal anchor Pith review Pith/arXiv arXiv 2021

[3] [4]

ISBN 9781450384544

Association for Computing Machinery. ISBN 9781450384544. doi: 10.1145/3460120.3484756. URL https://doi.org/10.1145/3460120.3484756. Jingpu Cheng, Ping Liu, Qianxiao Li, and Chi Zhang. Machine unlearning under retain-forget entanglement,

work page doi:10.1145/3460120.3484756

[4] [5]

Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li

URLhttps://arxiv.org/abs/2603.26569. Eli Chien, Haoyu Wang, Ziang Chen, and Pan Li. 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,

work page arXiv

[5] [6]

2014 , issue_date =

ISSN 1551-305X. doi: 10.1561/0400000042. URL https://doi.org/10. 1561/0400000042. Ali Ebrahimpour-Boroojeny, Yian Wang, and Hari Sundaram. On the necessity of output distribution reweighting for effective class unlearning,

work page doi:10.1561/0400000042

[6] [7]

Antonio A

URLhttps://arxiv.org/abs/2506.20893. Antonio A. Ginart, Melody Y . Guan, Gregory Valiant, and James Zou.Making AI forget you: data deletion in machine learning. Curran Associates Inc., Red Hook, NY , USA,

work page internal anchor Pith review arXiv

[7] [8]

Certified Unlearning for Neural Networks

URLhttps://arxiv.org/abs/2506.06985. Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto,

work page internal anchor Pith review Pith/arXiv arXiv

[8] [9]

Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini

URL https://arxiv.org/abs/2409.09778. Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary instantiation: Lower bounds for differentially private machine learning,

work page arXiv

[9] [10]

Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning

URLhttps://arxiv.org/abs/2101.04535. Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tram `er, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. InUSENIX Security Symposium, pages 1631–1648,

work page internal anchor Pith review Pith/arXiv arXiv

[10] [12]

Membership Inference Attacks against Machine Learning Models

URLhttp://arxiv.org/abs/1610.05820. David Marco Sommer, Liwei Song, Sameer Wagh, and Prateek Mittal. Athena: Probabilistic verification of machine unlearning.Proceedings on Privacy Enhancing Technologies (PoPETs), 2022(3):268–290,

work page internal anchor Pith review Pith/arXiv arXiv 2022

[11] [13]

URL https://arxiv.org/abs/2305.08846. Eleni Triantafillou, Peter Kairouz, Fabian Pedregosa, Jamie Hayes, Meghdad Kurmanji, Kairan Zhao, Vincent Dumoulin, Julio Jacques Junior, Ioannis Mitliagkas, Jun Wan, Lisheng Sun Hosoya, Sergio Escalera, Gintare Karolina Dziugaite, Peter Triantafillou, and Isabelle Guyon. Are we making progress in unlearning? findings...

work page internal anchor Pith review Pith/arXiv arXiv

[12] [14]

URL https://doi.org/ 10.1198/jasa.2009.tm08651

doi: 10.1198/jasa.2009.tm08651. URL https://doi.org/ 10.1198/jasa.2009.tm08651. Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. InIEEE Computer Security Foundations Symposium (CSF), pages 268–282,

work page doi:10.1198/jasa.2009.tm08651 2009

[13] [15]

URLhttps://arxiv.org/abs/2408.00920. 12 A Auditor algorithms: pseudocode This appendix gives pseudocode for the meta-algorithm of Section 4 and the two auditor instantiations (batchwise inclusion/exclusionandjoint sign vector prediction) of Section 5; see Algorithms 1 to

work page internal anchor Pith review Pith/arXiv arXiv

[14] [16]

audit DP by having the adversary distinguish two models trained on neighbouring datasets. We adapt this baseline to unlearning by distinguishing the two unlearned models f(i) u :=U A(Dr ∪ D(i) f ),D r ∪ D(i) f ,D (i) f for i∈ {1,2} , corresponding to two distinct forget setsD(1) f ,D (2) f . Calibration and prediction are identical to Instantiation II 13 ...

work page 2015

[15] [17]

16 Define the upper tailP ε(v) :=Pr u=v πε(u)

r/2 α1 r/2 α2 · eε + M ′−1 M ′ K δ eε +M ′ −1 . 16 Define the upper tailP ε(v) :=Pr u=v πε(u). Then for everyv∈R, Pr " 1 L LX ℓ=1 V (ℓ) ≥v # ≤inf λ≥0 exp Llog rX u=0 eλuπε(u) −λLv ! (9) Pr Median {V (ℓ)}L ℓ=1 ≥v ≤ L ⌊L/2⌋ Pε(v)⌈L/2⌉.(10) Additionally, for the test to be meaningful, we need to ensure that the upper bound is monotonically non-decreasing inε...

work page 2000

[16] [18]

From the training portion, we designate 10% of the points as the forget set Df (4,500 points), and use the remaining 40,500 points as the retain set Dr

D.1 CIFAR-100 Forget/retain construction.For CIFAR-100 [Krizhevsky, 2009], we first split the original training set into a training portion (90%) and a validation portion (10%). From the training portion, we designate 10% of the points as the forget set Df (4,500 points), and use the remaining 40,500 points as the retain set Dr. We consider two types of s...

work page 2009

[17] [19]

A discussion of why this split between auditor instantiations is appropriate is given in Section F.4, with a more detailed study in Section F

for certified methods. A discussion of why this split between auditor instantiations is appropriate is given in Section F.4, with a more detailed study in Section F. Model.We use a TinyNetCIFAR100 model, a lightweight CNN that attains around 55% accuracy on the CIFAR- 100 test set after400 epochs of training. The architecture consists of two convolutional...

work page 2017

[18] [20]

The retain samples and sampled forget samples are then pooled and shuffled to form the training dataset

Each chunk and the retain set are independently converted to sliding-window samples of length 80 characters, where x is the input sequence and y is the target sequence shifted by one character. The retain samples and sampled forget samples are then pooled and shuffled to form the training dataset. The retain and forget datasets used during evaluation are ...

work page 2025

[19] [21]

Model.The model is a 2-layer stacked character-level LSTM following McMahan et al

throughout, as on CIFAR-100. Model.The model is a 2-layer stacked character-level LSTM following McMahan et al. [2017]. Each input character is embedded into an 8-dimensional space, processed through two LSTM layers each with 256 hidden units, and projected to a softmax output layer over the vocabulary of|V|= 100 characters. The full model has 825,220 par...

work page 2017

[20] [22]

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

100 17.4945 3.31 N/A N/A 200 29.5805 6.46 0.53 N.A 400 47.8495 13.06 1.21 N.A 1000 80.693 29.74 3.26 0.00 2000 90.1105 51.47 6.64 0.27 3000 79.835 64.08 9.99 0.76 3500 73.21 65.19 N/A N/A 4000 66.631 64.22 13.26 1.29 Table 5: Comparison across batch sizes for the ascent on forget set setting. further, however, perfect overlap becomes harder to attain — th...

work page 2000

[21] [23]

so that the iterate xTnoisy satisfies the target(ε, δ)guarantee. Phase 2: fine-tuning.Starting from xTnoisy, 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.2 Hyperparameters As chosen in Koloskova et al. [2025], we train for a total of 400 epochs with a tra...

work page 2025

[22] [24]

To obtain tighter bounds in this regime we use L= 500 runs

admits, so no certified(ε, δ) guarantee applies; we still report εLB at every step t as defined above. To obtain tighter bounds in this regime we use L= 500 runs. For context, 1 epoch corresponds to 317 steps in this setup, so Figure 1a effectively covers up to roughly2epochs. G.2 Rewind-to-delete We take T= 40 training epochs and K= 5 rewind epochs. Foll...

work page 2025

[23] [25]

Shakespeare.We vary q∈ {1,2,4} , Ef ∈ {5,7} , and λ∈ {0.5,1.0,1.5}

The learning rate is held constant at 10−3 during the interleaved phase, and reverts to a one-cycle schedule with maximum0.1during the retain-set fine-tuning phase. Shakespeare.We vary q∈ {1,2,4} , Ef ∈ {5,7} , and λ∈ {0.5,1.0,1.5} . The learning rate is held constant at 0.05 during the interleaved phase and held constant at 0.1 during the retain finetuni...

work page 2021

[24] [26]

25 H.1 Auditor pipeline We adapt the pairwise auditor of Section 5 (Nasr et al., 2021-style) to the convex setting, with two changes. First, in line with Theorem H.1, the auditor distinguishes the unlearned model produced from a non-empty forget set, U(D f ,A(D), S(D)) , against the model produced from an empty forget set, U(∅,A(D r), S(Dr)), rather than ...

work page 2021

[25] [27]

[2021]); this is because the norm bound (∆) used for the addition of Gaussian noise is closer to what is actually attained empirically

RemarkI.1.One may wonder why output perturbation gives a much tighter lower bound than Perturbed Hessian unlearning (given in Sekhari et al. [2021]); this is because the norm bound (∆) used for the addition of Gaussian noise is closer to what is actually attained empirically. J Computational resources All experiments were performed on NVIDIA RTX 4000 GPUs...

work page 2021