Differential Privacy and Randomized Responses for Counting Queries

Question

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!

Answer 1

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.