最近，我一直在研究Martin J. Wainwright 所写的High-Dimensional Statistics: A Non-Asymptotic Viewpoint 。在本书中，作者使用了一种特殊的复杂度度量，称为局部 Rademacher 复杂度，以表明非参数最小二乘估计与某个函数类（分布族）的极小极大风险相匹配。

我很困惑为什么我们需要这种略有不同的本地化版本的 Rademacher 复杂性。我做了一些研究，发现它是由Vladimir Koltchinskii和Peter L. Bartlett提出的。在巴特利特的论文中，对于每个$r>0$, 局部 Rademacher 复杂度定义为

$$E[\frac{1}{n}\sup_{f\in\mathcal F, P f^2\leq r}\sum_{i=1}^n\sigma_if(X_i)]$$ 这与通常的 Rademacher 复杂性不同，它受到$Pf^2\leq r$的限制，其中$Pf^2$表示$f^2$对未知数据分布$P$的期望。

在Bartlett 的论文中，他们声称

" Rademacher 平均值（复杂度）的缺点之一是它们提供了函数类复杂度的全局估计，也就是说，它们没有反映算法可能会选择具有小误差的函数的事实，并且特别是，只使用函数类的一小部分。因此，可以通过全局 Rademacher 平均值获得的最佳错误率至少为 $\frac{1}{\sqrt{n}}$（其中 n 是样本大小），在某些情况下是次优的。”

我对这个声明有很多疑问。

首先，为什么 Rademacher 复杂度的下限至少是？在统计学习中，我们经常使用 Rademacher 复杂度作为估计误差的上限。给定特定的函数类，我们从未实际计算过它的下限。我认为我们知道的唯一下限来自统计学习的基本理论，这仅适用于 0-1 损失和二元分类。（有关详细信息，另请参阅此问题）。但是，Rademacher 复杂性在此设置中最为严格。为界时，Massart 的引理表明 Rademacher 复杂度为。$\frac{1}{\sqrt{n}}$$M$$O(\frac{\sqrt{\log M}}{n})$

其次，在哪个非平凡但经常访问的学习模型中，我们可以有函数类假设 Rademacher 复杂度是但实际上我们可以通过适当的分析来实现快速收敛使用局部 Rademacher 复杂度？（这样的函数类的存在证明了 Rademacher 复杂性的松散性）$\Omega(\frac{1}{\sqrt{n}})$

第三，在这样的分析中，我们经常需要假设对于类的每个成员，可以使用它的期望来控制它的方差。也就是说存在一个常数 B 使得 为什么我们真的需要这个方差假设及其直觉和暗示？$\mathcal F$

$$\forall f\in\mathcal F,\ Pf^2\leq B Pf$$