2
$\begingroup$

In a paper Distributed Private Data Analysis: On Simultaneously Solving How and What, a bit vector $x=(x_1,\dots,x_n)$ is given, whose sum $f=\sum_i x_i$. Each bit $x_i$ is independently flipped with probability $p=\frac{1}{2+\epsilon}$ for fixed $\epsilon>0$. That is, let $z_i=x_i$ with probability $1-p$ and $z_i=1-x_i$ otherwise. Then given the flipped bit vector $\mathrm{flip}(x)=(z_1,\dots,z_n)$, the original sum $f$ has an unbiased estimator: $ \hat{f}=\epsilon^{-1}((2+\epsilon)\sum_i z_i) - \epsilon^{-1}n $ The paper then claims that this estimator has error $\mathcal{O}(\sqrt{n}/\epsilon)$ with constant probability. That is, for all bit vectors $x$: $ \Pr[|\hat{f}(x) - f(x)| > \mathcal{O}(\sqrt{n}/\epsilon)] \leq \mathcal{O}(1) $ They say they got it via Chernoff bound. So I tried to work my way, using the definition of Chernoff bound from the book "The Probabilistic Method" (note: the absolute is missing): $ \Pr[\hat{f} - f > \ell] \leq \mathbb{E}[e^{\lambda(\hat{f} - f)}] e^{-\lambda \ell} = \mathbb{E}[e^{\lambda \hat{f} }] e^{-\lambda (\ell+ f)} $ Then $ \mathbb{E}[e^{\lambda \hat{f} }] = \mathbb{E}[e^{2 \frac{\lambda}{\epsilon} \sum_i z_i+ \lambda \sum_i z_i - \frac{\lambda}{\epsilon}n }] = \mathbb{E}[e^{2 \frac{\lambda}{\epsilon} \sum_i z_i} ] \mathbb{E}[ e^ { \lambda \sum_i z_i } ] e ^ {- \frac{\lambda}{\epsilon} n } $

$ = (\prod_i \mathbb{E}[e^{2 \frac{\lambda}{\epsilon} z_i} ] ) (\prod_i \mathbb{E}[ e^ { \lambda z_i } ] ) e ^ {- \frac{\lambda}{\epsilon} n } $

When I expand $\mathbb{E}[ e^ { \lambda z_i } ]$ to $p e^ { \lambda (1-x_i) } + (1-p) e^ { \lambda x_i } $, I collect in two groups to get rid of $x_i$'s; a group evaluated at $x_i=1$ and raised to power $f$ (number of ones in the bit vector) and similarly for $x_i=0$.

I end up with a big ugly equation that I have no hope of setting $\lambda$ to get a constant probability (in $n$) as the paper claims (remember $\ell = \mathcal{O}(\sqrt{n}/\epsilon)$).

I am not sure how to proceed or whether I am doing things wrong. I've spend a lot of time on this (several weeks!) and tried to read about Chernoff bound from different sources. Any feedback is welcome, hints or directions are also great. Thank you.

1 Answers 1

1

The original binomial random variable has variance $\Theta(n)$, and so $\hat{f}-f$ has zero mean and variance $\Theta(n/\epsilon^2)$. The standard deviation is $\Theta(\sqrt{n}/\epsilon)$, and the central limit theorem implies that the probability that you're more than a constant number of standard deviations off is some constant.

Chernoff's bound is a "finite" version of the central limit theorem giving explicit bounds (rather than bounds in probability), that are useful to bound large deviations. But in this case you don't even have to use it. But if you do use it, it should work.

The version you're quoting from the book is part of the proof of the bound. The proof already optimizes $\lambda$ and estimates the resulting bound. If you use a more streamlined version (which must be available even in the book), you should just "plug the numbers" and get your result.

  • 0
    The contribution of each bit to $\hat{f} - f$ is either $Z$ or $-Z$, depending on the bit, where $Z$ is some affine transformation of a Bernoulli random variable. So you're right that the bits are not symmetric, but the bound works anyhow. If it helps, both $Z$ and $-Z$ have the same first two moments.2011-07-01