3.1 Rademacher complexity

• 我们将继续使用 $\mathcal{H}$ 来表示假设集，正如前几章中所述。

• 本节的许多结果是通用的，并且适用于任意的损失函数 $L:\mathcal{Y}\times \mathcal{Y}\to \mathbb{R}$ 。

• 在下文中，$\mathcal{G}$ 通常被解释为与假设集 $\mathcal{H}$ 相关联的损失函数族，这些损失函数从 $\mathcal{Z}=\mathcal{X}\times \mathcal{Y}$ 映射到 $\mathbb{R}$： $\mathcal{G}=\{g:\left(x,y\right)\mapsto L\left(h\left(x\right),y\right):h\in \mathcal{H}\}.$

• 然而，定义是针对函数族 $\mathcal{G}$ 的一般情况给出的，该函数族从任意输入空间 $z$ 映射到 $\mathbb{R}$。

• Rademacher 复杂度通过衡量假设集拟合随机噪声的程度来捕捉函数族的丰富性。

• 以下是经验 Rademacher 复杂度和平均 Rademacher 复杂度的正式定义。

Rademacher 复杂度的定义

现在我们准备基于 Rademacher 复杂度给出我们的第一个泛化界限。

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

以下结果涉及到假设集 $\mathcal{H}$ 的经验 Rademacher 复杂度以及在二元损失（零一损失）情况下与 $\mathcal{H}$ 相关的损失函数族 $\mathcal{G}$ 的经验 Rademacher 复杂度。

引理 3.4 0-1 loss 的 Rademacher 复杂度

定理 3.5 Rademacher 复杂度界限——二元分类

Remark

• 该定理基于 Rademacher 复杂度提供了两个二元分类的推广界限。
• 需要注意的是，第二个界限 (3.18) 是依赖于数据的：
  • 经验 Rademacher 复杂度 ${\hat{\mathfrak{R}}}_S\left(\mathcal{H}\right)$ 是所抽取的具体样本 $S$ 的函数。
  • 因此，如果我们能够计算 ${\hat{\mathfrak{R}}}_S\left(\mathcal{H}\right)$，这个界限可能特别有用。
• 那么，我们如何计算经验 Rademacher 复杂度呢？
  • 再次利用 ${\sigma }_i$ 和 $-{\sigma }_i$ 具有相同的分布，我们可以写出 ${\hat{\mathfrak{R}}}_S\left(\mathcal{H}\right)=\underset{\sigma }{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\sup }\frac{1}{m}\sum _{i=1}^m-{\sigma }_{i}h\left(x_i\right)\right]=-\underset{\sigma }{\mathbb{E}}\left[\underset{h\in \mathcal{H}}{\inf }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}h\left(x_i\right)\right].$
  • 在固定的 $\sigma$ 值的情况下，计算 $\underset{h\in \mathcal{H}}{\inf }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}h\left(x_i\right)$ 等价于一个经验风险最小化问题。
  • 对于某些假设集，这已知是计算上困难的问题。
• 因此，在某些情况下，计算 ${\hat{\Re }}_S\left(\mathcal{H}\right)$ 可能是计算上困难的。

在接下来的部分中，我们将把 Rademacher 复杂度与更容易计算的组合测度联系起来。 这些测度在许多学习分析背景下非常有用，并且独立存在一定的研究价值。