Bernstein’s Condition and Tail Bounds

SECTION 01Bernstein’s Condition

Directly computing or bounding the MGF can be impractical. An alternative is to control the polynomial moments of X.

Definition · Bernstein’s Condition

Let X have mean μ = E[X] and variance σ² = E[(X − μ)²]. Bernstein’s condition with parameter b > 0 holds if

| E [{(X - μ)}^{k}] | \leq \frac{1}{2} k! σ^{2} b^{k - 2}, k = 2, 3, \dots

Claim · Bernstein’s Condition Implies Sub-Exponentiality

If X satisfies Bernstein’s condition, it is sub-exponential with parameters (ν, α) = (√2σ, 2b).

Proof of the Claim

Expand the exponential. The linear term vanishes because E[X − μ] = 0:

E [e^{λ (X - μ)}] = 1 + \frac{λ^{2} σ^{2}}{2} + \sum_{k = 3}^{\infty} \frac{λ^{k} E [{(X - μ)}^{k}]}{k!}

Applying Bernstein’s condition term by term gives

E [e^{λ (X - μ)}] \leq 1 + \frac{λ^{2} σ^{2}}{2} + \frac{λ^{2} σ^{2}}{2} \sum_{k = 3}^{\infty} {(| λ | b)}^{k - 2}

For |λ| < 1/b, summing the geometric series gives

E [e^{λ (X - μ)}] \leq 1 + \frac{\frac{λ^{2} σ^{2}}{2}}{1 - b | λ |} \leq e^{\frac{\frac{λ^{2} σ^{2}}{2}}{1 - b | λ |}}

Restricting to |λ| < 1/(2b) makes 1 − b|λ| ≥ 1/2, so

E [e^{λ (X - μ)}] \leq e^{λ^{2} σ^{2}} = e^{\frac{{(\sqrt{2} σ)}^{2} λ^{2}}{2}}

SECTION 02Bernstein-Type Bound

We could apply the preceding sub-exponential tail bound. Keeping the more precise MGF bound from the proof gives a sharper result.

Formulation · Bernstein-Type Bound

For any X satisfying Bernstein’s condition,

E [e^{λ (X - μ)}] \leq e^{\frac{\frac{λ^{2} σ^{2}}{2}}{1 - b | λ |}}, | λ | < \frac{1}{b}

The corresponding two-sided concentration bound is

P (| X - μ | \geq t) \leq 2 e^{- \frac{t^{2}}{2 (σ^{2} + b t)}}, t \geq 0

SECTION 03Bounded Variables and Comparison with Hoeffding

Example · A Bounded Variable Satisfies Bernstein’s Condition

Suppose |X − μ| ≤ b. For every integer k ≥ 2,

| E [{(X - μ)}^{k}] | \leq E [{| X - μ |}^{k}] \leq b^{k - 2} σ^{2} \leq \frac{k!}{2} σ^{2} b^{k - 2}

Thus Bernstein’s condition holds. Hoeffding uses the range [μ − b, μ + b], giving

P (| X - μ | \geq t) \leq 2 e^{- \frac{t^{2}}{2 b^{2}}}

Bernstein instead uses the actual variance σ²:

P (| X - μ | \geq t) \leq 2 e^{- \frac{t^{2}}{2 (σ^{2} + b t)}}

(1) For small deviations with bt ≪ σ², the Bernstein bound has approximately the Gaussian form 2 exp(−t²/(2σ²)).

(2) Since σ² ≤ b², the variance can be much smaller than the range-based scale b². Bernstein is tighter than the displayed Hoeffding bound when σ² + bt < b², though it is not uniformly tighter for every t.

SECTION 04One-Sided Bounds

A bound on |X| is sufficient for Bernstein’s condition to hold. If we only have a one-sided bound, we can still derive a bound on the corresponding tail.

Formulation · One-Sided Bernstein MGF Bound

Let X have a finite second moment and satisfy X ≤ b almost surely, for some b > 0. Then

E [e^{λ (X - E [X])}] \leq e^{\frac{\frac{λ^{2}}{2} E [X^{2}]}{1 - \frac{b λ}{3}}}, 0 \leq λ < \frac{3}{b}

SECTION 05Independent Sums

Formulation · One-Sided Bernstein Tail Bound

For independent variables X₁, …, Xₙ with finite second moments and Xₖ ≤ b almost surely, the MGF bound gives, for δ ≥ 0,

P (\sum_{k = 1}^{n} (X_{k} - E [X_{k}]) \geq n δ) \leq e^{- \frac{n δ^{2}}{2 (\frac{1}{n} \sum_{k = 1}^{n} E [{X_{k}}^{2}] + \frac{b δ}{3})}}

SECTION 06Lower Tails of Nonnegative Variables

If a variable is bounded from below, apply the upper-tail result to −X to control its lower tail.

Formulation · Nonnegative Variables

In particular, let Y₁, …, Yₙ be independent nonnegative variables with finite second moments. Then, for δ ≥ 0,

P (\sum_{k = 1}^{n} (Y_{k} - E [Y_{k}]) \leq - n δ) \leq e^{- \frac{n δ^{2}}{2 \frac{1}{n} \sum_{k = 1}^{n} E [{Y_{k}}^{2}]}}