A Counterexample to ERM Consistency Without Uniform Convergence

Why Pointwise Convergence May Not Protect ERM

For a fixed predictor, the empirical risk is an average of observed losses. Under standard conditions, that average converges to the predictor’s population risk. But an empirical risk minimizer does not choose a predictor in advance: it searches the class after seeing the sample. In a sufficiently rich class, it can find a predictor that fits the observations by exploiting a feature of the sample that would not help on new data.

The distinction is between convergence for each fixed predictor and convergence uniformly over the entire class. The construction below makes the distinction exact: every fixed predictor’s empirical risk converges almost surely, yet an empirical minimizer has excess risk \(1/2\) at every sample size.

A Countable Class With Unseen Coordinates

Let the input space be \(\mathcal X=\{0,1\}^{\mathbb N}\), the set of infinite binary sequences. Give \(X\) the product distribution under which its coordinates \(X_j\), \(j\geq 1\), are independent Bernoulli random variables with success probability \(1/2\). Set the response \(Y=0\) with probability one, and use zero-one loss, \(\ell(a,y)=\mathbf 1\{a\ne y\}\).

Consider the countable predictor class consisting of the constant-zero predictor \(h_*\) and one predictor for each coordinate: \(h_j(x)=x_j\), for \(j\geq1\). The constant predictor is correct on every observation. Each coordinate predictor predicts one precisely when that coordinate is one.

Empirical Minimization Can Find a Perfectly Fitting Coordinate

For a sample of size \(n\), call coordinate \(j\) unseen in the positive direction if \(X_{ij}=0\) for every \(i=1,\ldots,n\). In that event \(h_j\) makes no errors on the sample, even though its population risk is \(1/2\). For each fixed coordinate, the probability of this event is \(2^{-n}\). The important feature is that there are infinitely many independent coordinates to search.

The specified first three coordinate patterns occur with probability \((1/4)(1/4)(1/4)=1/64\); later coordinates do not affect the claim that the first all-zero sample coordinate is the third. This example illustrates one possible sample. The result below shows that a suitable coordinate exists with probability one, for every fixed sample size.

Proof. For each \(n\), define \(J_n\) to be the smallest positive integer \(j\) for which \(X_{ij}=0\) for all \(i=1,\ldots,n\), if such a coordinate exists. For any fixed \(j\), the \(n\) sample entries in coordinate \(j\) are independent Bernoulli\((1/2)\), so the probability that all are zero is \(2^{-n}\). Also, the coordinate-vectors \((X_{1j},\ldots,X_{nj})\) are independent as \(j\) varies. Consequently, the probability that none of the first \(m\) coordinates is all zero is

Thus \(J_n\) exists almost surely. Its definition uses countably many measurable coordinate events, so \(J_n\), as a countably valued function of the sample, is measurable on the event of existence. Define it arbitrarily on the null event where it does not exist, and set \(\hat h_n=h_{J_n}\). By construction, \(\hat R_n(\hat h_n)=0\). Since empirical risks are nonnegative, this is a global empirical minimum, even though \(h_*\) is also an empirical minimizer. The selected predictor has population risk \(1/2\), so its excess risk is \(1/2\) almost surely.

For each fixed \(j\), the losses \(\ell(h_j(X_i),Y_i)=X_{ij}\) are independent and identically distributed Bernoulli\((1/2)\). The strong law of large numbers gives \(\hat R_n(h_j)\xrightarrow{a.s.}1/2=R(h_j)\). For \(h_*\), both empirical and population risks are zero. Since \(\mathcal H\) is countable, the intersection of these probability-one convergence events over all its predictors still has probability one. Thus all fixed predictors have convergent empirical risks simultaneously.

Finally, \(|\hat R_n(h_j)-R(h_j)|\leq1/2\) because \(\hat R_n(h_j)\in[0,1]\) and \(R(h_j)=1/2\), and the deviation for \(h_*\) is zero. But the selected coordinate has empirical risk zero, and hence deviation \(1/2\). Therefore, almost surely,

The probability-one statements above hold for each \(n\); taking a countable intersection over \(n\) makes them hold for every sample size simultaneously. This proves the theorem. \(\square\)

Worked Example: Truncating the Number of Coordinates

To see why the infinite class matters, retain only \(h_*\) and the first \(M\) coordinate predictors. Break ties in favor of a coordinate predictor whenever at least one of these coordinates is all zero on the sample; otherwise choose \(h_*\). For each coordinate the probability of an all-zero sample column is \(2^{-n}\), and these events are independent across the \(M\) coordinates. Hence the probability that the ERM selects a coordinate predictor is

If it selects a coordinate predictor, its excess risk is \(1/2\); if it selects \(h_*\), its excess risk is zero. The expected excess risk is therefore

For fixed \(M\), this tends to zero as \(n\) increases. In contrast, if the number of available coordinates is \(M_n=2^n\), then \((1-2^{-n})^{2^n}\to e^{-1}\), so the expected excess risk tends to \(\frac12(1-e^{-1})\), not zero. With infinitely many coordinates, the ERM finds an all-zero sample column with probability one at each finite \(n\), as established above.

What the Counterexample Shows

The pointwise statement has the quantifier order “for every fixed \(h\), the empirical risk converges.” ERM needs control of predictors that may change with the sample and with \(n\). In this example, the selected coordinate \(J_n\) is not fixed in advance. Its empirical risk is zero, even though each fixed coordinate eventually has empirical risk close to \(1/2\).

This is precisely why pointwise convergence alone does not imply ERM consistency. Uniform risk convergence would prevent the empirical risk of any selected predictor from differing greatly from its population risk. Here that protection is absent: the supremum deviation remains \(1/2\), and the empirical minimizer’s excess risk never decreases.