Columbia 可靠统计推断第二课·bounded diff

2020-12-27 本文已影响0人顾劝劝

我们要证明ERM估计的参数能够达到总体分布下损失期望的近似最优。
也就是uniform concentration guarantees:
$\sup_{\theta\in\Theta}|\dfrac{1}{n}\sum l(\theta;Z_i)-\mathbb{E}l(\theta;Z)|\rightarrow 0, \text{fast enough}$

定义1（轻尾）

A RV $X$ is $\sigma^2$ -sub-Gaussian if $\mathbb{E}e^{\lambda(X-\mathbb{E}X)}\leq e^{\sigma^2\lambda^2/2}, \forall \lambda \in \mathbb{R}$ 。
其实不等式右边就是标准正态的矩母函数。等于说这个分布的尾巴至少和正态分布一样轻。

这样用马尔可夫不等式我们就有 $\mathbb{P}(X-\mathbb{E}X\geq t)= \mathbb{P}(\lambda(X-\mathbb{E}X)\geq\lambda t) = \mathbb{P}(e^{\lambda(X-\mathbb{E}X)}\geq e^{\lambda t})\\ \leq\mathbb{E}e^{\lambda(X-\mathbb{E}X)}/e^{\lambda t} \leq e^{\sigma^2\lambda^2/2-\lambda t}$

$\lambda=\frac{t}{\sigma^2}$ 时，上式 $\leq \exp(-t^2/(2\sigma^2))$ 。
同样地，对于 $-X$ 也有 $\mathbb{P}(X-\mathbb{E}X\leq -t)\leq \exp(-t^2/(2\sigma^2))$

例子1： $\epsilon$ 随机符号（Rademacher）是1-sub-Gaussian
$\mathbb{E}e^{\lambda(\epsilon-\mathbb{E}\epsilon)}=\mathbb{E}e^{\lambda \epsilon}=\dfrac{1}{2}(e^\lambda+e^{-\lambda})=\dfrac{1}{2}(\sum_{k=1}^\infty \dfrac{\lambda^k}{k!} + \sum_{k=1}^\infty \dfrac{(-\lambda)^k}{k!})=$
例子2：在a和b的闭区间内的零均值随机变量是 $(b-a)^2/4$ -sub-Gaussian

Bounded differences对证明下面的定理非常有用

定理1

如果g有这样的性质：
$|g(z_1,\ldots, z_i, \ldots, z_n)-g(z_1,\ldots, z'_i, \ldots, z_n)| \leq c_i, \forall 1\leq i\leq n$
（一个维度不会改变整体函数值太多）
对于独立的随机变量 $z_i$ 来说， $\mathbb{P}\left(g(z_1^n)-\mathbb{E}g\left(z_1^n\right)\geq t\right)\leq \exp(-2t^2/\sum_i^n c_i^2)$
(Hoeffding bound的推广）

定义2 （鞅差）

$\{M_i\}_{i=0}^n$ 是一个鞅序列，w.r.t. 随机变量 $Z_1,\cdots,Z_n$ 。
如果M是 $Z_1,\cdots,Z_n$ 可测的， $\mathbb E|M_i|<\infty$ ， $\mathbb E[M_i|Z_{i-1}] = M_{i=1}$ ，
那么 $\{D_i:=M_i-M_{i-1}\}_{i=1}^n$ 叫做martingale difference sequence w.r.t $Z_1,\cdots,Z_n$ ，而且 $\mathbb E[D_i|X_1^{i-1}]=0$ 。

引理1

如果 $\{D_i\}_{i=1}^n$ 是martingale difference sequence w.r.t $Z_1,\cdots,Z_n$ ，
那么存在 $\sigma^2_i$ ，使得 $\mathbb E[e^{\lambda D_i}|Z_1^{i-1}]\leq e^{\frac{\sigma^2 t^2}{2}}$ ，那么 $M_n-M_0 = \sum_{i=1}^n D_i$ 是 $\sum \sigma^2$ -sub-Gaussian的。