A Maximal Version of Empirical Bernstein Inequality

up vote
1
down vote

favorite

Bernstein inequality is a very powerful concentration inequality, and can obtain a sharper bound than Hoeffding providing the variance is sufficiently small. The following statements exactly show this [1].

Bernstein Inequality.

Let $X_1,X_2,ldots,$ be a sequence of independent random variables such that for all $igeq 1$, with $mathbbE[X_i]=0$ and $X_iin [-1,1]$. Suppose their variance is smaller than $sigma$, that is, $mathbbE[X_i^2]leq sigma$. Then the classic Bernstein ineqality says that
$$
Prleft[sum_i=1^m X_i > t right]leq expleft-fract^22msigma + 4tright.
$$

Maximal Form of Bernstein Inequality. With the same condition as shown in Bernstein inequality, then the maximal form says that
$$
Prleft[max_1leq jleq msum_i=1^j X_i > t right]leq expleft-fract^22msigma + 4tright.
$$

In many scenarios, however, we prefer to adopt the empirical Bernstein inequality shown as follows (Theorem 1 in [2]),

Empirical Bernstein Inequality. Let $X_1,X_2,ldots,$ are iid random variables taking values in $[0,b]$, and $mathbbE[X_i]=0$ for all $i$. Define the emprical variance as $hatsigma_t=sum_i=1^t(X_t-hatmu_t)^2/t$, with $hatmu_t = sum_i=1^t X_i/t$, then for any $tin mathbbN$ and $s>0$,
$$
Prleft[|hatmu_t|leq sqrtfrac2hatsigma_t st + frac3bstright] geq 1-3e^-s.
$$

My question: is there a maximal version of empirical Bernstein inequality? Thanks.

Reference:

[1] A note on a maximal Bernstein inequality, https://arxiv.org/pdf/1107.3365.pdf

[2] Exploration-exploitation trade-off using variance estimates in the multiarmed bandit setting, http://certis.enpc.fr/~audibert/RR0731.pdf

edited Jul 24 at 1:41

asked Jul 23 at 2:15

Peng Zhao

689

add a commentÂ |Â

up vote
1
down vote

favorite

Bernstein Inequality.

Let $X_1,X_2,ldots,$ be a sequence of independent random variables such that for all $igeq 1$, with $mathbbE[X_i]=0$ and $X_iin [-1,1]$. Suppose their variance is smaller than $sigma$, that is, $mathbbE[X_i^2]leq sigma$. Then the classic Bernstein ineqality says that
$$
Prleft[sum_i=1^m X_i > t right]leq expleft-fract^22msigma + 4tright.
$$

Maximal Form of Bernstein Inequality. With the same condition as shown in Bernstein inequality, then the maximal form says that
$$
Prleft[max_1leq jleq msum_i=1^j X_i > t right]leq expleft-fract^22msigma + 4tright.
$$

In many scenarios, however, we prefer to adopt the empirical Bernstein inequality shown as follows (Theorem 1 in [2]),

Empirical Bernstein Inequality. Let $X_1,X_2,ldots,$ are iid random variables taking values in $[0,b]$, and $mathbbE[X_i]=0$ for all $i$. Define the emprical variance as $hatsigma_t=sum_i=1^t(X_t-hatmu_t)^2/t$, with $hatmu_t = sum_i=1^t X_i/t$, then for any $tin mathbbN$ and $s>0$,
$$
Prleft[|hatmu_t|leq sqrtfrac2hatsigma_t st + frac3bstright] geq 1-3e^-s.
$$

My question: is there a maximal version of empirical Bernstein inequality? Thanks.

Reference:

[1] A note on a maximal Bernstein inequality, https://arxiv.org/pdf/1107.3365.pdf

[2] Exploration-exploitation trade-off using variance estimates in the multiarmed bandit setting, http://certis.enpc.fr/~audibert/RR0731.pdf

edited Jul 24 at 1:41

asked Jul 23 at 2:15

Peng Zhao

689

add a commentÂ |Â

up vote
1
down vote

favorite

Bernstein Inequality.

Let $X_1,X_2,ldots,$ be a sequence of independent random variables such that for all $igeq 1$, with $mathbbE[X_i]=0$ and $X_iin [-1,1]$. Suppose their variance is smaller than $sigma$, that is, $mathbbE[X_i^2]leq sigma$. Then the classic Bernstein ineqality says that
$$
Prleft[sum_i=1^m X_i > t right]leq expleft-fract^22msigma + 4tright.
$$

Maximal Form of Bernstein Inequality. With the same condition as shown in Bernstein inequality, then the maximal form says that
$$
Prleft[max_1leq jleq msum_i=1^j X_i > t right]leq expleft-fract^22msigma + 4tright.
$$

In many scenarios, however, we prefer to adopt the empirical Bernstein inequality shown as follows (Theorem 1 in [2]),

Empirical Bernstein Inequality. Let $X_1,X_2,ldots,$ are iid random variables taking values in $[0,b]$, and $mathbbE[X_i]=0$ for all $i$. Define the emprical variance as $hatsigma_t=sum_i=1^t(X_t-hatmu_t)^2/t$, with $hatmu_t = sum_i=1^t X_i/t$, then for any $tin mathbbN$ and $s>0$,
$$
Prleft[|hatmu_t|leq sqrtfrac2hatsigma_t st + frac3bstright] geq 1-3e^-s.
$$

My question: is there a maximal version of empirical Bernstein inequality? Thanks.

Reference:

[1] A note on a maximal Bernstein inequality, https://arxiv.org/pdf/1107.3365.pdf

[2] Exploration-exploitation trade-off using variance estimates in the multiarmed bandit setting, http://certis.enpc.fr/~audibert/RR0731.pdf

edited Jul 24 at 1:41

asked Jul 23 at 2:15

Peng Zhao

689

Bernstein Inequality.

Let $X_1,X_2,ldots,$ be a sequence of independent random variables such that for all $igeq 1$, with $mathbbE[X_i]=0$ and $X_iin [-1,1]$. Suppose their variance is smaller than $sigma$, that is, $mathbbE[X_i^2]leq sigma$. Then the classic Bernstein ineqality says that
$$
Prleft[sum_i=1^m X_i > t right]leq expleft-fract^22msigma + 4tright.
$$

Maximal Form of Bernstein Inequality. With the same condition as shown in Bernstein inequality, then the maximal form says that
$$
Prleft[max_1leq jleq msum_i=1^j X_i > t right]leq expleft-fract^22msigma + 4tright.
$$

In many scenarios, however, we prefer to adopt the empirical Bernstein inequality shown as follows (Theorem 1 in [2]),

Empirical Bernstein Inequality. Let $X_1,X_2,ldots,$ are iid random variables taking values in $[0,b]$, and $mathbbE[X_i]=0$ for all $i$. Define the emprical variance as $hatsigma_t=sum_i=1^t(X_t-hatmu_t)^2/t$, with $hatmu_t = sum_i=1^t X_i/t$, then for any $tin mathbbN$ and $s>0$,
$$
Prleft[|hatmu_t|leq sqrtfrac2hatsigma_t st + frac3bstright] geq 1-3e^-s.
$$

My question: is there a maximal version of empirical Bernstein inequality? Thanks.

Reference:

[1] A note on a maximal Bernstein inequality, https://arxiv.org/pdf/1107.3365.pdf

[2] Exploration-exploitation trade-off using variance estimates in the multiarmed bandit setting, http://certis.enpc.fr/~audibert/RR0731.pdf

edited Jul 24 at 1:41

asked Jul 23 at 2:15

Peng Zhao

689

edited Jul 24 at 1:41

asked Jul 23 at 2:15

Peng Zhao

689

asked Jul 23 at 2:15

Peng Zhao

689

asked Jul 23 at 2:15

Peng Zhao

689

add a commentÂ |Â

active

oldest

votes

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859951%2fa-maximal-version-of-empirical-bernstein-inequality%23new-answer', 'question_page');

);

Post as a guest

Name

active

oldest

votes

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

ukmuiik