Thanks for posting. Just wanted to make a comment that often the delta > 2e-1 case is treated separately, but for delta larger than some constant, it follows from the (e^delta / (1+delta)^{1+delta})^{mu} bound that the tail is actually something like exp(-Omega(delta * ln(delta) * mu))) (as opposed to just the exp(-Omega(delta*mu)) written in many places). This extra ln(delta) in the exponent can be important sometimes. Also, a slightly stronger tail bound which both implies Chernoff and dominates Bernstein is Bennett’s inequality, which really isn’t much harder to prove and doesn’t seem to get enough credit (e.g. it’s not in the Dubhashi and Panconesi book as far as I can tell). It says that if X_1,…,X_n are indep. with X their sum and sigma^2 = Var[X], and |X_i| t*sigma) <~ exp(-Omega(t^2 / sigma^2)) + (t K / sigma^2)^{-Omega(t/K)}
The last part got clobbered somehow and I can’t edit…the statement of Bennett is:
It says that if X_1,…,X_n are indep. with X their sum and sigma^2 = Var[X], and |X_i| t*sigma) <~ exp(-Omega(t^2 / sigma^2)) + (t K / sigma^2)^{-Omega(t/K)}
Jelani Nelson said: 2015.09.04 12:56
Hm, clobbered again …it seems the commenting feature doesn’t want me to write the tail bound. 🙂
Hey Sariel,
Thanks for posting. Just wanted to make a comment that often the delta > 2e-1 case is treated separately, but for delta larger than some constant, it follows from the (e^delta / (1+delta)^{1+delta})^{mu} bound that the tail is actually something like exp(-Omega(delta * ln(delta) * mu))) (as opposed to just the exp(-Omega(delta*mu)) written in many places). This extra ln(delta) in the exponent can be important sometimes. Also, a slightly stronger tail bound which both implies Chernoff and dominates Bernstein is Bennett’s inequality, which really isn’t much harder to prove and doesn’t seem to get enough credit (e.g. it’s not in the Dubhashi and Panconesi book as far as I can tell). It says that if X_1,…,X_n are indep. with X their sum and sigma^2 = Var[X], and |X_i| t*sigma) <~ exp(-Omega(t^2 / sigma^2)) + (t K / sigma^2)^{-Omega(t/K)}
It's mentioned here as exercise 3: https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/
The last part got clobbered somehow and I can’t edit…the statement of Bennett is:
It says that if X_1,…,X_n are indep. with X their sum and sigma^2 = Var[X], and |X_i| t*sigma) <~ exp(-Omega(t^2 / sigma^2)) + (t K / sigma^2)^{-Omega(t/K)}
Hm, clobbered again …it seems the commenting feature doesn’t want me to write the tail bound. 🙂
https://en.wikipedia.org/wiki/Bennett%27s_inequality
Thanks Jelani, I would look into these inequalities…
The far bound that you mentioned is used quite a bit. It would indeed be useful to mention it somehow…