A plug-in uniform law of large numbers

Attention Conservation Notice: I’m writing this down because I just spent too long trying to find a citation for it to give a student. A useful citation for many purposes is Newey WK (1989) “Uniform Convergence in Probability and Stochastic Equicontinuity” Princeton Econometric Research Memorandum No 342

There are lots of laws of large numbers: theorems whose conclusions are that an average ${\overline{X}}_n$ converges in some useful sense to an expected value $\mu$. You might have the simplest weak LLN: if $X_i$ are iid and $E\left[X_i^2\right]$ and $\mu =E\left[X_i\right]$ exist then $${\overline{X}}_n-\mu \stackrel{p}{\to }0.$$ You might have a law of large numbers for independent but not identically distributed sequences. Or for strong mixing random fields, or survey samples, or sparsely correlated sequences, or sequences of random functions, or whatever. Many of these are fairly easy to prove¹; some are much more difficult². For notational reasons I’ll assume we have a weak law of large numbers, with convergence in probability, but the argument goes through the same for other modes of convergence.

The next complication is that you might have more than one such sequence. If you have finitely many sequences ($K$, say), and ${\overline{X}}_{nk}$ is the mean of the first $n$ elements of sequence $k$, then $$\underset{k\in 1\dots K}{sup}|{\overline{X}}_{nk}-{\mu }_k|\stackrel{p}{\to }0$$ because the supremum is just a finite maximum.

If you have infinitely many sequences, things can go wrong. There is, however, a fairly simple intermediate setting, where $X\left(\theta \right)$ is indexed by a parameter $\theta$ taking values in a compact set $\Theta$. The problem with general $\Theta$ is that weird stuff can happen at the remote edges, and the point of a compact set is that it doesn’t have any remote edges for weird stuff to happen at.

We’ll obviously need a bit more in the way of assumptions, because assuming $\Theta$ is compact gets you precisely nothing if $X\left(\theta \right)$ doesn’t have some well-behavedness as a function of $\theta$. I will assume $X\left(\theta \right)$ is Lipschitz in $\theta$, in the sense that there is a metric $d\left(\right)$ on $\Theta$ and a random variable $M$ with finite mean such that for any ${\theta }_1$, ${\theta }_2$, $$\left|X_i\right({\theta }_1)-X_i({\theta }_2\left)\right|\le Md({\theta }_1,{\theta }_2)$$

---

Theorem: If ${\overline{X}}_n\left(\theta \right)\stackrel{p}{\to }\mu \left(\theta \right)$ pointwise and $X_i\left(\theta \right)$ satisfies the stochastic Lipschitz condition for all $\theta$ in a compact set $\Theta$, then $$\underset{\theta \in \Theta }{sup}\left|{\overline{X}}_n\right(\theta )-\mu (\theta \left)\right|\stackrel{p}{\to }0$$

Proof: Let $ϵ$ be given and choose ${\theta }_1\dots {\theta }_K$ so that the balls of radius $ϵ$ around the ${\theta }_k$ cover all of $\Theta$ (using compactness). For any $\theta \in \Theta$ and the ${\theta }_k$ it belongs to, $$|{\overline{X}}_n\left(\theta \right)-\mu \left(\theta \right)|<|X_n\left(\theta \right)-X_n\left({\theta }_k\right)|+|{\overline{X}}_n\left({\theta }_k\right)-\mu \left({\theta }_k\right)|+|\mu \left({\theta }_k\right)-\mu \left(\theta \right)|$$ The middle term goes to zero in probability as $n\to \infty$ by the pointwise law of large numbers, the first and last terms are bounded in probability by $Mϵ$ and bounded by $E\left[M\right]ϵ$ respectively.

---

This proof is reminiscent of the classical proof of the Glivenko-Cantelli Lemma. It’s a bit different, because it uses a Lipschitz condition rather than monotonicity to bound the first and last terms. Notably, the Glivenko-Cantelli Lemma does not need the index set $\Theta$ to be compact and does not need $X_i\left(\theta \right)$ and $\mu \left(\theta \right)$ to even be continuous.

My result above is not quite the theorem given in Newey’s report; he does not assume that the function ${\overline{X}}_n\left(\theta \right)$ is actually a sample average. That’s important because assuming it’s a sample average is valuable: for the analogue of the Glivenko-Cantelli theorem where you just have an arbitrary sequence $F_n$ of monotone functions converging to a monotone limit $F$, the convergence is in general not uniform on intervals containing a discontinuity of $F$. The key thing about a sample average is that the points stay where you put them: they accumulate, but they don’t move around. The counterexamples to uniform convergence for monotone functions involve the discontinuities moving – eg $F_n$ has a jump at $1-\frac{1}{n}$ and $F$ has a jump at 1. Newey needs some additional assumptions to get equicontinuity as the price for generalising beyond sample averages.

For comparison, here’s the Glivenko-Cantelli lemma, upgraded to take a plug-in pointwise LLN.

---

Theorem: Let $X_i$, $i=1\dots n$ be a sequence of real-value random variables with common marginal distribution $F$. Let $$F_n\left(t\right)=\frac{1}{n}\sum _{i=1}^{n}I(X\le t)$$ be the empirical cumulative distribution function. If $F_n\left(t\right)\stackrel{p}{\to }F\left(t\right)$ for every fixed $t$ then $$\underset{t}{sup}\left|F_n\right(t)-F(t\left)\right|\stackrel{p}{\to }0$$ Proof: Let $ϵ>0$ be given. Choose $-\infty =t_1<t_2<\cdots <t_K=\infty$ so that ${max}_k\left(F\right(t_K)-F(t_{k-1}\left)\right)<ϵ$, where $F(-\infty )=0$ and $F\left(\infty \right)=1$. For any $t$, let $t^{\ast }$ be the first $t_k$ with $t\le t_k$ $$F_n\left(t\right)-F\left(t\right)\le \left(F\right(t^{\ast })-F(t\left)\right)+|F_n\left(t^{\ast }\right)-F\left(t^{\ast }\right)|\le ϵ+\underset{k}{max}|F_n\left(t_k\right)-F\left(t_k\right)|$$ By assumption, we have pointwise (and thus uniform) convergence over $k$, so the second term on the right goes to zero in probability.

Similarly, $$F_n\left(t\right)-F\left(t\right)\ge \left(F\right(t^{\ast })-F(t\left)\right)-|F_n\left(t^{\ast }\right)-F\left(t^{\ast }\right)|\ge ϵ-\underset{k}{max}|F_n\left(t^{\ast }\right)-F\left(t^{\ast }\right)|$$ which again goes to $ϵ$ in probability.

Since $ϵ$ was arbitrary we are done.

---

The two proofs can be reunited by using bracketing numbers, which gives the proof I actually want to present. I got this proof from Weak Convergence and Empirical Processes by van der Vaart and Wellner, where it’s about a third of the first page of Chapter 2.4, but (a) not everyone has read that book,³ and (b) the proof is presented there for iid sequences, so it’s not that useful to me as a citation.

To start with, we need to define bracketing numbers. Given two functions $\ell$ and $u$, the bracket $[\ell ,u]$ is the set of functions $f$ with $\ell \le f\le u$. An $ϵ$-bracket in some norm $\parallel \cdot \parallel$is a bracket with $\parallel u-l\parallel \le ϵ.$ The bracketing number $N_{\left[\right]}(ϵ,\parallel \cdot \parallel ,F)$ of a set $F$ of functions is the minimum number of $ϵ$-brackets needed to cover $F$.

---

Theorem: Let $F$ be a class of measurable functions and $X_i$ a sequence such that (i) $f\left(X_i\right)$ satisfies a weak law of large numbers for each $f\in F$ and (ii) the bracketing numbers $N_{\left[\right]}(ϵ,\parallel \cdot \parallel ,F)$ are finite for every $ϵ>0$. The law of large numbers holds uniformly over $f\in F$.

Proof: Let $ϵ>0$ be given. Write ${\overline{X}}_n\left(f\right)$ for $\frac{1}{n}{\sum }_{i}f\left(X_i\right)$ and $\mu \left(f\right)$ for $E\left[f\right(X\left)\right]$. Choose $N_{\left[\right]}(ϵ,\parallel \cdot \parallel ,F)$ $ϵ$-brackets that cover $F$. Write $u_f$ for the upper function in the bracketing containing $f$ and ${\ell }_f$ for the corresponding lower function.

$${\overline{X}}_n\left(f\right)-\mu \left(f\right)\le \left(\mu \right(u_f)-\mu (f\left)\right)+|{\overline{X}}_n\left(u_f\right)-\mu \left(u_f\right)|$$ so $$\begin{array}{cc}\underset{f\in F}{sup}\left({\overline{X}}_n\right(f)-\mu (f\left)\right)& \le \underset{f\in F}{sup}\left(\mu \right(u_f)-\mu (f\left)\right)+\underset{f\in F}{sup}|{\overline{X}}_n\left(u_f\right)-\mu \left(u_f\right)|\\ & =\underset{f\in F}{sup}\left(\mu \right(u_f)-\mu (f\left)\right)+\underset{i}{max}|{\overline{X}}_n\left(u_i\right)-\mu \left(u_I\right)|\end{array}$$ The first term is bounded by $ϵ$ (by construction). Because there are only finitely many distinct $u_i$ and we assume pointwise convergence, the second term converges to zero in probability as $n\to \infty$.

Similarly $${\overline{X}}_n\left(f\right)-\mu \left(f\right)\ge \left(\mu \right(u_f)-\mu (f\left)\right)-|{\overline{X}}_n\left(u_f\right)-\mu \left(u_f\right)|$$ so $$\begin{array}{cc}\underset{f\in F}{inf}\left({\overline{X}}_n\right(f)-\mu (f\left)\right)& \ge \underset{f\in F}{inf}\left(\mu \right(u_f)-\mu (f\left)\right)-\underset{f\in F}{inf}|{\overline{X}}_n\left(u_f\right)-\mu \left(u_f\right)|\\ & =\underset{f\in F}{inf}\left(\mu \right(u_f)-\mu (f\left)\right)-\underset{i}{min}|{\overline{X}}_n\left(u_i\right)-\mu \left(u_I\right)|\end{array}$$ The first term is bounded by $ϵ$ (by construction); the second term again converges to zero in probability as $n\to \infty$.

Since $ϵ$ was arbitrary, we are done.

---

The classical Glivenko-Cantelli lemma is the case where $F$ is the set of indicators of half-lines: $F=\left\{f_t\right(x)=I(x\ge t),t\in R\}$, whose bracketing numbers that are $O\left({ϵ}^{-1}\right)$. The first result above is for a set of functions indexed by a compact metric space $\Theta$, where the functions are Lipschitz in the parameter. The bracketing numbers are proportional to the number of $ϵ$-balls it takes to cover $\Theta$, which is finite for every $ϵ$.⁴

This Lipschitz-in-the-parameter example is also valuable because the bracketing numbers are small enough that you get a uniform central limit theorem for $F$ with independent data – though, sadly, there aren’t plug-in uniform CLTs for dependent data.⁵ The uniform CLT for iid data is Theorem 5.31 of van der Vaart’s Asymptotic Statistics (though it’s not actually proved until Chapter 19). For independent but not iid data I think you need the van der Vaart and Wellner book, Theorem 2.11.9 and its corollaries and follow-ups.

There are a few similar uniform CLT results for dependent data; for example, there’s a very pretty argument by Doukhan, Massart and Rio for stationary $\beta$-mixing sequences. Most of the work is for stationary sequences, because probabilists understandably don’t want to complicate the interesting and intricate arguments needed to handle dependence with boring and intricate arguments needed to handle non-stationary sequences. One useful exception is by Andrews and Pollard, handling not necessarily stationary strong mixing sequences.