1
$\begingroup$

I'm trying to understand a basic randomized response mechanism for differential privacy (concrete definition not relevant for the question), but I have some trouble understanding the last step in the calculations.

The randomized response mechanism works as follows:

Let's call $q(x) = \frac{1}{n} \sum_{i=1}^{n}q(x_i)$ a counting query for a database $x$ with $n$ entries $x_i$. Each $q(x_i)$ maps into ${0,1}$.

Now define a mechanism $M$ that works as follows:

$M(x_1, \dots, x_n) = (y_1, \dots, y_n)$, where each $y_i$ is computed as follows:

$ y_i = \begin{array}{cc} \{ & \begin{array}{cc} q(x_i) & \textrm{with probability } \frac{1+\epsilon}{2} \\ \neg q(x_i) & \textrm{with probability } \frac{1-\epsilon}{2} \end{array} \end{array} $

Now we can use the value of $M$ to estimate the value of the counting query $q(x)$.

The expected value of $y_i$ is $\mathbb{E}[y_i] = \epsilon q(x_i) + \frac{1-\epsilon}{2}$.

Now the bit that I do not understand

By Chernoff bound,

$$ \left| \frac{1}{n}\sum_i\frac{1}{\epsilon} \cdot (y_i - \frac{(1-\epsilon)}{2}) - q(x) \right| \lt \mathcal{O}\left(\frac{1}{\sqrt{n}\cdot\epsilon}\right) $$

I assume they used the additive Chernoff bound $ \Pr[X \gt \mu + \epsilon] \leq e^{-2n\epsilon^2}$.

It's not clear to me how they got the last part, since it's also not exactly clear to me how they apply the Chernoff bound. In particular how they use the expected value of $y_i$ in combination with $x_i$ and the bound.

Could somebody maybe give me a more detailed calculation of how the last statement was calculated?

Thanks in advance!

$\endgroup$
  • $\begingroup$ for what it's worth, what you describe only satisfies differential privacy if the query $q(x_i) \in \{0, 1\}$ rather than $[0,1]$. $\endgroup$ – Sasho Nikolov May 17 '16 at 19:20
3
$\begingroup$

You have $\mathbb{E}[y_i]=\epsilon q(x_i) + (1-\epsilon)/2$ and $0 \leq y_i \leq 1$, with all they $y_i$s being independent. Thus the Chernoff-Hoeffding bound gives $$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n y_i -\epsilon q(x_i) - \frac{1-\epsilon}2\right| \geq \lambda\right] \leq 2 \cdot e^{-2\lambda^2 n}$$ for all $\lambda>0$. Multiply through by $1/\varepsilon$ to get $$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i - \frac{1-\epsilon}2\right)-q(x_i)\right| \geq \frac{\lambda}{\epsilon}\right] \leq 2 \cdot e^{-2\lambda^2 n}.$$ Set $\lambda=\sqrt{\log(2/\delta)/2n}$ and substitute in $q(x)=\frac{1}{n}\sum_{i=1}^n q(x_i)$ to get $$\mathbb{P}\left[\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i - \frac{1-\epsilon}2\right)-q(x)\right| \geq \frac{\sqrt{\log(2/\delta)}}{\epsilon\sqrt{2n}}\right] \leq \delta.$$ Now "suppress" the $\delta$ parameter using big-O notation to get $$\left|\frac{1}{n} \sum_{i=1}^n \frac{1}{\epsilon}\left(y_i - \frac{1-\epsilon}2\right)-q(x)\right| \leq O\left(\frac{1}{\epsilon\sqrt{n}}\right)$$ with high probability, as required.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Somehow I assumed I would need to use the bound directly on on the value of q(x) and the expected value of the randomized response, but this way I guess it also gives me a bound on the error, since, when n goes to inf the error goes to 0. Is that the reasoning here or are there some more subtle points I'm missing? $\endgroup$ – Cryptonaut May 18 '16 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.