Privacy Loss Distribution

The privacy loss random variable for a mechanism M on neighboring datasets D and D' is defined as the log-likelihood ratio of observing output o under M(D) versus M(D'). Its distribution over all possible outputs constitutes the privacy loss distribution (PLD). This distribution captures the complete privacy profile of a mechanism, encoding all information needed to derive any privacy parameter—including epsilon, delta, and Rényi divergences—without approximation.

For a fixed mechanism output o, the privacy loss is:

• L(o) = ln( Pr[M(D)=o] / Pr[M(D')=o] )

Key properties:

• Positive values indicate the output is more likely under D, potentially revealing membership
• Negative values indicate the output is more likely under D'
• Zero means the output is equally likely under both datasets
• The distribution of L(o) over the randomness of M fully determines the mechanism's privacy guarantees

The connection between the PLD and (ε, δ)-differential privacy is direct:

• A mechanism satisfies (ε, δ)-DP if and only if the probability that the privacy loss exceeds ε is bounded by δ
• Formally: Pr[ L(o) > ε ] ≤ δ under the distribution induced by M(D)
• This tail probability interpretation is the foundation of privacy accounting: tracking how the PLD evolves under composition to compute tight (ε, δ) guarantees

When multiple mechanisms are applied to the same dataset, their privacy loss distributions compose by convolution:

• The PLD of a sequence of k mechanisms is the k-fold convolution of their individual PLDs
• This follows from the additive property of log-likelihood ratios: the total privacy loss is the sum of individual losses
• Fourier accounting exploits this property by computing convolutions efficiently in the frequency domain using the fast Fourier transform (FFT)

A mechanism's privacy guarantee can be characterized by a dominating pair of distributions (P, Q) such that:

• The PLD of M on any neighboring datasets is stochastically dominated by the PLD of (P, Q)
• This reduces the analysis of complex mechanisms to studying a single pair of distributions
• For the Gaussian mechanism, the dominating pair consists of two Gaussian distributions with means ±(sensitivity/σ)²/2, enabling exact analytical privacy accounting

Modern privacy accounting relies on numerical computation of PLDs:

• Fourier accounting (Koskela et al.): Computes tight (ε, δ) bounds by convolving PLDs via FFT, achieving near-exact composition for DP-SGD
• Privacy loss distribution accounting (PLD accounting): Directly tracks the PLD through subsampling and composition steps
• Rényi DP to (ε, δ)-DP conversion: Uses the moments of the PLD to derive RDP guarantees, then converts to standard DP via optimized conversion formulas
• These methods significantly outperform the advanced composition theorem in tightness

The fundamental random variable whose distribution defines the PLD. For a mechanism M and adjacent datasets D, D', it is defined as the log-likelihood ratio of observing output o under M(D) versus M(D'). Formally: L_{M(D)||M(D')}(o) = ln( P[M(D)=o] / P[M(D')=o] ). The PLD is the distribution of this variable over all possible outputs. A mechanism is ε-DP if the absolute value of this variable is bounded by ε with probability 1.

A divergence measure that directly connects the PLD to (ε, δ)-differential privacy. For distributions P and Q, the hockey-stick divergence of order e^ε is D_{e^ε}(P||Q) = max_S [P(S) - e^ε Q(S)]. A mechanism satisfies (ε, δ)-DP if and only if D_{e^ε}(M(D)||M(D')) ≤ δ for all neighboring datasets. This divergence is the key tool for computing tight δ(ε) curves from the PLD.

A numerical privacy accounting method that computes the PLD of a composed mechanism by operating in Fourier space. The characteristic function of the PLD is the product of the characteristic functions of individual mechanisms. The Fourier accountant discretizes the PLD, applies FFT-based convolution, and reconstructs the composed PLD to extract tight (ε, δ) guarantees. This avoids the looseness of moment-based methods and is the state-of-the-art for DP-SGD composition.

The probability distribution of the privacy loss random variable, fully characterizing a mechanism's privacy properties. The PLD enables tight numerical composition through methods like Fourier accounting. Key properties:

• Support: The range of possible privacy loss values
• Tail bounds: Control the δ parameter in (ε, δ)-DP
• Convolution: The PLD of composed mechanisms is the convolution of individual PLDs
• Dominating pairs: A single pair of distributions whose PLD upper-bounds all neighboring dataset pairs

Functional representations of the privacy guarantee derived from the PLD. The δ(ε) curve maps each ε to the smallest δ such that (ε, δ)-DP holds. The f-DP trade-off curve maps false positive rates to false negative rates in membership inference. These curves are computed directly from the PLD and provide a complete, interpretable picture of privacy loss without reducing to a single parameter pair.

A privacy definition based on the Rényi divergence of order α between output distributions. RDP bounds the α-th moment of the privacy loss random variable: E[e^{(α-1)L}] ≤ e^{(α-1)ε}. The PLD's moment-generating function directly yields RDP parameters. RDP enables simple composition (additive in ε) and converts to (ε, δ)-DP via tail bounds, though it is generally looser than PLD-based Fourier accounting for heterogeneous mechanisms.