Privacy Loss Distribution (PLD)

Unlike Rényi Differential Privacy (RDP) or moments accountant which summarize privacy loss into a single scalar moment, PLD accounting maintains the complete probability distribution of the privacy loss random variable. This captures the exact tail behavior of the privacy loss, avoiding the looseness introduced by moment-based bounds. The distribution is represented as a discrete histogram over possible epsilon values, updated at each composition step through convolution operations.

PLD accountants compose mechanisms by convolving their individual privacy loss distributions rather than summing moment-generating functions. For a sequence of mechanisms M₁, M₂, ..., Mₖ, the composed PLD is computed as the convolution of their individual distributions. This exact arithmetic on distributions eliminates the compounding approximation error inherent in RDP-to-DP conversion, often yielding 20-40% tighter epsilon values for the same delta parameter in DP-SGD training runs.

PLD accounting is grounded in the concept of dominating pairs of distributions (P, Q) that bound the behavior of the mechanism on adjacent datasets. The privacy loss distribution is derived from the log-likelihood ratio between these dominating distributions. The final (ε, δ) guarantee is computed using the hockey-stick divergence: E_{Y∼P}[max(0, 1 - e^{ε} · (dQ/dP)(Y))] ≤ δ. This formulation provides an exact characterization of the privacy guarantee without intermediate relaxations.

The core object in PLD accounting is the privacy loss random variable L = log(P(M(D) = o) / P(M(D') = o)), where D and D' are adjacent datasets. For DP-SGD with Gaussian noise, this variable follows a shifted and scaled non-central chi-squared distribution. PLD accountants numerically compute and track this distribution across training iterations, capturing the precise probability of large privacy losses that determine the final (ε, δ) guarantee.

Modern DP libraries implement PLD accounting through fast Fourier transform (FFT) based convolution on discretized privacy loss distributions. The open-source opacus library from Meta and Google's dp_accounting library both support PLD accountants. Key implementation details include:

• Discretization granularity: finer bins yield tighter bounds at computational cost
• Truncation bounds: clipping the distribution tails introduces negligible error
• Adaptive composition: supports variable noise multipliers and sampling rates across training

PLD accounting provides strictly tighter bounds than the moments accountant (RDP) for Gaussian mechanisms under Poisson subsampling. Empirical comparisons show:

• ~30% reduction in epsilon for typical DP-SGD settings (σ=1.0, q=0.01, 10⁴ iterations)
• No conversion loss: RDP must convert to (ε, δ)-DP via an inequality that introduces slack
• Handles heterogeneous compositions naturally, where noise multipliers or sampling rates vary across training steps
• Direct (ε, δ) output without intermediate RDP orders that require optimization

The fundamental building block of PLD accounting. For a mechanism M, the privacy loss random variable is defined as the log-ratio of the probability of observing an output under two neighboring datasets:

L = log( P[M(D)=o] / P[M(D')=o] )

• Support: Can take negative values (evidence for absence) and positive values (evidence for presence)
• Tail bounds on this random variable directly yield (ε, δ)-DP guarantees
• PLD tracks the full distribution of L rather than just its moments

The probability distribution of the privacy loss random variable, denoted as ω, which captures the complete privacy leakage profile of a mechanism:

• Discrete distribution for composed mechanisms, represented as a probability mass function over loss values
• Dominating pairs of distributions (P, Q) define the PLD where P models output on D and Q models output on D'
• Enables tight composition by convolving PLDs rather than summing moment bounds
• The hockey-stick divergence between P and Q at threshold ε yields the exact δ(ε) curve

A relaxation of pure DP based on Rényi divergence of order α between output distributions on neighboring datasets:

Dα(P||Q) = (1/(α-1)) log E[(P/Q)^α]

• RDP parameters (α, ε) convert to (ε, δ)-DP via tight conversion formulas
• PLD-based accounting subsumes RDP: RDP bounds the α-moment of the privacy loss, while PLD captures the full distribution
• RDP composition is additive across mechanisms but looser than PLD convolution for heterogeneous steps
• Commonly used as a lightweight alternative when full PLD tracking is computationally expensive

A precise accounting method that tracks the full distribution of privacy loss random variables across composed mechanisms, enabling tighter privacy budget calculations than moment-based accountants:

• Convolution: The PLD of composed mechanisms is the convolution of individual PLDs, computed efficiently via FFT
• Truncation: Tail probabilities below a threshold are accumulated into δ, providing the (ε, δ)-DP guarantee
• Heterogeneous composition: Unlike RDP or moments accountant, PLD handles varying noise scales and sampling rates natively
• Implemented in Google's DP libraries and the open-source opacus and tf-privacy frameworks

The exact operational quantity connecting PLD to (ε, δ)-DP guarantees. For distributions P and Q:

Hε(P||Q) = ∫ max(p(x) - e^ε q(x), 0) dx

• A mechanism is (ε, δ)-DP if and only if Hε(P||Q) ≤ δ for all neighboring datasets
• The trade-off curve δ(ε) is computed by evaluating Hε at each ε of interest
• PLD accountants precompute this curve once and interpolate to answer privacy budget queries
• Provides the tightest known characterization of differential privacy for composed mechanisms

The property where randomly sampling a subset of data for each training step amplifies the privacy guarantee, as the uncertainty of inclusion provides an additional layer of deniability:

• Poisson subsampling: Each record is included independently with probability q, yielding a dominant pair (qP + (1-q)Q, Q)
• Shuffling: Random permutation followed by fixed-size batches provides stronger amplification than independent sampling
• PLD accountants model subsampling by transforming the PLD of the base mechanism before convolution
• The amplification effect is non-linear in the sampling rate, making PLD tracking essential for accurate accounting