Bennett inequality
= Bennett inequality
{c}
{wiki}
Let $X_1,\ldots,X_n$ be <independent random variables> with zero <expected value>, $X_i\leq b$ <almost surely> for $b>0$, and $\sum_i\mathbb EX_i^2\leq v$ for $v>0$. For $t\geq0$, the <Bennett inequality> states
$$
\mathbb P\left(\sum_iX_i\geq t\right)\leq
\exp\left[-\frac{v}{b^2}h\left(\frac{bt}{v}\right)\right],\qquad h(u)=(1+u)\log(1+u)-u.
$$
Only an upper bound on each $X_i$ is needed for this upper tail. Apply the same result to $-X_i$ for a lower tail when the corresponding lower bounds are available.
To see the exponent, for $\lambda\geq0$ the pointwise bound
$$
e^{\lambda x}\leq1+\lambda x+\frac{x^2}{b^2}(e^{\lambda b}-1-\lambda b),\qquad x\leq b,
$$
follows because $(e^u-1-u)/u^2=\int_0^1(1-s)e^{su}\,ds$ is increasing in $u$. Taking <expected values>, using $1+z\leq e^z$, and multiplying by <independence> bounds the <moment-generating function> of the sum by $\exp[v(e^{\lambda b}-1-\lambda b)/b^2]$. The <Chernoff bound> is optimized at $\lambda=b^{-1}\log(1+bt/v)$, giving the result. The <Bennett rate function> is approximately quadratic for small deviations, with a stronger large-deviation shape than its quadratic approximation. If the total <variance> is zero, all centered variables vanish <almost surely> and the positive tail is zero.