Hoeffding Bounds for Independent Nonidentical Observations

Why Independence Does Not Require Identical Distributions

A sample average is often centered at a single population mean. That is appropriate when observations share a distribution, but it is not necessary for concentration. If the observations are independent and bounded, each may have its own distribution and its own expectation. The relevant center is then the average of those individual expectations.

This distinction matters in learning problems where different observations may come from different distributions, or where the expected loss varies across observation positions. Independence still lets us control the moment-generating function of the centered sum. Boundedness controls each factor, even when those factors are not identical.

Hoeffding’s Lemma for One Bounded Variable

The basic ingredient is a bound on the moment-generating function of a bounded variable after centering. It does not depend on the variable’s distribution beyond its range.

Proof. If \(a=b\), then \(X=a\) almost surely and the left side equals 1, so the result holds. Otherwise, set \(Z=(X-a)/(b-a)\), so \(0\leq Z\leq1\), and write \(p=E[Z]\). For any real \(t\), convexity of the exponential function implies that its value at a point in \([0,1]\) is no greater than the linear interpolation between its endpoint values:

Taking expectations and multiplying by the centering factor gives

For \(0<p<1\), define \(h(t)=\log(1-p+pe^t)-pt\). The cases \(p=0\) and \(p=1\) give a constant \(Z\) and the desired inequality immediately. In the remaining case, \(h(0)=h'(0)=0\), and

Taylor’s formula with integral remainder, valid for positive and negative \(t\), now yields

Thus \(E[e^{t(Z-p)}]\leq e^{t^2/8}\). Since \(X-E[X]=(b-a)(Z-p)\), taking \(t=\lambda(b-a)\) proves the lemma. \(\square\)

The Independent, Nonidentical Hoeffding Bound

For each observation, let \(c_i=b_i-a_i\) be the width of its known range, and define \(V=\sum_{i=1}^n c_i^2\). Independence allows the moment-generating functions of the centered observations to multiply. This is the step that makes the result apply without identical distributions.

Proof. Write \(S=\sum_{i=1}^n(X_i-\mu_i)\). For \(\lambda>0\), independence and Hoeffding’s lemma give

Markov’s inequality applied to \(e^{\lambda S}\) therefore gives

The right side is minimized over \(\lambda>0\) at \(\lambda=4t/V\). Substitution gives \(P(S\geq t)\leq e^{-2t^2/V}\). Apply the same argument to \(-S\), whose centered summands have the same range widths, to obtain the lower-tail bound. The two-sided result follows by applying the union bound to the upper- and lower-tail events with \(t=n\varepsilon\). If \(V=0\), every \(X_i\) is constant almost surely, so the centered sum is zero and every positive-deviation probability is zero. \(\square\)

If every observation has a common known range of width \(c\), then \(V=nc^2\), and the average bound becomes \(2\exp(-2n\varepsilon^2/c^2)\). When the ranges differ, keeping the sum of squared widths \(V\) can give a sharper statement than replacing all ranges by the largest one.

Application to Observation-Specific Expected Losses

Suppose a fixed predictor \(h\) is evaluated on independent observations \(Z_1,\ldots,Z_n\), which need not have the same distribution. Let the loss at observation \(i\) be \(X_i=\ell(h,Z_i)\), and assume \(0\leq\ell(h,Z_i)\leq1\) almost surely for every \(i\). Define \(R_i(h)=E[\ell(h,Z_i)]\), the expected loss under the distribution of observation \(i\). The empirical average loss concentrates around \(\frac{1}{n}\sum_i R_i(h)\).

This application does not assert that all observations estimate one common population risk. When the observation distributions differ, the natural target for this average is the average of the individual expected losses. Concentration controls the empirical average around that target.

Common Mistake: Centering at a Fictional Shared Mean

A tempting but incorrect step is to write \(E[X_i]=\mu\) for every \(i\) simply because all variables are being averaged. Independence does not imply equal distributions or equal expectations. The correction is to center each term separately:

and then express the average’s center as \(\bar{\mu}=n^{-1}\sum_i\mu_i\). A second common mistake is to treat the sum as having range width \(b_n-a_n\), or to use only one observation’s range. The sum’s squared-width quantity is \(\sum_i(b_i-a_i)^2\), because each independent centered term contributes its own range-width square to the moment-generating-function bound.