Epsilon Budget

The most fundamental property: privacy loss is additive. If you run a query with privacy loss ε₁ and another with ε₂, the total privacy loss is ε₁ + ε₂. This is why the budget is a finite resource that must be carefully allocated across all queries against a dataset. Example: Three queries with ε=0.5 each consume a total budget of 1.5.

When queries operate on disjoint subsets of the data, the total privacy cost is the maximum of the individual queries, not the sum. This property allows for significant budget savings in well-partitioned systems. Example: A query on European users (ε=1.0) and a query on Asian users (ε=1.0) costs a total budget of 1.0, not 2.0, because no individual's data is in both subsets.

Once a result is released with a privacy guarantee ε, no further computation on that result can degrade the privacy guarantee. You can visualize, normalize, or run arbitrary functions on the noisy output without consuming additional budget. This property is crucial for building complex analytics pipelines where raw noisy outputs are transformed for presentation.

A budget is not infinite. When the cumulative ε reaches a pre-defined threshold, the privacy guarantee is considered exhausted. At this point, the data curator must either:

• Refuse further queries
• Add so much noise that results become meaningless
• Refresh the budget with a new, independent dataset

Setting this threshold is a policy decision balancing utility against risk.

While basic composition is linear, advanced composition theorems provide a tighter, sub-linear bound on total privacy loss for multiple adaptive queries. For k queries, the total loss is bounded by roughly O(√k) rather than k * ε, at the cost of introducing a small failure probability δ. This allows for significantly more queries under a fixed budget in practice.

The standard guarantee protects a single individual's record. If you need to protect a group of size g (e.g., a family), the privacy loss multiplies. A mechanism that is ε-differentially private for an individual is g·ε-differentially private for a group of size g. This is a direct consequence of the sequential composition property applied to correlated records.

The mathematical framework that defines the epsilon budget. It provides a provable guarantee that the output of an analysis is nearly identical whether or not any single individual is included in the dataset. The privacy loss parameter (ε) quantifies the maximum divergence between these two probability distributions.

The foundational noise-injection algorithm for achieving pure ε-differential privacy. It draws noise from a Laplace distribution calibrated to the L1 sensitivity (Δf) of the query and the allocated epsilon. Each invocation consumes exactly ε from the total budget.

• Noise scale: b = Δf / ε
• Higher sensitivity or lower epsilon results in more noise.

An alternative noise mechanism used for approximate (ε, δ)-differential privacy. It adds Gaussian noise calibrated to the L2 sensitivity and is preferred for high-dimensional queries where the Laplace mechanism would over-consume the budget. It introduces a failure probability δ, representing a tiny chance the privacy guarantee is violated.

A probabilistic tool for tight composition analysis. Instead of using loose worst-case bounds, the PLD tracks the exact distribution of privacy loss random variables across sequential mechanisms. This enables privacy accountants to calculate the precise cumulative ε after many queries, often yielding significantly lower total budget consumption than basic composition theorems.

The formal rules governing how epsilon budgets aggregate across multiple queries. Basic composition states that k mechanisms each using ε_i result in a total of Σε_i. Advanced composition provides a sub-linear bound, allowing for a total of O(√k * ε) under (ε, δ)-DP, which is critical for iterative machine learning training loops.

A relaxation of pure differential privacy based on the Rényi divergence. RDP provides much tighter composition bounds than standard DP, making it the preferred accounting method for differentially private stochastic gradient descent (DP-SGD). Privacy loss is tracked via moments of the privacy loss variable rather than a single absolute bound.