1
$\begingroup$

Hoeffding's inequality is surely a concentration inequality. It can be written in the form:

$\Pr(\bar X + f(n,\delta) \geq \mu) \geq 1-\delta,$

for some function $f$, where $X$ is a set of i.i.d. samples of a random variable with mean $\mu$, $\bar X$ is the sample mean, and $\delta \in [0,1]$. Maurer and Pontil presented an empirical Bernstein bound that uses the sample mean and sample standard deviation. It can be written in the form:

$\Pr(\bar X + f(X, n, \delta) \geq \mu) \geq 1-\delta,$

for some other function f that now depends on the sample $X$ (specifically, on the sample standard deviation of $X$).

Interestingly, Maurer and Pontil do not call their inequality a "concentration inequality". Notice that the width of the confidence interval it would provide on the mean depends on the samples, X. Similarly, Anderson (1969) presented a high-confidence bound on the mean that cannot (immediately) be formulated as a deviation from the sample mean. That is, its most natural form would be:

$\Pr(f(X, n, \delta) \geq \mu) \geq 1-\delta,$

for some other function f that one could (with work) phrase as the sample mean plus another term that depends on the sample, but which is not naturally in this form.

Which of these is a "concentration inequality"? Is Anderson's inequality not a concentration inequality because it is not clearly showing how the sample mean deviates from the expected value? Is even Maurer and Pontil's inequality not a concentration inequality because its confidence interval around the sample mean depends on the sample (and hence it cannot be written in the form Hoeffding's inequality is usually presented in)?

If Maurer & Pontil's inequality and/or Anderson's inequality are not concentration inequalities, what would you call them? Is the term "concentration inequality" sufficiently vague that it is up to personal interpretation whether each of these is a concentration inequality?

$\endgroup$
2
  • $\begingroup$ Are you saying that the probability to deviate from the mean is large? $\endgroup$
    – lcv
    Apr 4, 2019 at 21:32
  • $\begingroup$ No, the probability of the mean being less than the sample mean plus f(n,delta) is high, so the probability that the sample mean deviates (by being too small) by more than f(n,delta) is low. $\endgroup$
    – PThomasCS
    Apr 4, 2019 at 21:41

0

Your Answer

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