acceptodds
Under review as a conference paper at ICLR 2027

Label-Level Certified Untraining for Privacy Guarantees in Deep Neural Networks

Abstract

Untraining removes the influence of specific training data (the forget set) from a model without retraining from scratch, a practical necessity for privacy. Yet no method guarantees privacy for deep neural networks (DNNs), where untraining matters most due to excessive costs: heuristic methods offer only empirical evidence, and certified methods, which draw on differential privacy (DP), yield vacuous guarantees as model size grows. We introduce -certification, the first label-DP-style formalization of untraining, which certifies the model's confidence scores on the forget set rather than its parameters, keeping guarantees meaningful at scale. We then propose certified untraining via prediction calibration (CUP), which calibrates these scores toward a retraining-free reference, the original model's confidences on unseen data. CUP transfers across settings, even without access to the remaining training data, by leveraging this retraining-free reference. Extensive ablations show that CUP can yield privacy guarantees without compromising untraining performance and model generalization. On ViT-Large, a scale unexplored by certified work, CUP guarantees that any test distinguishing untrained from retrained forget-set confidences errs at least of the time (random guessing: ).

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
untraining, unlearning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_Sk6MOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper

Critical strengths

The paper use a novel concept of using the confidence of the model's output in order to untrain / unlearn. The paper use a novel definition that yields a DP-style guarantees. The paper shows an upper bound on ε\varepsilon and δ\delta on the DP-style guarantees. In addition, the paper backs its claims with various experiments.

Critical weaknesses
  1. I'm concerned that the paper is mostly AI generated. Even if the main ideas and proofs are of the authors, the writings seems mostly AI with little to no human intervention. This makes the paper really hard to understand. For example, in the Introduction there are 4 lines of introduction before stating what is missing from current work. At this point, I still have no idea what is the current work, I even don't know what is the difference between unlearning and untraining. Another example is mentioning differential privacy without ever citing [1]. Another example is the usage of the word "certify" in many places which is a bit unordinary.

  2. The paper use many undefined terms, such as f-divergence, DP mechanisms for privacy-preserving predictions (which seems very relevant to the paper)

  3. The paper seems a bit of a mess, where some of the definition and all the theorems are deferred to the appendix. This makes the paper really hard to follow. I can't tell what parts of the algorithms are proven and what are only empirical.

Giving all this, it is hard for me to assess the idea itself.

[1] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis.

Questions for authors
  1. In Definition 2, what is the purpose of the partition? Why not just use [K] (the class of labels)? Are the distribution over the output of the model or over its confidence? it is not clear to me. Lines 124-125 make me think that the distribution is over the output.

  2. what is f-divergence (line 128). It is never defined and never really used anywhere.

  3. In algorithm 1, only CUP-DF is presented with a short sentence about CUP algorithm. Consider adding the CUP part to the pseudocode itself with a comment what part is only for CUP algorithm.

3 comments

I thank the authors for their response in the general comment. The rebuttal included too many changes which makes the paper very different from the version that was initially submitted. I encourage to authors to rewrite the paper to be easier to follow and submit to another conference. I would keep my score, good luck.

We revised the paper focusing on improving the presentation. The revisions include additions, clarifications and moving parts from Appendix B (Preliminaries from Statistics and Information Theory) to the main manuscript. Lines from the revised paper that refer to the reviewer's comments are denoted here as (xxx-yyy). We accept that the presentation could be improved in some parts and we refer the reviewer to the revised paper and the brief summary of our revisions (shared as a comment to all the reviewers).

We do not accept the reviewer's self-reported "careful reading", mostly based on: (i) missing paper summary, (ii) no comments even for the algorithmic/experimental contributions of the paper, and (iii) contents of Question 1. We claim full responsibility and ownership over this paper, the AI use is explicitly reported in (542-549). We appreciate the reviewer's comment on the originality of the theoretical results, and his/her effort/time for pointing out parts that could enhance the presentation of the paper.

  1. Additions and clarifications discussed in Weakness 1:
    • (030-037): Further details about the the difference between untraining (unlearning for privacy) and unlearning for concept removal, which were previously included in the Appendix A (Reltated Work). New experiment and analysis in 498-518 provide further intuition.
    • We cite early the DP paper of Dwork et al. in line 044. Previously, the reference to this paper was indirect coming from prior certified work in Gap 1, that adapts formulation from this to the unlearning/untraining task. We also cite this paper in 183, replacing the reference to DP-SGD from Abadi et al. which adapts DP formulation to machine learning tasks. We accept that the fundamental paper of Dwork et al. is more recognizable and facilitates readability.
    • (038-051): Intuition/Clarification on the difference between certified and heuristic untraining. This intuition is later formalized in Sec. 2 (132-160). Related work (i.e., prior untraining certificates) remains as part of Gap 1. Further details are in in Appendix A (Related Work), the formulation of prior (121-131).
    • We replace instances of the word "certify", that refer to our TV certificate or prior certified work, with descriptive phrases such as "yields a certificate" or "provides privacy guarantees". We do not accept that the word "certify" is odd in the context of certified work, but it remains more ambiguous than descriptive phrasings.
  2. We couldn't find any other terms than the following that could be considered unknown:
    • f-divergence: In 210 we add the reference to the Duchi's "lecture notes on information theory", which we broadly cite in the appendix to refer to fundamental results and preliminaries from information theory. Moreover, we explicitly mention that the Total Variation distance is an f-divergence to avoid any confusion on why it is relevant to our paper. The term is used once in the paragraph (208-215) which explains why quantization (i.e., binning) is needed because this refers to f-divergences in general, not just TV. We accept that the reference add to the paper as Duchi's definition provides a more rigorous analysis on why quantization is needed.
    • DP mechanisms for privacy-preserving prediction: the term was used once next to the citation "Dwork and Vitaly, Privacy-Preserving Prediction (2018)". It is not fundamental for the paper, it was used only for intuition. We wanted to link the DP literature with the certified work in untraining. Specifically, the DP literature has examined privacy guarantees in both the model space and the output space, while in certified untraining the output space remains underexplored: that is what we study here to address Gap 1. Now, in our revised paragraph 182-188, we use more recognizable papers that refer to these concept to facilitate intuition. And build intuition on concepts that are more recognizable (global vs local guarantees).
  3. In Appendix B we include known results, either fundamental (from academic textbooks) or from recent papers. We had them in the appendix for the reproducibility of the theoretical claims. We accept that this may hampered readability, thus we transfer some of them along with an analysis for intuition in Sec. 2 (132-161).
  4. The partition (i.e., quantization/binning) is not a design choice, but a requirement (see Cover's book in our references (Ch 11, (p. 294)): "This arguement can be also extended to continuous distributions using quantization"). The reference that we now added for f-divergence (Duchi's lecture notes), upon your righteous request, presents a more rigorous analysis on why quantization is needed. In 218-215, we present a more intuitive justification, and the revision aimed to further facilitate intuition.
  5. We included the pseudocode of the algorithm in Sec. 4 (361-376) and moved the data-free algorithm to the Appendix D.

Thank you for your review. Your concerns about the presentation played a central role in our revision, while the original contributions remain intact:

  • Unchanged: the TV certificate and its decomposition, the theoretical results and their proofs, the method, and the experimental results.
  • Added: one experiment supporting the analysis of our assumption (498-517).

We apologize for the late response. We considered all comments very carefully, and chose to first revise the paper and then write comprehensive answers. We particularly focused on your concerns about the presentation, so that you can already assess a revised paper with improved presentation, rather than promises of changes for the camera-ready version.

All changes respond to concerns raised by the reviewers. We hope that the revisions on the presentation facilitate a clearer assessment of our contributions. Your scores on Soundness and Informativeness strongly motivated us to improve the presentation within the limited time of the rebuttal. We would greatly appreciate it if you could revisit the revised paper during the remaining discussion. Thank you, and all the best to you too!

Reviewer_asbJOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies the problem of certified untraining: removing the effect of a forget set from a trained network without retraining from scratch. The authors argue that the current certified methods provide guarantees in the parameter space and for deep networks these guarantees become meaningless since the privacy budgets are huge (ε in the hundreds or even more). They propose certifying something more narrow: the distribution of true-label confidence scores on the forget set.

Critical strengths
  • Splitting the bound into four parts shows clearly what the method controls and what depends on data or assumptions.

  • The method is simple, scales to ViT-Large, and runs 3–27x faster than retraining.

  • CUP gets the best average gap in most settings and stays stable even without retain data.

  • The synthetic calibration experiments show the method can still work when no held-out real data is available.

Critical weaknesses
  • The guarantee does not cover single samples. δtv\delta_{tv} compares a reference histogram with the histogram of all confidence scores on the forget set. If the confidence scores are shuffled between forget samples, the certificate is unaffected. Thus, a model could still pass, while having high confidence on exactly the samples that should be forgotten. Privacy is about data of specific individuals, so an assurance on the average shape of a histogram misses the point.

  • I also feel that it is not a proper DP style guarantee. CUP does not contribute any noise, so the only randomness in the guarantee is which “forget” sample is chosen. The bound is based on an attacker seeing one confidence score from an unknown sample, but any real attacker can check every forget sample, so the guarantee is much weaker than it appears. This is why it is not fair to compare it with DP bounds in model space in Table 1.

  • The bound is assumed (δcon\delta_{con}, δdom\delta_{dom}) and are not proven. δcon\delta_{con} requires the retrained model, which is not available in practice, the paper assumes it is small. δdom\delta_{dom} is estimated from one empirical value without any confidence bound. Thus the final certificate is based on assumptions that a user cannot check.

Questions for authors

I have my questions as part of the weaknesses

5 comments
AuthorsOpenReview ↗

Answer to Weakness 1

Thank you for your careful review and appreciation of our contributions. We have submitted the revised paper. Lines (xxx-yyy) refer to the revised version, including the additions, clarifications, and corrections motivated by your comments.

Our analysis focuses on the population level, following most prior unlearning/untraining works, which use population-level MIAs to assess privacy for the forget data as a whole rather than per example. We state this explicitly in Limitations & Future Work (534-539). However, the TV certificate could be extended to the per-example setting as well:

  • Now, in the population-level setting, the confidence score is defined as the probability of the true label c((x,y);θ):=p(y∣x;θ)c((x,y); \theta) := p(y \mid x ; \theta), i.e., the model is fixed and the randomness, required for the empirical confidence-score distribution, comes from (x,y)∼D(x,y)\sim \mathcal{D}. In the per-example setting, the confidence score could be defined as c(θ;(x,y)):=p(y∣θ;x)c(\theta;(x,y)):=p(y \mid \theta; x). In this case, the data sample is fixed and the randomness comes from the models, i.e., θ\theta is drawn from the distribution induced by the (un)training algorithm, e.g., over random seeds.
  • Let us define the total number of these models as nθn_\theta. Now the nθn_\theta plays the role of nunsn_\text{uns} in the Eq. 8. You need a sufficiently large number of nθn_\theta so that δetp\delta_\text{etp} does not inflate significantly. Each of these nθn_\theta models requires a separate (un)training run, which is computationally intensive for large models.
  • That is why we focus on the population-level setting in this paper. Our contributions are not only theoretical, we also experiment on large models, such as ViT-Large. This may be the reason that most of the unlearning/untraining papers use population-level MIAs for evaluation. For example, none of the baselines in Table 3 used per-example attacks for evaluation. Nevertheless, the natural extension of the TV certificate to the per-example setting motivates future work that can discuss these trade-offs as well.
AuthorsOpenReview ↗

Answer to Weakness 2

  1. We renamed our method from CUP (Certified Untraining via Prediction calibration) to PUP (Principled Untraining via Prediction calibration), following concerns that “certified” could imply that the algorithm itself provides the guarantee.

    • The contributions remain intact: Certification comes from the TV certificate (Gap 1), and alignment with real-world requirements such as adaptability, low sensitivity to hyperparameters, no access to the retain set (Gap 2) comes from the algorithm, PUP.
    • We name it "principled" because by design it optimizes the TV certificate, and leverages quantities of the TV certificate for adaptive untraining (377-392 and 428-431). Evaluations indicate that this mechanism supports its performance (462-475). In combination, PUP and the TV certificate provide state-of-the-art results in jointly maximizing privacy and utility, together with certification (privacy guarantees).
  2. Thank you for your careful review, which helped us identify an imprecision in Definition 2 (199-207) that understated the scope of our TV certificate. We corrected it.

    • The TV certificate considers an attacker that views all the binned confidence-scores. It refers to the complete histogram, i.e., the empirical confidence-score distribution. That follows from the definition of the total variation distance (Eq. 5, 220-225). Your valid concern arose from Definition 2, which we corrected (199-207): the measurable sets are all unions of the bins. Definition 2 serves as the explanatory link between prior DP-style untraining formulations and our TV certificate, which is defined directly through Eq. 5. Therefore, the subsequent analysis and the results remain intact.
  3. We revised the caption of Table 1 (054-060) to avoid any misinterpretation. It now states explicitly: "The two approaches are not directly comparable, since they address different attack surfaces and hence different hypothesis tests; the comparison concerns only whether the guarantees are vacuous or not."

AuthorsOpenReview ↗

Answer to Weakness 3

Our revisions facilitate a clearer analysis of our assumption in lines 244-294. This analysis includes a new experiment presented in lines 498-517.

To the best of our knowledge, all prior untraining certificates for DNNs require quantities that are not available in the real setting (see 093-096, and 820-831), so this is not a requirement for "untraining certification". **Our advantage is that our non-computable quantities (δdom\delta_\text{dom}, δcon\delta_\mathrm{con}) are eliminated under a ubiquitous assumption, that can be largely ensured in practice.

Example from prior work for comparison: CNS, which reports the tightest privacy bound among prior certificates for DNNs, requires the minimum eigenvalue of the loss Hessian. This value is intractable for DNNs, so it is treated as a tunable hyperparameter, i.e., a practitioner defines the minimum eigenvalue arbitrarily. This is a common problem in prior work (named in Gap 2 (093-096), and with more detail in Related Work (820-831)).

Why our assumption is largely ensured in practice? Our assumption is: the unseen (during training) data (e.g. the test set) are sampled from the data-generating distribution of the forget data (Eq. 7). This is the fundamental i.i.d. assumption. Established evaluation protocols, including MIAs and Test Accuracy, are based on this assumption. In practice, this is largely ensured by using the same protocol to collect and annotate the data, and then randomly select the test data as a held-out split. This is the established protocol in machine learning pipelines, which follows that our assumption is largely ensured in practice.

Reviewer_u1XxOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper proposes a narrower form of certified unlearning than the usual model-space definition. Rather than compare distributions over retrained and untrained parameters, it compares binned distributions of true-label confidence scores on forget examples. The proposed CUP method fine-tunes the original model so that its forget-set confidence histogram matches the original model’s histogram on held-out calibration data. The TV bound is split into empirical, finite-calibration, domain-shift, and concept-drift terms. The paper reports results on CIFAR and TinyImageNet with ResNets and ViTs.

Critical strengths
  1. The paper is clear that it is narrowing the attack surface. The calibration construction is simple and scalable, and the empirical treatment of the finite-reference term is careful. CUP may be useful as a practical confidence-calibration unlearning heuristic.

  2. The experiments cover larger vision models than much of the certified-unlearning literature, and the retain-data-free variant is a useful practical test.

Critical weaknesses
  1. The advertised certificate includes quantities that are not available in the real setting. Most notably, δcon\delta_{\mathrm{con}} compares against the unknown retrained model. Saying that the forget set is small and i.i.d. does not prove that this distance is small; Table 5 merely measures it where retraining is available. The same concern applies to the assumptions behind δdom\delta_{\mathrm{dom}}. The practical certificate is therefore conditional on unverified assumptions, not something CUP can certify on its own.

  2. The interpretation of the TV guarantee seems too broad. Definition 2 bounds the distribution of one binned true-label confidence score. An attacker who sees the whole vector or multiset of forget-set scores gets many observations, and the TV distance between the resulting joint distributions can be much larger. The paper does not provide a joint-distribution bound. Nor does the definition control predicted labels, other probability coordinates, per-example score associations, losses, or white-box access. The statement that any test observing forget-set confidences must be close to random guessing does not follow from the stated marginal-histogram guarantee.

Questions for authors
  1. Please define the adversary’s observation exactly and prove the lower bound for that full observation. What bound applies when the adversary receives the complete forget-set histogram or ordered score vector rather than one sampled confidence score?

  2. In deployment, what computable high-probability bound replaces δcon\delta_{\mathrm{con}}? A stability theorem with explicit assumptions would address this. Otherwise, I think the result should be described as a conditional or empirical confidence-distribution guarantee, rather than a certified privacy guarantee.

4 comments
AuthorsOpenReview ↗

Answer to Weakness 1 and Question 2

Thank you for the constructive feedback which motivated clarification and additional experiments. We have submitted the revised paper.

Answer to Weakness 1

Our revisions facilitate a clearer analysis of our assumption in lines 244-294.

To the best of our knowledge, all prior untraining certificates for DNNs require quantities that are not available in the real setting (see 093-096, and 820-831), so this is not a requirement for "untraining certification". Our advantage is that our non-computable quantities (δdom\delta_\text{dom}, δcon\delta_\text{con}) are eliminated under a ubiquitous assumption, that can be largely ensured in practice.

Example from prior work for comparison: CNS, which reports the tightest privacy bound among prior certificates for DNNs, requires the minimum eigenvalue of the loss Hessian. This value is intractable for DNNs, so it is treated as a tunable hyperparameter, i.e., a practitioner defines the minimum eigenvalue arbitrarily. This is a common problem in prior work (named in Gap 2 (093-096), and with more detail in Related Work (820-831)).

Why our assumption is largely ensured in practice? Our assumption is: the unseen (during training) data (e.g. the test set) are sampled from the data-generating distribution of the forget data (Eq. 7). This is the fundamental i.i.d. assumption. Established evaluation protocols, including MIAs and Test Accuracy, are based on this assumption. In practice, this is largely ensured by using the same protocol to collect and annotate the data, and then randomly select the test data as a held-out split. This is the established protocol in machine learning pipelines, which follows that our assumption is largely ensured in practice.

Answer to Question 2

This answer follows our answer to weakness 1 focusing on δcon\delta_\text{con}, i.e., the term of our TV certificate which includes the optimally untrained model θ⋆\theta^\star in its definition. In our revised paper, it is covered in lines 278-288 and backed up by a new experiment and finding in lines 498-517.

By definition, optimal untraining ensures privacy for the forget data, and preserves model utility (i.e., the generalization capacity of the original model). δcon\delta_\mathrm{con} captures the TV distance between the confidence-score distributions induced by the original and the optimally untrained model on the data-generating distribution. I.e., δcon\delta_\text{con} is zero if and only if optimal untraining does not hamper generalization, which holds by definition. Hence, δcon=0\delta_\mathrm{con}=0 by definition. It doesn't require a high-probability upper-bound.

New experiment + finding: Are the parameters of the model retrained from scratch those of the optimally untrained model, θ⋆\theta^\star? No, they are only an estimation of θ⋆\theta^\star (see 498-517), used for empirical evaluation. Our TV certificate does not require the retrained model to assess generalization. Instead, generalization is captured by δemp\delta_\text{emp} based on the original model, which is available in real-world scenarios (see 329-345). Hence, in our TV certificate θ⋆\theta^\star is not estimated by the retrained model. That is why the TV certificate does not require any further assumptions (under which the retrained model is a good estimate of the optimally untrained model θ⋆\theta^\star, and δcon=0\delta_\text{con}=0, by definition. That is why we apply the triangle inequality in the first place, i.e., to isolate the non-computable terms.

AuthorsOpenReview ↗

Answer to Weakness 2 and Question 1 (part 1)

Thank you for your careful review, which helped us identify an imprecision in Definition 2 (199-207) that understated the scope of our TV certificate. We corrected it, and submitted the revised paper. Also your review motivated clarifications/additions into Section 2 (132-161), Section 3.2 (319-328) and Section 6 (534-539).

The TV certificate refers to the complete histogram, i.e., the empirical confidence-score distribution. That follows from the definition of the total variation distance (Eq. 5, 220-225). Your valid concern arose from Definition 2, which we corrected (199-207): the measurable sets are all unions of the bins. Definition 2 serves as the explanatory link between prior DP-style untraining formulations and our TV certificate, which is defined directly through Eq. 5. Therefore, the subsequent analysis and the results remain intact.

The TV certificate for a specific attack surface is stronger than any attack (e.g., MIA) that views the same attack surface. You can read "attack" as "a hypothesis test" and "same attack surface" as "same hypotheses". This is the general result of our theoretical analysis. Now, in our revised paper, the proof is in the main manuscript, Sec. 2 (132-161).

  1. In 132-161, we link DP and TV explicitly, and prove (based on fundamental results, which were already included in the Appendix) why the respective TV yields an upper bound on the maximum advantage (compared to random guessing) of any attacker, while a MIA only provides a lower bound.

  2. In 216-249, we specify the aforementioned result on confidence scores. Thus, the TV certificate for binned confidence scores is stronger than any attack that views binned confidence scores. We say it explicitly in 215 and 353. Please, remember "binned" for the point 5.

  3. A TV certificate for confidence scores is not comparable to black-box MIAs that consider other statistics, such as loss. We say that explicitly in 534-539. However, the TV certificate could be extended to attack surfaces of other black-box MIAs, such as the loss values. In this case, the TV certificate is computed over distributions of the negative logarithm of the confidence score (−log⁡c-\log c), i.e., the cross-entropy loss.

  4. White-box MIAs are outside the scope of our certificate. This is the attack surface considered in prior (model-level) certificates that cannot scale to DNNs. We make this clear throughout the paper. We shift focus on the output space to yield meaningful guarantees. We report this trade-off: "broader attack surface and vacuous guarantees" vs "restricted attack surface and meaningful guarantees" in the Abstract (018-020) and in the Limitation (532-534).

AuthorsOpenReview ↗

Answer to Weakness 2 and Question 1 (part 2)

  1. Similarly, the TV certificate could be extended to the broader attack surface that captures the whole probability vector, but this entails trade-offs, which are captured by the δetp\delta_\text{etp} term of our TV certificate. We describe them explicitly in (319-328).

    • The TV certificate considers binned distributions. You need a sufficiently large number of bins mm so that the induced error from binning will not significantly affect your empirical measurement (e.g., δemp\delta_\text{emp}, see ablations in Table 10). The number of required bins increases exponentially with the dimension of the empirical distribution. I.e., if you need mm bins for the univariate distribution (e.g., confidence-score distribution), then you need mKm^K bins for the K-variate distribution over prediction probabilities of all class labels.
    • Subsequently, more bins require more unseen data samples (see Eq. 8). This is the sampling error that is captured by the δetp\delta_\text{etp} term of our TV certificate. If the total number of the unseen data (nuns)(n_\text{uns}) is too small for the given number of bins, then δetp\delta_\text{etp} inflates, and subsequently the TV certificate inflates. In simple terms, the TV certificate jointly reflects the empirical measurement (δemp\delta_\text{emp}), and how much you should trust it (captured by δetp\delta_\mathrm{etp}).
    • This is another advantage of our TV certificate compared to attacks, such as MIAs. The MIA we used for empirical evaluation (from LoTUS, SSD) does not capture the sampling error, which may play a critical role. For example, consider that with the same number (nunsn_\text{uns}) of validation data (i.e., non-members of the training set), you train one classifier to discriminate members from non-members, in two settings. In the first setting, you consider only the confidence score, and in the second one all KK prediction probabilities. The second one refers to a broader attack surface, but if nunsn_\text{uns} is too small and the classifier underfits, it gives a false sense of privacy. In contrast, the TV certificate inflates through δetp\delta_\text{etp} and signals that the estimate is unreliable.
    • Overall, the TV certificate could be extended to the broader attack surface that considers all KK classes, while capturing in each formulation the requirements for such an extension.
  2. All the aforementioned discussion was about population-level attacks (e.g., MIAs). We explicitly mention this in 534-539. However, the TV certificate could be extended to the per-example setting as well, but this also entails trade-offs.

    • Now, in the population-level setting, the confidence score is defined as the probability of the true label c((x,y);θ):=p(y∣x;θ)c((x,y); \theta) := p(y \mid x ; \theta), i.e., the model is fixed and the randomness, required for the empirical confidence-score distribution, comes from (x,y)∼D(x,y)\sim \mathcal{D}. In the per-example setting, the confidence score could be defined as c(θ;(x,y)):=p(y∣θ;x)c(\theta;(x,y)):=p(y \mid \theta; x). In this case, the data sample is fixed and the randomness comes from the models, i.e., θ\theta is drawn from the distribution induced by the (un)training algorithm, e.g., over random seeds.
    • Let us define the total number of these models as nθn_\theta. Now the nθn_\theta plays the role of nunsn_\text{uns} in the 5th point. You need a sufficiently large number of nθn_\theta so that δetp\delta_\text{etp} does not inflate significantly. Each of these nθn_\theta models requires a separate (un)training run, which is computationally intensive for large models.
    • That is why we focus on the population-level setting in this paper. Our contributions are not only theoretical, we also experiment on large models, such as ViT-Large. This may be the reason that most of the unlearning/untraining papers use population-level MIAs for evaluation. For example, none of the baselines in Table 3 used per-example attacks for evaluation. Nevertheless, the natural extension of the TV certificate to the per-example setting motivates future work that can discuss these trade-offs as well.
AuthorsOpenReview ↗

Regarding Strength 1

We renamed our method from CUP (Certified Untraining via Prediction calibration) to PUP (Principled Untraining via Prediction calibration), following concerns that “certified” could imply that the algorithm itself provides the guarantee.

  • The contributions remain intact: Certification comes from the TV certificate (Gap 1), and alignment with real-world requirements such as adaptability, low sensitivity to hyperparameters, no access to the retain set (Gap 2) comes from the algorithm, PUP.
  • We name it "principled" because by design it optimizes the TV certificate, and leverages quantities of the TV certificate for adaptive untraining (377-392 and 428-431). Evaluations indicate that this mechanism supports its performance (462-475). In combination, PUP and the TV certificate provide state-of-the-art results in jointly maximizing privacy and utility, together with certification (privacy guarantees).

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions in the updated manuscript.

Our initial contributions remain intact; the revision clarifies them, corrects two imprecisions, and adds results.

Key changes: (i) we corrected Def. 2 (199-207); (ii) the TV certificate requires a single assumption, not two (251-294, 489-517); (iii) we renamed CUP to PUP (359-368); (iv) we give intuition (038-051) and a formal analysis (132-160) of why certificates upper-bound the advantage of any attacker, while MIAs only lower-bound it.

Sec, 1:

  • Clarification (032-037): We now delineate untraining from unlearning in the introduction (previously only in the appendix), so the problem is clear from the start.
  • Clarification (038-051): Intuition, from hypothesis testing, on why a certificate is superior to an MIA score.
  • Clarification (Table 1): The caption now states that the two approaches address different attack surfaces; we compare only whether their guarantees are vacuous.

Sec. 2:

  • Addition (132-160): A direct analysis of why certificates upper-bound the advantage of any attacker that tests the same hypotheses, while MIAs provide only a lower bound. This makes explicit what the TV certificate guarantees and why MIAs cannot replace it. It builds on known theoretical results (from two textbooks and a recent proposition for Total Variation-Differential Privacy) already included in the appendix (copied from the sources) and properly cited. To our knowledge, it was missing from prior untraining work; we frame it as a secondary contribution.

Sec. 3:

  • Correction: Definition 2 (199-207): We corrected an imprecision, which rightly raised the reviewers' concerns: the measurable sets are all unions of the bins, so the TV certificate captures the whole histogram of binned confidence scores. The TV distance in Eq. 5, on which all results build, was already correct; Def. 2 serves only exposition, linking prior formulations to ours.
  • Clarification: We present the TV distance in both formulations (supremum and summation) and gather all theory on the TV certificate in Sec. 3, so the main text shows what is proven.
  • Correction: Assumption (251-294): We require a single assumption, not two (see Sec. 5): the unseen data (used for evaluation) and the forget data share the same data-generating distribution. Under it, the non-computable TV terms are zero. It is ubiquitous in machine learning, implicit in MIA-based evaluation, and largely ensured in practice, unlike those of prior certificates.
  • Clarification (319-328): Why we use the confidence score (true-label probability) instead of all K class probabilities: a broader attack surface comes at the cost of a larger sampling error, δetp\delta_\text{etp}.
  • Addition (329-351): Why the TV certificate evaluates privacy and utility jointly, unlike MIAs.
  • Clarification (352-353): We state the adversary's observation precisely: the TV certificate upper-bounds the advantage of any attacker who observes the binned confidence score, i.e., population-level attacks, extension to per-example attacks (and how to) is discussed in Sec. 6.

Sec. 4:

  • Correction (359-368): We rename the algorithm from "certified" to "principled" (CUP->PUP), since "certified" could be misread as implying pre-specified statistical noise. The contributions remain intact: Certification comes from the TV certificate (Gap 1). Adaptability to real-world requirements from the algorithm (Gap 2).
  • Addition (362-375): The pseudocode of PUP is now in the main manuscript, and that of PUP-DF in the appendix.

Sec 5:

  • Addition (Table 3): Two new data-free baselines, including Mu-Mis (ICLR26). PUP(-DF) remains state-of-the-art in jointly maximizing privacy and utility, now against 16 baselines, 3 models, and 3 datasets.
  • Correction + New finding (489-517): The assumption on the forget-set size, adopted from prior certified work, is redundant. A sanity check provides evidence that it stems from an "axiom" of prior work, that the model retrained from scratch is the gold standard, which it is not by default. This removes one of the two assumptions and further separates untraining (for privacy) from concept removal. We frame it as a secondary contribution.

Sec. 6:

  • Addition to Limitations (532-534): We state what the TV certificate does not cover: MIAs on other attack surfaces (e.g., loss, gradients, entropies) and per-example MIAs. No prior certificate meaningful for DNNs covers them either; our formulation allows extension to both.

Removals: To make room for the theory, we removed (i) the bin-count ablation table, whose results remain in Appendix, Table 10, and (ii) the empirical upper bounds of the population-level TV terms, which are best analyzed where they are defined.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.