One Law, Two Different Quantifiers
A law of large numbers gives a reliable statement about the empirical average of a fixed function. In learning problems, however, we often examine many functions and focus on whichever one has the largest empirical error. That function can change with the sample size, and even with the observed data. The distinction between a fixed function and a function selected from a class is the difference between a pointwise law and a uniform law.
Let \(X_1,X_2,\ldots\) be independent and identically distributed observations with distribution \(P\). For a measurable function \(f\) with finite expectation, write \(Pf=E[f(X_1)]\) and define its empirical average by \(P_n f=n^{-1}\sum_{i=1}^n f(X_i)\). The empirical deviation of \(f\) is \(|P_n f-Pf|\).
For a fixed bounded measurable \(f\), the strong law of large numbers gives \(P_n f\xrightarrow{a.s.}Pf\). The statement fixes \(f\) before observing the sample. Uniform convergence instead asks for one bound that applies at once to every function in \(\mathcal{F}\). Thus the pointwise statement has the form “for every fixed \(f\), the deviation vanishes,” whereas the uniform statement controls the supremum of deviations, including those from functions chosen after seeing the data.
Why a Finite Class Is Different
For a finite class, pointwise almost-sure convergence does imply uniform almost-sure convergence. The reason is elementary but important: only finitely many probability-one events need to hold simultaneously. For an infinite class, that argument no longer applies automatically.
Proof. For each \(j\), the strong law gives an event \(A_j\) of probability one on which \(P_n f_j\to Pf_j\). Since the class is finite, the intersection \(A=\bigcap_{j=1}^m A_j\) also has probability one: its complement is the finite union of the zero-probability events \(A_j^c\). Fix an outcome in \(A\), and let \(\varepsilon>0\). For every \(j\), convergence supplies an integer \(N_j\) such that \(n\ge N_j\) implies \(|P_n f_j-Pf_j|<\varepsilon\). Set \(N=\max_{1\le j\le m}N_j\). Then for every \(n\ge N\), all \(m\) deviations are below \(\varepsilon\), so their maximum is below \(\varepsilon\). This proves almost-sure convergence of the maximum to zero. \(\square\)
Worked Example: A Finite Class on Bernoulli Data
Let \(X_i\) be iid Bernoulli\((1/2)\) variables, and consider \(f_1(x)=x\) and \(f_2(x)=1-x\). For the observed sample \((1,0,1,1)\), calculate the two empirical deviations and their maximum.
The sample size is \(n=4\), and \(P f_1=P f_2=1/2\). The empirical average for \(f_1\) is $$ P_4 f_1=\frac{1+0+1+1}{4}=\frac{3}{4}, \qquad |P_4 f_1-Pf_1|=\left|\frac{3}{4}-\frac{1}{2}\right|=\frac{1}{4}. $$
For \(f_2\), the observed values are \((0,1,0,0)\), so $$ P_4 f_2=\frac{0+1+0+0}{4}=\frac{1}{4}, \qquad |P_4 f_2-Pf_2|=\left|\frac{1}{4}-\frac{1}{2}\right|=\frac{1}{4}. $$
Consequently, the maximum deviation over this two-function class is \(1/4\) for this sample. The theorem says that as the sample grows, both deviations—and therefore their maximum—converge almost surely to zero. The finite-class result does not say the observed deviations are already small at a particular sample size; it guarantees their eventual convergence.
An Infinite Class Can Defeat Pointwise Convergence
The following example gives a sharp contrast. Every fixed function in the class has empirical deviation zero almost surely, yet the supremum of deviations equals one for every sample size. The function witnessing the large deviation is selected from the observed data.
Worked Example: Indicators of Finite Sets
Let \(X_i\) be iid Uniform\([0,1]\). Let \(\mathcal{F}\) contain the indicator function \(f_A(x)=\mathbf{1}\{x\in A\}\) for every finite subset \(A\) of \([0,1]\). First fix any one finite set \(A\). Since the uniform distribution assigns probability zero to each point, it assigns probability zero to every finite set, so \(P f_A=P(A)=0\).
For this fixed \(A\), \(P(X_i\in A)=0\) for each \(i\). The probability that any observation ever belongs to \(A\) is also zero, because $$ P\left(\bigcup_{i=1}^{\infty}\{X_i\in A\}\right) \leq \sum_{i=1}^{\infty}P(X_i\in A)=0. $$ Thus \(P_n f_A=0\) for every \(n\), almost surely. In particular, each fixed function in the class obeys the pointwise law.
Now, for each realized sample size \(n\), choose the finite set \(A_n=\{X_1,\ldots,X_n\}\). This set contains every observed value, even if some observations are repeated. Therefore, $$ P_n f_{A_n}=\frac{1}{n}\sum_{i=1}^n \mathbf{1}\{X_i\in A_n\}=1, \qquad P f_{A_n}=0. $$ Every function in the class takes values between zero and one, so no deviation can exceed one. Since the selected function attains one, the supremum is exactly $$ \sup_{f\in\mathcal{F}}|P_n f-Pf|=1 $$ for every \(n\). Hence pointwise almost-sure convergence holds for each fixed function, but uniform convergence fails completely. The function \(f_{A_n}\) changes with the sample and with \(n\); it is not one fixed function to which the pointwise strong law applies.
This example also makes the quantifier issue concrete. For each fixed \(A\), the event that the sample never hits \(A\) has probability one. But the event “the sample never hits any finite set” is not the relevant conclusion: after observing the data, one can choose a finite set containing it. Probability-one statements for each individual member do not by themselves give a probability-one statement simultaneously over an unrestricted infinite class.
Not Every Infinite Class Fails
An infinite class can still have a vanishing supremum. The preceding example uses functions that can collect an entire sample into a set of population probability zero. Restricting the class can prevent that behavior.
Worked Example: Indicators of Singletons
Again let \(X_i\) be iid Uniform\([0,1]\), but now let \(\mathcal{F}\) contain only \(f_t(x)=\mathbf{1}\{x=t\}\), one function for each \(t\in[0,1]\). For every fixed \(t\), \(P f_t=0\), and the probability of observing \(t\) at any sample index is zero. Thus the pointwise deviation for this fixed function is almost surely zero.
For a given sample, \(P_n f_t\) is the fraction of observations equal to \(t\). Taking the supremum over \(t\) gives the largest sample proportion at any single observed value: $$ \sup_{t\in[0,1]}|P_n f_t-Pf_t| =\frac{1}{n}\max_{t\in[0,1]}\sum_{i=1}^n\mathbf{1}\{X_i=t\}. $$
For any two distinct indices \(i\ne j\), \(P(X_i=X_j)=0\) under the continuous uniform distribution. There are only countably many index pairs, so with probability one no pair of observations is equal. On that event, the maximum number of observations at any one value is exactly one. Consequently, the supremum is \(1/n\), which converges to zero. The class is infinite, but its uniform deviation vanishes.
The comparison matters: allowing a function to select an arbitrary finite set makes it possible to capture all observations, while allowing only a singleton captures at most one observation almost surely. The number of functions in a class alone does not determine whether a uniform law holds. The class’s structure determines how effectively its members can adapt to the observed sample.
A Useful Finite-Class Probability Bound
When the functions are bounded, the finite-class argument can also yield a probability bound. Suppose each \(f\in\mathcal{F}\) takes values in \([0,1]\), and \(\mathcal{F}\) has \(m\) members. Hoeffding’s inequality for a fixed \(f\) gives \(P(|P_n f-Pf|>\varepsilon)\leq 2e^{-2n\varepsilon^2}\). If the maximum deviation exceeds \(\varepsilon\), at least one member has deviation exceeding \(\varepsilon\). Applying the union bound to those \(m\) events gives $$ P\left(\max_{f\in\mathcal{F}}|P_n f-Pf|>\varepsilon\right) \leq 2m e^{-2n\varepsilon^2}. $$
The factor \(m\) records the cost of controlling multiple functions at once. For fixed finite \(m\), the right-hand side tends to zero as \(n\) grows. If the class is infinite, this direct union bound is unavailable: the expression would involve an infinite sum and need not be informative. Other methods are needed to establish uniform convergence for infinite classes; the pointwise strong law alone does not supply it.
Common Mistake: Applying the Law to a Data-Selected Function
A tempting but invalid argument is: “For every fixed \(f\), \(P_n f-Pf\) converges to zero. Therefore, if I choose the function with the largest observed deviation at each \(n\), that deviation also converges to zero.” The conclusion does not follow. The selected function \(f_n\) is not fixed as \(n\) varies, and the pointwise law gives no uniform control over such a sequence. In the finite-set example, \(f_n=f_{A_n}\) has deviation one at every \(n\), despite the pointwise law holding for every fixed class member.
Uniform control is important whenever a statistical procedure searches over many candidate predictors, rules, or models and reports the best empirical result. The reported choice is data-dependent, so a guarantee for each candidate considered separately may not control the selected candidate’s deviation. The central question is therefore not only whether every fixed function behaves well, but whether the whole class can adapt enough to make some empirical deviation large.
Check Your Understanding
Use the definitions and examples above to answer these questions.
- State the difference in quantifiers between pointwise almost-sure convergence and uniform almost-sure convergence.
- Why does a finite intersection of probability-one events suffice to prove the finite-class theorem?
- In the finite-subsets example, why does each fixed \(f_A\) have zero empirical average almost surely, but the supremum equal one?
- For the singleton class, what is the supremum of the deviations when all \(n\) observations are distinct?
- Why can a pointwise strong law not automatically be applied to a function chosen after observing the sample?