推论 3.8 用生长函数来界定 Rademacher 复杂度的上界

推论 3.8 用生长函数来界定 Rademacher 复杂度的上界

设 $\mathcal{G}$ 是一个取值在 $\{-1,+1\}$ 的函数族。 那么以下结果成立： {\Re }_{m}\left( \mathcal{G}\right) \leq \sqrt{\frac{2\log {\Pi }_{\mathcal{G}}\left( m\right) }{m}}. \tag{3.21}

\begin{proof}

• 对于固定的样本 $S=\left(x_1,\dots ,x_m\right)$，

• 我们用 ${\mathcal{G}}_{\mid S}$ 表示函数值向量的集合 ${\left(g\left(x_1\right),\dots ,g\left(x_m\right)\right)}^{\top }$，其中 $g\in \mathcal{G}$。

• 由于 $g\in \mathcal{G}$ 的取值范围是 $\{-1,+1\}$，

  • 这些向量的范数被界定为 $\sqrt{m}$。

• 我们可以如下应用 Massart 引理： ${\Re }_m\left(\mathcal{G}\right)=\underset{S}{\mathbb{E}}\left[\underset{\sigma }{\mathbb{E}}\left[\underset{u\in {\mathcal{G}}_{\mid S}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_i{u}_i\right]\right]\le \underset{S}{\mathbb{E}}\left[\frac{\sqrt{m}\sqrt{2\log |{\mathcal{G}}_{\mid S}|}}{m}\right].$

• 根据定义，$\left|{\mathcal{G}}_{\mid S}\right|$ 被生长函数界定，因此， ${\Re }_m\left(\mathcal{G}\right)\le \underset{S}{\mathbb{E}}\left[\frac{\sqrt{m}\sqrt{2\log {\Pi }_{\mathcal{G}}\left(m\right)}}{m}\right]=\sqrt{\frac{2\log {\Pi }_{\mathcal{G}}\left(m\right)}{m}},$ 得证 \end{proof}