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. 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, the empirical frequency is

The theoretical probability

, then with high probability, the empirical frequency will be close to its expected value, which is the theoretical probability.

Here "simple" means that the Vapnik–Chervonenkis dimension 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 using the concept of growth function.

Uniform Convergence Theorem

The statement of the Uniform Convergence Theorem is as follows:

is a probability distribution a positive integer, we have:

and for any natural number

to be the Concept/Hypothesis. Crucially, the Sauer–Shelah lemma is the VC dimension.

Proof of the Uniform Convergence Theorem

and 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:.

2. Permutation:.

3. Reduction to a finite class: 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 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.

Symmetrization

Lemma: and

.

Proof: By the triangle inequality,.

Therefore,

are independent.

, we shall show that

. And hence we perform the first step of our high level idea.

is a binomial random variable. By Chebyshev's inequality we get

.

Permutations

.

Lemma:. Then,

.

.)

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,

1. .

otherwise.

. By union bound we get

, with equal probability.

Thus,

and both the possibilities are equally likely. By Hoeffding's inequality.

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

References