Privacy Budget

Epsilon (ε) is the primary parameter defining the strength of the privacy guarantee in differential privacy. It quantifies the maximum allowable privacy loss for an individual across an analysis.

• A lower ε value (e.g., 0.1) provides a stronger, more conservative privacy guarantee by permitting less information leakage.
• A higher ε value (e.g., 10.0) allows for greater data utility but offers a weaker privacy guarantee.
• The privacy budget is often expressed as a total cumulative ε that cannot be exceeded. Once spent, no further queries can be made on that dataset without violating the guarantee.

Delta (δ) is a secondary parameter in the relaxed (ε, δ)-differential privacy model. It represents a small, acceptable probability that the pure ε privacy guarantee is violated.

• Pure differential privacy has δ = 0.
• A non-zero δ (e.g., 1e-5) allows for the use of more efficient mechanisms like the Gaussian mechanism, which adds less noise than the Laplace mechanism for the same ε.
• δ must be set to a cryptographically small value, typically significantly less than 1/n (where n is the dataset size), to be considered safe against catastrophic privacy failure.

Sensitivity is a mathematical property of a query function that measures the maximum possible change in its output when a single individual's data is added or removed from the dataset.

• Global Sensitivity (Δf): The worst-case change across all possible neighboring datasets. It directly determines the scale of the noise that must be added. For a count query, Δf = 1. For a sum query, Δf is the maximum possible contribution of one record.
• The amount of noise (e.g., from a Laplace or Gaussian distribution) is scaled proportionally to Δf / ε. A higher sensitivity query consumes more of the privacy budget per unit of accuracy.

Composition theorems are the mathematical rules that govern how the privacy budget is consumed when multiple analyses are performed.

• Sequential Composition: The most straightforward rule. If you run k mechanisms with guarantees (ε₁, δ₁)...(εₖ, δₖ), the total privacy loss is (Σεᵢ, Σδᵢ). This is how a budget is tracked and depleted.
• Advanced Composition: Provides tighter bounds for many queries, allowing for a total ε that grows roughly with the square root of the number of queries under certain conditions, enabling more analyses for the same budget.
• Parallel Composition: If analyses are performed on disjoint subsets of the data, the privacy costs do not fully add up, allowing for more efficient budget utilization.

The privacy-utility trade-off is the fundamental tension managed by the budget. It describes the inverse relationship between the strength of privacy protection and the accuracy (utility) of the released data or model outputs.

• Spending more budget (higher ε) on a query allows for less noise to be added, yielding more accurate and useful results.
• Conserving budget (lower ε) forces the addition of more noise, protecting privacy but reducing result accuracy.
• Effective privacy budget management involves strategically allocating ε across different queries to maximize the overall utility of the released information while staying within the total allowable spend.

Managing a finite privacy budget requires strategic planning akin to financial budgeting.

• Static Allocation: Pre-determining a fixed ε for each planned query in a workflow. Simple but inflexible.
• Adaptive Allocation: Using an interactive system that tracks remaining budget in real-time and can allocate it dynamically based on intermediate results. More efficient but complex.
• Optimization for Workflows: Allocating more budget to high-value, low-sensitivity queries. For example, a query with global sensitivity Δf=1 will yield more accurate results per unit of ε than a query with Δf=100.
• The goal is to prevent budget exhaustion before critical analyses are complete, which would halt all further querying.