Gaussian Mechanism

The standard deviation (σ) of the added Gaussian noise is calibrated to the L2-sensitivity (Δ₂) of the query function. The formula is σ = Δ₂ * √(2 * ln(1.25/δ)) / ε, where (ε, δ) are the privacy parameters.

• L2-Sensitivity (Δ₂): The maximum possible change in the function's output (in Euclidean distance) when a single individual's data is added or removed from the dataset.
• Core Principle: Higher sensitivity requires more noise to 'hide' the influence of any single data point, providing the formal privacy guarantee.

The Gaussian Mechanism provides (ε, δ)-differential privacy, a relaxation of pure (ε,0)-DP.

• Epsilon (ε): The primary privacy loss parameter. A smaller ε (e.g., 0.1, 1.0) indicates a stronger privacy guarantee.
• Delta (δ): A small probability (e.g., 1e-5) that the pure ε guarantee might fail. It represents a negligible but non-zero chance of a significant privacy breach.
• Interpretation: The mechanism ensures that the probability of any output changes by at most a factor of e^ε, except with probability δ. This allows for less noise than the Laplace mechanism for real-valued vectors.

The Gaussian Mechanism's privacy loss composes analytically under repeated applications, which is critical for iterative algorithms like federated learning.

• Basic Composition: The privacy parameters (ε, δ) add up linearly across multiple mechanism calls, leading to a loose bound.
• Advanced Composition (e.g., Moments Accountant): Provides a much tighter bound on the total privacy loss (ε_total) after many iterations. For T rounds of Gaussian noise addition with parameters (ε, δ), the total ε grows roughly with √T, not linearly.
• This property enables the practical use of DP in training deep neural networks over hundreds of rounds.

Compared to the Laplace mechanism, the Gaussian mechanism offers superior utility (accuracy) when the query output is a high-dimensional real-valued vector, such as a model gradient or weight update.

• Noise Distribution: Gaussian noise is spherically symmetric, adding independent noise to each dimension. The L2 norm of the noise grows as O(√d), where d is dimensionality.
• Laplace Comparison: The Laplace mechanism adds noise proportional to L1-sensitivity, where the noise magnitude grows linearly with d (O(d)).
• Result: For common machine learning parameters where d is large (thousands to millions), the Gaussian mechanism introduces less distortion per coordinate for the same (ε, δ) guarantee, preserving more signal in the aggregated update.

The Gaussian Mechanism is primarily deployed in the central model of differential privacy, which assumes a trusted aggregator (server).

• Central Model: Raw data or updates are sent to a trusted server, which applies the Gaussian noise before releasing the aggregated result. This provides a better accuracy-privacy trade-off.
• Local Model (LDP) Contrast: In Local Differential Privacy, each client adds noise to their data before sending it to an untrusted server. Achieving the same (ε, δ) guarantee in the local model requires significantly more noise, drastically reducing utility.
• Federated Learning Context: Secure Aggregation protocols often simulate a trusted server via cryptography, allowing the application of the central-model Gaussian mechanism to the sum of client updates.

In machine learning applications, the Gaussian Mechanism is almost always preceded by gradient clipping, which bounds the L2-sensitivity.

• Process Flow: 1) Compute per-client gradient. 2) Clip its L2 norm to a threshold C. 3) Add Gaussian noise scaled by C.
• Purpose: Clipping ensures the sensitivity Δ₂ is finite and known (Δ₂ = 2C), as raw gradients can have unbounded norm. It also limits the influence of any single client's data.
• Trade-off: The clipping threshold C is a hyperparameter. Too small a C loses signal; too large a C requires excessive noise for privacy. Adaptive clipping strategies are often used to optimize this balance.

The Gaussian Mechanism is particularly well-suited for functions with outputs in ℝ^d (multi-dimensional real space), such as:

• Gradients in machine learning, which are high-dimensional vectors.
• Embeddings or feature vectors.
• Sets of multiple statistics released simultaneously. Its noise scales with the Euclidean norm (L2 norm) of the function's sensitivity, which is often more natural and adds less distortion per dimension compared to the Laplace Mechanism when d is large. This makes it the mechanism of choice for privatizing complex, vector-valued computations.

For algorithms that require multiple, adaptive queries to private data (e.g., iterative optimization, hyperparameter tuning), the Gaussian Mechanism is used with advanced composition theorems. These theorems allow for a careful tracking of the cumulative privacy budget (ε, δ) across many steps. The Gaussian noise's distribution is stable under composition, meaning the total privacy cost can be calculated and controlled more tightly than with some other mechanisms, enabling complex, multi-step private analyses.

The cryptographic protocol that enables the practical use of the Gaussian Mechanism in federated learning by hiding individual updates before summation.

• Primary Function: Allows a central server to compute the sum of client model updates (e.g., gradients) without learning any individual client's contribution.
• Synergy with Gaussian Mechanism: Secure Aggregation computes the exact sum of updates privately; the Gaussian Mechanism can then be applied to this aggregated sum to provide a differential privacy guarantee for the final model.
• Key Technique: Often employs pairwise masking and cryptographic primitives so that masks cancel out when all client contributions are summed.

A stronger, trust-minimized privacy model where each client perturbs their data locally before sending it to an aggregator.

• Contrast with Central Model: In the central model (used with Gaussian Mechanism in federated learning), a trusted curator adds noise to the aggregated result. In LDP, no trusted curator is needed; privacy is enforced at the source.
• Application Context: LDP is used when the server cannot be trusted, such as in crowdsourced data collection. The Gaussian Mechanism can be adapted for the local model, though it typically requires significantly more noise.
• Common Mechanisms: The Randomized Response technique is a classic example of LDP for categorical data.

A necessary pre-processing step before applying the Gaussian Mechanism to training updates, as it bounds the sensitivity of the function.

• Purpose: To enforce a maximum norm (e.g., L2 norm) on individual client gradients or model updates. This bound, denoted as sensitivity S, is a critical parameter for calibrating the Gaussian noise.
• Process: Each client's update vector is scaled down if its norm exceeds the clipping threshold C. This ensures that a single client's data has a bounded influence on the aggregate.
• Impact on Noise: The standard deviation σ of the Gaussian noise is proportional to S (the clipping threshold) and inversely proportional to the privacy parameters (ε, δ).

The canonical alternative to the Gaussian Mechanism for achieving pure differential privacy (δ=0).

• Core Difference: Adds noise drawn from a Laplace distribution calibrated to the function's L1 sensitivity. It provides (ε, 0)-differential privacy.
• When to Use: Preferred when a pure ε-DP guarantee (δ=0) is required, often for scalar-valued or low-dimensional outputs. The Gaussian Mechanism, which requires a small δ > 0, is generally preferred for high-dimensional vectors (like model updates) because it adds noise with better statistical properties (lower L2 error) for the same privacy cost.
• Noise Scale: For a function with L1 sensitivity Δ, noise is drawn from Laplace(Δ/ε).

A powerful technique that improves the privacy guarantee of a mechanism when it is applied to a random subset of the data.

• Principle: If a mechanism is applied to a randomly sampled portion of a dataset (e.g., a random cohort of clients in a federated learning round), the effective privacy parameters (ε, δ) can be tightened compared to applying it to the full dataset.
• Application in Federated Learning: This is a key reason why federated averaging with client sampling can achieve strong privacy. The Gaussian Mechanism's noise can be reduced for a target privacy level because the act of random client participation itself provides a privacy boost.
• Formal Result: Governed by theorems like the Amplification by Subsampling lemma, which quantifies the improved (ε', δ') guarantee.