12
$\begingroup$

In the spirit of this question Understanding proof of a lemma used in Hoeffding inequality , I am trying to understand the steps that lead to Hoeffding's inequality.

What holds the most mystery for me in the proof is the part where exponential moments are computed for the sum of i.i.d variables, after-which Markov's inequality is applied.

My goal is to understand: Why does this technique give a tight inequality, and is it the tightest we can achieve? A typical explanation refers to the moment generating properties of the exponent. Yet, I find this too vague.

A post in Tao's blog, http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/#hoeff, might hold some answers.

With this goal in mind, my question is about three points in Tao's post which I am stuck at and which I hope could give insight once explained.

  1. Tao derives the following inequality using the k-th moment$$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq 2 (\frac{\sqrt{ek/2}}{\lambda})^k. \ \ \ \ \ (7)$$ If this is true for any k, he concludes an exponential bound. This is where I'm lost. $$\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ) \ \ \ \ \ (8)$$

  2. Hoeffding's lemma is presented: Lemma 1 (Hoeffding’s lemma) Let ${X}$ be a scalar variable taking values in an interval ${[a,b]}$. Then for any ${t>0}$, $$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} (1 + O( t^2 {\bf Var}(X) \exp( O( t (b-a) ) ) ). \ \ \ \ \ (9)$$ In particular $$\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} \exp( O( t^2 (b-a)^2 ) ). \ \ \ \ \ (10)$$ The proof of Lemma 1 begins by taking expectation over the taylor expansion $\displaystyle e^{tX} = 1 + tX + O( t^2 X^2 \exp( O(t) ) )$ .Why can the expansion be bounded by that quadratic term? and how does equation 10 follow?

  3. Finally, an exercise is given:
    Exercise 1 Show that the ${O(t^2(b-a)^2)}$ factor in (10) can be replaced with ${t^2 (b-a)^2/8}$, and that this is sharp. This would provide a much shorter proof than the one in Understanding proof of a lemma used in Hoeffding inequality , but I do not know how to solve this.

Any further intuitions\explanations about the proof of the inequality or the reason we cannot derive a tighter bound are definitely welcome.

$\endgroup$
  • $\begingroup$ Have you read the original Hoeffding's paper? $\endgroup$ – Alecos Papadopoulos Sep 23 '13 at 12:20
  • $\begingroup$ @AlecosPapadopoulos I actually haven't. I am under the impression the derivation there consists of algebraic steps typically taught in math courses lacking the explanation I'm looking for. Can you say otherwise? $\endgroup$ – Leo Sep 23 '13 at 23:20
  • $\begingroup$ I suggest you read it. The stable url in jstor is jstor.org/stable/2282952 . What "holds the most mystery to you" is Theorems 1, 2 & 3 of the paper, the proofs of which are in section 4 of the paper (not in the end), and they look pretty clear to me. I don't know if you are searching for some "non-mathematical" intuition -if yes, it doesn't always exist. $\endgroup$ – Alecos Papadopoulos Sep 23 '13 at 23:39
3
$\begingroup$

The use of exponential moments is a common step in the process of proving concentration of measure inequalities. My understanding is as follows 1) By using $\mathbb{E}e^X$ rather than $\mathbb{E} X$, one captures all the moments of $X$, rather than just the first moment. Hence, it is always advantageous to bound $\mathbb{E} e^X$, rather than bound $\mathbb{E}X$, as there is more information in $\mathbb{E} e^X$. Why does $\mathbb{E} e^X$ have more information? An informal explanation is given by the fact that a Taylor expansion of $e^{X}=1+X+\frac{X^2}{2}+\frac{X^3}{6}+\ldots$. As you can see all the powers of $X$ are involved. Hence, when you take $\mathbb{E}X$, you essentially end up bounding all moments of $X$.

$\endgroup$
  • 2
    $\begingroup$ By definition, any analytic function $f$ in a neighborhood of $0$ has an absolutely convergent Taylor series there. Your argument therefore suggests that the exponential $e^X$ could just as well be replaced by $f(X)$. Is there nothing special about the exponential? $\endgroup$ – whuber Nov 19 '13 at 18:17
  • 1
    $\begingroup$ I did not think of replacing $f$, with a general analytic function. But now that you have mentioned it, I guess a "suitable" function could be such that $f(x) >0$, so that Markov's inequality can be applied, and one whose Taylor expansion has all powers of $X$, so that all moments are captured. I guess then $e^X$ is the simplest and the most natural choice. $\endgroup$ – gmravi2003 Nov 19 '13 at 21:32
  • 1
    $\begingroup$ I haven't looked into it, but I suspect the exponential enjoys some particular properties, including those you name, which are critical: all coefficients should be strictly positive and it's handy that it converges absolutely everywhere. But I believe there are deeper reasons why this function is essential, related to properties of Fourier and Laplace transforms. It might be illuminating to explore the derivations of the measure inequalities to see just what properties of the exponential are really used! (+1) $\endgroup$ – whuber Nov 19 '13 at 23:53
  • $\begingroup$ @whuber that is a nice observation. I currently find the moment explanation lacking. What does convince me though is the upper bound and separability properties of the exponent function. That is, $P\{x1+x2>0\}=E\{1[x1+x2>0]\} \leq E\{exp(t*x1)\}E\{exp(t*x2)\}$. So if $E\{exp(t*x1)\}<1$, the more i.i.d variables we average, the larger the power acting on this term. Thus giving an exponential bound. $\endgroup$ – Leo Nov 20 '13 at 23:30
  • $\begingroup$ I'd like to interest you in a question about this bound's tightness: stats.stackexchange.com/questions/77019/… $\endgroup$ – Leo Nov 20 '13 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.