Bennett's Inequality and Its Bernstein Comparison

Why a Variance-Sensitive Bound Has More Than One Form

For a sum of independent centered variables, an upper bound on each summand and the sum’s variance together control its upper tail. Bernstein’s inequality expresses this control through a simple rational function of the deviation. Bennett’s inequality uses a different deviation function: it retains more detail from the exponential-moment calculation and gives a tail bound at least as strong as Bernstein’s under the same assumptions.

The comparison is useful because the two expressions describe different levels of approximation. At moderate deviations their exponents are close, while Bennett’s exponent grows faster for large values of the scaled deviation. The starting point is an upper bound on each centered summand, not necessarily a bound on its absolute value.

The function satisfies \(h(0)=0\) and \(h'(u)=\log(1+u)>0\) for \(u>0\), so it is increasing away from zero. Its local behavior is quadratic: \(h(u)=u^2/2+o(u^2)\) as \(u\) tends to zero. For large \(u\), it grows on the order of \(u\log u\). These features help explain how the resulting tail bound responds to different deviation sizes.

Deriving Bennett’s Bound

The key step is to control the moment-generating function of a single centered summand. For \(\lambda\ge 0\) and real \(x\), Taylor’s formula with integral remainder gives \[ e^{\lambda x}-1-\lambda x =\lambda^2x^2\int_0^1(1-s)e^{s\lambda x}\,ds. \] For fixed \(\lambda\ge0\), the integral on the right is nondecreasing in \(x\), since its integrand is nondecreasing in \(x\) for every \(s\in[0,1]\). Thus, whenever \(x\le b\), \[ e^{\lambda x}\le 1+\lambda x+ \frac{x^2}{b^2}\bigl(e^{\lambda b}-1-\lambda b\bigr). \] This includes negative \(x\); no lower bound on \(X_i\) is needed.

To prove the result, take expectations in the pointwise inequality with \(x=X_i\). Since \(E[X_i]=0\) and \(E[X_i^2]=\sigma_i^2\), \[ E[e^{\lambda X_i}] \le 1+\frac{\sigma_i^2}{b^2}\bigl(e^{\lambda b}-1-\lambda b\bigr) \le \exp\left\{\frac{\sigma_i^2}{b^2}\bigl(e^{\lambda b}-1-\lambda b\bigr)\right\}. \] The last step uses \(1+y\le e^y\) for \(y\ge0\). Independence gives \[ E[e^{\lambda S}] =\prod_{i=1}^n E[e^{\lambda X_i}] \le \exp\left\{\frac{v}{b^2}\bigl(e^{\lambda b}-1-\lambda b\bigr)\right\}. \] For \(\lambda>0\), Markov’s inequality applied to \(e^{\lambda S}\) now yields \[ P(S\ge t)\le \exp\left\{-\lambda t+\frac{v}{b^2} \bigl(e^{\lambda b}-1-\lambda b\bigr)\right\}. \] The exponent is minimized over \(\lambda\ge0\) at the solution of \[ -t+\frac{v}{b}(e^{\lambda b}-1)=0, \qquad \lambda_*=\frac{1}{b}\log\left(1+\frac{bt}{v}\right). \] Set \(u=bt/v\). Substituting \(\lambda_*\) gives \[ -\lambda_*t+\frac{v}{b^2} \bigl(e^{\lambda_*b}-1-\lambda_*b\bigr) =-\frac{v}{b^2}\bigl((1+u)\log(1+u)-u\bigr). \] This is the stated Bennett bound. If \(v=0\), every \(X_i\) has zero variance and mean zero, so each equals zero almost surely; the asserted tail probability follows. \(\square\)

The optimized parameter \(u=bt/v\) is dimensionless. It compares the requested deviation \(t\), scaled by the per-summand upper bound \(b\), with the total variance \(v\). Small \(u\) corresponds to the range where a quadratic approximation is accurate; larger \(u\) exposes the stronger growth of \(h(u)\).

Why Bennett Implies Bernstein

Bernstein’s inequality has a more compact denominator. The comparison follows from a lower bound on \(h\), which we prove rather than assume.

For the function inequality, define \[ g(u)=h(u)-\frac{3u^2}{2(u+3)}. \] We have \(g(0)=0\). Differentiating gives \[ g'(u)=\log(1+u)-\frac{3u(u+6)}{2(u+3)^2}. \] Call the right-hand side \(q(u)\). Then \(q(0)=0\), and direct differentiation gives \[ q'(u)=\frac{1}{1+u}-\frac{27}{(u+3)^3} =\frac{u^2(u+9)}{(1+u)(u+3)^3}\ge0. \] Therefore \(q(u)\ge0\) and \(g'(u)\ge0\) for \(u\ge0\). Since \(g(0)=0\), it follows that \(g(u)\ge0\), proving the claimed inequality. Substituting \(u=bt/v\) into it gives \[ \frac{v}{b^2}h\left(\frac{bt}{v}\right) \ge \frac{v}{b^2}\frac{(bt/v)^2}{2(1+bt/(3v))} =\frac{t^2}{2(v+bt/3)}. \] Applying Bennett’s inequality proves the Bernstein comparison. \(\square\)

For \(u>0\), the comparison is strict, so Bennett’s exponent is strictly larger and its upper bound strictly smaller. Near zero, \(h(u)\) is approximately \(u^2/2\). For large \(u\), Bennett’s deviation function grows roughly as \(u\log u\), whereas the Bernstein exponent’s corresponding function \(u^2/[2(1+u/3)]\) grows roughly as \(3u/2\). Thus the two bounds can differ more substantially at large scaled deviations.

Using the Bound Carefully

Bennett’s inequality is a one-sided statement: its assumption is \(X_i\le b\), and its conclusion bounds \(P(S\ge t)\). If an absolute two-sided bound \(|X_i|\le b\) is available, apply the same result to \(X_i\) and to \(-X_i\), then use the union bound: \[ P(|S|\ge t)\le 2\exp\left\{-\frac{v}{b^2}h\left(\frac{bt}{v}\right)\right\}. \] The factor of two comes from combining the upper and lower tails; it is not part of the one-sided Bennett bound.

A common mistake is to replace Bennett’s deviation function by its quadratic approximation \(h(u)\approx u^2/2\) for every \(u\). That approximation describes the behavior near zero, not the full function. For larger \(u\), using it as an equality can substantially misstate the exponent. Another error is to use \(b\) as though it were an upper bound on \(|X_i|\): for the upper-tail theorem, only \(X_i\le b\) is required, but the same \(b\) does not automatically bound the lower tail. Check the direction and size of the bound before applying the result.