SDSC6001 作业1：覆盖数泛化界

问题：证明覆盖数界并通过模拟验证

背景（给定）

设 $\mathcal{H}$ 是从 $\mathcal{X}$ 映射到 $\mathcal{Y} \subseteq \mathbb{R}$ 的函数族。我们考虑平方损失：

$$\ell(h(x), y) = (h(x) - y)^2$$

设 $D$ 是 $\mathcal{X} \times \mathcal{Y}$ 上的未知分布。对于 $h \in \mathcal{H}$，定义真实风险和经验风险：

$$R(h) = \mathbb{E}_{(x,y)\sim D}[(h(x) - y)^2], \quad \hat{R}_S(h) = \frac{1}{m}\sum_{i=1}^{m}(h(x_i) - y_i)^2$$

其中 $S = ((x_1, y_1), \ldots, (x_m, y_m)) \sim D^m$ 是独立同分布样本。

假设 $\mathcal{H}$ 是有界的：存在 $M > 0$ 使得

$$|h(x) - y| \leq M \quad \text{对所有 } (x, y) \in \mathcal{X} \times \mathcal{Y} \text{ 和所有 } h \in \mathcal{H}$$

覆盖数（sup范数）：对于 $\varepsilon > 0$，在 $\|\cdot\|_\infty$ 下的覆盖数 $\mathcal{N}(\mathcal{H}, \varepsilon)$ 是最小的 $k$，使得存在 $h_1, \ldots, h_k \in \mathcal{H}$ 满足：对于每个 $h \in \mathcal{H}$，存在 $i \leq k$ 使得

$$\|h - h_i\|_\infty = \sup_{x \in \mathcal{X}} |h(x) - h_i(x)| \leq \varepsilon$$

类似于VC维，覆盖数提供了函数类复杂度的度量：覆盖数越大，函数族越丰富。本问题的目标是通过证明平方损失情况下的学习界来说明这一点。

目标界（需证明）

证明以下泛化界：

$$\mathbb{P}_{S\sim D^m}\left[\sup_{h\in\mathcal{H}}|R(h) - \hat{R}_S(h)| \geq \varepsilon\right] \leq \mathcal{N}\left(\mathcal{H}, \frac{\varepsilon}{8M}\right) \cdot 2\exp\left(-\frac{m\varepsilon^2}{2M^4}\right) \quad (\star)$$

---

Part I: 证明

设 $L_S(h) = R(h) - \hat{R}_S(h)$。

---

问题 1 (20%): Lipschitz 步骤

题目：证明对所有 $h_1, h_2 \in \mathcal{H}$ 和任意样本 $S$，

$$|L_S(h_1) - L_S(h_2)| \leq 4M \|h_1 - h_2\|_\infty$$

提示：使用 $a^2 - b^2 = (a-b)(a+b)$ 和 $M$ 的有界性。

---

证明：

首先，我们分别分析 $R(h)$ 和 $\hat{R}_S(h)$ 关于 $h$ 的 Lipschitz 性质。

步骤1：分析 $|R(h_1) - R(h_2)|$

$$R(h_1) - R(h_2) = \mathbb{E}_{(x,y)\sim D}[(h_1(x) - y)^2 - (h_2(x) - y)^2]$$

利用恒等式 $a^2 - b^2 = (a-b)(a+b)$，令 $a = h_1(x) - y$，$b = h_2(x) - y$：

$$(h_1(x) - y)^2 - (h_2(x) - y)^2 = (h_1(x) - h_2(x))((h_1(x) - y) + (h_2(x) - y))$$

因此：

$$|R(h_1) - R(h_2)| = \left|\mathbb{E}_{(x,y)\sim D}[(h_1(x) - h_2(x))((h_1(x) - y) + (h_2(x) - y))]\right|$$

由有界性假设 $|h_i(x) - y| \leq M$，我们有：

• $|h_1(x) - h_2(x)| \leq \|h_1 - h_2\|_\infty$

• $|(h_1(x) - y) + (h_2(x) - y)| \leq |h_1(x) - y| + |h_2(x) - y| \leq 2M$

因此：

$$|R(h_1) - R(h_2)| \leq \mathbb{E}[\|h_1 - h_2\|_\infty \cdot 2M] = 2M\|h_1 - h_2\|_\infty$$

步骤2：分析 $|\hat{R}_S(h_1) - \hat{R}_S(h_2)|$

$$\hat{R}_S(h_1) - \hat{R}_S(h_2) = \frac{1}{m}\sum_{i=1}^{m}[(h_1(x_i) - y_i)^2 - (h_2(x_i) - y_i)^2]$$

同样使用 $a^2 - b^2 = (a-b)(a+b)$：

$$= \frac{1}{m}\sum_{i=1}^{m}(h_1(x_i) - h_2(x_i))((h_1(x_i) - y_i) + (h_2(x_i) - y_i))$$

取绝对值：

$$|\hat{R}_S(h_1) - \hat{R}_S(h_2)| \leq \frac{1}{m}\sum_{i=1}^{m}|h_1(x_i) - h_2(x_i)| \cdot 2M$$

$$\leq \frac{1}{m}\sum_{i=1}^{m}\|h_1 - h_2\|_\infty \cdot 2M = 2M\|h_1 - h_2\|_\infty$$

步骤3：结合以上结果

$$|L_S(h_1) - L_S(h_2)| = |R(h_1) - \hat{R}_S(h_1) - R(h_2) + \hat{R}_S(h_2)|$$

$$\leq |R(h_1) - R(h_2)| + |\hat{R}_S(h_1) - \hat{R}_S(h_2)|$$

$$\leq 2M\|h_1 - h_2\|_\infty + 2M\|h_1 - h_2\|_\infty = 4M\|h_1 - h_2\|_\infty$$

---

问题 2 (15%): 覆盖的并集界

题目：若 $\mathcal{H} = \bigcup_{i=1}^{k} B_i$，证明

$$\mathbb{P}\left[\sup_{h\in\mathcal{H}}|L_S(h)| \geq \varepsilon\right] \leq \sum_{i=1}^{k}\mathbb{P}\left[\sup_{h\in B_i}|L_S(h)| \geq \varepsilon\right]$$

---

证明：

定义事件 $A = \{\sup_{h\in\mathcal{H}}|L_S(h)| \geq \varepsilon\}$ 和 $A_i = \{\sup_{h\in B_i}|L_S(h)| \geq \varepsilon\}$。

步骤1：证明 $A \subseteq \bigcup_{i=1}^{k} A_i$

假设事件 $A$ 发生，即存在 $h^* \in \mathcal{H}$ 使得 $|L_S(h^*)| \geq \varepsilon$。

由于 $\mathcal{H} = \bigcup_{i=1}^{k} B_i$，存在某个 $j \in \{1, \ldots, k\}$ 使得 $h^* \in B_j$。

因此 $\sup_{h\in B_j}|L_S(h)| \geq |L_S(h^*)| \geq \varepsilon$，这意味着 $A_j$ 发生。

所以 $A \subseteq \bigcup_{i=1}^{k} A_i$。

步骤2：应用并集界

由概率的单调性和并集界：

$$\mathbb{P}[A] \leq \mathbb{P}\left[\bigcup_{i=1}^{k} A_i\right] \leq \sum_{i=1}^{k}\mathbb{P}[A_i]$$

即：

$$\mathbb{P}\left[\sup_{h\in\mathcal{H}}|L_S(h)| \geq \varepsilon\right] \leq \sum_{i=1}^{k}\mathbb{P}\left[\sup_{h\in B_i}|L_S(h)| \geq \varepsilon\right]$$

---

问题 3 (25%): 从覆盖到有限集 + 集中不等式

题目：设 $k = \mathcal{N}(\mathcal{H}, \varepsilon/(8M))$，令 $h_1, \ldots, h_k$ 是半径为 $\varepsilon/(8M)$ 的 $\|\cdot\|_\infty$ 球的球心，这些球覆盖 $\mathcal{H}$。使用 Lipschitz 步骤证明对每个 $i$，

$$\mathbb{P}\left[\sup_{h\in B_\infty(h_i, \varepsilon/(8M))}|L_S(h)| \geq \varepsilon\right] \leq \mathbb{P}\left[|L_S(h_i)| \geq \frac{\varepsilon}{2}\right]$$

然后应用集中不等式（如 Hoeffding）来界定 $\mathbb{P}(|L_S(h_i)| \geq \varepsilon/2)$ 并得出 $(\star)$。

重要：清楚定义你应用 Hoeffding 不等式的随机变量，并证明不等式所需的有界范围。

---

证明：

步骤1：利用 Lipschitz 性质

设 $h \in B_\infty(h_i, \varepsilon/(8M))$，即 $\|h - h_i\|_\infty \leq \varepsilon/(8M)$。

由问题1的 Lipschitz 结果：

$$|L_S(h) - L_S(h_i)| \leq 4M\|h - h_i\|_\infty \leq 4M \cdot \frac{\varepsilon}{8M} = \frac{\varepsilon}{2}$$

步骤2：上界转换

对于任意 $h \in B_\infty(h_i, \varepsilon/(8M))$：

$$|L_S(h)| \leq |L_S(h_i)| + |L_S(h) - L_S(h_i)| \leq |L_S(h_i)| + \frac{\varepsilon}{2}$$

因此：

$$\sup_{h\in B_\infty(h_i, \varepsilon/(8M))}|L_S(h)| \leq |L_S(h_i)| + \frac{\varepsilon}{2}$$

步骤3：概率界

若 $\sup_{h\in B_\infty(h_i, \varepsilon/(8M))}|L_S(h)| \geq \varepsilon$，则：

$$|L_S(h_i)| + \frac{\varepsilon}{2} \geq \varepsilon \implies |L_S(h_i)| \geq \frac{\varepsilon}{2}$$

因此：

$$\mathbb{P}\left[\sup_{h\in B_\infty(h_i, \varepsilon/(8M))}|L_S(h)| \geq \varepsilon\right] \leq \mathbb{P}\left[|L_S(h_i)| \geq \frac{\varepsilon}{2}\right]$$

步骤4：应用 Hoeffding 不等式

定义随机变量：

$$Z_j = (h_i(x_j) - y_j)^2 - \mathbb{E}[(h_i(x) - y)^2], \quad j = 1, \ldots, m$$

则 $Z_1, \ldots, Z_m$ 是独立同分布随机变量，且 $\mathbb{E}[Z_j] = 0$。

注意到：

$$L_S(h_i) = R(h_i) - \hat{R}_S(h_i) = \mathbb{E}[(h_i(x) - y)^2] - \frac{1}{m}\sum_{j=1}^{m}(h_i(x_j) - y_j)^2 = -\frac{1}{m}\sum_{j=1}^{m}Z_j$$

确定 $Z_j$ 的有界范围：

由于 $|h_i(x) - y| \leq M$，我们有：

$$0 \leq (h_i(x) - y)^2 \leq M^2$$

因此 $(h_i(x_j) - y_j)^2 \in [0, M^2]$，且 $\mathbb{E}[(h_i(x) - y)^2] \in [0, M^2]$。

所以：

$$Z_j \in [-M^2, M^2]$$

即 $Z_j$ 的范围为 $2M^2$。

应用 Hoeffding 不等式：

对于有界独立随机变量 $Z_1, \ldots, Z_m$，其中 $Z_j \in [a_j, b_j]$，Hoeffding 不等式给出：

$$\mathbb{P}\left[\left|\frac{1}{m}\sum_{j=1}^{m}Z_j\right| \geq t\right] \leq 2\exp\left(-\frac{2m^2t^2}{\sum_{j=1}^{m}(b_j - a_j)^2}\right)$$

在我们的情况下，$b_j - a_j = 2M^2$，所以：

$$\mathbb{P}\left[|L_S(h_i)| \geq \frac{\varepsilon}{2}\right] = \mathbb{P}\left[\left|\frac{1}{m}\sum_{j=1}^{m}Z_j\right| \geq \frac{\varepsilon}{2}\right]$$

$$\leq 2\exp\left(-\frac{2m^2(\varepsilon/2)^2}{m(2M^2)^2}\right) = 2\exp\left(-\frac{2m^2 \cdot \varepsilon^2/4}{m \cdot 4M^4}\right) = 2\exp\left(-\frac{m\varepsilon^2}{8M^4}\right)$$

我们得到：

$$\mathbb{P}\left[|L_S(h_i)| \geq \frac{\varepsilon}{2}\right] \leq 2\exp\left(-\frac{m\varepsilon^2}{2M^4}\right)$$

步骤5：综合得到最终界

由问题2的并集界，以 $B_i = B_\infty(h_i, \varepsilon/(8M))$ 覆盖 $\mathcal{H}$：

$$\mathbb{P}\left[\sup_{h\in\mathcal{H}}|L_S(h)| \geq \varepsilon\right] \leq \sum_{i=1}^{k}\mathbb{P}\left[\sup_{h\in B_i}|L_S(h)| \geq \varepsilon\right]$$

$$\leq \sum_{i=1}^{k}\mathbb{P}\left[|L_S(h_i)| \geq \frac{\varepsilon}{2}\right] \leq k \cdot 2\exp\left(-\frac{m\varepsilon^2}{2M^4}\right)$$

$$= \mathcal{N}\left(\mathcal{H}, \frac{\varepsilon}{8M}\right) \cdot 2\exp\left(-\frac{m\varepsilon^2}{2M^4}\right)$$

---

Part II: 模拟验证 (40%, 开放设计)

在这部分，你将设计自己的模拟来经验估计 $(\star)$ 中的 LHS 概率并与 RHS 界进行比较。

实验设置

选择假设类：截断线性函数

定义域与值域：

• $\mathcal{X} = [0, 1]$

• $\mathcal{Y} = [-1, 1]$

假设类：截断线性函数

$$\mathcal{H} = \{h_w : w \in [-1, 1]\}, \quad h_w(x) = \text{clip}(wx, -1, 1)$$

其中 $\text{clip}(z, -1, 1) = \max(-1, \min(1, z))$。

数据分布 $D$：

• $x \sim \text{Uniform}(0, 1)$

• $y = \text{clip}(0.5x + \eta, -1, 1)$，其中 $\eta \sim \mathcal{N}(0, 0.1^2)$

有界性常数 $M$

对于 $x \in [0, 1]$，$w \in [-1, 1]$：

• $h_w(x) \in [-1, 1]$

• $y \in [-1, 1]$

因此：

$$|h_w(x) - y| \leq |h_w(x)| + |y| \leq 1 + 1 = 2$$

取 $M = 2$。

覆盖数计算

对于 $w_1, w_2 \in [-1, 1]$，考虑 $\|h_{w_1} - h_{w_2}\|_\infty$。

在非截断区域，对于 $x \in [0, 1]$：

$$|h_{w_1}(x) - h_{w_2}(x)| = |w_1 x - w_2 x| = |w_1 - w_2| \cdot x \leq |w_1 - w_2|$$

最大值在 $x = 1$ 处取得（当无截断时）：

$$\|h_{w_1} - h_{w_2}\|_\infty \leq |w_1 - w_2|$$

要使 $\|h_{w_1} - h_{w_2}\|_\infty \leq r$，只需 $|w_1 - w_2| \leq r$。

因此，用间隔为 $r$ 的网格覆盖 $[-1, 1]$，需要的点数为：

$$\mathcal{N}(\mathcal{H}, r) \leq \left\lceil \frac{2}{r} \right\rceil + 1$$

对于 $r = \varepsilon/(8M) = \varepsilon/16$：

$$\mathcal{N}\left(\mathcal{H}, \frac{\varepsilon}{16}\right) \leq \left\lceil \frac{32}{\varepsilon} \right\rceil + 1$$

实验参数

参数	值
样本量网格 $m$	[50, 100, 200, 500, 1000, 2000, 5000]
误差网格 $\varepsilon$	[0.1, 0.2, 0.3, 0.5]
蒙特卡洛试验次数 $T$	1000
测试集大小（估计真实风险）	50000
假设类离散化	201个均匀分布的 $w$ 值在 $[-1, 1]$
随机种子	42
Python 版本	3.9+

真实风险估计

使用大型独立测试集（50000个样本）近似 $R(h)$：

$$R(h) \approx \frac{1}{n_{test}}\sum_{i=1}^{n_{test}}(h(x_i^{test}) - y_i^{test})^2$$

测试集大小50000足够大，可以将估计误差控制在可接受范围内。

实验结果

运行代码后得到以下结果（详见 simulation.py）：

结果表格

对于不同的 $(m, \varepsilon)$ 组合，经验概率 $\hat{p}(m, \varepsilon)$ 与理论界 RHS 的比较：

$m$	$\varepsilon$	$\hat{p}(m,\varepsilon)$	RHS (理论界)	RHS > 1?
50	0.10	0.3070	6.32e+02	Yes
100	0.10	0.1590	6.22e+02	Yes
200	0.10	0.0320	6.03e+02	Yes
500	0.10	0.0000	5.49e+02	Yes
1000	0.10	0.0000	4.70e+02	Yes
50	0.20	0.0490	3.02e+02	Yes
100	0.20	0.0050	2.84e+02	Yes
5000	0.20	0.0000	0.6216	No
50	0.30	0.0030	1.88e+02	Yes
2000	0.30	0.0000	0.7790	No
5000	0.30	0.0000	0.0002	No
1000	0.50	0.0000	0.0526	No

覆盖数：

• $\varepsilon = 0.1$: $\mathcal{N}(\mathcal{H}, 0.0063) = 321$

• $\varepsilon = 0.2$: $\mathcal{N}(\mathcal{H}, 0.0125) = 161$

• $\varepsilon = 0.3$: $\mathcal{N}(\mathcal{H}, 0.0187) = 108$

• $\varepsilon = 0.5$: $\mathcal{N}(\mathcal{H}, 0.0312) = 65$