不等式
Hoeffding Lemma: For r.v. $X\in [a,b]$ and $\lambda\in\mathbb R$, it holds
$$ \mathbb E[\mathrm e^{\lambda(X-\mathbb E[X])}] \leq \exp\left(\frac{\lambda^2(b-a)^2}{8}\right). $$Especially, for $X\in [0,1]$, we have
$$ \mathbb E[\mathrm e^{\lambda(X-\mathbb E[X])}] \leq \mathrm e^{\lambda^2/8}. $$Markov Inequality: For a non-negative r.v. $X$ and $a>0$, it holds
$$ \mathbb P(X\geq a) \leq \frac{\mathbb E[X]}{a}. $$Hoeffding Inequality: Let $X_1,\ldots,X_m$ be independent r.v.s with $X_i\in [a_i,b_i]$. Then for any $\varepsilon>0$,
$$ \mathbb P\left(\sum_{i=1}^m(X_i-\mathbb E[X_i])\geq \varepsilon\right) \leq \exp\left(-\frac{2\varepsilon^2}{\sum_{i=1}^m(b_i-a_i)^2}\right). $$Especially, for $X_i\in [0,1]$, we have
$$ \mathbb P\left(\sum_{i=1}^m(X_i-\mathbb E[X_i])\geq \varepsilon\right) \leq \mathrm e^{-2\varepsilon^2m}.$$12
默认损失函数 $l(h,Z)\in [0,1]$.
有限假设类
有限假设类是 $|\mathcal H|<\infty$ 的假设类。应用 Hoeffding 不等式可以控制，得到有限假设类的一致收敛定理
$$\begin{equation}\mathbb P_{\mathcal S\sim P^m}\left(\sup_{h\in\mathcal H}\left|\hat L_{\mathcal S}(h)-L_{\mathcal P}(h)\right|\geq \varepsilon\right)\leq 2|\mathcal H|\mathrm e^{-2m\varepsilon^2}\leq \delta, \end{equation}$$一致收敛定理说明控制统一偏差 $(\varepsilon,\delta)$ 的样本复杂度依赖为
$$m_{\mathcal H}^{UC}(\varepsilon,\delta)=\mathcal O\left(\dfrac {\log |\mathcal H|-\log \delta}{\varepsilon^2}\right),$$而通过枚举计算 ERM 的时间复杂度为 $\mathcal O(|\mathcal H|)$，统计上需要少量样本，但不说明计算上能高效找到假设 $\hat h\in\mathcal H$，最坏时间指数级增加。作为推论，有限假设类的 ERM 算法是 agnostic-PAC 可学习的。
VC 维
对于二分类假设类 $\mathcal H\subset \{0,1\}^{\mathcal X}$，其 VC 维定义为
$$ \mathrm{VCdim}(\mathcal H)=\sup\{m\in\mathbb N:\tau_{\mathcal H}(m)=2^m\}.$$有限假设类的 VC 维不超过 $\lfloor \log_2 |\mathcal H|\rfloor$。VC 维刻画是否存在长度为 $\mathrm{VCdim}(\mathcal H)$ 的样本集 $\mathcal C\subset \mathcal X$，使得 $\mathcal H$ 打散 $\mathcal C$，不能仅单独验证某个假设在某个样本集上的标签。打散衡量假设类的复杂度，来刻画它能记住任意标签模式的能力
$$\exists \mathcal C=\{x_1,\ldots,x_m\}\subset \mathcal X, \forall \mathbf y\in\{0,1\}^m, \exists h_{\mathbf y}\in\mathcal H,\forall i\in[m], h_{\mathbf y}(x_i)=y_i.$$二分类假设类
Sauer-Shelah-Perles 引理指出，对于有限 VC 维不超过 $d$ 的二分类假设类 $\mathcal H$，对 $m\in\mathbb N$，其增长函数满足
$$\tau_{\mathcal H}(m)\leq \sum_{i=0}^{d}\binom{m}{i}.$$特别地，当 $1\leq d\leq m$ 时，有进一步估计
$$\tau_{\mathcal H}(m)\leq \left(\frac{\mathrm em}{d}\right)^d.$$这说明 $\tau_{\mathcal H}(m)=\mathcal O(m^d)$ 是多项式级增长。即便 $\mathcal H$ 可能是不可数的，但其有效分类能力是有限的。