Differential Privacy › The Gaussian Mechanism

To make any function differentially private, you add noise proportional to how sensitive the function's output is to a single data point. The Gaussian mechanism is the standard approach for vector-valued functions such as gradients.

The $\ell_2$ sensitivity of a function $f$ measures the maximum change in its output norm when one record is added or removed:

$$\Delta_2 f = \max_{D, D': \|D - D'\|_{\text{Hamming}}=1} \| f(D) - f(D') \|_2$$

where:

• $\Delta_2 f$ is the $\ell_2$ sensitivity of function $f$, measuring the worst-case change in output when one record changes.
• $\|D - D'\|_{\text{Hamming}} = 1$ restricts the maximum to neighboring datasets that differ by exactly one record.
• $\| f(D) - f(D') \|_2$ is the Euclidean distance between the outputs on the two neighboring datasets.

The Gaussian mechanism adds isotropic Gaussian noise scaled to the sensitivity:

$$\mathcal{M}(D) = f(D) + \mathcal{N}(0, \sigma^2 \cdot \mathbf{I})$$

where:

• $\mathcal{N}(0, \sigma^2 \cdot \mathbf{I})$ is multivariate Gaussian noise with standard deviation $\sigma$ in each dimension.
• $\sigma$ controls the amount of noise added, which in turn controls the privacy-utility tradeoff.
• Larger $\sigma$ means more noise, which means stronger privacy but lower utility.

For approximate DP with parameters $(\varepsilon, \delta)$, the Gaussian mechanism satisfies DP when:

$$\sigma \geq \frac{\sqrt{2 \ln(1.25/\delta)} \cdot \Delta_2 f}{\varepsilon}$$

where:

• $\sigma$ is the noise standard deviation to be added.
• $\sqrt{2 \ln(1.25/\delta)}$ is a constant derived from the tail bounds of the Gaussian distribution, growing slowly as $\delta$ decreases.
• $\Delta_2 f$ is the $\ell_2$ sensitivity of the function being computed.
• $\varepsilon$ is the target privacy parameter; smaller $\varepsilon$ requires larger $\sigma$.

This formula captures the three-way tradeoff precisely. To achieve stronger privacy (smaller $\varepsilon$), you need more noise (larger $\sigma$). To guarantee the privacy bound holds more reliably (smaller $\delta$), you again need more noise, because the Gaussian's tail probability shrinks only logarithmically with $\sigma$. The sensitivity $\Delta_2 f$ anchors the scale of the noise to the specific function being computed: a function that barely changes when one record is removed needs very little noise to hide that change.

The Gaussian mechanism has an important property that makes it particularly well-suited to machine learning: in high dimensions, Gaussian noise distributes evenly across all directions. Adding $\sigma^2 I$ noise to a gradient vector perturbs all parameter directions equally, which tends to have a smaller effect on the overall model quality than directional noise would. This isotropy is part of why the Gaussian mechanism is preferred over alternatives for neural network training.