Epsilon (ε)

Formally, a randomized mechanism M satisfies ε-differential privacy if for all datasets D and D' differing on at most one individual (neighbors), and for all subsets S of possible outputs: Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S]. This multiplicative bound ensures the output distributions are statistically indistinguishable, limiting an adversary's ability to infer an individual's participation. A smaller ε enforces tighter indistinguishability, providing a stronger guarantee.

Epsilon functions as a finite, consumable privacy budget. Each query or training step (e.g., a gradient update in DP-SGD) consumes a portion of ε. The total ε across all operations is the cumulative privacy loss. This enforces a hard limit on how many questions can be asked of a sensitive dataset before the privacy guarantee is exhausted. In federated learning, this budget is typically applied at the client level, protecting the participation of an entire device or user.

Epsilon sits at the center of the fundamental privacy-utility trade-off. A smaller ε (stronger privacy) requires adding more noise, which degrades model accuracy or query utility. A larger ε (weaker privacy) permits less noise and higher utility. Selecting ε is a policy and business decision:

• ε < 1: Very strong privacy, significant utility loss.
• ε between 1 and 10: Common practical range for machine learning, balancing meaningful privacy with acceptable accuracy.
• ε > 10: Weak privacy, approaching non-private utility. There is no universally 'correct' ε; it is chosen based on the sensitivity of the data and the required output quality.

Epsilon defines pure differential privacy (ε-DP), which offers a strict, absolute guarantee. The Laplace Mechanism achieves pure DP. In practice, approximate differential privacy ((ε, δ)-DP) is often used, where δ is a small probability the guarantee fails (e.g., δ = 10^-5). The Gaussian Mechanism achieves (ε, δ)-DP. This relaxation allows for adding less noise (better utility) for the same ε, or achieving a smaller effective ε for the same noise level, making it essential for iterative algorithms like DP-SGD.

Epsilon composes under sequential analysis:

• Basic Composition: The ε's of k mechanisms simply add (k * ε). This is simple but pessimistic.
• Advanced Composition (e.g., for (ε, δ)-DP): Provides a √k dependence, allowing for more queries.
• Tighter Accounting (RDP/zCDP): Methods like Rényi DP or Zero-Concentrated DP provide much tighter bounds on the ε of composed Gaussian mechanisms, which is critical for training deep networks with DP-SGD. Privacy can also be amplified. Applying a mechanism to a random subsample (e.g., a mini-batch) results in an effective ε smaller than the one applied to the batch, a principle called amplification by sampling.

Choosing ε requires context. For highly sensitive data (e.g., medical records), ε is often set below 1. For less sensitive applications or large, diverse datasets, values up to 10 may be acceptable. Example deployments:

• Apple's iOS: Uses local differential privacy with ε values like 4 or 8 for usage telemetry collection.
• US Census 2020: Used differential privacy with a total ε of 19.61 for the redistricting data, allocated across thousands of queries.
• DP-SGD for CIFAR-10: Achieving ~70% accuracy might require ε between 2 and 8, depending on the model and δ setting. These are not recommendations but illustrate real-world trade-offs. The setting must be justified by a threat model and risk assessment.

Delta (δ) is the secondary parameter in (ε, δ)-differential privacy, representing a small probability of the pure ε privacy guarantee failing. It is interpreted as the probability of a catastrophic privacy failure where the privacy loss exceeds ε.

• Typical Setting: δ is set to a value significantly smaller than the inverse of the dataset size (e.g., δ < 1/n). For a dataset of 1 million users, δ might be set to 10⁻⁵ or 10⁻⁶.
• Role in Mechanisms: Allows the use of the Gaussian mechanism, which adds noise proportional to the L2 sensitivity, often providing better utility than the Laplace mechanism for high-dimensional vectors like gradients.
• Risk Interpretation: A δ of 10⁻⁵ means there is a 1 in 100,000 chance of a privacy breach worse than ε. In federated learning, this is applied at the client level.

Sensitivity is the maximum possible change in the output of a function when a single individual's data is added or removed. It is the fundamental determinant of noise scale in differential privacy.

• L1 Sensitivity (Δ₁): Used for the Laplace Mechanism. Defined as the maximum absolute change in the function's output: Δ₁f = max ||f(D) - f(D')||₁.
• L2 Sensitivity (Δ₂): Used for the Gaussian Mechanism. Defined as the maximum Euclidean norm change: Δ₂f = max ||f(D) - f(D')||₂.
• In Federated Learning: The function is often the aggregate of client model updates. Gradient clipping is used to artificially bound the L2 sensitivity of each client's update to a predefined clip threshold (C), enabling the controlled addition of Gaussian noise.

A privacy budget is a finite allocation of ε (and δ) consumed over multiple queries or training steps. Privacy accounting is the process of tracking this cumulative consumption.

• Budget Allocation: In iterative training like DP-FedAvg, each communication round consumes a portion of the total budget. The budget defines the ultimate privacy-utility trade-off.
• Composition Theorems: Basic (sequential) composition states that applying k mechanisms with guarantees (εᵢ, δᵢ) yields a total guarantee of (Σεᵢ, Σδᵢ). Advanced composition allows for tighter bounds.
• Advanced Accountants: The Moment Accountant (used in DP-SGD) and analyses based on Rényi Differential Privacy (RDP) provide much tighter tracking of privacy loss under composition than naive theorems, enabling more training rounds for the same final ε.

These are the two primary noise-adding mechanisms for achieving differential privacy, chosen based on the desired guarantee and sensitivity type.

• Laplace Mechanism: Achieves pure ε-DP. For a function f with L1 sensitivity Δ₁f, it outputs f(D) + Lap(Δ₁f/ε). The noise is drawn from a Laplace distribution.
• Gaussian Mechanism: Achieves (ε, δ)-DP. For a function f with L2 sensitivity Δ₂f, it outputs f(D) + N(0, σ²). The noise scale σ is proportional to Δ₂f and depends on ε and δ (σ = Δ₂f * √(2log(1.25/δ)) / ε).
• Application: In federated learning with DP-FedAvg, the Gaussian mechanism is typically applied to the sum of clipped client updates because it adds less noise per coordinate for high-dimensional vectors, preserving more model utility.

These are the two primary models defining where the privacy-preserving noise is applied in the data pipeline.

• Local Differential Privacy (LDP): Each client perturbs their own data locally before sending it to an untrusted server. Provides a stronger, client-side guarantee but typically requires more noise per client, harming utility. Example: Randomized Response.
• Central Differential Privacy: A trusted curator (the server) holds the raw data and applies a DP mechanism before releasing any output. Allows for less noise overall (better utility) but requires trust in the curator.
• Federated Learning Context: Standard DP-FedAvg implements a hybrid: clients perform clipping and noising locally, but the formal guarantee is often analyzed as central DP at the client level, assuming a trusted server for secure aggregation.

These are the canonical algorithms for applying differential privacy to model training in centralized and federated settings, respectively.

• DP-SGD (Differentially Private Stochastic Gradient Descent): The foundational algorithm for centralized DP training. For each batch:
  1. Compute per-example gradients.
  2. Clip each gradient's L2 norm to a threshold C.
  3. Average the clipped gradients.
  4. Add Gaussian noise scaled to C and the target (ε, δ).
  5. Take a descent step.
• DP-FedAvg (Differentially Private Federated Averaging): The federated adaptation. In each round:
  1. Selected clients clip their local model update (e.g., gradient or weight delta) to bound sensitivity.
  2. Clients add Gaussian noise to their clipped update.
  3. Server aggregates noised updates via Secure Aggregation (to hide individual noise).
  4. Server applies the aggregated, private update to the global model.