3
$\begingroup$

I've read in a paper using Hoeffding's inequality to derive a bound on the probability of the difference of means of two samples being larger than a threshold that "Hoeffding's bound greatly overestimates the probability of large deviations for distributions of small variance; in fact, it is equivalent to assuming always the worst-case variance $\sigma ^{2}=\frac{1}{4}$" but I'm having a tough time figuring out why it is the case.

Thank you in advance for any help.

$\endgroup$
1
  • 1
    $\begingroup$ It wouldn't be a bound if the worst-case variance caused the probability to exceed the bound. $\endgroup$
    – jbowman
    Apr 13, 2022 at 2:06

1 Answer 1

4
$\begingroup$

I would have said that was true for moderate deviations rather than large deviations. One way to look at it is to compare Hoeffding's inequality, which only uses the upper and lower bounds, with Bernstein's inequality, which uses explicit variances.

Hoeffding's inequality says $$P( |\bar X_n-\mu_n|>t)\leq 2\exp\left(-\frac{2nt^2}{(b-a)^2}\right)$$ Bernstein's inequality says $$P(|\bar X_n-\mu_n|>t)\leq 2\exp\left(-\frac{nt^2}{2\sigma^2+2ct/3} \right)$$ where $\sigma^2=\frac{1}{n}\sum_{i=1}^n\mathrm{var}[X_i]$ and $c$ is a bound on $|X|$. We can reasonably compare these by taking $2c=(b-a)$

When $t$ is small (so $\bar X_n$ is o(\sqrt{n}) standard errors away from its expectation), the second term in the denominator of Bernstein's inequality is small. Bernstein's inequality then has $nt^2$ scaled by $1/(2\sigma^2)$ and Hoeffding's has it scaled by $2/(b-a)^2$. These are the same if $\sigma^2=(b-a)^2/4$, which is the largest value it can possibly have for a variable restricted to $[a,b]$ -- the value it would have for a binary variable that's equal to each endpoint 50% of the time.

For any other bounded variable (and small $t$), you gain by using the actual variance $\sigma^2$ rather than the upper bound. For large $t$ it's not so simple: the second term in the denominator of Bernstein's inequality dominates, and the bound is much weaker than the Hoeffding one.

You can also see that as $n\to\infty$, the Bernstein bound gets relatively close to the Normal tail probability from the Central Limit Theorem. It doesn't reach the Normal tail probability -- it shouldn't, it's an upper bound -- but the normal density $\phi(t)$ is larger than the tail probability $\Phi(t)$, only by a factor of about $1/t$, not an exponential.

(note: there are lots of ways to write these two inequalities, I used the forms from here)

$\endgroup$
5
  • $\begingroup$ Thank you for your answer, it helped a lot. So it's better to use Hoeffding's inequality when $t$ is small or when $n \rightarrow \infty$. Can I ask you why $\bar{X_{n}}$ is $o(\sqrt{n})$ corresponds to a small $t$ please? $\endgroup$
    – Daviiid
    Apr 14, 2022 at 5:48
  • 1
    $\begingroup$ It's not $\bar X_n=o(\sqrt{n}$, it's $(\bar X_n-\mu)/se =o(\sqrt{n})$. The standard error of $\bar X_n$ is $o(1/\sqrt{n})$, so a constant $t$ is some multiple of $\sqrt{n}$ times the standard error. A small $t$ is of smaller order than that. $\endgroup$ Apr 14, 2022 at 6:33
  • $\begingroup$ I see, right, many thanks for the answers. $\endgroup$
    – Daviiid
    Apr 14, 2022 at 17:54
  • 2
    $\begingroup$ Also, on your first comment: it's better to use Hoeffding's inequality when $t$ is large or $X_i$ are binary (so $\sigma^2$ is that large), or, importantly, when you don't know a bound on $\sigma^2$. $\endgroup$ Apr 14, 2022 at 20:01
  • 1
    $\begingroup$ I understand better why the authors of the paper I was reading used the Hoeffding's now, their main use-cases were on binary $X_{i}$ variables. Thanks a lot ! ^^ $\endgroup$
    – Daviiid
    Apr 16, 2022 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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