Choosing Hoeffding or Bernstein from Tail Diagnostics

Why Compare the Two Bounds?

For a fixed predictor, a bounded loss makes concentration guarantees available, but it does not by itself tell us which guarantee will be informative. Hoeffding’s inequality uses the loss range; Bernstein’s inequality also uses the variance. When the variance is small relative to the squared range, Bernstein can give a much sharper tail bound. When it is not, Hoeffding may give the stronger guarantee. The comparison depends on the deviation size as well as on the distribution’s variance and range.

Here we make that choice explicit. We work with independent, identically distributed losses, as in the fixed-predictor setting. The same comparison principle applies to other versions of the inequalities when their assumptions and variance terms are adjusted accordingly.

Setup: Let \(Z_1,\ldots,Z_n\) be independent and identically distributed losses with \(0\leq Z_i\leq R\), where \(R>0\). Write \(\mu=E[Z_i]\), \(\bar Z=n^{-1}\sum_{i=1}^n Z_i\), and assume \(\operatorname{Var}(Z_i)\leq v\). The range width is \(R\), and \(v\) has units of loss squared.

The Two Guarantees on the Same Scale

For any \(t>0\), Hoeffding’s inequality and Bernstein’s inequality give the following two-sided bounds:

P\!\left(|\bar Z-\mu|\geq t\right) \leq 2\exp\!\left(-\frac{2nt^2}{R^2}\right) \quad\text{(Hoeffding)}

P\!\left(|\bar Z-\mu|\geq t\right) \leq 2\exp\!\left(-\frac{nt^2}{2v+(2/3)Rt}\right) \quad\text{(Bernstein).}

Each right-hand side is a valid upper bound; if it exceeds 1, it may be replaced by the trivial bound 1. To compare the guarantees at a particular \(t\), compare their exponents. A larger positive exponent produces a smaller exponential bound. The factor 2 is the same in both inequalities, so it does not affect which one is smaller.

Comparison rule: At a specified deviation \(t\), Bernstein’s exponential bound is no larger than Hoeffding’s when \(2v+(2/3)Rt\leq R^2/2\), or equivalently \(v\leq R^2/4-Rt/3\). If the right-hand side is negative, this condition cannot hold for a nonnegative variance bound \(v\).

The rule follows directly from the exponents: Bernstein’s denominator is \(2v+(2/3)Rt\), while Hoeffding’s exponent can be written as \(nt^2/(R^2/2)\). Because both exponents have the same numerator \(nt^2\), Bernstein has the larger exponent precisely when its denominator is no larger. Rearranging gives the stated condition. In particular, small variance helps Bernstein, but the linear term \((2/3)Rt\) grows with the threshold. At sufficiently large \(t\), even a very small variance need not make the Bernstein exponent larger.

This is a comparison of these two upper bounds, not a statement that either bound equals the true tail probability. Both can be conservative, and neither necessarily captures every feature of a particular loss distribution.

Worked Examples: Diagnosing the Bounds

Worked Example: Rare Binary Losses

Suppose each loss is Bernoulli with \(P(Z_i=1)=0.01\), and take \(n=1000\). Then \(R=1\), \(\mu=0.01\), and \(v=\operatorname{Var}(Z_i)=0.01(0.99)=0.0099\). Compare the two bounds at \(t=0.08\).

For Hoeffding, the exponent is \(2nt^2/R^2=2(1000)(0.08)^2=12.8\). Thus the bound is \(2e^{-12.8}\approx 5.52\times 10^{-6}\).

For Bernstein, the denominator is \(2v+(2/3)Rt=2(0.0099)+(2/3)(1)(0.08)=0.0198+0.053333\ldots=0.073133\ldots\). The numerator is \(nt^2=1000(0.08)^2=6.4\), so the exponent is approximately \(6.4/0.073133=87.51\). The Bernstein bound is therefore approximately \(2e^{-87.51}\approx 1.97\times 10^{-38}\). At this threshold, the variance-sensitive guarantee is substantially smaller.

Check what event the two-sided probability describes. The lower-deviation event would require \(\bar Z\leq\mu-t= -0.07\), which is impossible because \(\bar Z\geq0\). The upper-deviation event requires \(\bar Z\geq\mu+t=0.09\), which is possible: among 1000 Bernoulli observations, for example, 90 losses equal to 1 give \(\bar Z=0.09\). So the two-sided event is possible, although this calculation alone does not determine its exact probability.

Worked Example: Variance Does Not Always Make Bernstein Better

Now let \(Z_i\) be Bernoulli with success probability \(1/2\), so \(R=1\), \(\mu=1/2\), and \(v=1/4\). For \(n=100\) and \(t=0.2\), Hoeffding gives exponent \(2(100)(0.2)^2=8\), hence the bound \(2e^{-8}\approx0.000671\).

Bernstein’s denominator is \(2(1/4)+(2/3)(1)(0.2)=0.5+0.133333\ldots=0.633333\ldots\). Its numerator is \(100(0.2)^2=4\), giving exponent \(4/0.633333\ldots\approx6.316\). Its bound is approximately \(2e^{-6.316}\approx0.00362\), which is larger than Hoeffding’s bound.

The comparison condition gives the same conclusion: \(R^2/4-Rt/3=0.25-0.066667\ldots\approx0.1833\), while \(v=0.25\) exceeds this value. Here the variance is not small enough, relative to the range and this threshold, for the Bernstein exponent to win.

Choosing a Bound at a Confidence Level

A common task is to find a deviation radius that makes the probability of error at most \(\delta\), where \(0<\delta<1\). Put \(x=\log(2/\delta)\). Solving the Hoeffding inequality for \(t\) gives the radius

t_H=R\sqrt{\frac{x}{2n}}.

For Bernstein, require \(nt^2/(2v+(2/3)Rt)\geq x\). Since the denominator is positive, this is equivalent to \(nt^2-(2/3)Rx\,t-2vx\geq0\). The nonnegative radius at which equality holds is

t_B= \frac{(2/3)Rx+\sqrt{((2/3)Rx)^2+8nvx}}{2n}.

To see why this is the relevant root, the quadratic has leading coefficient \(n>0\). If \(v>0\), its constant term \(-2vx\) is negative, so it has one positive and one negative root; the displayed expression is the positive root from the quadratic formula. If \(v=0\), it factors as \(t(nt-(2/3)Rx)\), with roots \(0\) and \(2Rx/(3n)>0\). The displayed expression still gives the positive root. In either case, any \(t\geq t_B\) satisfies the required quadratic inequality and hence yields the Bernstein confidence guarantee.

Worked Example: Comparing Confidence Radii

Suppose \(R=1\), \(n=100\), and a justified variance bound is \(v=0.01\). For confidence level \(1-\delta=0.95\), \(x=\log(2/0.05)=\log(40)\approx3.6889\).

The Hoeffding radius is \(t_H=\sqrt{3.6889/200}=\sqrt{0.0184445}\approx0.1358\).

For Bernstein, \((2/3)Rx=(2/3)(3.6889)\approx2.4593\), and \(8nvx=8(100)(0.01)(3.6889)\approx29.5112\). Therefore, \[ t_B=\frac{2.4593+\sqrt{2.4593^2+29.5112}}{200} \approx\frac{2.4593+\sqrt{35.5590}}{200} \approx\frac{8.4224}{200} \approx0.0421. \] The Bernstein radius is much smaller. This comparison is valid only if \(v=0.01\) is a valid population-variance bound for the losses; an observed sample variance cannot automatically be substituted into this fixed-variance inequality.

A Practical Diagnostic

A disciplined comparison has four steps:

Identify a valid range.
Use a bound \(0\leq Z_i\leq R\) that holds for every loss. A tighter valid range can improve both inequalities.

Check the variance information.
Use a known variance or a valid upper bound \(v\). The variance must refer to the random loss distribution under consideration.

Fix the target.
For a tail comparison, specify \(t\); for a confidence comparison, specify \(\delta\) and compute both radii.

Compare the guarantees.
Use \(v\leq R^2/4-Rt/3\) for a fixed threshold, or compare \(t_B\) and \(t_H\) at the desired confidence level.

A range bound can be conservative. If losses are known to lie in a smaller interval than the nominal loss scale suggests, use the smaller valid width. Conversely, a small-looking sample variance is not itself a justification for plugging that value into the population Bernstein inequality. Empirical Bernstein guarantees require their own stated conditions and correction terms; they are not obtained by simply replacing \(v\) with the sample variance.

Common Mistakes and Why the Choice Matters

Choosing Bernstein just because it uses variance. Its variance term can make the bound much sharper, but its linear-in-\(t\) term also matters. Compare the denominators at the target threshold.
Comparing variances without checking the scale. The relevant comparison is between \(v\), \(R^2\), and \(Rt\), not whether a variance seems small in isolation.
Calling an event impossible from the range without checking the threshold. For losses in \([0,1]\) with mean \(0.01\), a deviation \(t=0.8\) has an impossible lower side, but its upper side requires \(\bar Z\geq0.81\), which is possible. The whole two-sided event is therefore possible.
Treating a tail bound as the true tail probability. The bounds are guarantees, not exact probabilities. A valid bound may be much larger than the actual tail, or may be uninformative if its right-hand side exceeds 1.
Using an unsupported variance estimate. The standard Bernstein guarantee uses a valid variance bound for the losses. Replacing it with an empirical variance requires an empirical Bernstein result, not just algebraic substitution.

The purpose of the diagnostic is not to declare one inequality universally superior. It is to select the tighter valid guarantee for the information available and the deviation or confidence level of interest. When variance is low compared with the squared range, Bernstein can improve dramatically; when it is not, Hoeffding may be preferable.

Check Your Understanding

For each question, attend to the range, variance, and threshold rather than choosing a bound by name alone.

For losses in \([0,R]\), derive the condition under which the Bernstein exponent is at least the Hoeffding exponent at a fixed \(t>0\).
If \(R=1\), \(t=0.1\), and \(v=0.1\), does the comparison condition favor Bernstein or Hoeffding?
Why is a two-sided deviation event not necessarily impossible when its lower-deviation side is impossible?
What is the positive Bernstein confidence radius when \(v=0\), and why does the quadratic have a zero root as well?
Why is it not valid to substitute the observed sample variance directly into the standard population-variance Bernstein bound?