Gaussian Mechanism

Background

Let $(\mathcal{X}, d)$ be a metric space, and $f$ be a function $\mathcal{X} \rightarrow \mathbb{R}^n$. A Gaussian mechanism adds Gaussian noise to the output of $f$, such that for all neighboring pairs $x, y \in \mathcal{X}$ with $d(x, y) = 1$, it is hard to distinguish the outputs, i.e., their outputs distributions are similar.

Definition. The sensitivity $\Delta$ of $f$ is defined as

$$\Delta = \max_{x, y \in \mathcal{X}, d(x, y) = 1 } \Vert f(x) - f(y) \Vert_2,$$

where $\Vert \cdot \Vert_2$ is the $\ell_2$-norm of a vector in $\mathbb{R}^n$.

Definition. Given $f$ and a variance parameter $\sigma^2$, the output of the Gaussian mechanism is a random variable defines as

$$g(x) = f(x) + X,$$

where $X = (X_1, X_2, ..., X_n) \sim N(0, \sigma^2 I)$.

Privacy Guarantee

Theorem. For $\delta, \epsilon \in (0, 1)$, if $\sigma^2 = \frac{ \Delta^2 }{ \epsilon^2 } \Big( 2 \ln \frac{1}{\delta} + \epsilon \Big)$, then $\forall x, y \in \mathcal{X}$, s.t., $d(x, y) = 1$, and for all measurable subset $S \subset \mathbb{R}^n$, it holds

$$\Pr[ g(x) \in S] \le e^\epsilon \cdot \Pr[ g(y) \in S] + \delta$$

It is obvious that if we set $\sigma \rightarrow \infty$, then the Gaussian distribution converge to a uniform one and it holds that $\Pr[ g(x) \in S] = \Pr[ g(y) \in S]$. Therefore, we are interested in how small $\sigma$ can be.

We claim that $\sigma = O(\frac{\Delta}{\epsilon } )$ suffices. This is based on three observations:

1. Most of the probability mass of a Gaussian distribution concentrates on a ball centered at its mean with radius $O(\sigma)$.
2. The density ratio of any two points within the ball is bounded by a constant.
3. The distance between the distribution center of $g(x)$ and $g(y)$ is bounded by $\Delta$.

Proof. To ease the notations, we write $g(y) = f(y) + Y$ to distinguish it from $g(x)$. By definition,

Let $p_x$ and $p_y$ the density functions of $g(x)$ and $g(y)$ respectively. The sketch of the proof is as follows: we partition $\mathbb{R}^n$ into two parts:

If $\Pr[ g(x) \in \mathcal{Y}_2 ] \le \delta$ $\big($ here we measure the size of $\mathcal{Y}_2$ by the probability measure induced by $g(x)$ $\big)$, then

As $p_y(t) > 0$ for all $t \in \mathbb{R}^n$, we can rewrite

In literature, the ratio $\ln \frac{p_x(t) }{ p_y(t) }$ is know as privacy loss. Substituting $p_x(t)$ and $p_y(t)$ with their definitions, and letting $t' = t - f(x)$ and $v = f(x) - f(y)$, we get

If $t \sim N( f(x), \sigma^2 I)$, it holds that $t' \sim N( 0, \sigma^2 I)$.

Then $v^T t' \sim N(0, \Vert v \Vert ^2 \sigma^2)$. Let $Z \sim N(0, 1)$, then $\ln \frac{ p_x( t) }{ p_y(t)}$ has the same distribution as

Now,

As $Z \sim N(0, 1)$, $\forall z \in \mathbb{R}_{\ge 0}$,

Assuming that $\sigma^2 \ge \frac{\Vert v \Vert^2}{ 2 \epsilon }$. Then $\frac{ \sigma }{ \Vert v\Vert } \epsilon - \frac{ \Vert v\Vert }{ 2 \sigma } \ge 0$. Replacing $z$ with $\frac{ \sigma }{ \Vert v\Vert } \epsilon - \frac{ \Vert v\Vert }{ 2 \sigma }$,

We would like to bound this probability by some $\delta \in (0, 1)$, then

Finally, we get

By concavity of the square root function, it suffices to take

i.e.,

$\blacksquare$

Reference

[1] G. Kamath, “Lecture 5 — Approximate Differential Privacy”, CS 860 - Algorithms for Private Data Analy sis.