Glivenko–Cantelli Classes

From Pointwise Laws to a Class-Wide Property

For one fixed function, the strong law of large numbers says that its empirical average converges to its expectation under standard integrability conditions. A learning problem, however, often considers many candidate functions at once. The relevant question is then whether the largest discrepancy across the whole class becomes small. A class with this property is called a Glivenko–Cantelli class.

Let $X_1,X_2,\ldots$ be independent and identically distributed observations with distribution $P$. For a measurable function $f$, write $Pf=E[f(X_1)]$, when this expectation exists, and define its empirical average by $P_n f=n^{-1}\sum_{i=1}^n f(X_i)$. Uniform convergence concerns the random supremum of $|P_n f-Pf|$ over a class, not just convergence for each fixed $f$.

Definition: Let $\mathcal F$ be a class of measurable, $P$-integrable real-valued functions. Assume the supremum below is measurable (for example, $\mathcal F$ is countable). The class is Glivenko–Cantelli for $P$, or $P$-Glivenko–Cantelli, if $$ \sup_{f\in\mathcal F}|P_n f-Pf|\xrightarrow{a.s.}0. $$ It is Glivenko–Cantelli in probability for $P$ if, for every $\varepsilon>0$, $$ P\!\left(\sup_{f\in\mathcal F}|P_n f-Pf|>\varepsilon\right)\longrightarrow 0. $$ If the relevant property holds for every distribution $P$ in a specified family, the class is called Glivenko–Cantelli for that family. Without a specified family, “Glivenko–Cantelli class” often means the property holds for every distribution under consideration.

The measurability condition matters: an uncountable supremum of measurable random variables need not itself be measurable. Countable classes avoid this issue, as do classes with suitable separability conditions. In the examples below, the suprema are measurable; for the threshold example, the supremum can be reduced to a countable set of sample-dependent endpoints.

Two Convergence Modes and a Basic Implication

Almost-sure convergence is the stronger pathwise statement: with probability one, the supremum deviation tends to zero as the sample grows. Convergence in probability says that the chance of exceeding any fixed positive tolerance tends to zero. These modes should be named explicitly; a class may be known to satisfy one without a proof of the other.

Proposition: If $\sup_{f\in\mathcal F}|P_n f-Pf|\xrightarrow{a.s.}0$, then $\sup_{f\in\mathcal F}|P_n f-Pf|\xrightarrow{p}0$.

Proof. Set $Z_n=\sup_{f\in\mathcal F}|P_n f-Pf|$. For fixed $\varepsilon>0$, let $A_n=\{Z_n>\varepsilon\}$. Almost-sure convergence implies that, with probability one, only finitely many of the events $A_n$ occur. Thus $P(\bigcap_{m\geq1}\bigcup_{n\geq m}A_n)=0$. The events $B_m=\bigcup_{n\geq m}A_n$ decrease with $m$, so continuity of probability for decreasing events gives $P(B_m)\to0$. For $n\geq m$, $A_n\subseteq B_m$; hence $P(A_n)\leq P(B_m)$. Taking $m$ large proves $P(A_n)\to0$. $\square$

Finite Classes: Pointwise Laws Become Uniform

A useful first case requires no sophisticated uniform-convergence machinery. If there are only finitely many functions, the strong law can be applied to each one and the finitely many conclusions combined.

Theorem: Let $\mathcal F=\{f_1,\ldots,f_M\}$, where $M<\infty$, and suppose $E[|f_j(X_1)|]<\infty$ for every $j$. Then $\mathcal F$ is $P$-Glivenko–Cantelli.

Proof. By the strong law of large numbers, for each $j\in\{1,\ldots,M\}$, $P_n f_j\to Pf_j$ almost surely. The intersection of these $M$ probability-one events still has probability one, because its complement is a finite union of probability-zero events. On that intersection, for any $\varepsilon>0$, each $j$ has an index $N_j$ such that $n\geq N_j$ implies $|P_n f_j-Pf_j|<\varepsilon$. Since there are finitely many indices, $N=\max_j N_j$ is finite. For $n\geq N$, every deviation is below $\varepsilon$, so $$ \sup_{f\in\mathcal F}|P_n f-Pf| =\max_{1\leq j\leq M}|P_n f_j-Pf_j|<\varepsilon. $$ This is almost-sure uniform convergence. $\square$

Worked Example: A Two-Function Class

Let $X_i\sim\operatorname{Bernoulli}(1/2)$, and consider $f_1(x)=x$ and $f_2(x)=1-x$. For a sample of $n=4$ observations, suppose the observed values are $1,0,1,1$. Then $P_n f_1=3/4$, while $Pf_1=1/2$, so the deviation for $f_1$ is $1/4$. For $f_2$, $P_n f_2=1/4$ and $Pf_2=1/2$, giving deviation $1/4$ again. Therefore the supremum deviation for this sample is $1/4$.

The numerical discrepancy at $n=4$ is not itself a convergence claim. The theorem applies because the class has only two functions and both are integrable. It gives $\max(|P_n f_1-Pf_1|,|P_n f_2-Pf_2|)\to0$ almost surely as $n$ grows.

Threshold Functions and Uniform CDF Convergence

An important infinite class consists of threshold indicators on the real line. For $t\in\mathbb R$, let $f_t(x)=\mathbf 1\{x\leq t\}$. Then $P f_t=F(t)$, where $F$ is the distribution function, and $P_n f_t=F_n(t)$, the empirical distribution function. Uniform convergence over this class is exactly $\sup_t|F_n(t)-F(t)|\to0$.

Theorem: If $F$ is continuous, the class $\{f_t:t\in\mathbb R\}$ is $P$-Glivenko–Cantelli. In particular, the empirical distribution function converges uniformly to $F$ almost surely.

Proof. Fix an integer $m\geq2$. Since $F$ is continuous and has limits 0 and 1 at the two tails, choose finite real numbers $t_1<\cdots<t_{m-1}$ such that $F(t_j)=j/m$. Set $t_0=-\infty$ and $t_m=+\infty$. For each fixed finite $j$, the strong law applied to $\mathbf 1\{X_i\leq t_j\}$ gives $F_n(t_j)\to F(t_j)$ almost surely. There are finitely many such points, so all these convergences hold together almost surely.

For $t_j\leq t\leq t_{j+1}$, monotonicity of both distribution functions gives $F_n(t_j)\leq F_n(t)\leq F_n(t_{j+1})$ and $F(t_j)\leq F(t)\leq F(t_{j+1})$. Since $F(t_{j+1})-F(t_j)=1/m$, these inequalities imply $$ |F_n(t)-F(t)| \leq \max\{|F_n(t_j)-F(t_j)|,\ |F_n(t_{j+1})-F(t_{j+1})|\}+\frac{1}{m}. $$ The same bound applies to the two tails using $F(t_1)=1/m$ and $1-F(t_{m-1})=1/m$. Taking the supremum over $t$ yields, almost surely, $$ \limsup_{n\to\infty}\sup_{t\in\mathbb R}|F_n(t)-F(t)|\leq\frac{1}{m}. $$ This reasoning holds for every integer $m\geq2$; intersecting the corresponding countably many probability-one events still gives an event of probability one. Letting $m\to\infty$ proves the result. $\square$

Worked Example: Uniform Thresholds on the Unit Interval

Let $X_i\sim\operatorname{Uniform}[0,1]$. Here $F(t)=0$ for $t<0$, $F(t)=t$ for $0\leq t\leq1$, and $F(t)=1$ for $t>1$. With $m=4$, choose cutpoints $t_1=1/4$, $t_2=1/2$, and $t_3=3/4$. The theorem’s monotonicity argument gives $$ \sup_t|F_n(t)-F(t)| \leq \max_{j=1,2,3}|F_n(t_j)-F(t_j)|+\frac14 $$ for every sample and every $n$. For any desired tolerance, choose $m$ large enough that $1/m$ is smaller than half that tolerance. The finitely many empirical proportions at the corresponding grid points converge by the strong law, so their maximum is eventually smaller than the other half, almost surely. Thus the full supremum tends to zero, not merely the deviations at the selected cutpoints.

Distribution-Specific Need Not Mean Distribution-Free

A class can have uniform convergence for one distribution and fail it for another. This is why a distribution-specific label such as $P$-Glivenko–Cantelli is informative. The following example also shows why infinitely many functions cannot be treated like a finite list.

Worked Example: Finite-Set Indicators

Take the sample space $[0,1]$ with its Borel sets, and let $\mathcal F$ contain $f_A(x)=\mathbf 1\{x\in A\}$ for every finite subset $A\subseteq[0,1]$. First let $P$ be the point mass at 0. For every finite $A$, all observations equal 0 almost surely. If $0\in A$, both $P_n f_A$ and $P f_A$ equal 1; if $0\notin A$, both equal 0. Consequently the supremum deviation is exactly 0 for every $n$, and the class is $P$-Glivenko–Cantelli.

Now let $P$ be the uniform distribution on $[0,1]$. For any realized sample $X_1,\ldots,X_n$, take the finite set $A=\{X_1,\ldots,X_n\}$. Then $P_n f_A=1$, while $P f_A=0$, because every finite set has uniform probability zero. Thus $$ \sup_{f\in\mathcal F}|P_n f-Pf|=1 $$ for every $n$, so the class is not Glivenko–Cantelli for the uniform distribution. The supremum here is measurable: it equals the constant 1. The same class therefore has different uniform-convergence behavior under two distributions.

Common Pitfall and Why the Property Matters

Common mistake: “For every fixed $f$, the law of large numbers gives $P_n f\to Pf$, so the supremum over $f$ must also converge to zero.” The conclusion does not follow. Pointwise convergence controls each fixed function, while the function attaining the largest deviation may change with the sample size. In the finite-set example, each fixed finite-set indicator obeys the strong law, yet a sample-dependent set makes the supremum deviation equal to 1.

A Glivenko–Cantelli condition is useful in statistical learning because it turns empirical averages into reliable approximations to population averages uniformly over a candidate class. That uniformity is what allows conclusions about data-selected functions, rather than only functions fixed before observing the sample. Always specify the class, the distributional scope, and whether convergence is almost sure or in probability.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

What additional claim does almost-sure Glivenko–Cantelli convergence make beyond convergence in probability?
Why does the finite-class theorem require only finitely many applications of the strong law?
For threshold indicators, what empirical quantity is the supremum deviation measuring?
In the finite-set example, why does the set $A=\{X_1,\ldots,X_n\}$ demonstrate failure for the uniform distribution?
Why does pointwise convergence for every fixed function not by itself imply uniform convergence over an infinite class?

What You'll Learn