- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
Machine unlearning updates a trained model after deletion requests but can introduce new errors on retained data, and searching over update configurations can select ones whose observed retain scores understate true population risk. The paper proposes CMUCE (Conformal Machine Unlearning Configuration Evaluation): a bounded positive prediction regret score s_ret ∈ [0,1] measuring how often an update flips a previously-correct retained prediction to an error relative to a fixed reference model; a Hoeffding–Bentkus lower-tail inversion for a fixed-candidate retain-risk upper bound (Prop. 4.1); Bonferroni/Holm family-wise error control over a candidate grid to preserve the retain guarantee after selection from shared calibration data (Prop. 4.2); and intersection with a separately-specified deletion-efficacy set. Theorem 5.1 states conditions (anchor quality, gradient alignment, local score transfer) under which counterfactual-guided candidates tighten the certificate; Theorem 6.1 adds a √(2ρ) margin under a Hellinger shift budget H(D,Q) ≤ ρ. Validation spans CIFAR-100 and CUB-200 (ResNet-18, with ViT/DeiT transfer), AG News (DistilBERT), and Adult/German, comparing CF-guided + CMUCE against seven unlearning baselines on a 20-class deletion task (Table 1), plus budget/noise/backbone and runtime studies.
Critical strengths
- The selection-valid retain guarantee is the right primitive, correctly executed. The paper identifies a real failure mode — configuration search inflating apparent retain performance — and controls it with a finite-sample, distribution-free family-wise construction (Prop. 4.2) that requires no independence among candidate scores and correctly observes that intersecting with the deletion-effective set can only shrink the accepted set. This is consequential because it is the paper's genuine, defensible deliverable and holds up under scrutiny.
- Honest exposure of the certificate–reality gap. Figure 2 and Table 1 report the HB upper bound and the independent-test retain regret side by side, and the text states plainly that the UCB stays above the test proxy (≈ 2×) and that the CUB certificate ties a baseline rather than beating it. This candor is consequential because it keeps the core "certified" claim defensible exactly where the empirical edge is thin, and lets a reader locate the real contribution without reverse-engineering it.
Critical weaknesses
- The word "certified" in the title and abstract claims more than the theorems deliver, at the two points that distinguish the paper. The abstract's "under a Hellinger shift budget ρ, a margin of √(2ρ) extends certification to the deployment distribution" is, in Thm 6.1, a bound that holds only if H(D,Q) ≤ ρ — and the paper provides no procedure to certify ρ, conceding that estimating the radius needs external evidence. The deployment "certificate" is therefore an assumption-conditional bound, not a guarantee the method can issue on real data. Likewise "certified improvement" (Thm 5.1) is a sufficient-condition result resting on M_ν>0, c_s>0, gradient alignment, and a local score-transfer condition, none of which is shown to hold for the configurations CMUCE actually selects in Table 1. Since "certified," applied to deployment and to the counterfactual-guidance benefit, is the paper's headline differentiator, the gap between the word and the theorems is material.
- The empirical superiority rests on a single run with no variance, and the flagship advantage is a tie or within plausible noise. Table 1 reports one number per cell at a fixed seed (42) with no std or confidence interval. The claimed advantages are small: the CIFAR UCB edge is .042 vs. .045/.048, and on CUB the UCB (.096) ties ℓ₁-Sparse; retain-regret differences of .002–.007 over a 10% test split with no reported n or event count are not shown to exceed sampling noise, and the deletion-audit FA (5.6/7.3) is not best (ℓ₁-Sparse 5.2/6.7; Retrain 0.0) but merely under the threshold. A central contribution billed as empirical improvement is thus demonstrated only for one seed, leaving the comparative claims unestablished.
Questions for authors
- Please report Table 1's R and UCB columns as mean ± std over multiple seeds / calibration splits, with the test-split n and event count behind each R. The claimed edges (.002–.007) are smaller than plausible single-seed noise; without variance the "lowest retain risk" and "tightest CIFAR UCB" claims cannot be told apart from chance.
- For the configurations CMUCE actually selects in Table 1, do the Thm 5.1 conditions (M_ν>0, c_s>0, gradient alignment, the Eq. 13 score-transfer condition) hold? Please show a diagnostic in at least the controlled settings where they can be measured. If they are not verified, "certified improvement" should be restated as a sufficient-condition theorem that is not demonstrated on the runs.
- How would a practitioner obtain or bound ρ = H(D,Q) for a real deployment distribution? If ρ cannot be estimated from available data, the abstract/title phrase "extends certification to the deployment distribution" overstates Thm 6.1 — will you qualify it to "conditional on an assumed Hellinger budget," or supply a procedure that certifies ρ?
- CF-guided uses N_cf=50 counterfactual generations (an extra ~8.4 s and an extra optimization signal) that the baselines do not receive. Is the Table 1 comparison matched on total compute and on the information available to each method? Please add a compute-matched or signal-matched baseline; otherwise the retain-risk edge cannot be attributed to the method rather than to extra tuning.
11 comments
2.In Section 5 of the revised manuscript, we have titled Theorem 5.1 “Sufficient conditions for one-step certificate ordering.” The theorem describes a particular comparison between two updates from the same starting parameter. Both update directions are evaluated at that starting point. The resulting certificates use the same calibration observations and confidence level.
The guarantee applies under the stated assumptions on anchor quality, gradient alignment, smoothness and score transfer. These assumptions yield a probability bound for . For its application to the Table 1 models, the required uniform population bounds remain explicit assumptions. In particular, establishing and requires bounds that hold across the relevant population.
The empirical role of the diagnostics is to characterize the observed relationship between the optimization loss and the retain score. Appendix E.10, Table 9, reports the expanded results below. Each vision or text grid contributes 156 paired standard/CF updates, and each tabular grid contributes 52 pairs. These counts refer to paired diagnostic observations.
| Dataset / task | Backbone | Valid-anchor fraction | Gradient cosine | Surrogate gap | Same-sign rate | Fitted slope |
|---|---|---|---|---|---|---|
| CIFAR-100 class | ResNet-18 | 0.72 ± 0.03 | 0.27 ± 0.04 | 0.068 ± 0.009 | 79.5% | 0.18 |
| CIFAR-100 class | ViT-Tiny | 0.69 ± 0.04 | 0.23 ± 0.04 | 0.059 ± 0.010 | 76.3% | 0.17 |
| CIFAR-100 class | DeiT-Tiny | 0.70 ± 0.03 | 0.25 ± 0.04 | 0.063 ± 0.009 | 77.6% | 0.17 |
| CUB-200 class | ResNet-18 | 0.66 ± 0.04 | 0.23 ± 0.05 | 0.074 ± 0.011 | 76.3% | 0.15 |
| CUB-200 class | ViT-Tiny | 0.63 ± 0.04 | 0.20 ± 0.05 | 0.065 ± 0.012 | 73.7% | 0.14 |
| CUB-200 class | DeiT-Tiny | 0.64 ± 0.04 | 0.21 ± 0.04 | 0.069 ± 0.011 | 75.0% | 0.15 |
| AG News | DistilBERT | 0.75 ± 0.03 | 0.29 ± 0.04 | 0.048 ± 0.007 | 81.4% | 0.19 |
| Adult | 3-layer DNN | 0.78 ± 0.03 | 0.31 ± 0.04 | 0.055 ± 0.008 | 82.7% | 0.21 |
| German | 3-layer DNN | 0.71 ± 0.04 | 0.24 ± 0.05 | 0.052 ± 0.009 | 76.9% | 0.17 |
Yield, cosine and surrogate-gap entries report diagnostic means ± SD. Sign agreement is 73.7%–82.7%, and the fitted slopes are positive across all nine settings. These measurements provide empirical support for an association between surrogate and score changes. The fitted slope summarizes that observed association. The theorem's specifies a uniform population lower bound. The average cosine similarly describes the observed alignment, while the theorem requires its stated alignment and margin conditions.
The roles of the two evaluations are also explicit in the revised manuscript. Table 1 compares fixed configurations and gives their nominal bounds. The 52-candidate selection analysis applies the deletion screen and the family-wise retain-risk tests to decide which candidates qualify for deployment.
The central certification result is established by Propositions 4.1–4.2. It controls retain risk after selection under the conditional-i.i.d. and calibration-separation assumptions. Candidate-wise tests may share data and may be dependent. This guarantee holds independently of the additional conditions used to explain one-step certificate ordering.
3.The revised Abstract describes the shift extension in plain language. Section 6 specifies the Hellinger budget as an input that requires external justification for the intended deployment. Theorem 6.1 gives a sensitivity bound conditional on this assumed budget for the full evaluation-unit distribution.
Under the normalized convention used in the manuscript, the additional risk margin is times . For the fixed bounded retain score and , $ \left|R_Q(\lambda)-R_D(\lambda)\right| \le \operatorname{TV}(D_Z,Q_Z) \le \sqrt{2}H(D_Z,Q_Z) \le \sqrt{2}\rho.$ The distance inequality is recorded in Gibbs and Su, Section 3, Eq. (8), now cited in Section 6 and Appendix D.1 of the revised manuscript. Their Section 2 uses the unnormalized distance . Let be the family-wise source-calibration error budget. The simultaneous source-certification event has probability at least . On this event, the inequality gives the following bound for every candidate in the declared family: $ H(D_Z,Q_Z)\le\rho \Longrightarrow R_Q(\lambda)\le\min\{1,a^{\mathrm{sim}}_{\lambda,D}+\sqrt{2}\rho\}. $ This makes the effect of a chosen budget explicit. When , the headroom gives the admissible-radius boundary. The sufficient rule accepts a justified budget strictly below that boundary.
An external procedure could supply a valid upper bound on the radius with error probability . Combining this with the source-calibration error budget gives confidence at least . Bonferroni source calibration allocates to each candidate. Another practical option is direct recalibration on an independent i.i.d. labeled sample from . The candidate family is frozen before that calibration, with the same fixed bounded score and appropriate family-wise control.
We retain "Certified" in the title because it refers to the retain-degradation control of Propositions 4.1–4.2, which holds after selection under the stated calibration assumptions; the shift and counterfactual-guidance results are now presented as conditional and sufficient-condition results, respectively.
Thank you for your careful review. We have revised the manuscript to address your questions and make the evidence for each conclusion easier to assess.
1.Table 1 of the revised manuscript reports mean ± sample SD over three seeds. The R and nominal HB results are reproduced below, with δ=0.10 for each fixed candidate. Appendix E.9 gives exact calibration and test counts in Tables 6–7 for the key CF-guided versus ℓ₁-Sparse comparisons on both datasets, together with CIFAR-100 retraining. Table 8 reports the corresponding summaries.
Each reported CIFAR-100 run uses 4,800 retained calibration examples and 4,800 retained test examples. Each reported CUB-200 run uses 1,060 examples in each split. Here k counts examples that the reference predicts correctly and the updated model predicts incorrectly. The denominator n includes the entire retained split, so test regret is ktest/ntest. We compute nominal HB from kcal and ncal using Proposition 4.1 at δ=0.10. The integer count enters the binomial tail directly.
CIFAR-100:
CUB-200: