📊 statistics

Composition Theorems for Multiple Differential Privacy Constraints

This paper establishes a framework for the exact composition of mechanisms satisfying multiple simultaneous differential privacy constraints by deriving a structural lemma for mixtures of binary hypothesis tests, which yields a privacy region representable as a mixture of heterogeneous guarantees and generalizes to any number of constraints.

Original authors: Cemre Cadir, Salim Najib, Yanina Y. Shkel

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Cemre Cadir, Salim Najib, Yanina Y. Shkel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the guardian of a massive, secret library. Your job is to answer questions about the books inside without revealing any specific person's story. This is the world of Differential Privacy (DP).

In this paper, the authors (Cemre Cadir, Salim Najib, and Yanina Shkel) are solving a very tricky puzzle: What happens when you ask many questions, and each question has to follow two different sets of privacy rules at the same time?

Here is the breakdown using simple analogies.

1. The Problem: The "Double-Constraint" Guard

Usually, privacy rules are like a single speed limit sign.

Standard Rule: "You can drive up to 60 mph." (This is the standard $(\epsilon, \delta)$ privacy).
The Twist: Imagine a road where you have to obey two signs simultaneously:
1. "Don't go faster than 60 mph."
2. "Don't go faster than 40 mph."
- Result: You must drive at 40 mph. The stricter rule wins.

But in the real world of data, it's not always that simple. Sometimes, a data mechanism (a tool that answers questions) is good at hiding secrets in one way, but not another. It might be very strict about "Type A" leaks but slightly looser on "Type B" leaks.

The authors ask: "If I use this tool 100 times, and it has to satisfy BOTH Rule A and Rule B every single time, how much privacy do I actually have left?"

2. The Old Way vs. The New Way

The Old Way (The "Worst-Case" Guess): Previous methods were like a paranoid guard who assumes the worst possible scenario every time. They would say, "If you use this tool 100 times, you lose all privacy!" This is safe, but it's too pessimistic. It throws away useful data just to be safe.
The New Way (The "Recipe" Approach): The authors realized that instead of guessing, we can calculate the exact privacy loss. They found a mathematical "recipe" that mixes different types of privacy guarantees together to see the true result.

3. The Secret Sauce: The "Hypothesis Test"

To understand their math, imagine a game of "Guess the Neighbor."

The Setup: An attacker tries to guess if a specific person is in the database. They look at the output of your privacy tool.
The Trade-off: The tool tries to make it hard for the attacker.
- If the tool says "Yes," the attacker might be right (False Alarm).
- If the tool says "No," the attacker might be wrong (Missed Detection).
The Curve: The authors draw a line (a curve) showing the balance between these two errors. This is called the Privacy Region.

The Big Discovery:
The authors found that when you mix two different privacy tools (or one tool with two rules), the resulting "Privacy Region" isn't just a messy overlap. It's actually a mixture of simpler regions.

Think of it like mixing paint:

You have a bucket of "Red Privacy Paint" (Rule A).
You have a bucket of "Blue Privacy Paint" (Rule B).
Instead of just squishing them together, the authors found a way to calculate exactly what color you get when you mix them in specific proportions. They proved that the final color is a precise blend of the original colors.

4. The "Heterogeneous" Puzzle

The paper also solves a related puzzle: What if you use 50 tools of Type A and 50 tools of Type B?

Old thinking: "It's too complicated to calculate the exact mix."
New thinking: "We can treat this as a single, complex mixture."
The authors created an algorithm (a step-by-step recipe) that tells you exactly how much privacy is lost when you mix different types of tools. It's like a chef who can tell you exactly how a cake will taste if you swap 50% of the flour for almond meal, without having to bake it first.

5. Why Does This Matter? (The "f-DP" Connection)

There is a very advanced, flexible way to describe privacy called f-DP. It's like a super-precise ruler that can measure privacy in infinite ways. However, calculating the result of using f-DP tools many times is incredibly hard (like trying to solve a Rubik's cube blindfolded).

The Authors' Solution:
They showed that you can approximate this super-precise ruler (f-DP) by using their new "Double-Constraint" method.

They take the complex, hard-to-calculate f-DP rule.
They find the closest "Double-Constraint" rule that fits underneath it (like tracing a complex shape with simple blocks).
They calculate the result using their new easy recipe.
They do the same for a rule that fits above it.

The Result: You get a "sandwich" of privacy guarantees. You know the privacy loss is at least this much and at most that much. As you use the tools more and more, this sandwich gets tighter and tighter, giving you a near-perfect answer without the heavy math headache.

Summary

The Problem: Calculating privacy loss when multiple, different rules apply simultaneously is hard.
The Breakthrough: The authors proved that these complex mixes can be broken down into simple, calculable parts (like mixing paints or ingredients).
The Benefit: They provide a new, exact formula for calculating privacy loss in complex scenarios.
The Application: This allows data scientists to use advanced privacy tools (f-DP) with confidence, knowing exactly how much privacy they are sacrificing, rather than guessing or being overly conservative.

In short, they turned a "black box" of complex privacy math into a clear, transparent recipe that anyone can follow to ensure data stays safe.

1. Problem Statement

The paper addresses the challenge of composing differentially private (DP) mechanisms when a single mechanism must satisfy multiple simultaneous DP constraints.

Context: In many privacy applications, a mechanism is required to satisfy not just one $(\epsilon, \delta)$ -DP guarantee, but a set of them (e.g., satisfying both $(\epsilon_1, \delta_1)$ -DP and $(\epsilon_2, \delta_2)$ -DP simultaneously). This often arises when approximating $f$ -Differential Privacy ( $f$ -DP), where the trade-off function $f$ is approximated by the intersection of multiple $(\epsilon, \delta)$ constraints.
The Gap: Existing composition theorems (e.g., by Kairouz et al., Ghazi et al., Dong et al.) primarily handle single constraints or specific heterogeneous cases (e.g., pure $\epsilon$ -DP). There was no exact framework for the $k$ -fold composition of mechanisms satisfying double-DP (or $n$ -DP) constraints simultaneously.
Goal: To derive exact composition regions for mechanisms satisfying multiple DP constraints and use this to provide tighter approximations for $f$ -DP composition.

2. Methodology

The authors leverage the hypothesis testing perspective of differential privacy, where privacy is characterized by the trade-off function between Type I and Type II errors.

Structural Lemma for Mixtures (Lemma 1):
The core theoretical contribution is a lemma describing the trade-off function of a mixture of hypothesis tests. If a mechanism $M$ is a probabilistic mixture of $n$ sub-mechanisms with weights $\alpha_i$ and trade-off functions $f_i$ , the resulting trade-off function $f_m$ is the weighted infimal convolution of the individual $f_i$ :
$f_m(t) = \min_{\substack{t_i \in [0,1] \\ \sum \alpha_i t_i = t}} \sum_{i=1}^n \alpha_i f_i(t_i)$
Geometrically, the privacy region of the mixture is the convex hull (weighted sum) of the individual privacy regions.
Reduction to Heterogeneous Composition:
The authors show that a mechanism satisfying simultaneous $(\epsilon_1, \delta_1)$ and $(\epsilon_2, \delta_2)$ constraints can be modeled as a mixture of simpler mechanisms. Specifically, they construct a mechanism that behaves as an $\epsilon_1$ -DP mechanism with probability $1-\alpha$ and an $\epsilon_2$ -DP mechanism with probability $\alpha$ (plus a "leakage" component for $\delta > 0$ ).
This allows the problem of Double-DP composition to be reduced to the problem of Heterogeneous Composition (composing $x$ mechanisms of type 1 and $y$ mechanisms of type 2).
Exact Computation via Algorithm 1:
They provide an algorithm to compute the exact privacy region for the heterogeneous composition of $x$ $\epsilon_1$ -DP and $y$ $\epsilon_2$ -DP mechanisms. This involves:
1. Identifying all possible likelihood ratio slopes generated by the composition.
2. Calculating the corresponding $\delta$ offsets for each slope.
3. Intersecting the resulting $(\epsilon, \delta)$ regions.

3. Key Contributions

A. Exact Composition Theorems for Double-DP

The paper presents two theorems characterizing the exact privacy region $R^k(\epsilon, \delta)$ for the $k$ -fold composition of mechanisms satisfying two simultaneous constraints:

Theorem 2: Expresses the region as a mixture of heterogeneous composition regions $C_{i, k-i}(\epsilon_1, \epsilon_2)$ . It relies on the structural lemma to show that the composition of double-constraint mechanisms is equivalent to a mixture of compositions of pure $\epsilon$ -DP mechanisms.
Theorem 3: Provides a closed-form expression for the region without explicitly invoking the heterogeneous composition algorithm, derived by analyzing the likelihood ratios of the composed mechanism directly.

B. Heterogeneous Composition Theorem (Theorem 1)

The authors derive the exact privacy region for the composition of $x$ mechanisms of $(\epsilon_1, 0)$ -DP and $y$ mechanisms of $(\epsilon_2, 0)$ -DP.

This result is of independent interest as it generalizes previous work on pure $\epsilon$ -DP composition.
It offers lower computational complexity compared to existing heterogeneous composition methods (e.g., Murtagh et al.) by providing a closed-form characterization of the region boundaries.

C. Approximation of $f$ -DP Composition

The authors propose a method to approximate the composition of an arbitrary $f$ -DP mechanism:

Approximation: Approximate the target trade-off function $f$ from below ( $f_{\epsilon^-, \delta^-}$ ) and above ( $f_{\epsilon^+, \delta^+}$ ) using double-DP trade-off functions. This is achieved via a "normal rotation" of the function graph to find optimal tangent lines.
Composition: Use Theorems 2 and 3 to compute the exact $k$ -fold composition of these bounding double-DP mechanisms.
Result: This yields tight lower and upper bounds on the privacy region of the composed $f$ -DP mechanism.

4. Results and Evaluation

Tightness: The paper demonstrates that the proposed bounds are significantly tighter than previous baselines (such as the intersection of individual composition bounds or total variation bounds) especially as the number of compositions $k$ increases.
Gaussian Mechanism Example: Applied to the Gaussian mechanism (which is $G_\mu$ -DP), the method produces empirical bounds that converge rapidly to the exact composition region.
Comparison: The results show that while previous approximations (like the Central Limit Theorem approach by Dong et al.) are asymptotically tight, the proposed double-DP approach provides superior finite-sample guarantees and avoids the computational complexity of FFT-based methods.

5. Significance

Theoretical Advancement: This work bridges the gap between simple $(\epsilon, \delta)$ -DP and the more general $f$ -DP framework by providing the first exact composition theorems for mechanisms with multiple simultaneous constraints.
Practical Utility: It offers a computationally efficient way to analyze complex privacy budgets where mechanisms must satisfy multiple criteria (e.g., strict $\epsilon$ limits for some queries and relaxed $\delta$ limits for others).
Foundation for Future Work: The structural lemma regarding mixtures of hypothesis tests provides a general tool for analyzing complex privacy mechanisms. The authors conjecture that this framework can be generalized to $n$ -DP constraints (multiple simultaneous constraints), paving the way for even more precise privacy accounting in complex systems.

In summary, the paper provides a rigorous mathematical framework to handle the composition of mechanisms under complex, multi-faceted privacy constraints, significantly improving the accuracy of privacy loss accounting in practical differential privacy applications.