霍夫丁不等式

1. 简介

在概率论中，霍夫丁不等式（Hoeffding’s Inequality）给出了有界独立随机变量之和偏离其均值超过一定数量的概率上界。霍夫不等式是切比雪夫界的推广，同时又是吾妻不等式和McDiarmid不等式（还没给出标准的中文翻译2333）。霍夫丁不等式是机器学习的基础理论。

2. 定义

假设 $\boldsymbol{X}_1,\boldsymbol{X}_2,\cdots,\boldsymbol{X}_N$ 是独立随机变量，且 $\boldsymbol{X}_i \in [a_i,b_i]$ ， $i = 1,2,\cdots,N$ ； $\bar{\boldsymbol{X}}$ 是 $\boldsymbol{X}_1,\boldsymbol{X}_2,\cdots,\boldsymbol{X}_N$ 的经验均值，即 $\bar{\boldsymbol{X}} = \frac{1}{N} \sum_{i=1}^N \boldsymbol{X}_i$ ，则对任意 $t \gt 0$ ，以下霍夫丁不等式成立：

$\begin{array}{c} P[\bar{\boldsymbol{X}} - E(\bar{\boldsymbol{X}}) \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} \\ P[E(\bar{\boldsymbol{X}}) - \bar{\boldsymbol{X}} \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})} \\ \end{array}$

证明

由霍夫丁引理可得

$\begin{array}{cc} E(e^{s(\boldsymbol{X}-E(\boldsymbol{X}))}) \leq \exp{(\frac{1}{8} s^2 (b_i - a_i)^2)} & (1 \leq i \leq n) \end{array}$

令 $\boldsymbol{S}_n = \boldsymbol{X}_1 + \boldsymbol{X}_2 + \cdots + \boldsymbol{X}_n$ ，对于 $\forall s,t \gt 0$ ，可得

$\begin{array}{c} P(\boldsymbol{S}_n - E(\boldsymbol{S}_n) \geq t) = P(e^{s(S_n - E(S_n))} \geq e^{st}) \end{array}$

进一步根据马尔可夫不等式和 $\boldsymbol{X}_i$ 之间的独立性可得

$\begin{array}{rl} P(e^{s(S_n - E(S_n))} \geq e^{st}) & \leq e^{-st} E(e^{s(\boldsymbol{S}_n-E(\boldsymbol{S}_n))}) \\ & = e^{-st} \prod_{i=1}^n E(e^{s(\boldsymbol{X}_i-E(\boldsymbol{X}_i))}) \\ & \leq e^{-st} \prod_{i=1}^n e^{\frac{s^2(b_i-a_i)^2}{8}} \\ & = \exp{(-st + \frac{1}{8} s^2 \sum_{i=1}^n (b_i - a_i)^2)} \end{array}$

令 $g(s) = -st + \frac{s^2}{8} \sum_{i=1}^n (b_i - a_i)^2$ ，则 $g(s)$ 为关于 $s$ 的二次函数，从而易得

$\begin{array}{c} s = \frac{4t}{\sum_{i=1}^n (b_i - a_i)^2} \end{array}$

为 $g(s)$ 的最小值点。由于

$\begin{array}{c} P(e^{s(S_n - E(S_n))} \geq e^{st}) \leq \exp{(-st + \frac{1}{8} s^2 \sum_{i=1}^n (b_i - a_i)^2)} \end{array}$

对 $\forall s \gt 0$ 都成立，因此当 $s$ 取 $g(s)$ 的最小值点时，得到 $P(e^{s(S_n - E(S_n))} \geq e^{st})$ 的紧上界，即

$\begin{array}{c} P(e^{s(S_n - E(S_n))} \geq e^{st}) \leq \exp{(-\frac{2t^2}{\sum_{i=1}^n (b_i - a_i)^2})} \end{array}$

最终简单变换后可得 $P[\bar{\boldsymbol{X}} - E(\bar{\boldsymbol{X}}) \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})}$ 。另一个不等式 $P[E(\bar{\boldsymbol{X}}) - \bar{\boldsymbol{X}} \geq t] \leq \exp{(-\frac{2N^2t^2}{\sum_{i=1}^N(b_i-a_i)^2})}$ 同理可证。