定理 3.7 Massart 引理

定理 3.7（Massart 引理）

• 设 $\mathcal{A}\subseteq {\mathbb{R}}^m$ 是一个有限集，
  • 且 $r=\underset{\mathbf{x}\in \mathcal{A}}{\max }\parallel \mathbf{x}{\parallel }_2$，
• 则以下结果成立： \underset{\mathbf{\sigma }}{\mathbb{E}}\left\lbrack {\frac{1}{m}\mathop{\sup }\limits_{{\mathbf{x} \in \mathcal{A}}}\mathop{\sum }\limits_{{i = 1}}^{m}{\sigma }_{i}{x}_{i}}\right\rbrack \leq \frac{r\sqrt{2\log \left| \mathcal{A}\right| }}{m}, \tag{3.20} 其中
• ${\sigma }_i$ 是取值在 $\{-1,+1\}$ 的独立均匀随机变量，
• $x_1,\dots ,x_m$ 是向量 $\mathbf{x}$ 的分量。

\begin{proof}

• 这个结果立即来自于 Corollary D. 11 给出的最大值期望的界限，
• 因为
  • 随机变量 ${\sigma }_i{x}_i$ 是独立的，
  • 并且每个 ${\sigma }_i{x}_i$ 的取值范围是 $\left[-\left|x_i\right|,\left|x_i\right|\right]$，其中 $\sqrt{\sum _{i=1}^m{x}_i^2}\le r^2.$ \end{proof}