LFTP Chapter 1 笔记整理

对应 Learning Theory from First Principles：§1.2.3 Bernstein's Inequality、§1.2.4 Expectation of the Maximum、§1.2.5 Estimation of Expectations through Quadrature。

本文由手写扫描稿整理，并统一了符号、补足了省略步骤、纠正了公式笔误。

1.2.3 Bernstein 不等式

命题

设随机变量 $Z_1,\dots,Z_n$ 相互独立，并满足

$\mathbb E[Z_i]=0,\qquad |Z_i|\le c\quad\text{a.s.}$

记

$\sigma^2=\frac1n\sum_{i=1}^n\operatorname{Var}(Z_i).$

则对任意 $t>0$，

$\mathbb P\!\left(\left|\frac1n\sum_{i=1}^n Z_i\right|>t\right) \le 2\exp\!\left(-\frac{nt^2}{2\sigma^2+\frac{2ct}{3}}\right).$

等价地，对任意 $\delta\in(0,1)$，以至少 $1-\delta$ 的概率，

$\left|\frac1n\sum_{i=1}^n Z_i\right| \le \sqrt{\frac{2\sigma^2\log(2/\delta)}{n}} + \frac{2c\log(2/\delta)}{3n}.$

第一步：单个随机变量的矩母函数界

设 $Z$ 满足 $\mathbb E[Z]=0$、$|Z|\le c$ 且 $\mathbb E[Z^2]=\sigma^2$。对任意 $s>0$，

$\begin{aligned} \mathbb E[e^{sZ}] &=1+s\mathbb E[Z]+\sum_{k=2}^{\infty}\frac{s^k}{k!}\mathbb E[Z^k]\\ &\le 1+\sum_{k=2}^{\infty}\frac{s^k}{k!}\mathbb E[|Z|^k]\\ &\le 1+\sum_{k=2}^{\infty}\frac{s^k}{k!}c^{k-2}\mathbb E[Z^2]\\ &=1+\frac{\sigma^2}{c^2}\bigl(e^{sc}-1-sc\bigr)\\ &\le \exp\!\left[\frac{\sigma^2}{c^2}\bigl(e^{sc}-1-sc\bigr)\right]. \end{aligned}$

最后一步使用了 $1+x\le e^x$。

第二步：Chernoff 方法

记 $\sigma_i^2=\operatorname{Var}(Z_i)$。由独立性与上面的矩母函数界，

$\begin{aligned} \mathbb P\!\left(\frac1n\sum_{i=1}^n Z_i>t\right) &=\mathbb P\!\left(e^{s\sum_{i=1}^n Z_i}>e^{nst}\right)\\ &\le e^{-nst}\prod_{i=1}^n\mathbb E[e^{sZ_i}]\\ &\le \exp\!\left[-nst+\frac{n\sigma^2}{c^2}\bigl(e^{sc}-1-sc\bigr)\right]. \end{aligned}$

令

$u=sc,\qquad \alpha=\frac{ct}{\sigma^2}.$

则指数可写为

$\frac{n\sigma^2}{c^2}\bigl(e^u-1-u-\alpha u\bigr).$

对 $0<u<3$，由级数展开

$\begin{aligned} e^u-1-u &=\sum_{k=0}^{\infty}\frac{u^{k+2}}{(k+2)!}\\ &\le \frac{u^2}{2}\sum_{k=0}^{\infty}\left(\frac u3\right)^k =\frac{u^2}{2(1-u/3)}. \end{aligned}$

取

$u=\frac{\alpha}{1+\alpha/3},$

得到

$e^u-1-u-\alpha u \le -\frac{\alpha^2}{2(1+\alpha/3)}.$

因此

$\mathbb P\!\left(\frac1n\sum_{i=1}^n Z_i>t\right) \le \exp\!\left(-\frac{nt^2}{2\sigma^2+\frac{2ct}{3}}\right).$

对 $-Z_i$ 应用同一结论，再使用 union bound，即得双边 Bernstein 不等式。

解释

当 $t$ 较小时，分母主要由 $2\sigma^2$ 控制，尾界具有近似高斯型衰减。
当 $t$ 较大时，线性项 $2ct/3$ 开始占主导，尾部近似呈指数衰减。
与只利用有界性的 Hoeffding 不等式相比，Bernstein 不等式进一步使用了方差信息。

1.2.4 次高斯变量最大值的期望

设 $Z_1,\dots,Z_n$ 均为零均值、次高斯参数为 $\tau^2$ 的随机变量，即

$\mathbb E[e^{\lambda Z_i}] \le \exp\!\left(\frac{\tau^2\lambda^2}{2}\right), \qquad \lambda\in\mathbb R.$

这里不要求 $Z_1,\dots,Z_n$ 相互独立。

命题：最大值

$\mathbb E\left[\max_{1\le i\le n}Z_i\right] \le \sqrt{2\tau^2\log n}.$

证明

对任意 $\lambda>0$，由 Jensen 不等式、$\max_i a_i\le\sum_i a_i$ 以及次高斯性，

$\begin{aligned} \mathbb E\left[\max_i Z_i\right] &\le \frac1\lambda \log\mathbb E\left[e^{\lambda\max_i Z_i}\right]\\ &=\frac1\lambda \log\mathbb E\left[\max_i e^{\lambda Z_i}\right]\\ &\le\frac1\lambda \log\mathbb E\left[\sum_{i=1}^n e^{\lambda Z_i}\right]\\ &\le\frac1\lambda\log\left(ne^{\tau^2\lambda^2/2}\right)\\ &=\frac{\log n}{\lambda}+\frac{\tau^2\lambda}{2}. \end{aligned}$

右端在

$\lambda=\frac{\sqrt{2\log n}}{\tau}$

处取得最小值，从而得到结论。

绝对值最大值

把

$|Z_i|=\max\{Z_i,-Z_i\}$

看成 $2n$ 个次高斯变量的最大值，可得

$\boxed{ \mathbb E\left[\max_{1\le i\le n}|Z_i|\right] \le \sqrt{2\tau^2\log(2n)} }.$

使用尾界与 union bound 的另一种证明

记

$M=\max_{1\le i\le n}|Z_i|.$

由次高斯尾界和 union bound，

$\mathbb P(M>t) \le \sum_{i=1}^n\mathbb P(|Z_i|>t) \le 2n\exp\!\left(-\frac{t^2}{2\tau^2}\right).$

取

$a=\tau\sqrt{2\log(2n)}.$

由尾积分公式 $\mathbb E[M]=\int_0^\infty\mathbb P(M>t)\,dt$，

$\begin{aligned} \mathbb E[M] &\le a+ 2n\int_a^\infty \exp\!\left(-\frac{t^2}{2\tau^2}\right)dt\\ &\le a+ 2n\frac{\tau^2}{a} \exp\!\left(-\frac{a^2}{2\tau^2}\right)\\ &=a+\frac{\tau^2}{a}. \end{aligned}$

所以

$\mathbb E[M] \le \tau\left( \sqrt{2\log(2n)}+ rac1{\sqrt{2\log(2n)}} \right) \le 2\tau\sqrt{2\log(2n)}.$

这与精确的 Laplace-transform 证明只相差一个普适常数。

1.2.5 用求积公式估计期望

设 $X\sim\operatorname{Unif}[0,1]$，需要计算

$I=\mathbb E[f(X)]=\int_0^1f(x)\,dx.$

取均匀网格

$x_i=\frac in,\qquad i=0,1,\dots,n.$

梯形公式为

$\widehat I = \frac1n\left[ \frac12f(x_0)+\sum_{i=1}^{n-1}f(x_i)+\frac12f(x_n) \right] = \frac1{2n}\sum_{i=1}^n\bigl[f(x_{i-1})+f(x_i)\bigr].$

它等价于：在每个小区间 $[x_{i-1},x_i]$ 上用端点确定的线性插值函数代替 $f$，再对该插值函数积分。

单区间线性插值误差

设 $g:[0,1]\to\mathbb R$，端点线性插值为

$\widetilde g(x)=(1-x)g(0)+xg(1).$

直接积分可得

$\int_0^1\widetilde g(x)\,dx = \frac{g(0)+g(1)}2.$

若 $g$ 二阶可微，且

$|g''(x)|\le L,$

则线性插值余项公式给出：对每个 $x\in[0,1]$，存在 $\xi_x\in(0,1)$ 使得

$g(x)-\widetilde g(x) = \frac{g''(\xi_x)}2x(x-1).$

因此

$\boxed{ |g(x)-\widetilde g(x)| \le \frac L2x(1-x) }.$

梯形公式的全局误差

在长度为

$h=x_i-x_{i-1}=\frac1n$

的小区间上，缩放上述结论得到

$|f(x)-\widetilde f_i(x)| \le \frac L2(x-x_{i-1})(x_i-x).$

于是局部积分误差满足

$\begin{aligned} \left| \int_{x_{i-1}}^{x_i}f(x)\,dx - \frac h2\bigl[f(x_{i-1})+f(x_i)\bigr] \right| &\le \frac L2\int_{x_{i-1}}^{x_i} (x-x_{i-1})(x_i-x)\,dx\\ &= \frac{Lh^3}{12}. \end{aligned}$

将 $n$ 个区间相加，得到

$\boxed{ |I-\widehat I| \le \frac{L}{12n^2} }.$

因此，在二阶导数一致有界时，梯形公式的误差阶为

$|I-\widehat I|=O(n^{-2}).$

若只假设一阶导数有界，一般只能得到 $O(n^{-1})$ 的误差。

主要校订

Bernstein 不等式的分母应为 $2\sigma^2+2ct/3$，不能把方差项或线性项的系数混写。
次高斯最大值证明中的优化变量应取 $\lambda=\sqrt{2\log n}/\tau$。
对绝对值最大值，应把变量数从 $n$ 改为 $2n$，故出现 $\log(2n)$。
梯形公式的二阶光滑误差为 $L/(12n^2)$；单区间插值误差为 $\frac L2x(1-x)$。