Nierówność McDiarmida

W teorii prawdopodobieństwa i informatyce teoretycznej nierówność McDiarmida jest nierównością koncentracji , która ogranicza odchylenie między próbkowaną wartością a oczekiwaną wartością pewnych funkcji, gdy są one oceniane na podstawie niezależnych zmiennych losowych . Nierówność McDiarmida dotyczy funkcji spełniających ograniczone różnice właściwość, co oznacza, że zastąpienie pojedynczego argumentu funkcji, przy pozostawieniu wszystkich pozostałych argumentów bez zmian, nie może spowodować zbyt dużej zmiany wartości funkcji.

Oświadczenie

Funkcja ${\ Displaystyle f: {\ mathcal {X}} _ {1} \ razy {\ mathcal {X}} _ {2} \ razy \ cdots \ razy {\ mathcal {X}} _ {n} \ rightarrow \ mathbb {R}}$ spełnia właściwość ograniczonych różnic , jeśli zastępuje się wartość współrzędnej ${\ displaystyle i}$ zmienia się ${\ displaystyle x_ {i}}$ wartość co najwyżej o ${\ displaystyle f}$ ${\ displaystyle c_ {i}}$ . $Displaystyle i\w [n]}$ $n$ istnieją dla , i wszystkie ${\ Displaystyle x_ {1} \ w {\ mathcal {X}} _ {1}, \, x_ {2} \ w {\ mathcal {X}} _ {2}, \, \ ldots, \, x_ { n}\w {\mathcal {X}}_{n}}$ ,

{\ Displaystyle \ sup _ {x_ {i} '\ w {\ mathcal {X}} _ {i}} \ lewo | f (x_ {1}, \ kropki, x_ {i-1}, x_ {i} ,x_{i+1},\ldots ,x_{n})-f(x_{1},\dots ,x_{i-1},x_{i}',x_{i+1},\ldots , x_{n})\prawo|\równoważnik c_{i}.}

Nierówność McDiarmida - Niech ${\ Displaystyle f: {\ mathcal {X}} _ {1} \ razy {\ mathcal {X}} _ {2} \ razy \ cdots \times {\ mathcal {X}} _ {n} \ rightarrow \ mathbb {R}}$ spełniają właściwość ograniczonych różnic z granicami ${\ Displaystyle c_ {1}, c_ {2 },\kropki ,c_{n}}$ .

${\ mathcal {X}} _ {i}}$ niezależne gdzie $i$ $Displaystyle$ dla wszystkich ${\ displaystyle i}$ . Następnie, dla dowolnego , ${\ displaystyle \ varepsilon > 0$ }

{\ Displaystyle {\ tekst {P}} \ lewo (f (X_ {1}, X_ {2}, \ ldots, X_ {n}) - \ mathbb {E} [f (X_ {1}, X_ {2} },\ldots,X_{n})]\geq \varepsilon \right)\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n }c_{i}^{2}}}\right),}

\ Displaystyle {\ tekst {P}} (f (X_ {1}, X_ {2}, \ ldots, X_ {n}) - \ mathbb {E} [f(X_{1},X_{2},\ldots,X_{n})]\leq -\varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2 }}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}

i jako bezpośrednia konsekwencja

{\ Displaystyle {\ tekst {P}} (| f (X_ {1}, X_ {2}, \ ldots, X_ {n}) - \ mathbb {E} [f (X_ {1}, X_ {2} ,\ldots ,X_{n})]|\geq \varepsilon )\równoważnik 2\exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n} c_{i}^{2}}}\prawo).}

Rozszerzenia

Rozkłady niezrównoważone

Silniejsze ograniczenie można podać, gdy argumenty funkcji są próbkowane z niezrównoważonych rozkładów, tak że ponowne próbkowanie pojedynczego argumentu rzadko powoduje dużą zmianę wartości funkcji.

Nierówność McDiarmida (niezrównoważona) - Niech właściwość ograniczonych różnic spełnia granice ${\ Displaystyle c_ {1}, c_ {2}, \ kropki, c_ {n}}$ ${\ Displaystyle f: {\ mathcal {X}} ^ {n} \ rightarrow \ mathbb {R}$ .

Rozważ niezależne zmienne losowe ${\ Displaystyle X_ {1}, X_ {2}, \ ldots, X_ {n} \ in {\ mathcal {X}}}$ narysowane z rozkładu gdzie istnieje określona wartość , która występuje z prawdopodobieństwem $}$ $\ chi _ {0} \ in {\ mathcal {X$ . Następnie, dla dowolnego , ${\ displaystyle \ varepsilon > 0$ }

{\ Displaystyle {\ tekst {P}} (| f (X_ {1}, \ ldots, X_ {n}) - \ mathbb {E} [f (X_ {1}, \ ldots, X_ {n})] |\geq \varepsilon )\równoważnik 2\exp \left({\frac {-\varepsilon ^{2}}{2p(2-p)\sum _{i=1}^{n}c_{i}^ {2}+{\frac {2}{3}}\varepsilon \max _{i}c_{i}}}\right).}

Można to wykorzystać na przykład do scharakteryzowania wartości funkcji na wykresach , gdy są one oceniane na rzadkich losowych wykresach i hipergrafach , ponieważ na rzadkim grafie losowym jest znacznie bardziej prawdopodobne, że brakuje jakiejkolwiek określonej krawędzi niż jest obecna.

Różnice ograniczone dużym prawdopodobieństwem

Nierówność McDiarmida można rozszerzyć na przypadek, w którym analizowana funkcja nie spełnia ściśle własności różnic ograniczonych, ale duże różnice pozostają bardzo rzadkie.

Nierówność McDiarmida (różnice ograniczone z dużym prawdopodobieństwem) - Niech ${\ Displaystyle f: {\ mathcal {X}} _ {1} \ razy {\ mathcal {X}} _{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } będzie$ funkcją i ${\ Displaystyle {\ mathcal {Y}} \ subseteq {\ mathcal {X}} _ {1} \ razy {\ mathcal {X}} _ {2} \ razy \ cdots \ razy {\ mathcal {X}} _ {n}}$ będzie podzbiorem jego dziedziny i niech do ${\ Displaystyle c_ {1}, c_ {2}, \ kropki, c_ {n} \ geq 0}$ stałymi takimi że dla wszystkich par ${\ Displaystyle (x_ {1}, \ ldots, x_ {n}) \ in {\ mathcal {Y}}}$ i ${\ Displaystyle (x'_ {1}, \ ldots, x'_ {n}) \ w {\ mathcal {Y}}}$ ,

{\ Displaystyle \ lewo | f (x_ {1}, \ ldots, x_ {n}) - f (x'_ {1}, \ ldots, x'_ {n}) \ prawo | \ równoważnik \ suma _ { i:x_{i}\neq x'_{i}}c_{i}.}

${\ mathcal {X}} _ {i}}$ niezależne gdzie $i$ $Displaystyle$ dla wszystkich ${\ displaystyle i}$ . Niech ${\ Displaystyle p = 1-\ operatorname {P} ((X_ {1}, \ ldots, X_ {n}) \ in {\ mathcal {Y}})} i$ niech ${\ Displaystyle m = \ mathbb {E} [f (X_ {1}, \ ldots, X_ {n}) \ mid (X_ {1} ,\ldots ,X_{n})\w {\mathcal {Y}}]}$ . Następnie, dla dowolnego , ${\ displaystyle \ varepsilon > 0$ }

{\ Displaystyle {\ text {P}} \ lewo (f (X_ {1}, \ ldots, X_ {n}) -m \ geq \ varepsilon \ prawej) \ równoważnik p + \ exp \ lewo (- {\ frac { 2\max \left(0,\varepsilon -p\sum _{i=1}^{n}c_{i}\right)^{2}}{\sum _{i=1}^{n}c_ {i}^{2}}}\prawo),}

i jako bezpośrednia konsekwencja

{\ Displaystyle {\ tekst {P}} (| f (X_ {1}, \ ldots, X_ {n}) - m | \ geq \ varepsilon ) \ równoważnik 2 p + 2 \ exp \ lewo (- {\ Frac {2 \ max \ lewo (0, \ varepsilon - p \ suma _ {i = 1} ^ {n} c_ {i} \ prawo) ^ {2}} {\ suma _ {i = 1} ^ {n} c_{i}^{2}}}\prawo).}

Istnieją silniejsze udoskonalenia tej analizy w niektórych scenariuszach zależnych od dystrybucji, takich jak te, które pojawiają się w teorii uczenia się .

Normy subgaussowskie i subwykładnicze

Niech ${\$ ta wyśrodkowana warunkowa wersja funkcji będzie $k}$

{\ Displaystyle f_ {k} (X) (x): = f (x_ {1}, \ ldots, x_ {k-1}, X_ {k}, x_{k+1},\ldots ,x_{n})-\mathbb {E} _{X'_{k}}f(x_{1},\ldots ,x_{k-1},X'_ {k},x_{k+1},\ldkropki,x_{n}),}

więc ${\ Displaystyle f_ {k} (X)}$ jest zmienną losową zależną od losowych wartości ${\ Displaystyle x_ {1},\ldots,x_{k-1},x_{k+1},\ldots,x_{n}}$ .

Nierówność McDiarmida (norma subgaussowska) - Niech ${\ Displaystyle f: {\ mathcal {X}} _ {1} \ razy {\ mathcal {X}} _ {2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} }$ będzie funkcją. Rozważ niezależne zmienne losowe ${\ Displaystyle X = (X_ {1}, X_ {2}, \ kropki, X_ {n})}$ gdzie ${\ Displaystyle X_ {i} \ w {\ mathcal {X}} _ {i }}$ dla wszystkich ${\ displaystyle i}$ .

Niech odnosi się do wyśrodkowanej warunkowej wersji $\ Displaystyle$ $k} (X)$ $}$ . Niech $_$ . _ _

Następnie, dla dowolnego , ${\ displaystyle \ varepsilon > 0$ }

{\ Displaystyle {\ tekst {P}} \ lewo (f (X_ {1}, \ ldots, X_ {n}) -m \ geq \ varepsilon \ prawej) \ równoważnik \ exp \ lewo ({\ frac {- \ varepsilon ^{2}}{32e\left\|\suma _{k\in [n]}\|f_{k}(X)\|_{\psi _{2}}^{2}\right\ |_{\infty}}}\prawo).}

Nierówność McDiarmida (norma podwykładnicza) - Niech ${\ Displaystyle f: {\ mathcal {X}} _ {1} \ razy {\ mathcal {X}} _ {2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} }$ będzie funkcją. Rozważ niezależne zmienne losowe ${\ Displaystyle X = (X_ {1}, X_ {2}, \ kropki, X_ {n})}$ gdzie ${\ Displaystyle X_ {i} \ w {\ mathcal {X}} _ {i }}$ dla wszystkich ${\ displaystyle i}$ .

Niech odnosi się do wyśrodkowanej warunkowej wersji $\ Displaystyle$ $k} (X)$ $}$ . Niech $_$ .

Następnie dla dowolnego , ${\ displaystyle \ varepsilon > 0$ }

{\ Displaystyle {\ text {P}} \ lewo (f (X_ {1}, \ ldots, X_ {n}) -m \ geq \ varepsilon \ prawej) \ równoważnik \ exp \ lewo ({\ Frac {- \ varepsilon ^ {2}} {4e ^ {2} \ lewo \ | \ suma _ {k \ in [n]} \ | f_ {k} (X) \ | _ {\ psi _ {1}} ^ {2}\right\|_{\infty }+2\varepsilon e\max _{k\in [n]}\left\|\|f_{k}(X)\|_{\psi _{1}}\right\|_{\infty }}}\right).}

Formy Bennetta i Bernsteina

Udoskonalenia nierówności McDiarmida w stylu nierówności Bennetta i nierówności Bernsteina są możliwe dzięki zdefiniowaniu terminu wariancji dla każdego argumentu funkcji. Pozwalać

{\ Displaystyle {\ rozpocząć {wyrównane} B &: = \ max _ {k \ w [n]} \ sup _ {x_ {1}, \ kropki, x_ {k-1}, x_ {k + 1}, \ kropki, x_ {n}} \ lewo | f (x_ {1}, \ kropki, x_ {k-1}, X_ {k}, x_ {k + 1}, \ kropki, x _{n})-\mathbb {E} _{X_{k}}f(x_{1},\kropki ,x_{k-1},X_{k},x_{k+1},\kropki ,x_{n})\right|,\\V_{k}&:=\sup _{x_{1},\kropki ,x_{k-1},x_{k+1},\kropki ,x_{n}}\mathbb {E} _{X_{k}}\left(f(x_{1},\kropki ,x_{k-1},X_{k},x_{k+1},\kropki ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\kropki ,x_{k-1},X_{k},x_{ k+1},\kropki ,x_{n})\right)^{2},\\{\tylda {\sigma }}^{2}&:=\sum _{k=1}^{n}V_{k}.\end{wyrównane}}}

Nierówność McDiarmida (forma Bennetta) - Niech właściwość różnic ograniczonych spełnia granice ${\ Displaystyle c_ {1}, c_ {2}, \ kropki, c_ {n}}$ ${\ Displaystyle f: {\ mathcal {X}} ^ {n} \ rightarrow \ mathbb {R}$ . Rozważ niezależne zmienne losowe ${\ Displaystyle X_ {1}, X_ {2}, \ kropki, X_ {n}}$ gdzie ${\ Displaystyle X_ {i} \ w {\ mathcal {X}} _ {i}}$ dla wszystkich ${\ displaystyle i}$ . Niech $tej$ będą $.$ na początku

Następnie, dla dowolnego , ${\ displaystyle \ varepsilon > 0$ }

{\ Displaystyle {\ tekst {P}} (f (X_ {1}, \ ldots, X_ {n}) - \ mathbb {E} [f (X_ {1}, \ ldots, X_ {n})] \ geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon }{2B}}\log \left(1+{\frac {B\varepsilon}}{{\tilde {\sigma}}^{2 }}}\prawo)\prawo).}

${\ Displaystyle c_ {1}, c_ {2}, \ kropki, c_ {n}}$ McDiarmida (forma $c$ Niech właściwość granice . Niech ${\ Displaystyle B}$ i ${\ Displaystyle {\ tylda {\ sigma}} ^ {2}}$ być zdefiniowane jak na początku tej sekcji.

Następnie dla dowolnego , ${\ displaystyle \ varepsilon > 0$ }

{\ Displaystyle {\ tekst {P}} (f (X_ {1}, \ ldots, X_ {n}) - \ mathbb {E} [f (X_ {1}, \ ldots, X_ {n})] \ geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon ^{2}}{2\left({\tylda {\sigma}}^{2}+{\frac {B\varepsilon}}{ 3}}\prawo)}}\prawo).}

Dowód

Poniższy dowód nierówności McDiarmida konstruuje martyngał Dooba śledzący warunkową wartość oczekiwaną funkcji w miarę próbkowania i warunkowania coraz większej liczby jej argumentów, a następnie stosuje nierówność koncentracji martyngału ( nierówność Azumy ). Istnieje również alternatywny argument unikający używania martyngałów, wykorzystujący niezależność argumentów funkcji, aby zapewnić podobny do Chernoffa .

Dla lepszej czytelności wprowadzimy skrót notacyjny: ${\ Displaystyle Z_ {i \ rightharpoondown j}}$ $i$ oznaczać ${\ Displaystyle z_ {i}, \ kropki, z_ {j}}$ liczb całkowitych $\ Displaystyle 1 \ równoważnik i \ równoważnik j \ równoważnik n}$ tak że na przykład

{\ Displaystyle f (X_ {1 \ rightharpoondown (i-1)}, y, x_ {(i + 1) \ rightharpoondown n}): = f (X_ {1}, \ ldots, X_ {i-1}, y,x_{i+1},\ldkropki,x_{n}).}

Wybierz dowolny ${\ Displaystyle x_ {1} ', x_ {2} ', \ ldots, x_ {n}'}$ . Następnie dla dowolnego ${\ Displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$ przez nierówność trójkąta ,

{\ Displaystyle {\ rozpocząć {wyrównane} & | f (x_ {1 \ rightharpoondown n}) - f (x'_ {1 \ rightharpoondown n}) |\\ [6pt] \ równoważnik {} & | f (x_ { 1\rightharpoondown \,n})-f(x'_{1\rightharpoondown (n-1)},x_{n})|+c_{n}\\\leq {}&|f(x_{1\ rightharpoondown n})-f(x'_{1\rightharpoondown (n-2)},x_{(n-1)\rightharpoondown n})|+c_{n-1}+c_{n}\\\leq {}&\ldots \\\leq {}&\sum _{i=1}^{n}c_{i},\end{wyrównane}}}

a zatem $ograniczony$ .

Ponieważ $}$ $($ martyngał Dooba każdy $zmienną$ losową zależną od losowej zmiennej wartości ${\ Displaystyle X_ {1}, \ ldots, X_ {i}} )$ jako

{\ Displaystyle Z_ {i}: = \ mathbb {E} [f (X_ {1 \ rightharpoondown n}) \ mid X_ {1 \ rightharpoondown i}]}

ja ${\ Displaystyle i \ geq 1}$ i ${\ Displaystyle Z_ {0}: = \ mathbb {E} [f (X_ {1 \ rightharpoondown$ , tak że ${\ Displaystyle Z_ {n} = f (X_ {1 \ rightharpoondown n})}$ .

Teraz zdefiniuj zmienne losowe dla każdego ${\ displaystyle i}$

{\ Displaystyle {\ rozpocząć {wyrównane} U_ {i} &: = \ sup _ {x \ w {\ mathcal {X}} _ {i}} \ mathbb {E} [f (X_ {1 \ rightharpoondown (i -1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{ 1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&:=\inf _{x\in { \mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1 \rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\ rightharpoondown (i-1)}].\\\end{aligned}}}

Ponieważ ${\ Displaystyle X_ {i}, \ ldots, X_ {n}}$ są od siebie niezależne, warunkowanie na ${\ displaystyle X_ {i} = x}$ nie wpływa na X ja = x prawdopodobieństw innych zmiennych, więc są one równe wyrażeniom

{\ Displaystyle {\ rozpocząć {wyrównane} U_ {i} & = \ sup _ {x \ w {\ mathcal {X}} _ {i}} \ mathbb {E} [f (X_ {1 \ rightharpoondown (i- 1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i -1)}],\\L_{i}&=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1 )},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i- 1)}].\\\end{wyrównane}}}

Zauważ, że ${\ Displaystyle L_ {i} \ równoważnik Z_ {i} -Z_ {i-1} \ równoważnik U_ {i}}$ . Ponadto,

{\ Displaystyle {\ rozpocząć {wyrównane} U_ {i} -L_ {i} & = \ sup _ {u \ w {\ mathcal {X}} _ {i}, \ ell \ w {\ mathcal {X}} _{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1 )}]-\mathbb {E} [f(X_{1\rightharpoondown (i-1)},\ell ,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1 )}]\\[6pt]&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},l,X_{(i +1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\&\leq \sup _{x_{u}\in {\mathcal {X}}_{i},x_ {l}\in {\mathcal {X}}_{i}}\mathbb {E} [c_{i}\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&\leq c_ {i}\end{wyrównane}}}

Następnie, stosując ogólną postać nierówności Azumy do , mamy ${\ Displaystyle \ lewo \ {Z_ {i} \ prawo \}}$

{\ Displaystyle {\ tekst {P}} (f (X_ {1}, \ ldots, X_ {n}) - \ mathbb {E} [f (X_ {1}, \ ldots, X_ {n})] \ geq \varepsilon )=\operatorname {P} (Z_{n}-Z_{0}\geq \varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{ i=1}^{n}c_{i}^{2}}}\prawo).}

Jednostronne ograniczenie w drugim kierunku uzyskuje się przez zastosowanie nierówności Azumy do ${\ Displaystyle \ lewo \ {-Z_ {i} \ prawo \}},$ a dwustronne ograniczenie wynika z ograniczenia łączącego . ${\ Displaystyle \ kwadrat}$

Zobacz też