acceptodds
Under review as a conference paper at ICLR 2027

Universal Privacy Is All-or-Nothing: A Phase Transition at Decision Sufficiency

Abstract

Machine-learning systems release internal representations, such as embeddings behind APIs or shared features, without knowing which attributes an adversary will try to infer. Yet defences protect only named attributes. Can one release be at least as private as every equally useful alternative, for every attribute and every attacker? We prove that the answer is all or nothing. Apart from the release that reveals nothing, such a release exists only if it keeps all the information the task needs. It is then the task's minimal sufficient summary, which reveals which answer an input deserves and nothing more. As soon as task information is traded away, universal privacy becomes impossible and its price total. Tolerating a small leakage relaxes this only proportionally. The guarantee survives estimation error of a learned summary and holds for deterministic attributes. On nine tabular, graph, image and text datasets with trained attackers, the learned summary leaks less than standard embeddings on almost every held-out attribute, and cuts MNIST re-identification from 93% to 1.0%. Below sufficiency, no release wins on every attribute: privacy that does not name what it protects exists only at sufficiency.

Primary area:
learning theory
Keywords:
Representation Learning, Universal Privacy, Privacy-Preserving Learning, Information Leakage, Blackwell Sufficiency, Minimal Sufficient Statistics, Information Bottleneck, Privacy-Utility Tradeoff, Sufficient Representations, Semantic Security

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_jSBFOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper considers the question of universal privacy, where we seek a learned representation of an input that preserves privacy across all potential sensitive attributes while retaining utility. The paper argues that (1) Releases that maintain privacy at least as much as all other releases at its utility or better only exist at zero and full sufficiency (using known arguments in a privacy setting); (2) Matching privacy across attackers/attributes at any level below maximum utility carries no information (exactly for continuous data, up to a vanishing margin for finite data); and contains additional analysis for binary vs. multiclass decisions and hard vs. learned quotients. Proofs are supplied, and a variety of experimental settings are used to verify the findings.

Critical strengths
  • The paper is structured well, and plots and tables are visually appealing and clear. Related work, both in the specific section and throughout the paper, is thorough (though I cannot verify if citations were missed, as I am not an expert in this field).
  • Proofs are supplemented with reproducible numerical verification on random instances; The experimental setup is clear and much information is provided for reproducibility.
Critical weaknesses
  • While some scoping is provided, more could be done to situate this stream of information-theoretic inference privacy research in the broader realm of what generally falls under "ML privacy". Does the notion of 'privacy' under this threat model encompass what other related fields would consider a 'private' model?
  • Some clarification on experimental setup choices is needed (see Questions).
Questions for authors
  • In the experiments, could the authors please share how they came to their choices of model architectures, attackers, and inversion procedure? Is there a risk of attacks not being strong enough in any case, as the theorems concern idealized attackers?
  • Are citations needed for the classicial results in Proposition 1 and Theorem 1(a)? Where can more uninitiated readers (like myself) learn more about these results in their original (non-privacy) settings?
  • Could the authors please clarify the use of the word 'phase transition' to describe the phenomenon of Theorem 1? Does this phrase have a history of use in information-theoretic contexts? Are there aspects of a physical phase transition that are not present in this setting?
3 comments
AuthorsOpenReview ↗

Reply to Reviewer jSBF: notion of privacy, attackers, citations, terminology

Thank you for your review.

W1. This notion of privacy. The threat model is attribute inference: an attacker who knows the data distribution sees the release of one input and infers attributes of that input. The guarantee is comparative, as in semantic security. Scope now says what this covers. It does not cover membership inference or extraction of training data. Differential privacy gives individual-level guarantees that can limit those attacks. The result is about being safest among equally useful releases. It does not rule out stand-alone, target-agnostic guarantees based on differential privacy, bounded leakage, computational assumptions or restricted target classes. Related work now discusses Stadler et al. (ICML 2024), who formalise least-privilege learning and establish utility-leakage limits for representations, while we study the ordering of releases and whether a universally safest one exists.

Q1. Architectures, attackers and inversion; strength of the attacks. We applied one rule: a small standard architecture per modality (App. F: an MLP, a two-layer GCN, a two-block CNN and a mean-of-word-embeddings network), and a single attacker and inversion procedure for all releases. The attacker is one MLP, retrained from scratch against each release. The architecture and training hyperparameters are fixed across releases; only the stopping epoch is selected separately for each attribute on a validation split. A trained attacker gives the quantity a practitioner can audit. The original inversion attack is one fixed MLP decoder followed by nearest-neighbour identification in a gallery.

Attacks can be too weak, and this limits what measured leakage levels mean. In Section 5 and Appendix I we attacked continuous releases again with a linear probe, one independent MLP per target, kk-NN and gradient-boosted trees, and discrete codes with a contingency table (the Bayes attacker up to estimation error). On continuous releases, validation picks our attacker for 23-70% of (release, attribute) pairs, and one of the two MLPs for 52-92%. With the strongest attacker (chosen by validation per release and attribute), the posterior does not leak more than the embedding on any attribute of 7 of the 9 datasets (3 seeds). On Cora and CiteSeer its mean leakage is lower than the embedding's by 0.042±0.0200.042 \pm 0.020 and 0.054±0.0130.054 \pm 0.013 of the entropy (10 seeds, Table 11).

We also added stronger re-identification attacks (Table 8): a larger decoder, a convolutional decoder, and a CNN that learns to map images to releases and matches the observed release in the gallery. The original attack understated the embedding, which is re-identified at 100%, 100% and 96% among 1,000 test images of MNIST, Fashion-MNIST and CIFAR-10 (93%, 61% and 22% in Table 1). Every hard code stays within its certificate ∣c∣/n|c|/n, and the predicted label stays at 1.0%, its exact Bayes rate. The posterior and VIB have no certificate, and their rates depend on what the attacker knows. A learned attack, which only sees image-release pairs from the attacker split, reaches 1.8-4.5% and 7-17%. An attacker who knows the encoder can compute the release of each gallery image and re-identifies every posterior at full precision. The Table 1 caption now says this, and it is why the paper recommends hard codes.

The posterior and hard codes are post-processings of the embedding, so their true leakage cannot exceed the embedding's, whatever the attacker. Measured levels depend on the attacker, as the paper now states (Table 4, linear probe on MNIST).

Q2. Citations for Proposition 1 and Theorem 1(a). Yes. They now appear at the statements. Proposition 1 is Blackwell's theorem (Blackwell, 1953) applied to attributes. For the original setting, see Le Cam (1964) and Torgersen (1991) on the comparison of experiments. Theorem 1(a) is the minimal sufficiency of the quotient (Bahadur, 1954).

Q3. "Phase transition". We mean a sharp threshold. By Theorem 1, a universally optimal release exists only at utility 0 or II. By Theorem 2, on inputs continuous within each class, the best universally safe utility is 0 for every τ<I\tau < I and jumps to II at τ=I\tau = I. On finite data the margin vanishes as the data grow. The term is used in a similar way for the Information Bottleneck (Wu and Fischer, ICLR 2020). Unlike a physical transition, there is no order parameter or critical scaling. Section 4.1 now says this.

Thank you for your thorough response to myself and other reviewers. I have updated my score.

Thank you for taking the time to review our revisions and update your assessment. We sincerely appreciate your thoughtful feedback and constructive suggestions, which have helped us improve the paper. Thank you again for your time and consideration.

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

This paper maps the concept of privacy (in context of representation learning) to the field of information theory asking whether it is possible to release a representation that is as private as every other alternative for all attributes (named as protected or otherwise) against all possible adversaries. This is close to the field of privacy auditing wherein to assess the privacy an algorithm affords, it is evaluated against strongest possible adversaries. Here, the question additionally concerns simultaneous comparisons across all attributes and alternative representations. In representation learning, according to author(s), most defences protect a chosen attribute, which aims to protect against all adversaries targeting that attribute, but is likely to leak information to an adversary targeting other attribute(s) that the defence chose not to protect. The central question in the paper also concerns the representation utility: task information I(Z;Y)I(Z;Y); how much task (YY)-relevant information does the representation ZZ possess. The authors show that at full task sufficiency, the minimal sufficient statistic is universally optimal, whereas at intermediate utility, different representations can protect different attributes, leaving no universally optimal choice. This optimality is relative to alternative representations satisfying the utility requirement; it does not imply that no sensitive information is revealed. The paper reveals a dichotomy: A release that is as private as any other alternative with equivalent utility exists only when either (a) the full task-relevant information is preserved by ZZ (I(Z;Y)=I(X;Y)(I(Z;Y) = I(X;Y), or (b) no task-relevant information is preserved by ZZ (I(Z;Y)=0)(I(Z;Y) = 0).

Critical strengths
  • The paper is well-written and easy to follow (at least the portion of the main paper). It studies privacy-utility trade-off in representation learning through the lens of information theory. The authors build on established results on post-processing and minimal,task-relevant sufficient statistics. Their main new contribution is showing that no universally optimal release exists at intermediate utility. They also quantify the utility cost of requiring universal safety.

  • The author(s) also provide empirical results that support their argument in practice. The results span across nine datasets demonstrating that learned quotient representations reduce leakage while retaining most of the release’s estimated task utility. At lower utility levels, however, different releases protect different attributes, with no single release performing best across all tested attributes.

Critical weaknesses
  • My primary concern is how utility is defined in the paper. It is associated with task-relevant information. But, assuming these representations are used for training models further in a pipeline, how useful are the universally-optimal released representation there? While preserving I(Z;Y)I(Z;Y) means preserving information about YY, I am worried that focusing just on releasing optimal representations for each task won't necessarily translate to them being equally useful for further use. For example, recommendation in Lines 375-376 turning an embedding into a hard code cannot increase leakage, but that alone says nothing about its usefulness for training. Similaryl, another recommendation in Line 375 suggest to release outputs rather than embeddings. This might limit their usability for downstream task. I would like to know author(s)' stance on this.

  • The theory applies to supervised representation learning guided by the task knowledge. I rank this as lower order weakness but it ought to be acknowledged in limitations.

Questions for authors

Questions

  • Appendix E’s numerical checks are useful sanity checks, but the random-direction LP search does not certify the maximum utility. Could the authors clarify how the best value found supports the claim in lines 958–959 that the bound is loose by an order of magnitude, given that there is a possibility that the KP search just missed the releases with higher utility? Or is the probability of missing releases is low/ negligible? You checked 18 cases in the paper, what if you expand the search space? Maybe modify the eps_lists or n_dirs in the check_V2(...) function in the code?

  • W.R.T. Proposition 3, η\eta is the misalignment probability between the learned code and the ideal quotient after relabelling its classes. However, the appendix defines η\eta as simulation deficiency (Lines 709–710) and uses it in the utility bound (Lines 711–712). Could the authors clarify this change? Being able to simulate the learned code from the quotient need not mean that the learned code preserves its task information.

Suggestions

  • W.R.T. Theorem 3, the qualification mentioned in Line 802, "A matching lower bound against all encoders is open." ought to be put in the main text where you say, The rate in ε\varepsilon is attained." (Line 203). The proof in the Appendix however, shows only that it is attainable against {E,ZA}\{E,Z_A\}.

  • The proofs for Theorems (Appendix B) need a better presentation. It was painful to read through them since they look visually dense. You have virtually no upper bound on the pages in the Appendix. And while as reviewers, reading Appendix is deemed as "optional", we do look into important aspects like theorem proofs. I hope, the author(s) take this into consideration when revising the paper.

3 comments
AuthorsOpenReview ↗

Reply to Reviewer h48M: downstream use, Theorem 3, Proposition 3, proofs

Thank you for reading the appendix closely.

W1. Downstream usefulness. This is an important practical question, and the submitted Discussion stated the recommendation too broadly. I(Z;Y)I(Z;Y) measures usefulness for the named task only, and a hard code that cannot increase leakage may still be of little use. The recommendation now reads "When the recipient needs the task decision, release outputs rather than embeddings".

We measured both sides, with models retrained on each release and tested on held-out data (Section 5 and Table 2b; details in Tables 6, 7 and 9).

  • Named task (Table 6): the posterior stays within 0.7 accuracy points of the embedding outside the graphs, and within 2.7 on them.
  • Other tasks (Table 7): treating each natural held-out attribute as a downstream task, the loss is large. On Adult, mean accuracy falls from 94.9% with the embedding to 63.2% with the posterior (majority class: 55.8%). The posterior keeps 5-79% of the embedding's gain over the majority class, and the finest hard code 6-63%, on the tasks where the embedding beats that class by at least 0.5 point (only 10 and 11 of 32 on Cora and CiteSeer).

A downstream task defined on the input is an attribute in the paper's sense, so what a release hides from an attacker it also hides from a downstream model. The choice of release depends on its use.

  • If the recipient needs only the decision, we recommend the quotient.
  • If the downstream tasks are known, they can be included in the decision YY, which the framework leaves free, and Theorem 1(a) applies to the quotient of the joint decision (Table 9 tests this on a task fixed in advance).
  • If the release must serve unknown tasks, the embedding remains more useful, at the cost of exposure: a stronger attack re-identifies 100% of a gallery of 1,000 MNIST test images from it (Table 8).

Which of these settings is closest to the pipelines you have in mind? If another downstream evaluation would help, we can run it during the discussion.

W2. Supervised setting. Scope now states at the start that the theorems need a known decision YY.

Q1. Numerical check of Theorem 3 (lines 958-959). We agree. The search misses maxima: on 2 of the 6 instances, the best value found decreases when ε\varepsilon increases. The bound also exceeded II on all 18 cases, so the ratio 0.09 said nothing about tightness. We removed this claim.

The larger search you suggested (30 instances, 8 values of ε\varepsilon, 300 directions instead of 60, more output symbols, gradient ascent) improves 17 of the 18 published cases (median factor 1.25, up to 2.8). No case violates the bound. Where the new upper bound is below II (130 of these 240 cases, and 118 of 150 in a second set), the best value found is at most 0.33 and 0.40 times the bound. The search is a lower estimate, so we make no claim on the constant.

Q2. η\eta in Proposition 3. The statement was wrong as written: η\eta was the deficiency in the utility bound, while the proof uses the misassignment probability. A constant release has zero deficiency and no utility. The privacy bound now uses η=δP(π→c^)\eta = \delta_P(\pi \to \hat c). For a hard code, the utility bound uses ηϕ=P(c^≠ϕ(π))\eta_\phi = P(\hat c \ne \phi(\pi)) with an injective relabelling ϕ\phi. The privacy guarantee is unchanged.

Suggestion 1. "The rate in ε\varepsilon is attained." The proof showed this only against {E,ZA}\{E, Z_A\}. The revision proves, for every τ<I\tau < I and against every encoder,

min⁡(I,κε/(1−τ/I))≤Uε⋆(τ)≤12Lε/(1−τ/I)\min(I, \kappa\varepsilon/(1-\tau/I)) \le U^\star_\varepsilon(\tau) \le 12L\varepsilon/(1-\tau/I),

where κ\kappa and LL are task-dependent constants defined in Appendix A. The upper bound keeps the assumption of atomless conditional distributions within each decision class. The lower bound does not require the atomless-within-classes assumption. It uses a new inequality: for every release, the Bayes guess of the quotient errs with probability at most (I−I(Z;Y))/κ(I - I(Z;Y))/\kappa. The thinned erasure code of parameter min⁡(1,κε/(I−τ))\min(1, \kappa\varepsilon/(I-\tau)) is then ε\varepsilon-safe against every release of utility at least τ\tau. The bounds match in ε\varepsilon and 1−τ/I1-\tau/I, up to these constants. Theorem 3 in the main text now states both bounds, which replaces the qualification you asked to move, and Section 4.2 gives this inequality and the construction.

Suggestion 2. Appendix B is now organised in labelled steps.

Reviewer_h48MOpenReview ↗

Response to the author(s)

I commend the author(s) on providing the detailed response. May I know whether you has updated the paper with the changes? If yes, I would recommend highlighting the changes with a different color to make them easier to spot. That would be a great help for the reviewers in general.

AuthorsOpenReview ↗

Reply to Reviewer h48M: revised PDF with changes in blue

Thank you for the suggestion. Yes, the paper has been revised with all the changes described in our responses. The revised PDF now on OpenReview shows new or rewritten text in blue; deleted text is not shown. Apart from the colour, it is identical to the revision, with the same pages and line numbers. Entirely new elements are in blue as a whole: Corollary 1 (Section 4.2), Table 2b, Appendix I with Tables 4-12, the labelled proof steps of Appendix B, and seven new references. The figures are unchanged. The removed claims are listed in our general comment ("Summary of the revision").

Reviewer_B3avOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies whether a representation can provide privacy against every possible sensitive attribute and every possible attacker without requiring the protected attribute to be specified in advance. Privacy is formalized through the Blackwell order: a representation is considered universally safer than another if it can be obtained as a garbling of the other representation. Utility is measured using the mutual information between the released representation and the task variable. The main theoretical result is an "all-or-nothing" characterization. At zero utility, a constant representation is universally optimal. At full decision sufficiency, the minimal sufficient statistic, termed the quotient, is universally optimal. At every intermediate utility level, the paper argues that no universally optimal representation exists. The paper supplements this result with approximate-universality bounds, extensions to deterministic attributes, guarantees for learned approximations of the quotient, and experiments on tabular, graph, vision, and text datasets.

Critical strengths
  • Appropriate decision-theoretic formalization: The use of Blackwell comparison gives a precise interpretation to the requirement that one representation be no more informative than another for every target and every decision-making adversary.

  • Substantial supplementary and empirical effort: The authors provide proofs, numerical checks, experimental protocols, multiple data modalities, inversion experiments, and re-identification evaluations.

Critical weaknesses
  • The experiments do not test the paper’s central universal claim: The theory concerns all attributes, all attackers, and all admissible encoders, whereas the experiments consider a finite collection of representations, selected attributes, and a particular family of trained attackers. The empirical findings therefore illustrate selected instances but cannot establish universal dominance or universal nonexistence.

  • The reported leakage estimates do not reliably establish leakage ordering: Leakage is estimated using attacker cross-entropy, producing a variational lower bound whose tightness can differ across representations. A smaller estimated value may indicate less information in the representation, but it may also indicate that the attacker had greater difficulty extracting the available information. Clipping negative estimates at zero further introduces artificial ties and floor effects.

Questions for authors
  • What formal result supports the statement that the learned quotient is “the safest release of its utility”?
  • How can true leakage ordering be inferred from representation-dependent variational lower bounds? Specifically, If one attacker achieves a lower estimate on Z1Z_1​ than on Z2Z_2​, how do the authors distinguish lower true information from poorer attacker optimization or approximation on Z1Z_1​? Can the authors provide comparisons across multiple attacker classes and demonstrate that the ordering is stable?
  • Does an analogous result hold when utility is measured by Bayes risk, excess classification error, log-loss, calibration error, or performance within a restricted downstream hypothesis class? If not, how broadly should the practical conclusion be interpreted?
  • Can the authors compare the quotient, embeddings, VIB, and named-target defenses at matched task accuracy, log-loss, or calibration rather than only through normalized mutual-information estimates?
  • The theorem rules out universal optimality under an unrestricted Blackwell criterion. It does not appear to rule out target-agnostic protection under differential privacy, bounded leakage, computational assumptions, or restricted target classes. Would the authors revise the central claim to make this limitation explicit?
3 comments
AuthorsOpenReview ↗

Reply to Reviewer B3av: experiments, attackers, other utilities, scope of the claim

Thank you for your questions. New experiments are in Section 5 (Table 2b) and Appendix I (Tables 4-6, 10 and 11).

W1. Experiments and the universal claim. We agree: the universal statements come from the proofs; Appendix E and the experiments only cover finite instances and a finite pool.

Q1. "The safest release of its utility." This sentence had no formal support and contradicted Theorem 1(b). We removed it. What holds is Prop. 2 (a hard code is certified by its number of cells) and Prop. 3 (a code with error rate η\eta is at most η\eta less private than any sufficient release).

W2, Q2. Variational estimates, clipping, several attackers. Post-processing fixes the true order of the posterior and hard codes against the embedding; the attacker only changes the size of the gap. For other pairs the estimated ordering can depend on the attacker: trained attackers give lower bounds up to sampling noise, so agreement between families is evidence, not proof.

We re-attacked continuous releases with a linear probe, one MLP per target, kk-NN and boosted trees, and discrete codes with a contingency table (Bayes up to estimation error). "Strongest" picks the attacker by validation per release and attribute.

  • Validation picks our attacker for 23-70% of (continuous release, attribute) pairs. On discrete codes it matches the table (median gap at most 0.002 of the entropy, 0.008 on Cora and CiteSeer).
  • Posterior against embedding, no tolerance, no clipping (3 seeds): with our attacker and the strongest, it leaks no more on every attribute of 7 of the 9 datasets. Weak attackers misorder it: 50-54% on MNIST and CIFAR-10 (linear probe), 50% on SST-2 (kk-NN).
  • Cora and CiteSeer, the two noisiest datasets, now have 10 seeds. The mean difference posterior minus embedding is −0.017±0.004-0.017 \pm 0.004 and −0.032±0.006-0.032 \pm 0.006 of the entropy with our attacker, −0.042±0.020-0.042 \pm 0.020 and −0.054±0.013-0.054 \pm 0.013 with the strongest (95% intervals). Per attribute, five Cora intervals lie above 0 with our attacker, none with the strongest; the true sign is known, so these are attacker errors.
  • For continuous releases more than 0.01 apart under our attacker, the strongest reverses the order by more than 0.01 in at most 1.7% of pairs on seven datasets, and 13% and 3% on Cora and CiteSeer (10 seeds; Table 5 gives 19% and 9% with 3 seeds). Others reach 14% outside the graphs.

Clipping: 5-47% of estimates per dataset are negative, with the highest shares on Cora and CiteSeer. On these two it raises the share of attributes that leak no more, from 55% and 68% to 71% and 74% in the same re-run (Section 5, original runs: 68% and 79%). The seven other datasets are unaffected. The posterior-embedding comparisons and the reversals above are without clipping.

Q3. Other utilities. Let UG(Z)=E[G(P(Y∣Z))]−G(PY)U_G(Z) = \mathbb{E}[G(P(Y|Z))] - G(P_Y) with GG convex, which covers the Bayes risk of any bounded loss. Erasure keeps a fraction pp of UGU_G, the only property the proof of Theorem 2 uses, so its impossibility holds below the maximum of UGU_G. For strictly proper losses, the proof of Theorem 1 carries over. For the 0-1 loss, whose utility gap is the excess classification error, the Bayes action replaces the quotient in Theorem 1(a) when a.s. unique. For log-loss with a restricted class that can read a one-hot code, Theorems 1 and 2 hold as stated. Calibration is not a utility: a constant release predicting PYP_Y is calibrated and uninformative (Corollary 1, Section 4.2; Appendix C).

Q4. Matched comparisons. Each family gives the release closest to the embedding, on test log-loss (Table 10) or accuracy (Table 6), with ECE and leakage. The posterior's log-loss is within 0.041 of the embedding outside the graphs (0.067 on them), and it loses at most 0.7 accuracy points (2.7 on them). The ECE of all these releases stays between 0.003 and 0.052. The posterior's mean leakage falls on all nine datasets, by 26% on Fashion-MNIST (0.60 to 0.45) up to 97% on Bank (0.84 to 0.03), and to 0 on Cora, where the embedding leaks only 0.06. At matched accuracy, censoring reaches 0.70, 0.71 and 0.25 on Adult, Bank and SST-2; otherwise named-target defences stay within 0.06 of the embedding. VIB leaks less than the posterior on most datasets, usually at lower accuracy. On MNIST and Fashion-MNIST its accuracy is within 0.2 point (the posterior only estimates the quotient); the hard code leaks less than VIB there (0.08 vs 0.14, 0.34 vs 0.41).

Q5. Revising the central claim. Yes. The abstract, Scope and Conclusion now limit the negative result to being safest among equally useful releases in the Blackwell order, which does not rule out stand-alone, target-agnostic guarantees based on differential privacy, bounded leakage, computational assumptions or restricted target classes (now stated in Scope). An ε\varepsilon-LDP release of utility in (0,I)(0, I), for example, bounds leakage on every attribute but, by Theorem 1(b), is not the safest at its utility.

I have read through the paper and changes and increased my score. All the best

Thank you for taking the time to read our revisions and reconsider your assessment. We appreciate your constructive feedback, which helped us improve the paper. Thank you again for your consideration.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We thank the reviewers and the AC. We uploaded a revised PDF (10 pages) and an updated supplementary. The title, the sections, and the numbering of theorems, propositions, lemmas, remarks, figures and Tables 1-3 are unchanged; Corollary 1 and Table 2b are new. The new experiments are summarised in Section 5 and detailed in Appendix I.

Corrections

  • TL;DR: the form does not let us edit this field during the discussion. Its phrase "below sufficiency, no universal privacy guarantee exists" overstates the result. It should say that below sufficiency no release of positive utility is safest among equally useful ones for every attribute and every attacker. We will correct it when the field can be edited.
  • Section 6: we removed "the safest release of its utility". It had no formal support and contradicted Theorem 1(b).
  • Proposition 3: the full statement (Appendix A) now uses two separate quantities for the privacy and utility bounds, and for a hard code the relabelling must be injective.
  • Appendix E and Section 6: we withdrew the claim that the bound of Theorem 3 is loose by an order of magnitude.
  • Section 5: "It leaks no more on 87-100% of the held-out attributes" relied on an undeclared tolerance of 0.01. We now report it without tolerance, and the test error of the predicted label is given on six datasets instead of three.
  • Section 5, Figure 2 and Table 2: we separate the tolerance δ\delta of the pool statistic from the ε\varepsilon of Theorem 3.
  • Section 5: we removed "several times the seed noise" for δ=0.01\delta = 0.01, which is now given in standard errors of the mean.
  • Section 1 and Appendix E: numerical checks now refer to the statements with a finite form, on random instances, instead of "every statement".
  • Proposition 1 is stated as four equivalent conditions. A single leakage measure gives only one implication.
  • Proposition 4 states the additional condition needed to extend Theorem 2(a) to deterministic attributes.
  • Table 1: the caption says that the posterior and VIB rows have no certificate and depend on the attack.

Theorem 3

  • For every τ<I\tau < I, the theorem now has a lower bound against every encoder. The upper bound keeps the assumption of atomless conditional distributions within each decision class and no longer has a logarithmic term, and its constant goes from 8L8L to 12L12L. On such inputs the rate in ε\varepsilon is attained against all encoders (proof in Appendix B, checks in Appendix E).

Additions

  • Appendix I, Tables 4-10: every release attacked by several attacker families, estimates without clipping, stability of the ordering, task accuracy, log-loss and calibration at matched utility, usefulness for other downstream tasks (including a known task), and stronger re-identification attacks.
  • Appendix I, Table 9: a known downstream task TT, fixed in advance, is included in the decision. Accuracy on TT rises from 38.6-90.8% for the quotient of YY to 96.5-100% on tabular, image and text data, where these tasks are easy (an input column on Adult and Bank, a pixel statistic on images, a negation cue on SST-2). On the graphs it reaches 67-84%, against 75-86% for the embedding. The quotient of the joint decision leaks more on other attributes than the quotient of YY on eight datasets, by 0.01 to 0.14.
  • Appendix I, Tables 11-12: 95% intervals over seeds for the comparison between the posterior and the embedding, seed-to-seed variation of the other new experiments, and 7 more seeds on Cora and CiteSeer (10 in total). The interval of the mean difference now lies below 0 on both graphs. Per attribute, 21 and 20 of the 38 intervals contain 0 on Cora and CiteSeer with the reference attacker, and 23 and 17 with the strongest.
  • Section 4.2, Corollary 1 (proof in Appendix C): other measures of utility.
  • Section 4.2: the inequality behind the lower bound of Theorem 3.
  • Section 5: new paragraphs on the dependence on the attacker, matched task performance and other tasks, with Table 2b, and stronger re-identification. Section 6 states how the choice of release depends on its use.
  • Section 6, Abstract and Conclusion: the central claim is about being safest among equally useful releases, with its limits stated (stand-alone guarantees, threat model, supervised setting).
  • Citations at Proposition 1 and Theorem 1(a), and the meaning of "phase transition" in Section 4.1.
  • Sections 2 and 6, Appendix D: discussion of Stadler et al. (ICML 2024) and further related work.
  • Appendix B: proofs organised in labelled steps.

The supplementary keeps all the original code and adds the new scripts and saved results (run_revision.sh).

We hope these revisions address the reviewers' concerns, and we would be glad to discuss any remaining questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.