Ogranicza się do

Jeśli jest funkcją wypukłą, to nierówność Jensena stwierdza, że i mutatis mutandis, gdy jest wklęsłe. Oczywiście w najgorszym przypadku nie można górnej granicy w kategoriach dla wypukłego , ale czy istnieje granica, która idzie w tym kierunku, jeśli jest wypukły, ale „niezbyt wypukły”? Czy istnieje jakieś standardowe ograniczenie, które określa warunki dla funkcji wypukłej (i ewentualnie także rozkład, jeśli to konieczne), które pozwoliłyby wyciągnąć wniosek, że , gdzie $f$ $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$ $f$ $\textbf{E}[f(x)]$ $f(\textbf{E}[x])$ $f$ $f$ $f$ $\textbf{E}[f(x)] \le \varphi(f)f(\textbf{E}[x])$ $\varphi(f)$ jest jakąś funkcją krzywizny / stopnia wypukłości ? Może coś podobnego do stanu Lipschitza? $f$

randomness pr.probability randomized-algorithms

— Ian
źródło

Głosowanie na zakończenie jest nie na temat. math.stackexchange.com może?

— Aryabhata

Myślę, że to pytanie powinno pozostać otwarte; jest to rodzaj nierówności, który wielu pracujących teoretyków uznałby za użyteczne regularnie.

— Aaron Roth

Wiem, że jest to bliższe czystej matematyce niż większości zadanych do tej pory pytań, ale argumentowałbym, że jest to temat, ponieważ takie rzeczy często pojawiają się w analizie algorytmów losowych (która jest aplikacją, w której mam umysł). Myślę, że matematyka, która jest szeroko stosowana w informatyce, powinna być uważana za uczciwą grę w pytania.

— Ian

głosuj, aby pozostać otwartym. zdecydowanie na temat

— Suresh Venkat

Głosuję również, aby pozostać otwartym.

— Jeffε

EDYCJA: w oryginalnej wersji brakowało wartości bezwzględnej. Przepraszam!!

Cześć Ian. Pokrótce przedstawię dwie przykładowe nierówności, jedną przy użyciu wiązania Lipschitza, drugą przy użyciu wiązania na drugiej pochodnej, a następnie omówię pewne trudności w tym problemie. Chociaż jestem zbędny, ponieważ podejście wykorzystujące jedną pochodną wyjaśnia, co dzieje się z większą liczbą pochodnych (przez Taylora), okazuje się, że druga wersja pochodnej jest całkiem niezła.

Po pierwsze, związane z Lipschitzem: po prostu przerób standardową nierówność Jensena. Ta sama sztuczka dotyczy: oblicz ekspansję Taylora na oczekiwanej wartości.

W szczególności Niech ma odpowiednią miarę i ustaw . Jeśli ma stałą Lipschitza , to według twierdzenia Taylora $X$ $\mu$ $m := \textrm E(x)$ $f$ $L$

f (x) = f (m) + f^{'} (z) (x - m) \leq f (m) + L | x - m |,

$f(x) = f(m) + f'(z)(x-m) \leq f(m) + L|x-m|,$

gdzie (Uwaga: i jest możliwe). Używając tego i ponownie pracując nad dowodem Jensena (jestem paranoikiem i sprawdziłem, czy ten standardowy rzeczywiście jest na wikipedii), $z \in [m, x]$ $x\leq m$ $x> m$

\begin{aligned} E (f (X)) & = \int f (x) d μ (x) \leq f (m) \int d μ (x) + L \int | x - m | d μ (x) \\ = f (E (X)) + L E (| X - E (X) |) . \end{aligned}

$\begin{align} \operatorname{E}(f(X)) & = \int f(x) \, d\mu(x) \leq f(m) \int d\mu(x) + L\int |x-m| \, d\mu(x) \\[6pt] & = f(\operatorname{E}(X)) + L \operatorname{E} (|X-\operatorname{E}(X)|). \end{align}$

Załóżmy teraz . W tym przypadku, $|f''(x)| \leq \lambda$

\begin{aligned} f (x) & = f (m) + f^{'} (m) (x - m) + f^{″} (z) \frac{(x - m)^{2}}{2} \\ \leq f (m) + f^{'} (m) (x - m) + λ \frac{(x - m)^{2}}{2}, \end{aligned}

$\begin{align} f(x) & = f(m) + f'(m)(x-m) + f''(z) \frac{(x-m)^2} 2 \\[6pt] & \leq f(m) + f'(m)(x-m) + \lambda \frac{(x-m)^2} 2, \end{align}$

a więc

\begin{aligned} E (f (X)) & \leq f (m) + f^{'} (m) (E (X) - m) + \frac{λ E ((X - m)^{2})}{2} \\ = f (E (X)) + \frac{λ Var (X)}{2} . \end{aligned}

$\begin{align} \operatorname{E}(f(X)) & \leq f(m) + f'(m)(\operatorname{E}(X) - m) + \frac {\lambda \operatorname{E}((X-m)^2)}{2} \\[6pt] & = f(\operatorname{E}(X)) + \frac {\lambda \operatorname{Var}(X)}2. \end{align}$

Chciałbym krótko wspomnieć o kilku rzeczach. Przepraszam, jeśli są oczywiste.

Jest to, że nie można po prostu powiedzenia „wlog ” przez przesuwanie rozkładu, ponieważ zmienia się zależność między i . $\operatorname{E}(X) = 0$ $f$ $\mu$

Następnie granica musi w jakiś sposób zależeć od dystrybucji. W tym celu patrz wyobrazić, że i . Niezależnie od wartości , nadal otrzymujesz . Z drugiej strony . Tak więc, zmieniając , możesz uczynić odstęp między dwiema wielkościami dowolnymi! Intuicyjnie większa masa jest wypychana ze średniej, a zatem dla każdej ściśle wypukłej funkcji nazwa wzrośnie. $X \sim \textrm{Gaussian}(0, \sigma^2)$ $f(x) = x^2$ $\sigma$ $f(\operatorname{E}(X)) = f(0) = 0$ $\operatorname{E}(f(X)) = \operatorname{E}(X^2) = \sigma^2$ $\sigma$ $\operatorname{E} (f(X))$

Wreszcie nie widzę, jak uzyskać mnożenie, jak sugerujesz. Wszystko, czego użyłem w tym poście, jest standardowe: twierdzenie Taylora i granice pochodnych są chlebem i masłem w granicach statystyki i automatycznie dają błędy addytywne, a nie mnożące.

Zastanowię się jednak i opublikuję coś. Nieokreślona intuicja mówi, że będzie wymagała bardzo uciążliwych warunków zarówno dla funkcji, jak i rozkładu, i że granica addytywna jest w istocie jej sednem.

— matus
źródło

Za każdym razem, gdy edytuję, odpowiedź jest podbijana. Zwrócę więc uwagę: druga granica pochodnej jest ścisła w podanym przykładzie.

— matus

Myślę, że masz rację, że granice addytywne są najlepsze z możliwych bez znacznie silniejszych warunków dla funkcji.

— Ian

Drogi łanie, myślałem o tym problemie nieco bardziej, ale główną trudność w moim umyśle daje przykład, który podałem, gdzie

, ale

. Możesz ograniczyć zarówno rodzinę funkcji (ograniczone, pochodne ograniczone, całkowalne), jak i rozkład (gładkie, ograniczone, ograniczone momenty) i nadal masz te przykłady. Wystarczy mieć symetryczną, nieujemną funkcję równą zero przy średniej rozkładu. To powiedziawszy, wszystko zależy od ograniczeń Twojego dokładnego problemu. W ogólnym przypadku myślę, że charakter addytywny jest fundamentalny.

f (E (X)) = 0

$f(\textrm E(X))= 0$

E (f (X)) > 0

$\textrm E (f(X)) > 0$

— matus

@Ian: Dowody nierówności Chernoffa i Azumy-Hoeffdinga wykorzystują argumenty przypominające to, więc możesz przeczytać je dla inspiracji. Patrz np. Książka Mitzenmachera i Upfala na temat randomizacji w informatyce.

— Warren Schudy,

Aby uzyskać wgląd, rozważ rozkład skoncentrowany na dwóch wartościach; powiedzmy, z jednakowymi prawdopodobieństwami 1/2, że wynosi 1 lub 3, skąd . Take i . Rozważ funkcje dla których i . Robiąc $\textbf{E}[x] = 2$ $N >> 0$ $\epsilon > 0$ $f$ $f(1) = f(3)= N\epsilon$ $f(\textbf{E}[x]) = f(2) = \epsilon$ wystarczająco małe iciągłełączenie pomiędzy tymi trzema punktami możemy sprawić, że krzywizna tak mała, jak to pożądane. Następnie $\epsilon$ $f$ $f$

jeszcze $\textbf{E}[f(x)] = N\epsilon$

. $N = N\epsilon / \epsilon = \textbf{E}[f(x)] / f(\textbf{E}[x]) \le \varphi(f)$

To pokazuje, że musi być dowolnie duże. $\varphi(f)$

— whuber
źródło