empirical process theory

Let $X_1,\dots ,X_n$ be random samples with values in some space $\mathcal{X}$. Let $\mathcal{F}$ be a set of functions $f:\mathcal{X}\to \mathbb{R}$. Let

$${\alpha }_n(f)=\frac{1}{n}\sum _{i\le n}f(X_i)-\mathbb{E}f(X).$$

The empirical process associated with $\mathcal{F}$ is

$${\Delta }_n(\mathcal{F})=\underset{f\in \mathcal{F}}{\sup }\left|{\alpha }_n(f)\right|.$$

(Though sometimes ${\alpha }_n(f)$ itself is referred to as the empirical process.)

Empirical process theory is concerned with statements about the behavior of ${\sup }_f{\alpha }_n(f)$ and ${\Delta }_n(\mathcal{F})$, whether in probability, almost surely, or in distribution. That is, we are searching for uniform laws of large numbers or uniform central limit theorems or uniform concentration inequalities (i.e., uniform convergence bounds). Uniform refers to uniformity over $\mathcal{F}$, which is what makes empirical process theory more challenging than simply analyzing sums of iid random variables.

To quote Bartl and Mendelson:

Empirical processes theory was developed as an attempt of obtaining uniform versions of the fundamental limit laws of probability theory — leading to the uniform law of large numbers; the uniform central limit theorem; and the uniform law of the iterated logarithm. However, over the last 25 years the focus of the theory has shifted [to non-asymptotics]— because it has become apparent that quantitative estimates and not the limit behaviour of empirical processes are of central importance in Data Science.

If ${\Delta }_n(\mathcal{F})\to 0$ in probability (or almost surely), we call $\mathcal{F}$ a Glivenko-Cantelli class. If $\sqrt{n}{\alpha }_n$ obeys a CLT (in the space of processes indexed by $\mathcal{F}$), we say it is a Donsker class.

A common way to control ${\Delta }_n(\mathcal{F})$ is via covering and packing numbers for the class $\mathcal{F}$. The relationship between covering and shattering numbers is then exploited by Vapnik-Chervonenkis theory to give bounds based on the VC-dimension.

Applications of empirical process theory are wide ranging. It pops up in M-estimation (eg proving properties of the MLE), hypothesis testing (eg analyzing goodness-of-fit tests), analyzing bootstrapping, learning theory (especially via Vapnik-Chervonenkis theory), nonparametric density estimation and nonparametric regression, and causal inference.