Privacy Accounting

The fundamental property that privacy loss accumulates additively across multiple queries or training steps. If mechanism M₁ provides ε₁-differential privacy and M₂ provides ε₂-differential privacy, their sequential application on the same dataset provides (ε₁ + ε₂)-differential privacy. This linear accumulation is the primary reason privacy budgets deplete rapidly in iterative algorithms like DP-SGD, where each gradient step consumes a fraction of the total budget.

Refined bounds that account for the probabilistic nature of privacy loss rather than assuming worst-case linear accumulation. Advanced composition shows that applying a mechanism k times with (ε, δ)-differential privacy each time results in approximately (ε√(2k ln(1/δ')), kδ + δ')-differential privacy overall. This sub-linear scaling is critical for practical deployments, allowing many more queries than naive composition would permit while maintaining meaningful guarantees.

A state-of-the-art accounting technique that tracks the moment-generating function of the privacy loss random variable to compute tight, numerically accurate bounds on cumulative privacy expenditure. Introduced by Abadi et al. (2016) alongside DP-SGD, the moments accountant:

• Computes the log of the moment-generating function at each step
• Accumulates these logs across training iterations
• Converts the final accumulated moment bound back to (ε, δ) parameters
• Provides significantly tighter bounds than advanced composition for subsampled Gaussian mechanisms

An accounting framework based on Rényi divergence rather than the standard (ε, δ) definition. Rényi DP of order α bounds the Rényi divergence between output distributions on adjacent datasets. Key advantages:

• Exact composition: Privacy loss adds linearly under Rényi DP without approximation
• Tighter conversion: Converting Rényi DP guarantees back to (ε, δ)-DP yields tighter bounds than moments accountant in many regimes
• Natural fit for subsampling: The privacy amplification from subsampling has clean analytical forms under Rényi divergence

A probabilistic characterization that tracks the full distribution of the privacy loss random variable rather than just its tail bounds. The privacy loss random variable L = log(P(M(D)=o) / P(M(D')=o)) captures the complete information-theoretic divergence between outputs on adjacent datasets D and D'. Privacy loss distribution accounting:

• Enables privacy filters that halt computation when a precise budget threshold is crossed
• Supports privacy odometers that provide real-time budget consumption monitoring
• Allows composition of heterogeneous mechanisms with different privacy profiles

A phenomenon where randomly sampling a subset of data before applying a differentially private mechanism provides a stronger overall privacy guarantee than processing the full dataset. In DP-SGD, each batch is a random sample from the training set. The privacy amplification ratio depends on the sampling probability q = B/N (batch size / dataset size). For a Gaussian mechanism with noise σ, subsampling effectively multiplies the privacy guarantee by approximately q, enabling practical deep learning with differential privacy on large datasets while maintaining single-digit epsilon budgets.

A relaxation of standard differential privacy based on Rényi divergence that provides significantly tighter composition bounds than basic composition theorems. Unlike pure ε-differential privacy, RDP is parameterized by an order α, allowing accountants to track privacy loss across multiple orders simultaneously.

• Key advantage: Converts multiplicative composition into additive composition in log-space
• Common use: The default accounting method in DP-SGD implementations like Opacus
• Conversion: RDP guarantees can be converted back to standard (ε, δ)-DP bounds for reporting

A specific privacy accounting technique introduced by Abadi et al. (2016) that tracks the moment-generating function of the privacy loss random variable. By computing moments across all orders simultaneously, it produces dramatically tighter bounds than the naive strong composition theorem.

• Mechanism: Computes the log of the moment-generating function at each training step
• Result: Reduces total ε by 2-5x compared to advanced composition for equivalent iterations
• Integration: Built directly into the DP-SGD training loop for real-time budget tracking

A probabilistic characterization of the divergence between output distributions of a mechanism run on two adjacent datasets. Rather than tracking a single scalar ε, PLD accounting tracks the full distribution of the privacy loss random variable, enabling the tightest known composition bounds.

• Advantage: Captures the complete privacy loss profile, not just worst-case bounds
• Implementation: Used in Google's TF Privacy and the PLD Accountant library
• Trade-off: Higher computational cost for accounting, but yields optimal ε values

A privacy amplification phenomenon where randomly sampling a subset of data before applying a differentially private mechanism provides a stronger overall guarantee. When each example only participates with probability q, the privacy loss is amplified by a factor approximately equal to q.

• Mechanism: Poisson subsampling or shuffling with fixed batch sizes
• Effect: Converts an (ε, δ)-DP mechanism into an O(qε, qδ)-DP mechanism
• Critical for DP-SGD: Without subsampling, training deep models with meaningful privacy would be infeasible

A quantifiable limit on the total privacy loss permitted over a series of differentially private operations. The budget is parameterized by ε (epsilon), where smaller values indicate stronger privacy. Once the cumulative ε expenditure reaches the predefined threshold, no further queries or training steps are permitted.

• Typical ranges: ε = 0.1 to 10 for production systems
• Composition: Sequential queries sum their ε values under basic composition
• Enforcement: Requires real-time accounting integrated into query engines or training loops

A fundamental differential privacy mechanism that achieves (ε, δ)-DP by adding noise drawn from a Gaussian distribution calibrated to the L2 sensitivity of the query function. Unlike the Laplace mechanism, it provides only approximate DP but enables tighter composition through moments accounting.

• Noise scale: σ = Δ₂(f) · √(2·ln(1.25/δ)) / ε
• Advantage: Composes gracefully under subsampling and is the standard for DP-SGD
• Relationship: The noise added to gradients in DP-SGD is a direct application of the Gaussian mechanism