Uniform Empirical Deviations and Their Suprema

From One Function to a Whole Class

For a single measurable function, the empirical average is compared with its population average. In learning problems, however, the function of interest may be selected from many candidates. A useful way to describe the largest discrepancy across those candidates is to take a supremum over a function class. This definition is the starting point for studying uniform deviations: it records how far empirical averages can be from population averages anywhere in the class.

Let $X_1,\ldots,X_n$ be independent and identically distributed observations with common distribution $P$. For an integrable measurable function $f$, write $Pf$ for its population average and $P_nf$ for its empirical average. We use the following convention for their difference.

Pf=E[f(X_1)],\qquad P_nf=\frac{1}{n}\sum_{i=1}^n f(X_i).

For each fixed $f$, the difference $P_nf-Pf$ is a random variable because it depends on the sample. Its scaled version is commonly called the empirical process. The unscaled difference is the deviation itself; keeping both versions explicit avoids confusion about factors of $\sqrt n$.

Definition: For a class $\mathcal F$ of measurable, $P$-integrable functions, define the empirical process by $\mathbb G_n f=\sqrt n(P_nf-Pf)$. Define the uniform empirical deviation by $$ U_n(\mathcal F)=\sup_{f\in\mathcal F}|P_nf-Pf|. $$ The corresponding supremum of the scaled empirical process is $\sup_{f\in\mathcal F}|\mathbb G_n f|=\sqrt n\,U_n(\mathcal F)$. Unless stated otherwise, assume the supremum is measurable; this holds, in particular, for a finite or countable class.

The population average $Pf$ is fixed once $P$ and $f$ are specified. The empirical average $P_nf$, and hence the deviation and its supremum, vary from sample to sample. The absolute value makes $U_n(\mathcal F)$ sensitive to both overestimation and underestimation. If $\mathcal F$ is empty, the usual supremum convention is not useful here, so we take $\mathcal F$ to be nonempty.

Expectation and Probability Formulations

The expected uniform deviation is $E[U_n(\mathcal F)]$. It summarizes the typical size of the largest discrepancy, averaged over repeated samples. A probability formulation instead asks how likely it is that the largest discrepancy exceeds a chosen tolerance $\varepsilon>0$:

P\!\left(U_n(\mathcal F)>\varepsilon\right) = P\!\left(\text{there exists }f\in\mathcal F: |P_nf-Pf|>\varepsilon\right).

Equivalently, the event $U_n(\mathcal F)\leq\varepsilon$ says that every function in the class has deviation at most $\varepsilon$. The expected and probability formulations answer different questions: one reports an average magnitude, while the other reports a tail probability at a specified threshold. A bound for one may imply a bound for the other, but the conversion requires a valid inequality and its conditions.

Worked Example: A Single Bernoulli Function

Let $X_i$ be independent Bernoulli random variables with $P(X_i=1)=P(X_i=0)=1/2$, and take $\mathcal F=\{f\}$, where $f(x)=x$. Then $Pf=1/2$. For $n=2$, let $K=X_1+X_2$. The empirical average is $K/2$, so

U_2(\mathcal F)=\left|\frac K2-\frac12\right|.

The outcomes $K=0,1,2$ have probabilities $1/4,1/2,1/4$, respectively. The corresponding deviations are $1/2,0,1/2$. Therefore

E[U_2(\mathcal F)] =\frac14\cdot\frac12+\frac12\cdot0+\frac14\cdot\frac12 =\frac14,

and, for example, $P(U_2(\mathcal F)>1/4)=1/2$. Even a single function can have nonzero expected absolute deviation, although its signed deviation has expectation zero.

Worked Example: A Threshold Class and a Supremum That Is Not Attained

Suppose $X_1,X_2,X_3$ are observed values $0.2,0.6,0.9$, and the population distribution is uniform on $[0,1]$. Let $\mathcal F$ consist of $f_t(x)=\mathbf 1\{x\leq t\}$ for $0\leq t\leq1$. For this distribution, $Pf_t=t$. The empirical average is the observed proportion at or below $t$.

Between the sample values, that proportion is constant. For $0\leq t<0.2$, the deviation is $-t$, whose absolute value approaches $0.2$ as $t$ approaches $0.2$ from below. At $t=0.2$, the empirical proportion jumps to $1/3$, and the deviation is $1/3-0.2=2/15$. For $0.2\leq t<0.6$, the deviation is $1/3-t$, whose absolute value approaches $0.6-1/3=4/15$ as $t$ approaches $0.6$ from below.

The supremum $4/15$ is not attained: it is approached as $t\to0.6^{-}$. At $t=0.6$, the empirical proportion jumps to $2/3$, and the deviation is $2/3-0.6=1/15$. On $0.6\leq t<0.9$, the deviation is $2/3-t$, with absolute value approaching $0.9-2/3=7/30$ as $t$ approaches $0.9$ from below. At $t=0.9$, the deviation is $1-0.9=0.1$, and for $0.9\leq t\leq1$, its absolute value is $1-t\leq0.1$. Comparing these values gives

U_3(\mathcal F)=\max\left\{\frac15,\frac{4}{15},\frac{7}{30},\frac{1}{10}\right\} =\frac{4}{15}.

This example shows why “supremum” is more precise than “maximum”: the least upper bound of the deviations need not equal the deviation at any one function in the class.

Worked Example: Taking the Supremum Over Two Functions

Let $P$ assign probability $1/4$ to each of $a,b,c,d$, and let $\mathcal F=\{f_1,f_2\}$, where $f_1=\mathbf 1_{\{a,b\}}$ and $f_2=\mathbf 1_{\{c,d\}}$. Consider a sample of size four with observations $a,b,b,d$. Since each set has population probability $1/2$, $Pf_1=Pf_2=1/2$. The empirical proportions are $P_nf_1=3/4$ and $P_nf_2=1/4$. Thus

U_4(\mathcal F) =\max\left\{\left|\frac34-\frac12\right|, \left|\frac14-\frac12\right|\right\} =\frac14.

The supremum selects the larger absolute discrepancy among the two functions. It is not the discrepancy for an average function, nor is it an average of the two absolute discrepancies.

A Finite-Class Bound

For a finite class, elementary variance calculations give direct bounds on both formulations. This result is useful for interpreting the supremum without making claims about more general function classes.

Theorem: Suppose $X_1,\ldots,X_n$ are independent and identically distributed with distribution $P$, and $\mathcal F=\{f_1,\ldots,f_m\}$ is a nonempty finite class of measurable functions with $E[f_j(X_1)^2]<\infty$ for every $j$. Then, for every $\varepsilon>0$, $$ E[U_n(\mathcal F)] \leq \left(\frac{1}{n}\sum_{j=1}^m\operatorname{Var}(f_j(X_1))\right)^{1/2}, \qquad P(U_n(\mathcal F)>\varepsilon) \leq \frac{1}{n\varepsilon^2} \sum_{j=1}^m\operatorname{Var}(f_j(X_1)). $$

Proof. Set $Z_j=P_nf_j-Pf_j$. Independence and identical distribution imply $E[Z_j]=0$ and

E[Z_j^2] =\operatorname{Var}\left(\frac1n\sum_{i=1}^n f_j(X_i)\right) =\frac{1}{n^2}\sum_{i=1}^n\operatorname{Var}(f_j(X_i)) =\frac{\operatorname{Var}(f_j(X_1))}{n}.

Since $U_n(\mathcal F)=\max_{1\leq j\leq m}|Z_j|$, the pointwise inequality $(\max_j|Z_j|)^2\leq\sum_{j=1}^m Z_j^2$ gives

E[U_n(\mathcal F)] \leq \sqrt{E[U_n(\mathcal F)^2]} \leq \left(\sum_{j=1}^m E[Z_j^2]\right)^{1/2} =\left(\frac1n\sum_{j=1}^m\operatorname{Var}(f_j(X_1))\right)^{1/2}.

The first inequality is Cauchy–Schwarz. For the probability bound, if $U_n(\mathcal F)>\varepsilon$, then at least one $|Z_j|>\varepsilon$. The union bound and Chebyshev’s inequality therefore give

P(U_n(\mathcal F)>\varepsilon) \leq\sum_{j=1}^m P(|Z_j|>\varepsilon) \leq\sum_{j=1}^m\frac{E[Z_j^2]}{\varepsilon^2} =\frac{1}{n\varepsilon^2}\sum_{j=1}^m\operatorname{Var}(f_j(X_1)).

This proves both inequalities. $\square$

The bound uses only finite second moments and a finite number of functions; it is not a sharp result in every setting. In particular, the factor involving the number of functions arises from controlling each coordinate separately, rather than from detailed structure shared by the functions.

Expected Deviation as an Integral of Tail Probabilities

A general identity connects the expectation formulation to the probability formulation. It applies to any nonnegative measurable random variable, and therefore to $U_n(\mathcal F)$ whenever the supremum is measurable.

Theorem: If $U$ is a nonnegative measurable random variable, then, allowing either side to be infinite, $$ E[U]=\int_0^\infty P(U>t)\,dt. $$

Proof. For every outcome, $U=\int_0^\infty \mathbf 1\{t<U\}\,dt$, because the indicator is one precisely over an interval of length $U$. The function $(\omega,t)\mapsto\mathbf 1\{t<U(\omega)\}$ is nonnegative and measurable. Tonelli’s theorem therefore permits exchanging expectation and integration:

E[U] =E\!\left[\int_0^\infty \mathbf 1\{t<U\}\,dt\right] =\int_0^\infty E[\mathbf 1\{t<U\}]\,dt =\int_0^\infty P(U>t)\,dt.

This identity says that the expected uniform deviation is the area under its tail-probability curve. A single probability bound at one threshold controls only one point on that curve; bounds across thresholds can be integrated when they are valid over the required range. $\square$

Measurability and Common Pitfalls

For a finite or countable class, each deviation is measurable and the supremum of countably many measurable random variables is measurable. For an uncountable class, measurability is not automatic. One must impose conditions ensuring that the supremum is measurable or adopt a carefully defined outer-probability framework. In the statements here, the measurable-supremum assumption is explicit.

Mistake: treating the supremum like a fixed function. For each fixed $f$, $E[P_nf-Pf]=0$, but this does not imply $E[\sup_f|P_nf-Pf|]=0$. In the Bernoulli example, the signed deviation is centered while the expected absolute deviation is $1/4$.
Mistake: replacing a supremum with a maximum without checking attainment. A supremum is a least upper bound; it need not be attained. The threshold example has supremum $4/15$, approached from below at $t=0.6$, while the deviation at $t=0.6$ is $1/15$.
Mistake: confusing a probability statement with an expectation statement. $P(U_n>\varepsilon)$ is a tail probability at a chosen threshold. $E[U_n]$ averages over all possible sizes and is related to the full tail curve by the integral identity.

Key takeaway: Uniform empirical deviation is the random supremum of absolute empirical-minus-population averages over a function class. Its expectation and its tail probabilities are distinct summaries, and both require attention to the class and to measurability.

Check Your Understanding

Try these questions using the definitions and arguments above.

Write the empirical process and the uniform empirical deviation for a class $\mathcal F$, and state how their suprema are related.
Why does $E[P_nf-Pf]=0$ for each fixed $f$ not imply that $E[U_n(\mathcal F)]=0$?
In the threshold example, what is the deviation at $t=0.6$, and why is it different from the supremum?
Which moment condition is needed for the finite-class theorem, and where does it enter its proof?
State the tail-integral identity for a nonnegative random variable and explain what area it represents.