Composition Theorems for Multiple Differential Privacy Constraints
This provides a foundational framework for analyzing privacy in complex systems with multiple constraints, which is incremental but important for privacy-preserving machine learning.
The paper tackles the problem of exactly composing mechanisms that satisfy multiple differential privacy constraints simultaneously, and shows that the resulting privacy region can be represented as a mixture over compositions with heterogeneous DP guarantees, generalizing to any number of constraints.
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.