Privacy Budget

The privacy budget is a strict upper bound on total privacy loss, denoted by epsilon (ε). Each differentially private query consumes a portion of this budget. Once the cumulative loss reaches the limit, no further queries are permitted on the dataset to maintain the global privacy guarantee. This forces a discipline of judicious query planning.

The total privacy loss from multiple queries is governed by composition theorems. Basic Composition states that the total epsilon is the sum of individual epsilons. Advanced Composition provides a tighter, sub-linear bound on total loss, allowing for more queries under the same total budget. This is the formal mechanism for tracking sequential consumption.

The budget is consumed differently based on data access patterns. Sequential composition on the same dataset sums the privacy loss. However, parallel composition on disjoint subsets of the data incurs no cumulative cost; the total privacy loss is the maximum of the individual queries. This property enables scalable, privacy-safe analytics on partitioned data.

A privacy odometer is a mechanism for enforcing a pre-defined budget in an online, adaptive setting. It continuously tracks the cumulative privacy loss as an analyst makes queries and halts all access the moment the total loss reaches the specified limit. This prevents accidental budget overruns and provides a hard guarantee.

A critical property is that the privacy budget is not consumed by post-processing. Any arbitrary computation performed on the output of a differentially private mechanism does not incur additional privacy loss. This means results can be normalized, visualized, or used in further non-private calculations without affecting the budget.

Effective use requires a strategy for dividing the total epsilon across tasks. Common approaches include:

• Uniform allocation: Assigning equal epsilon to each query.
• Weighted allocation: Giving more budget to higher-utility queries.
• Threshold-based access: Using the Sparse Vector Technique to only spend budget on queries that exceed a noisy threshold, conserving it for significant results.

The foundational mathematical framework that defines the privacy loss parameter epsilon (ε). A mechanism is ε-differentially private if the probability of any output changes by at most a factor of e^ε when a single record is added or removed. Lower epsilon values indicate stronger privacy guarantees but require more noise, directly consuming the privacy budget.

The formal rule governing how privacy loss accumulates across multiple queries. Sequential composition states that the total epsilon is the sum of individual epsilons. Advanced composition provides tighter bounds for (ε, δ)-DP mechanisms. This theorem is the accounting backbone of the privacy budget, dictating when a budget is exhausted and queries must halt.

A privacy accounting method that tracks the moments of the privacy loss random variable to compute a tight bound on total privacy loss. Essential for Differentially Private Stochastic Gradient Descent (DP-SGD) , it prevents overestimating privacy consumption during iterative training. This allows more training epochs within the same fixed privacy budget compared to naive composition.

A mechanism for enforcing a pre-defined privacy budget in an online, adaptive setting. The odometer continuously tracks cumulative privacy loss and halts further queries once the limit is reached. This prevents budget overspend in interactive data exploration systems where the sequence of queries is not known in advance.

A mechanism that efficiently answers a stream of threshold queries while conserving privacy budget. It only releases noisy answers for queries that exceed a dynamically calibrated, noisy threshold. This dramatically reduces budget consumption when only a small fraction of queries are statistically significant, making it ideal for anomaly detection and monitoring.

A privacy definition based on Rényi divergence that provides tighter composition bounds than standard (ε, δ)-DP. By tracking privacy loss in terms of RDP orders and converting back to (ε, δ)-DP at the end, it enables more accurate budget accounting for iterative algorithms, effectively allowing more computation under the same total privacy constraint.