机器算法验证 - 了解测量浓度不等式 - 吾爱随笔录

本着这个问题的精神，理解 Hoeffding 不等式中使用的引理证明，我试图理解导致 Hoeffding 不等式的步骤。

在证明中对我来说最神秘的是计算 iid 变量总和的指数矩的部分，然后应用马尔可夫不等式。

我的目标是理解：为什么这种技术会给出严格的不等式，它是我们能达到的最严格的吗？一个典型的解释是指指数的矩生成特性。然而，我觉得这太模糊了。

考虑到这个目标，我的问题是关于 Tao 的帖子中的三点，我一直坚持，我希望一旦解释就可以提供见解。

Tao 使用第 k 个矩导出以下不等式
$P (| S_{n} | \geq λ \sqrt{n}) \leq 2 (\frac{\sqrt{e k / 2}}{λ})^{k} . (7)$ $\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq 2 (\frac{\sqrt{ek/2}}{\lambda})^k. \ \ \ \ \ (7)$ 如果这对于任何 k 都是正确的，那么他得出一个指数界。这就是我迷路的地方。 $P (| S_{n} | \geq λ \sqrt{n}) \leq C \exp (- c λ^{2}) (8)$ $\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ) \ \ \ \ \ (8)$
提出了 Hoeffding 引理： Lemma 1 (Hoeffding's lemma) 让 ${X}$ 是在区间内取值的标量变量 ${[a,b]}$ . 那么对于任何 ${t>0}$ ,
$E e^{t X} \leq e^{t E X} (1 + O (t^{2} V a r (X) \exp (O (t (b - a)))) . (9)$ $\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} (1 + O( t^2 {\bf Var}(X) \exp( O( t (b-a) ) ) ). \ \ \ \ \ (9)$ 尤其 $E e^{t X} \leq e^{t E X} \exp (O (t^{2} (b - a)^{2})) . (10)$ $\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} \exp( O( t^2 (b-a)^2 ) ). \ \ \ \ \ (10)$ 引理 1 的证明始于对泰勒展开的期望 $\displaystyle e^{tX} = 1 + tX + O( t^2 X^2 \exp( O(t) ) )$ .为什么展开可以由那个二次项限制？等式 10 是如何得出的？
最后给出一个练习：
练习 1 证明 ${O(t^2(b-a)^2)}$ （10）中的因子可以替换为 ${t^2 (b-a)^2/8}$ ，这很锋利。这将提供比理解 Hoeffding 不等式中使用的引理的证明更短的证明，但我不知道如何解决这个问题。

关于不等式的证明或我们无法得出更严格界限的原因的任何进一步的直觉\解释绝对是受欢迎的。