- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper proposes a hypothesis-testing framework for auditing machine unlearning algorithms. The method derives empirical lower confidence bounds on the zCDP parameter of certified unlearning, with extensions to Gaussian DP and pure DP. The proposed auditor uses randomized inclusion of candidate forget batches and membership-inference-based predictions to construct overlap statistics. The authors evaluate the framework on CIFAR-100, Shakespeare, TOFU, and small convex optimization problems.
Critical strengths
-
The paper formulates a concrete hypothesis-testing objective with controlled Type I error. It correctly emphasizes that a non-rejection is not evidence of successful unlearning.
-
The connection between subset-level certified unlearning and Rényi-DP-based auditing is potentially useful.
Critical weaknesses
-
Poor presentation and organization. The abstract contains poorly formatted citations and unnecessary implementation-level details. The main text is fragmented: Sections 6–8 mix experimental setup, algorithm descriptions, repeated discussions of results, and a separate convex evaluation. Section 7.3 largely revisits findings from earlier subsections. The overall experimental narrative is difficult to follow.
-
Insufficient and poorly controlled experiments. The main-text experimental analysis is limited, and essential configurations are scattered across multiple appendices. More importantly, certified and uncertified methods use substantially different auditing configurations ((m=6) versus (m=4500)), making their reported lower bounds difficult to compare. The R2D experiment also uses a base model with only approximately 4% CIFAR-100 accuracy.
-
The central empirical claim is not convincingly supported. For certified methods, the auditor produces zero or very small lower bounds and does not falsify any valid certificate. Appendix F.1 shows that the auditing configuration itself imposes a severe upper limit on attainable bounds: even perfect predictions cannot produce a meaningful test of large claimed privacy parameters.
-
Limited theoretical novelty. The main theoretical arguments substantially build on established Rényi-DP inequalities and multi-canary auditing methods. The manuscript does not sufficiently demonstrate what fundamentally new capability is enabled by these adaptations.
Questions for authors
-
Why are substantially different auditor configurations used for certified and uncertified methods, and how can the resulting bounds be compared fairly?
-
Can the authors report statistical power and rejection rates for deliberately invalid certificates under a fixed computational budget?
-
How much of the looseness comes from the common-reference reduction, the hypothesis-testing bound, and the membership predictor, respectively?
5 comments
Response to reviewer waN6 (continued)
3. Certified methods and the attainable bound
Why no valid certificate is refuted. A valid certificate is a theorem, so a sound auditor cannot refute it: if our bound exceeded a correctly proved parameter, either the auditor or the proof would be wrong. The auditor should instead be judged by two things. Does it refute certificates used outside their assumptions? And does it respond when the certificate is removed? It does both.
- Certificates used outside their assumptions. The certificate of Hessian-based unlearning (Zhang et al., 2024) relies on smoothness constants and conditions that are not verified for the neural networks it is proposed for. On CIFAR-100 under uniform splitting our bound is , and on Shakespeare it is , the largest there (Table 1). These are among the largest bounds in the paper.
- Certificates removed. If model clipping is run with beyond what Theorem 4.2 of Koloskova et al. (2025) admits, the same auditor reaches the maximum attainable bound and then decays as noisy steps proceed (Section 7.1, and on CIFAR-10 in point 2 above). With the certified parameters the bound is .
The configuration limits the bound (Appendix F.1). We agree that the configuration caps the attainable bound, and that our certified audits (, ) cannot refute a claimed above about . We will state this in Section 7.1. Three points put this in context.
- The cap is not what binds for the certified methods. Model clipping gives and R2D about , both below the cap of that the same configuration reaches for uncertified model clipping. A larger cap would not change these numbers.
- The cap is set by the configuration and grows linearly in . It is at and but at , the setting we use for uncertified methods. We use for certified methods because their per-batch signal is weak, and with many candidates the auditor cannot beat chance (Appendix F.2).
- DP audits face the same limit. With trainings per hypothesis, even a perfect attack certifies an that grows only logarithmically in : at most with 500 trials at 99% confidence (Jagielski et al., 2020) and with 1,000 trials (Nasr et al., 2021). Nasr et al. (2023) report bounds close to this maximum. One-run audits are likewise capped by the number of guesses (Steinke et al., 2023; Mahloujifar et al., 2025), and Steinke et al. (2023, Figure 2) plot their bound up to perfect guessing.
What a small bound means. A bound below the claimed parameter does not show that a method unlearns. To check how close our bound gets when the truth is known, Section 8 audits convex mechanisms with exact parameters. For output perturbation at claimed , the bound is . The new Appendix G shows that, in a Gaussian model, the bound stays within a constant factor of the true parameter as grows.
4. Theoretical novelty
We agree that our proofs use established tools: Rényi-DP inequalities and the multi-canary design of one-run DP audits. Our contribution is to bring them to certified unlearning. DP auditing is well studied (Jagielski et al., 2020; Nasr et al., 2021; Nasr et al., 2023; Steinke et al., 2023; Mahloujifar et al., 2025), but existing unlearning audits return per-example completeness scores or verification signals, not a bound on a certificate's parameter (Appendix A). To our knowledge, ours is the first audit to return a high-confidence lower bound on the parameter of an indistinguishability-based unlearning definition, which can be compared directly with a published certificate and can refute it.
The adaptation is not direct, for two reasons.
- The reference model is unobservable. Certified unlearning compares the unlearned model with a reference algorithm that the auditor cannot run. Lemma 4.1 removes the reference by passing through it via transitivity, so the auditor compares two unlearned models directly.
- The guarantee is subset-level. The guarantee covers every pair of forget subsets, not neighbouring datasets. Lemma 4.2 turns the overlap of a predicted forget set with the true one into a bound on under this all-pairs constraint.
Applying the one-run -DP audit of Mahloujifar et al. (2025) to the train-then-unlearn mechanism also gives a valid bound, but it is typically two to four orders of magnitude smaller than ours (Table R1 in our response to Reviewer t67Y; e.g. versus for Hessian-based unlearning on CIFAR-100). Both audits score all candidates jointly; they differ in the guarantee they test. The -DP audit tests the record-level guarantee, which bounds the effect of changing one candidate, whereas ours tests the guarantee for every pair of forget subsets, which constrains how far apart two whole forget sets can be.
Response to reviewer waN6
Questions
1. Different auditor configurations for certified and uncertified methods
We agree that the two groups use different configurations, and that the paper should explain this more prominently. Appendix F.4 currently contains the discussion.
Why the configurations differ. Certified methods add Gaussian noise to the model weights. The distributions of the attack score with a batch included and excluded then overlap substantially, so predicting each batch separately is close to chance. The batchwise inclusion/exclusion predictor used for uncertified methods therefore gives near-zero bounds here, even on the uncertified variant of model clipping. After the first unlearning step, it gives at () and at () (Appendix F.4). We therefore use the joint sign-vector predictor for certified methods. It calibrates a separate Gaussian for every candidate sign vector and pools evidence across all forget points before committing to one. Because it needs calibration runs for every sign vector, it is feasible only for a few batches, so we use (). For uncertified methods the per-batch signal is strong, so the batchwise predictor works at (), where enumerating sign vectors is infeasible.
What the configuration changes. Lemma 4.2 holds for any predictor and any , so every reported bound remains a valid high-confidence lower bound on the -zCDP unlearning parameter. We agree, however, that the same algorithm can receive very different bounds under different configurations. On uncertified model clipping, for example, the batchwise predictor gives after the first step, whereas the joint sign-vector predictor reaches about . A bound therefore reflects both the algorithm and the auditor configuration, and bounds obtained under different configurations should not be compared directly.
The separation between certified and uncertified methods does not rely on this difference. Under the batchwise predictor used for uncertified methods, model clipping gives near-zero bounds even in its uncertified variant: at , at , and lower still at . The same predictor at gives bounds of up to on the uncertified methods (Table 1).
Changes. We will highlight this choice and its rationale more clearly in the updated version.
2. Power and rejection rates for invalid certificates under a fixed budget.
Our main uncertified case is Hessian-based unlearning (Zhang et al., 2024), proposed for deep networks. Its certificate depends on smoothness constants that cannot be verified for real networks (the authors set them as hyperparameters), so its certified level cannot be computed; we follow their algorithm and noise level. Model clipping beyond Theorem 4.2 (point 2 above) is a second, deliberately uncertified case. Budgets are fixed: runs of about one GPU-hour each for deep models, and for model clipping. A bound rejects every claim at level 5%. For Hessian-based unlearning, this rejects any claim below on CIFAR-100 (uniform split) and on Shakespeare; Table R1 (response to Reviewer t67Y) shows the same with a single run. Estimating rejection rates empirically would cost more training runs per repetition, so the new Section 4.3 (proofs in Appendix G) instead computes the power analytically in a Gaussian model with a known true parameter, for any and and in the limit (Proposition 4.4).
3. Sources of looseness.
- Common-reference reduction: we expect essentially no loss. Lemma 4.1 is the group-privacy argument of Bun and Steinke (2016, Proposition 9), which is tight for the Gaussian mechanism; in the Gaussian model of Appendix G the factor 4 is attained exactly (Proposition G.1).
- Membership predictor: we expect a large share of the gap here. Our auditor observes only model outputs, not the weights or internal representations, which may retain information that outputs miss; extending the attack to them could give larger bounds (Section 9). Even in the Gaussian model, a predictor that keeps one bit per candidate loses a factor (Remark G.6).
- The certificate itself: We believe that the upper bounds for many certified algorithms that we audit are not tight. Tighter analyses of the certified algorithms would narrow the gap from above (Section 9).
We appreciate your feedback and hope this addresses your concerns. Please let us know if anything needs clarification or if you have further questions.
Response to reviewer waN6
We thank the reviewer for their detailed review and provide responses to their questions and weaknesses below.
Critical weakness
We thank the reviewer for pointing out ways to improve the clarity of our manuscript.
1. Presentation and organization
Abstract. We would respectfully note that the abstract contains no implementation details. Apart from the auditing approach and threat model, it only names the unlearning algorithms we audit, together with their citations. One citation (SCRUB) was formatted incorrectly, and we have fixed it. We agree that the abstract could be shorter if it named the classes of methods audited (certified, Hessian-based, gradient-based and distillation-based) rather than each method.
Sections 6–8. We agree that the experimental sections mixed setup, method descriptions and results, and that Section 7.3 restated earlier findings. We have reorganized them so that every description comes before any result and each number is stated only once:
2. Experimental control
Base models for the certified methods. We agree that model clipping and R2D reach low accuracy on CIFAR-100. Model clipping was evaluated by Koloskova et al. (2025) on CIFAR-10, and we extended it to CIFAR-100 to keep every audit on the same dataset. The paper omitted the retain/forget/test (R/F/T) accuracies of model clipping on CIFAR-100; Table R2 below gives them, and we have added them to Appendix J.1. They are reasonable under adversarial splitting but close to chance under uniform splitting.
Table R2. Final R/F/T accuracy (%) of model clipping on CIFAR-100. Certified: the last row of the table in Appendix J.1.2 (C2=0.225, σ=10−3, ε=105). Uncertified: the configuration of Appendix J.1.3 (C2=5, σ=10−4).
We therefore now also audit model clipping on CIFAR-10. The setup mirrors the certified CIFAR-100 audits (Section 6.3 and Appendix J.1): a small CNN trained for 400 epochs (72.0% test accuracy), a forget pool of 4,500 points split into m=6 batches of 750, and L=500 runs. We audit two configurations, both under uniform splitting:
We audit the model after each noisy step t. In the uncertified configuration, the bound is 0.68 at step 1, the maximum attainable with m=6 and L=500, and stays there for the first 10 steps. It then decays slowly: 0.60 at step 20, 0.23 at step 40, 0.09 at step 100 and 0.003 at step 300. In the certified configuration, the bound is 0.006 after one step and 0 from step 2 on, long before the certified stopping step. R2D was evaluated by its authors on eICU and Lacuna-100 rather than CIFAR-10 (Mu and Klabjan, 2025), so we did not rerun it there.