Differential Privacy Budget

Epsilon defines the privacy loss parameter—the maximum distance between the probability distributions of query outputs on two neighboring datasets differing by one record.

• ε = 0: Perfect privacy; outputs are identical regardless of any individual's presence. Utility is zero.
• ε < 1: Strong privacy guarantee; high noise injection.
• ε > 10: Weak privacy guarantee; minimal noise, approaching raw data release.

A lower epsilon forces the mechanism to add more calibrated noise, strictly bounding an adversary's ability to infer any single record's contribution.

Delta represents the failure probability of the pure ε-differential privacy guarantee. It allows for a small, negligible chance that the privacy loss bound defined by epsilon is exceeded.

• (ε, 0)-DP: Pure differential privacy; delta is zero. No catastrophic failure is tolerated.
• (ε, δ)-DP: Approximate differential privacy; a non-zero delta (e.g., 10⁻⁶) permits a tiny probability of information leakage beyond ε.

Delta is typically chosen to be cryptographically small—much smaller than the inverse of the dataset size—to ensure the risk of failure is practically non-existent.

The privacy budget is consumed additively. If you run two independent (ε₁)-DP and (ε₂)-DP mechanisms on the same dataset, the total privacy guarantee degrades to (ε₁ + ε₂)-differential privacy.

• Analogy: A fixed bank account. Each query is a withdrawal.
• Implication: A data scientist with a total budget of ε=1.0 cannot run 100 queries at ε=0.1 each without exceeding the limit.

This property forces careful accounting and query optimization to maximize utility before the budget is exhausted.

When differentially private mechanisms are applied to disjoint subsets of data, the privacy cost does not accumulate. The total privacy guarantee remains the maximum of the individual epsilons used.

• Rule: If user A's data is in Partition 1 and user B's data is in Partition 2, querying both partitions costs max(ε₁, ε₂), not ε₁ + ε₂.
• Benefit: Enables efficient scaling of private analytics across sharded or partitioned databases without linear budget depletion.

This is the foundational principle allowing large-scale private data aggregation systems to function.

Once the cumulative epsilon reaches the predefined global threshold, the data access is locked to prevent re-identification. This is a hard technical enforcement, not a policy suggestion.

• Mechanism: A privacy accountant module tracks total spend in real-time.
• Consequence: Subsequent queries are rejected or answered with pure noise, preserving the formal guarantee.
• Reset: The budget can only be reset by ingesting a new, independent dataset or by introducing a trusted data curator refresh.

This finite nature ensures that exhaustive statistical attacks are mathematically bounded.

Naive sequential composition (k*ε) is loose. Advanced composition theorems provide a tighter, sub-linear bound on total privacy loss over k adaptive queries.

• Result: For k queries, the total privacy loss is bounded by roughly O(√(k ln(1/δ)) * ε) rather than k*ε.
• Utility: Allows significantly more queries under the same total budget by leveraging the probabilistic nature of (ε, δ)-DP.
• Tools: Privacy accountants like the Rényi Differential Privacy (RDP) accountant or Privacy Loss Distribution (PLD) accountant use these theorems to track the precise moment the budget is exhausted.

Apple employs a technique known as Privacy-Preserving Data Collection using local differential privacy. Before user data (e.g., emoji usage, QuickType suggestions) leaves the device, it is randomized using ε = 4 per day. This finite budget limits the total information leaked about any single user's activity, even across millions of devices, ensuring aggregate trends are visible while individual inputs remain obscured.

To prevent reconstruction attacks on the decennial census, the Bureau replaced traditional swapping with a formal zero-Concentrated Differential Privacy (zCDP) framework. A global privacy-loss budget (ρ) was allocated across the entire publication system. This required a complex optimization problem to determine how much noise to inject into each query (age, race, housing) to maintain statistical fitness while exhausting the budget.

During the pandemic, Google published aggregated mobility trends from Location History data. They applied a differential privacy mechanism with a carefully calibrated epsilon to anonymize community movement patterns. The system added Laplace noise scaled to the sensitivity of the location queries. Once the daily epsilon budget was consumed, no further granular queries could be released, enforcing a hard mathematical limit on re-identification risk.

In cross-device federated training (e.g., Gboard), a per-round epsilon is spent when model updates are aggregated. To prevent the server from inspecting individual updates, Secure Aggregation protocols encrypt the gradients. The privacy accountant tracks the cumulative privacy loss over thousands of training rounds. Training halts automatically when the predefined global epsilon budget is exhausted, preventing model memorization of private user text.

Systems like Uber's Chorus or Tumult Analytics enforce a privacy budget at the database query layer. Analysts write standard SQL, but a middleware layer intercepts the query, calculates the privacy cost, and deducts it from a fixed epsilon pool. If a user requests a query that exceeds the remaining budget, the system blocks execution. This allows data scientists to explore sensitive tables without requiring deep differential privacy expertise.

Generative models (e.g., GANs) trained with DP-SGD (Differentially Private Stochastic Gradient Descent) produce synthetic datasets that mimic the statistical properties of real data. The privacy budget (ε) controls the fidelity-privacy trade-off. A low epsilon (ε < 1) guarantees strong privacy but may produce less realistic synthetic records, while a higher budget improves utility at the cost of greater privacy loss. The resulting synthetic data can often be shared freely without consuming further budget.