4
$\begingroup$

The Hoeffding's inequality is $P(S_n - E[S_n] \geq \epsilon) \leq e^{-2\epsilon^2/k'}$, where $S_n = \sum_{i=1}^{n} X_i$, $X_i$'s are independent bounded random variables, and $k'$ depends on the random variables. In the proof of Hoeffding's inequality, an optimization problem of the form is solved: $$\min_{s} \ \ e^{-s\epsilon}e^{ks^2}$$ subject to $s > 0$, to obtain a tight upper bound (which in turn yields the Hoeffding's inequality). It turns out that $s = \epsilon/2k$ is the value that obtains the Hoeffding's inequality. I don't see how.

EDIT: Note that $k > 0, \epsilon > 0$.

$\endgroup$
4
  • $\begingroup$ I see that the problem is convex. I hope I'm have not misinterpreted the way $s$ is found to tighten the bound. $\endgroup$
    – Naga
    Nov 1, 2010 at 4:07
  • $\begingroup$ Could you write up the proof or include a link to it somewhere? It would then be helpful if you could point exactly to the place in the proof where you are having trouble. $\endgroup$ Nov 1, 2010 at 5:12
  • $\begingroup$ Since $f(s)=e^{ks^2-s\epsilon}$ has derivative $f'(s)=(2ks-\epsilon) e^{ks^2-s\epsilon}$, which is negative for $s<\epsilon/2k$ and positive for $s>\epsilon/2k$, the minumum is attained at $s=\epsilon/2k$. Is that what's causing you trouble, or is it something else later on that you haven't told us about? $\endgroup$ Nov 1, 2010 at 7:09
  • $\begingroup$ Yes, I was making a silly mistake. I think that's it. However, even for the function to be convex, we need something $s >= \epsilon/2k$ I guess. $\endgroup$
    – Naga
    Nov 1, 2010 at 13:11

1 Answer 1

2
$\begingroup$

Since $\exp$ is monotone increasing, your problem is equivalent to minimizing the quadratic $ks^2 - \epsilon s = k(s - \epsilon/2k)^2 - \epsilon^2/4k$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .