Foundations of Machine Learning

PAC

Probably Approximately Correct

Definition

$\mathcal{X}$：input space (the set of all possible examples or instances)

$\mathcal{Y}$：output space (all possible labels or target values)

A concept $c \colon \mathcal{X} \to \mathcal{Y}$ is a mapping from $\mathcal{X}$ to $\mathcal{Y}$.

对于可以学到的 mapping 称作 hypothesis

它们属于对应集合，concept $c\in \mathcal{C}$ 以及 hypothesis $h\in \mathcal{H}$。

consistent vs computational cost trade-off：$\mathcal{H}$ 越大，$\mathcal{C,H}$ 交集越大 (consistent)，但是对应计算复杂度更大 (computational cost)

同时 $\mathcal{H}$ 过大/小也会出现 overfitting 或者 underfitting 的问题。

Definition (PAC-learning): A concept class $\mathcal{C}$ is PAC-learnable if there exists an algorithm $\mathcal{A}$ such that for all $\varepsilon > 0$, $\delta > 0$, for all distributions $\mathcal{D}$, and for all $c \in \mathcal{C}$:

$$\forall m \ge \text{poly}\left(\frac{1}{\varepsilon}, \frac{1}{\delta}, n, \text{size}(c)\right), \quad \Pr_{S \sim \mathcal{D}^m}\Big(R(h_S) \le \varepsilon\Big) \ge 1 - \delta$$

• $n$：表示 Sample $x$ 的维度/编码复杂度；
• $\text{size}(c)$：表示描述 concept $c$ 或者 hypothesis 的表示大小/复杂度；

例如在二分类问题中，对于 $n$ 个元素而言想要分辨出谁是 1 谁是 0，需要 $\mathbb{F}_2^n$ 下的一个向量描述，共 $n$ bit 所以 $\text{size}(c)=n$。

• $R(h_S) \le \varepsilon$：近似正确（误差率不超过容忍度 $\varepsilon$）Approximately Correct ；
• $\ge 1 - \delta$：以至少 $1 - \delta$ 的高置信度成立 Probably.

也就是说，在样本数 $m$ 足够大时，在 $\mathcal{D}$ 中采样得到 $\mathcal{S}$，其 Generalization Error 是 Probably Approximately Correct 的。

更进一步地, if $\mathcal{A}$ runs in $\text{poly}\left(\frac{1}{\varepsilon}, \frac{1}{\delta}, n, \text{size}(c)\right)$，则称其 efficiently PAC-learnable .

注意这里是对一个 concept 集合 $\mathcal{C}$ 而言的，不是对特定的一种情况 concept $c$。

Unbiased Estimator

设在某应用场景下（例如观测赤道地区的温度指标），观测样本 $X_1, \dots, X_n$ 为独立同分布（i.i.d.）的随机变量： $X_1, \dots, X_n \stackrel{\text{i.i.d.}}{\sim} \mathcal{D}$

• $\mathbb{E}[X_i]=\mu$
• $\text{Var}[X_i] = \sigma^2$

定义令 Empirical Mean 作为估计量（预测模型）： $\bar{X} = \frac{1}{n} \sum_{i=1}^n X_i$，则模型的期望与方差分别为：

• $\mathbb{E}[\bar{X}] = \mathbb{E}\left[ \frac{1}{n} \sum_{i=1}^n X_i \right] = \frac{1}{n} \sum_{i=1}^n \mathbb{E}[X_i] = \frac{1}{n} \cdot (n \mu) = \mu$
• $\text{Var}[\bar{X}] = \text{Var}\left( \frac{1}{n} \sum_{i=1}^n X_i \right) = \frac{1}{n^2} \sum_{i=1}^n \text{Var}[X_i] = \frac{1}{n^2} \cdot (n \sigma^2) = \frac{\sigma^2}{n}$

Concentration（测度集中）:

Chebyshev’s Inequality： 对于任意随机变量 $X$ 及其偏离阈值 $t > 0$ 有： $\Pr(|X - \mathbb{E}[X]| \ge t) \le \frac{\text{Var}[X]}{t^2}$

令 $t = \varepsilon \mu$，$\Pr(|\bar{X} - \mu| \ge \varepsilon \mu) \le \frac{\text{Var}[\bar{X}]}{(\varepsilon \mu)^2} = \frac{\frac{\sigma^2}{n}}{\varepsilon^2 \mu^2} = \frac{\sigma^2}{\varepsilon^2 \mu^2 n}$。

PAC框架中，需要单次估计至少 $1 - \delta$ 的置信度，则

$$\Pr(|\bar{X} - \mu| \ge \varepsilon \mu) \le \frac{\sigma^2}{\varepsilon^2 \mu^2 n} \le \delta\\ \Longrightarrow n \ge \frac{\sigma^2}{\varepsilon^2 \mu^2 \delta}=\text{poly}(\frac{1}{\varepsilon},\frac{1}{\delta})$$

其中 sample 度量维度为 $1$，因为只有一维标量 label (or value) 即预测温度；由于直接给出预测值 hypothesis size 视作常数。

ERM 任务，使用最小二乘损失，其解为 sample mean，model size 视作常数。

Example 2.4 (Learning axis-aligned rectangles)

下面这个解释是 ok 的，来自该视频的评论区。

其中《注意到》简而言之是在说明，$R_S$ 四条边都分别落在 $r_1,r_2,r_3,r_4$ 中 $\Longrightarrow$ 误差 $\leq \epsilon$，则讨论误差 $>\epsilon$ 的概率仅需考虑其逆否命题。

假设二分类数据集，模型是记忆所有的正类样本。遇到相同的就为正，否则为负。

Generalization Bounds

Theorem 2.5 (Learning bound — finite $\mathcal{H}$, consistent case)

Theorem 2.5 (Learning bound — finite $\mathcal{H}$, consistent case)，考虑 hypothesis set $\mathcal{H}$ finite 且 consistent 的情况下，let $\mathcal{A}$ be the algorithm that for any concept $c\in \mathcal{H}$ and I.I.D. Sample $S$，$\mathcal{A}$ 给出的 $h_S$ 满足 Training Error $\widehat{R}_S(h_S) = 0$，则 for any $\epsilon,\delta>0$，概率 $\mathbb{P}_{S \sim \mathcal{D}^m} [R(h_S) \le \epsilon] \ge 1 - \delta$ holds if $m \ge \frac{1}{\epsilon} \left( \log |\mathcal{H}| + \log \frac{1}{\delta} \right)$。

将其改写为等价的 Generalization bound 的形式（由于任意满足条件的 $\epsilon$ 均成立，故可取 $\epsilon=\frac{1}{m}\left( \log |\mathcal{H}| + \log \frac{1}{\delta} \right)$，此时原命题等价于

$$\Longleftrightarrow R(h_S) \le \frac{1}{m} \left( \log |\mathcal{H}| + \log \frac{1}{\delta} \right)\quad w.p. 1-\delta$$

Proof: 考虑问题的反面，如果学到的 $h_S$ 满足 $R(h_S)>\epsilon$，说明 $h_S$ 在分布 $D$ 中有 $>\epsilon$ 的概率出错。而 $S$ 是 I.I.D. 选取的，则 $Pr\left(\widehat{R}_S(h_S) = \frac{1}{m}\sum\limits_{i=1}^m\mathbb{1}_{h(x_i)\neq y_i}=0\right)\leq (1-\epsilon)^m$，即每次抽样都抽到表现正确的 example。令 $\mathcal{H}_\epsilon = \{h \in \mathcal{H}: R(h) > \epsilon\}$，则失败即选取到 $\mathcal{H}_{\epsilon}$ 内满足 $\widehat{R}_S(h) = 0$ 的 $h$，那么计算存在这样一个 $h$ 的概率。

$$\begin{aligned} \mathbb{P} \left[ \exists h \in \mathcal{H}_\epsilon: \widehat{R}_S(h) = 0 \right] &= \mathbb{P} \left[ \widehat{R}_S(h_1) = 0 \lor \dots \lor \widehat{R}_S(h_{|\mathcal{H}_\epsilon|}) = 0 \right] \\ &\le \sum_{h \in \mathcal{H}_\epsilon} \mathbb{P} \left[ \widehat{R}_S(h) = 0 \right] \qquad \text{(union bound)} \\ &\le \sum_{h \in \mathcal{H}_\epsilon} (1 - \epsilon)^m \le |\mathcal{H}|(1 - \epsilon)^m \le |\mathcal{H}|e^{-m\epsilon}. \end{aligned}$$

令 $|\mathcal{H}|e^{-m\epsilon}\leq \delta$ (失败率) 则得到 $m\geq \frac{1}{\epsilon}(\log H+\log\frac{1}{\delta})$，PAC-learning。

所以，Under finite $H$, consistent algorithm $A$ is PAC-learnable algorithm.

回顾一下，如果 Algorithm $\mathcal{A}$ 总能找到 consistent hypothesis, 并且 sample 足够大时，它在泛化误差上的表现不会太差，要不然它是以很低的概率才能恰好命中自己会的那些 training data。

[Example 2.6] Conjunction of Boolean literals

要预测一个输入在合取范式下的结果 (positive, or negative)，给定很多 examples 有 positive 和 negative 的。执行算法：先假设所有文字和其反面都在合取范式中，每次得到一个 positive example 时将其违反的文字去除。例如 $(1,1,0,0)$ 会将 $\bar{x_1},\bar{x_2},x_3,x_4$ 去除。那么得到的合取范式肯定会对 positive example 预测正确，由于可能去除本应该去除的文字，所以该合取范式会比真正的合取范式更严格，那么对 negative example 也可以预测正确。

现在我们来看 hypothesis set $\mathcal{H}$，对每个文字存在三种情况：$x,\bar x,\empty$，分别要求 positive, negative, unknown，所以 $|\mathcal{H}|=|\mathcal{C}|=3^n$，根据定理，有 $m \ge \frac{1}{\epsilon} \left( (\log 3)n + \log \frac{1}{\delta} \right)$，PAC-learnable，同时也是 efficient PAC-learnable。

Learning bound — finite $\mathcal{H}$, inconsistent case

Hoeffding’s inequality: 设 $X_1, X_2, \dots, X_n$ 为相互独立的随机变量，且每个 $X_i$ 几乎必然取值于有界闭区间 $[a_i, b_i]$。其均值 $\bar{X} = \frac{1}{n} \sum_{i=1}^n X_i$，对于任意常数 $t > 0$，单侧偏差界 $P(\bar{X} - \mathbb{E}[\bar{X}] \ge t) \le \exp\left( - \frac{2 n^2 t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right)$，其几何意义是测度几乎集中在均值附近。

在 inconsistent case 中 $\widehat{R}_S(h)\neq 0,\mathbb{E}\left(\widehat{R}_S(h)\right)=R(h)$，那么就可以用 Heffding’s inequality 去 bound 住 $R(h)$，对于 $\widehat{R}_S(h)=\sum\frac{1}{m}\mathbb{1}_{h_S(x_i)\neq y_i}$ 则 $\sum(b_i-a_i)^2=\frac{1}{m}$ 所以有 $\underset{S \sim \mathcal{D}^m}{\Pr} \left( \left\vert{} \widehat{R}_S(h) - R(h) \right\vert{} \ge \varepsilon \right) \le 2\exp(-2m\varepsilon^2)$ 令其 $=\delta$，所以化简得到

$\Rightarrow$ single hypothesis: $h \colon \mathcal{X} \to \{0, 1\}$, $\forall \delta > 0$, w.p. $\ge 1 - \delta$:

$$\underline{R(h)} \le \widehat{R}_S(h) + \sqrt{\frac{\log \frac{2}{\delta}}{2m}}$$

Theorem 2.13 (Learning bound — finite H, inconsistent case)

Theorem 2.13 (Learning bound — finite $\mathcal{H}$, inconsistent case) Let $\mathcal{H}$ be a finite hypothesis set. Then, for any $\delta > 0$, with probability at least $1 - \delta$, the following inequality holds:

$$\forall h \in \mathcal{H}, \quad R(h) \le \widehat{R}_S(h) + \sqrt{\frac{\log \vert{}\mathcal{H}\vert{} + \log \frac{2}{\delta}}{2m}} \tag{2.20}$$

Proof (Obviously):

$$\begin{align} \mathbb{P} \left[ \exists h \in \mathcal{H} : |\widehat{R}_S(h) - R(h)| > \epsilon \right] &= \mathbb{P} \left[ (|\widehat{R}_S(h_1) - R(h_1)| > \epsilon) \lor \dots \lor (|\widehat{R}_S(h_{|\mathcal{H}|}) - R(h_{|\mathcal{H}|})| > \epsilon) \right] \\ &\le \sum_{h \in \mathcal{H}} \mathbb{P} \left[ |\widehat{R}_S(h) - R(h)| > \epsilon \right] \\ &\le 2|\mathcal{H}| \exp(-2m\epsilon^2)=\delta \end{align}$$

利用 Union Bound，再令最后 bound 的概率为 $\delta$，最后解得 $\epsilon = \sqrt{\frac{\log \vert{}\mathcal{H}\vert{} + \log \frac{2}{\delta}}{2m}}$，那么

对 hypothesis class 内所有 hypothesis $h \in \mathcal{H}$ 同时成立 w.p. $\geq 1-\delta$：

$$R(h) \le \widehat{R}_S(h) + \epsilon = \widehat{R}_S(h) + \sqrt{\frac{\log \vert{}\mathcal{H}\vert{} + \log \frac{2}{\delta}}{2m}}$$

Agnostic PAC-learning

当输出是随机分布的。

Definition 2.14 (Agnostic PAC-learning) Let $\mathcal{H}$ be a hypothesis set. $\mathcal{A}$ is an agnostic PAC-learning algorithm if there exists a polynomial function $\operatorname{poly}(\cdot, \cdot, \cdot, \cdot)$ such that for any $\epsilon > 0$ and $\delta > 0$, for all distributions $\mathcal{D}$ over $\mathcal{X} \times \mathcal{Y}$, the following holds for any sample size $m \ge \operatorname{poly}(1/\epsilon, 1/\delta, n, \operatorname{size}(c))$:

$$\underset{S \sim \mathcal{D}^m}{\mathbb{P}} \left[ R(h_S) - \min_{h \in \mathcal{H}} R(h) \le \epsilon \right] \ge 1 - \delta. \tag{2.21}$$

If $\mathcal{A}$ further runs in $\operatorname{poly}(1/\epsilon, 1/\delta, n)$, then it is said to be an efficient agnostic PAC-learning algorithm.

Rademacher Complexity

Definition

The family of loss functions associated with $\mathcal{H}$: $\mathcal{G} = \{g \colon (x, y) \mapsto L(h(x), y) \colon h \in \mathcal{H}\}$，即对于所有 hypothesis $h$，它对应的 loss function 构成的集合。

Definition 3.1 (Empirical Rademacher complexity) Let $\mathcal{G}$ be a family of functions mapping from $\mathcal{Z}$ to $[a, b]$ and $S = (z_1, \dots, z_m)$ a fixed sample of size $m$ with elements in $\mathcal{Z}$. Then, the empirical Rademacher complexity of $\mathcal{G}$ with respect to the sample $S$ is defined as:

$$\widehat{\mathfrak{R}}_S(\mathcal{G}) = \underset{\boldsymbol{\sigma}}{\mathbb{E}}\left[\sup_{g \in \mathcal{G}} \frac{1}{m} \sum_{i=1}^m \sigma_i g(z_i)\right]$$

其中 $\sigma$ 是一个由 $\{-1,+1\}$ 各 w.p. $\frac{1}{2}$ 构成的向量，为随机噪声。$\widehat{\mathfrak{R}}_S(\mathcal{G}) = \underset{\boldsymbol{\sigma}}{\mathbb{E}}\left[\sup_{g \in \mathcal{G}} \frac{\boldsymbol{\sigma} \cdot \mathbf{g}_S}{m}\right]$，其中内积是衡量相似度的指标，所以此处反映了 loss functions family $\mathcal{G}$ 对随机噪声的拟合能力 / 表达能力。

Definition 3.2 (Rademacher complexity)

$$\mathfrak{R}_m(\mathcal{G}) = \underset{S \sim \mathcal{D}^m}{\mathbb{E}} [\widehat{\mathfrak{R}}_S(\mathcal{G})]$$

Theorem 1

对 i.i.d. Sample $\mathcal{S}$ of size $m$, w.p. $\geq 1-\delta$, $\forall g\in \mathcal{G}$，存在泛化界

$$\begin{align} \mathbb{E}[g(z)] \le \frac{1}{m} \sum_{i=1}^m g(z_i) + 2\mathfrak{R}_m(\mathcal{G}) + \sqrt{\frac{\log \frac{1}{\delta}}{2m}}\tag{3.3} \\ \mathbb{E}[g(z)] \le \frac{1}{m} \sum_{i=1}^m g(z_i) + 2\widehat{\mathfrak{R}}_S(\mathcal{G}) + 3\sqrt{\frac{\log \frac{2}{\delta}}{2m}}\tag{3.4} \end{align}$$

Proof: 定义 $g$ 在 $S$ 上的 empirical average $\widehat{\mathbb{E}}_S[g] = \frac{1}{m} \sum_{i=1}^m g(z_i)$. 对 Sample $S$ 定义

$$\Phi(S) = \sup_{g \in \mathcal{G}} \left(\mathbb{E}[g] - \widehat{\mathbb{E}}_S[g]\right)$$

由于 $\Phi(S) = \sup_{g \in \mathcal{G}} \left(\mathbb{E}[g] - \widehat{\mathbb{E}}_S[g]\right)\geq \mathbb{E}[g] - \widehat{\mathbb{E}}_S[g],\forall g\in \mathcal{G}$，对 $(3.3)$ 仅需证明 $\Phi(S)\leq 2\mathfrak{R}_m(\mathcal{G}) + \sqrt{\frac{\log \frac{1}{\delta}}{2m}}$。

McDiarmid 不等式

对于 $m$ 个独立随机变量 $X_i \in \mathcal{X}$，若函数 $f$ 满足 Lipschitz condition 即 $\vert{}f(X_1, \cdots, X_{i-1}, X_i, X_{i+1}, \cdots, X_m) - f(X_1, \cdots, X_{i-1}, X_i’, X_{i+1}, \cdots, x_m)\vert{} \le c_i$，则对于任意 $\varepsilon > 0$，有：

$$\Pr(f(X_1, \cdots, X_m) - \mathbb{E}[f(X_1, \cdots, X_m)] \ge \varepsilon) \le \exp\left(-\frac{\varepsilon^2}{2\sum_{i=1}^m c_i^2}\right)$$

当 $f$ 为 $\sum$ 时就是 Hoeffding 不等式。

Reference/Bounded_Difference_Method)

考察 $\Phi(S)$ 是否满足 Lipschitz 条件，它是在随机变量 $S=(S_1,S_2,\ldots,S_m)$，那么 $\Phi(S’)-\Phi(S)=\sup\left(\widehat{\mathbb{E}}_S[g]-\widehat{\mathbb{E}}_S’[g]\right)=\sup\left(\frac{1}{m}\left(g(z_i)-g(z’_i)\right)\right)=\frac{1}{m}$，此处不妨 bound 住损失函数 $\mathcal{L}: \mathcal{Y}\times \mathcal{Y}\to \mathcal{R}_{[0,1]}$（因为 $\mathcal{R}$ 与 $\mathcal{R}_{[0,1]}$ 存在双射例如 $\arctan$）。

所以 $\Phi(S)$ 是 $\frac{1}{m}$ Lipschitz 的，故 $\Pr\left(\Phi(S)\leq \mathbb{E}\left[\Phi (S)\right]+t\right) \le \exp\left(-2m{t^2}\right)=\delta$，解得 $t=\sqrt{\frac{\log \frac{1}{\delta}}{2m}}$，w.p. $\geq 1-\delta$。

则 $\Phi(S)\leq \mathbb{E}\left[\Phi (S)\right]+\sqrt{\frac{\log \frac{1}{\delta}}{2m}}$ w.p. $\geq 1-\delta$，现仅需证 $\mathbb{E}\left[\Phi (S)\right]\leq 2\mathfrak{R}_m(\mathcal{G})$

$$\begin{align*} \underset{S}{\mathbb{E}}[\Phi(S)] &= \underset{S}{\mathbb{E}} \left[ \sup_{g \in \mathcal{G}} \left(\mathbb{E}[g] - \widehat{\mathbb{E}}_S(g)\right) \right] \\ &= \underset{S}{\mathbb{E}} \left[ \sup_{g \in \mathcal{G}} \underset{S'}{\mathbb{E}} \left[\widehat{\mathbb{E}}_{S'}(g) - \widehat{\mathbb{E}}_S(g)\right] \right] \tag{3.8} \\ &\le \underset{S, S'}{\mathbb{E}} \left[ \sup_{g \in \mathcal{G}} \left(\widehat{\mathbb{E}}_{S'}(g) - \widehat{\mathbb{E}}_S(g)\right) \right] \tag{3.9} \\ &= \underset{S, S'}{\mathbb{E}} \left[ \sup_{g \in \mathcal{G}} \frac{1}{m} \sum_{i=1}^m (g(z_i') - g(z_i)) \right] \tag{3.10} \\ &= \underset{\boldsymbol{\sigma}, S, S'}{\mathbb{E}} \left[ \sup_{g \in \mathcal{G}} \frac{1}{m} \sum_{i=1}^m \sigma_i (g(z_i') - g(z_i)) \right] \tag{3.11} \\ &\le \underset{\boldsymbol{\sigma}, S'}{\mathbb{E}} \left[ \sup_{g \in \mathcal{G}} \frac{1}{m} \sum_{i=1}^m \sigma_i g(z_i') \right] + \underset{\boldsymbol{\sigma}, S}{\mathbb{E}} \left[ \sup_{g \in \mathcal{G}} \frac{1}{m} \sum_{i=1}^m -\sigma_i g(z_i) \right] \tag{3.12} \\ &= 2 \underset{\boldsymbol{\sigma}, S}{\mathbb{E}} \left[ \sup_{g \in \mathcal{G}} \frac{1}{m} \sum_{i=1}^m \sigma_i g(z_i) \right] = 2\mathfrak{R}_m(\mathcal{G}). \tag{3.13} \end{align*}$$

$(3.8)$ 到 $(3.9)$ 是由于 $\sup$ 存在 sub-additivity 次可加性，即 $\sup f+\sup g\geq \sup(f+g)$，把内部的期望拆出来即可。其中 $(3.10)$ 到 $(3.11)$ 中引入了噪声，因为 $S$ 和 $S’$ 都是 i.i.d. 的，所以任意交换 $z$ 和 $z’$ 的位置不会影响期望。 $(3.12)$ 依然是利用 sub-additivity。自此，证明了 $\Phi(S)\leq 2\mathfrak{R}_m(\mathcal{G})+\sqrt{\frac{\log \frac{1}{\delta}}{m}}$ w.p. $\geq 1-\delta$，则 $(3.3)$ 自然成立。

对于 $(3.4)$，对 $\mathfrak{R}_m(\mathcal{G}) = \mathbb{E}[\widehat{\mathfrak{R}}_S(\mathcal{G})]$ 运用 McDiarmid inequality 得到 w.p. $\geq 1-\delta$，$\mathfrak{R}_m(\mathcal{G})\leq \widehat{\mathfrak{R}}_S(\mathcal{G})+\sqrt{\frac{\log\frac{1}{\delta}}{2m}}$。为了统一 probability，在 $(3.3)$ 和此处均取 w.p. $\geq 1-\frac{\delta}{2}$，那么均满足的概率 $\geq 1-\delta$。，此时联合 $\mathbb{E}[g(z)] \le \frac{1}{m} \sum_{i=1}^m g(z_i) + 2\mathfrak{R}_m(\mathcal{G}) + \sqrt{\frac{\log \frac{2}{\delta}}{2m}}$ 和 $\mathfrak{R}_m(\mathcal{G})\leq \widehat{\mathfrak{R}}_S(\mathcal{G})+\sqrt{\frac{\log\frac{2}{\delta}}{2m}}$，就得到 $(3.4)$。

Theorem 3.3 给予我们一个通过 Rademacher complexity 用 empirical error 给 generalization error 定界的一个方法。

Theorem 2

Lemma 3.4 Let $\mathcal{H}$ be a family of functions taking values in $\{-1, +1\}$ and let $\mathcal{G}$ be the family of loss functions associated to $\mathcal{H}$ for the zero-one loss: $\mathcal{G} = \{(x, y) \mapsto 1_{h(x) \neq y} : h \in \mathcal{H}\}$. 即 $\{-1,+1\}$ 的损失函数与对应 01 损失函数集合，empirical error 呈两倍关系

For any sample $S = ((x_1, y_1), \dots, (x_m, y_m))$ of elements in $\mathcal{X} \times \{-1, +1\}$, let $S_{\mathcal{X}}$ denote its projection over $\mathcal{X}$: $S_{\mathcal{X}} = (x_1, \dots, x_m)$. Then, the following relation holds between the empirical Rademacher complexities of $\mathcal{G}$ and $\mathcal{H}$:

$$\widehat{\mathfrak{R}}_S(\mathcal{G}) = \frac{1}{2} \widehat{\mathfrak{R}}_{S_{\mathcal{X}}}(\mathcal{H})$$

Proof: 对于 $y, h(x) \in \{-1, +1\}$，01 损失可以表示为 $1_{h(x) \neq y} = \frac{1 - y \cdot h(x)}{2}$ 代回原式得证。

Theorem 3.5 (Rademacher complexity bounds – binary classification) $\mathcal{H}$ 为假设空间，$h\in \mathcal{H}$ 满足 $h(x)\in \{-1,+1\},\forall \delta>0$:

$$\begin{align} R(h) &\le \widehat{R}_S(h) + \mathfrak{R}_m(\mathcal{H}) + \sqrt{\frac{\log \frac{1}{\delta}}{2m}} \tag{3.17} \\ R(h) &\le \widehat{R}_S(h) + \widehat{\mathfrak{R}}_S(\mathcal{H}) + 3\sqrt{\frac{\log \frac{2}{\delta}}{2m}} \tag{3.18} \end{align}$$

由 Theorem 3.3 和 Lemma 3.4 即证。为了让 bound 住的界更紧，即 minimize $\underset{\boldsymbol{\sigma}}{\mathbb{E}}\left[\inf\limits_{g \in \mathcal{G}} \frac{1}{m} \sum\limits_{i=1}^m \sigma_i g(z_i)\right]$，这个问题叫作 Empirical Risk Minimization (ERM)，对 classification problem with a 0-1 loss function 是 NP-Hard 问题。