Privacy Budget

A privacy budget is a strict, non-renewable limit on cumulative privacy loss. Every query or analysis 'spends' a portion of the budget. Once the budget is exhausted, further access to the raw data must be denied to prevent reconstruction attacks. This is not a rate limit but a total lifetime consumption cap, formalized by the Composition Theorem.

The budget is parameterized by ε (epsilon), the privacy loss parameter. A smaller ε (e.g., 0.1) provides a stronger, more stringent privacy guarantee, as it tightly bounds the maximum divergence in output probabilities between neighboring datasets. A larger ε (e.g., 10) permits more information leakage, trading privacy for greater statistical accuracy.

When multiple differentially private mechanisms are applied to the same dataset, their privacy budgets add up linearly. If a query spends ε₁ and a second spends ε₂, the total privacy loss is ε₁ + ε₂. This sequential composition rule is fundamental to tracking cumulative leakage and enforcing the global budget limit.

When queries operate on disjoint, non-overlapping subsets of the data, the total privacy cost is the maximum of the individual queries, not their sum. This parallel composition property allows for efficient budget utilization in horizontally partitioned systems, such as federated learning across independent silos.

The budget directly governs the signal-to-noise ratio. A tight budget (low ε) requires injecting more calibrated noise (via the Laplace or Gaussian Mechanism), which degrades query accuracy. The core engineering challenge is architecting analyses to extract maximum statistical utility before the budget is fully depleted.

Naive linear composition can overestimate privacy loss. The Moments Accountant is a sophisticated technique used in DP-SGD that tracks higher-order moments of the privacy loss random variable. This provides a much tighter, non-linear bound on the total ε spent during iterative training, enabling more learning within the same budget.

The formal rule governing how privacy loss accumulates. Basic composition sums epsilons linearly: querying a dataset 10 times with ε=0.1 consumes a total budget of ε=1.0. Advanced composition provides tighter bounds, showing that the total loss scales proportionally to the square root of the number of queries, enabling more efficient budget utilization.

A privacy accounting technique that tracks higher-order moments of the privacy loss random variable rather than just the worst-case bound. This provides significantly tighter estimates of cumulative privacy loss during iterative training (e.g., DP-SGD), allowing more training epochs before exhausting the budget compared to naive composition.

A phenomenon where randomly sampling a subset of data before applying a differentially private mechanism amplifies the privacy guarantee. If each training step only processes a random mini-batch, the effective epsilon is much smaller than processing the full dataset, dramatically slowing budget consumption.

The maximum change in a query's output caused by adding or removing a single record. This directly determines the noise scale required: higher sensitivity demands more noise, consuming more budget per query. Reducing sensitivity through clipping or bounded queries is a primary strategy for budget conservation.

A resilience property guaranteeing that any computation applied to a differentially private output cannot weaken the privacy guarantee. Once a result is released under a specific epsilon cost, analysts can filter, transform, or visualize it freely without further budget consumption—a critical principle for efficient data release strategies.