acceptodds
Under review as a conference paper at ICLR 2027

Privacy or Utility First? Lexicographic Optimization of the Privacy–Utility Bound

Abstract

Privacy-preserving representation learning seeks to suppress sensitive information while retaining information required for a downstream task. Many existing neural information-theoretic approaches resolve this conflict through externally chosen constraints or weighted objectives, such that the resulting privacy-utility operating point depends on externally chosen hyperparameters rather than on a theoretically characterized privacy-utility bound. We derive a global information-theoretic lower bound on sensitive leakage as a function of retained utility and introduce qualified privacy mechanisms that characterize its equality cases. Furthermore, we show that interaction information constrains the compatibility of privacy and utility: qualified mechanisms can only exist for non-negative interaction information, whereas jointly ideal mechanisms can only exist for non-positive interaction information. In the positive-interaction regime, the extremal equality coordinates of this bound are distinct. We propose privacy-first and utility-first lexicographic optimization (priLO and utiLO) and prove that, whenever these coordinates are attainable by qualified mechanisms, the lexicographic objectives recover them exactly. For neural optimization, we realize these priorities using adaptive gradient surgery, eliminating the need for a fixed trade-off coefficient. Controlled synthetic experiments recover the predicted endpoint structure, while experiments on six real-world datasets show that the proposed lexicographic objectives provide competitive privacy-utility operating points without selecting a fixed trade-off coefficient.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
privacy, mutual information, lexicographic optimization, privacy-preserving, multi-objective

Reviews

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

A representation ZZ is produced by a privacy mechanism Π\Pi from observation XX, with sensitive attribute SS and utility label UU, under the Markov assumption (S,U)→X→ΠZ(S,U) \to X \xrightarrow{\Pi} Z.

Critical strengths
  1. The interaction-information separation theorem is correct, non-trivial, and makes the regime a computable diagnostic.
  2. The finite-support validation is built so the learned mechanism cannot game the metric.
Critical weaknesses
  1. The headline empirical claim is contradicted by the paper's own Table 2.
  2. Assumption 1 does not describe the mechanisms the paper's own experiments instantiate.
Questions for authors
  1. On W1: on Adult, CFB attains F1U=78.8F_1^U=78.8 at F1S=52.8F_1^S=52.8 while priLO attains 60.2 at 40.3. Under an identical post-hoc protocol, what reading of "competitive" survives this? If none, please reword the abstract and conclusion.
  2. On COMPAS, is F1U=49.0F_1^U=49.0 at or below the majority-class baseline? If a trivial classifier matches it, the paper should say so and attribute the cause among the conditional secondary objective, the critic budget, and the realizability gap.
2 comments
AuthorsOpenReview ↗

Markov assumption and dataset-specific performance

We thank the reviewer for identifying the overly broad empirical interpretation and for questioning how Assumption 1 applies to the neural implementation. We have revised the main text and added controlled comparisons.

1. Competitiveness on Adult

We agree that the original results do not justify describing priLO as generally competitive.

In the original Adult experiment, priLO obtains 60.2%60.2\% utility macro-F1F_1 at 40.3%40.3\% sensitive macro-F1F_1, compared with 76.1%76.1\% and 41.2%41.2\% for privacy-oriented CPFSI.

We have revised the abstract, experimental discussion, and conclusions to distinguish priLO from utiLO.

Appendix D.4 provides independently retrained comparisons over fifteen matched seeds. Adult priLO retains only 47.95%47.95\% utility versus 76.21%76.21\% for privacy-oriented CPFSI.

utiLO performs differently. It achieves 78.68%78.68\% utility and 51.98%51.98\% sensitive macro-F1F_1, compared with 78.76%78.76\% and 53.19%53.19\% for high-utility CFB. The matched-bootstrap sensitive macro-F1F_1 difference is −1.21-1.21 percentage points, with a 95%95\% interval of [−2.13,−0.25][-2.13,-0.25].

Our revised claim is therefore narrower: utiLO remains competitive with strong high-utility baselines, whereas priLO frequently sacrifices substantial utility. We do not claim universal Pareto dominance.

2. COMPAS and trivial baselines

Appendix D.4 now includes majority-class, constant-representation, and training-prior randomized controls.

COMPAS priLO achieves 48.40%48.40\% utility macro-F1F_1. This exceeds the majority baseline (35.27%35.27\%), but falls below the training-prior randomized baseline (49.97%49.97\%). The paired-bootstrap difference is −1.56-1.56 percentage points, with a 95%95\% interval of [−2.28,−0.88][-2.28,-0.88].

We therefore acknowledge that priLO does not establish nontrivial utility recovery against the stronger control.

Appendices A.8–A.9 distinguish structural endpoint attainability from the actual population optima, while B.1–B.2 address surrogate and optimization limitations.

The experiments do not isolate a unique cause of the failure. We therefore avoid attributing it specifically to secondary optimization, critic capacity, or endpoint unattainability.

3. Markov assumption

Assumption 1 concerns the representation produced by a fixed encoder on a fresh observation, not the labeled data used to train it.

Although SS and UU supervise MI critics during training, they are not inputs to the deployed encoder. For fixed learned parameters θ\boldsymbol\theta and independent sampling noise ε\varepsilon,

\qquad I(S,U;Z\mid X,\boldsymbol\theta)=0.$$ For fresh observations independent of the training procedure, this gives the required Markov structure $(S,U)\to X\to Z$. We have clarified this distinction immediately after Assumption 1.

Thanks, the revision settles both things I raised, and my majority-baseline guess was wrong; the training-prior control is the right comparator. I'm leaving the score at 2 though, because the same tables make the contribution thinner than the title suggests: priLO loses to CPFSI by 28 points on Adult and sits below a trivial prior control on COMPAS, and utiLO's edge over tuned CFB is 1.2 points of sensitive F1 at equal utility.

Reviewer_6d4JOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies privacy-preserving representation learning where a mechanism transforms input X into representation Z to suppress sensitive information S while retaining utility information U, under the Markov structure (S,U) -> X -> Z.

Existing information-theoretic approaches such as the privacy funnel, conditional privacy funnel, and information bottleneck resolve the conflict via externally chosen thresholds or Lagrangian weights. The resulting operating point depends on the hyperparameter rather than a theoretically characterized bound.

The authors derive a global lower bound on sensitive leakage for any retained utility: I(S;Z) >= I(U;Z) - I(U;X|S), using chain rule and data-processing inequality. Equality holds iff the mechanism is qualified: I(S;Z|U)=0 and I(U;Z|S)=I(U;X|S). Qualified mechanisms suppress sensitive information unrelated to utility while preserving all attainable utility information unrelated to sensitive variable. Jointly ideal mechanisms are defined as I(S;Z)=0 and I(U;Z)=I(U;X).

Interaction information I(S;U;X)=I(S;U)-I(S;U|X) constrains compatibility. Theorem 1 shows qualification can exist only for non-negative interaction information, joint ideality only for non-positive interaction, and both together only at zero interaction where classes coincide at (I(U;X),0). For positive interaction, no jointly ideal mechanism exists. Every qualified mechanism lies on line segment between privacy endpoint P_priv=(I(U;X|S),0) and utility endpoint P_util=(I(U;X), I(S;U;X)), with parameter t=I(S;Z). Endpoints are not guaranteed attainable; a counterexample with X=U, S=U XOR N shows P_priv unattainable despite positive interaction.

Because endpoints are distinct in positive-interaction regime, the authors formulate two lexicographic priorities: privacy-first LO (priLO) lex min [I(S;Z), -I(U;Z)] and utility-first LO (utiLO) lex min [-I(U;Z), I(S;Z)]. Proposition 1 proves that whenever both qualified endpoints are attainable, lexicographic optima recover them exactly and are qualified. Weighted scalarization would need geometry-dependent weight requiring knowledge of attainable region.

For neural optimization, primary and secondary objectives are optimized via adaptive gradient surgery based on Hsieh et al. 2024. Gradient is decomposed into primary gradient a_t and orthogonalized secondary component b_t using EMA of primary gradients m_t. Candidate direction d_t=lambda_t = a_t + lambda_t b_t with lambda_t in [0,1] is selected via finite-step safeguard checking that both primary and secondary losses do not increase after SGD step, picking lambda with smallest secondary objective; if none admissible, pure primary update.

Mutual information terms are estimated variationally: Barber-Agakov lower bound for maximization and vCLUB upper bound for minimization, with classifiers q_psi and q_phi fitted by cross-entropy. Discrete conditional MI expressed as entropy minus cross-entropy.

Critical strengths
  1. Global lower bound and exact characterization of equality via qualified mechanisms provides principled reference independent of hyperparameters.

  2. Necessary sign conditions for qualification vs joint ideality, separation of zero, positive, negative regimes, and explicit endpoint coordinates clarifies why privacy and utility conflict.

  3. Strict priority ordering eliminates trade-off coefficient and targets bound endpoints directly; recovery proof conditional on attainability is solid.

  4. Proposition 2 shows that if both endpoints attainable, entire qualified segment attainable via Bernoulli mixing, completing picture.

  5. Both neural recovery and exact enumeration independent of variational bounds support theory; dimensional scaling exposes practical limits honestly.

Critical weaknesses
  1. Theorem 1 gives only necessary conditions. Corollary endpoints need not be attainable, as shown by counterexample X=U. Proposition 1 assumes qualified mechanisms attain both endpoints, making lexicographic recovery conditional. No sufficient condition for attainability given beyond constructed shared-private binary symmetric channels. Real data may fall into unattainable case, then priLO/utiLO have no endpoint to recover.

  2. vCLUB is upper bound only when variational posterior matches true conditional; otherwise only approaches true MI as approximation becomes accurate. BA is lower bound. Optimizing bounds does not guarantee optimizing true I(S;Z) and I(U;Z). Evaluation also uses BA lower bounds, so leakage may be underestimated. No guarantee that gradient surgery on surrogates preserves lexicographic optimality for true objectives. Limitations paragraph admits this but paper still claims endpoint recovery.

  3. Adaptive lambda_t selection via geometric decreasing candidates with finite-step check requires EMA decay, epsilon for orthogonalization, step size, candidate grid. No convergence analysis for non-convex neural nets. Secondary-gradient starvation observed on AudioMNIST priLO (utility F1 31.6% vs identity 99.6%) indicates failure mode not addressed.

  4. Figure 3: priLO under-recovers utility for most dimensions, utiLO deviation substantial at larger d with increased variance at 1024. Analytical endpoints constant, so failure is purely optimization/estimation. This undermines claim that method eliminates hyperparameter tuning — high-dimensional settings still need architecture/tuning to recover endpoints.

  5. MI measures average dependence, provides neither differential privacy nor worst-case disclosure. Ethics statement correctly warns, but title and abstract may overclaim privacy-preserving. No comparison to DP baselines despite discussing medical privacy motivation.

Questions for authors
  1. Beyond constructed BSC example, can you give sufficient condition on P(S,U,X) for P_priv and P_util attainability? Is interaction non-negativity plus some functional representation condition enough?

  2. Since vCLUB may not be upper bound, does minimizing vCLUB guarantee I(S;Z) reduction? Can you report true MI via exact enumeration on synthetic Gaussian mixture where true MI computable, to quantify bound gap?

  3. Under what conditions does finite-step safeguard ensure primary objective monotonic decrease? What EMA decay and epsilon used, and how sensitive are results?

  4. Why does utiLO variance explode at d=1024? Is it due to vCLUB variance with nuisance dimensions or orthogonalization instability? Does increasing critic capacity restore endpoints?

  5. Did you sweep beta/gamma beyond {1,64,1024}? CFB beta=1024 selected as non-collapsed across datasets, but collapses to near-zero utility on some settings per text — how was collapse defined?

  6. Post-hoc attacker F1 reduction to chance on HAR/AudioMNIST is impressive, but attacker uses same architecture as utility classifier. Have you tested stronger attacker or membership inference? Does low BA I(S;Z) imply low attacker F1 generally?

  7. You state Pq empty for I<0 but P* not excluded. Can you give example where jointly ideal exists with negative interaction, and what would priLO/utiLO do there?

1 comment
AuthorsOpenReview ↗

Theoretic and experimental amendments

We thank the reviewer. We added attainability theorems, MI diagnostics, optimization analysis and experimental controls.

1. Attainability and actual optima

Appendix A.8 gives necessary and sufficient P(S,U,X)P(S,U,X) conditions for both endpoints: privacy requires posterior factorization and g(X)⊥S\mathbf g(X)\perp S under sensitive-class overlap; utility uses t(X)=P(U=⋅∣X)\mathbf t(X)=P(U=\cdot\mid X) without overlap. Appendix A.9 characterizes both actual lexicographic optima even when equality fails: privacy-first via convex order on posterior laws, utility-first via Z=t(X)Z=\mathbf t(X). These do not guarantee neural recovery.

2. BA/vCLUB and independent MI evaluation

Learned vCLUB need not upper-bound true MI or guarantee reduced leakage. Appendix B.1 derives the exact gaps: the BA shortfall is an expected posterior KL divergence; the vCLUB gap is a difference of KL divergences of indeterminate sign (Barber and Agakov, 2003; Cheng et al., 2020; Poole et al., 2019). Appendix C.2 evaluates the Gaussian channel by independent density-ratio Monte Carlo. For one-bit utiLO, reference leakage is 1.0867591.086759 bits versus refitted BA 1.0517721.051772 and vCLUB 9.1849.184; utility is 1.9999991.999999 bits. Thus leakage exceeds the attainable minimum by 0.0867590.086759 bit. They are numerical estimates, not optimality certificates.

3. Safeguard, settings and convergence

Appendix B.2 proves primary-loss monotonicity for exact safeguarded steps when the primary loss is lower bounded and LL-smooth and ηt≤1/L\eta_t\leq1/L. Under stated schedules, stochastic primary stationarity has an O(T−1/4)O(T^{-1/4}) bound accounting for EMA tracking, bias, variance and regularization. B.3 checks the exact-gradient safeguard on a known lexicographic problem. Neither proves global true-MI convergence. EMA sensitivity is untested; AudioMNIST secondary-gradient starvation is hypothetical.

The reported EMA optimizer uses decay 0.90.9 (update weight 0.10.1), ε=10−7\varepsilon=10^{-7}, η=0.1\eta=0.1, gradient-norm cap 11, and stationarity threshold 10−1210^{-12}. Its candidate grid is {2−k:k=0,…,10}∪{0}\{2^{-k}:k=0,\ldots,10\}\cup\{0\}. Choose the positive candidate with lowest secondary loss among those passing both checks; otherwise use λ=0\lambda=0. This is not a fixed trade-off weight.

4. High-dimensional instability

Appendix C.3 varies data (up to 500500k observations), encoder width, latent size dZ∈{4,8,16,32}d_Z\in\{4,8,16,32\}, and training duration. Utility values below are held-out BA estimates, not exact MI. The mean probe train–test cross-entropy gap falls from 0.4850.485 to 0.0180.018 bit; at d=512d=512, wide utiLO utility rises from 0.5860.586 to 0.8410.841 bits. At d=1024d=1024, capacity-adaptive priLO reaches 0.4700.470 bits at 1212k updates (target 0.485940.48594), with no leakage detected by the probes, while utiLO reaches 0.9190.919 at 66k but falls to 0.8100.810 at 1212k (target 0.971890.97189). Architectures were selected on validation seeds and tested on new seeds. The training critic registers a larger 66k-to-1212k utiLO decline (0.3710.371 versus 0.1080.108 bit for an independent linear probe). An informative-coordinate oracle reaches 0.9660.966 bits. They improve recovery but do not isolate vCLUB variance, projection instability or training-critic capacity; initial width ablations held critics at 256256. No EMA sweep or perfect-privacy certificate is claimed.

5. Baselines and collapse

Appendix D.4 reports the complete evaluated CFB grid β∈{1,64,1024}\beta\in\{1,64,1024\} and CPFSI grid (β,γ)∈{1,64,1024}2(\beta,\gamma)\in\{1,64,1024\}^2; no broader sweep is claimed. CFB β=1024\beta=1024 is a high-utility reference, not universally optimal. “Collapse” means utility near trivial-predictor performance, not a formal MI cutoff: on Adult, CFB utility macro-F1F_1 is 42.93%42.93\% at β=1\beta=1 versus 78.76%78.76\% at 10241024. We claim no universal dominance.

6. Attacks and classification guarantees

Appendix D.5 tests stronger linear, wider, deeper and longer-trained attackers, plus random forests on tabular data. PriLO sensitive balanced accuracy is 3.50%3.50\% on HAR (chance 3.33%3.33\%) and 2.34%2.34\% on AudioMNIST (chance 1.67%1.67\%). Fano's inequality links true MI to optimal classification error, e.g. for a balanced binary label, Pe∗≥h2−1(1−I(Y;Z))P_e^*\geq h_2^{-1}(1-I(Y;Z)). Low BA does not certify privacy or bound macro-F1F_1. Membership inference was not tested.

7. Differential privacy

MI measures average dependence, not DP or worst-case disclosure. We claim no such guarantees; DP comparison needs a specified neighboring-dataset model.

8. Negative interaction example

Appendix A.5 takes independent fair bits A,B,C,DA,B,C,D, with S=(C,D)S=(C,D), U=(A,B)U=(A,B) and X=(A,C,B⊕D)X=(A,C,B\oplus D). Then I(S;U;X)=−1I(S;U;X)=-1 bit, yet Z=AZ=A satisfies I(S;Z)=0I(S;Z)=0 and I(U;Z)=I(U;X)=1I(U;Z)=I(U;X)=1. Thus priLO and utiLO share the jointly ideal point (1,0)(1,0) despite negative interaction; its sign alone is not sufficient for ideality.

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

This paper studies privacy-preserving representation learning under the Markov assumption. It derives the leakage bound and characterizes equality through qualified mechanisms. It then establishes necessary interaction-information conditions for qualification and joint ideality, and formulates privacy-first and utility-first lexicographic objectives. A neural implementation combines gradient projection with an adaptive finite-step safeguard. Experiments include analytically tractable synthetic problems and six real-world benchmarks.

Critical strengths
  1. The paper is well-written, easy to read and follow.

  2. The paper explicitly distinguishes analytical equality coordinates from attainable operating points. Appendix A.6 provides a useful counterexample showing that positive interaction information does not guarantee attainability of the privacy endpoint.

  3. The authors acknowledge substantial endpoint-recovery failures, including utility loss for priLO on AudioMNIST and degradation with increasing observation dimensionality.

Critical weaknesses
  1. The theoretical results characterize ideal lexicographic solutions, but the paper does not establish that the proposed neural training algorithm reaches these solutions. The substantial utility loss of priLO on AudioMNIST highlights this gap. Clarify this clearly in the paper.

  2. The theoretical contribution is useful but relatively limited without stronger attainability results. The paper acknowledges this issue, but provides neither broadly applicable sufficient conditions nor a characterization of the actual endpoints when the bound is loose. Consequently, the theory does not yet tell practitioners whether the analytical targets describe their problem.

Questions for authors
  1. Can the authors explain what guarantees the proposed training algorithm provides for finding a solution that respects the privacy-first or utility-first priority?

  2. Can the authors provide useful sufficient conditions for endpoint attainability beyond the shared/private-component constructions?

2 comments
AuthorsOpenReview ↗

Attainability conditions, realizable optima and neural convergence

We thank the reviewer for identifying two limitations of the original submission. We have added theoretical results addressing endpoint attainability and clarified the guarantees of the neural implementation.

1. Neural convergence and lexicographic priorities

We agree that the population-level recovery theorem does not guarantee neural convergence. Appendix A.10 proves that exact lexicographic optimization recovers a qualified equality endpoint whenever it is attainable. The neural algorithm is only an approximation to this optimization problem.

Appendix B.2 now establishes primary-loss monotonicity for exact safeguarded updates under LL-smoothness and a step size ηt≤1/L\eta_t\leq1/L. It also derives a nonconvex stochastic primary-stationarity bound with an O(T−1/4)O(T^{-1/4}) rate under specified assumptions and parameter schedules, based on the analysis from (Hsieh et al., 2024). Appendix B.3 validates convergence toward both the primary and restricted-secondary optima on a controlled exact-gradient problem.

These results concern fixed differentiable objectives, not convergence of jointly trained neural MI estimators to a global lexicographic optimum. We have made this limitation explicit. In particular, priLO's AudioMNIST utility macro-F1F_1 of 31.6%31.6\%, compared with 99.6%99.6\% for Z=XZ=X, remains an unresolved neural recovery failure.

2. Endpoint attainability and actual lexicographic optima

Appendix A.8 now gives necessary and sufficient attainability conditions directly in terms of P(S,U,X)P(S,U,X), without assuming a shared/private-component construction.

For the privacy endpoint, under sensitive-class overlap, a canonical posterior-ratio statistic g(X)\mathbf g(X) must satisfy a common posterior factorization and be independent of SS. For the utility endpoint, we derive joint-posterior conditions using the sufficient statistic t(X)=P(U=⋅∣X)\mathbf t(X)=P(U=\cdot\mid X), without requiring overlap.

Appendix A.9 goes further by characterizing both actual lexicographic optima, including cases where the analytical equality endpoints are unattainable. For finite S,US,U and standard Borel XX, the privacy-first optimum is characterized through convex-order optimization over output-posterior laws. The utility-first optimum has a unique optimal posterior law, attained by Z=t(X)Z=\mathbf t(X).

Reviewer_JirQOpenReview ↗

Official comment

Thank you for your response. Some of my concerns have been addressed. I maintain my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.