(ε, δ)-Differential Privacy

Epsilon (ε) is the primary privacy loss parameter. It quantifies the maximum allowable multiplicative difference in the probability of any output, with or without any single individual's data. A smaller ε indicates a stronger privacy guarantee.

• Interpretation: For ε=1, the likelihood of any output can change by a factor of ~2.718 (e^1). For ε=0.1, the factor is ~1.105.
• Practical Range: Values like 0.1, 1, or 8 are common, where ε < 1 is considered strong privacy and ε > 10 offers weaker protection.
• Role in (ε, δ)-DP: It defines the core, high-probability privacy bound.

Delta (δ) is the secondary parameter representing a small probability that the strict ε guarantee fails. It accounts for a negligible chance of a catastrophic privacy breach.

• Typical Setting: δ is set to a cryptographically small value, significantly less than the inverse of the dataset size (e.g., δ < 10^-5). This makes a meaningful privacy violation extremely unlikely.
• Purpose: Introducing δ > 0 enables the use of the Gaussian mechanism, which adds noise from a normal distribution. This is often more analytically and practically favorable than the Laplace mechanism required for pure ε-DP.
• Risk Interpretation: A δ of 10^-5 means there is a 1 in 100,000 probability the privacy loss exceeds ε.

The Gaussian mechanism is the canonical algorithm for achieving (ε, δ)-differential privacy. It adds noise drawn from a normal distribution to the true output of a function.

• Noise Scale: The standard deviation σ of the Gaussian noise is scaled by the function's L2 sensitivity (Δ₂) and the desired (ε, δ) parameters: σ = (Δ₂ * √(2 log(1.25/δ))) / ε.
• Key Advantage: Gaussian noise is often preferable in machine learning (e.g., for gradients) as it is unbounded and symmetric, and it composes more tightly under advanced accounting methods like Rényi DP.
• Contrast with Laplace: The Laplace mechanism, used for pure ε-DP, adds noise from a Laplace distribution scaled by L1 sensitivity.

Sensitivity is the maximum possible change in a function's output when a single data point is added or removed. It determines how much noise must be added.

• L1 Sensitivity (Δ₁): The maximum absolute change, measured by the L1 norm. It directly scales the noise for the Laplace mechanism.
• L2 Sensitivity (Δ₂): The maximum Euclidean distance change, measured by the L2 norm. It directly scales the noise for the Gaussian mechanism.
• Example: For a counting query ("how many records satisfy property P?"), both L1 and L2 sensitivity are 1. For a gradient vector, the L2 sensitivity is controlled via gradient clipping to a threshold C.

When a dataset is analyzed multiple times, privacy loss accumulates. Composition theorems and privacy accounting track the total (ε, δ) across all operations.

• Basic Composition: The ε parameters sum linearly, and δ parameters sum linearly. This is simple but pessimistic.
• Advanced Composition: Provides tighter bounds, especially for many iterations. Methods like the Moment Accountant, Rényi DP (RDP), and Zero-Concentrated DP (zCDP) give far more favorable ε for the same δ after many queries.
• Privacy Budget: A total allowable (ε_total, δ_total) is set. Each analysis consumes part of this budget; accounting ensures it is not exceeded.

In Federated Learning, (ε, δ)-DP is applied at the client level to protect a user's entire local dataset. The standard algorithm is Differentially Private Federated Averaging (DP-FedAvg).

• Process: Each client clips their local model update (gradients or weight delta) to a maximum L2 norm C (controlling sensitivity). They then add Gaussian noise scaled to (ε, δ) and send the noised update to the server.
• Server-Side Aggregation: The server averages the noised client updates. Due to post-processing immunity, the final global model inherits the (ε, δ) guarantee.
• Key Trade-off: Higher noise (lower ε) increases privacy but reduces model accuracy and slows convergence. The clip threshold C and noise multiplier are critical hyperparameters.

National statistical agencies (e.g., U.S. Census Bureau) use (ε, δ)-DP to release aggregate demographic statistics while preventing reconstruction of individual records. Queries on the dataset (counts, averages, histograms) have noise added via the Gaussian mechanism. The δ parameter allows for the use of Gaussian noise, which has lighter tails than the Laplace noise required for pure ε-DP, often leading to better utility for the same privacy cost. This application relies heavily on privacy accounting across thousands of queries.

Companies like Google and Apple apply (ε, δ)-DP to collect aggregate usage statistics for model improvement without learning about any specific user. For example, learning popular emojis or detecting trending websites. The δ value is set extremely low (e.g., 10^-10) to make the probability of a privacy failure negligible. Techniques like the sparse vector technique and report noisy max (built on the exponential mechanism) are used to identify top items privately. Local DP is often used at the device level, with further (ε, δ)-DP guarantees applied during central aggregation.

In vertical federated learning or multi-institutional studies, (ε, δ)-DP enables the release of summary statistics—like allele frequencies, disease association metrics, or aggregated model updates—from sensitive genomic or patient health datasets. Researchers can perform genome-wide association studies (GWAS) with formal privacy guarantees. The δ parameter is crucial here, as the Gaussian mechanism's analytical tractability allows for precise control over the trade-off between data utility for medical discovery and the very low probability of privacy violation.

Banks and financial institutions can collaboratively train fraud detection models on transaction data from multiple sources using (ε, δ)-DP in a federated setting. The δ allowance permits the use of more efficient mechanisms, making it feasible to train complex models like gradient-boosted trees or neural networks with formal guarantees. This ensures that patterns indicative of fraud are learned without leaking information about any individual customer's specific transactions. Client-level DP protects the entire data contribution of a single bank or user.

Pure differential privacy is the strict, original definition of the framework, providing an absolute guarantee without failure probability. It requires that for any two adjacent datasets (differing by one record), the probability of any output from a mechanism is within a multiplicative factor of e^ε. The Laplace Mechanism is the canonical algorithm for achieving ε-DP. Unlike (ε, δ)-DP, it does not allow a δ probability of the guarantee failing, making it more rigid for complex, iterative algorithms like DP-SGD.

Rényi differential privacy is a relaxation defined using Rényi divergence, providing a different lens for privacy loss accounting. It is characterized by parameters (α, ε), where α is a moment order. RDP often enables tighter composition bounds for iterative algorithms compared to basic (ε, δ) composition theorems. A key advantage is that RDP guarantees can be converted to (ε, δ)-DP guarantees, and this conversion is frequently used by privacy accountants like the Moment Accountant in DP-SGD to track cumulative loss more precisely.

Zero-concentrated differential privacy is a variant that sits between pure DP and (ε, δ)-DP, designed to simplify the analysis of mechanisms based on Gaussian noise. It is defined by a single parameter ρ (rho) that bounds the Rényi divergence of all orders. zCDP provides clean and nearly tight composition for Gaussian mechanisms and subsampling. Like RDP, zCDP guarantees can be losslessly converted to (ε, δ)-DP statements, making it a powerful intermediate tool for proving privacy for complex, multi-step training processes.

Privacy amplification by subsampling is a crucial technique where applying a DP mechanism to a random subset of the data (e.g., a mini-batch) results in a stronger effective privacy guarantee than if applied to the full dataset. In federated learning and DP-SGD, this means the per-round privacy cost (ε, δ) is reduced because each client's data or each training example is only included in a randomly selected batch with probability equal to the sampling rate. This allows for achieving a desired final privacy bound with less noise per step.

Client-level differential privacy defines the granularity of protection in federated learning, where an adjacent dataset is defined as two sets of participating clients that differ by one entire client. The privacy guarantee ensures that the aggregated model update or final model does not reveal whether any single client's dataset was included in the training round. This is the standard privacy notion for DP-FedAvg, where noise is added to the aggregate of client updates. It protects all records belonging to a user or device, aligning with the federated learning paradigm.

The privacy loss random variable is a foundational concept for understanding (ε, δ)-DP. For a fixed pair of adjacent datasets and a specific output, it quantifies the logarithm of the ratio of the probability densities under the two datasets. (ε, δ)-differential privacy requires that the probability this random variable exceeds ε is bounded by δ. Advanced accounting methods like the Moment Accountant and analyses for RDP/zCDP work by bounding the moments or tail behavior of this random variable across all possible outputs and dataset pairs.