I am trying to solve the probability approximately correct learning problem and encountered the inequality, where $Z_i$ are i.i.d. random variables with range $0\leq Z_i \leq 1$ $$\Pr \left( \sum_{i=1}^n \frac{1}{n} (Z_i-\mathbb{E}Z_i)>\varepsilon \right) \leq \exp\left( \frac{-n\varepsilon^2}{2(\varepsilon/3+\mathbb{E}Z_i)} \right) $$ which required me to proved a concentration inequality with expectation at denominator. However, the Chernoff bound have expectation in numerator. May anyone give me some hints where to start?

  • 1
    $\begingroup$ When you write \mathrm{exp} instead of \exp, you don't get proper spacing in things like $x\exp y$ and $x\exp(y).$ Instead you see $x\mathrm{exp}y$ and $x\mathrm{exp}(y). \qquad$ $\endgroup$ – Michael Hardy Apr 10 '18 at 3:46
  • 2
    $\begingroup$ en.wikipedia.org/wiki/… Looks very similar to the Bernstein inequality, see if it help. $\endgroup$ – BGM Apr 10 '18 at 8:05

Your Answer

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

Browse other questions tagged or ask your own question.