Uniform Convergence from Growth Functions

From Individual Accuracy to Uniform Accuracy

For one fixed event, the empirical proportion of observations in that event is close to its population probability with high probability. Learning, however, often selects an event or classifier after seeing the data. The relevant question is then simultaneous: how large can the discrepancy be among all members of a class? A bound for each fixed member does not by itself answer this question, because the selected member may depend on the sample.

The growth function measures how many distinct binary patterns a class can produce on a finite set of points. Combining this count with concentration gives a distribution-free bound on the largest empirical-to-population probability error. “Distribution-free” means that the bound holds for every underlying distribution $P$, not just for a particular model of the data.

Definition: Let $\mathcal H$ be a class of measurable functions $h:\mathcal X\to\{0,1\}$. For points $x_1,\ldots,x_m$, the class produces the vectors $(h(x_1),\ldots,h(x_m))$ as $h$ ranges over $\mathcal H$. The growth function is $$ \Pi_{\mathcal H}(m)=\sup_{x_1,\ldots,x_m\in\mathcal X} \left|\left\{(h(x_1),\ldots,h(x_m)):h\in\mathcal H\right\}\right|. $$ For an event $A\subseteq\mathcal X$, its indicator is $h_A(x)=\mathbf 1\{x\in A\}$. Thus, for a class of indicators, $\Pi_{\mathcal H}(m)$ counts the distinct membership patterns the events can produce on $m$ points.

Let $X_1,\ldots,X_n$ be independent and identically distributed according to $P$. For a binary function $h$, write $$ P h=E[h(X)],\qquad P_n h=\frac{1}{n}\sum_{i=1}^n h(X_i). $$ When $h=h_A$, these are $P(A)$, the population probability of the event, and $P_n(A)$, its observed sample proportion. The quantity of interest is the supremum of $|P_n h-P h|$ over the class.

Concentration for a Fixed Binary Function

For one fixed $h$, the variables $h(X_i)$ are independent and lie in $[0,1]$. Hoeffding’s inequality states that if independent $Z_i$ lie in intervals of lengths at most $c_i$, then $$ P\left(\left|\frac{1}{n}\sum_{i=1}^n(Z_i-E[Z_i])\right|>t\right) \leq 2\exp\left(-\frac{2n^2t^2}{\sum_{i=1}^n c_i^2}\right). $$ In particular, with $Z_i=h(X_i)$, all $c_i=1$, so $$ P\bigl(|P_n h-P h|>t\bigr)\leq 2\exp(-2nt^2). $$ This is a fixed-function result. Taking a union bound directly over the observed patterns is not enough: two functions that agree on the observed sample can still have different population probabilities. The proof of the uniform bound therefore introduces an independent sample.

Result: If $Z_i$ are independent and $a_i\leq Z_i\leq b_i$, then for every $s>0$, $$ E\left[\exp\left\{s\sum_{i=1}^n(Z_i-E[Z_i])\right\}\right] \leq \exp\left(\frac{s^2}{8}\sum_{i=1}^n(b_i-a_i)^2\right). $$ Consequently, applying Markov’s inequality to the exponential and optimizing over $s$, then applying the same argument to the negative sum, gives Hoeffding’s inequality above.

For completeness, the exponential-moment inequality follows from Hoeffding’s lemma. If $Z\in[a,b]$, convexity of the exponential bounds its moment-generating function by that of a two-point variable at the endpoints with the same mean. After centering and putting $u=s(b-a)$, the resulting log moment-generating function has the form $$ g(u)=\log\bigl((1-q)e^{-qu}+q e^{(1-q)u}\bigr) $$ for some $q\in[0,1]$. It satisfies $g(0)=g'(0)=0$. Its second derivative is the variance of a two-point variable with values separated by one, under an exponentially tilted probability, and is therefore at most $1/4$. Integrating this bound twice gives $g(u)\leq u^2/8$, proving the lemma. Independence multiplies the moment-generating functions, yielding the stated sum bound.

Worked Example: A Fixed Event

Suppose $A$ is a fixed event, $n=100$, and the desired error tolerance is $t=0.2$. Hoeffding’s inequality gives $$ P\bigl(|P_n(A)-P(A)|>0.2\bigr) \leq 2\exp\bigl(-2(100)(0.2)^2\bigr) =2e^{-8}\approx 0.000671. $$

The bound applies to this event regardless of the distribution $P$. It does not, by itself, guarantee that every event in a class has error at most $0.2$; that simultaneous question requires accounting for the class’s possible patterns.

Uniform Convergence from the Growth Function

The following theorem makes the class-size adjustment explicit. Assume $\mathcal H$ is countable, so the supremum event is measurable and a member witnessing a strict exceedance can be selected measurably. The usual measurable-separability conditions give the same conclusion for suitable uncountable classes.

Theorem: Let $X_1,\ldots,X_n$ be iid from any distribution $P$, and let $\mathcal H$ be a countable class of measurable functions from $\mathcal X$ to $\{0,1\}$. For every $\varepsilon>0$ satisfying $n\varepsilon^2\geq 2$, $$ P\left(\sup_{h\in\mathcal H}|P_n h-P h|>\varepsilon\right) \leq 4\Pi_{\mathcal H}(2n)\exp\left(-\frac{n\varepsilon^2}{8}\right). $$

To prove the theorem, let $X'_1,\ldots,X'_n$ be an independent sample from $P$, and write $P'_n h=n^{-1}\sum_{i=1}^n h(X'_i)$. This is the ghost sample: it has the same distribution as the original sample but is independent of it.

Replace population means by a ghost sample.
Let $E$ denote the event $\sup_{h\in\mathcal H}|P_n h-P h|>\varepsilon$. On $E$, select an $h$ with $|P_n h-P h|>\varepsilon$. Conditional on the original sample, $\operatorname{Var}(P'_n h)\leq 1/(4n)$. Chebyshev’s inequality gives $P(|P'_n h-P h|\geq\varepsilon/2)\leq 1/(n\varepsilon^2)\leq 1/2$. With conditional probability at least $1/2$, therefore, $|P'_n h-P h|<\varepsilon/2$, which implies $|P_n h-P'_n h|>\varepsilon/2$. Hence $$ P(E)\leq 2P\left(\sup_{h\in\mathcal H}|P_n h-P'_n h|>\varepsilon/2\right). $$

Randomly swap each paired observation.
For each $i$, independently swap $X_i$ and $X'_i$ with probability $1/2$. The joint distribution of the two samples is unchanged. Conditional on the $2n$ pooled observations, the difference for any fixed $h$ has the form $$ \frac{1}{n}\sum_{i=1}^n \sigma_i\bigl(h(z_i)-h(z_{n+i})\bigr), $$ where the $\sigma_i$ are independent random signs, each equally likely to be $1$ or $-1$, and the $z_i$ are the pooled points arranged in pairs.

Count patterns and apply concentration.
For fixed pooled points, at most $\Pi_{\mathcal H}(2n)$ distinct vectors of $2n$ labels occur. Each vector fixes coefficients $a_i=h(z_i)-h(z_{n+i})\in\{-1,0,1\}$. The independent summands $\sigma_i a_i$ have interval lengths at most $2$. Hoeffding’s inequality gives, for each vector, $$ P\left(\left|\frac{1}{n}\sum_{i=1}^n\sigma_i a_i\right|>\varepsilon/2\right) \leq 2\exp\left(-\frac{2n^2(\varepsilon/2)^2}{4n}\right) =2\exp\left(-\frac{n\varepsilon^2}{8}\right). $$ A union bound over the distinct vectors bounds the conditional probability by $2\Pi_{\mathcal H}(2n)e^{-n\varepsilon^2/8}$. Averaging over the pooled observations and using Step 1 proves the theorem. $\square$

The factor $\Pi_{\mathcal H}(2n)$ enters because the comparison uses two samples, containing $2n$ points in total. The proof does not union-bound over every member of an infinite class; it counts only the distinct label vectors on those pooled points. The bound is uniform over $P$, since neither the concentration inequality nor the pattern count requires a special distribution.

Worked Example: Eight Hypotheses

Suppose $\mathcal H$ contains eight binary functions. Then $\Pi_{\mathcal H}(m)\leq 8$ for every $m$. For $n=500$ and $\varepsilon=0.2$, the condition $n\varepsilon^2=20\geq 2$ holds, and the theorem gives $$ P\left(\sup_{h\in\mathcal H}|P_n h-P h|>0.2\right) \leq 4(8)\exp\left(-\frac{500(0.2)^2}{8}\right) =32e^{-2.5}\approx 2.627. $$

A probability is at most one, so this numerical upper bound can be replaced by $\min(1,2.627)=1$. It is valid but uninformative: the sample size and tolerance do not make the exponential factor small enough to offset the class-size factor.

Worked Example: A Useful Finite-Class Bound

Suppose there are 100 binary hypotheses, so $\Pi_{\mathcal H}(m)\leq100$. Take $n=1000$ and $\varepsilon=0.3$. The theorem’s condition holds because $n\varepsilon^2=90$. Substitution gives $$ P\left(\sup_{h\in\mathcal H}|P_n h-P h|>0.3\right) \leq 4(100)\exp\left(-\frac{1000(0.3)^2}{8}\right) =400e^{-11.25}\approx 0.005203. $$

Thus, under any distribution $P$, the probability that at least one of these hypotheses has empirical probability error greater than $0.3$ is at most about $0.005203$. This is a simultaneous statement, not 100 separate claims that each hold only for a preselected hypothesis.

Worked Example: A Class of Singletons

Let $\mathcal X=\{1,\ldots,10\}$, let $P$ be uniform on $\mathcal X$, and let $\mathcal H$ contain the indicator of every singleton subset of $\mathcal X$, together with the zero function for the empty set. On any $m$ points, the only possible patterns mark no observed point or mark the observations equal to one of the distinct singleton locations. Therefore $\Pi_{\mathcal H}(m)\leq m+1$.

For $n=10{,}000$ and $\varepsilon=0.1$, $n\varepsilon^2=100\geq2$, and $\Pi_{\mathcal H}(2n)\leq20{,}001$. Consequently, $$ P\left(\sup_{h\in\mathcal H}|P_n h-P h|>0.1\right) \leq 4(20{,}001)e^{-12.5} =80{,}004e^{-12.5} \approx 0.2982. $$

The calculation uses the stated bound $m+1$ at $m=20{,}000$, then multiplies by the theorem’s factor of four. The result is distribution-free, although this particular example specifies a uniform distribution. The numerical guarantee is valid but not especially sharp; growth-based bounds can be conservative.

Why the Bound Matters—and a Common Pitfall

The theorem turns a combinatorial count into a statistical guarantee. If the class produces relatively few patterns on $2n$ points, the exponential concentration term can dominate that count, making large simultaneous errors unlikely. This matters when a classifier is chosen using the sample: a uniform statement applies to the data-selected member as well as to each member considered in advance.

A common mistake is to say: “There are at most $\Pi_{\mathcal H}(n)$ patterns on the observed sample, so I can apply fixed-function Hoeffding and union-bound over those patterns.” The gap is that an observed pattern does not determine $P h$. Functions agreeing at all observed points may differ away from those points, so their empirical averages can match while their population probabilities do not. The ghost sample supplies additional points on which these distinctions can appear; the proof counts patterns on all $2n$ points and pays for the comparison through its constants and exponential rate.

The bound is an upper bound, not a prediction of the actual error. If its right-hand side exceeds one, it provides no nontrivial probability guarantee. If it is small, it controls the largest deviation over the whole class, without requiring a special assumption on $P$. The growth-function calculation is therefore useful both as a guarantee and as a diagnostic: it shows whether the class’s combinatorial richness is small enough for this route to yield a meaningful result.

Key takeaway: For a binary class, the probability of any empirical-to-population error exceeding $\varepsilon$ is bounded by $4\Pi_{\mathcal H}(2n)e^{-n\varepsilon^2/8}$ when $n\varepsilon^2\geq2$. The growth function accounts for the class’s distinct patterns; the ghost sample makes a uniform comparison possible.

Check Your Understanding

Answer each question using the definitions and argument above.

What does $\Pi_{\mathcal H}(m)$ count, and why can it be much smaller than the number of functions in an infinite class?
For a fixed binary function, what does Hoeffding’s inequality say about $P(|P_n h-P h|>t)$?
Why does the uniform-deviation proof introduce an independent ghost sample?
In the theorem, why is the growth function evaluated at $2n$ rather than $n$?
A class has at most 20 distinct functions. Write the theorem’s bound for the probability of a uniform error greater than $\varepsilon$, including its condition on $n$ and $\varepsilon$.