Chernoff-Hoeffding Bound

Mathematics 读书笔记 ConcentrationInequality

---

引文

中心不等式（Concentration Inequality）是分析随机算法的经典工具，在机器学习算法的理论分析中也用的特别多。为了
学习这方面的知识，刚开始我选择的是Massart和Lugosi所著的Concentration Inequalities，无奈数学水平不够，看了一章就实在看不下去了。后来换了本简单一些的Concentration of Measure for the Analysis of Randomized Algorithms，总算是能往后翻了。这个系列的文章作为该书的读书笔记，希望能够督促自己坚持读完。

Concentration of meature可简单地理解为随机变量在其期望处“聚集”的行为。概率论中已经提供了两个经典工具————大数定律及中心极限定理————来刻画这种现象，然而它们所给出的结果存在几点不足：

• 上述结果只刻画了渐进情况下的性质，然而在分析实际算法时我们更青睐能够应用于finite case的结果
• 上述经典工具给出的是qualitative的结果，但我们更希望有quantitative的结果，也即明确的收敛率
• 上述经典工具给出的结果都基于独立性的假设，然而对于很多复杂的随机算法，独立性是不满足的，因此我们需要不依赖独立性假设的工具。

Chernoff Bound

Chernoff bounding technique指的是用moment-generating function来处理多个随机变量之和的期望的技巧。所谓moment-generating function被定义为随机变量$X$的指数函数的期望$E[e^{\lambda X}]$。

先来看一个简单的例子：考虑独立同分布的Bernoulli随机变量$X_i\sim Bernoulli(p)$及它们的和$X=\sum_{i\in[n]}X_i$，易见$X\sim Binomial(n,p)$。现在要估计$X$偏离其期望一定距离的概率，即$Pr[X>n(p+t)]$. 先考虑一个一般性的情况：估计$Pr[X>m]$. 由Markov不等式易得

$$\begin{align} Pr[X>m] &= Pr[e^{\lambda X}>e^{\lambda m}] \\ &\leq \frac{E[e^{\lambda X}]}{e^{\lambda m}} \end{align}$$

根据$X_i$的独立性，上述式子中的moment-generating function可写成

$$\begin{align} E[e^{\lambda X}] &= E[e^{\lambda\sum_i X_i}] \\ &= E[\prod_i e^{\lambda X_i}] \\ &= \prod_i E[e^{\lambda X_i}] \\ &= (pe^\lambda+q)^n \end{align}$$

其中$q=1-p$.再令$m=(p+t)n$，原不等式变为

$$Pr[X>m]\leq\left(\frac{pe^\lambda+q}{e^{\lambda(p+t)}}\right)^n$$

将上述不等式右边视为$\lambda$的函数，找一个$\lambda>0$使右边最小，由此我们得到基本的Chernoff bound：

$$\begin{align} Pr[X>(p+t)n] &\leq \left(\left(\frac{p}{p+t} \right)^{p+t} \left(\frac{q}{q-t}\right)^{q-t}\right)^n \\ &= \left[\text{exp}\left(-(p+t)\text{ln}\frac{p+t}{p}-(q-t)\text{ln}\frac{q-t}{q}\right)\right]^n \\ &= \text{exp}\left(-nD_{KL}(p+t||p)\right) \end{align}$$

其中$D_{KL}(\cdot||\cdot)$是KL-Divergence.上述bound说明，当实际分布（的参数）是$(p,q)$时，观测到经验分布$(p+t,q-t)$的概率随着样本大小$n$的增加指数下降，且下降速率与实际分布及经验分布的KL-Divergence密切相关。

Chernoff-Hoeffding bound

之前Chernoff bound的推导是在$X_i$为独立同分布的Bernoulli随机变量的假定下进行的，现在我们把上述bound推广到$X_i$是任意$[0,1]$间的独立随机变量的情况。首先考虑$X_i$是独立但非同分布的Bernoulli随机变量的情况。此时$X$的moment-generating function变为

$$E[e^{\lambda X}] = \prod_i(p_ie^\lambda+q_i)$$

根据Arithmetic-Geometric Mean Inequality易得

$$\begin{align} E[e^{\lambda X}] &= \prod_i(p_ie^\lambda+q_i) \\ &\leq\left(\frac{\sum_i(p_ie^\lambda+q_i)}{n}\right)^n \\ &= (pe^\lambda+q)^n \end{align}$$

其中$p=\sum_ip_i/n, q=1-p$. 易见此时bound又变回了之前独立同分布时的形式，因此上一节得到的bound依然成立。

接下来考虑$X_i$是$[0,1]$上任意（既可以是离散也可以是连续的）独立随机变量的情况，使用的技巧是由Hoeffding提出的，因此最后得到的bound也叫Chernoff-Hoeffding bound。这里要利用函数$e^{\lambda x}$的凸性：在区间$[0,1]$上，$e^{\lambda x}$的图像总在连接点$(0,1)$及$(1,e^\lambda)$的直线之下。该直线的方程为$y=(e^\lambda-1)x+1$，因此有

$$E[e^{\lambda X_i}] \leq E[(e^\lambda-1)X_i+1] = p_ie^\lambda+q_i$$

故有

$$E[e^{\lambda X}] \leq \prod_i E[e^{\lambda X_i}] \leq \prod_i(p_ie^\lambda+q_i)$$

这与前述$X_i$是独立非同分布Bernoulli随机变量的情况一致，因此上一节得到的bound依然成立。

Variance bound

之前得到的bound都只利用了一阶矩（期望）的信息，作为Chernoff bounding technique的一个简单应用，我们考虑引入二阶矩（方差）的信息。这里的关键技巧是利用不等式$e^x\leq1+x+x^2, (0<|x|<1)$为moment-generating function构造上界，从而引入二阶矩（$x^2$）。设$\mu_i=E[X_i], \mu=E[X]$，易知

$$\begin{align} Pr[X>\mu+t] &= Pr[\sum_i(X_i-\mu_i)>t] \\ &= Pr[e^{\lambda\sum_i (X_i-\mu_i)}>e^{\lambda t}] \\ &\leq E[e^{\lambda\sum_i(X_i-\mu_i)}]/e^{\lambda t} \end{align}$$

利用之前提到的不等式及$e^x\geq1+x$，并假设$\forall i\in[n], \text{max}(\mu_i,1-\mu_i)<1/\lambda$，有

$$\begin{align} E[e^{\lambda\sum_i(X_i-\mu_i)}] &= \prod_iE[e^{\lambda(X_i-\mu_i)}] \\ &\leq \prod_i E[1+\lambda(X_i-\mu_i)+\lambda^2(X_i-\mu_i)^2] \\ &= \prod_i(1+\lambda^2\sigma_i^2) \\ &\leq \prod_ie^{\lambda^2\sigma_i^2} \\ &= e^{\lambda^2\sigma^2} \end{align}$$

其中$\sigma_i^2,\sigma^2$分别是$X_i,X$的方差。综上，有

$$Pr[X>\mu+t] \leq e^{\lambda^2\sigma^2}/e^{\lambda t}$$

针对$\lambda<\text{max}(\mu_i,1-\mu_i)$最小化该上界，易知当$\lambda=t/2\sigma^2$时有

$$Pr[X>\mu+t] \leq \text{exp}\left(\frac{-t^2}{4\sigma^2}\right)$$

其中$t<2\sigma^2/(\text{max}_i\ \text{max}(\mu_i, 1-\mu_i))$