# 3.1. Uniform Law Under Finite Bracketing Entropy

$\newcommand{\argmin}{\mathop{\mathrm{argmin}}\limits}$ $\newcommand{\argmax}{\mathop{\mathrm{argmax}}\limits}$

In Chapter 3, we will focus on the uniform law of large numbers and its sufficiencies. The first part of the chapter consists of the simplest case: ULLN under finite bracketing entropy condition. After that, techniques to prove sufficiencies of ULLN will be introduced. Finally, ULLN under limiting $L^1$-entropy, popular function classes, or under constraints in VC dimension will be covered.

## ULLN under finite bracketing entropy

The first form of the ULLN can be derived from finite bracketing entropy condition.

$$H_{B,1,P}(\delta,\mathcal G),~ \forall \delta >0 \implies \mathcal G \text{ satisfies the ULLN.}$$

Given $\delta>0.$ Let $\{[\ell_i,u_i]\}_{i=1}^N$ be a set of $\delta$-brackets for $\mathcal G.$ \begin{aligned} \int g d(P_n-P) &le \int u_i dP_n - \int g dP \\ &= \int u_i d(P_n-P) + \int (u_i-g) dP \\ &\le \int u_id(P_n-P) + \delta. \end{aligned} Similarly, $$\int gd(P_n-P) \ge \int \ell_id(P_n-P) - \delta.$$ Hence, \begin{aligned} \left| \int g d(P_n-P) \right| &\le \max\left\{ \int\ell_id(P_n-P), \int u_id(P_n-P) \right\} + \delta. \\ \sup_{g\in\mathcal G}\left| \int g d(P_n-P) \right| &\le \max_{i=1,\cdots,N}\left\{ \int\ell_id(P_n-P), \int u_id(P_n-P) \right\} + \delta. \\ \end{aligned} By Glivenko-Cantelli theorem, $\int \ell_i dP_n$ converges to $\int \ell_i dP$ almost surely for all $i$'s. Since the indices are finite, $$\max_{i=1,\cdots,N}\left\{ \int\ell_id(P_n-P), \int u_id(P_n-P) \right\} \le \delta$$ for sufficiently large $n.$ Hence $$\limsup_n \sup_{g\in\mathcal G} \left| \int g d(P_n-P) \right| \le 2\delta \text{ a.s.}$$ and the result follows.

## The envelope condition

For a function class $\mathcal G,$ the function $G:=\sup_{g\in\mathcal G} |g|$ is the envelope of $\mathcal G$.
In addition, we say $\mathcal G$ satisfies the envelope condition, if $G \in L^1(P).$

In fact, the condition given in the lemma 3.1 is a sufficiency of the envelope condition.

$$H_{B,1,P}(\delta,\mathcal G) < \infty,~ \forall\delta>0 \implies G \in L^1(P)$$ where $G(x):=\sup_{g\in\mathcal G} |g(x)|.$

By the given condition, $\sup_{g\in\mathcal G}\|g\|_{1,P} < \infty.$

Let $\{[\ell_i,u_i]\}_{i=1}^N$ be a set of $1$-brackets of $\mathcal G.$ For $g\in\mathcal G,$ there exists an index $j$ such that $\ell_j \le g\le u_j.$ Because $|u_i-\ell_i|\le 1$ for all $i=1,\cdots,N,$ \begin{aligned} |g| &\le |u_j - \ell_j| + |\ell_j|, \\ \sup_{g\in\mathcal G} |g| &\le \sum_{i=1}^N |\ell_i| + \sum_{i=1}^N |u_i-\ell_i|. \end{aligned} Hence, $$\|G\|_{1,P} \le \sum_{i=1}^N \|\ell_i\|_{1,P} + N < \infty.$$

References

• van de Geer. 2000. Empirical Processes in M-estimation. Cambridge University Press.
• Theory of Statistics II (Fall, 2020) @ Seoul National University, Republic of Korea (instructor: Prof. Jaeyong Lee).