Gaussian Mechanism

Unlike the Laplace Mechanism which provides pure ε-differential privacy, the Gaussian Mechanism satisfies approximate (ε, δ)-differential privacy. The δ parameter represents a small probability (often cryptographically small, e.g., 10⁻⁵) that the privacy guarantee may be violated by a factor of ε. This relaxation allows for tighter noise scaling in high-dimensional queries, making it the standard for deep learning applications like Differentially Private Stochastic Gradient Descent (DP-SGD).

The noise is calibrated to the L2-sensitivity (ℓ₂-sensitivity) of the query function, not the L1-sensitivity. The L2-sensitivity measures the maximum Euclidean distance between query outputs on neighboring datasets. For a query f, the mechanism adds noise from N(0, σ²) where σ = (Δ₂f * √(2*ln(1.25/δ))) / ε. This makes it particularly suited for vector-valued queries where the L2 norm is a natural measure of magnitude.

The Gaussian Mechanism interacts gracefully under sequential composition. When multiple queries are performed, the total privacy cost accumulates. Advanced composition theorems provide a tighter bound on the total ε and δ after k applications:

• Basic Composition: ε_total = kε, δ_total = kδ
• Advanced Composition: For ε < 1, the total privacy loss scales proportionally to √(k) rather than k, enabling more queries under a fixed privacy budget. This is critical for iterative algorithms like DP-SGD.

A powerful property exploited in deep learning is that applying the Gaussian Mechanism to a random subsample of the data amplifies privacy. If a batch is sampled with probability q, the privacy parameters (ε, δ) are effectively reduced. This is the foundational principle behind DP-SGD, where gradients are clipped and noised on randomly sampled mini-batches, achieving a much stronger overall privacy guarantee than applying the mechanism to the full dataset.

Tracking the precise privacy loss over many iterations requires a moments accountant. Instead of using loose composition theorems, the moments accountant computes the exact Renyi Differential Privacy (RDP) of the Gaussian Mechanism under subsampling. This provides a provably tighter bound on the final (ε, δ) values, reducing the required noise multiplier for a target privacy budget and directly improving model utility.

For a query with L2-sensitivity Δ₂f, the Gaussian Mechanism introduces mean squared error E[||noise||²] = dσ², where d is the output dimensionality. The expected L2 error is therefore d * (Δ₂f)² * 2*ln(1.25/δ) / ε². This reveals the fundamental trade-off: error scales quadratically with sensitivity, linearly with dimensionality, and inversely with ε². Reducing dimensionality via projection or PCA before noising is a common optimization.

The parameter ε (epsilon) quantifies the privacy loss permitted by a mechanism. A smaller epsilon (e.g., 0.1) provides stronger privacy but requires more noise, degrading accuracy. The Gaussian Mechanism consumes a portion of this budget with each query. Key concepts:

• Privacy budget: The total ε allocated to all queries on a dataset
• Composition: Multiple queries sum their privacy loss (basic composition) or degrade by √k (advanced composition)
• Privacy-utility trade-off: ε directly controls the variance of Gaussian noise added

The sensitivity of a query determines the scale of Gaussian noise required. Two variants are critical:

• L2 Sensitivity (Δ₂): The maximum Euclidean distance between query outputs on datasets differing by one record. Used directly by the Gaussian Mechanism
• L1 Sensitivity (Δ₁): The maximum L1 distance, used by the Laplace Mechanism For a sum query bounded to [0,1], Δ₂ = 1. For a mean query over n records, Δ₂ = 1/n. Accurate sensitivity calibration is essential—overestimation adds unnecessary noise, while underestimation breaks the privacy guarantee.