Epsilon (ε)

Epsilon (ε) is the upper bound on privacy loss. Formally, a randomized mechanism M satisfies (ε, δ)-differential privacy if, for all neighboring datasets D and D' differing by one record and all outputs S, the probability ratio is bounded: Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S] + δ. A smaller ε makes the two probabilities more similar, making it harder to distinguish if a specific individual's data was in the dataset. This bound is additive across multiple queries on the same dataset, requiring careful budget management.

Epsilon directly controls the fundamental trade-off between privacy and model utility. Adding calibrated noise to achieve a small ε (e.g., ε < 1.0) provides strong privacy but degrades the signal-to-noise ratio in model updates, potentially slowing convergence and reducing final accuracy. A larger ε (e.g., ε > 5.0) adds less noise, preserving utility but offering weaker formal guarantees. In federated learning, this manifests as a choice: a highly private global model with lower accuracy or a more accurate model with increased privacy risk. Techniques like adaptive budget allocation and privacy amplification by subsampling can help optimize this trade-off.

Privacy loss accumulates. Core composition theorems govern how ε grows with repeated computations:

• Sequential Composition: If mechanism M1 is ε1-DP and M2 is ε2-DP, their sequential application satisfies (ε1 + ε2)-DP. This is used to track the budget across federated learning rounds.
• Advanced Composition: Provides tighter bounds for k-fold adaptive composition, often yielding an overall ε that grows roughly with √k rather than linearly, allowing for more training rounds within a fixed total budget.
• Parallel Composition: If mechanisms are applied to disjoint subsets of data, the overall ε is the maximum of the individual εi values, not the sum. This is leveraged in federated learning's client-level DP, where each device's update consumes a portion of the total budget.

Interpreting ε values is context-dependent, but guidelines exist:

• ε ≤ 0.1: Considered a very strong privacy guarantee, often used for highly sensitive data (e.g., medical records). Noise addition is significant.
• 0.1 < ε ≤ 1: A strong guarantee suitable for many commercial applications with personal data.
• 1 < ε ≤ 10: A moderate privacy guarantee, common in research settings and some production systems where utility is a higher priority.
• ε > 10: Provides weak formal privacy, though still more private than no guarantee. Often used for non-sensitive analytics. The U.S. Census Bureau used ε ≈ 19 for the 2020 Census, while Apple uses ε values as low as 2 and 4 for features like QuickType suggestions.

Epsilon is almost always paired with delta (δ), a small probability of privacy failure. The guarantee is (ε, δ)-differential privacy. While ε bounds the expected privacy loss, δ accounts for a tiny probability that this bound is violated. For pure DP, δ = 0. In practice, δ is set to a cryptographically small value, typically significantly less than 1/n, where n is the dataset size (e.g., δ = 10^-5). A non-zero δ allows for mechanisms like the Gaussian mechanism, which often provides better utility than the Laplace mechanism for a given ε. Choosing δ requires careful consideration of the allowed failure probability.

Specific noise-adding mechanisms are calibrated to achieve a target ε:

• Laplace Mechanism: Adds noise drawn from a Laplace distribution with scale Δf/ε, where Δf is the sensitivity (maximum change in query output from a single record). Used for real-valued queries.
• Gaussian Mechanism: Adds noise from a Gaussian distribution N(0, σ²). It satisfies (ε, δ)-DP for σ ≥ Δf√(2ln(1.25/δ))/ε. Preferred in deep learning for its additive properties.
• Exponential Mechanism: Used for non-numeric queries (e.g., selecting a best outcome). It samples from a probability distribution weighted by a utility function, scaled by ε. In federated learning, these mechanisms are applied to client model updates (gradients or weights) before they are sent to the server for secure aggregation.

The utility-privacy trade-off is the fundamental inverse relationship governed by epsilon (ε). Strengthening privacy (smaller ε) by adding more noise to updates typically degrades the final model's accuracy, convergence speed, and overall utility.

• Engineering Challenge: Selecting an optimal ε value that satisfies regulatory requirements while maintaining acceptable model performance.
• Quantifying the Trade-off: Measured by the drop in global model accuracy or increase in loss for a given ε budget.

Delta (δ) is the secondary parameter in the (ε, δ)-differential privacy definition. It represents a small probability of the privacy guarantee failing (i.e., a chance of catastrophic privacy loss). While ε controls the privacy loss bound, δ accounts for a negligible failure probability.

• Interpretation: A δ of 1e-5 means a 0.001% chance the mechanism violates the ε guarantee.
• Common Practice: δ is typically set to a value significantly smaller than 1/n, where n is the dataset size.

The privacy budget is the total allowable cumulative privacy loss (ε) allocated to a sequence of queries or training rounds in a federated learning job. Epsilon is consumed with each noisy aggregation step.

• Budget Management: Techniques like the Advanced Composition Theorem track total expenditure.
• Exhaustion: Once the budget is spent, no further queries can be made on the data without violating the DP guarantee, necessitating careful allocation across communication rounds.

These are the core randomized algorithms used to achieve differential privacy by injecting calibrated noise. The choice of mechanism and its noise scale (σ) is directly determined by the target ε and δ values, as well as the sensitivity of the function (e.g., the model update).

• Laplace Mechanism: Used for pure ε-DP (δ=0). Adds noise from the Laplace distribution.
• Gaussian Mechanism: Used for (ε, δ)-DP. Adds noise from the Gaussian distribution; often preferred for federated learning due to its properties.