Uniform convergence in probability

For other uses, see uniform convergence.

Uniform convergence in probability is a form of convergence in probability in statistical asymptotic theory and probability theory. It means that, under certain conditions, the empirical frequencies of all events in a certain event-family uniformly converge to their theoretical probabilities. Uniform convergence in probability has applications to statistics as well as machine learning as part of statistical learning theory. Specifically, the Glivenko-Cantelli theorem and the homonymous classes of functions are fundamentally related to uniform convergence.

The law of large numbers says that, for each single event ${\displaystyle A}$, its empirical frequency in a sequence of independent trials converges (with high probability) to its theoretical probability. In many application however, the need arises to judge simultaneously the probabilities of events of an entire class ${\displaystyle S}$ from one and the same sample. Moreover it, is required that the relative frequency of the events converge to the probability uniformly over the entire class of events ${\displaystyle S}$ ^[1]. The Uniform Convergence Theorem gives a sufficient condition for this convergence to hold. Roughly, if the event-family is sufficiently simple (its VC dimension is sufficiently small) then uniform convergence holds.

Definitions

For a class of predicates ${\displaystyle H}$ defined on a set ${\displaystyle X}$ and a set of samples ${\displaystyle x=(x_{1},x_{2},\dots ,x_{m})}$, where ${\displaystyle x_{i}\in X}$, the empirical frequency of ${\displaystyle h\in H}$ on ${\displaystyle x}$ is

${\displaystyle {\widehat {Q}}_{x}(h)={\frac {1}{m}}|\{i:1\leq i\leq m,h(x_{i})=1\}|.}$

The theoretical probability of ${\displaystyle h\in H}$ is defined as ${\displaystyle Q_{P}(h)=P\{y\in X:h(y)=1\}.}$

The Uniform Convergence Theorem states, roughly, that if ${\displaystyle H}$ is "simple" and we draw samples independently (with replacement) from ${\displaystyle X}$ according to any distribution ${\displaystyle P}$, then with high probability, the empirical frequency will be close to its expected value, which is the theoretical probability.^[2]

Here "simple" means that the Vapnik–Chervonenkis dimension of the class ${\displaystyle H}$ is small relative to the size of the sample. In other words, a sufficiently simple collection of functions behaves roughly the same on a small random sample as it does on the distribution as a whole.

The Uniform Convergence Theorem was first proved by Vapnik and Chervonenkis^[1] using the concept of growth function.

Uniform Convergence Theorem

The statement of the Uniform Convergence Theorem is as follows:^[3]

If ${\displaystyle H}$ is a set of ${\displaystyle \{0,1\}}$-valued functions defined on a set ${\displaystyle X}$ and ${\displaystyle P}$ is a probability distribution on ${\displaystyle X}$ then for ${\displaystyle \varepsilon >0}$ and ${\displaystyle m}$ a positive integer, we have:

${\displaystyle P^{m}\{|Q_{P}(h)-{\widehat {Q_{x}}}(h)|\geq \varepsilon {\text{ for some }}h\in H\}\leq 4\Pi _{H}(2m)e^{-\varepsilon ^{2}m/8}.}$

In the above, for any ${\displaystyle x\in X^{m},}$${\displaystyle Q_{P}(h)=P\{(y\in X:h(y)=1\},}$${\displaystyle {\widehat {Q}}_{x}(h)={\frac {1}{m}}|\{i:1\leq i\leq m,h(x_{i})=1\}|}$ and ${\displaystyle |x|=m.}$ ${\displaystyle P^{m}}$ indicates that the probability is taken over ${\displaystyle x}$ consisting of ${\displaystyle m}$ i.i.d. draws from the distribution ${\displaystyle P.}$

Finally, the growth function ${\displaystyle \Pi _{H}}$ is defined in the following way, for any ${\displaystyle \{0,1\}}$-valued functions ${\displaystyle H}$ over ${\displaystyle X}$ and for any natural number ${\displaystyle m}$: ${\displaystyle \Pi _{H}(m)=\max |\{h\cap D:D\subseteq X,|D|=m,h\in H\}|.}$

From the point of view of Learning Theory one can consider ${\displaystyle H}$ to be the Concept/Hypothesis class defined over the instance set ${\displaystyle X}$. Crucially, the Sauer–Shelah lemma implies that ${\displaystyle \Pi _{H}(m)\leq m^{d}}$, where ${\displaystyle d}$ is the VC dimension of ${\displaystyle H}$.

Proof of the Uniform Convergence Theorem

^[1] and ^[3] are the sources of the proof below. Before we get into the details of the proof of the Uniform Convergence Theorem we will present a high level overview of the proof.

1. Symmetrization: We transform the problem of analyzing ${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{x}(h)|\geq \varepsilon }$ into the problem of analyzing ${\displaystyle |{\widehat {Q}}_{r}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2}$, where ${\displaystyle r}$ and ${\displaystyle s}$ are i.i.d samples of size ${\displaystyle m}$ drawn according to the distribution ${\displaystyle P}$. One can view ${\displaystyle r}$ as the original randomly drawn sample of length ${\displaystyle m}$, while ${\displaystyle s}$ may be thought as the testing sample which is used to estimate ${\displaystyle Q_{P}(h)}$.
2. Permutation: Since ${\displaystyle r}$ and ${\displaystyle s}$ are picked identically and independently, so swapping elements between them will not change the probability distribution on ${\displaystyle r}$ and ${\displaystyle s}$. So, we will try to bound the probability of ${\displaystyle |{\widehat {Q}}_{r}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2}$ for some ${\displaystyle h\in H}$ by considering the effect of a specific collection of permutations of the joint sample ${\displaystyle x=r||s}$. Specifically, we consider permutations ${\displaystyle \sigma (x)}$ which swap ${\displaystyle x_{i}}$ and ${\displaystyle x_{m+i}}$ in some subset of ${\displaystyle {1,2,...,m}}$. The symbol ${\displaystyle r||s}$ means the concatenation of ${\displaystyle r}$ and ${\displaystyle s}$.^{[citation needed]}
3. Reduction to a finite class: We can now restrict the function class ${\displaystyle H}$ to a fixed joint sample and hence, if ${\displaystyle H}$ has finite VC Dimension, it reduces to the problem to one involving a finite function class.

We present the technical details of the proof. It should be stressed that this proof glosses over details like the measurability of the events ${\displaystyle V}$ and ${\displaystyle R}$; measurability is granted in the case of ${\displaystyle H}$ being finite or countable, but this is not normally the case in standard applications of the theorem (e.g. for statistical learning theory or to prove the Glivenko-Cantelli theorem). To get measurability, one needs to use a notion of separability of the underlying space, possibly related to ${\displaystyle H}$^[4].

Symmetrization

Lemma: Let ${\displaystyle V=\{x\in X^{m}:|Q_{P}(h)-{\widehat {Q}}_{x}(h)|\geq \varepsilon {\text{ for some }}h\in H\}}$ and

${\displaystyle R=\{(r,s)\in X^{m}\times X^{m}:|{\widehat {Q_{r}}}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2{\text{ for some }}h\in H\}.}$

Then for ${\displaystyle m\geq {\frac {2}{\varepsilon ^{2}}}}$, ${\displaystyle P^{m}(V)\leq 2P^{2m}(R)}$.

Proof: By the triangle inequality,
if ${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon }$ and ${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2}$ then ${\displaystyle |{\widehat {Q}}_{r}(h)-{\widehat {Q}}_{s}(h)|\geq \varepsilon /2}$.

Therefore,

${\displaystyle {\begin{aligned}&P^{2m}(R)\\[5pt]\geq {}&P^{2m}\{\exists h\in H,|Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon {\text{ and }}|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2\}\\[5pt]={}&\int _{V}P^{m}\{s:\exists h\in H,|Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon {\text{ and }}|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq \varepsilon /2\}\,dP^{m}(r)\\[5pt]={}&A\end{aligned}}}$

since ${\displaystyle r}$ and ${\displaystyle s}$ are independent.

Now for ${\displaystyle r\in V}$ fix an ${\displaystyle h\in H}$ such that ${\displaystyle |Q_{P}(h)-{\widehat {Q}}_{r}(h)|\geq \varepsilon }$. For this ${\displaystyle h}$, we shall show that

${\displaystyle P^{m}\left\{|Q_{P}(h)-{\widehat {Q}}_{s}(h)|\leq {\frac {\varepsilon }{2}}\right\}\geq {\frac {1}{2}}.}$

Thus for any ${\displaystyle r\in V}$, ${\displaystyle A\geq {\frac {P^{m}(V)}{2}}}$ and hence ${\displaystyle P^{2m}(R)\geq {\frac {P^{m}(V)}{2}}}$. And hence we perform the first step of our high level idea.

Notice, ${\displaystyle m\cdot {\widehat {Q}}_{s}(h)}$ is a binomial random variable with expectation ${\displaystyle m\cdot Q_{P}(h)}$ and variance ${\displaystyle m\cdot Q_{P}(h)(1-Q_{P}(h))}$. By Chebyshev's inequality we get

${\displaystyle P^{m}\left\{|Q_{P}(h)-{\widehat {Q_{s}(h)}}|>{\frac {\varepsilon }{2}}\right\}\leq {\frac {m\cdot Q_{P}(h)(1-Q_{P}(h))}{(\varepsilon m/2)^{2}}}\leq {\frac {1}{\varepsilon ^{2}m}}\leq {\frac {1}{2}}}$

for the mentioned bound on ${\displaystyle m}$. Here we use the fact that ${\displaystyle x(1-x)\leq 1/4}$ for ${\displaystyle x}$.

Permutations

Let ${\displaystyle \Gamma _{m}}$ be the set of all permutations of ${\displaystyle \{1,2,3,\dots ,2m\}}$ that swaps ${\displaystyle i}$ and ${\displaystyle m+i}$ ${\displaystyle \forall i}$ in some subset of ${\displaystyle \{1,2,3,\ldots ,2m\}}$.

Lemma: Let ${\displaystyle R}$ be any subset of ${\displaystyle X^{2m}}$ and ${\displaystyle P}$ any probability distribution on ${\displaystyle X}$. Then,

${\displaystyle P^{2m}(R)=E[\Pr[\sigma (x)\in R]]\leq \max _{x\in X^{2m}}(\Pr[\sigma (x)\in R]),}$

where the expectation is over ${\displaystyle x}$ chosen according to ${\displaystyle P^{2m}}$, and the probability is over ${\displaystyle \sigma }$ chosen uniformly from ${\displaystyle \Gamma _{m}}$.

Proof: For any ${\displaystyle \sigma \in \Gamma _{m},}$

${\displaystyle P^{2m}(R)=P^{2m}\{x:\sigma (x)\in R\}}$

(since coordinate permutations preserve the product distribution ${\displaystyle P^{2m}}$.)

${\displaystyle {\begin{aligned}\therefore P^{2m}(R)={}&\int _{X^{2m}}1_{R}(x)\,dP^{2m}(x)\\[5pt]={}&{\frac {1}{|\Gamma _{m}|}}\sum _{\sigma \in \Gamma _{m}}\int _{X^{2m}}1_{R}(\sigma (x))\,dP^{2m}(x)\\[5pt]={}&\int _{X^{2m}}{\frac {1}{|\Gamma _{m}|}}\sum _{\sigma \in \Gamma _{m}}1_{R}(\sigma (x))\,dP^{2m}(x)\\[5pt]&{\text{(because }}|\Gamma _{m}|{\text{ is finite)}}\\[5pt]={}&\int _{X^{2m}}\Pr[\sigma (x)\in R]\,dP^{2m}(x)\quad {\text{(the expectation)}}\\[5pt]\leq {}&\max _{x\in X^{2m}}(\Pr[\sigma (x)\in R]).\end{aligned}}}$

The maximum is guaranteed to exist since there is only a finite set of values that probability under a random permutation can take.

Reduction to a finite class

Lemma: Basing on the previous lemma,

${\displaystyle \max _{x\in X^{2m}}(\Pr[\sigma (x)\in R])\leq 4\Pi _{H}(2m)e^{-\varepsilon ^{2}m/8}}$.

Proof: Let us define ${\displaystyle x=(x_{1},x_{2},\ldots ,x_{2m})}$ and ${\displaystyle t=|H|_{x}|}$ which is at most ${\displaystyle \Pi _{H}(2m)}$. This means there are functions ${\displaystyle h_{1},h_{2},\ldots ,h_{t}\in H}$ such that for any ${\displaystyle h\in H,\exists i}$ between ${\displaystyle 1}$ and ${\displaystyle t}$ with ${\displaystyle h_{i}(x_{k})=h(x_{k})}$ for ${\displaystyle 1\leq k\leq 2m.}$

We see that ${\displaystyle \sigma (x)\in R}$ iff for some ${\displaystyle h}$ in ${\displaystyle H}$ satisfies, ${\displaystyle |{\frac {1}{m}}|\{1\leq i\leq m:h(x_{\sigma _{i}})=1\}|-{\frac {1}{m}}|\{m+1\leq i\leq 2m:h(x_{\sigma _{i}})=1\}||\geq {\frac {\varepsilon }{2}}}$. Hence if we define ${\displaystyle w_{i}^{j}=1}$ if ${\displaystyle h_{j}(x_{i})=1}$ and ${\displaystyle w_{i}^{j}=0}$ otherwise.

For ${\displaystyle 1\leq i\leq m}$ and ${\displaystyle 1\leq j\leq t}$, we have that ${\displaystyle \sigma (x)\in R}$ iff for some ${\displaystyle j}$ in ${\displaystyle {1,\ldots ,t}}$ satisfies ${\displaystyle |{\frac {1}{m}}\left(\sum _{i}w_{\sigma (i)}^{j}-\sum _{i}w_{\sigma (m+i)}^{j}\right)|\geq {\frac {\varepsilon }{2}}}$. By union bound we get

${\displaystyle \Pr[\sigma (x)\in R]\leq t\cdot \max \left(\Pr[|{\frac {1}{m}}\left(\sum _{i}w_{\sigma _{i}}^{j}-\sum _{i}w_{\sigma _{m+i}}^{j}\right)|\geq {\frac {\varepsilon }{2}}]\right)}$

${\displaystyle \leq \Pi _{H}(2m)\cdot \max \left(\Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}w_{\sigma _{i}}^{j}-\sum _{i}w_{\sigma _{m+i}}^{j}\right)\right|\geq {\frac {\varepsilon }{2}}\right]\right).}$

Since, the distribution over the permutations ${\displaystyle \sigma }$ is uniform for each ${\displaystyle i}$, so ${\displaystyle w_{\sigma _{i}}^{j}-w_{\sigma _{m+i}}^{j}}$ equals ${\displaystyle \pm |w_{i}^{j}-w_{m+i}^{j}|}$, with equal probability.

Thus,

${\displaystyle \Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}\left(w_{\sigma _{i}}^{j}-w_{\sigma _{m+i}}^{j}\right)\right)\right|\geq {\frac {\varepsilon }{2}}\right]=\Pr \left[\left|{\frac {1}{m}}\left(\sum _{i}|w_{i}^{j}-w_{m+i}^{j}|\beta _{i}\right)\right|\geq {\frac {\varepsilon }{2}}\right],}$

where the probability on the right is over ${\displaystyle \beta _{i}}$ and both the possibilities are equally likely. By Hoeffding's inequality, this is at most ${\displaystyle 2e^{-m\varepsilon ^{2}/8}}$.

Finally, combining all the three parts of the proof we get the Uniform Convergence Theorem.

References

1. Vapnik, V. N.; Chervonenkis, A. Ya. (1971). "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Theory of Probability & Its Applications. 16 (2): 264. doi:10.1137/1116025. This is an English translation, by B. Seckler, of the Russian paper: "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Dokl. Akad. Nauk. 181 (4): 781. 1968. The translation was reproduced as: Vapnik, V. N.; Chervonenkis, A. Ya. (2015). "On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities". Measures of Complexity. p. 11. doi:10.1007/978-3-319-21852-6_3. ISBN 978-3-319-21851-9.
2. "Martingales", Probability with Martingales, Cambridge University Press, pp. 93–105, 1991-02-14, doi:10.1017/cbo9780511813658.014, ISBN 978-0-521-40455-6, retrieved 2023-12-08
3. Martin Anthony Peter, l. Bartlett. Neural Network Learning: Theoretical Foundations, pages 46–50. First Edition, 1999. Cambridge University Press ISBN 0-521-57353-X
4. Krapp, Lothar Sebastian; Wirth, Laura (26 September 2025), Measurability in the Fundamental Theorem of Statistical Learning, v3, arXiv:2410.10243, doi:10.48550/arXiv.2410.10243