Epsilon (ε)

Epsilon defines the privacy loss budget—a finite, quantifiable resource consumed by every differentially private query. A smaller epsilon enforces a tighter bound on information leakage. Typical values range from ε = 0.01 (extremely strong privacy) to ε = 10 (weak privacy). Once the cumulative epsilon across all queries exceeds a predefined threshold, the dataset must be retired to prevent privacy exhaustion.

A randomized mechanism M satisfies ε-differential privacy if for all neighboring datasets D and D' (differing by one record) and all possible output sets S:

Pr[M(D) ∈ S] ≤ e^ε × Pr[M(D') ∈ S]

This inequality guarantees that an adversary observing the output cannot confidently determine whether any specific individual's data was included. The factor e^ε bounds the multiplicative difference in probabilities.

Epsilon directly governs the privacy-utility trade-off:

• Low ε (e.g., 0.1): Injects substantial noise, providing ironclad privacy but degrading statistical accuracy. Suitable for publishing census tables.
• High ε (e.g., 5.0): Adds minimal noise, preserving analytical utility but weakening the formal privacy guarantee. Used when accuracy is paramount.

Selecting epsilon requires balancing the risk of membership inference against the need for actionable insights.

Repeated queries on the same dataset consume the privacy budget cumulatively. Composition theorems quantify this accumulation:

• Basic Composition: The total epsilon after k queries is at most k × ε.
• Advanced Composition: Provides a tighter bound, showing that privacy degrades proportionally to √k, not k, when using Gaussian noise and a small failure probability δ.

This forces architects to track a global privacy accountant across all computations.

There is no universal 'correct' epsilon. Selection is context-dependent and often guided by regulatory or industry standards:

• U.S. Census Bureau: Uses ε = 19.61 for the 2020 decennial census redistricting data, a controversial choice balancing accuracy against re-identification risk.
• Apple's iOS QuickType: Deployed with a per-donor ε ≈ 4 for local differential privacy on emoji suggestions.
• Healthcare research: Often targets ε < 1 to protect patient-level data under HIPAA.

Pure ε-differential privacy can be overly restrictive. The relaxation (ε, δ)-differential privacy introduces a small failure probability δ, allowing a mechanism to violate the ε-bound with probability at most δ. This enables the Gaussian mechanism, which adds noise calibrated to L2 sensitivity. A typical δ value is chosen to be cryptographically small, such as 10^-5 or smaller than the inverse of the dataset size.

The cumulative limit on privacy loss across multiple queries. Each differentially private analysis consumes a portion of the total budget, typically tracked as the sum of epsilon values. Once the budget is exhausted, no further queries can be answered without risking re-identification. Composition theorems govern how epsilon accumulates:

• Sequential composition: Querying the same data k times with ε₁, ε₂, ..., εₖ results in total privacy loss Σεᵢ
• Parallel composition: Querying disjoint subsets of data incurs only the maximum ε among the queries
• Advanced composition: Provides tighter bounds for (ε, δ)-differential privacy under multiple queries

The maximum change in a query's output when a single record is added or removed. Sensitivity directly determines how much noise must be added to achieve a given epsilon guarantee. Key types:

• L1 Sensitivity (Δf₁): Maximum L1 distance between query outputs on neighboring datasets; used by the Laplace mechanism
• L2 Sensitivity (Δf₂): Maximum L2 distance; used by the Gaussian mechanism
• Local Sensitivity: The sensitivity of a query on a specific dataset instance, which can be much smaller than global sensitivity but risks leaking information if used naively

A query counting patients with a condition has sensitivity 1; a sum query has sensitivity equal to the maximum possible value.

The foundational mechanism for achieving pure ε-differential privacy. It adds noise drawn from a Laplace distribution centered at zero with scale parameter b = Δf₁/ε to the true query output. The Laplace distribution's exponential tail ensures that the probability ratio of any two outputs on neighboring datasets is bounded by e^ε.

Key properties:

• Satisfies ε-differential privacy (δ = 0)
• Optimal for L1 sensitivity and single numeric queries
• Noise magnitude scales linearly with sensitivity and inversely with epsilon
• Used extensively in the U.S. Census Bureau's 2020 Disclosure Avoidance System

Adds noise from a Gaussian (normal) distribution to satisfy approximate (ε, δ)-differential privacy. Unlike the Laplace mechanism, it introduces a small failure probability δ where the privacy guarantee may be violated. The standard deviation σ is calibrated to Δf₂, ε, and δ.

Advantages over Laplace:

• Tighter composition under multiple queries due to Gaussian tail properties
• Natural fit for machine learning where Gaussian noise is already used in optimization (e.g., DP-SGD)
• Smaller noise magnitude for high-dimensional queries with bounded L2 sensitivity

Trade-off: The δ parameter represents a tiny probability of catastrophic privacy failure, typically set to be cryptographically small (e.g., δ < 1/n where n is dataset size).

A stronger privacy model where noise is added on each user's device before data is transmitted to an untrusted aggregator. Unlike central DP where a trusted curator applies the mechanism, LDP protects against a malicious server. Each user's data satisfies ε-LDP independently.

Key distinctions from central DP:

• No trusted curator required; privacy is guaranteed at the data source
• Significantly more noise required to achieve the same utility as central DP for the same ε
• Used by Apple (iOS keyboard suggestions), Google (Chrome telemetry), and Microsoft (Windows telemetry)
• Randomized Response is the canonical LDP mechanism for binary attributes

In healthcare federated learning, LDP can protect patient data before gradient updates leave the hospital's firewall.

A relaxation of differential privacy based on Rényi divergence rather than max divergence, providing tighter composition bounds for iterative algorithms like DP-SGD. Parameterized by order α > 1, it interpolates between pure DP (α → ∞) and a more flexible privacy accounting.

Practical significance:

• Enables moments accountant, the privacy accounting technique used in DP-SGD for deep learning
• Provides much tighter ε bounds after many training iterations compared to strong composition theorems
• Converts to standard (ε, δ)-DP via a conversion lemma
• Underpins the privacy analysis in TensorFlow Privacy and Opacus libraries

For federated learning with hundreds of communication rounds, RDP accounting can mean the difference between a usable model and one destroyed by noise.