UA MATH567 高維統計IV Lipschitz組合2 Spherical Distribution的Lipschitz函數

這一講我們先介紹最簡單的高維分布，也就是球面分布的Lipschitz函數的concentration。

我們在上上部分隨機向量第三講介紹過這個分布，$X～Unif(\sqrt{n}{S}^{n?1})$，其中$S^{n?1}$表示$n$維空間中的單位球面，這個符號說明$X$在半徑在$\sqrt{n}$的球面上服從均勻分布，它是零均值各向同性的，并且當$n$足夠大時，$N(0,I_n)\approx Unif(\sqrt{n}{S}^{n?1})$。

定理 球面分布的Lipschitz函數是亞高斯的
$X～Unif(\sqrt{n}{S}^{n?1})$，$f:\sqrt{n}{S}^{n?1}\to \mathbb{R}$是Lipschitz函數，則$?C>0$
$${\Vert f(X)?Ef(X)\Vert }_{{\psi }_2}\le C{\Vert f\Vert }_{Lip}$$

其中${\Vert f\Vert }_{Lip}$是$f$的Lipschitz范數。

評注
根據亞高斯性，$?c>0$
$$P(|f(X)?Ef(X)|\ge t)\le 2e^{?c{t}^2/{\Vert f\Vert }_{Lip}^2}$$

與前兩部分的結論相比，這個結果說明隨機向量的Lipschitz函數具有與線性函數類似的concentration property。

這個定理的證明有一點點復雜，需要用到一些其他的結果，這里先介紹一下要用到的結論：

Isoperimetric不等式1 歐氏空間中，給定體積則表面積最小的一定是球體，基于這個觀察我們有：
$$A_{?}=\{x\in {\mathbb{R}}^n:?y\in A,{\Vert x?y\Vert }_2\le ?\}=A+?B_2^n$$

第二個等號后的$B_2^n$表示$n$維單位球，$+$表示Minkowski和，這個結論看似顯然但證明復雜，所以這里不展示。

Isoperimetric不等式2 球面上封閉曲線圍成的面積一定時，封閉曲線為圓形需要的長度最短，基于這個觀察我們有：
$$A_{?}=\{x\in S^{n?1}:?y\in A,{\Vert x?y\Vert }_2\le ?\}$$

則$A_{?}$是$S^{n?1}$與過球心的某個圓錐的交集，進一步地，如果定義$\sigma$為normalized area，使得$?A?S^{n?1},\sigma (A)$表示將球面縮放為$S^{n?1}$后，$A$對應的面積，如果$\sigma (A)\ge 1/2$，則
$$\sigma (A_{?})\ge 1?e^{?c{?}^2},?c>0$$

證明
用$H$表示下半球面：
$$H=\{x=(x_1,?,x_n)\in \sqrt{n}{S}^{n?1}:x_1\le 0\}$$

根據$\sigma$的定義，$\sigma (H)=1/2$，引入隨機向量$X～Unif(\sqrt{n}{S}^{n?1})$，于是
$$\begin{gathered} \sigma (H_{?})=P(X\in H_{?})\ge P(X\in \sqrt{n}{S}^{n?1}\cap \{x_1\le ?/\sqrt{2}\}) \\ =P(X_1\le ?/\sqrt{2})\ge 1?e^{?c{?}^2},?c>0 \end{gathered}$$

因為$X_1$是亞高斯的。因為$\sigma (A)\ge 1/2$，于是$$\sigma (A_{?})\ge \sigma (H_{?})\ge 1?e^{?c{?}^2}$$

說明
$$H_{?}=\{x\in \sqrt{n}{S}^{n?1}:?y\in H,{\Vert x?y\Vert }_2\le ?\}$$

因為$X$限制在$\sqrt{n}{S}^{n?1}$上，要使$X$與$H$上的點最近距離不超過$?$，一種可行的操作是限制一個坐標使其不超過$?/\sqrt{2}$，于是
$$H_{?}?\sqrt{n}{S}^{n?1}\cap \{x_1\le ?/\sqrt{2}\}$$

---

下面我們開始證明那個定理：

證明
假設${\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 \sqrt{n}{S}^{n?1}:f(x)\le M\}$$

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

根據Isoperimetric不等式2，
$$\sigma (A_t)\ge 1?e^{?c{t}^2},?c>0$$

因為$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^{?c{t}^2}$$

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

所以
$$P(|f(X)?M|\ge t)\le 2e^{?c{t}^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组合2 Spherical Distribution的Lipschitz函数 Isoperimetric不等式的全部內容，希望文章能夠幫你解決所遇到的問題。

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