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

作者: 顾劝劝 | 来源:发表于2020-12-27 22:09 被阅读0次

Columbia 可靠统计推断第二课·bounded diff
Columbia 可靠统计推断第四课·Asymptotics
Columbia 可靠统计推断第一课·概览
假设检验之概念篇
统计中的假设检验
统计推断
深度学习之路
统计学复习
概率
统计推断概述

我们要证明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的。

Columbia 可靠统计推断第二课·bounded diff
课件来自Namkoong讲义[https://hsnamkoong.github.io/b9145/lecture...
Columbia 可靠统计推断第四课·Asymptotics
定义1 （大O小o）随机变量，如果，随着。随机变量，如果。如果那么用一致大数定律（ULLN）证明渐进接下来证...
Columbia 可靠统计推断第一课·概览
这门课的要点：逻辑回归随机优化最小化损失的监督学习随机梯度下降近年来高阶机器学习话题归纳偏置（inducti...
假设检验之概念篇
一、几个概念 1、统计推断由样本信息对相应总体的特征进行推断称为统计推断，简言之，由样本推断总体的方法称为统计...
统计中的假设检验
推断统计的概念推断统计是研究如何利用样本数据来推断总体特征的统计方法。包含两个内容：参数估计，即利用样本信息推断...
统计推断
一、单样本假设检验：对单一的母体参数进行检验假设检验步骤：1.根据实际情况提出原假设和备择假设；2.根据假设的特征...
深度学习之路
一.概率论与统计推断概率论与统计推断(一) ------ 概率论的基本概念概率论与统计推断(二) ------ ...
统计学复习
如上图所示统计学主要是依照样本数据分析推断和描述数据总体分布情况。统计方法可分为推断统计和描述统计；其中推断统计是...
概率
统计学分为描述性统计和推断统计。推断统计是指通过样本数据对总体特征作出推断，它有3个要素：1.随机观测的样本数据；...
统计推断概述
什么是统计推断对于要做统计推断的人来讲，这个问题似乎显得多余，他们往往关心怎样做统计推断。这也许可以窥得发展中国...

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

定义1（轻尾）

定理1

定义2 （鞅差）

引理1

相关文章