Composition Theorem

When multiple differentially private mechanisms are applied sequentially to the same dataset, the total privacy loss is the sum of the individual privacy losses.

• If mechanism M₁ provides ε₁-DP and M₂ provides ε₂-DP, the combined release provides (ε₁ + ε₂)-DP.
• This property governs iterative training loops where a model queries the dataset repeatedly.
• It is the primary reason a privacy budget must be carefully allocated and tracked across all steps of an algorithm.

When mechanisms are applied to disjoint, independent subsets of a dataset, the total privacy loss is bounded by the maximum of the individual losses, not their sum.

• If a dataset is partitioned into non-overlapping shards, applying an ε-DP mechanism to each shard yields an overall ε-DP guarantee.
• This property is the foundation of the Private Aggregation of Teacher Ensembles (PATE) framework, where teacher models train on disjoint data partitions.
• It enables efficient scaling of private computation across distributed data silos without consuming additional budget.

The naive sequential bound (summing epsilons) is often loose. Advanced composition theorems provide a tighter, sub-linear bound on total privacy loss for k-fold adaptive compositions.

• For (ε, δ)-DP mechanisms, the total loss after k iterations is approximately O(√k · ε), not k · ε.
• This is critical for Differentially Private Stochastic Gradient Descent (DP-SGD), which may require thousands of training iterations.
• The Moments Accountant and Rényi Differential Privacy (RDP) are modern techniques that achieve even tighter composition bounds by tracking higher-order moments of the privacy loss random variable.

A fundamental consequence of the composition theorem is that any computation applied to the output of a differentially private mechanism does not degrade the privacy guarantee.

• An adversary cannot "un-privatize" a noisy statistic by applying arbitrary post-processing functions.
• This property ensures that model weights trained with DP-SGD remain differentially private with respect to the training data, even if an attacker inspects or transforms the weights.
• It provides a crucial composability guarantee: private intermediate results can be safely used as inputs to subsequent, non-private computations without additional privacy cost.

The composition of mechanisms is fully characterized by the convolution of their privacy loss distributions (PLDs).

• The PLD is the probability distribution of the privacy loss random variable, which measures the log-ratio of output probabilities on neighboring datasets.
• Fourier accounting and other numerical methods compute the exact composed PLD, yielding the tightest possible (ε, δ) bounds.
• This approach underpins modern privacy accounting libraries like Google's TF Privacy and Meta's Opacus, enabling precise budget tracking for complex, adaptive compositions.

In practice, mechanisms are chosen adaptively based on the outputs of previous mechanisms. The composition theorem holds even under this worst-case scenario.

• An adversary can select the next query after observing all previous noisy outputs, and the composition bound still applies.
• This models the reality of interactive data exploration and iterative model training, where hyperparameters and architectures are tuned based on intermediate results.
• The guarantee is robust: the privacy loss accumulates independently of the analyst's strategy, preventing privacy budget gaming through adaptive query selection.

The foundational theorem stating that the total privacy loss parameter ε adds up linearly when multiple ε-differentially private mechanisms are applied to the same dataset.

• k-fold composition: Running k mechanisms, each with guarantee ε_i, results in a total guarantee of Σ ε_i.
• This is a conservative upper bound; tighter accounting methods like RDP often yield much lower total privacy loss.
• Governs the sequential consumption of a global privacy budget.

A rule stating that when differentially private mechanisms are applied to disjoint subsets of a dataset, the total privacy loss is the maximum ε among the mechanisms, not the sum.

• If a dataset is partitioned into independent shards, querying each shard once with ε-differential privacy yields an overall ε guarantee.
• This is critical for scaling privacy-preserving analytics across non-overlapping user groups or data silos.

A refinement over basic composition that provides a sub-linear bound on total privacy loss. For k (ε, δ)-DP mechanisms, the total loss is bounded by roughly O(√k · ε) rather than k · ε.

• Enables significantly more queries under the same privacy budget.
• Forms the theoretical basis for the Moments Accountant used in DP-SGD.
• Relies on the tail properties of the privacy loss distribution.

A privacy accounting method that tracks the log moments of the privacy loss random variable to compute a tight bound on the total (ε, δ) guarantee.

• Used in Differentially Private Stochastic Gradient Descent (DP-SGD) to track privacy loss across thousands of training iterations.
• Provides much tighter bounds than basic composition by accounting for the specific noise distribution (e.g., Gaussian) and privacy amplification by subsampling.

A privacy definition based on Rényi divergence that provides naturally tight composition bounds. Converting an RDP guarantee back to (ε, δ)-DP often yields a lower ε than tracking (ε, δ) directly.

• RDP parameters compose linearly by simple addition, making accounting trivial.
• The conversion to standard DP is done via a provable lemma, avoiding the looseness of advanced composition theorems.

A mechanism for enforcing a pre-set privacy budget in an online, adaptive setting. The odometer tracks cumulative privacy loss and halts all queries once the limit is reached.

• Prevents 'privacy budget overdraw' in interactive systems.
• Uses sequential composition guarantees to maintain a real-time, high-confidence upper bound on total ε.
• Essential for production systems serving arbitrary analyst queries.