A Unifying Privacy Analysis Framework for Unknown Domain Algorithms in Differential Privacy

We will rely on Lemma 3.1 to prove this result. Consider neighbors $h,h^{\prime}$ where $h$ has one additional user’s data from $h^{\prime}$, without loss of generality. By assumption, we know that $h$ can differ in at most $\Delta_{0}$ counts for different labels. Furthermore, we know that in counts that are differing, they can differ by at most $\Delta_{\infty}$. Consider the set $S$ to be the set of labels that are common between $h$ and $h^{\prime}$ along with corresponding counts. Since we assume that $h$ has one additional user’s data from $h^{\prime}$, we know that this set $S$ must include all labels of $h^{\prime}$. Note that the counts for the items that are not present in $h^{\prime}$ but are present in $h$ must be at most $\Delta_{\infty}$. We now cover each item in Lemma 3.1.

• 1.

  We define the event $E$ to be all the randomness in $A(h)$ that can generate outcomes in $S$, so that $E$ must only include the noise that is added to items that are common between $h$ and $h^{\prime}$ and the noise that is added to the items’ counts in $h$, but not in $h^{\prime}$ must be bounded. We then lower bound the probability of event $E$. Note that for every item $j$ who is in $h$ just not in $S$, it’s count can be no more than $\Delta_{\infty}$.

  	$\displaystyle\Pr_{A(h)}[E]$	$\displaystyle=\prod_{j:(j,\cdot)\in h\setminus h^{\prime}}\Pr[c_{j}+\mathrm{Noise}\leq T]$
  		$\displaystyle\geq\prod_{j:(j,\cdot)\in h\setminus h^{\prime}}\Pr[\Delta_{\infty}+\mathrm{Noise}\leq T]$

  We then consider the two scenarios with either Laplace noise or Gaussian noise.

  • –

    (Laplace) With Laplace noise of scale $b>0$, with $T=\Delta_{\infty}+b\log(\tfrac{\Delta_{0}}{2\delta})$, we have

    $\displaystyle\Pr_{A(h)}[E]\geq\left(1-\frac{1}{2}\exp\left(-\frac{T-\Delta_{\infty}}{b}\right)\right)^{\Delta_{0}}\geq 1-\delta.$

  • –

    (Gaussian) Next we consider the Gaussian noise version that has standard deviation $\sigma>0$ with $T=\Delta_{\infty}+\sigma\Phi^{-1}(1-\delta/\Delta_{0})$.

    $\displaystyle\Pr_{A(h)}[E]\geq\Phi\left(\frac{T-\Delta_{\infty}}{\sigma}\right)^{\Delta_{0}}\geq 1-\delta.$

  For this case, the event $E^{\prime}$ is all randomness in $A(h^{\prime})$ that can generate outcomes in $S$, which would include all randomness in $A(h^{\prime})$ because $h^{\prime}$ is a subset of $h$.

• 2.

  We then consider the mechanism $A^{\prime}$ whose domain is the set of common items between $h$ and $h^{\prime}$ and has noise added to each count so that only noisy counts above $T$ are returned with its corresponding item label. We write the distribution of $A^{\prime}(h)$ as $P^{\prime}$ and the distribution of $A^{\prime}(h^{\prime})$ as $Q^{\prime}$. Because we add independent noise to each histogram count, we can separate out the noise terms added to the counts of labels that are not common between $h$ and $h^{\prime}$, hence we know that $P(y)=\Pr[E]P^{\prime}(y)$ for $y\in S$, by design. Furthermore $Q\equiv Q^{\prime}$.

• 3.

  Note that $A^{\prime}$ is either the Laplace mechanism or the Gaussian mechanism over common items between $h$ and $h^{\prime}$. We then cover each variant separately.

  • –

    (Laplace) We first consider the case where we apply Laplace noise with noise parameter $b>0$. Note that $A^{\prime}$ is a Laplace Mechanism over a histogram that can change in at most $\Delta_{0}$ counts and each count can differ by at most $\Delta_{\infty}$. Ignoring the threshold in $A^{\prime}$, as this is a post processing of the noisy histogram and does not impact the privacy analysis, we can then say that the Laplace mechanism is being applied to a histogram with $\ell_{1}$-sensitivity $\Delta_{0}\Delta_{\infty}$. Hence, we know that the Laplace mechanism is $\Delta_{0}\Delta_{\infty}/b$-(pure) DP and hence $(\Delta_{0}^{2}\Delta_{\infty}^{2}/b^{2}/2)$-(pure) CDP. However, this will not get us the result we want because it would result in $\Delta_{0}^{2}\varepsilon^{2}/2$-CDP with $b=\Delta_{\infty}/\varepsilon$. This was due to using the $\ell_{1}$-sensitivity of the histogram and then applying Theorem 1.

    We now consider the Laplace mechanism only on the common items between $h$ and $h^{\prime}$ that also have differing counts. We call the corresponding mechanism $\hat{A}$ and denote the distribution $\hat{P}$ for $\hat{A}(h)$ and the distribution $\hat{Q}$ for $\hat{A}(h^{\prime})$. Note that each noisy count in $\hat{A}$ is generated independently, so we can say that each count in $\hat{A}$ is a single univariate Laplace mechanism. Each Laplace mechanism will then be $\Delta_{\infty}/b$-(pure) DP and hence $(\Delta_{\infty}/b)^{2}/2$-(pure) CDP. Applying composition from Theorem 6 over each univariate Laplace mechanism implies that $\hat{A}$ is $\frac{\Delta_{0}(\Delta_{\infty})^{2}}{2b^{2}}$-(pure) CDP. Let $\tilde{A}$ denote the Laplace Mechanism applied to the counts that were unchanged between $h$ and $h^{\prime}$ with distribution $\tilde{P}$ for $\tilde{A}(h)=\tilde{A}(h^{\prime})$. For ease of notation, let $h$ and $h^{\prime}$ match on the first $d^{\prime}\leq d$ indices and let the first $k\leq\Delta_{0}$ indices of $h$ and $h^{\prime}$ have differing counts. Hence, we have for outcome $y=(y_{1},\cdots,y_{d^{\prime}})$ that $P^{\prime}(y)=\hat{P}(y_{1},\cdots,y_{k})\cdot\tilde{P}(y_{k+1},\cdots,y_{d^{\prime}})$. Similarly, we have $Q^{\prime}(y)=\hat{Q}(y_{1},\cdots,y_{k})\cdot\tilde{P}(y_{k+1},\cdots,y_{d^{\prime}})$. This gives us the following for $\lambda\geq 1$

    $$D_{\lambda}(P^{\prime}||Q^{\prime})=D_{\lambda}\left(\hat{P}||\hat{Q}\right)\leq\frac{\Delta_{0}(\Delta_{\infty})^{2}}{2b^{2}}$$

    and similarly,

    $$D_{\lambda}(Q^{\prime}||P^{\prime})\leq\frac{\Delta_{0}(\Delta_{\infty})^{2}}{2b^{2}}.$$

  • –

    (Gaussian) We next consider the Gaussian noise variant. We will denote $A^{\prime}$ as the Gaussian mechanism whose domain is the set of common items between $h$ and $h^{\prime}$ and has noise standard deviation $\Delta_{\infty}/b$ and only counts above $T$ will be returned with its corresponding item label. We write the distribution of $A(h)$ as $P^{\prime}$ and the distribution of $A^{\prime}(h^{\prime})$ as $Q^{\prime}$.

    Note that $A^{\prime}$ is a Gaussian Mechanism over a histogram that can change in at most $\Delta_{0}$ counts and each count can differ by at most $\Delta_{\infty}$. Ignoring the threshold in $A^{\prime}$, again this does not impact the privacy analysis, we can then say that the Gaussian mechanism is being applied to a histogram with $\ell_{2}$-sensitivity $\Delta_{\infty}\sqrt{\Delta_{\infty}}$. Hence, we know that the Gaussian mechanism is $\Delta_{\infty}^{2}\Delta_{0}/\sigma^{2}$-(pure) CDP from Theorem 4. Furthermore, post processing the Gaussian Mechanism is also CDP with the same parameters, so restricting the noisy counts to be larger than $T$ gets us back to distributions $P^{\prime}$ and $Q^{\prime}$. This gives us $D_{\lambda}(P^{\prime}||Q^{\prime})\leq\lambda\tfrac{\Delta_{\infty}^{2}\Delta_{0}}{2\sigma^{2}}$ and $D_{\lambda}(Q^{\prime}||P^{\prime})\leq\lambda\tfrac{\Delta_{\infty}^{2}\Delta_{0}}{2\sigma^{2}}$, for all $\lambda\geq 1$.

Hence, using Laplace noise with scale $b>0$ in the Unknown Domain Histogram algorithm is $\delta$-approximate $\frac{\Delta_{0}^{2}\Delta_{\infty}^{2}}{2b^{2}}$-CDP. Setting $b=\Delta_{\infty}/\varepsilon$ completes the proof for Laplace noise. Furthermore, using Gaussian noise with standard deviation $\sigma$ is $\delta$-approximate $\frac{\Delta_{\infty}^{2}\Delta_{0}}{2\sigma^{2}}$-CDP and setting $\sigma=\frac{\Delta_{\infty}}{\varepsilon}$ completes the proof.

∎

We follow the same analysis as in the proof of Theorem 7, which used Lemma 3.1. We again set $S$ to be the set of labels that are common between neighbors $h$ and $h^{\prime}$. Note that we are only considering items with counts in the top-$(\bar{k})$ of each histogram and the items between $h_{(\bar{k})}$ and $h_{(\bar{k})}^{\prime}$, including the zero count items with labels in $\{\bot_{j}\}$. Hence, there might be different items between $h_{(\bar{k})}$ and $h_{(\bar{k})}$, as reducing some counts in $h$ might change the order of the top-$(\bar{k}+1)$. From Lemma 5.2 in [6], we know that there can be at most $\min\{\bar{k},\Delta_{0}\}$ many differing items between the top-$(\bar{k}+1)$ histograms $h_{(\bar{k})}$ and $h_{(\bar{k})}^{\prime}$. We then follow the three items that we need to show in order to apply Lemma 3.1.

• 1.

  We denote $A$ as Algorithm 2 and the event $E$ as the noise added to counts in outcomes $S$ for $A(h)$, the noise added for the threshold $T+c_{(\bar{k}+1)}$ to get $\tilde{T}$, and the noise added to the differing items not in $S$ must be no more that $\tilde{T}$. We define $E^{\prime}$ similarly for $A(h^{\prime})$. Note that for any item $j$ that is in $h_{(\bar{k})}$ but not an item that can be returned in $S$, we know

  $$c_{j}\leq c_{j}^{\prime}+\Delta_{\infty}\leq c^{\prime}_{(\bar{k})}+\Delta_{\infty}\leq c_{(\bar{k})}+\Delta_{\infty}\leq c_{(\bar{k}+1)}+\Delta_{\infty}.$$

  The analysis is straightforward due to the difference between two Gaussians being Gaussian itself. Hence, we have with $\hat{T}=\sqrt{2}\sigma\Phi^{-1}(1-\delta/\Delta_{0})$ so that $T=\hat{T}+\Delta_{\infty}$.

  	$\displaystyle\Pr_{A(x)}[\neg E]$	$\displaystyle\leq\sum_{i=1}^{\Delta_{0}}\Pr\left[c_{(\bar{k}+1)}+\Delta_{\infty}+\mathrm{N}(0,\sigma^{2})>c_{(\bar{k}+1)}+T+\mathrm{N}(0,\sigma^{2})\right]$
  		$\displaystyle=\Delta_{0}\Pr[\mathrm{N}(0,2\sigma^{2})>\hat{T}]$
  		$\displaystyle=\Delta_{0}\left(1-\Phi\left(\frac{\hat{T}}{\sqrt{2}\sigma}\right)\right)$
  		$\displaystyle=\Delta_{0}\left(1-(1-\delta/\Delta_{0})\right)=\delta$

  The analysis to show $\Pr_{A(x^{\prime})}[\neg E^{\prime}]$ is similar.

• 2.

  We then consider the distribution $P^{\prime}(y)$ to be the distribution of $A(h)$ conditioned on $E$. Note that $P(y)=\Pr[E]P^{\prime}(y)$ for each $y\in S$ and similarly $Q(y)=\Pr[E^{\prime}]Q^{\prime}(y)$ for $Q^{\prime}(y)$ being the distribution of $A(h^{\prime})$ conditioned on $E^{\prime}$. We will modify the mechanism $A(h)$ and $A(h^{\prime})$ that will result in the same mechanism when conditioned on events $E$ and $E^{\prime}$, respectively. For each label that differs between $h_{(\bar{k})}$ and $h^{\prime}_{(\bar{k})}$, we change it to common labels $b_{1},\cdots b_{\ell}$ where $\ell=|\{j:(j,\cdot)\in\{h_{(\bar{k})}\setminus h^{\prime}_{(\bar{k})}\}\}|\leq\Delta_{0}$. Because we condition on events $E$, no outcome $y\in S$ can include the indices $b_{1},\cdots,b_{\ell}$. Furthermore, it was shown in [17][Lemma 6.4]] that the resulting histogram with common labels will also have as many as $\Delta_{0}$ items with differing counts, and those counts can change by at most $\Delta_{\infty}$, regardless of how we assign the common labels $\{b_{j}\}$. We then let $P^{\prime}$ and $Q^{\prime}$ be the resulting distribution after this relabeling.

Next we will need to bound the Rényi divergence between $P^{\prime}$ and $Q^{\prime}$. We will make use of the following result from [12][Corollary 4.3]

This result is useful because it allows us to condition on outcomes from a joint Gaussian Mechanism falling in some convex region, which will correspond to releasing only “good” outcomes, i.e. not allowing certain counts from going above some noisy value. For the Gaussian mechanism, we have $F(z)=||z-h||_{2}^{2}$ and $F^{\prime}(z)=||z-h^{\prime}||_{2}^{2}$, which are both $2$-strongly convex over any convex region. Furthermore, we have $||z-h||_{2}^{2}-||z-h^{\prime}||_{2}^{2}$ is $2\sqrt{\Delta_{0}}\cdot\Delta_{\infty}$-Lipschitz. For the density of a Gaussian, we then use $m=\tfrac{1}{2\sigma^{2}}$

• 3.

  We now want to prove that the Rényi divergence between $P^{\prime}$ and $Q^{\prime}$, which are conditioned on events in $E$ and $E^{\prime}$ respectively. To do this we will consider the joint Gaussian distribution that releases all counts over the histograms with common labels, including the $(\bar{k}+1)$-th largest count with added $T$ to its count being labeled $\bot$, but we do not enforce the threshold. We only want to consider events that do not have the items with labels in $\{b_{j}\}$ having noisy count above the noisy count for $\bot$. We then consider the convex region $\mathcal{K}$ where these “bad” noisy counts do not go above the noisy count for $\bot$. We then apply Lemma 4.1 to claim that the resulting mechanism conditioned on this region has a bound on the Rényi Divergence that is the same as if it were the Gaussian mechanism not constrained to region $\mathcal{K}$. Dropping the items with counts lower than the noisy count for $\bot$ is simply post processing, which does not increase the Rényi divergence bound. Hence, we have $D_{\lambda}(P^{\prime}||Q^{\prime})\leq\frac{\lambda\Delta_{0}\Delta_{\infty}^{2}}{2\sigma^{2}}$ and $D_{\lambda}(P^{\prime}||Q^{\prime})\leq\frac{\lambda\Delta_{0}\Delta_{\infty}^{2}}{2\sigma^{2}}$ for all $\lambda\geq 1$.

Setting $\sigma=\Delta_{\infty}/\varepsilon$ completes the proof. ∎