定理 3.3 经验期望与 Rademacher 复杂度控制期望

定理 3.3 经验期望与 Rademacher 复杂度控制期望

• 设 $\mathcal{G}$ 为从 $z$ 映射到区间 $\left[0,1\right]$ 的函数族。
• 那么，对于任意 $\delta >0$，以至少 $1-\delta$ 的概率，
• 对于大小为 $m$ 的独立同分布样本 $S$，
• 以下每个不等式对所有 $g\in \mathcal{G}$ 均成立： \mathbb{E}\left\lbrack {g\left( z\right) }\right\rbrack \leq \frac{1}{m}\mathop{\sum }\limits_{{i = 1}}^{m}g\left( {z}_{i}\right) + 2{\Re }_{m}\left( \mathcal{G}\right) + \sqrt{\frac{\log \frac{1}{\delta }}{2m}} \tag{3.3} 以及 \mathbb{E}\left\lbrack {g\left( z\right) }\right\rbrack \leq \frac{1}{m}\mathop{\sum }\limits_{{i = 1}}^{m}g\left( {z}_{i}\right) + 2{\widehat{\mathfrak{R}}}_{S}\left( \mathcal{G}\right) + 3\sqrt{\frac{\log \frac{2}{\delta }}{2m}}\text{.} \tag{3.4}

\begin{proof} 对于任何样本 $S=\left(z_1,\dots ,z_m\right)$ 和任何 $g\in \mathcal{G}$，我们用 ${\hat{\mathbb{E}}}_S\left[g\right]$ 表示 $g$ 在 $S$ 上的经验平均值：${\hat{\mathbb{E}}}_S\left[g\right]=\frac{1}{m}\sum _{i=1}^{m}g\left(z_i\right)$。证明的关键在于将 McDiarmid 不等式应用于函数 $\Phi$，该函数对于任何样本 $S$ 定义为：

\Phi \left( S\right) = \mathop{\sup }\limits_{{g \in \mathcal{G}}}\left( {\mathbb{E}\left\lbrack g\right\rbrack - {\widehat{\mathbb{E}}}_{S}\left\lbrack g\right\rbrack }\right) . \tag{3.5}

设 $S$ 和 $S^{\prime }$ 为两个样本，且它们仅在一个点上不同，例如 $S$ 中的 $z_m$ 和 $S^{\prime }$ 中的 $z_m^{\prime }$。那么，由于上确界的差异不会超过差异的上确界，我们有：

$$\begin{array}{rl}\Phi \left(S^{\prime }\right)-\Phi \left(S\right)& \le \underset{g\in \mathcal{G}}{\sup }\left({\hat{\mathbb{E}}}_S\left[g\right]-{\hat{\mathbb{E}}}_{S^{\prime }}\left[g\right]\right)\\ & =\underset{g\in \mathcal{G}}{\sup }\frac{g\left(z_m\right)-g\left(z_m^{\prime }\right)}{m}\le \frac{1}{m}.\end{array}\text{\hspace{1em}(3.6)}$$

类似地，我们可以得到 $\Phi \left(S\right)-\Phi \left(S^{\prime }\right)\le \frac{1}{m}$，因此： $\left|\Phi \left(S\right)-\Phi \left(S^{\prime }\right)\right|\le \frac{1}{m}.$

然后，根据 McDiarmid 不等式，对于任何 $\delta >0$，以至少 $1-\delta /2$ 的概率，以下不等式成立： \Phi \left( S\right) \leq \underset{S}{\mathbb{E}}\left\lbrack {\Phi \left( S\right) }\right\rbrack + \sqrt{\frac{\log \frac{2}{\delta }}{2m}}. \tag{3.7}

接下来，我们对右侧的期望值进行界定如下：

$$\begin{array}{rl}& \underset{S}{\mathbb{E}}\left[\Phi \left(S\right)\right]\\ & =\underset{S}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\left(\mathbb{E}\left[g\right]-{\hat{\mathbb{E}}}_S\left(g\right)\right)\right]\\ & =\underset{S}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\underset{S^{\prime }}{\mathbb{E}}\left[{\hat{\mathbb{E}}}_{S^{\prime }}\left(g\right)-{\hat{\mathbb{E}}}_S\left(g\right)\right]\right]\\ & \le \underset{S,S^{\prime }}{\mathbb{E}}\left[\underset{g\in S}{\sup }\left({\hat{\mathbb{E}}}_{S^{\prime }}\left(g\right)-{\hat{\mathbb{E}}}_S\left(g\right)\right)\right]\\ & =\underset{S,S^{\prime }}{\mathbb{E}}\left[\underset{g\in S}{\sup }\frac{1}{m}\sum _{i=1}^m\left(g\left(z_i^{\prime }\right)-g\left(z_i\right)\right)\right]\\ & =\underset{\sigma ,S,S^{\prime }}{\mathbb{E}}\left[\underset{g\in S}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_i\left(g\left(z_i^{\prime }\right)-g\left(z_i\right)\right)\right]\\ & \le \underset{\sigma ,S^{\prime }}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}g\left(z_i^{\prime }\right)\right]+\underset{\sigma ,S}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\frac{1}{m}\sum _{i=1}^m-{\sigma }_{i}g\left(z_i\right)\right]\\ & =2\underset{\sigma ,S}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}g\left(z_i\right)\right]=2{\Re }_m\left(\mathcal{G}\right).\end{array}\text{\hspace{1em}(3.8)(3.9)(3.10)(3.11)(3.12)(3.13)}$$

公式 (3.8) 使用了 $S^{\prime }$ 中的点是以 i.i.d. 方式抽样的，因此 $\mathbb{E}\left[g\right]={\mathbb{E}}_{S^{\prime }}\left[{\hat{\mathbb{E}}}_{S^{\prime }}\left(g\right)\right]$，如公式 (2.3) 所示。

$$\begin{array}{r}\underset{S}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\underset{S^{\prime }}{\mathbb{E}}\left[{\hat{\mathbb{E}}}_{S^{\prime }}\left(g\right)-{\hat{\mathbb{E}}}_S\left(g\right)\right]\right]\le \underset{S,S^{\prime }}{\mathbb{E}}\left[\underset{g\in S}{\sup }\left({\hat{\mathbb{E}}}_{S^{\prime }}\left(g\right)-{\hat{\mathbb{E}}}_S\left(g\right)\right)\right]\end{array}\text{\hspace{1em}(3.9)}$$

不等式 (3.9) 由于上确界函数的次可加性而成立。

$$\begin{array}{rl}& \underset{S,S^{\prime }}{\mathbb{E}}\left[\underset{g\in S}{\sup }\left({\hat{\mathbb{E}}}_{S^{\prime }}\left(g\right)-{\hat{\mathbb{E}}}_S\left(g\right)\right)\right]\\ & =\underset{S,S^{\prime }}{\mathbb{E}}\left[\underset{g\in S}{\sup }\frac{1}{m}\sum _{i=1}^m\left(g\left(z_i^{\prime }\right)-g\left(z_i\right)\right)\right]\\ & =\underset{\sigma ,S,S^{\prime }}{\mathbb{E}}\left[\underset{g\in S}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_i\left(g\left(z_i^{\prime }\right)-g\left(z_i\right)\right)\right]\end{array}\text{\hspace{1em}(3.9)(3.10)(3.11)}$$

在公式 (3.11) 中，我们引入了 Rademacher 变量 ${\sigma }_i$，这些变量是取值于 $\{-1,+1\}$ 的均匀分布独立随机变量，如定义 3.2 中所述。 这不会改变公式 (3.10) 中出现的期望值：

• 当 ${\sigma }_i=1$ 时，相应的加项保持不变；
• 当 ${\sigma }_i=-1$ 时，相应的加项符号翻转，这等同于在 $S$ 和 $S^{\prime }$ 之间交换 $z_i$ 和 $z_i^{\prime }$。
  • 由于我们对所有可能的 $S$ 和 $S^{\prime }$ 取期望，这种交换不会影响整体期望；
  • 我们只是改变了期望中的加项的顺序。

$$\begin{array}{rl}& \underset{\sigma ,S,S^{\prime }}{\mathbb{E}}\left[\underset{g\in S}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_i\left(g\left(z_i^{\prime }\right)-g\left(z_i\right)\right)\right]\\ & \le \underset{\sigma ,S^{\prime }}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}g\left(z_i^{\prime }\right)\right]+\underset{\sigma ,S}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\frac{1}{m}\sum _{i=1}^m-{\sigma }_{i}g\left(z_i\right)\right]\end{array}\text{\hspace{1em}(3.11)(3.12)}$$

公式 (3.12) 由上确界函数的次可加性成立，即不等式 $\sup \left(U+V\right)\le \sup \left(U\right)+\sup \left(V\right)$。

$$\begin{array}{rl}& \underset{\sigma ,S^{\prime }}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}g\left(z_i^{\prime }\right)\right]+\underset{\sigma ,S}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\frac{1}{m}\sum _{i=1}^m-{\sigma }_{i}g\left(z_i\right)\right]\\ & =2\underset{\sigma ,S}{\mathbb{E}}\left[\underset{g\in \mathcal{G}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}g\left(z_i\right)\right]=2{\Re }_m\left(\mathcal{G}\right).\end{array}\text{\hspace{1em}(3.12)(3.13)}$$

最后，公式 (3.13) 来源于 Rademacher 复杂度的定义以及变量 ${\sigma }_i$ 和 $-{\sigma }_i$ 以相同方式分布的事实。

综上所述，可得

\underset{S}{\mathbb{E}}\left\lbrack {\Phi \left( S\right) }\right\rbrack \leq 2{\Re }_{m}\left( \mathcal{G}\right) . $$ 将 ${\mathfrak{R}}_{m}\left( \mathcal{G}\right)$ 化简为公式 (3.13) 中的结果，得到了公式 (3.3) 中的界限，使用 $\delta$ 替代了 $\delta /2$。 为了推导以 ${\widehat{\mathfrak{R}}}_{S}\left( \mathcal{G}\right)$ 为变量的界限，我们注意到，根据定义 3.1，改变 $S$ 中的一个点最多会使 ${\widehat{\Re }}_{S}\left( S\right)$ 改变 $1/m$。 然后，再次使用 McDiarmid 不等式，以概率 $1 - \delta /2$，以下不等式成立： $${\Re }_{m}\left( \mathcal{G}\right) \leq {\widehat{\Re }}_{S}\left( \mathcal{G}\right) + \sqrt{\frac{\log \frac{2}{\delta }}{2m}}. \tag{3.14}$$ 最后，我们使用并集界限将不等式 3.7 和 3.14 结合起来，这样以至少 $1 - \delta$ 的概率，我们得到： $$\Phi \left( S\right) \leq 2{\widehat{\Re }}_{S}\left( \mathcal{G}\right) + 3\sqrt{\frac{\log \frac{2}{\delta }}{2m}} \tag{3.15}$$ 可得 (3.4). `\end{proof}`