2

The definition of differential privacy states that if $\mathcal{M}$ is $(\epsilon,\delta)$-differentially private, then $\forall x,y$ such that $||x-y||_1\leq1$ and for all $S \subseteq \mathrm{Range}(\mathcal{M})$:

$$\mathrm{Pr}(M(x)\in S) \leq e^\epsilon \mathrm{Pr}(M(y)\in S) + \delta. $$

Now, suppose you were able to show that for any outcome $s_i$ (single element) that $\mathcal{M}$ was $(\epsilon,\delta)$-differentially private, i.e., $\mathrm{Pr}(M(x)= s_i) \leq e^\epsilon \mathrm{Pr}(M(y)= s_i) + \delta $. Then for a set $S=\cup_i s_i$, since $\mathrm{Pr}(M(x)\in S) = \sum_i \mathrm{Pr}(M(x)=s_i)$, we have that:

$$\sum_i \mathrm{Pr}(M(x)=s_i) \leq e^\epsilon \sum_i \mathrm{Pr}(M(y)=s_i) + |S| \delta \implies$$ $$\mathrm{Pr}(M(x)\in S) \leq e^\epsilon \mathrm{Pr}(M(y) \in S) + |S| \delta$$

The above is fine if we have $(\epsilon,0)$ with $\delta=0$, but non-zero delta causes a problem. There is a one to one corresponds between proving differential privacy over a single element and a set in the case when $\delta=0$. But the definition doesn't make sense to me for $\delta \neq 0$.

What am I missing?

SAE
  • 23

1 Answers1

1

To show that a mechanism/algorithm is $(\epsilon,\delta)$-differentially private you would have to show that the inequality holds for all subsets (technically all measurable subsets, which matters if the output is continuous).

So if you are in a situation where all you can show is that for single outputs $s$ that the inequality holds for some $\delta > 0$ then you might, as you see, have a hard time stitching together the same guarantee for all subsets. In most cases, however, you won't need to build up the result like that.

An intuition behind the parameter $\delta$ is that it is the probability that the stronger $(\epsilon,0)$ guarantee fails to hold. That is, the probability of producing an $s$ such that for some neighboring $y$ the bound fails to hold.

A related concept are composition bounds, which are used to analyze the aggregate privacy risk of releases from a collection of $(\epsilon,\delta)$-differentially private mechanisms. Composition bounds give an upper bound on the total privacy risk. However each individual risk has to satisfy the bound for all measurable subsets in the range of the mechanism.

Anand Sarwate
  • 94