Empirical measures provide a constructive route from testing geometry to estimators. A class of sets defines a probability distance; VC complexity controls its empirical fluctuation; minimizing that distance over a model yields finite-sample and asymptotic risk bounds.
Set-indexed probability distances
Definition. For a class \(\mathcal C\) of measurable sets, define \[ d_{\mathcal C}(P,Q) = \sup_{A\in\mathcal C}|P(A)-Q(A)|. \] The empirical measure is \[ P_n(A)=\frac1n\sum_{i=1}^n1\{X_i\in A\}. \]
If \(\mathcal C\) is the class of all measurable sets, \(d_{\mathcal C}\) is total variation, but empirical and continuous laws are then maximally far apart. A smaller class trades resolution for estimability.
VC uniform deviation
Theorem. Let \(\mathcal C\) have VC dimension \(V<\infty\) and satisfy a standard measurability condition. Universal constants \(c,C>0\) exist such that \[ P\left\{ \sup_{A\in\mathcal C}|P_n(A)-P(A)| > C\sqrt{\frac{V+t}{n}} \right\} \leq e^{-ct}. \] Consequently, \[ E\,d_{\mathcal C}(P_n,P)\lesssim\sqrt{V/n}. \]
Proof outline. Symmetrization bounds the expected supremum by a Rademacher process. Conditional on the pooled sample, only the traces \(\{C\cap\{X_1,\ldots,X_n\}:C\in\mathcal C\}\) matter. Sauer–Shelah bounds their number by \(\sum_{j=0}^V\binom nj\), and the finite-class maximal inequality yields order \(\sqrt{V/n}\). Bounded-difference or Talagrand concentration gives the tail bound. \(\square\)
Minimum-distance estimators
Definition. For a model \(\{P_\theta:\theta\in\Theta\}\), a minimum-distance estimator satisfies \[ d_{\mathcal C}(P_n,P_{\hat\theta}) \leq \inf_{\theta\in\Theta} d_{\mathcal C}(P_n,P_\theta)+\eta_n. \]
Theorem (oracle inequality). Let \[ \theta^\circ\in\arg\min_\theta d_{\mathcal C}(P,P_\theta). \] Then \[ d_{\mathcal C}(P,P_{\hat\theta}) \leq 2d_{\mathcal C}(P_n,P) +d_{\mathcal C}(P,P_{\theta^\circ}) +\eta_n. \]
Proof. By the triangle inequality and approximate optimality, \[ \begin{aligned} d_{\mathcal C}(P,P_{\hat\theta}) &\leq d_{\mathcal C}(P,P_n) +d_{\mathcal C}(P_n,P_{\hat\theta})\\ &\leq d_{\mathcal C}(P,P_n) +d_{\mathcal C}(P_n,P_{\theta^\circ})+\eta_n\\ &\leq2d_{\mathcal C}(P_n,P) +d_{\mathcal C}(P,P_{\theta^\circ})+\eta_n. \end{aligned} \] \(\square\)
Under correct specification the approximation term vanishes. If the model is identifiable in \(d_{\mathcal C}\), the estimator is consistent; a quantitative inverse inequality converts probability-distance error into parameter loss.
Yatracos classes
Definition. For a dominated density model \(\{p_\theta\}\), the Yatracos class is \[ \mathcal Y = \{\{x:p_\theta(x)>p_\eta(x)\}: \theta,\eta\in\Theta\}. \]
Proposition. For model laws \(P_\theta,P_\eta\), \[ \|P_\theta-P_\eta\|_{\mathrm{TV}} = d_{\mathcal Y}(P_\theta,P_\eta). \]
Proof. The total-variation maximizing set is \(\{p_\theta>p_\eta\}\), which belongs to \(\mathcal Y\). No class supremum can exceed total variation. \(\square\)
If the Yatracos class has finite VC dimension, the minimum-distance estimator achieves total-variation error of order \(\sqrt{V/n}\) plus model approximation error.
Testing from set classes
Proposition. Given two model laws \(P,Q\), a set \(A\) with \(P(A)-Q(A)\) near \(d_{\mathcal C}(P,Q)\) yields a test based on \(P_n(A)\). Hoeffding concentration gives exponentially small errors when \[ |P(A)-Q(A)|\gg n^{-1/2}. \]
For composite hypotheses, finite VC complexity permits uniform tests over separated model sets. Such tests are central both to frequentist minimum-distance estimators and to Bayesian posterior contraction.
Relation to empirical-process theory
This chapter isolates the decision-theoretic use of VC control. The full proofs of symmetrization, Sauer–Shelah, entropy, Donsker convergence, and localized maximal inequalities are in Empirical processes.