Composition Theorems

The Sequential Composition Theorem states that the privacy parameters (epsilon and delta) add when multiple differentially private mechanisms are applied to the same dataset in sequence. If mechanism M1 is (ε₁, δ₁)-DP and mechanism M2 is (ε₂, δ₂)-DP, then their sequential composition satisfies (ε₁ + ε₂, δ₁ + δ₂)-DP. This is the fundamental rule for tracking a privacy budget.

• Key Implication: It enables the design of complex, multi-step private algorithms by allowing engineers to allocate portions of a total privacy budget to each step.
• Practical Use: Used in private machine learning where each training epoch or gradient update step consumes a portion of the overall budget.

The Parallel Composition Theorem provides a more favorable bound when mechanisms are applied to disjoint subsets of a dataset. If a dataset is partitioned into disjoint subsets, and a (ε, δ)-DP mechanism is applied to each partition, the overall process remains (ε, δ)-DP.

• Key Implication: Privacy loss does not compound across independent data partitions. This allows for highly scalable private analyses on large, partitioned data.
• Practical Use: Essential for privacy-preserving analytics in federated learning or distributed databases, where operations occur on separate user shards.

Advanced Composition Theorems provide tighter, more refined bounds for the composition of many mechanisms, improving over the simple linear addition of the basic sequential theorem. For k compositions of (ε, δ)-DP mechanisms, advanced composition can show the overall guarantee is approximately (ε√(2k log(1/δ')), kδ + δ')-DP for a chosen δ'.

• Key Implication: The privacy parameter grows with O(√k) rather than O(k), allowing for a much larger number of queries or iterations within a fixed privacy budget.
• Practical Use: Critical for enabling iterative algorithms like differentially private stochastic gradient descent (DP-SGD), which may require thousands of training steps.

Adaptive Composition considers the realistic scenario where each subsequent mechanism can be chosen adaptively based on the outputs of previous mechanisms. All standard composition theorems (sequential, parallel, advanced) hold under adaptive composition, which is the model used for most real-world privacy accounting.

• Key Implication: An adversary can adaptively choose queries based on past answers without weakening the proven composition bounds. This models realistic, interactive data analysis.
• Practical Use: Underpins privacy accounting in interactive systems like differentially private SQL interfaces, where the analyst's next question depends on earlier results.

Privacy Filters and Odometers are algorithmic constructs built upon composition theorems that allow for online or interactive privacy budgeting. A filter halts computation before a pre-specified privacy budget is exceeded, while an odometer tracks the spent budget in real-time.

• Key Implication: They enable the safe deployment of private algorithms where the total number of computations or queries is not known in advance.
• Practical Use: Used in systems that interactively answer an unknown number of user questions while guaranteeing the total privacy loss never surpasses a global limit (ε_total, δ_total).

Real-world private systems often compose mechanisms with different privacy guarantees (e.g., Laplace, Gaussian, Exponential mechanisms) and parameters. Composition theorems generalize to handle these heterogeneous compositions, with the overall (ε, δ) calculated by combining the respective parameters of each sub-mechanism.

• Key Implication: System designers can mix and match optimal mechanisms for different data types (numeric, categorical) or operations (counting, averaging, selection) within a single private pipeline.
• Practical Use: Designing a complex private data release that involves histogram queries (Laplace), means (Gaussian), and selecting a top-K result (Exponential mechanism) in a coordinated workflow.

This is the most direct application. When a data analyst runs multiple statistical queries (e.g., counts, averages, histograms) on the same dataset, each using a differentially private mechanism like the Laplace or Gaussian mechanism, the composition theorems provide the formula to compute the total privacy budget (ε_total, δ_total) consumed. This allows for the design of workflows where the analyst can 'spend' a pre-defined privacy budget across many questions, ensuring the entire process remains within a safe privacy limit.

• Example: A health researcher queries a private medical dataset 100 times, each with ε=0.01. Using basic sequential composition, the total privacy cost is a straightforward sum: ε_total = 1.0. Advanced composition allows for a tighter, more favorable bound.

Training machine learning models—like gradient descent for logistic regression or neural networks—requires hundreds or thousands of iterations over the training data. Differentially Private Stochastic Gradient Descent (DP-SGD) adds noise to gradient computations in each training step. Composition theorems are essential for tracking the privacy loss across all iterations, providing the final (ε, δ) guarantee for the trained model. Without composition, it would be impossible to offer a rigorous privacy promise for any iteratively trained model.

• Key Insight: The moment accountant and Rényi differential privacy are advanced composition techniques specifically developed to deliver much tighter privacy bounds for these iterative algorithms than naive sequential composition would allow.

Modern data pipelines are not single queries but directed acyclic graphs (DAGs) of operations: data cleaning, feature engineering, model training, and evaluation. Composition theorems enable privacy by design for these entire pipelines. Engineers can assign privacy parameters to each component and use composition rules (sequential, parallel, adaptive) to compute the end-to-end privacy guarantee. This modular approach is foundational to systems like Google's Differential Privacy Library and Microsoft's SmartNoise.

• Parallel Composition: A powerful rule stating that applying DP mechanisms to disjoint subsets of the data does not increase the overall ε for the worst-case individual, only the δ. This is crucial for partitioning data for scalable, private analysis.

In enterprise settings, a privacy budget is allocated per dataset or per user. Composition theorems are the accounting ledger. Every query or model training job consumes a portion of this budget (ε, δ). A privacy budget manager tracks cumulative consumption using composition rules, enforcing hard stops when the budget is exhausted. This creates an auditable trail, proving to regulators (and individuals) that data usage complied with pre-defined, quantifiable privacy limits.

• Compliance Use Case: Under frameworks like GDPR, demonstrating 'privacy by design' requires measurable controls. Composition theorems provide the necessary mathematics to generate an audit report showing total privacy loss never exceeded the policy-mandated threshold (e.g., ε=1.0, δ=1e-5).

Beyond simple summation, advanced composition theorems are a key application in themselves. They show that the privacy loss from k adaptive mechanisms grows much more slowly than k * ε—roughly on the order of √k. This quadratic improvement is what makes practical DP feasible. Libraries use these theorems to allow far more queries or training iterations for the same final privacy guarantee.

• Technical Note: Advanced composition introduces a small, non-zero δ (failure probability). This trade-off—accepting a tiny, quantifiable risk of catastrophic privacy failure (δ) for a vastly improved ε bound—is a critical engineering decision enabled by the (ε, δ)-differential privacy framework and its composition rules.

Composition theorems are not used in isolation. They are combined with other privacy-preserving techniques to build robust systems. For example:

• With Federated Learning: Each round of model aggregation from devices can be made differentially private. Composition theorems track the privacy loss across all communication rounds.
• With Secure Multi-Party Computation (MPC) or Homomorphic Encryption: DP noise can be added within a secure computation, and composition tracks the privacy loss of the overall secure protocol.
• With Synthetic Data Generation: A generative model (like a GAN) trained with DP-SGD has a privacy guarantee derived via composition. The theorem certifies that the entire synthetic dataset, not just the model, carries the composed (ε, δ) guarantee.

The foundational mathematical framework that composition theorems operate within. Differential privacy provides a rigorous, quantifiable guarantee that the output of an algorithm is statistically indistinguishable whether any single individual's data is included or excluded. It is defined by parameters epsilon (ε) and delta (δ), which bound the privacy loss.

• Core Property: The definition ensures that an adversary, seeing the algorithm's output, cannot confidently infer the presence or absence of any specific individual in the input dataset.
• Mechanisms: Achieved by injecting calibrated noise (e.g., via the Laplace or Gaussian mechanism) into query results.

A cumulative, trackable limit on the total allowable privacy loss, quantified by the epsilon parameter. Composition theorems are the rules for spending this budget across multiple analyses.

• Accounting: Every differentially private query consumes a portion of the total budget. Sequential composition theorems sum these individual epsilons.
• Management: In production systems, a privacy budget tracker is essential to enforce limits and prevent over-spending, which would violate the overall privacy guarantee.
• Example: If an analysis consists of 10 queries, each with ε=0.1, basic sequential composition states the total cost is ε=1.0.

The fundamental composition theorem for calculating privacy loss when multiple mechanisms are applied to the same dataset in sequence. The privacy parameters add up.

• Pure DP: For mechanisms satisfying (ε, 0)-differential privacy, the composition of k mechanisms satisfies (Σε_i, 0)-DP.
• Approximate DP: For (ε, δ)-DP mechanisms, the Advanced Composition Theorem provides a tighter, more favorable bound than simple summation, especially for large k.
• Use Case: This governs the design of complex data pipelines where multiple statistics (e.g., averages, counts, histograms) are released from one dataset.

A powerful theorem that applies when differentially private mechanisms are applied to disjoint subsets of a dataset. The overall privacy guarantee is based on the worst-case guarantee of any single mechanism, not their sum.

• Rule: If mechanism M1 with guarantee (ε, δ) operates on subset D1, and M2 with the same guarantee operates on disjoint subset D2, the overall release for D1 ∪ D2 still satisfies (ε, δ)-DP.
• Efficiency: This allows for highly scalable, privacy-preserving analytics. For example, calculating a statistic per hospital in a national database, where each patient's records are in only one hospital.
• Key Requirement: The data partitions must be disjoint and known a priori, independent of the private data itself.

Provides a tighter analysis of sequential composition for (ε, δ)-differential privacy, showing that the privacy loss grows sub-linearly in the number of compositions k under certain conditions.

• Result: For k mechanisms each satisfying (ε, δ)-DP, their k-fold adaptive composition satisfies (ε′, kδ + δ′)-DP for any δ′ > 0, where ε′ = ε√(2k log(1/δ′)) + kε(e^ε – 1).
• Significance: This is far more favorable than the naive ε_total = kε bound, enabling many more queries on the same privacy budget.
• Application: Essential for designing practical, iterative algorithms like private stochastic gradient descent, where the model is updated over thousands of steps.

The mathematical construct used to prove and refine composition theorems. It quantifies the actual privacy cost of observing an output, which is a random variable due to the noise injected by the DP mechanism.

• Definition: For a specific output, it's the log-ratio of the probability densities under two adjacent datasets. Composition corresponds to summing these random variables across mechanisms.
• Moment Accountants: Advanced composition tools like the Moments Accountant and Zero-Concentrated DP (zCDP) track the moments (e.g., the moment generating function) of this privacy loss variable to derive very tight composition bounds.
• Role: Moving from worst-case (ε) bounds to tracking the distribution of privacy loss enables optimal composition, minimizing the total epsilon spent.