Releasing Histogram Privately

Given a set of $n$ elements $S$ that belongs to some finite domain $\mathcal{X}= \{ x_1, x_2, ..., x_m \}$ , we want to release the (normalized) histogram in a differentially private manner. Define $\forall x_i \in \mathcal{X}$ :

$F_S(x_i) \doteq$ the number of times $x_i$ appears in $S$ ;
$f_S(x_i) \doteq \frac{F_S(x_i) }{ |S| } = \frac{F_S(x_i) }{ n }$ , the frequency of $x_i$ in $S$ .

The (normalized) histogram of $h_S$ is a frequency vector:

h_S \doteq \left< f_S(x_1), f_S(x_2), ..., f_S(x_m) \right> \in \mathbb{R}^m

Consider another set $S'$ obtained by replacing an element $x_k$ in $S$ to another element $x_l$ , such that

$F_{S'} (x_k) = F_{S} (x_k) - 1$ ;
$F_{S'} (x_l) = F_{S} (x_l) + 1$ ;
$F_{S'} (x_i) = F_{S} (x_i), \forall i \notin \{k, l\}$ .

Let $h_{S'}$ be the histogram of $S'$ . Our goal is to design some mechanism $M$ that adds noise to the normalized so that the output distribution of $M(h_S)$ and $M(h_{S'})$ are indistinguishable.

Naive Laplacian

One way is to add Laplacian noise directly to each dimension of the histogram. For any vector $v \in \mathbb{R}^m$ , $M$ outputs a new perturbed vector:

M(v) \doteq v + L

where $L \doteq \left< l_1, l_2, ..., l_m\right>$ and each $l_i$ is sampled independently from $Lap( \frac{2 }{ n \epsilon } )$ .

Privacy

We claim this mechanism is $(\epsilon, 0)$ -differentially private. For $u \in \mathbb{R}^n$ , we have

\begin{aligned} \frac{ p(M(h_S) = u) }{ p(M(h_{S'}) = u) } &= \frac{ \prod_{i \in [m] } p( f_S (x_i) + l_i = u_i) }{ \prod_{i \in [m] } p( f_{S'} (x_i) + l_i = u_i) } \\ &= \frac{ \prod_{i \in \{k, l\} } p( f_S (x_i) + l_i = u_i) }{ \prod_{i \in \{k, l\} } p( f_{S'} (x_i) + l_i = u_i) } \\ &\le \exp( - (|u_k - f_S(x_k)| - |u_k - f_{S'} (x_k) |) \frac{n\epsilon}{2} ) \\ &\quad \cdot \exp( - (|u_l - f_S(x_l)| - |u_l - f_{S'} (x_l) |) \frac{n\epsilon}{2} ) \\ &\le \exp( |f_S(x_k) - f_{S'} (x_k) | \frac{n\epsilon}{2} ) \cdot \exp( |f_S(x_l) - f_{S'} (x_l) | \frac{n\epsilon}{2} ) \\ &= \exp( \frac{1}{n} \frac{ n \epsilon}{2} ) \cdot \exp( \frac{1}{n} \frac{n\epsilon}{2} ) \\ &= \exp( \epsilon). \end{aligned}

Accuracy

We prove that $|M(h_S) - h_S |_\infty = O (\frac{1}{ n \epsilon } \log \frac{m}{\delta})$ with probability at least $1 - \delta$ .

Let $b = \frac{2 }{ n \epsilon }$ . For a failure probability $\delta$ ,

\Pr[ |f_S(x_i) + l_i - f_S(x_i) | \ge b \log \frac{m}{\delta} ] = \int_{ b \log \frac{m}{\delta} }^\infty \frac{1}{b} \exp( - x / b ) \ dx = \exp(- \log \frac{m}{\delta} ) = \frac{\delta}{m}

By union bound, it holds that

\Pr[ |M(h_S) - h_S |_\infty \ge b \log \frac{m}{\delta} ] \le \delta.

$\square$

Rounding Small Values

When $|\mathcal{X}| = m \gg n$ , we could improve the release mechanism. As shown in the previous section, we would like to achieve error $O(\frac{1}{n})$ . This inspire to round the small frequencies (roughly $O(\frac{1}{n})$ ) to zero. Of course, we should carry out this in a differentially private manner.

Mechanism $M$
$===============================$
INPUT: a set $S$ of $n$ elements.
OUTPUT: a histogram of $S$ in differentially private manner.
$------------------------$
For $i \in [m]$ do
$\qquad$ If $f_S(x_i) = 0$ , then $M(h_S)_i \leftarrow 0$
$\qquad$ Else
$\qquad$ $\qquad$ $M(h_S)_i \leftarrow f_S(x_i) + l_i$ , where $l_i \sim Lap(\frac{2}{n \epsilon} )$ .
$\qquad$ $\qquad$ If $M(h_S)_i < \frac{1}{n} +\frac{2 \log 2 / \delta }{ \epsilon n}$ , then $M(h_S)_i \leftarrow 0$ .
Release $M(h_S) \doteq \left< M(h_S)_1, M(h_S)_2, ... , M(h_S)_n \right>$
$------------------------$

Privacy

We claim this mechanism is $(\epsilon, \delta)$ -differentially private.

Case 1. If $S$ and $S'$ have the same set of supports, i.e., $f_S(x_i) > 0 \leftrightarrow f_{S'}(x_i) > 0$ , then $M$ is $(\epsilon, 0)$ differentially private.
Case 2.
1. $F_{S} (x_k) = 1$ , then $F_{S'} (x_k) = F_{S} (x_k) - 1 = 0$ . For $S'$ , it is guaranteed that $M(h_{S'})_k = 0$ . For $S$ , as $f_S(x_k) = \frac{1}{n}$ , $\Pr[ M(h_S)_k \neq 0 ] = \Pr[ M(h_S)_k \neq M(h_{S'})_k ] = \frac{\delta}{2}$
2. $F_{S} (x_l) = 0$ , then $F_{S'} (x_l) = F_{S} (x_l) + 1 = 1$ . For $S$ , it is guaranteed that $M(h_S)_k = 0$ . For $S'$ , by similar argument, we have $\Pr[ M(h_{S'})_k \neq 0 ] = \Pr[ M(h_S)_k \neq M(h_{S'})_k ] = \frac{\delta}{2}$ .
There are three combinations such that either $F_S(x_k) = 1$ or $F_{S} (x_l) = 0$ holds, namely
1. $F_S(x_k) = 1, F_{S} (x_l) = 0$ ,
2. $F_S(x_k) = 1, F_{S} (x_l) > 0$ ,
3. $F_S(x_k) > 1, F_{S} (x_l) = 0$ .
We give a proof for the first case. The proofs for the other two are similar. Now, for $\forall$ measurable $E \subset \mathbb{R}^n$ ,
$\begin{aligned} \Pr[ M(h_S) \in E] &= \Pr[ M(h_S) \in E \mid M(h_S)_k = 0, M(h_{S'})_l = 0] \\ &\ + \Pr[ M(h_S) \in E \mid M(h_S)_k \neq 0 \vee M(h_{S'})_l \neq 0] \\ &\le \Pr[ M(h_S) \in E \mid M(h_S)_k = 0, M(h_{S'})_l = 0] \\ &\ + \Pr[M(h_S)_k \neq 0 ] + \Pr[ M(h_{S'})_l \neq 0] \\ &= \Pr[ M(h_{S'}) \in E \mid M(h_S)_k = 0, M(h_{S'})_l = 0] + \delta \\ &\le \Pr[ M(h_{S'}) \in E] + \delta \end{aligned}$

Accuracy

We prove that $|M(h_S) - h_S |_\infty = O (\frac{1}{ n \epsilon } \log \frac{1}{\delta})$ with probability at least $1 - \delta$ , if $\delta \le \frac{1}{n}$ .

If $f_S(x_i) = 0$ , then there is no error.
Otherwise, if $M(h_S)_i$ is not truncated, with probability at most $\frac{\delta}{n}$ , it $|M(h_S)_i - f_S(x_i)|\le \frac{2\log 1 / \delta}{n\epsilon}$ . If it is truncated, this will introduce an additional error of at most $\frac{1}{n} +\frac{2 \log 2 / \delta }{ \epsilon n}$ . The overall error is at most $\frac{1}{n} +\frac{4 \log 2 / \delta }{ \epsilon n}$ , which is $O( \frac{ \log 1 / \delta }{ \epsilon n})$ if $\epsilon \le \log n$ .

$\square$

Reference

[1] S. Vadhan, “The Complexity of Differential Privacy,” in Tutorials on the Foundations of Cryptography, Y. Lindell, Ed. Cham: Springer International Publishing, 2017, pp. 347–450.