Diagnosing Invalid Concentration Arguments

Why Concentration Arguments Need an Assumption Audit

A concentration inequality is not a formula that can be applied whenever a sample average appears. Its conclusion depends on the structure of the data and on what is known about the random variables being averaged. A correct inequality used with the wrong hypotheses can give a confidently wrong answer.

For a predictor $h$, write its loss on an observation $Z$ as $\ell_h(Z)$, its risk as $R(h)=E[\ell_h(Z)]$, and its empirical risk on observations $Z_1,\ldots,Z_n$ as $\widehat R_n(h)=n^{-1}\sum_{i=1}^n\ell_h(Z_i)$. A typical concentration claim controls the difference between these risks. Before using one, check whether the observations are independent, whether the loss has the required tail or range, whether $h$ was fixed independently of the data, and whether the variance in the formula is actually known.

The examples below focus on four common failures. They also distinguish an invalid argument from a valid bound that is simply too weak to be useful.

What the Standard Bounds Actually Require

Theorem: Let $X_1,\ldots,X_n$ be independent random variables with $a<b$ and $P(a\le X_i\le b)=1$ for every $i$, and let $\mu_i=E[X_i]$. For every $t>0$, $$ P\left(\left|\frac{1}{n}\sum_{i=1}^n(X_i-\mu_i)\right|\ge t\right) \le 2\exp\left(-\frac{2nt^2}{(b-a)^2}\right). $$ The variables need not have identical distributions. Independence and the common bounded interval are essential hypotheses of this version of Hoeffding’s inequality.

Here is a derivation, including the moment-generating-function step. For any random variable $X$ in $[a,b]$, convexity of the exponential gives, for $x\in[a,b]$, $\exp(\lambda x)\le \frac{b-x}{b-a}\exp(\lambda a)+\frac{x-a}{b-a}\exp(\lambda b)$. Taking expectations and centering at $\mu=E[X]$ reduces the resulting bound to the two-point expression $(1-p)\exp(-pu)+p\exp((1-p)u)$, where $p=(\mu-a)/(b-a)$ and $u=\lambda(b-a)$.

To bound that expression, let $g(u)=\log(1-p+p\exp(u))-pu$. Then $g(0)=g'(0)=0$, while $g''(u)=q(u)(1-q(u))\le 1/4$, where $q(u)=p\exp(u)/(1-p+p\exp(u))$. Integrating the second-derivative bound from zero to $u$, for either sign of $u$, gives $g(u)\le u^2/8$. Thus $E[\exp(\lambda(X-\mu))]\le\exp(\lambda^2(b-a)^2/8)$.

Independence lets us multiply these moment-generating-function bounds for the $n$ centered variables. Markov’s inequality therefore gives, for $\lambda>0$, $P(\sum_i(X_i-\mu_i)\ge nt)\le\exp(-\lambda nt+n\lambda^2(b-a)^2/8)$. Choosing $\lambda=4t/(b-a)^2$ gives the upper-tail bound $\exp(-2nt^2/(b-a)^2)$. Applying the same argument to the negatives gives the lower-tail bound; adding the two probabilities proves the displayed inequality. $\square$

For bounded losses in $[0,1]$, the result has $a=0$ and $b=1$. In particular, at $t=1/2$, its right-hand side is $2\exp(-n/2)$, not $2\exp(-n)$. Checking the constants in the exponent is part of checking the argument.

Result: If $H$ is a fixed finite set of $M$ predictors, the observations are independent and identically distributed, and every loss $\ell_h(Z_i)$ lies in $[0,1]$, then for every $t>0$, $$ P\left(\max_{h\in H}|\widehat R_n(h)-R(h)|\ge t\right) \le 2M\exp(-2nt^2). $$ Consequently, with probability at least $1-\delta$, every $h\in H$ satisfies $$ |\widehat R_n(h)-R(h)|\le \sqrt{\frac{\log(2M/\delta)}{2n}}, \qquad 0<\delta<1. $$

For each fixed $h$, Hoeffding’s inequality bounds the probability of a deviation of at least $t$ by $2\exp(-2nt^2)$. The event that the maximum deviation is at least $t$ is the union, over $h\in H$, of the corresponding fixed-predictor events. The union bound gives a probability no greater than the sum of their probabilities, namely $2M\exp(-2nt^2)$. Setting this quantity equal to $\delta$ and solving for $t$ yields the stated confidence bound. $\square$

Worked Example: A Pointwise Bound Is Not a Selection Bound

Let each observation be $Z_i=(Z_{i1},\ldots,Z_{iM})$, with all coordinates independent Bernoulli random variables with success probability $1/2$, and let the observations be independent across $i$. Define predictor $h_j$ to have loss $\ell_{h_j}(Z_i)=Z_{ij}$. For every fixed $j$, the risk is $1/2$, and Hoeffding’s inequality applies.

Now select a predictor after seeing the sample: choose the first $j$ whose $n$ observed losses are all zero, if such a coordinate exists. For each $j$, the probability of all-zero losses is $2^{-n}$. These events are independent across the $M$ coordinates, so the probability that at least one predictor has empirical risk zero is $1-(1-2^{-n})^M$.

For $n=5$ and $M=32$, this probability is $1-(31/32)^{32}$, approximately $0.638$. When selection succeeds, the selected predictor has empirical risk zero but true risk $1/2$. Thus it has an absolute deviation of $1/2$ with probability about $0.638$. A fixed-predictor bound at that deviation is $2\exp(-2\cdot5\cdot(1/2)^2)=2\exp(-2.5)$, approximately $0.164$. It cannot be asserted as a bound for this data-selected predictor. For the finite class, the derived bound includes the factor $M$; it accounts for the possibility of finding an unusually favorable predictor among many candidates.

Failure 1: Treating Dependent Observations as Independent

The standard sample-mean form of Hoeffding’s inequality requires independence. Having bounded observations with the right marginal distribution is not enough. Dependence can prevent averaging from reducing variability.

Worked Example: Repeated Copies of One Random Variable

Let $B\sim\operatorname{Bernoulli}(1/2)$, and set $X_i=B$ for every $i=1,\ldots,4$. Each $X_i$ lies in $[0,1]$ and has mean $1/2$, but the four observations are perfectly dependent. Their sample mean is $B$, so $P(|\bar X-1/2|\ge 1/2)=1$.

If one incorrectly applied the independent-observation Hoeffding bound, its right-hand side at $n=4$ and $t=1/2$ would be $2\exp(-2\cdot4\cdot(1/2)^2)=2\exp(-2)$, approximately $0.271$. This contradicts the actual probability $1$. The calculation is not a counterexample to Hoeffding’s inequality: its independence hypothesis is violated.

The variance calculation shows the same failure. Each $X_i$ has variance $1/4$, but $\operatorname{Var}(\bar X)=1/4$, not $1/(4n)$. In general, $\operatorname{Var}(\bar X)=n^{-2}\sum_i\operatorname{Var}(X_i)+2n^{-2}\sum_{i<j}\operatorname{Cov}(X_i,X_j)$. The covariance terms vanish for independent observations; they need not vanish for dependent ones. A dependent-data bound requires assumptions that address the actual dependence structure.

Failure 2: Using a Bounded-Loss Inequality for Unbounded Losses

Hoeffding’s inequality requires a known finite interval containing each variable. Finite expectation alone does not supply such a range or guarantee a particular exponential tail. Conversely, an unbounded variable may still admit a useful bound under other assumptions, such as a suitable sub-Gaussian or sub-exponential condition. The point is to use a result whose hypotheses match the loss distribution.

Worked Example: A Rare, Large Loss

For a given sample size $n$, let $X_i$ be independent with $P(X_i=2n)=1/(2n)$ and $P(X_i=0)=1-1/(2n)$. Each variable has mean $E[X_i]=(2n)(1/(2n))=1$.

The event that all $n$ observations equal zero has probability $(1-1/(2n))^n$. On that event, the sample mean is zero, so its deviation from the mean is $1$. For $n=10$, this event has probability $0.95^{10}$, approximately $0.599$.

A claim using the $[0,1]$ Hoeffding bound at $t=1$ would give $2\exp(-20)$, approximately $4.12\times10^{-9}$, far below the actual event probability. The claim fails because $X_i$ can equal $20$, not because Hoeffding’s inequality fails. If the range $[0,2n]$ is used instead, the inequality is valid but gives $2\exp(-1/(2n))$, which is not a useful small upper bound here. Knowing that the mean is finite does not make the bounded-loss assumption true.

Failure 3: Substituting an Observed Variance for a Population Variance

Variance-sensitive inequalities have their own hypotheses. For example, if $X_1,\ldots,X_n$ are independent and identically distributed, $E[X_i]=\mu$, $\operatorname{Var}(X_i)=v<\infty$, and $|X_i-\mu|\le b$ almost surely, Bernstein’s inequality gives, for $t>0$, $$ P(|\bar X-\mu|\ge t)\le 2\exp\left(-\frac{nt^2}{2(v+bt/3)}\right). $$ The variance $v$ here is a property of the distribution, not the sample variance observed after drawing the data. Replacing it mechanically with a random estimate does not preserve the theorem.

Worked Example: Zero Sample Variance Does Not Mean Zero Risk

Let $X_i$ be independent Bernoulli variables with success probability $p=1/(2n)$. Then $\mu=p$. Suppose every observed value is zero. The empirical mean is zero and the sample variance $S^2=(n-1)^{-1}\sum_i(X_i-\bar X)^2$ is also zero (for $n>1$).

For $n=10$, this all-zero sample occurs with probability $0.95^{10}$, approximately $0.599$, even though the population mean is $0.05$. A naive variance-only interval centered at $\bar X$, with a radius proportional to $S/\sqrt n$, would have radius zero and fail to cover the mean on this event. It cannot be justified by a population-variance inequality simply by inserting $S^2$ for $v$.

This does not rule out empirical Bernstein bounds. Such results add appropriate correction terms and state their own conditions; the sample variance alone is not a direct replacement in the population-variance formula. Nor is Chebyshev’s inequality a remedy for unknown variance: its usual sample-mean version requires the actual variance $v$, and states $P(|\bar X-\mu|\ge t)\le v/(nt^2)$ for independent, identically distributed observations with finite variance.

A Practical Assumption Audit

Before trusting a concentration claim, inspect the object being bounded and the route by which it was chosen. A predictor fixed before observing the sample can have a pointwise risk bound even when the same bound does not apply unchanged to a predictor selected to minimize empirical risk. For a finite set of candidates, a union bound is one direct correction; the required factor depends on the number of candidates. More general classes require additional arguments beyond a single fixed-predictor inequality.

Likewise, a variance-sensitive result does not automatically become data-adaptive when its population variance is unknown. If the variance estimate is random, a theorem must account for its randomness. If the loss is unbounded, check whether a tail condition, a moment assumption, or a truncation argument is available rather than silently treating the loss as bounded.

Key takeaway: Match each concentration inequality to its exact assumptions. Check independence or an appropriate dependence condition, the loss range or tail condition, whether the predictor was fixed or selected, and whether a variance is population-known or estimated. A familiar formula is not evidence that those conditions hold.

Common Mistake

A common but incorrect line of reasoning is: “Hoeffding’s inequality holds for every fixed predictor, and the predictor I report is one of those predictors, so the fixed-predictor bound applies to it.” The conclusion does not follow when the reported predictor was chosen using the same sample. The choice may favor a predictor whose empirical loss happens to be unusually small. For a finite candidate set, bound the maximum deviation with the union-bound result before selecting; do not treat the selected predictor as if it had been fixed in advance.

Check Your Understanding

For each claim, identify the missing assumption or explain why the stated correction is needed.

Why does the independent-observation Hoeffding inequality fail for repeated copies of a single Bernoulli variable?
For losses in $[0,1]$, what is the two-sided Hoeffding bound at deviation $t=1/2$, and why is the exponent $-n/2$?
In the finite-class result, where does the factor $M$ enter, and what does it protect against?
Why does finite expectation alone not justify applying a bounded-loss concentration inequality?
What is wrong with replacing the population variance in a Bernstein bound directly by the observed sample variance?