Comprendre la preuve d'un lemme utilisé dans l'inégalité de Hoeffding

J'étudie les notes de cours de Larry Wasserman sur les statistiques qui utilisent Casella et Berger comme texte principal. Je travaille sur ses notes de cours ensemble 2 et je suis resté coincé dans la dérivation du lemme utilisé dans l'inégalité de Hoeffding (pp.2-3). Je reproduis la preuve dans les notes ci-dessous et après la preuve je montrerai où je suis coincé.

Lemme

Supposons que et que . Alors . $\mathbb{E}(X) = 0$ $a \le X \le b$ $\mathbb{E}(e^{tX}) \le e^{t^2 (b-a)^2/8}$

Preuve

Puisque , nous pouvons écrire comme une combinaison convexe de et , à savoir où . Par convexité de la fonction on a $a \le X \le b$ $X$ $a$ $b$ $X = \alpha b + (1 - \alpha) a$ $\alpha = \frac{X-a}{b-a}$ $y \to e^{ty}$

$e^{tX} \le \alpha e^{tb} + (1 - \alpha) e^{ta} = \frac{X-a}{b-a} e^{tb} + \frac{b-X}{b-a} e^{ta}$

Prenez les attentes des deux côtés et utilisez le fait pour obtenir $\mathbb{E}(X) = 0$

$\mathbb{E}(e^{tX}) \le \frac{-a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} = e^{g(u)}$

où , et . Notez que . Aussi pour tout . $u = t(b-a)$ $g(u) = -\gamma u + \log(1-\gamma + \gamma e^{u})$ $\gamma = -a /(b-a)$ $g(0) = g^{'}(0) = 0$ $g^{''}(u) \le 1/4$ $u > 0$

Selon le théorème de Taylor, il existe un tel que $\varepsilon \in (0, u)$ $g(u) = g(0) + u g^{'}(0) + \frac{u^2}{2} g^{''}(\varepsilon) = \frac{u^2}{2} g^{''}(\varepsilon) \le \frac{u^2}{8} = \frac{t^2(b-a)^2}{8}$

D'où . $\mathbb{E}(e^{tX}) \le e^{g(u)} \le e^{\frac{t^2(b-a)^2}{8}}$

Je pourrais suivre la preuve jusqu'à

$\mathbb{E}(e^{tX}) \le \frac{-a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} = e^{g(u)}$ mais je n'arrive pas à comprendre comment dériver . $u, g(u), \gamma$

probability probability-inequalities Anand
la source

Il est intéressant de noter que la valeur maximale de est et donc que le résultat est effectivement qui semble bien trop familier pour naître d'une pure coïncidence. Je soupçonne qu'il existe un autre moyen, peut-être plus simple, de dériver le résultat via un argument probabiliste.

var (X)

$\text{var}(X)$

σ_{max}^{2} = (b - a)^{2} / 4

$\sigma_{\max}^2 = (b-a)^2/4$

E [e^{t X}] \leq e^{σ_{max}^{2} t^{2} / 2}

$E[e^{tX}] \leq e^{\sigma_{\max}^2t^2/2}$

Dilip Sarwate

@DilipSarwate Ma compréhension est que la variance maximale se produit pour une variable aléatoire uniforme . La variance de est . Pouvez-vous expliquer comment vous avez obtenu ?

X \sim U (a, b)

$X \sim \mathcal{U}(a,b)$

X

$X$

V a r (X) = \frac{(b - a)^{2}}{12}

$\mathsf{Var}(X) = \frac{(b-a)^2}{12}$

\frac{(b - a)^{2}}{4}

$\frac{(b-a)^2}{4}$

Anand

En concentrant la masse sur les points d'extrémité ...

Elvis

@DilipSarwate J'ai ajouté quelques commentaires dans la preuve, qui peuvent clarifier un peu pourquoi le pire des cas est la variance maximale.

Elvis

@DilipSarwate - Voir le lemme 1 et l'exercice 1 ici: terrytao.wordpress.com/2010/01/03/… . Il semble qu'il existe une dérivation plus simple reposant sur l'inégalité de Jensen et l'expansion de Taylor. Pourtant, les détails de cela ne sont pas clairs pour moi. Peut-être que quelqu'un peut comprendre cela. (dérivation de (9) à (10) et exercice 1)

Leo

Je ne suis pas sûr d'avoir bien compris votre question. Je vais essayer de répondre: essayez d'écrire en fonction de : this est naturel car vous voulez une borne dans .

- \frac{a}{b - a} e^{t b} + \frac{b}{b - a} e^{t a}

$-\frac{a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta}$

u = t (b - a)

$u = t(b-a)$

e^{\frac{u^{2}}{8}}

$e^{u^2 \over 8}$

Aidé par l'expérience, vous saurez qu'il vaut mieux choisir de l'écrire sous la forme . Alors conduit à avec . $e^{g(u)}$

e^{g (u)} = - \frac{a}{b - a} e^{t b} + \frac{b}{b - a} e^{t a}

$e^{g(u)} = -\frac{a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta}$

\begin{aligned} g (u) & = \log (- \frac{a}{b - a} e^{t b} + \frac{b}{b - a} e^{t a}) \\ = \log (e^{t a} (- \frac{a}{b - a} e^{t (b - a)} + \frac{b}{b - a})) \\ = t a + \log (γ e^{u} + (1 - γ)) \\ = - γ u + \log (γ e^{u} + (1 - γ)), \end{aligned}

$\begin{align*} g(u) &= \log\left( -\frac{a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} \right)\\ &= \log\left( e^{ta} \left( -\frac{a}{b-a} e^{t(b-a)} + \frac{b}{b-a} \right)\right)\\ &= ta + \log\left( \gamma e^u + (1-\gamma) \right)\\ &= -\gamma u + \log\left( \gamma e^u + (1-\gamma) \right),\\ \end{align*}$

γ = - \frac{a}{b - a}

$\gamma = - {a \over b-a}$

Est-ce le genre de chose que vous demandiez?

Edit: quelques commentaires sur la preuve

La première astuce mérite d'être examinée attentivement: si est une fonction convexe, et est une variable aléatoire centrée, alors où est la variable discrète définie par Par conséquent, vous obtenez que est la variable centrée avec support dans qui a la plus grande variance: Notez que si nous fixons une largeur de support $\phi$ $a\le X\le b$ $E (ϕ (X)) \leq - \frac{a}{b - a} ϕ (b) + \frac{b}{b - a} ϕ (a) = E (ϕ (X_{0})),$ $\mathbb{E}(\phi(X)) \le -{a\over b-a} \phi(b) + {b \over b-a} \phi(a) = \mathbb{E}(\phi(X_0)),$ $X_0$ $\begin{aligned} P (X_{0} = a) & = \frac{b}{b - a} \\ P (X_{0} = b) & = - \frac{a}{b - a} . \end{aligned}$ $\begin{align*} \mathbb P(X_0=a) &= {b \over b-a}\\ \mathbb P(X_0=b) &= -{a \over b-a}.\end{align*}$ $X_0$ $[a,b]$ $V a r (X) = E (X^{2}) \leq E (X_{0}^{2}) = \frac{b a^{2} - a b^{2}}{b - a} = - a b .$ $\mathsf{Var} (X) = \mathbb{E}(X^2) \le \mathbb{E}(X_0^2) = {ba^2 - ab^2 \over b-a } = - ab.$ $(b-a)$ , c'est moins que comme Dilip le dit dans les commentaires, c'est parce que ; la borne est atteinte pour . $(b-a)^2\over 4$ $(b-a)^2 + 4ab \ge 0$ $a=-b$
Passons maintenant à notre problème. Pourquoi est-il possible d'obtenir une borne ne dépendant que de ? Intuitivement, il s'agit simplement de redimensionner : si vous avez une borne pour le cas , alors la borne générale peut être obtenu en prenant . Pensez maintenant à l'ensemble des variables centrées avec le support de la largeur 1: il n'y a pas tellement de liberté, donc une borne comme devrait exister. Une autre approche consiste à dire simplement que par le lemme ci-dessus sur , puis plus généralement , qui ne dépend que de et $u = t(b-a)$ $X$ $\mathbb{E}\left( e^{tX} \right) \le s(t)$ $b-a=1$ $s( t(b-a) )$ $s(t)$

$\mathbb{E}(\phi(X))$ $\mathbb{E}(\phi(tX)) \le \mathbb{E}(\phi(tX_0))$ $u$ $\gamma$ : si vous fixez et , et que varient, il n'y a qu'un seul degré de liberté, et , , . On obtient Il vous suffit de trouver une borne impliquant uniquement . $u = u_0 = t_0 (b_0 - a_0)$ $\gamma = \gamma_0 = - {a_0 \over b_0-a_0}$ $t, a, b$ $t = {t_0 \over \alpha}$ $a = \alpha a_0$ $b = \alpha a_0$
$- \frac{a}{b - a} ϕ (t b) + \frac{b}{b - a} ϕ (t a) = - \frac{a_{0}}{b_{0} - a_{0}} ϕ (t b_{0}) + \frac{b_{0}}{b_{0} - a_{0}} ϕ (a_{0}) .$ $-{a\over b-a} \phi(tb) + {b \over b-a} \phi(ta) = -{a_0\over b_0-a_0} \phi(tb_0) + {b_0 \over b_0-a_0} \phi(a_0).$ $u$
Maintenant, nous sommes convaincus que cela peut être fait, cela doit être beaucoup plus facile! Vous ne pensez pas nécessairement à pour commencer. Le fait est que vous devez tout écrire en fonction de et . Notez d'abord que , , et . Puis Maintenant, nous sommes dans le cas particulier ... I pensez que vous pouvez terminer. $g$ $u$ $\gamma$

$\gamma = -{a\over b-a}$ $1 -\gamma = {b\over b-a}$ $at = -\gamma u$ $bt = (1-\gamma)u$
$\begin{aligned} E (ϕ (t X)) \leq & - \frac{a}{b - a} ϕ (t b) + \frac{b}{b - a} ϕ (t a) \\ = & γ ϕ ((1 - γ) u) + (1 - γ) ϕ (- γ u) \end{aligned}$ $\begin{align*} \mathbb{E}(\phi(tX)) \le &-{a\over b-a} \phi(tb) + {b \over b-a} \phi(ta) \\ = & \gamma \phi((1-\gamma)u) + (1-\gamma) \phi(-\gamma u) \end{align*}$

$\phi=\exp$

J'espère que je l'ai clarifié un peu.

Elvis
la source

c'est exactement ce que je cherchais. Merci beaucoup.

Anand

@Anand Je sais que c'est un conseil difficile à suivre, mais je pense que vous ne devriez pas commencer par vous concentrer sur les détails techniques, mais plutôt essayer de comprendre pourquoi une telle limite peut exister ... alors la preuve devrait apparaître plus facilement. J'ai essayé de vous montrer le pourquoi dans la deuxième partie, a ajouté ce matin (vous devez dormir sur une question comme celle-ci - au moins je dois le faire). Je pense que c'est terrible de voir comment ce genre d'intuitions n'apparaît pas dans la plupart des manuels ... même si vous obtenez la partie technique, tant que vous n'avez pas les idées, tout semble magique. Merci à CrossV de m'avoir donné l'occasion de réfléchir à cela en détail!

Elvis

Hou la la! +1 pour l'édition. Merci. Mais ne serait-ce pas bien s'il était possible d'obtenir quelque chose comme

E [e^{t X}] \leq e^{E [t^{2} X^{2} / 2]} = e^{(t^{2} / 2) E [X^{2}]} = e^{(t^{2} / 2) var (X)} \leq e^{t^{2} σ_{max}^{2} / 2} ?

$E[e^{tX}] \leq e^{E[t^2X^2/2]} = e^{(t^2/2)E[X^2]} = e^{(t^2/2)\text{var}(X)} \leq e^{t^2\sigma_{\max}^2/2}?$

Dilip Sarwate

@Elvis Merci pour les conseils et pour avoir pris le temps d'écrire la partie intuitive. J'ai besoin de passer du temps pour comprendre ça!

Anand

@Elvis En ce qui concerne l'intuition, je veux clarifier ma compréhension. Pour obtenir des limites plus nettes, il faut des moments plus élevés. Markov utilise le premier moment, Tchebychev le deuxième moment et Hoeffding utilise mgf. Est-ce correct? Si quelqu'un peut développer et clarifier cette partie, ce serait formidable.

Anand

Comprendre la preuve d'un lemme utilisé dans l'inégalité de Hoeffding

Réponses: