arxiv: 2603.20968 · v2 · submitted 2026-03-21 · 💻 cs.IT · cs.CR· math.IT· math.ST· stat.TH

Recognition: 2 theorem links

· Lean Theorem

Composition Theorems for Multiple Differential Privacy Constraints

Cemre Cadir , Salim Najib , Yanina Y. Shkel

Authors on Pith no claims yet

Pith reviewed 2026-05-15 06:24 UTC · model grok-4.3

classification 💻 cs.IT cs.CRmath.ITmath.STstat.TH

keywords differential privacycomposition theoremsprivacy regionbinary hypothesis testsmultiple constraintsf-DP

0 comments

The pith

Mechanisms satisfying multiple simultaneous differential privacy constraints compose exactly as a mixture of heterogeneous single-constraint compositions.

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

This paper studies the exact composition of differential privacy mechanisms when two or more DP constraints must hold at once. It proves that the resulting privacy region equals a mixture of ordinary compositions, each using a different single privacy guarantee. The proof relies on a structural lemma about mixtures of binary hypothesis tests. The same construction extends immediately to any number of simultaneous constraints and is worked out in detail for approximate f-DP. The result gives a precise, non-approximate way to track privacy loss under layered guarantees.

Core claim

The exact composition of mechanisms for which two differential privacy constraints hold simultaneously admits an exact representation as a mixture over compositions of mechanisms of heterogeneous DP guarantees. This is established through a structural lemma for mixtures of binary hypothesis tests, and the framework generalizes to any number of DP constraints. The methodology is applied to approximate f-DP composition.

What carries the argument

Mixture representation of the privacy region over compositions of heterogeneous DP mechanisms, obtained from the structural lemma on mixtures of binary hypothesis tests.

If this is right

The privacy loss for any number of simultaneous constraints can be computed exactly by enumerating the relevant mixture components.
Approximate f-DP composition under multiple constraints reduces to the same mixture construction without additional approximation error.
Complex mechanisms can be analyzed by decomposing them into independent privacy constraints that are then recombined via the mixture.
The framework supplies a closed-form description of the overall privacy region rather than bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Designers of privacy systems could assign distinct constraints to different data subsets and still obtain an exact joint guarantee by the mixture rule.
The same structural lemma may apply to other hypothesis-testing-based privacy notions such as Renyi or concentrated DP.
Numerical verification on elementary mechanisms like Laplace noise with two different epsilon values would confirm or refute the mixture equality.
In federated or multi-party settings the approach offers a way to combine per-party privacy levels without conservative over-estimation.

Load-bearing premise

The structural lemma for mixtures of binary hypothesis tests holds for the mechanisms of interest and the simultaneous DP constraints can be treated as independent in the mixture.

What would settle it

A concrete mechanism such as the Gaussian mechanism with two simultaneous epsilon-delta pairs whose observed privacy region deviates from the mixture of the corresponding heterogeneous single-constraint compositions.

Figures

Figures reproduced from arXiv: 2603.20968 by Cemre Cadir, Salim Najib, Yanina Y. Shkel.

**Figure 1.** Figure 1: The trade-off functions f1.3,0 and f0.5,0.2, and their mixture with weights αi = 0.5. The mixture region does not necessarily include the union of the original regions. Likewise, it is not necessarily included in the union of the original regions. β m II as Pn i=1 αifi(ti). The precise arguments can be found in Appendix A. Equation (7) is known in the convex optimization literature as a weighted infimal co… view at source ↗

**Figure 2.** Figure 2: The privacy region of (ε, δ)-DP under k-fold composition with ε = (0.3, 0.15), δ = (0, 0.02) and k ∈ {3, 20}, as computed according to our result (Theorems 2-3) and prior works in Remarks 1 and 2. It is apparent that the previous bounds are close to the exact privacy region in the high privacy regime and with small k. As k increases, these approximations rapidly worsen. can also directly tackle it as follo… view at source ↗

**Figure 3.** Figure 3: Privacy region of Gaussian mechanism with [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

read the original abstract

The exact composition of mechanisms for which two differential privacy (DP) constraints hold simultaneously is studied. The resulting privacy region admits an exact representation as a mixture over compositions of mechanisms of heterogeneous DP guarantees, yielding a framework that naturally generalizes to the composition of mechanisms for which any number of DP constraints hold. This result is shown through a structural lemma for mixtures of binary hypothesis tests. Lastly, the developed methodology is applied to approximate $f$-DP composition.

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.

Desk Editor's Note private letter to a colleague

The paper offers an exact mixture-based composition for simultaneous multi-DP constraints via a structural lemma, but the handling of dependent tests on identical mechanisms needs close checking.

read the letter

The punchline is that this paper establishes an exact mixture representation for the composition of mechanisms under multiple simultaneous DP constraints, derived from a structural lemma on binary hypothesis test mixtures. It generalizes the idea to any number of constraints and applies it to approximate f-DP composition. This is a clean structural result that moves beyond standard single-constraint theorems and could support tighter accounting when constraints overlap in practice. The derivation looks formally grounded and avoids circularity by introducing the new lemma rather than fitting parameters. What the paper does well is lay out the mixture construction explicitly and show how it yields a framework for heterogeneous guarantees. The application section demonstrates the method on f-DP without adding extra assumptions. The main soft spot is the lemma's applicability when constraints act on the same mechanism and neighboring pair. In that setting the likelihood ratios are deterministically linked, so the binary tests are not independent. The mixture construction implicitly treats them as mixable without altering the convex hull of achievable error pairs. If the proof absorbs that dependence fully into the weights, the representation stays exact; if not, the joint privacy region claim weakens. The stress-test note on this point is worth checking against the full details. This paper is for researchers focused on differential privacy composition and privacy accounting. Readers working on f-DP or complex system deployments would find the structural approach useful. I recommend sending it for peer review. The central claim addresses a real gap and the formal steps are clear enough to merit referee time, even if the dependence issue requires verification.

Referee Report

1 major / 1 minor

Summary. The manuscript studies the exact composition of mechanisms satisfying two simultaneous differential privacy constraints. It claims that the resulting privacy region admits an exact representation as a mixture over compositions of mechanisms with heterogeneous DP guarantees. This is derived from a structural lemma on mixtures of binary hypothesis tests and is shown to generalize to any number of simultaneous DP constraints. The framework is applied to approximate f-DP composition.

Significance. If the structural lemma applies without loss of exactness to the joint DP setting, the result would provide a precise, non-asymptotic characterization of multi-constraint privacy regions. This advances composition theory beyond standard bounds and supplies a mixture-based representation that could support tighter privacy accounting for mechanisms subject to several guarantees at once.

major comments (1)

[structural lemma and privacy-region derivation] The central claim that the joint privacy region equals a mixture of heterogeneous single-constraint compositions rests on the structural lemma treating the binary hypothesis tests as independently mixable. When both DP constraints apply to the identical mechanism and neighboring dataset pair, the likelihood ratios are deterministically linked; the manuscript must verify that this dependence is fully absorbed into the mixture weights without altering the convex hull of achievable (type-I, type-II) error pairs (see the statement and proof of the structural lemma).

minor comments (1)

[abstract] The abstract states that the result follows from the structural lemma but does not list the lemma's assumptions; adding one sentence on the conditions under which the mixture representation remains exact would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our manuscript. We address the major comment regarding the structural lemma and the handling of dependence in the joint privacy setting below.

read point-by-point responses

Referee: [structural lemma and privacy-region derivation] The central claim that the joint privacy region equals a mixture of heterogeneous single-constraint compositions rests on the structural lemma treating the binary hypothesis tests as independently mixable. When both DP constraints apply to the identical mechanism and neighboring dataset pair, the likelihood ratios are deterministically linked; the manuscript must verify that this dependence is fully absorbed into the mixture weights without altering the convex hull of achievable (type-I, type-II) error pairs (see the statement and proof of the structural lemma).

Authors: We appreciate the referee's careful scrutiny of the structural lemma's applicability in the joint setting. The lemma itself is stated in a general form that does not assume independence of the hypothesis tests; it applies to any mixture of distributions, including those where the likelihood ratios are dependent due to being derived from the same mechanism. In the proof of Theorem 1, the mixture weights are derived from the joint distribution of the outputs under the neighboring datasets, which inherently incorporates the deterministic linkage between the two likelihood ratios. This ensures that the resulting privacy region is exactly the convex hull of the heterogeneous compositions without any loss from the dependence. To make this explicit, we will add a clarifying paragraph in Section 3.2 explaining how the joint probability measure is used to define the mixture, along with a small illustrative example for a simple mechanism satisfying two constraints simultaneously. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation rests on independently stated structural lemma

full rationale

The paper establishes the exact composition result for simultaneous DP constraints by proving a structural lemma on mixtures of binary hypothesis tests, then applying it to represent the joint privacy region as a mixture over heterogeneous single-constraint compositions. This lemma is presented as a new, self-contained result rather than a redefinition of the target quantity or a fit to the same data. No equations reduce the claimed representation to its inputs by construction, no parameters are fitted and then relabeled as predictions, and no load-bearing step depends on a self-citation chain or imported uniqueness theorem. The generalization to arbitrary numbers of constraints follows directly from the same lemma without circular closure. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on standard differential privacy definitions and the new structural lemma for mixtures of binary hypothesis tests; no free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Standard definitions of differential privacy and f-DP
The paper builds directly on established DP notions without re-deriving them.

pith-pipeline@v0.9.0 · 5369 in / 1244 out tokens · 34482 ms · 2026-05-15T06:24:32.741172+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 1: fm(t) = min_{ti} ∑ αi fi(ti) s.t. ∑ αi ti = t (weighted infimal convolution of trade-off functions)
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat recovery and embed_strictMono unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2: Rk(ε,δ) expressed as mixture δ̃ R(0,1) + (1-δ̃) ∑ binom(k,i) (1-α)^i α^{k-i} C_{i,k-i}(ε)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

[1]

Calibrating noise to sensitivity in private data analysis,

C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” inTheory of Cryptography: Third Theory of Cryptography Conference. Springer, 2006, pp. 265–284

work page 2006
[2]

Our data, ourselves: Privacy via distributed noise generation,

C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” inAdvances in Cryptology-EUROCRYPT 2006: 24th Annual International Confer- ence on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25. Springer, 2006, pp. 486–503

work page 2006
[3]

Gaussian differential privacy,

J. Dong, A. Roth, and W. J. Su, “Gaussian differential privacy,”Journal of the Royal Statistical Society: Series B (Statistical Methodology), vol. 84, no. 1, pp. 3–37, 2022

work page 2022
[4]

A statistical framework for differential privacy,

L. Wasserman and S. Zhou, “A statistical framework for differential privacy,”Journal of the American Statistical Association, vol. 105, no. 489, pp. 375–389, 2010

work page 2010
[5]

The composition theorem for differential privacy,

P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,”IEEE Transactions on Information Theory, vol. 63, no. 6, pp. 4037–4049, 2017

work page 2017
[6]

Total variation meets differential privacy,

E. Ghazi and I. Issa, “Total variation meets differential privacy,”IEEE Journal on Selected Areas in Information Theory, 2024

work page 2024
[7]

Differential privacy: A survey of results,

C. Dwork, “Differential privacy: A survey of results,” inInternational conference on theory and applications of models of computation. Springer, 2008, pp. 1–19

work page 2008
[8]

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. IEEE, 2013, pp. 429–438

work page 2013
[9]

Extremal mechanisms for local differential privacy,

P. Kairouz, S. Oh, and P. Viswanath, “Extremal mechanisms for local differential privacy,”Advances in neural information processing systems, vol. 27, 2014

work page 2014
[10]

Local, private, efficient protocols for succinct histograms,

R. Bassily and A. Smith, “Local, private, efficient protocols for succinct histograms,” inProceedings of the forty-seventh annual ACM symposium on Theory of computing, 2015, pp. 127–135

work page 2015
[11]

The complexity of computing the optimal composition of differential privacy,

J. Murtagh and S. Vadhan, “The complexity of computing the optimal composition of differential privacy,” inTheory of Cryptography Confer- ence. Springer, 2015, pp. 157–175

work page 2015
[12]

Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang

M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS’16. ACM, Oct. 2016. [Online]. Available: http://dx.doi.org/10.1145/2976749.2978318

work page doi:10.1145/2976749.2978318 2016
[13]

Concentrated differential privacy: Simpli- fications, extensions, and lower bounds,

M. Bun and T. Steinke, “Concentrated differential privacy: Simpli- fications, extensions, and lower bounds,” inTheory of cryptography conference. Springer, 2016, pp. 635–658

work page 2016
[14]

Rényi differential privacy,

I. Mironov, “Rényi differential privacy,” in2017 IEEE 30th Computer Security Foundations Symposium (CSF), 2017, pp. 263–275

work page 2017
[15]

Computing tight differential privacy guarantees using fft,

A. Koskela, J. Jälkö, and A. Honkela, “Computing tight differential privacy guarantees using fft,” inInternational Conference on Artificial Intelligence and Statistics. PMLR, 2020, pp. 2560–2569

work page 2020
[16]

A better bound gives a hundred rounds: Enhanced privacy guarantees via f- divergences,

S. Asoodeh, J. Liao, F. P. Calmon, O. Kosut, and L. Sankar, “A better bound gives a hundred rounds: Enhanced privacy guarantees via f- divergences,” in2020 IEEE International Symposium on Information Theory (ISIT). IEEE, 2020, pp. 920–925

work page 2020
[17]

When machine learning meets privacy: A survey and outlook,

B. Liu, M. Ding, S. Shaham, W. Rahayu, F. Farokhi, and Z. Lin, “When machine learning meets privacy: A survey and outlook,”ACM Computing Surveys (CSUR), vol. 54, no. 2, pp. 1–36, 2021

work page 2021
[18]

Numerical composition of dif- ferential privacy,

S. Gopi, Y . T. Lee, and L. Wutschitz, “Numerical composition of dif- ferential privacy,”Advances in Neural Information Processing Systems, vol. 34, pp. 11 631–11 642, 2021

work page 2021
[19]

Computing differential privacy guar- antees for heterogeneous compositions using fft,

A. Koskela and A. Honkela, “Computing differential privacy guar- antees for heterogeneous compositions using fft,”arXiv preprint arXiv:2102.12412, 2021

work page arXiv 2021
[20]

Optimal accounting of differential privacy via characteristic function,

Y . Zhu, J. Dong, and Y .-X. Wang, “Optimal accounting of differential privacy via characteristic function,” inInternational Conference on Artificial Intelligence and Statistics. PMLR, 2022, pp. 4782–4817

work page 2022
[21]

Local differential privacy and its applications: A comprehensive survey,

M. Yang, T. Guo, T. Zhu, I. Tjuawinata, J. Zhao, and K.-Y . Lam, “Local differential privacy and its applications: A comprehensive survey,”Computer Standards & Interfaces, vol. 89, p. 103827, 2024. [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S0920548923001083

work page 2024
[22]

Composition in differential privacy for general granularity notions,

P. Guerra-Balboa, À. Miranda-Pascual, J. Parra-Arnau, and T. Strufe, “Composition in differential privacy for general granularity notions,” in2024 IEEE 37th Computer Security Foundations Symposium (CSF). IEEE, 2024, pp. 680–696

work page 2024
[23]

Mixtures and Products of Dominated Experiments,

E. N. Torgersen, “Mixtures and Products of Dominated Experiments,” The Annals of Statistics, vol. 5, no. 1, pp. 44 – 64, 1977. [Online]. Available: https://doi.org/10.1214/aos/1176343739

work page doi:10.1214/aos/1176343739 1977
[24]

L. M. Le Cam,Asymptotic methods in statistical decision theory, ser. Springer series in statistics. New York: Springer-Verlag, 1986

work page 1986
[25]

H. H. Bauschke and P. L. Combettes,Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 1st ed. Springer Publishing Company, Incorporated, 2011

work page 2011
[26]

Boyd and L

S. Boyd and L. Vandenberghe,Convex Optimization. Cambridge University Press, 2004

work page 2004
[27]

Equivalent comparisons of experiments,

D. Blackwell, “Equivalent comparisons of experiments,”Annals of Mathematical Statistics, vol. 24, pp. 265–272, 1953. [Online]. Available: https://api.semanticscholar.org/CorpusID:122228054

work page 1953