定理 3.5 Rademacher 复杂度界限——二元分类
- 设
- 为取值于 的函数族，
- 为定义在输入空间 上的分布。
- 那么，对于任意 ，
- 以至少 的概率，从分布 中抽取的大小为 的样本 上，
- 以下不等式对任意 成立： R\left( h\right) \leq {\widehat{R}}_{S}\left( h\right) + {\Re }_{m}\left( \mathcal{H}\right) + \sqrt{\frac{\log \frac{1}{\delta }}{2m}} \tag{3.17} 以及 R\left( h\right) \leq {\widehat{R}}_{S}\left( h\right) + {\widehat{\Re }}_{S}\left( \mathcal{H}\right) + 3\sqrt{\frac{\log \frac{2}{\delta }}{2m}}\text{.} \tag{3.18}