Privacy Budget

Epsilon is the privacy loss parameter that quantifies the strength of the guarantee. A smaller ε (e.g., 0.1) provides stronger privacy by tightly bounding the output distribution divergence between neighboring datasets.

• ε = 0: Perfect privacy, but zero utility (output is pure noise).
• ε = 1: A common strong privacy setting; the probability of any output changes by at most a factor of e¹ ≈ 2.72.
• ε = 10: Weak privacy; high utility but significant leakage risk.
• The budget is consumed additively with each query under pure ε-differential privacy.

The sequential composition theorem states that privacy loss accumulates linearly. If you run mechanism M₁ with budget ε₁ and M₂ with budget ε₂ on the same dataset, the total privacy cost is ε₁ + ε₂.

• This is the fundamental accounting rule of a privacy budget.
• It forces a trade-off: every analytical query has a cost.
• A system with a total budget of ε=1.0 cannot run 100 queries at ε=0.1 each.
• Advanced composition theorems offer tighter bounds for multiple queries, allowing slightly more analysis under the same total ε.

The parallel composition property provides a critical optimization. When queries operate on disjoint subsets of the data, the total privacy cost is the maximum of the individual ε values, not the sum.

• If user records are partitioned into non-overlapping groups, querying each group independently costs only max(ε_i).
• This is essential for scalable federated analytics where clients hold distinct local datasets.
• It relies on strict data partitioning; overlapping records cause budget summation.
• Enables complex workflows like per-cohort statistical analysis without exhausting the global budget.

Once an output is generated under a differential privacy mechanism, any further computation on that output cannot degrade the privacy guarantee. This is the post-processing theorem.

• An analyst can apply arbitrary transformations, visualizations, or machine learning to a differentially private result without consuming additional budget.
• The privacy protection is future-proof: no matter what auxiliary information an attacker later obtains, the original ε-bound holds.
• This property decouples the privacy mechanism from downstream data science workflows.
• It ensures that releasing a noisy statistic is safe, even if the recipient performs sophisticated inference on it.

A privacy budget is a hard limit, not a guideline. When the cumulative ε reaches the predefined threshold, the system must refuse further queries on that dataset to maintain the provable guarantee.

• This prevents the slow, iterative extraction of sensitive information through repeated questioning.
• Budget exhaustion is a deliberate safety mechanism, not a failure state.
• Strategies to manage exhaustion include setting a per-user budget, refreshing budgets with new data, or using relaxed definitions like (ε, δ)-differential privacy.
• In federated learning, the budget may span thousands of training rounds, requiring careful allocation per round.

Pure ε-differential privacy can be overly restrictive. (ε, δ)-differential privacy introduces a small failure probability δ, allowing the privacy guarantee to be violated with probability at most δ.

• δ is typically chosen to be cryptographically small, e.g., 10⁻⁵ or smaller than 1/N where N is the dataset size.
• This relaxation enables much more efficient algorithms, such as the Gaussian mechanism, which underpins DP-SGD.
• The composition of (ε, δ) mechanisms is tracked using advanced moment accountant methods.
• A non-zero δ means there is a tiny chance of catastrophic privacy failure, so δ must be negligible relative to the dataset scale.

The unit of measurement for the privacy budget. A smaller epsilon (e.g., ε = 0.1) provides stronger privacy guarantees by forcing more noise into the output, while a larger epsilon (e.g., ε = 10) permits more accurate but less private results.

• Typical range: 0.01 to 10 in practice
• Composition: Epsilon values sum across sequential queries
• Trade-off: Directly balances utility against privacy

Mathematical rules governing how privacy loss accumulates when multiple differentially private mechanisms are applied to the same dataset. The privacy budget is consumed additively under basic composition.

• Basic Composition: ε_total = ε_1 + ε_2 + ... + ε_k
• Advanced Composition: Tighter bounds using probabilistic analysis
• Rényi DP: Enables more precise accounting of cumulative loss

The implementation mechanism that consumes the privacy budget. Calibrated random noise drawn from Laplace or Gaussian distributions is added to query results or gradients to mask the contribution of individual records.

• Laplace mechanism: Optimal for L1 sensitivity queries
• Gaussian mechanism: Preferred for L2 sensitivity in high dimensions
• Scale parameter: Determined by sensitivity divided by epsilon