来自讲义
有没有注意到，上次的差距上界用到了，集合内参数取值数量。如果参数取值是连续的，那上界岂不是要无穷大了？不急，这节课针对参数空间有界的情况，我们值域离散化以后再来证明。本节课后半程会介绍更多的concentration inequalities。
1 参数化假设的一致收敛
基本思想是离散化后，每个点都找到一种和它接近的代表性取值，这样又可以进行累加找到适用于所有点的一致收敛。
1.1 设定
是参数化的假设函数，
，针对参数空间有界的情况，
，其中
是个正常数。
1.2 一致收敛
上回说到，假设有限的一致收敛定理是：
好了，让我们揭晓今天参数化假设的一致收敛定理真面目。
定理4.1
设，
都是基于l2范数L-Lipschitz。那么至少有
的概率：
评论4.1
这并不是一个紧界，经过更仔细的推导，你会发现失败概率可以从降低至
。
评论4.2
结合定理3的证明方法和定理4.1，
我们可以得到，至少有的概率：
其中
第一课曾讲到，估计参数和真实参数的渐进差距是：
（2）（3）这两个性质一比，你会发现（2）对n的收敛速度明显慢，不过（3）的条件更苛刻：一来，（2）并不限制n的大小。二者，（3）还得假设数据来自于真实分布，（2）和定理4.1没有关于数据分布的假设。
2.2.1 用
cover来给参数空间离散化
欲证定理4.1，我们得给参数空间找个离散化的方法。先来介绍一下cover：
定义4.1 (cover)
满足
就称这个
是
关于距离度量
的
cover。换言之，
要满足：
接下来的引理讲告诉我们，有界参数空间的cover不会包含太多元素。
引理4.1（cover元素个数）
如果是2范数，S的
cover元素个数最多
个。
讲讲大致证明的思路。我们可以这样设定cover：
也就是说，每个维度都在[-B,B]上规律地排列着格点，各自单维度距离是，这样两个p维空间上的点之间的欧氏距离就是
。这样的点有多少个呢？那就数每个维度
的个数，左右界是
，中间算上0，总共是
由红点构成的S的ε-cover
评论4.3
其实……这个个数还是放水放多了。我们能证明个！（不借助
直接排点就行了）
2.2.2 证明定理4.1
利用Hoeffding's inequality，我们有：
以概率满足。（因为
）
对于每个都能找到
使得
。用刚才假设的
、
有L-Lipschitz的特性，不难推出：
于是再过个桥，界就有了：
剩下的就是选个合适的和
来完成定理4.1的证明。
这样(4)的差距变成了
当M、L、B大于某些小常数时成立。这样我们证明了一个比定理4.1更强的定理。
3 concentration inequality
3.1 马尔科夫不等式
是非负的随机变量，对任何正数t，有
3.2 切比雪夫不等式
是随机变量，对于任何正数t，有
用马尔科夫不等式来证明切比雪夫不等式：
切比雪夫不等式的左边其实等于
那我们就把当做一个随机变量，根据马尔科夫不等式：
举一反三，对于任何正整数，都有
甚至不一定要多项式，换成其他非降函数也行。比如对非负的：
不过单用切比雪夫，只能得到n个0、1之间的随机变量的均值的方差小于等于n，好像推不出霍夫丁不等式那么小的失败概率。试试用矩母函数来推方差吧。
3.2 矩母函数
定义4.2
随机变量的矩母函数
是：
泰勒展开之后是
对于这个随机变量也是一样的，套用(6)可得：
回到，我们有
利用(5)这个马尔科夫不等式的变形，可得
对任意非负成立。也就是说，
两边取log
我们利用3.1中这个结论，可以得到
高阶小量
近似地，
虽然和霍夫丁不等式有所出入，但至少数量级对了。应当如何修正以证明霍夫丁不等式呢？请听下回分解。
网友评论