Uniform Laws from Vanishing Complexity

Why Pointwise Accuracy Is Not Enough

A law of large numbers for one fixed function says that its empirical average approaches its population average. Learning problems, however, often require accuracy for every function in a class at once. That is a stronger demand: even if each fixed function behaves well, a class that becomes sufficiently rich with sample size can contain functions that fit the observed sample unusually closely.

Expected Rademacher complexity quantifies how well a class can align with random signs on a sample. When this measure tends to zero, symmetrization turns it into a bound on uniform empirical deviation. Uniform boundedness then supplies concentration around that expected deviation, giving a uniform law of large numbers.

Setup and Definitions

Let $X_1,X_2,\ldots$ be independent and identically distributed observations with distribution $P$ on a measurable space $(\mathcal X,\mathcal A)$. For a measurable function $f:\mathcal X\to\mathbb R$, write $Pf=E[f(X_1)]$ and $P_n f=n^{-1}\sum_{i=1}^n f(X_i)$. At sample size $n$, let $\mathcal F_n$ be a nonempty, countable class of such functions. Countability ensures that the suprema below are measurable; more general classes require appropriate measurability conditions.

Definition: The uniform empirical deviation of $\mathcal F_n$ is $$ Z_n=\sup_{f\in\mathcal F_n}|P_n f-Pf|. $$ Let $\varepsilon_1,\ldots,\varepsilon_n$ be independent Rademacher signs, independent of the observations, so $P(\varepsilon_i=1)=P(\varepsilon_i=-1)=1/2$. The expected absolute Rademacher complexity is $$ \mathfrak R_n(\mathcal F_n) =E_{X,\varepsilon}\left[\sup_{f\in\mathcal F_n} \left|\frac{1}{n}\sum_{i=1}^n\varepsilon_i f(X_i)\right|\right]. $$

The absolute value is part of this convention: the complexity measures the largest magnitude of a signed sum. Assume there is a fixed finite constant $B$ such that $|f(x)|\le B$ for every $n$, every $f\in\mathcal F_n$, and every $x\in\mathcal X$. This condition makes the quantities integrable and will also control how much $Z_n$ can change when one observation is replaced.

The Uniform Law from Vanishing Complexity

Theorem: Suppose the observations are i.i.d., each $\mathcal F_n$ is countable and consists of measurable functions, and $|f(x)|\le B<\infty$ uniformly over $n,f,x$. If $$ \mathfrak R_n(\mathcal F_n)\longrightarrow 0, $$ then $Z_n\to 0$ in probability. In fact, for the sequence $X_1,X_2,\ldots$, $Z_n\to 0$ almost surely.

The first ingredient is the expected symmetrization inequality. In the form needed here, it states that $$ E[Z_n]\le 2\mathfrak R_n(\mathcal F_n). $$ For completeness, let $X_1',\ldots,X_n'$ be an independent sample from $P$. Conditional Jensen's inequality, applied to the supremum of absolute values, gives $$ E_X\sup_f\left|\frac{1}{n}\sum_i f(X_i)-Pf\right| \le E_{X,X'}\sup_f\left|\frac{1}{n}\sum_i\bigl(f(X_i)-f(X_i')\bigr)\right|. $$ For each $i$, swapping $X_i$ and $X_i'$ does not change their joint distribution. Thus independent signs can be inserted into the differences without changing the expectation. The triangle inequality then bounds the last display by $$ E\sup_f\left|\frac{1}{n}\sum_i\varepsilon_i f(X_i)\right| + E\sup_f\left|\frac{1}{n}\sum_i\varepsilon_i f(X_i')\right| =2\mathfrak R_n(\mathcal F_n). $$ This proves the stated inequality.

It follows immediately that $E[Z_n]\to0$. Markov's inequality therefore gives, for every $\delta>0$, $$ P(Z_n>\delta)\le \frac{E[Z_n]}{\delta} \le \frac{2\mathfrak R_n(\mathcal F_n)}{\delta}\longrightarrow 0. $$ This proves the uniform law in probability. To obtain the stronger almost-sure conclusion, we use bounded differences.

McDiarmid's inequality: If a measurable function $G(X_1,\ldots,X_n)$ changes by at most $c_i$ whenever only its $i$th coordinate is replaced, then for $t>0$, $$ P\bigl(G-E[G]>t\bigr)\le \exp\left(-\frac{2t^2}{\sum_{i=1}^n c_i^2}\right). $$

Replacing one observation changes $P_n f$ by at most $2B/n$, for every $f$. The inequality $||a|-|b||\le |a-b|$, followed by taking suprema, shows that $Z_n$ also changes by at most $2B/n$. Consequently, McDiarmid's inequality yields $$ P(Z_n-E[Z_n]>t)\le \exp\left(-\frac{nt^2}{2B^2}\right) $$ when $B>0$; if $B=0$, then $Z_n=0$ identically.

Fix $\delta>0$. Since $E[Z_n]\to0$, eventually $E[Z_n]\le\delta/2$. For those $n$, $$ P(Z_n>\delta)\le P\left(Z_n-E[Z_n]>\frac{\delta}{2}\right) \le \exp\left(-\frac{n\delta^2}{8B^2}\right). $$ The right-hand side is summable over $n$. By the Borel–Cantelli lemma, $Z_n>\delta$ occurs only finitely often, almost surely. Applying this conclusion to $\delta=1/k$ for each positive integer $k$ proves $Z_n\to0$ almost surely. $\square$

Worked Examples

Worked Example: A Single Bernoulli Function

Let $X_i\sim\operatorname{Bernoulli}(1/2)$, and let every $\mathcal F_n$ consist of the single function $f(x)=x$. The empirical deviation is simply the absolute difference between the sample proportion of ones and $1/2$. We can bound the complexity directly: $$ \mathfrak R_n(\mathcal F_n) =\frac{1}{n}E\left|\sum_{i=1}^n\varepsilon_i X_i\right| \le \frac{1}{n}\sqrt{E\left(\sum_{i=1}^n\varepsilon_i X_i\right)^2}. $$ The inequality is Cauchy–Schwarz. In the expectation of the square, cross terms vanish because the independent signs have mean zero, and $\varepsilon_i^2=1$. Hence $$ E\left(\sum_{i=1}^n\varepsilon_i X_i\right)^2 =\sum_{i=1}^n E[X_i^2] =\frac{n}{2}, \qquad \mathfrak R_n(\mathcal F_n)\le\frac{1}{\sqrt{2n}}. $$ Thus the complexity vanishes. The theorem gives uniform convergence here (uniformity is trivial for a singleton class), and the expected deviation bound is $E[Z_n]\le\sqrt{2/n}$.

Worked Example: A Growing Coordinate Class

At sample size $n$, let $X_i$ take values in $\{0,1\}^{m_n}$, and define $f_j(x)=x_j$ for $j=1,\ldots,m_n$. Take $m_n=\lfloor e^{\sqrt n}\rfloor$. Each function is bounded by one. Conditional on the data, put $T_j=\sum_i\varepsilon_i f_j(X_i)$. The Rademacher signs are sub-Gaussian, so $E_\varepsilon e^{\lambda T_j}\le e^{\lambda^2n/2}$, and the same bound holds for $-T_j$. Therefore $$ E_\varepsilon\max_{1\le j\le m_n}|T_j| \le \frac{\log(2m_n)}{\lambda}+\frac{\lambda n}{2}. $$ Choosing $\lambda=\sqrt{2\log(2m_n)/n}$ and dividing by $n$ gives $$ \mathfrak R_n(\mathcal F_n) \le\sqrt{\frac{2\log(2m_n)}{n}} \le\sqrt{\frac{2(\log 2+\sqrt n)}{n}} \longrightarrow 0. $$ The number of candidate functions grows rapidly, but its logarithm grows more slowly than the sample size. The theorem therefore guarantees uniform convergence over all these coordinates.

Worked Example: A Class Whose Complexity Does Not Vanish

Let the domain be $\{1,\ldots,m_n\}$, where $m_n=n^3$, with $X_i$ uniform on that domain. Let $\mathcal F_n$ contain the indicators of every subset of the domain. On the event $A_n$ that all $n$ sampled values are distinct, the class can select precisely the observations whose signs are positive. It can also select those whose signs are negative. One of these two groups has at least $n/2$ members, so $$ \sup_{f\in\mathcal F_n}\left|\sum_{i=1}^n\varepsilon_i f(X_i)\right| \ge \frac{n}{2} \quad\text{on }A_n. $$ A union bound over pairs of observations gives $$ P(A_n)\ge 1-\binom{n}{2}\frac{1}{m_n} =1-\frac{n(n-1)}{2n^3}. $$ Consequently, $$ \mathfrak R_n(\mathcal F_n)\ge\frac{P(A_n)}{2}\longrightarrow\frac{1}{2}. $$ This calculation does not show that the class fails every possible uniform law; it shows that the vanishing-complexity condition is not met. The class can adapt to the signs on the sample, which is precisely the behavior complexity is designed to detect.

Interpretation and a Common Pitfall

The theorem separates two tasks. Symmetrization converts the expected worst-case empirical error into a complexity measure, while boundedness controls fluctuations of that worst-case error around its expectation. Thus the assumption $\mathfrak R_n(\mathcal F_n)\to0$ is what drives the expected deviation to zero, and the uniform bound supplies concentration strong enough for almost-sure convergence.

Common mistake: It is tempting to argue that if every fixed $f$ satisfies a law of large numbers, then the supremum over $f\in\mathcal F_n$ must also converge to zero. The reasoning changes the order of “for each function” and “uniformly over the class.” A different function can be selected at each sample size, potentially exploiting the observed data. The correction is to control the supremum itself; vanishing expected Rademacher complexity provides such control through the symmetrization bound.

Uniform convergence matters when a statistical procedure compares many candidate functions using empirical averages. If those empirical averages are uniformly close to their population counterparts, empirical comparisons are informative across the whole class, rather than only for a function chosen in advance. The result does not by itself specify how to choose a function or establish any risk guarantee for a particular procedure; it supplies the uniform convergence fact those later arguments can use.

Check Your Understanding

Answer each question using the definitions and bounds developed above.

Why does the theorem require complexity to vanish for the sequence of classes, rather than only for each fixed function?
Which step in the proof gives convergence in probability, and which additional ingredient gives almost-sure convergence?
If $|f(x)|\le B$, how much can $Z_n$ change when one observation is replaced?
For the coordinate class, why does a number of functions growing like $e^{\sqrt n}$ still allow the stated complexity bound to vanish?
In the subset-indicator example, what feature of the class prevents the complexity from tending to zero?