pith. sign in

arxiv: 2605.19474 · v1 · pith:JJJEFBVLnew · submitted 2026-05-19 · 💻 cs.IT · math.IT

Worst-Case Utility Privacy Mechanism via Pointwise Maximal Leakage

Ci Song , Tobias J. Oechtering This is my paper

Pith reviewed 2026-05-20 02:45 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords pointwise maximal leakageprivacy mechanismworst-case utilityutility optimizationdiscrete privacydifferential privacy comparison
0
0 comments X

The pith

The utility-safe mechanism optimally maximizes worst-case utility under pointwise maximal leakage privacy by allowing zero probabilities.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces a discrete privacy mechanism that uses Pointwise Maximal Leakage to maximize the worst-case utility given utility assignments for every input-output pair. PML permits setting some conditional probabilities to zero, which prevents low-utility outcomes while keeping the privacy constraint strict, unlike differential privacy. The authors prove that a simple utility-safe mechanism with low computational complexity is optimal when the output support set is fixed. Numerical experiments demonstrate the approach in several cases, highlighting how PML enables designs that avoid undesirable utilities.

Core claim

We show that the utility-safe mechanism, with low computational complexity, is optimal for the worst-case utility problem with an additional constraint on the output support set. This holds because PML allows conditional probabilities to be set to zero while preserving a strict privacy constraint, thereby preventing the occurrence of some low utilities.

What carries the argument

The utility-safe mechanism, which assigns outputs to maximize the minimum utility while satisfying the PML privacy constraint and respecting a fixed output support set.

Load-bearing premise

The PML privacy constraint remains strict and enforceable when some conditional probabilities are set to zero.

What would settle it

An input alphabet, utility assignment, and PML bound where some other mechanism satisfies the same privacy constraint and output support but yields a strictly higher worst-case utility than the utility-safe mechanism.

Figures

Figures reproduced from arXiv: 2605.19474 by Ci Song, Tobias J. Oechtering.

Figure 1
Figure 1. Figure 1: Sample minimum of utility given x when using ϵ-PML utility-safe (S), exponential (E), and randomized response (R) mechanisms. Utility-safe mechanism offers higher worst-case utility when the privacy level ϵ is not too low (here ϵ > 0.8). Other mechanisms do not improve their worst-case utility with increasing ϵ. B. Optimality The utility-safe mechanism is optimal if SY satisfies the constraint in (3). As i… view at source ↗
Figure 2
Figure 2. Figure 2: Lowest leakage under worst-case utility h ∗ and ‘one-low-three-high’ prior with the utility-safe mechanism (S) and optimal mechanism (O). Utility￾safe mechanism achieves optimal performance. 0.05 0.1 0.15 0.2 1 2 3 pmin minimum PML h ∗=3-S h ∗=3-O h ∗=2-S h ∗=2-O [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Lowest leakage under worst-case utility h ∗ and ‘three-low-one￾high’ prior with the utility-safe mechanism (S) and optimal mechanism (O). Suboptimality can be observed in low worst-case utility case (solid lines), while our utility-safe mechanism is optimal for higher utilities (dashed lines). The optimality of utility-safe mechanisms depends on many factors, including h ∗ , the pattern and value of the pr… view at source ↗
read the original abstract

We propose a discrete privacy mechanism exploiting beneficial properties of the novel privacy measure Pointwise Maximal Leakage (PML). Given the utility assignment characterized by every input-output letter pair, we study the mechanism design problem that satisfies PML privacy guarantees and maximizes the worst-case utility. Unlike popular privacy measures like Differential Privacy (DP), PML allows us to set some conditional probabilities in the mechanism to be zero and thereby preventing the occurrence of some low utilities while preserving a strict PML constraint. We show that the utility-safe mechanism, with low computational complexity, is optimal for the worst-case utility problem with an additional constraint on the output support set. We finally demonstrate the effectiveness in several numerical experiments. Due to DP's inability to have zeros in the mechanism, the design of privacy mechanisms that optimize the worst-case utility is underexplored, and this work shows that PML is a privacy measure that is perfectly suited for this purpose.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes a discrete privacy mechanism based on Pointwise Maximal Leakage (PML) to maximize worst-case utility subject to PML privacy guarantees. It introduces the utility-safe mechanism, which sets selected conditional probabilities to zero to avoid low-utility outcomes while preserving a strict PML bound, and claims this mechanism is optimal for the worst-case utility problem when an additional constraint on the output support set is imposed. Numerical experiments illustrate the approach and contrast it with Differential Privacy, which forbids zero probabilities.

Significance. If the optimality result holds, the work is significant for identifying PML as a privacy measure that enables mechanism designs focused on worst-case utility, an area underexplored under DP due to its positivity requirement. The low computational complexity of the proposed mechanism and the explicit handling of zero probabilities represent practical strengths. The paper supplies reproducible numerical examples that could serve as benchmarks for future PML-based designs.

major comments (2)
  1. [§4, Theorem 1] §4, Theorem 1: The optimality of the utility-safe mechanism under the output-support constraint is the central claim. The proof must explicitly verify that PML remains finite and well-defined when P_{Y|X}(y|x)=0 for selected pairs while P_Y(y)>0; if the expression in Eq. (8) involves a term such as log(1/P_Y(y)) or a supremum that becomes undefined precisely at these zeros, the claimed strict privacy guarantee and the distinction from DP would not hold.
  2. [§3.2, Eq. (12)] §3.2, Eq. (12): The definition of the utility-safe mechanism sets certain conditional probabilities to zero. It is unclear whether this construction preserves the feasible set of the original PML-constrained problem or inadvertently relaxes it via the added support constraint; the paper should show that any mechanism satisfying the original PML bound can be mapped to one satisfying the support constraint without decreasing worst-case utility.
minor comments (2)
  1. [Abstract] Abstract: The statement that the utility-safe mechanism has 'low computational complexity' is not quantified; a concrete complexity bound or comparison with exhaustive search should be added in §5.
  2. [Numerical experiments] Numerical experiments section: The utility assignment matrices used in the experiments should be reported explicitly (e.g., as a table) to support reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful review and valuable comments on our paper. The points raised regarding the proof of optimality and the relationship to the original optimization problem are well-taken. We provide point-by-point responses below and will update the manuscript to incorporate the suggested clarifications.

read point-by-point responses

  1. Referee: [§4, Theorem 1] §4, Theorem 1: The optimality of the utility-safe mechanism under the output-support constraint is the central claim. The proof must explicitly verify that PML remains finite and well-defined when P_{Y|X}(y|x)=0 for selected pairs while P_Y(y)>0; if the expression in Eq. (8) involves a term such as log(1/P_Y(y)) or a supremum that becomes undefined precisely at these zeros, the claimed strict privacy guarantee and the distinction from DP would not hold.

    Authors: We appreciate this observation. Upon re-examination, the definition of PML in our paper (see Section 2) is the supremum over x of log(P_{Y|X}(y|x)/P_Y(y)) for y in the support, but only for pairs where P_{Y|X}(y|x) > 0; when P_{Y|X}(y|x) = 0, that input does not contribute to the leakage for that y. The expression in Eq. (8) is constructed such that P_Y(y) is the marginal over the allowed support, ensuring it remains positive and the PML bound is strictly satisfied. To make this explicit, we will revise the proof of Theorem 1 to include a dedicated paragraph verifying the finiteness and well-definedness of PML under the zero-probability assignments. This will also reinforce why PML permits such zeros unlike DP. revision: yes

  2. Referee: [§3.2, Eq. (12)] §3.2, Eq. (12): The definition of the utility-safe mechanism sets certain conditional probabilities to zero. It is unclear whether this construction preserves the feasible set of the original PML-constrained problem or inadvertently relaxes it via the added support constraint; the paper should show that any mechanism satisfying the original PML bound can be mapped to one satisfying the support constraint without decreasing worst-case utility.

    Authors: The referee correctly identifies a potential gap in the exposition. The utility-safe mechanism is optimal within the class of mechanisms that satisfy both the PML constraint and the output support constraint. To connect it to the original problem, we will add a supporting argument (perhaps as a new proposition) showing that the worst-case utility achieved by the utility-safe mechanism is at least as high as that of any feasible mechanism in the original problem. This is because any mechanism with full support can be adjusted by setting low-utility conditional probabilities to zero while maintaining the PML bound through appropriate renormalization of the output distribution, without reducing the minimum utility. We believe this mapping preserves feasibility and does not relax the constraint. revision: yes

Circularity Check

0 steps flagged

No significant circularity; optimality follows from PML definition and support constraint without self-reduction.

full rationale

The provided abstract and text present the utility-safe mechanism as optimal for worst-case utility maximization under PML with an output-support constraint. This rests on PML's formal property of remaining well-defined and finite when selected conditional probabilities are zero (unlike DP), which is invoked as an external distinguishing feature rather than derived from the paper's own fitted values or prior self-citations. No equations or steps in the visible material reduce a claimed prediction or uniqueness result to a parameter fit or self-referential definition by construction. The derivation chain is therefore self-contained against the stated PML axioms and optimization setup, consistent with a standard theoretical contribution.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; the central claim rests on the unstated assumption that PML admits zero probabilities while remaining a valid privacy measure.

pith-pipeline@v0.9.0 · 5681 in / 1099 out tokens · 26795 ms · 2026-05-20T02:45:43.617082+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    The algorithmic foundations of differential privacy,

    C. Dwork and A. Roth, “The algorithmic foundations of differential privacy,”Found. Trends Theor. Comput. Sci., vol. 9, no. 3–4, pp. 211– 407, 2014

    work page 2014

  2. [2]

    Mechanism design via differential privacy,

    F. McSherry and K. Talwar, “Mechanism design via differential privacy,” in48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), 2007, pp. 94–103

    work page 2007

  3. [3]

    Universally utility- maximizing privacy mechanisms,

    A. Ghosh, T. Roughgarden, and M. Sundararajan, “Universally utility- maximizing privacy mechanisms,” inProceedings of the Forty-First Annual ACM Symposium on Theory of Computing, ser. STOC ’09. Association for Computing Machinery, 2009, p. 351–360

    work page 2009

  4. [4]

    An algorithm for enhancing privacy- utility tradeoff in the privacy funnel and other lift-based measures,

    M. A. Zarrabian and P. Sadeghi, “An algorithm for enhancing privacy- utility tradeoff in the privacy funnel and other lift-based measures,” in 2024 17th International Conference on Signal Processing and Commu- nication System (ICSPCS), 2024, pp. 1–7

    work page 2024

  5. [5]

    A linear reduction method for local differential privacy and log-lift,

    N. Ding, Y . Liu, and F. Farokhi, “A linear reduction method for local differential privacy and log-lift,” in2021 IEEE International Symposium on Information Theory (ISIT), 2021, pp. 551–556

    work page 2021

  6. [6]

    Optimal utility-privacy trade-off with total variation distance as a privacy measure,

    B. Rassouli and D. G ¨und¨uz, “Optimal utility-privacy trade-off with total variation distance as a privacy measure,”IEEE Trans. Inf. Forensics Secur., vol. 15, pp. 594–603, 2020

    work page 2020

  7. [7]

    Context-aware local informa- tion privacy,

    B. Jiang, M. Seif, R. Tandon, and M. Li, “Context-aware local informa- tion privacy,”IEEE Trans. Inf. Forensics Secur., vol. 16, pp. 3694–3708, 2021

    work page 2021

  8. [8]

    Pointwise maximal leakage,

    S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Pointwise maximal leakage,”IEEE Trans. on Inf. Theory, vol. 69, no. 12, p. 8054–8080, Dec. 2023

    work page 2023

  9. [9]

    Artificial intelligence risk management framework,

    National Institute of Standards and Technology, “Artificial intelligence risk management framework,” 2023

    work page 2023

  10. [10]

    Artificial intelligence act,

    European Union, “Artificial intelligence act,” Official Journal of the European Union, Regulation (EU) 2024/1689, 2024

    work page 2024

  11. [11]

    Rethinking disclosure prevention with pointwise maximal leakage,

    S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Rethinking disclosure prevention with pointwise maximal leakage,”J. Priv. Confid., vol. 15, Mar. 2025

    work page 2025

  12. [12]

    Privacy mechanism design based on empirical distributions,

    L. Grosse, S. Saeidian, T. J. Oechtering, and M. Skoglund, “Privacy mechanism design based on empirical distributions,” insubmitted to IEEE CSF 2026

    work page 2026

  13. [13]

    Extremal mechanisms for pointwise maximal leakage,

    L. Grosse, S. Saeidian, and T. J. Oechtering, “Extremal mechanisms for pointwise maximal leakage,”IEEE Trans. Inf. Forensics Secur., vol. 19, pp. 7952–7967, 2024

    work page 2024

  14. [14]

    Extremal mechanisms for local differential privacy,

    P. Kairouz, S. Oh, and P. Viswanath, “Extremal mechanisms for local differential privacy,”J. Mach. Learn. Res., vol. 17, no. 1, p. 492–542, Jan. 2016

    work page 2016

  15. [15]

    Limiting privacy breaches in privacy preserving data mining,

    A. Evfimievski, J. Gehrke, and R. Srikant, “Limiting privacy breaches in privacy preserving data mining,” inProceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, ser. PODS ’03, 2003, p. 211–222

    work page 2003

  16. [16]

    Local privacy and statistical minimax rates,

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 429–438

    work page 2013