高维统计理论 Gauss与Rademacher复杂度

对于随机过程 { X θ , θ ∈ T } \{X_{\theta},\theta \in T\} {Xθ​,θ∈T}，其中$T$是随机过程的指标集，给定$\theta \in T$时，$X_{\theta }$是一个随机变量。在本篇中，我们感兴趣的问题是如何利用已知的随机过程研究指标集$T$的性质。

---

定义 Gauss复杂度（Gaussian Complexity）
对于给定的指标集$T$，定义随机过程 { G θ , θ ∈ T } \{G_{\theta},\theta \in T\} {Gθ​,θ∈T}，其中
$$G_{\theta }=\sum _{i=1}^d{w}_i{\theta }_i,w_i\stackrel{i.i.d.}{\sim }N(0,1)$$

称$\mathcal{G}(T)$是 { G θ , θ ∈ T } \{G_{\theta},\theta \in T\} {Gθ​,θ∈T}的Gauss复杂度，
$$\mathcal{G}(T)=E\left[\underset{\theta \in T}{\sup }{G}_{\theta }\right]$$

即随机过程的期望上确界。它的作用是衡量指标集的“复杂程度”或者说“大小”。

定义 Rademacher复杂度（Rademacher Complexity）
对于给定的指标集$T$，定义随机过程 { R θ , θ ∈ T } \{R_{\theta},\theta \in T\} {Rθ​,θ∈T}，其中
R θ = ∑ i = 1 d ϵ i θ i , ϵ i ∼ i . i . d . U { − 1 , + 1 } ( Rademacher随机变量 ) R_{\theta}=\sum_{i=1}^d \epsilon_i\theta_i,\epsilon_i \overset{i.i.d.}{\sim} U\{-1,+1\}(\text{Rademacher}随机变量) Rθ​=i=1∑d​ϵi​θi​,ϵi​∼i.i.d.U{−1,+1}(Rademacher随机变量)

称$\mathcal{R}(T)$是 { R θ , θ ∈ T } \{R_{\theta},\theta \in T\} {Rθ​,θ∈T}的Gauss复杂度，
$$\mathcal{R}(T)=E\left[\underset{\theta \in T}{\sup }{R}_{\theta }\right]$$

定理 Gauss复杂度与Rademacher复杂度的关系
如果$T$是${\mathbb{R}}^d$的子集，则
$$\begin{gathered} \mathcal{R}(T)\le \sqrt{\frac{\pi }{2}}\mathcal{G}(T) \\ \mathcal{G}(T)\le 2\sqrt{\log d}\mathcal{R}(T) \end{gathered}$$

例 Gauss复杂度与Rademacher复杂度相等
假设 T = B 2 d = { θ ∈ R d : ∥ θ ∥ 2 ≤ 1 } T=B_2^d=\{\theta \in \mathbb R^d:\left\| \theta\right\|_2 \le 1\} T=B2d​={θ∈Rd:∥θ∥2​≤1}，根据Cauchy不等式，
$$\mathcal{R}(T)=E\underset{\theta \in T}{\sup }⟨\theta ,ϵ⟩=\underset{\theta \in T}{\sup }{\Vert \theta \Vert }_{2}E{\Vert ϵ\Vert }_2\le E{\Vert ϵ\Vert }_2=\sqrt{d}$$

Gauss复杂度计算思路类似，根据Cauchy不等式以及Jensen不等式，
$$\begin{gathered} \mathcal{G}(T)=E\underset{\theta \in T}{\sup }⟨\theta ,w⟩=\underset{\theta \in T}{\sup }{\Vert \theta \Vert }_{2}E{\Vert w\Vert }_2=E{\Vert w\Vert }_2 \\ \le \sqrt{E{\Vert w\Vert }_2^2}=\sqrt{dVar(w_i)}=\sqrt{d} \end{gathered}$$

另外，根据${\chi }^2$分布的concentration，
$$\begin{gathered} E{\Vert w\Vert }_2={\int }_0^{+\infty }\sqrt{x}d{P}_{{\chi }_d^2}(x)\ge {\int }_{d-t}^{d+t}\sqrt{x}d{P}_{{\chi }_d^2}(x) \\ \ge (\sqrt{d-t})(1-2e^{-\frac{t^{2}d}{8}})=\sqrt{d}(1-o(1)) \end{gathered}$$

因此$\mathcal{G}(T)=\sqrt{d}$。