UA MATH567 高維統計IV Lipschitz組合3 高斯分布的Lipschitz函數

首先我們在歐氏空間$({\mathbb{R}}^n,\mathcal{B}({\mathbb{R}}^n))$上建立高斯概率測度${\gamma }_n$，滿足$?B\in \mathcal{B}({\mathbb{R}}^n)$，
$${\gamma }_n(B)={\int }_B\frac{1}{(2\pi {)}^{n/2}}{e}^{?\frac{{\Vert x\Vert }_2^2}{2}}dx$$

則$({\mathbb{R}}^n,\mathcal{B}({\mathbb{R}}^n),{\gamma }_n)$成為一個概率空間。

Gaussian Isoperimetric不等式 $??>0$，$\underset{A\in \mathcal{B}({\mathbb{R}}^n)}{\mathrm{argmin}}{\gamma }_n(A_{?})$是一個half space。這里半空間指的是
$$\{x=(x_1,?,x_n)\in {\mathbb{R}}^n:?i\in \{1,?,n\},x_i\le c,c\in \mathbb{R}\}$$

并且如果${\gamma }_n(A)\ge 1/2$，則$\gamma (A_t)\ge 1?e^{?c{t}^2},?c>0$。

證明
我們簡單討論一下并且之后的一段。

用$H$表示一個半空間：
$$\{x=(x_1,?,x_n)\in {\mathbb{R}}^n:x_1\le 0\}$$

則${\gamma }_n(H)=1/2$，于是
$${\gamma }_n(H_t)=P(X\in H_t)=P(X_1\le t)\ge 1?e^{?t^2/2}$$

這是標準正態分布的tail bound。如果${\gamma }_n(A)\ge 1/2$，顯然
$$\gamma (A_t)\ge \gamma (H_t)\ge 1?e^{?t^2/2}$$

---

Gaussian concentration不等式
$X～N(0,I_n)$，$f:{\mathbb{R}}^n\to \mathbb{R}$是一個Lipschitz函數，則
$${\Vert f(X)?Ef(X)\Vert }_{{\psi }_2}\le C{\Vert f\Vert }_{Lip}$$

證明
這個不等式的證明技術與上一講的球面分布的Lipschitz函數一樣，先說明$f(X)?M$是亞高斯的，然后用centering技巧得到結論。假設${\Vert f\Vert }_{Lip}=1$，不然我們總是可以分析$f/{\Vert f\Vert }_{Lip}$，

第一步：$f(X)?M$是亞高斯的，其中$M$是$f(X)$的中位數，也就是
$$P(f(X)\ge M)\ge 1/2,P(f(X)\le M)\ge 1/2$$

定義
$$A=\{x\in {\mathbb{R}}^n:f(x)\le M\}$$

則
$$\sigma (A)=P(X\in A)=P(f(X)\le M)\ge 1/2$$

根據Gaussian Isoperimetric不等式，
$${\gamma }_n(A_t)\ge 1?e^{?t^2/2}$$

因為$x\in A_t$說明$?y\in A$, ${\Vert x?y\Vert }_2\le t$，根據Lipschitz函數的定義：
$$f(x)?f(y)\le {\Vert f\Vert }_{Lip}{\Vert x?y\Vert }_2\le t$$

$y\in A$說明$f(y)\le M$，所以
$$f(x)\le f(y)+t\le M+t$$

因此

$$P(f(X)?M\le t)\ge P(X\in A_t)=\sigma (A_t)\ge 1?e^{?t^2/2}$$

類似地，對于$f(X)?M\ge ?t$，我們有
$$P(f(X)?M\ge ?t)\ge 1?e^{?t^2/2}$$

所以
$$P(|f(X)?M|\ge t)\le 2e^{?t^2/2}$$

第二步：使用centering技巧，假設$X$是亞高斯隨機變量，則$X?EX$也是亞高斯隨機變量，并且存在常數$C$使得
$${\Vert X?EX\Vert }_{{\psi }_2}\le C{\Vert X\Vert }_{{\psi }_2}$$

因為$f(X)?M$是亞高斯的，于是$f(X)?M?E[f(X)?M]=f(X)?Ef(X)$也是亞高斯的，證畢。

總結

以上是生活随笔為你收集整理的UA MATH567 高维统计IV Lipschitz组合3 高斯分布的Lipschitz函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。