# 霍夫丁不等式 和 泛化误差上界

## 1. Hoeffding Inequality

\begin{aligned} P \Big[ \overline { X } – E [ \overline { X } ] \geq t \Big] \leq \exp \Bigg( – \frac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg) \end{aligned}

\begin{aligned} P \Big[ E [ \overline { X } ] – \overline { X } \leq t \Big] \leq \exp \Bigg( – \frac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg) \end{aligned}

ps：本文为了好看，所有求概率、求期望，均使用方括号。

### 1.1 Markov Inequality

$$P[X>\lambda] \le \frac{E[X]}{\lambda}$$

\begin{aligned} E[X] =& \int_0^\infty xp(x)dx \ge \int_{\lambda}^\infty xp(x)dx\\ \ge& \lambda\int_{\lambda}^\infty p(x)dx = \lambda P[X\ge \lambda] \end{aligned}

$$P[f(X)>f(\lambda)] \le \frac{E[f(X)]}{f(\lambda)}$$

$$P[X>\lambda] = P[f(X)>f(\lambda)] \le \frac{E[f(X)]}{f(\lambda)}$$

（这理论我是在 [4] 看到的，记得之前在方浩概率论的视频里也看到过，具体证明还 #TODO）

### 1.2 Chebyshev Bound

Chebyshev Bound 就是对上面定理的应用，我们令 $f(X) = (X-E[X])^2$，则

$$P[|X-E[X]|\ge\lambda] = P[(X-E[X])^2\ge \lambda^2] \le \frac{E[(X-E[X])^2]}{\lambda^2} = \frac{var(X)}{\lambda^2}$$

### 1.3 Chernoff Bound

$$P[X\ge E[X] + t] \le \mathop{\min_{\lambda \ge 0}} \dfrac{E[e^{\lambda (X-E[X])}]}{e^{\lambda t}}$$

$$P[X\le E[X] – t] \le \mathop{\min_{\lambda \ge 0}} \dfrac{E[e^{\lambda (E[X]-X)}]}{e^{\lambda t}}$$

$$e^{\lambda X} \ge e^{\lambda E[X] + \lambda t}$$ $$e^{\lambda (X-E[X])} \ge e^{\lambda t}$$

$$P[X-E[X]\ge t] = P[e^{\lambda(X-E[X])}\ge e^{\lambda t}] \le \frac{E[e^{\lambda(X-E[X])}]}{e^{\lambda t}}$$

### 1.4 Hoeffding Lemma

$$E(e^{\lambda X})\le \exp\Big(\dfrac{\lambda^2(b-a)^2}{8}\Big)$$

$$f(x)\le \alpha f(a) + (1-\alpha)f(b)$$

$$e^{\lambda x} \le \frac{b-x}{b-a}e^{\lambda a} + \frac{x-a}{b-a}e^{\lambda b}$$

$$E(e^{\lambda X}) \le \frac{b}{b-a}e^{\lambda a} – \frac{a}{b-a}e^{\lambda b}$$

\begin{aligned} \exp\Big(L(h)\Big) =& \exp\Big(-hp+\ln(1-p+pe^h)\Big) \\ =& (1-p+pe^h)e^{-hp}\\ =& \frac{b}{b-a}e^{\lambda a} – \frac{a}{b-a} e^{\lambda b} \end{aligned}

$$g(h) = L(h) – \frac{h^2}{8} = -hp + \ln(1-p+pe^h) – \frac{h^2}{8} \le 0,\;(h>0)$$

$$g'(h) = -p + \dfrac{pe^h}{1-p+pe^h} – \dfrac{h}{4}$$

$$g”(h) = \frac{(1-p)pe^h}{1-p+pe^h} – \frac{1}{4}$$

$$g”(h) = \frac{mn}{(m+n)^2} – \frac{1}{4} = \dfrac{1}{\frac{n}{m} + \frac{m}{n} + 2} – \frac{1}{4} \le 0$$

### 1.5 Hoeffding Inequality 证明

Chernoff Bound：$P\Big[X\ge E[X] + t\Big] \le \dfrac{E[e^{\lambda (X-E[X])}]}{e^{\lambda t}}$

Hoeffding Lemma：$E(e^{\lambda X})\le \exp\Big(\dfrac{\lambda^2(b-a)^2}{8}\Big)$

\begin{aligned} P \Big[ \overline { X } – E ( \overline { X } ) \geq t \Big] =& P \Big[ \frac{1}{N}\sum_{i=1}^N (X_i – E[X_i]) \geq t \Big] \\ =& P \Big[ \sum_{i=1}^N (X_i – E[X_i]) \geq Nt \Big] \\ \le& E \Big[\exp\Big( \lambda\sum_{i=1}^N(X_i – E[X_i])\Big)\Big] e^{-\lambda Nt} \\ =& \Big( \prod_{i=1}^N E[e^{\lambda(X_i – E[X_i])}]\Big) e^{-\lambda Nt} \\ \le& \Big( \prod_{i=1}^N \frac{\lambda^2(b_i-a_i)^2}{8}\Big) e^{-\lambda Nt} \\ =& \exp \Big(\frac{\lambda^2\sum_{i=1}^N(b_i-a_i)^2}{8} – \lambda Nt\Big) \end{aligned}

$$P \Big[ \overline { X } – E ( \overline { X } ) \geq t \Big] \le \mathop{\min_{\lambda \ge 0}} \exp \Big(\frac{\lambda^2\sum_{i=1}^N(b_i-a_i)^2}{8} – \lambda Nt\Big) = \exp \Big( – \frac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Big)$$

## 2. 泛化误差上界

$$P \Big[ E [ \overline { X }] – \overline { X } \geq t \Big] \leq \exp \Bigg( – \dfrac { 2 N^ { 2 }t ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg)$$

$$R(f)\le\hat{R}(f) + \varepsilon(d,N,\delta)$$

$$\varepsilon(d,N,\delta) = \sqrt{\frac{1}{2N}(\log d + \log \frac{1}{\delta})}$$

$$P \Big[ E [ S_N ] – S_N\geq N\varepsilon \Big] \leq \exp \Bigg( – \dfrac { 2(N\varepsilon) ^ { 2 } } {\sum _ { i = 1 } ^ { n } ( b _ { i } – a _ { i } ) ^ { 2 }} \Bigg)$$

$$P \Big[ E [ S_N ] – S_N \geq N\varepsilon \Big] \leq \exp ( – 2N\varepsilon^2 )$$

$$P \Big[ R(f) – \hat{R}(f) \geq \varepsilon \Big] \leq \exp ( – 2N\varepsilon^2 )$$

$\mathcal{F} = {f_a,f_2,…,f_d}$ 是一个有限集合，上面的十字表明 $\mathcal{F}$ 中的任何一个函数 $f$ 作为模型时 的泛化误差的上限。如果要求 $\mathcal{F}$ 中存在某个 $f$ 满足这个式子，则由概率的加和规则可以得到，对于 $\forall f\in \mathcal{F}$，有

\begin{aligned} & P \Big[\exists f \in \mathcal{F}: R(f) – \hat{R}(f)\geq \varepsilon \Big] \\ =& P \Big[ \bigcup_{f \in \mathcal{F}} { R(f) – \hat{R}(f)\geq \varepsilon } \Big] \\ \le&\sum_{f \in \mathcal{F}} P \Big[ R(f) – \hat{R}(f) \geq \varepsilon \Big]\\ \le&d \exp ( – 2N\varepsilon^2 ) \end{aligned}

$$P \Big[R(f) – \hat{R}(f) < \varepsilon \Big] \ge 1- d \exp ( – 2N\varepsilon^2 )$$

$$P \Big[R(f) < \hat{R}(f) + \varepsilon \Big] \ge 1- \delta$$

## 3. 本文的不足

1. 关于 Markov Inequality 的证明还没有。
2. [3] 中用杰森不等式证明 Hoeffding Lemma，虽然差个系数，但是也值得看一下
3. 在我的文章里，Hoeffding Lemma 要求 $E[X] = 0$，但是在 1.5 忽视了这个问题。总之，还是 Hoeffding Lemma 证明还有缺陷。

## 4. 引用与延伸阅读

[1] CS229 Supplemental Lecture notes Hoeffding’s inequality 写得真是好，是本文主要抄袭来源，推荐阅读原文。

[2] Hoeffding不等式证明 前半部分挺好，就是最后推导的是 Hoeffding Inequality 的第一种形式。

[3] 关于Hoeffding不等式及泛化误差上界 我最反感这种拼凑的博客了，难以下咽，不过对我还是有一点帮助

[4] Chernoff bound 只看了前面一小部分，没太大用

[5] Hoeffding不等式的证明 这篇文章很多错，不过对我还是有一点帮助

[6] 泛化误差上界（证明详推）