Privacy Loss Distribution

The privacy loss is defined as the log-likelihood ratio of observing a specific output from a mechanism on two adjacent datasets. It is a random variable because the mechanism's output is random. The distribution of this variable captures the full probabilistic nature of the privacy guarantee, moving beyond a single parameter like epsilon.

When composing multiple mechanisms, the overall privacy loss distribution is the convolution of the individual loss distributions. This is the key to tight accounting:

• The Moments Accountant tracks the moment-generating function of this distribution.
• Rényi Differential Privacy computes the Rényi divergence of this distribution.
• Privacy Loss Distribution (PLD) accounting directly works with the distribution to find the smallest possible epsilon for a given delta.

Formally, for a mechanism M and adjacent datasets D and D', the privacy loss random variable L for an output o ~ M(D) is:

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

A pure ε-differential privacy guarantee means this random variable is absolutely bounded: |L| ≤ ε with probability 1. Approximate (ε, δ)-DP allows the bound to be violated with probability at most δ.

The relationship between ε and δ is fully determined by the tail behavior of the privacy loss distribution. The function δ(ε) gives the probability that the loss exceeds ε. This curve is the complete fingerprint of a mechanism's privacy guarantee:

• Gaussian Mechanism: The loss distribution is also Gaussian, leading to a specific δ(ε) curve.
• Subsampling: Randomly sampling data before applying the mechanism amplifies privacy by concentrating the loss distribution, dramatically improving the δ(ε) trade-off.

A mechanism satisfies (ε, δ)-DP if and only if the hockey-stick divergence between its output distributions on adjacent datasets is bounded. The privacy loss distribution is often analyzed through the lens of dominating pairs of distributions (P, Q) that represent the worst-case behavior. The hockey-stick divergence H_ε(P||Q) directly computes the δ for a given ε, enabling numerical composition algorithms.

Modern privacy accounting libraries (e.g., Google's DP Accounting, Microsoft's prv_accountant) implement fast Fourier transform (FFT) based methods to numerically convolve privacy loss distributions. This approach:

• Computes the exact composed δ(ε) curve for hundreds of thousands of DP-SGD steps.
• Avoids the looseness of advanced composition theorems.
• Enables real-time privacy budget tracking in production ML systems.

The fundamental random variable whose distribution defines the Privacy Loss Distribution. For a mechanism M, datasets D and D', and outcome o, it is computed as the log-ratio of probability densities: L = log(P[M(D)=o] / P[M(D')=o]). This variable captures the complete spectrum of privacy loss, not just its worst-case bound. The PLD is the distribution of this variable, and its tail bounds directly yield (ε, δ)-differential privacy guarantees.

A quantifiable limit on the total privacy loss permitted over a series of differentially private queries or training steps, parameterized by the privacy loss parameter epsilon (ε). The Privacy Loss Distribution is the tool used to track this budget precisely. Rather than using loose composition theorems, the PLD enables tight accounting by convolving the loss distributions of individual mechanisms, ensuring the cumulative loss remains within the predefined budget without over-allocating noise.

A relaxation of standard differential privacy based on Rényi divergence that provides tighter composition bounds. RDP defines privacy in terms of the moment of the privacy loss random variable: the RDP parameter ε(α) at order α is the log of the α-th moment of e^L. This is directly derived from the moment-generating function of the Privacy Loss Distribution, making RDP a natural intermediary for computing PLD-based accountants.

A specific privacy accounting technique that tracks the moment-generating function of the privacy loss random variable to compute tight bounds on overall privacy cost. Introduced by Abadi et al. for DP-SGD, it computes the log-moment at multiple orders α and converts them to (ε, δ) bounds. The Moments Accountant is a precursor to full Privacy Loss Distribution accounting, which tracks the entire distribution rather than just its moments for even tighter composition.

A fundamental differential privacy mechanism that achieves privacy by adding noise drawn from a Gaussian distribution calibrated to the L2 sensitivity of the query function. Its Privacy Loss Distribution is itself a Gaussian distribution: L ~ N(η, 2η) where η = (Δf)²/(2σ²). This closed-form PLD makes the Gaussian mechanism the workhorse of DP-SGD and enables precise composition analysis when convolving multiple Gaussian losses.

A privacy amplification phenomenon where randomly sampling a subset of data before applying a differentially private mechanism provides a stronger overall guarantee. The Privacy Loss Distribution under subsampling becomes a mixture distribution: with probability q (sampling rate), the loss follows the mechanism's PLD; with probability 1-q, the loss is zero. This mixture is the key to the tight accounting that makes DP-SGD practical.