1
$\begingroup$

I came across the following problem when I read the book, "Understanding Machine Learning: from theory to algorithms". You can click the link to download the book.

The statement is on Page 399. When you arrive at Page 399, you can search the keywords "Chernoff’s inequality implies". Then you can find the whole inequality. Here is the snapshot of the statement: enter image description here

Let $X_1, ..., X_m$ be independent Bernoulli random variables, whose sum is $Z$, each having probability $p \in (0,1)$ of being equal to $1$.

Please prove that

$$P[Z\le \frac{pm}{2}]\le e^{-\frac{2}{mp} (mp-\frac{mp}{2})^2}$$

I have read some reference materials in Wikipedia, Chernoff's bound, but I did not find any theorem or inequality to get the solution straightforward. Hope you can help me!

$\endgroup$
9
  • $\begingroup$ Hi @Ben, please make an effort to show what you have already tried, including reading the Chernoff Wikipedia article. $\endgroup$ Nov 16 '19 at 8:17
  • $\begingroup$ I have added what I have tried. $\endgroup$
    – Ben
    Nov 16 '19 at 8:22
  • $\begingroup$ Great! Which materials did you read? And how close were they to giving the right solution? $\endgroup$ Nov 16 '19 at 10:47
  • $\begingroup$ That is en.wikipedia.org/wiki/Chernoff_bound. And I have also updated the question! I'll be looking forward to your answer. $\endgroup$
    – Ben
    Nov 16 '19 at 11:09
  • $\begingroup$ So your exponent is equal to $-mp/2$. A lot of the results on the Wikipedia page easily gives $-mp/8$. This is the kind of thing that would be useful for you to state in the question, so we know that it's not just a typo that you put it that way. $\endgroup$ Nov 16 '19 at 12:10
1
$\begingroup$

There is apparently a mistake in your book. One example where the bound $\Pr[Z\le mp/2]\le\exp(-mp/2)$ is wrong, is $p=1/8$, $m=16$. Then the bound says $\Pr[Z\le mp/2]\le\exp(-1)\approx 0.37$, while in actual fact $\Pr[Z\le mp/2] = \Pr[Z\le 1] = (1-p)^{16}+16(1-p)^{15}p \approx 0.39$.

The real best bound you should use from Chernoff (or Hoeffding) is \begin{align} \Pr( Z \leq \varepsilon m)\leq\exp\left(-\frac{(\epsilon-p)^2 m}{2p}\right). \end{align} In our case, setting $\varepsilon=p/2$, we get $\Pr( Z \leq pm/2)\leq\exp(-mp/8)$.

This bound is completely fine for the application in the book, since on the previous page, $m$ is defined to be $\ge\frac{8}{\epsilon}(2d\dots)$, and this factor of 8 is simply ignored in the proof. Thus everything works out well, and maybe the $/8$ version was even what was originally intended, since otherwise it's a bit weird to have that factor of 8 flying around in the theorem.

Sorry you ran into a bad proof. Computer scientists are often fairly sloppy with their constants when they use Chernoff bounds.

$\endgroup$
4
  • $\begingroup$ When setting $\epsilon = \frac{p}{2}$, how can we get $\Pr[Z\le mp/2]\le 1/2$? Could you provide the whole derivation? I'll be looking forward to your answer. Thank you a lot! $\endgroup$
    – Ben
    Nov 17 '19 at 3:06
  • $\begingroup$ Once you have $𝑚𝑝/8$, you just plug in the lower bound for $m$ stated on the previous page. $\endgroup$ Nov 17 '19 at 14:36
  • $\begingroup$ Could you provide the detailed derivation, please? I'm still puzzled about the derivation from $e^{-m\epsilon /8 }$ to $\frac{-dlog(\frac{1}{\delta})}{2}$. Hope you can help me! I will really appreciate your help! $\endgroup$
    – Ben
    Nov 18 '19 at 0:29
  • $\begingroup$ @Ben They're just doing a very rough bound. Basically saying that $d + \log1/\delta < d \log 1/\delta$. You probably have to ask a new question to make it sure exactly where things go bad when you're trying to follow their argument.. $\endgroup$ Nov 18 '19 at 7:56

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.