Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
    
I see that the problem is convex. I hope I'm have not misinterpreted the way $s$ is found to tighten the bound. –  Naga Nov 1 '10 at 4:07
    
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. –  Mike Spivey Nov 1 '10 at 5:12
    
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? –  Hans Lundmark Nov 1 '10 at 7:09
    
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. –  Naga Nov 1 '10 at 13:11
add comment

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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