Methods of Bounded Difference (1)

Conditional Expectation, Martingales, and Lipschitz condition

Mathematics 读书笔记 ConcentrationInequality

---

Overview

当随机变量$X$可表示成多个独立的有界随机变量之和时，可以用Chernoff-Hoeffding Bound为其给出很紧的concentration estimate，但是在很多实际应用中，
首先所研究的量未必能表示成多个随机变量之和的形式，其次随机变量间的独立性条件也未必满足：在更一般的情况中，我们感兴趣的变量$Z$是关于多个随机变量$X_1,\ldots,X_n$的某个函数，
即$Z=f(X_1,\ldots,X_n)$，注意这里$X_i$之间未必相互独立。当$f$与$X_i$满足某些条件时，可以利用一种称为bounded difference的技术给出concentration estimate，此时甚至不需要知道$f$的具体形式。
这个技巧的基本原理是用概率论中的一个叫做鞅（martingale）的概念来代替原本的独立性假设，因此先简要介绍鞅的一些性质，并从中出发得到一些初步的结果。

Conditional Expectation

条件期望就是对多个随机变量的函数求部分期望，即将某一部分随机变量视作已知值（即把它们“固定住”，又称conditioned on），然后对剩下的随机变量求期望。例如对函数$f(X, Y)$，其中参数$X, Y$是随机变量, 要求$X$关于$Y$的条件期望（expectation of $X$ conditioned on $Y$）就是$E_X[f(X, Y)|Y]$，这个期望的结果实际上还是一个随机变量——一个关于随机变量$Y$的函数。下面举几个条件期望的常用性质：

• $E_X[E_Y[f(X)g(X,Y)|X]] = E_X[f(X)E_Y[g(X,Y)|X]]$，这是因为在内层的条件期望中$X$是被“固定住”的，可被视为常量，因此$f(X)$能提到外层期望中去。

• $E_X[X ]= \sum_ip_iE_X[X|Y=y_i] = E_Y[E_X[X|Y]]$

• $E_Y[E_X[X|Y]|Z] = \sum_ip_iE_X[X|Y=y_i, Z] = E_X[X|Z]$

Martingales

所谓鞅（martingale）指的是满足一种“局部相关性”的随机变量序列，作为例子，考虑一个抛掷硬币的游戏：连续抛掷一枚均匀的硬币，若出现正面，则得分+1，反之得分-1，用$S_n$表示连续抛掷$n$次后的总得分，易见随机变量$S_0, S_1, \ldots$并不满足独立性假设，$S_n$是有之前$n$次抛掷后的得分$S_0,\ldots,S_{n-1}$及第$n$次抛掷的得分$X_n$决定，但仔细研究会发现，它们之间的相关性仅体现在某种局部的意义上：

$$\begin{align*} E[S_n|S_0,\ldots,S_{n-1}] &= E[S_n|S_{n-1}] \\ &= E[S_{n-1}+X_n|S_{n-1}] \\ &= S_{n-1}\quad(\text{由于}\ E[X_n]=0) \end{align*}$$
事实上，序列$S_0, S_1, \ldots$就是一种鞅序列。如果把它看成一种随机游走，则从期望的意义上，该序列不会离它的出发点太远（准确地说是留在原地），这也暗示了鞅有concentration的性质。
下面给出几个后面要用到的定义

• 若随机变量序列$X_0, X_1, \ldots$满足下述条件:
  

  $$E_{X_i}[X_i|X_0,X_1,\ldots,X_{i-1}] = X_{i-1}, i\geq1$$
  则称该序列为一个鞅（martingale），上述条件可以简记为$E_{X _i}[X_i|\mathbf{X}_{i-1}]$

• 若随机变量序列$X_0, X_1, \ldots$是一个鞅，定义序列
  

  $$Y_i=X_i-X_{i-1}, (i\geq1)$$
  则称序列$Y_i$为martingale difference sequence(MDS)，易见$E[Y_i|\mathbf{X}_{i-1}] = 0$

• 若随机变量序列$X_0, X_1, \ldots$是一个鞅，且每个$X_i$满足条件$a_i\leq X_i-X_{i-1}\leq b_i$，则称该序列满足bounded difference条件

前面说过鞅“不会离它的出发点太远“，这个东西形式化一下就是下面的concentration inequality：

(Azuma-Hoeffding Inequality)，设$X_0,X_1,\ldots$是一个鞅，且其满足bounded difference条件，则

$$\text{Pr}[X_n>X_0+t], \text{Pr}[X_n<X_0-t] \leq \text{exp}\left(-\frac{2t^2}{\sum_{i\in[n]}(b_i-a_i)^2}\right)$$

Generalized Martingales

本节把鞅的定义推广到一组随机变量依赖于另一组随机变量的情况，并给出推广后的Azuma-Hoeffding inequality。
若随机变量序列$\mathbf{Y} := Y_0,Y_1,\ldots$是关于另一组随机变量序列$\mathbf{X} := X_0,X_1,\ldots$的函数（精确地说就是存在函数$g_i$使$\mathbf{Y_i}=g_i(\mathbf{X_i})$），且

$$E[Y_i|\mathbf{X}_{i-1}]=Y_{i-1}, i\geq1$$
则称序列$\mathbf{Y}$是关于序列$\mathbf{X}$的鞅序列（martingale with respect to $\mathbf{X}$）

一个重要的例子就是所谓的Doob sequence，它是针对任意函数及任意一组随机变量序列所构造出的鞅，由于这个构造过程的普适性，在实际应用中常通过构造Doob序列来得到鞅。

（Doob sequence）任意一个$n$元函数$f$，视其$n$个参数为一个有限长的随机变量序列$X_1,\ldots,X_n$，则定义

$$Y_i := E[f|\mathbf{X}_i], 0\leq i\leq n$$
特别的，$Y_0 = E[f], Y_n = f(X_1,\ldots, X_n)$。称序列$\mathbf{Y}$为函数$f$关于变量$X_1,\ldots,X_n$的Doob序列。
可以证明Doob序列是一个鞅，即$E[Y_i|\mathbf{X}_{i-1}] = Y _{i-1}$

上一节的Azuma-Hoeffding Inequality也可以推广到本节的generalized martingale上：

(Azuma-Hoeffding Inequality - general version)，设$Y_0,Y_1,\ldots$是一个关于序列$X_0, X_1,\ldots$的鞅，且$Y$满足bounded difference条件，则

$$\text{Pr}[Y_n>Y_0+t], \text{Pr}[Y_n<Y_0-t] \leq \text{exp}\left(-\frac{2t^2}{\sum_{i\in[n]}(b_i-a_i)^2}\right)$$

鞅的引入是为了放松原本的随机变量$X_1,X_2,\ldots$间的独立性假设，在这个基础上研究$Z=f(X_1,\ldots,X_n)$的concentration性质。由于$f$的定义可能非常复杂，为了处理一般的情况，我们再为$f$引入一个所谓的Lipschitz condition；当$f$满足该条件时，不管其具体形式如何，都有可能为之得到较好的concentration bound。

Lipschitz condition

直观上，Lipschitz condition表明一个函数的图像是比较平缓的，不会变化非常剧烈。由于这里$f$是一个关于一群随机变量的函数，因此本文中的Lipschitz condition的定义与传统定义略有不同，但含义基本一致。下面分别介绍常用的几种定义，以及在满足该定义的情况下，我们能得到何种concentration bound。

设$X_1,\ldots,X_n$是任意一组随机变量，$f$是关于它们的函数。

1. Averaged bounded difference condition
   若$\forall i\in[n]$，存在$c_i\geq0$使得
   

   $$|E[f|\mathbf{X}_i]-E[f|\mathbf{X}_{i-1}]|\leq c_i$$
   则称$f$满足averaged bounded difference condition.易看出这实际上就是上一节所说的Doob sequence的一种特殊情况：取$Y_i:=E[f|\mathbf{X}_i]$即可。而且上一节所给出的generalized Azuma-Hoeffding不等式也可以直接用在这里。设$c:=\sum_ic_i^2$，则有
   $$\text{Pr}[f>Ef+t], \text{Pr}[f<Ef-t] \leq \text{exp}\left(-\frac{2t^2}{c}\right)$$

2. Averaged Lipschitz condition（ALC）
   若对随机变量$X_i$任意的两个可能取值$a_i, a_i'$，存在$c_i\geq0$使
   

   $$|E[f|\mathbf{X}_{i-1},X_i=a_i]-E[f|\mathbf{X}_{i-1},X_i=a_i']|\leq c_i$$
   则称$f$满足averaged Lipschitz condition。直观上说就是，固定前$i-1$个变量，然后让第$i$个变量取任意的两个值，接着对剩下的变量求条件期望，这样得到的两个随机变量（回忆之前介绍条件期望时所说的，对部分变量求条件期望后得到的结果仍是随机变量）是uniformly bounded by $c_i$.当$f$满足该条件时，可以得到同之前形式一样的bound：
   $$\text{Pr}[f>Ef+t], \text{Pr}[f<Ef-t] \leq \text{exp}\left(-\frac{2t^2}{c}\right)$$

3. Lipshitz property (or bounded difference condition)
   这个条件一般来说是最容易验证的，因此实践中用的非常多。若对函数$f(x_1,\ldots,x_n)$，存在常数$d_i,i\in[n]$使
   

   $$|f(\mathbf{a})-f(\mathbf{a}')|\leq d_i$$
   （其中$\mathbf{a},\mathbf{a}'$仅在第$i$个坐标上的值不同），则称$f$具有Lipschitz property。此时，若$X_1,\ldots,X_n$相互独立,则又能得到一个非常面熟的bound：
   $$\text{Pr}[f>Ef+t], \text{Pr}[f<Ef-t] \leq \text{exp}\left(-\frac{2t^2}{d}\right)$$
   只是这里由$c$换成了$d=\sum_id_i^2$. 然而这个bound在应用时有两个缺点：第一，它要求$f$的各个参数之间相互独立，这一般需要对变量进行一些替换才能达到（将在下章介绍）；第二，在该bounded difference condition中的参数$d_i$很可能会远大于前两个bound中的参数$c_i$，导致得到的bound非常松，因而意义不大（易看出ALC条件下的参数$c_i$是恒小于或等于$d_i$的）.与此相反的是，average bounded difference condition中的参数总是小于ALC条件中的对应$c_i$，因此从该条件出发得到的bound是上述三个bound中最紧的。