Bernstein inequalities

Remarks

Proof idea: for $\lambda > 0$, the bound $\abs{X_i} \le M$ gives $E[e^{\lambda X_i}] \le \exp\left(E[X_i^2] \, \frac{e^{\lambda M} - 1 - \lambda M}{M^2}\right)$. The Chernoff bound with the best $\lambda$ then gives Bennett's inequality, and an elementary estimate of the resulting function gives the bound above. Applying the bound to $-X_i$ gives the same bound for the lower tail, so $P(\abs{\sum_i X_i} \ge t)$ is at most twice the right-hand side. For small $t$, the exponent is about $-t^2 / (2 \sigma^2)$, as for a normal variable with the true variance $\sigma^2$. For large $t$, it is about $-3t / (2M)$, an exponential tail. Example: take $n$ independent centred variables with $\abs{X_i} \le 1$ and $E[X_i^2] = p$ small. Hoeffding's inequality gives the exponent $-t^2 / (2n)$. Bernstein gives about $-t^2 / (2np)$ when $t$ is much smaller than $np$, which is much better. The name covers a family of related bounds; other versions replace the bound $\abs{X_i} \le M$ by moment conditions $E[\abs{X_i}^k] \le \frac{k!}{2} E[X_i^2] M^{k-2}$ for all $k \ge 2$.

Going deeper

For a student

Bernstein's inequality sits between Hoeffding's inequality, which uses only bounds on the range, and the central limit theorem, which describes the normal approximation but gives no bound for finite $n$. Its tail is Gaussian for moderate deviations and exponential for large ones, which matches the behaviour of sub-exponential variables. It is a standard tool in statistics, randomized algorithms and the theory of empirical processes.