2
$\begingroup$

I have a question about Bernstein’s inequality for bounded random variables.

Its statement is the following. Let $X_1, \ldots, X_N$ be independent, mean zero random variables with $|X_i| \leq K \ (i = 1, \ldots, N)$. Then, for any $t \geq 0$, we have $$ P \left( \left|\sum_{i=1}^N X_i\right| \geq t \right) \leq 2 \exp\left(-\frac{t^2/2}{\sigma^2 + Kt/3}\right) $$ where $\sigma^2 = \sum_{i=1}^N \mathbb{E}[X_i^2]$ (see e.g. Theorem 2.8.4 of Vershynin's book).

If the variance $\sigma^2$ is known, we can use Bernstein’s inequality to obtain possibly a shaper bound than the Hoeffding bound (especially when $\sigma^2$ is small; see, e.g., the remark after Theorem 2.10 of Wainwright's book).

However, this inequality is not useful if we have access to only finite samples and don’t know the true variance $\sigma^2$, in the sense that we cannot directly evaluate the value of the right-hand side with the accessible samples.

In practice, if the sample variance is small and the sample size is sufficiently large, we can infer that $\sigma^2$ is small with a high probability. So it would be natural to hope to utilize such knowledge (i.e. small variance) to obtain a sharper bound than Hoeffding's bound with Bernstein's inequality.

Are there any proper ways of conducting such an idea?

$\endgroup$
2
  • $\begingroup$ Your questions are quite unclear and are impossible to answer in this form. What exactly do you know? And what is your goal here, specifically? Also, you should reduce your questions just to one. (There should not be multiple questions in one post.) $\endgroup$ Feb 22, 2023 at 18:57
  • $\begingroup$ Thank you for your comment. I revised my question to clarify my point. I found a paper that provided an answer, so I answered my question myself. $\endgroup$
    – aest
    Mar 1, 2023 at 13:00

1 Answer 1

1
$\begingroup$

I have learned that my question was the exact idea behind the so-called empirical Bernstein bounds. See this paper for details: https://www.learningtheory.org/colt2009/papers/012.pdf

$\endgroup$

Your Answer

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

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