Hoeffding不等式简介

1 Hoeffding不等式

Hoeffding不等式是非常有用的一个不等式，在机器学习、统计学等领域，都发挥着巨大的作用。

它的思想与Markov不等式有些类似，我们先给出它的形式：

Hoeffding不等式：(Y_1,ldots,Y_n)为独立观测，(E(Y_i)=0)，(a_ileq Y_ileq b_i)。对于(epsilongt 0)，(forall t gt 0)，有

[P(sum_{i=1}^{n} Y_i geq epsilon) leq e^{-tepsilon} prod_{i=1}^{n} e^{t^2 (b_i-a_i)^2/8} ]

2 证明

首先，(forall tgt 0)，利用Markov不等式，我们有

[egin{aligned} &Pleft(sum_{i=1}^{n} Y_i geq epsilon ight)\ = & Pleft(e^{tsum_{i=1}^{n} Y_i} geq e^{tepsilon} ight)\ leq & e^{-tepsilon} Eleft(e^{tsum_{i=1}^{n} Y_i} ight)\ = & e^{-tepsilon} prod_{i=1}^{n} Eleft(e^{t Y_i} ight) end{aligned} ]

而又由于(a_ileq Y_ileq b_i)，我们可将(Y_i)表示为(Y_i=alpha b_i+(1-alpha)a_i)，其中(alpha=dfrac{Y_i-a_i}{b_i-a_i})，利用Jensen不等式以及指数函数的凸性，有

[e^{tY}leq dfrac{Y_i-a_i}{b_i-a_i} e^{tb_i} + dfrac{b_i-Y_i}{b_i-a_i} e^{ta_i} ]

两边取期望后，再构造一个函数(g(u))，可得

[Eleft(e^{tY} ight) leq -dfrac{a_i}{b_i-a_i} e^{tb_i} + dfrac{b_i}{b_i-a_i} e^{ta_i} = e^{g(u)} ]

其中(u=t(b_i-a_i))，(g(u)=-gamma u+log(1-gamma+gamma e^u))，(gamma=-dfrac{a_i}{b_i-a_i})。

我们可知(g(0)=g'(0)=0)，并且(forall ugt 0)，有(g''(u)leq 1/4)。

现在，我们需要用到Taylor定理：若(g)为光滑函数，则(exists xiin(0,u))，使得(g(u)=g(0)+g'(0)u+dfrac{1}{2}g''(xi) u^2)。利用Taylor定理，必定(exists xiin (0,u))，使得

[egin{aligned} &g(u)\ =& g(0)+g'(0)u+dfrac{1}{2}g''(xi) u^2\ =& dfrac{1}{2}g''(xi) u^2\ leq & dfrac{u^2}{8}\ =& dfrac{t^2(b_i-a_i)^2}{8} end{aligned} ]

代回之后，我们有

[Eleft(e^{tY_i} ight) leq e^{g(u)}leq e^{t^2(b_i-a_i)^2/8} ]

代回最上式，得证。

3 Bernoulli分布情形

这里我们考虑一种特殊情况：Bernoulli分布。由于Bernoulli分布的随机变量是有界的，因此可以用Hoeffding不等式，该结论也可以看作是Hoeffding不等式的一种形式：

假设(X_1,ldots,X_nsim ext{Bernoulli}(p))，记(ar{X}_n = n^{-1}sum_{i=1}^{n}X_i)，则(forall epsilon gt 0)，有

[P(|ar X_n - p|gt epsilon) leq 2e^{-2nepsilon^2} ]

证明：令(Y_i=(1/n)(X_i-p))，有(E(Y_i)=0)，且(aleq Y_ileq b)，其中(a=-p/n)，(b=(1-p)/n)。直接应用Hoeffding不等式，有(forall epsilongt 0)，(forall t gt 0):

[P(ar{X}_n -p geq epsilon) = P(sum_{i=1}^{n} Y_i geq epsilon) leq e^{-tepsilon} prod_{i=1}^{n} e^{t^2/(8n^2)} ]

由于上式对于任意(t gt 0)都成立，取(t=4nepsilon)，得到

[P(ar{X}_n -p geq epsilon) leq e^{-4nepsilon^2} prod_{i=1}^{n} e^{2epsilon^2} = e^{-2nepsilon^2} ]

同理，若令(Y_i=(1/n)(p-X_i))，则有

[P(p-ar{X}_n geq epsilon) =P(ar{X}_n -p leq -epsilon) = e^{-2nepsilon^2} ]

将两个不等式合并后，得证。

4 应用

我们来看一个简单的应用，目的是说明Hoeffding不等式的上限，可能会比如Chebyshev不等式等更紧。

假设(X_1,ldots,X_nsim ext{Bernoulli}(p))，取(n=100)，(epsilon=0.2)，使用Chebyshev不等式，我们有

[P(|ar X_n - p|gt epsilon) leq dfrac{p(1-p)/n}{epsilon^2}leq 0.0625 ]

而使用第3节中的Hoeffding不等式，有

[P(|ar X_n - p|gt epsilon) leq 0.00067 ]

可以看到，Hoeffding不等式的上界要小得多。