Zrozumienie dowodu lematu stosowanego w nierówności Hoeffdinga

Studiuję notatki do wykładu Larry'ego Wassermana na temat statystyki, w których Casella i Berger są głównym tekstem. Pracuję nad jego notatkami z wykładu, zestawem 2 i utknąłem w wyprowadzaniu lematu stosowanego w nierówności Hoeffdinga (s. 2-3). Powtarzam dowód w uwagach poniżej, a po dowodzie wskażę, gdzie utknąłem.

Lemat

Załóżmy, że i że . Następnie . $\mathbb{E}(X) = 0$ $a \le X \le b$ $\mathbb{E}(e^{tX}) \le e^{t^2 (b-a)^2/8}$

Dowód

Ponieważ , możemy napisać jako wypukłą kombinację i , a mianowicie where . Wypukłość funkcji mamy $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}$

Weź oczekiwania obu stron i użyj faktu aby uzyskać $\mathbb{E}(X) = 0$

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

gdzie , i . Zauważ, że . Również dla wszystkich . $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$

Według twierdzenia Taylora istnieje $\varepsilon \in (0, u)$ taki, że $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}$

Stąd $\mathbb{E}(e^{tX}) \le e^{g(u)} \le e^{\frac{t^2(b-a)^2}{8}}$ .

Mogę śledzić dowód do

$\mathbb{E}(e^{tX}) \le \frac{-a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} = e^{g(u)}$ ale nie jestem w stanie dowiedzieć się, jak uzyskać . $u, g(u), \gamma$

probability probability-inequalities

— Anand
źródło

Interesujące jest to, że maksymalna wartość wynosi a zatem efektem jest efektywnie które wydaje się zbyt znajome, aby wynikać z czystego przypadku. Podejrzewam, że może istnieć inny, być może łatwiejszy, sposób na uzyskanie wyniku za pomocą argumentu probabilistycznego.

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 Rozumiem, że maksymalna wariancja występuje dla jednolitej zmiennej losowej . Wariacją jest . Czy możesz wyjaśnić, skąd masz ?

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

Koncentrując masę na punktach końcowych ...

— Elvis

@DilipSarwate W dowodzie dodałem kilka komentarzy, które mogą wyjaśnić trochę, dlaczego najgorszym przypadkiem jest maksymalna wariancja.

— Elvis

@DilipSarwate - Zobacz lemat 1 i ćwiczenie 1 tutaj: terrytao.wordpress.com/2010/01/03/… . Wydaje się, że istnieje prostsze wyprowadzenie oparte na nierówności Jensena i ekspansji Taylora. Jednak szczegóły tego są dla mnie niejasne. Być może ktoś może to zrozumieć. (wyprowadzenie (9) na (10) i ćwiczenie 1)

— Leo

Nie jestem pewien, czy poprawnie zrozumiałem twoje pytanie. Spróbuję odpowiedzieć: spróbuj napisać w funkcji : this jest naturalne, ponieważ chcesz powiązać w .

- \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}$

Dzięki doświadczeniu dowiesz się , że lepiej jest napisać go w formie . Następnie prowadzi do with . $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}$

Czy o to prosiłeś?

Edycja: kilka komentarzy do dowodu

Na pierwszą sztuczkę zasługuje się uważnie: jeśli jest funkcją wypukłą, a jest wyśrodkowaną zmienną losową, to gdzie jest zmienną dyskretną zdefiniowaną przez W rezultacie otrzymujesz, że jest środkowa zmienna z obsługą w która ma największą wariancję: Pamiętaj, że jeśli naprawimy szerokość podpory $\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)$ , jest to mniej niż jak mówi Dilip w komentarzach, dzieje się tak, ponieważ ; granica jest osiągana dla . $(b-a)^2\over 4$ $(b-a)^2 + 4ab \ge 0$ $a=-b$
Teraz przejdź do naszego problemu. Dlaczego możliwe jest uzyskanie granicy zależnej tylko od ? Intuicyjnie jest to tylko kwestia przeskalowania : jeśli masz ograniczony dla przypadku , to ogólne ograniczenie można uzyskać biorąc . Zastanówmy się teraz nad zestawem zmiennych wyśrodkowanych ze wsparciem szerokości 1: nie ma tak dużo swobody, więc powinna istnieć powiązana wartość . Innym podejściem jest powiedzenie po prostu, że z powyższego lematu na , a bardziej ogólnie , który zależy tylko od i $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$ : jeśli naprawisz i i pozwól że różnią, jest tylko jeden stopień swobody, i , , . Otrzymujemy Po prostu trzeba znaleźć związany z udziałem tylko . $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$
Teraz jesteśmy przekonani, że da się to zrobić, musi być znacznie łatwiej! Nie koniecznie pomyśleć na początku. Chodzi o to, że musisz napisać wszystko jako funkcję i . Najpierw zauważ, że , , and . Następnie Teraz jesteśmy w szczególnym przypadku ... I myślę, że możesz skończyć. $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$

Mam nadzieję, że trochę to wyjaśniłem.

— Elvis
źródło

właśnie tego szukałem. Wielkie dzięki.

— Anand

@I wiem, że trudno jest postępować zgodnie z radami, ale myślę, że nie powinieneś zaczynać od skupienia się na szczegółach technicznych, ale raczej spróbuj dowiedzieć się, dlaczego taka granica może istnieć ... wtedy dowód powinien być łatwiejszy. Próbowałem pokazać, dlaczego w drugiej części, dodałem dziś rano (musisz spać na takie pytanie - przynajmniej muszę). Myślę, że to okropne, że tego rodzaju intuicje nie pojawiają się w większości podręczników ... nawet jeśli dostaniesz część techniczną, dopóki nie masz pomysłów, wszystko wygląda magicznie. Dziękuję i CrossV za umożliwienie mi przemyślenia tego szczegółowo!

— Elvis

Łał! +1 za edycję. Dzięki. Ale czy nie byłoby miło, gdyby można było uzyskać coś takiego jak

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 Dziękujemy za radę i czas poświęcony na zapisanie części intuicyjnej. Muszę poświęcić trochę czasu, aby to zrozumieć!

— Anand

@ Elvis Biorąc pod uwagę intuicję, chcę wyjaśnić swoje rozumienie. Aby uzyskać ostrzejsze granice, potrzeba dłuższych chwil. Markow używa pierwszej chwili, Czebiszew drugiej, a Hoeffding używa mgf. Czy to jest poprawne? Gdyby ktoś mógł rozwinąć i wyjaśnić tę część, byłoby świetnie.

— Anand