Compact Parametric Classes and Equicontinuous Uniform Laws

From Pointwise to Uniform Convergence

A law of large numbers for each fixed parameter says that the empirical criterion becomes accurate if we decide in advance which parameter to inspect. A learning procedure, however, often selects a parameter after seeing the data. To control that data-dependent choice, we want the empirical criterion to be close to its population counterpart simultaneously over the whole parameter set.

Compactness and a common continuity bound provide one route from pointwise to uniform convergence. Compactness lets us represent the parameter space, to any chosen precision, using finitely many parameter values. A uniform Lipschitz bound then controls the error between those values. The argument is elementary, but its assumptions matter: the Lipschitz constant must not grow with sample size, and the parameter set must admit finite nets at every positive resolution.

Criteria and Uniform Lipschitz Control

Let \((\Theta,d)\) be a compact metric space. For each sample size \(n\), let \(M_n:\Theta\to\mathbb{R}\) be a random criterion, and let \(M:\Theta\to\mathbb{R}\) be its population target. In the common empirical-risk setting, \(M_n(\theta)=P_n m_\theta\) and \(M(\theta)=P m_\theta\), where \(P_n\) is the empirical distribution and \(P\) is the population distribution. The result below applies more generally; its key inputs concern convergence at fixed parameters and regularity as the parameter varies.

Definition: A function \(g:\Theta\to\mathbb{R}\) is \(L\)-Lipschitz if \(|g(\theta)-g(\eta)|\leq Ld(\theta,\eta)\) for every \(\theta,\eta\in\Theta\). The random criteria \(M_n\) have a common Lipschitz bound \(L\) if, with probability one, this inequality holds for \(g=M_n\) for every \(n\), using the same finite constant \(L\). A uniform law in probability is \(\sup_{\theta\in\Theta}|M_n(\theta)-M(\theta)|\xrightarrow{p}0\).

For the probability statements involving the supremum, assume it is measurable. For example, if \(\Theta\) is a compact subset of \(\mathbb{R}^d\), the random evaluations are measurable, and the sample paths are continuous, the supremum can be taken over a countable dense subset. This condition lets us interpret the displayed supremum as a random variable.

The Finite-Net Uniform Law

A \(\delta\)-net of \(\Theta\) is a finite set \(T_\delta\subseteq\Theta\) such that every \(\theta\in\Theta\) is within distance \(\delta\) of some point in \(T_\delta\). Every compact metric space has a finite \(\delta\)-net for each \(\delta>0\). The following theorem makes the approximation step explicit.

Theorem: Suppose \(\Theta\) is compact, \(M\) is \(L\)-Lipschitz, and \(M_n\) has the common Lipschitz bound \(L\). Suppose also that \(M_n(\theta)\xrightarrow{p}M(\theta)\) for every fixed \(\theta\in\Theta\), and that the supremum of the absolute error is measurable. Then \(\sup_{\theta\in\Theta}|M_n(\theta)-M(\theta)|\xrightarrow{p}0\). For every finite \(\delta\)-net \(T_\delta\), \[ \sup_{\theta\in\Theta}|M_n(\theta)-M(\theta)| \leq \max_{t\in T_\delta}|M_n(t)-M(t)|+2L\delta \] almost surely.

Proof. Fix \(\delta>0\). Given any \(\theta\in\Theta\), choose \(t\in T_\delta\) with \(d(\theta,t)\leq\delta\). The triangle inequality and the two Lipschitz bounds give \[ |M_n(\theta)-M(\theta)| \leq |M_n(\theta)-M_n(t)|+|M_n(t)-M(t)|+|M(t)-M(\theta)| \leq 2L\delta+\max_{s\in T_\delta}|M_n(s)-M(s)|. \] Taking the supremum over \(\theta\) proves the displayed bound.

Now fix \(\varepsilon>0\). If \(L>0\), choose a finite \(\delta\)-net with \(2L\delta<\varepsilon/2\); if \(L=0\), any positive \(\delta\) works because the Lipschitz contribution is zero. Since \(T_\delta\) is finite, pointwise convergence in probability and the union bound imply \[ P\!\left(\max_{t\in T_\delta}|M_n(t)-M(t)|>\varepsilon/2\right) \leq \sum_{t\in T_\delta}P\!\left(|M_n(t)-M(t)|>\varepsilon/2\right)\longrightarrow 0. \] The net inequality therefore gives \[ P\!\left(\sup_{\theta\in\Theta}|M_n(\theta)-M(\theta)|>\varepsilon\right)\longrightarrow 0, \] which is the asserted uniform convergence in probability. \(\square\)

If the empirical criteria have common Lipschitz bound \(L\), it is often unnecessary to assume separately that \(M\) is \(L\)-Lipschitz. In fact, if \(M_n(\theta)\xrightarrow{p}M(\theta)\) at every fixed \(\theta\), then \(M\) inherits that bound. For fixed \(\theta,\eta\), the random difference \(M_n(\theta)-M_n(\eta)\) converges in probability to the constant \(M(\theta)-M(\eta)\), while its absolute value is at most \(Ld(\theta,\eta)\) almost surely. A sequence bounded in absolute value by a constant cannot converge in probability to a constant outside that bound. Hence \[ |M(\theta)-M(\eta)|\leq Ld(\theta,\eta). \] Thus it suffices to check the common Lipschitz condition for the empirical criteria and pointwise convergence to the target.

Worked Example: Choosing a Net and Controlling the Error

Suppose \(\Theta=[0,1]\), the common Lipschitz bound for both \(M_n\) and \(M\) is \(L=2\), and pointwise convergence in probability holds. To make the probability of a uniform error above \(0.2\) small, use a net with radius \(\delta=0.025\).

The Lipschitz contribution to the error is at most \[ 2L\delta=2(2)(0.025)=0.1. \] Take \(T_\delta=\{0,0.025,0.050,\ldots,1\}\), which contains 41 points and is a \(0.025\)-net of \([0,1]\). If the error at every net point is at most \(0.1\), then the theorem’s bound gives \[ \sup_{\theta\in[0,1]}|M_n(\theta)-M(\theta)|\leq 0.1+0.1=0.2. \] Moreover, \[ P\!\left(\max_{t\in T_\delta}|M_n(t)-M(t)|>0.1\right) \leq \sum_{t\in T_\delta}P\!\left(|M_n(t)-M(t)|>0.1\right)\longrightarrow 0. \] There are only 41 terms, and each tends to zero by pointwise convergence. The example shows why a fixed, finite net is useful: no rate of convergence is needed, although the net’s size affects how quickly the union-bound probability may decrease.

Almost-Sure Version

The same finite-net idea also gives an almost-sure statement, but the pointwise assumption must be strengthened.

Theorem: Under the same compactness, measurability, and common Lipschitz assumptions, suppose \(M\) is \(L\)-Lipschitz and \(M_n(\theta)\xrightarrow{a.s.}M(\theta)\) for each fixed \(\theta\). Then \[ \sup_{\theta\in\Theta}|M_n(\theta)-M(\theta)|\xrightarrow{a.s.}0. \]

Proof. For each positive integer \(k\), choose a deterministic finite net \(T_k\) of radius \(\delta_k\), where \(\delta_k\to 0\). At every point of \(T_k\), pointwise almost-sure convergence holds. Since \(T_k\) is finite, there is a probability-one event on which convergence holds at all points of \(T_k\). Intersect these events over the countably many \(k\), and also with the probability-one event on which the common Lipschitz bounds hold. The resulting event still has probability one.

On that event, fix \(k\). The finite-net inequality implies \[ \limsup_{n\to\infty}\sup_{\theta\in\Theta}|M_n(\theta)-M(\theta)| \leq 2L\delta_k, \] because the maximum error over \(T_k\) tends to zero. This holds for every \(k\). Letting \(k\to\infty\) makes the right-hand side tend to zero. Since the supremum is nonnegative, it converges to zero on this probability-one event. \(\square\)

Worked Parametric Criteria

Worked Example: Uniform Convergence of Squared-Error Risk

Let \(X_1,X_2,\ldots\) be independent observations with a common distribution supported on \([0,1]\). For \(\theta\in[0,1]\), set \(m_\theta(x)=(\theta-x)^2\), \(M_n(\theta)=n^{-1}\sum_{i=1}^n m_\theta(X_i)\), and \(M(\theta)=E[m_\theta(X)]\).

For \(x,\theta,\eta\in[0,1]\), factor the difference: \[ |m_\theta(x)-m_\eta(x)| =|\theta-\eta|\,|\theta+\eta-2x| \leq 2|\theta-\eta|, \] since both \(\theta+\eta\) and \(2x\) lie in \([0,2]\). Averaging this inequality shows that every \(M_n\) is 2-Lipschitz. Taking expectations shows that \(M\) is also 2-Lipschitz. For each fixed \(\theta\), \(m_\theta(X_i)\) are independent, identically distributed, and bounded, so the strong law of large numbers gives \(M_n(\theta)\xrightarrow{a.s.}M(\theta)\). The almost-sure uniform theorem therefore applies.

The algebra also gives an exact discrepancy: \[ M_n(\theta)-M(\theta) =-2\theta(\bar X_n-E[X])+\left(\frac{1}{n}\sum_{i=1}^n X_i^2-E[X^2]\right), \] where \(\bar X_n=n^{-1}\sum_{i=1}^n X_i\). For example, suppose the observations are uniform on \([0,1]\), and the observed sample is \(0,0.2,0.8,1\). Then \(\bar X_4=0.5=E[X]\), while \(n^{-1}\sum X_i^2=(0+0.04+0.64+1)/4=0.42\) and \(E[X^2]=1/3\). Thus the discrepancy is the same for every \(\theta\), and \[ \sup_{\theta\in[0,1]}|M_4(\theta)-M(\theta)| =0.42-\frac{1}{3}=\frac{13}{150}\approx 0.0867. \]

Worked Example: Uniform Convergence of Bernoulli Log-Likelihood

Let \(X_i\) be independent Bernoulli random variables with success probability \(q=0.6\), and let \(\theta\in[-1,1]\) be the log-odds parameter. The model assigns success probability \(p_\theta=e^\theta/(1+e^\theta)\), so the log-likelihood contribution is \(m_\theta(x)=x\theta-\log(1+e^\theta)\). Define \(M_n(\theta)=n^{-1}\sum_{i=1}^n m_\theta(X_i)\) and \(M(\theta)=E[m_\theta(X)]\).

Differentiating with respect to \(\theta\) gives \[ \frac{\partial}{\partial\theta}m_\theta(x)=x-\frac{e^\theta}{1+e^\theta}. \] For \(x\in\{0,1\}\), the fraction lies in \((0,1)\), so the derivative’s absolute value is at most 1. The mean value theorem implies that \(m_\theta(x)\) is 1-Lipschitz in \(\theta\). Consequently, \(M_n\) and \(M\) are both 1-Lipschitz. At each fixed \(\theta\), the strong law applies because \(m_\theta(X_i)\) is bounded, and therefore \(M_n(\theta)\xrightarrow{a.s.}M(\theta)\). The theorem yields almost-sure uniform convergence on \([-1,1]\).

Here the error can also be calculated directly. Since \(E[X_i]=q\), \[ M_n(\theta)-M(\theta)=\theta(\bar X_n-q). \] As \(\max_{\theta\in[-1,1]}|\theta|=1\), it follows that \[ \sup_{\theta\in[-1,1]}|M_n(\theta)-M(\theta)|=|\bar X_n-q|\xrightarrow{a.s.}0. \] For a sample of size 10 containing 7 successes, the supremum error is \(|0.7-0.6|=0.1\). This finite-sample value illustrates the discrepancy; the almost-sure conclusion concerns its behavior as the sample size grows.

Why the Conditions Matter

A uniform law controls all parameters at once, so it can be used after a parameter has been selected from the observed data. For example, if an empirical-risk minimizer \(\hat{\theta}\) lies in \(\Theta\), then \[ |M_n(\hat{\theta})-M(\hat{\theta})| \leq \sup_{\theta\in\Theta}|M_n(\theta)-M(\theta)|. \] The right-hand side does not depend on how \(\hat{\theta}\) was chosen. Uniform control is therefore stronger and more useful for data-dependent choices than a statement made separately at each fixed parameter.

Common mistake: “For every fixed \(\theta\), the law of large numbers gives convergence, so the supremum over \(\theta\) must also converge.” This reasoning silently exchanges a statement for each fixed parameter with a statement holding simultaneously over all parameters. Pointwise convergence does not by itself justify that exchange. The finite-net proof supplies what is missing: a finite collection of pointwise statements controls the net, and the common Lipschitz bound controls every parameter between net points. Compactness alone is not a substitute for the uniform regularity condition, and a Lipschitz condition with a constant that grows without bound with \(n\) does not give the stated error bound.

Key takeaway: On a compact parameter space, pointwise convergence plus a common Lipschitz bound gives a uniform law: approximate the space by a finite net, control the finitely many net errors, and bound the gaps between net points by continuity.

Check Your Understanding

Use the finite-net argument and its assumptions to answer the following.

In the uniform error bound, why does a \(\delta\)-net contribute \(2L\delta\), rather than \(L\delta\)?
What property of a compact parameter set ensures that a finite net exists for each positive radius?
If \(M_n(\theta)\xrightarrow{p}M(\theta)\) for each fixed \(\theta\), which additional regularity condition allows the conclusion to be uniform?
For the Bernoulli log-likelihood example, explain why the absolute derivative with respect to \(\theta\) is at most 1.
Why does pointwise convergence alone not justify evaluating the convergence statement at a parameter selected using the data?