在前两篇关于集中不等式的文章中，我们从Markov不等式开始，通过Chernoff 界的方法得到了Berstein, Hoeffding不等式等结果，并定义了次高斯、次指数分布的概念. 假设现在观测到了i.i.d.的数据点\(X_1,\cdots, X_n\). 之前我们得到的集中不等式，更多的是在非渐近观点下看到的大数定律的表现. 也就是说，这些不等式更多刻画了样本均值如何集中在总体均值的附近. 如果我们把样本均值看成是样本(数据点的函数)，即令\(f(x_1,\cdots,x_n)=n^{-1}\sum_{i=1}^nX_i\), 那么之前的不等式刻画了如下的概率 \[ P(|f(X_1,\cdots,X_n)-\mathbb{E}f(X_1,\cdots,X_n)|>t) \] 对这一表达式，我们能否针对给广泛的函数类型\(f\)给出类似Hoeffding不等式这样的结果呢？答案是可以的！
差有界性质 差有界不等式
直观上来看，我们没有办法对所有的函数\(f\)都给出类似的保证. 如果降低我们的期望，希望函数\(f\)本身具有一些良好的性质，那么我们还是有可能通过一些工具来得到类似的结果的.
这类性质有很多，在这里我们举一个最常见的例子. 如果一个函数\(f:\mathcal{X}^n\rightarrow \mathbb{R}\)满足对所有的\(i\)都可以找到一个常数\(c_i<\infty\)， 使得 \[ |f(x_1,\cdots,x_n)-f(x_1,\cdots,x_{i-1},x_i',x_{i+1},\cdots,x_n)|\leq c_i \] 则称它是是 差有界(bounded difference property) 的
这样的函数实质上表明，函数并不是严重地依赖于每一个\(x_i\)的. 实际上这个性质也时常在机器学习中被看作某种稳定性质. 比如说\(f\)是某一个预测函数，如果除了一个点以外的其它数据点保持不变，那么预测结果也不会有很大的变化. 这也是我们非常欢迎的稳定性. 这类函数的一大好处就是， McDiarmid不等式 给出了一个概率界. 如果我们的样本是独立的,\(f\)是差有界的，那么 \[ P(|f(X_1,\cdots,X_n)-\mathbb{E}f(X_1,\cdots,X_n)|>t)\leq 2\exp\bigg\{-\frac{2t^2}{\sum_{i=1}^n c_i^2}\bigg\} \]
鞅差序列(Martingale difference sequence)
这一部分我们主要对McDiarmd不等式的证明进行介绍. 之所以会详细说这个证明，是因为我觉得这是鞅这一工具的一个非常好的应用的例子.
首先来回顾最基本的 (离散时间)鞅 的概念. 假设我们有一个随机过程(一列随机变量)\(X_n\)，可以把这里的\(n\)看成是时间之类的参量.它们满足 \[ \mathbb{E}|X_n|<\infty,\quad \mathbb{E}[X_{n+1}|X_1,\cdots,X_n]=X_n \] 则称这个随机过程是一个鞅. 这里的两个条件，第一个条件是正则性条件，只是说明了随机过程的积分是有限的；第二个条件则是核心定义，它说明在时刻\(n\),给定了之前所有的观测值以后，下一个观测值的条件期望和最近的一个观测值是相同的. 注意到条件期望和子\(\sigma-\)代数之间的关系. 实际上在这个条件期望的条件中，我们不需要考虑由之前所有观测生成的这个\(\sigma-\)代数. 更一般地，针对这个随机过程，我们考虑一个\(\sigma-\)代数流(过滤)\(\mathcal{F}_1\subset \mathcal{F}_2\subset\cdots\), 使得每个\(X_j\)都是可积且\(\mathcal{F}_j\)可测的，并且\(\mathbb{E}[X_{n+1}|\mathcal{F}_n]=X_n\)即可.
在此基础上我们可以定义 鞅差序列 ：一列随机变量\(D_j\)叫做适应于过滤\(\mathcal{F}_j\)的鞅差序列，如果它满足 \[ \mathbb{E}[D_j]<\infty,\quad \mathbb{E}[D_{j+1}|\mathcal{F}_j]=0 \]
对于一般的鞅差序列，我们有 Azuma-Hoeffding引理 ： 如果\(D_j\)是一个鞅差序列,\(|D_j|\leq a_j\)几乎处处成立，那么 \[ P(|\sum_j D_j|\geq t)\leq 2\exp\bigg\{-\frac{t^2}{2\sum_ja_j^2}\bigg\} \] 从形式上看这一结果和Hoeffding不等式非常相似. 其证明也是充分利用了和Hoeffding不等式的相似的想法.
回忆一下，对于相互独立的随机变量, Hoeffding不等式的证明主要是利用了次高斯性. 那对于鞅差序列，我们能否找到相似的次高斯性呢？答案是肯定的. 如果我们考虑随机变量\(D_j|\mathcal{F}_{j-1}\)，这是一个零期望的有界随机变量. 其次高斯参数可简单的取为\(\sigma_j^2=a_j^2\).这就说明了，对任何\(\lambda>0\) \[ \mathbb{E}[\exp(\lambda D_j)|\mathcal{F}_{j-1}]\leq \exp(\frac{\lambda^2a_j^2}{2}) \] 从而我们通过条件期望的方法有如下计算 \[ \begin{align} \mathbb{E}[\exp(\lambda\sum_{j}D_j)]&=\mathbb{E}[\mathbb{E}[\exp(\lambda\sum_jD_j)|\mathcal{F}_{n-1}]]\\ &\leq \mathbb{E}\big[\exp(\lambda\sum_{j=1}^{n-1}D_j)\big]\exp(\frac{\lambda^2a_j^2}{2})\\ &\leq \cdots\\ &\leq \exp\bigg(\lambda^2\sum_{j=1}^na_j^2/2\bigg) \end{align} \] 这说明了鞅差序列的和是次高斯分布的. 从而通过对一般的次高斯分布的随机变量的控制，我们就可以得到结果.
下面我们回到McDiarmid 不等式. 我们构造一个鞅差序列即可完成证明. 令 \[ D_j = \mathbb{E}[f(X)|X_1,\cdots,X_j]-\mathbb{E}[f(X)|X_1,\cdots,X_{j-1}] \] 则可以验证 \[ f(X)-\mathbb{E}f(X)=\sum_{j=1}^nD_j. \] 代回到Azuma-Hoeffding 不等式中，即可完成一个弱化版的结果.
\[ P(|f(X_1,\cdots,X_n)-\mathbb{E}f(X_1,\cdots,X_n)|>t)\leq 2\exp\bigg\{-\frac{t^2}{2\sum_{i=1}^n c_i^2}\bigg\} \]
这里的右端项的2出现在分母中，但是McDiarmid 不等式中的2出现在分子里. 这个常数的区别可以通过对鞅差序列的更加精细的刻画实现. 在此我们简述一下其条件：如果\(D_j\)是一个鞅差序列，对任何\(j\),存在随机变量\(B_{j-1}\) 使得 \[ P(B_{j-1}\leq D_j\leq B_{j-1}+2a_j|\mathcal{F}_{j-1})=1 \] 则 \[ P(|\sum_j D_j|\geq t)\leq 2\exp\big(-\frac{t^2}{2\sum_j a_j^2}\big) \] 我们之前的证明中是把\(B_{j-1}\)取成了\(-a_j\). 还有一点值得注意的是，这里虽然2仍然是在分母上，但是这里的\(a_j\)是之前证明中的一半. 利用这个结果我们就完成了McDiarmd 不等式的证明.