引理D.1 Hoeffding引理

引理D.1 (Hoeffding引理) $X$ 是一个随机变量，具有 $E\left[X\right]=0$ 和 $a\le X\le b$ ，并且 $b>a$ 。那么，对于任何 $t>0$ ，以下不等式成立:

$$\mathbb{E}\left[e^{tX}\right]\le e^{\frac{t^2{\left(b-a\right)}^2}{8}}.\text{\hspace{1em}(D. 2)}$$

证明:由于 $x\mapsto e^x$ 的凸性，对于所有 $x\in \left[a,b\right]$ ，以下成立:

$$e^{tx}\le \frac{b-x}{b-a}{e}^{ta}+\frac{x-a}{b-a}{e}^{tb}.$$

因此，使用 $\mathbb{E}\left[X\right]=0$ ，

$$\mathbb{E}\left[e^{tX}\right]\le \mathbb{E}\left[\frac{b-X}{b-a}{e}^{ta}+\frac{X-a}{b-a}{e}^{tb}\right]=\frac{b}{b-a}{e}^{ta}+\frac{-a}{b-a}{e}^{tb}=e^{\varphi \left(t\right)},$$

其中，

$$\varphi \left(t\right)=\log \left(\frac{b}{b-a}{e}^{ta}+\frac{-a}{b-a}{e}^{tb}\right)=ta+\log \left(\frac{b}{b-a}+\frac{-a}{b-a}{e}^{t\left(b-a\right)}\right).$$

对于任何 $t>0$ ，$\varphi$ 的一阶和二阶导数如下:

$${\varphi }^{\prime }\left(t\right)=a-\frac{a{e}^{t\left(b-a\right)}}{\frac{b}{b-a}-\frac{a}{b-a}{e}^{t\left(b-a\right)}}=a-\frac{a}{\frac{b}{b-a}{e}^{-t\left(b-a\right)}-\frac{a}{b-a}},$$ $$\begin{array}{rl}{\varphi }^{\prime \prime }\left(t\right)& =\frac{-ab{e}^{-t\left(b-a\right)}}{{\left[\frac{b}{b-a}{e}^{-t\left(b-a\right)}-\frac{a}{b-a}\right]}^2}\\ & =\frac{\alpha \left(1-\alpha \right)e^{-t\left(b-a\right)}{\left(b-a\right)}^2}{{\left[\left(1-\alpha \right)e^{-t\left(b-a\right)}+\alpha \right]}^2}\\ & =\frac{\alpha }{{\left(\left(1-\alpha \right)e^{-t\left(b-a\right)}+\alpha \right)}^2}\cdot \frac{\left(1-\alpha \right)e^{-t\left(b-a\right)}}{{\left(\left(1-\alpha \right)e^{-t\left(b-a\right)}+\alpha \right)}^2}{\left(b-a\right)}^2.\end{array}$$

其中 $\alpha$ 表示 $\frac{-a}{b-a}$ 。注意 $\varphi \left(0\right)={\varphi }^{\prime }\left(0\right)=0$ 并且 ${\varphi }^{\prime \prime }\left(t\right)=u\left(1-u\right){\left(b-a\right)}^2$ ，其中 $u=\frac{\alpha }{\left[\left(1-\alpha \right)e^{-t\left(b-a\right)}+\alpha \right]}$ 。由于 $u$ 在 $\left[0,1\right],u\left(1-u\right)$ 中，$\left[0,1\right],u\left(1-u\right)$ 被 $1/4$ 和 ${\varphi }^{\prime \prime }\left(t\right)\le \frac{{\left(b-a\right)}^2}{4}$ 界定。因此，通过函数 $\varphi$ 的二阶展开，存在 $\theta \in \left[0,t\right]$ 使得:

$$\varphi \left(t\right)=\varphi \left(0\right)+t{\varphi }^{\prime }\left(0\right)+\frac{t^2}{2}{\varphi }^{\prime \prime }\left(\theta \right)\le t^2\frac{{\left(b-a\right)}^2}{8},\text{\hspace{1em}(D.3)}$$

这完成了证明。