Gaussian Mechanism

The standard deviation (σ) of the Gaussian noise is calibrated to the L2 sensitivity (Δ₂f) of the function f. The noise scale is σ = Δ₂f * √(2 * ln(1.25/δ)) / ε. This ensures that the probability distribution of outputs is indistinguishable between neighboring datasets. The L2 sensitivity is the maximum Euclidean norm change in f's output when a single data point is altered.

The Gaussian mechanism provides (ε, δ)-differential privacy, a relaxation of pure ε-DP. The parameter δ represents a small probability that the strict ε privacy bound is violated. This relaxation is necessary because Gaussian noise has unbounded support, meaning there is always a non-zero probability of a negligibly small noise draw. In practice, δ is set to a cryptographically small value (e.g., 1e-5), much less than the inverse of the dataset size.

The mechanism operates by simple addition: it releases f(D) + N(0, σ²I), where N(0, σ²I) is multivariate Gaussian noise with mean zero and covariance σ²I. The noise is isotropic, meaning it is added independently and identically to each dimension of the function's output. This additive structure is computationally efficient and preserves the output type (e.g., a vector of gradients or model weights).

A key advantage is its clean behavior under composition. When multiple Gaussian mechanisms are applied, the total privacy cost can be precisely tracked using advanced composition theorems, Rényi Differential Privacy (RDP), or Zero-Concentrated DP (zCDP). These frameworks provide tighter bounds on the cumulative (ε, δ) than basic composition, making the Gaussian mechanism highly suitable for iterative algorithms like DP-SGD and DP-FedAvg.

The mechanism introduces a fundamental trade-off between privacy (ε, δ) and utility (accuracy). Stronger privacy (smaller ε) requires larger noise (σ), increasing the variance of the released statistic and degrading utility. The clip threshold (C) used to bound sensitivity also introduces bias. Tuning (ε, δ, C) is therefore critical to balance privacy protection with model performance in production systems.

Like all differentially private mechanisms, the Gaussian mechanism enjoys post-processing immunity. Any deterministic or randomized function applied to its noisy output cannot weaken the (ε, δ) privacy guarantee. This allows downstream processing—such as applying a model update, performing additional aggregation, or releasing derived statistics—without requiring a fresh privacy budget, a cornerstone of safe data analysis pipelines.

The canonical use case. In Differentially Private Stochastic Gradient Descent (DP-SGD), the Gaussian mechanism adds noise to the averaged gradient of a mini-batch.

• Process: Per-example gradients are first clipped to a maximum L2 norm (the sensitivity bound). The average of these clipped gradients is then perturbed with Gaussian noise scaled to this sensitivity and the desired (ε, δ).
• Why Gaussian? Training involves thousands of iterative queries. The Gaussian mechanism's cleaner composition under Rényi DP (RDP) or zCDP allows for much tighter privacy accounting than the Laplace mechanism, making private training feasible.

Extends privacy to the federated learning setting. Clients add Gaussian noise to their local model updates before sending them to the server for aggregation.

• Client-Level Privacy: Protects the participation and data of any single device/user (client).
• Workflow: Each client computes a model update (e.g., gradient), clips it to bound sensitivity, adds calibrated Gaussian noise, and transmits the noised update. The server then performs a secure aggregation of these private updates.
• Key Benefit: Provides a formal, mathematical guarantee against reconstruction or membership inference attacks on client data from the aggregated global model.

Ideal for privatizing queries where the output is a real-valued vector, and the L2 norm is the appropriate distance metric.

• Examples: Releasing a histogram of user demographics, a set of aggregate KPIs (Key Performance Indicators), or the weights of a trained model.
• Sensitivity Calculation: The L2 sensitivity (Δ₂) is the maximum Euclidean distance between the query's output on any two neighboring datasets. Noise scaled to σ = Δ₂ * √(2log(1.25/δ)) / ε is added to each coordinate of the vector.
• Advantage over Laplace: For high-dimensional vectors, adding independent Gaussian noise to each coordinate often provides better utility than Laplace noise for the same privacy budget when δ > 0 is permissible.

A powerful technique where applying the Gaussian mechanism to a random subset of data provides a stronger effective privacy guarantee.

• Common in DP-SGD: Each training step uses a randomly sampled mini-batch of data points. The privacy cost of the noised gradient update is amplified because the mechanism only "sees" a fraction of the dataset.
• Quantitative Gain: The effective privacy parameters (ε_amp, δ_amp) are smaller than the base parameters (ε, δ) applied to the subsampled batch. This allows for more training steps (higher utility) within a fixed total privacy budget.
• Critical Interaction: The analysis of this amplification is most tractable under the Gaussian mechanism's framework via RDP or zCDP.

The Gaussian mechanism is chosen over the Laplace mechanism in specific scenarios based on the privacy definition and output structure.

• Rule of Thumb: Use Laplace for a one-time, low-dimensional count query with a strict δ=0 requirement. Use Gaussian for iterative training or high-dimensional releases where a tiny, negligible δ (e.g., 1e-5) is acceptable for vastly improved utility.

Deploying the Gaussian mechanism requires careful calibration of its parameters, which form a utility-privacy trade-off.

• Epsilon (ε): The primary privacy loss bound. Lower ε = stronger privacy, more noise, worse model accuracy/statistical utility. Typical values in literature range from 0.1 (very strong) to 8.0 (weaker).
• Delta (δ): The probability of privacy failure. Must be set to a cryptographically small value, typically much less than 1/(dataset size). Common setting: δ = 1e-5 or 1e-6. It is not a "relaxation" to be tuned for utility.
• Noise Scale (σ): Directly calculated from ε, δ, and sensitivity (Δ₂): σ = Δ₂ * √(2log(1.25/δ)) / ε. Tuning the clip threshold (C) that defines Δ₂ is the primary practical knob for balancing bias (from clipping) and variance (from noise).

The overarching mathematical framework that defines privacy guarantees. It ensures that the inclusion or exclusion of any single individual's data from a dataset has a negligible effect on the output of an analysis. The Gaussian mechanism is one algorithm designed to satisfy this definition.

• Formal Guarantee: Provides a quantifiable, worst-case bound on privacy loss.
• Post-Processing Immunity: Any computation on a DP output remains DP.
• Composition: Privacy loss accumulates predictably across multiple queries.

The maximum possible change in the output of a function (e.g., a query or a model update) when a single data point is added or removed. For the Gaussian mechanism, the L2 sensitivity (the maximum change in the Euclidean norm) directly determines the scale of the noise that must be added.

• Definition: Δ₂f = max_{D, D′} ||f(D) - f(D′)||₂, where D and D′ are neighboring datasets.
• Critical Parameter: The noise standard σ is set proportional to Δ₂f / ε (scaled by δ).
• In Practice: In federated learning, this often means bounding the norm of a client's model update via gradient clipping.

The canonical mechanism for achieving pure (ε, 0)-differential privacy. It adds noise drawn from a Laplace distribution, where the scale parameter is set by the function's L1 sensitivity (Δ₁f) divided by ε.

• Contrast with Gaussian: Provides a stronger pure-DP guarantee but often requires more noise for high-dimensional vectors.
• Use Case: Ideal for scalar queries or low-dimensional outputs where L1 sensitivity is easily bounded.
• Noise Distribution: Heavier tails than Gaussian, which can impact utility differently.

The relaxed privacy definition satisfied by the Gaussian mechanism. It allows a small probability δ (e.g., 10⁻⁵) that the pure ε guarantee is violated. This relaxation enables the use of Gaussian noise, which is more amenable to analysis in high-dimensional settings like machine learning.

• Interpretation: The guarantee holds with probability at least (1 - δ).
• Practical Necessity: Essential for iterative algorithms like DP-SGD, where pure DP would require excessive noise.
• Parameter Setting: δ should be cryptographically small, typically less than 1/(dataset size).

The standard algorithm for training deep learning models with differential privacy. It is the primary use case for the Gaussian mechanism in ML. In each training step:

1. Per-example Gradient Clipping: Bounds the L2 norm of each gradient (controls sensitivity).
2. Noisy Averaging: Adds Gaussian noise to the sum of the clipped gradients (applies the Gaussian mechanism).
3. Privacy Accounting: Uses composition theorems (like RDP or the moment accountant) to track the total (ε, δ) spent over all training steps.

The direct application of differential privacy within the federated averaging algorithm. It provides client-level DP, protecting the fact of a client's participation. The core steps are:

• Local Clipping: Each client bounds their model update (e.g., weight delta) using an L2 norm clip threshold C.
• Local Noising: Clients add calibrated Gaussian noise to their clipped update.
• Secure Aggregation: The server aggregates the noised updates from many clients, which further amplifies privacy. This protocol ensures the aggregated model update released by the server satisfies (ε, δ)-DP.