Differential Privacy Budget

Epsilon is the privacy loss parameter that defines the upper bound on information leakage. A smaller ε (e.g., 0.1) provides stronger privacy but adds more noise, while a larger ε (e.g., 10) yields higher accuracy at the cost of weaker guarantees.

• ε < 1: Considered strong privacy protection
• 1 < ε < 10: Moderate privacy, usable for most analytics
• ε > 10: Weak protection, approaching raw data exposure

The choice of ε is a policy decision balancing utility against the mathematical guarantee that an adversary cannot confidently determine whether any individual's record was included in the dataset.

The sequential composition theorem states that privacy loss accumulates additively across multiple queries. If you run query A with budget ε₁ and query B with budget ε₂, the total privacy cost is ε₁ + ε₂.

• Each query consumes a portion of the global budget
• A budget of ε=1.0 could be split into 10 queries at ε=0.1 each
• Once the cumulative sum reaches the cap, no further queries are permitted

This property enforces a hard mathematical limit, preventing death-by-a-thousand-cuts reconstruction attacks where an analyst runs thousands of slightly different queries to isolate a single record.

The parallel composition theorem provides a critical optimization: when queries operate on disjoint, non-overlapping subsets of the data, the total privacy cost equals the maximum of the individual budgets, not their sum.

• Queries on separate partitions do not accumulate additively
• Enables efficient budgeting for partitioned data architectures
• Total cost = max(ε₁, ε₂, ..., εₙ) for disjoint subsets

This property is essential for practical deployments, allowing organizations to run complex analytics across independent data silos without prematurely exhausting the global privacy budget.

At its core, differential privacy relies on the privacy loss random variable, which measures how much an adversary's belief about a single record changes after observing a query output. For a mechanism M, this is defined as:

• L = ln( P(M(D) ∈ S) / P(M(D') ∈ S) )
• Where D and D' are datasets differing by exactly one record
• Pure ε-differential privacy requires |L| ≤ ε for all possible outputs

This formulation guarantees that no output event can become significantly more or less likely due to the presence or absence of any individual, providing a worst-case mathematical guarantee rather than an average-case heuristic.

A privacy budget is a finite, non-renewable resource. When the cumulative ε expenditure reaches the predefined cap, the system must deny all further queries on that dataset.

• Budget exhaustion is a hard enforcement mechanism, not a warning
• Prevents the fundamental law of information recovery: with unlimited queries, noise can be averaged away
• Requires careful query planning and prioritization by data analysts

This hard stop is what distinguishes differential privacy from ad-hoc anonymization techniques. It provides a provable termination guarantee against reconstruction attacks, forcing adversaries to work within a mathematically bounded information channel.

Pure ε-differential privacy can be relaxed to (ε, δ)-differential privacy, where δ represents a small probability of catastrophic failure. Advanced composition theorems show that after k queries, privacy loss grows proportionally to √(k) * ε rather than k * ε.

• δ is typically set to be cryptographically small (e.g., 10⁻⁶ or smaller than 1/n)
• Enables sub-linear budget consumption for large query batches
• Used in practice by Apple, Google, and the US Census Bureau

This relaxation trades a negligible failure probability for dramatically improved utility, making differential privacy practical for real-world machine learning training runs requiring thousands of iterative queries.