?
3.1 Rademacher Complexity
现在考虑无限集合 \(\cal H\)，并给出几个 guarantee
损失函数为映射 \(L:\cal Y\times Y\to \mathbb{R}\)；样本 \((x,y)\) 通过某个假设 \(h\in \cal H\) 再通过某个损失函数，可以视作一个从 \(\cal Z=X\times Y\) 到 \(\mathbb{R}\) 的映射 \(g\)，其集合 \(\cal G\) 用以表示上述 “基于 \(\cal H\) 的损失函数集合”：\({\cal G}=\{g:(x,y)\mapsto L(h(x),y):h\in\cal H\}=\{g:\cal Z\to \mathbb{R}\}\)
Rademacher Complexity 通过刻画函数集合 “拟合噪声的能力”，进而刻画其丰富程度（captures the richness of a family of functions by measuring the degree to which a hypothesis set can fit random noise）
定义 Empirical Rademacher complexity
函数集合 \(\cal G=\{g: Z\to [a,b]\}\)；样本 \(S=(z _1,\dotsb, z _m)\in \cal Z ^m\)，定义 \(\cal G\) 就关于 \(S\) 的 “经验 Rademacher 复杂度” 为：
其中 “噪声” \(\boldsymbol{\sigma}=(\sigma _1,\dotsb,\sigma _m)'\)，为 \(m\) 个独立服从 \(\{-1,+1\}\) 平均分布的变量，也称为 Rademacher 变量（后面证明里会提到这个谜之变量怎么出现的）；我们用 \(g\) 对样本 \(S\) 的映射结果 \({\bf g} _S\) 作为拟合噪声，并用点积刻画拟合程度。
可见 \(\widehat{\frak{R}} _S({\cal G})\) 表示 \(\cal G\) 中以采样 \(S\) “尽可能拟合”（通过 \(g\) 映射并取上界）各个噪声的平均能力（取期望值），从而反映 \(\cal G\) 的丰富程度。
进一步地，定义 \(\cal G\) 的 “Rademacher 复杂度” 为：
定义 Rademacher complexity
\(S\sim\cal D ^m\)，对于任意正整数 \(m\)，\(\cal G\) 的 Rademacher complexity 为其抽取 \(m\) 个样本得到经验 Rademacher 复杂度的期望值，也就是 “期望以随机采样” 拟合各个噪声的平均能力：
接下来就损失函数的期望，给出 generalization bound：
定理
函数集合 \(\cal G=\{g: Z\to [0,1]\}\)；以 i.i.d. 抽取 \(S=(z _1,\dotsb, z _m)\)，对于任意 \(\delta>0\)，以至少 \(1-\delta\) 的概率，对任意 \(g\in \cal G\) 都有其期望值 \(\mathbb{E}[g]\)：
也就是说，以很大的概率，\(\cal G\) 里任意一个损失函数 \(g\) 的期望值 \(\mathbb{E}[g]\)，通过采样，被采样试探出的平均值 + 一个刻画 \(\cal G\) 多样性的值（或者 \(\cal G\) 单就在样本 \(S\) 上体现的多样性）+ 一个负相关于采样数量的值给上限住了。
证明：
对于 \((1)\) 式，将 \(g\) 关于 \(S\) 的经验平均值记为 \(\widehat{\mathbb{E}} _S[g]=\frac{1}{m}\sum _{i=1}^m g(z _i)\)，并移到左边：\(\mathbb{E}[g]-\widehat{\mathbb{E}} _S[g]\)；定理对任意 \(g\) 的表述，等价刻画成左式看作关于 \(S\) 的函数并在 \(\cal G\) 取上界 \(\Phi(S)=\sup _{g\in \cal G}(\mathbb{E}[g]-\widehat{\mathbb{E}} _S[g])\)，然后考虑对其放缩
考虑 McDiarmid 不等式（见补充）用在 \(\Phi(S)\) 上：对于仅有一个点改变的 \(S, S'\)，由于上界的差不超过差的上界，有 \(\Phi(S')-\Phi(S)\le \sup _{g\in \cal G}(\widehat{\mathbb{E}} _S[g]-\widehat{\mathbb{E}} _{S'}[g])\le 1/m\)，于是应用不等式，以至少 \(1-\delta/2\) 的概率，有 \(\Phi(S)\le \mathbb{E} _S[\Phi(S)]+\sqrt{\frac{\log(2/\delta)}{2m}}\)，接下来考虑这个期望值：
注意证明里自从引入了谜之 Rademacher 变量，我们可以将对称的 \(S,S'\) 分开并摆脱正负号使两者等价，真是神奇的设计
从而 \((1)\) 式以至少 \(1-\delta\) 概率成立；对于 \((2)\) 式，只需要在 \((1)\) 式的基础上，注意到 \(\widehat{\frak{R}} _{S}(\cal G)\) 在改变一个样本点时最多改变 \(1/m\)（注意 \(g\) 只映射到 \([0,1]\)）且 \(\mathbb{E} _S(\widehat{\frak{R}} _{S}(\cal G))={\frak{R}} _{m}(\cal G)\)，故再次使用 McDiarmid 不等式，以至少 \(1-\delta/2\) 概率有 \({\frak{R}} _{m}(\cal G)\le \widehat{\frak{R}} _{S}(\cal G)+\sqrt{\frac{\log(2/\delta)}{2m}}\) 然后用 union bound 简单相加概率，即可证得 \((2)\) 式。
引理
补充
McDiarmid 不等式
\(m\) 维独立随机变量 \(S=(X _1,\dotsb, X _m)\in \cal X ^m\)；若对于每个 \(i\in [m]\) 都存在一个 \(c _i>0\)，使得多元函数 \(f:\cal X ^m\to\mathbb{R}\) 在任何时候单独以每一维取值变化时的函数值变化量不超过 \(c _i\)（于是若干维变化带来的函数值变化上界等于对应维度的上界和）：
则 \(f(S)\) 的值以很大概率满足其与期望值足够接近：