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.

  • 0
    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.2010-11-01

1 Answers 1

2

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