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

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

• 设
  • $\mathcal{H}$ 为取值于 $\{-1,+1\}$ 的函数族，
  • $\mathcal{G}$ 为与 $\mathcal{H}$ 相关的零一损失的损失函数族： $\mathcal{G}=\{\left(x,y\right)\mapsto 1_{h\left(x\right)\ne y}:h\in \mathcal{H}\}.$
• 对于任意样本 $S=\left(\left(x_1,y_1\right),\dots ,\left(x_m,y_m\right)\right)$，
  • 其中元素属于 $\mathcal{X}\times \{-1,+1\}$，
• 设 $S_{\mathcal{X}}$ 表示 $S$ 在 $\mathcal{X}$ 上的投影：$S_X=\left(x_1,\dots ,x_m\right)$。
• 则 $\mathcal{G}$ 和 $\mathcal{H}$ 的经验 Rademacher 复杂度之间存在以下关系： {\widehat{\mathfrak{R}}}_{S}\left( \mathcal{G}\right) = \frac{1}{2}{\widehat{\mathfrak{R}}}_{{S}_{\mathcal{X}}}\left( \mathcal{H}\right) \tag{3.16}

Remark

请注意，该引理通过取期望值得出，对于任意 $m\ge 1$，有 ${\Re }_m\left(\mathcal{G}\right)=\frac{1}{2}{\mathfrak{R}}_m\left(\mathcal{H}\right).$ 这些关于经验 Rademacher 复杂度和平均 Rademacher 复杂度的联系， 可以用于推导基于假设集 $\mathcal{H}$ 的 Rademacher 复杂度的二元分类推广界限。