Empirical Processes, Tensorization, and the Entropy Method
A sample average is close to its expectation under familiar assumptions. Statistical estimation asks for more: the function being averaged may be chosen after seeing the data, so we need simultaneous control over a whole class of averages. Empirical process theory develops this control. We will study fluctuations, uniformity, expected suprema, and Gaussian approximations.
Concentration. Suppose we are given i.i.d. random variables \(X_1, X_2, \dots\) with \(\mathbb{E}|X_1|<\infty\); by the law of large numbers, we have
\[\begin{aligned} \frac1n \sum_{1 \leq i \leq n} X_i - \mathbb{E} \left[ \frac1n \sum_{1 \leq i \leq n} X_i \right] \xrightarrow[n\to\infty]{P} 0 ~. \end{aligned}\]We can restate this in the following way: let \(f(x_1, \dots, x_n) = \frac1n \sum_{1 \leq i \leq n} x_i\). Then, the random variable \(f(X_1,\dots,X_n)\) is close to its mean for sufficiently large \(n\). Stated this way, the law of large numbers phenomenon reflects a general principle, called the concentration phenomenon, by virtue of which it is very common for functions of many independent variables to have small fluctuations.
Uniformity. In light of the scenario above, we may be interested in asking if a “small fluctuations” phenomenon holds for all functions \(f\) belonging to a certain class of functions. As we will see later, one remarkable feature of the concentration principle is that it provides information on the fluctuations for very general functions \(f\). Given these information, we want to understand if the convergence to the mean above is uniform over a certain class of functions.
Uniformity is a desirable property for investigating, among other things, consistency of statistical estimators. One important use case of uniformity is investigating the consequences of the plug-in principle. Many estimation problems can be seen as constructing a functional, \(L\), that maps a distribution function \(F\) to a real number. The plug-in principle suggests we replace \(F\) by its empirical distribution, \(\widehat F_n\), and we would study the limiting behaviour of \(L(\widehat F_n)\). In other words, we need to study the conditions under which \(L(\widehat F_n)\) converges to \(L(F)\) in probability, or almost surely. As we will see in the sequel, we often want such convergence to be uniform across some class of functions of interest.
Suprema. From above, the concentration principle is concerned with the deviation of a random function \(f(X_1, \dots, X_n)\) from its mean \(\mathbb{E} f(X_1, \dots, X_n)\). However, it does not provide any information on the value of \(\mathbb{E} f(X_1, \dots, X_n)\) itself. The problem of investigating uniformity can be treated at a very high level of generality. Without additional structure, the problem of estimating \(\mathbb{E} f(X_1, \dots, X_n)\) cannot be addressed at such a level of generality. The next-best option is to study the supremum of a random process, written as \(\sup_{t \in T} \: X_t\), where the set \(T\) indexes “time” (and the collection of random variables). The reason that such quantities play an important role in statistics and probability theory is twofold. One, a sizeable class of problems involve studying a large number of interdependent degrees of freedom; the need to obtain simultaneous control over many random variables thus arises frequently as an ingredient of the mathematical analysis. Two, there are many problems in which various quantities of interest can be naturally expressed in terms of suprema. We will see examples of these later.
Universality. A special case is the central limit theorem. Suppose the observations are i.i.d. with finite, nonzero variance. The centered average, multiplied by the square root of the sample size, converges in distribution to a Gaussian variable with that variance. This is an asymptotic statement as \(n\) tends to infinity:
\[\begin{aligned} \frac{1}{\sqrt{n}} \sum_{1 \leq i \leq n} (X_i - \mathbb{E} X_i) \xrightarrow[n\to\infty]{d} G_1 - \mathbb{E}G_1 ~, \end{aligned}\]where \(G_i\) are independent Gaussian random variables with the same mean and variance. The phenomenon that the detailed features of the distribution of the individual components (i.e. \(X_i\)s) become irrelevant is often referred to as universality. As in the case of concentration, it turns out that this phenomenon occurs much more generally. It can found in “sufficiently smooth” classes of functions, as we will see.
These questions require different estimates. Concentration bounds deviations from a mean; estimates for a supremum determine the scale around which concentration occurs. We begin with tensorization, which reduces variance and entropy estimates for independent coordinates to estimates involving one coordinate at a time.
1. Fundamental Techniques
1.1. The Principle of Tensorization
How does independence help bound the fluctuation of a function of many observations? Tensorization answers this by separating the contribution of each coordinate. We first consider the variance
Lemma 1. Let \(X\) be a random variable, possibly vector-valued. For any bounded measurable real-valued function \(f\),
Proof. Since \(\mathop{\mathrm{Var}}(f(X)) = \mathop{\mathrm{Var}}(f(X) - a) \leq \mathbb{E} [f(X) - a]^2\) for any \(a \in \mathbb R\), we can obtain the desired inequalities if we set \(a = \frac{\sup f + \inf f}{2}\) and \(a = \inf f\). ◻
The bound uses only the range of the function. It assumes nothing about \(X\), and therefore does not take advantage of independent coordinates. Tensorization allows us to apply a range estimate separately in each coordinate. The purpose of this technique is to deduce high-dimensional inequalities from low-dimensional ones without introducing additional dimension-dependent conditions. To formulate this bound, let \(X_1, \dots, X_n\) be independent random variables. For a function \(f(x_1, \dots, x_n)\), let
This is the variance calculated with respect to \(X_i\) only; all other entries are fixed. We apply the martingale difference method to show the following result.
Theorem 2 (Efron-Stein). If \(X_1, \dots, X_n\) are independent random variables and \(f(X_1,\dots,X_n)\) is square-integrable, then
Proof. Reveal the observations one at a time. The change in conditional expectation at each step defines a martingale difference:
Clearly,
Furthermore, for any \(\ell < i\), we have, by the law of iterated expectations,
Therefore,
If we can show \(\mathbb{E} \Delta_i^2 \leq \mathbb{E} [\mathop{\mathrm{Var}}_i (f(X_1, \dots, X_n))]\) for every \(i\), then we are done. To do this, note that, by the law of iterated expectations and that \(X_i\) is independent of \(X_1, \dots, X_{i-1}, X_{i+1}, \dots, X_n\),
Therefore, for the recentred increment
we have \(\Delta_i = \mathbb{E} [ \breve \Delta_i \mid X_1, \dots, X_i]\). It follows again by the independence of \(X_i\) and \(X_1, \dots, X_{i-1}, X_{i+1}, \dots, X_n\) that
The desired inequality then follows from Jensen’s inequality applied to the conditional expectation \(\mathbb{E} \Delta_i^2 = \mathbb{E}[ \mathbb{E}[\breve \Delta_i \mid X_1, \dots, X_i]^2] \leq \mathbb{E}\breve\Delta_i^2\). ◻
1.2. The Entropy Method
Variance controls a second moment. To obtain exponential tail bounds, we will instead control the exponential moments through entropy. This is the entropy method. For a nonnegative random variable \(X\), the (concentration) entropy of \(X\) is defined as
We use \(0\log0=0\) and assume finite mean and positive logarithmic moment whenever subtracting the two terms. Entropy is a convex functional of the random variable. To understand why the concentration entropy is a valuable tool for understanding concentration, we need to draw a connection with other concepts from the theory of concentration. The following result is fundamental, and is often called the Herbst argument.
For completeness, the function \(\Phi(u,m)=u\log(u/m)\) is jointly convex for \(u,m>0\): its Hessian has nonnegative diagonal entries and determinant zero. It extends continuously to \(u=0,m>0\). Applying this convexity pointwise to \((U,\mathbb{E}U)\) and \((V,\mathbb{E}V)\), then taking expectations, proves
If either variable has zero mean, it is zero almost surely, and the assertion follows from \(\operatorname{Ent}(cU)=c\operatorname{Ent}(U)\) for \(c\geq0\).
Proposition 3 (Herbst argument). Let \(X\) be integrable, with \(\mathbb{E}e^{\lambda X}<\infty\) for every \(\lambda>0\). Suppose
Then,
Proof. Put \(M(\lambda)=\mathbb{E}e^{\lambda X}\) and \(\psi(\lambda)=\log M(\lambda)-\lambda\mathbb{E}X\). For \(\lambda>0\), differentiation under the expectation is justified locally: on \(X\geq0\), \(|X|e^{\lambda X}\) is bounded by a constant times \(e^{(\lambda+\delta)X}\); on \(X<0\), it is bounded on any compact interval of positive \(\lambda\). Thus
At zero, integrability and a positive exponential moment justify \(M'(0+)=\mathbb{E}X\): the negative-side difference quotient is bounded by \(|X|\), and the positive side by \(Xe^{\delta X}\). Consequently \(\psi(\lambda)=o(\lambda)\) as \(\lambda\downarrow0\). Integrate the displayed derivative from \(a\) to \(\lambda\), and let \(a\downarrow0\). This gives \(\psi(\lambda)/\lambda\leq\lambda\sigma^2/2\), hence the claimed bound for \(\lambda>0\). At zero it is an equality. ◻
The Herbst argument reduces an exponential-moment bound to an entropy bound. For a function of independent observations, tensorization estimates this entropy one coordinate at a time, just as the Efron–Stein inequality estimates variance. To state this result, just as we did in the discussion of the variance, we need to look at the coordinate-wise entropy. To do so, let \(X_1, \dots, X_n\) be independent random variables. For some function \(f: \mathbb R^n \to [0,\infty)\), define the function
i.e. the \(i\)th coordinate entropy is the entropy of \(f(X_1, \dots, X_n)\) with respect to \(X_i\) only, while keeping the rest of the (random) variables fixed. We can then show the following statement.
Theorem 4 (Entropy tensorizes). Let \(X_1,\ldots,X_n\) be independent and \(Y=f(X_1,\ldots,X_n)\ge0\) measurable, with \(\mathbb{E}Y<\infty\) and \(\mathbb{E}[Y\log_+Y]<\infty\). With \(0\log0=0\),
A variational formula will supply the one-coordinate bound.
Proposition 5. For a nonnegative \(U\) with finite mean and \(\mathbb{E}[U\log_+U]<\infty\),
Proof. For an admissible \(V\), define \(dQ=e^VdP\). Jensen's inequality for \(x\log x\) gives
If \(\mathbb{E}U=0\), both sides of the variational formula are zero. Otherwise choose \(V_\epsilon=\log((U+\epsilon)/(\mathbb{E}U+\epsilon))\). This has \(\mathbb{E}e^{V_\epsilon}=1\), and \(\mathbb{E}[UV_\epsilon]\to\operatorname{Ent}(U)\) as \(\epsilon\downarrow0\). The assumed positive logarithmic moment and the bound on \(u|\log u|\) for \(0\le u\le1\) justify the limit. Thus zero values of \(U\) do not require taking a logarithm of zero in an admissible test variable. □
Proof of Theorem 4. First suppose \(0<a\le Y\le b<\infty\). Set \(M_i=\mathbb{E}[Y\mid X_1,\ldots,X_i]\), with \(M_0=\mathbb{E}Y\), and define the logarithmic increments
They telescope to \(\log Y-\log\mathbb{E}Y\). Moreover, conditional on all coordinates except \(X_i\), independence gives
Applying Proposition 5 to the conditional law in coordinate \(i\), then averaging, yields \(\mathbb{E}[YW_i]\le\mathbb{E}\operatorname{Ent}_i f\). Consequently,
For general \(Y\) under the stated assumptions, apply the bounded argument to \((Y\wedge m)+\epsilon\), let \(\epsilon\downarrow0\), and then \(m\to\infty\). Both the unconditional and conditional entropy expressions converge. Indeed, \(u\log u\) is bounded below, its positive part is dominated by \(Y\log_+Y\), and Jensen bounds the conditional-mean term by the conditional expectation of this integrable envelope. This proves the asserted inequality. □
Combining entropy tensorization with the Herbst argument gives a route to Gaussian-type concentration for nonlinear functions of independent variables. Among other things, we can show this approach yields a bounded difference inequality, where the variance proxy is the sum of squared “discrete derivatives” of the random variable. We will make this formal in the discussion of concentration inequalities (in particular, in Lemma 12 of the concentration-inequalities note). For now, we note the following result, known as a modified log-Sobolev inequality.
Theorem 6 (Modified log-Sobolev inequality; discrete). Let \(X\) and \(\widetilde X\) be i.i.d. real-valued random variables with finite second moments and finite expectations of their squares times their exponentials. Then,
where the expectation is over the independent pair.
The assumptions make every term finite: \(e^X\leq e+X^2e^X1_{\{X>1\}}\), while \(|X|e^X\) is controlled by \(e^X+X^2e^X\). Independence and \((X-\widetilde X)^2\leq2X^2+2\widetilde X^2\) then give integrability on the right. To justify the first entropy bound in the proof, Jensen yields \(\log\mathbb{E}e^X\geq\mathbb{E}X\), hence
The equality follows by expanding the product and using independence for both cross terms.
Proof. By direct calculations, note that for any \(a, b \in \mathbb R\),
where the inequality follows from convexity of the map \(t \mapsto e^{(1-t) a + t b}\). It follows from the definition of entropy and the variational formulation that
where the equality follows from the fact that \(X\) and \(\widetilde X\) are i.i.d. random variables. ◻
Remark 7. The inequality in (1) is straightforward to obtain: note that the concavity of the logarithm tells us that, if \(W\) and \(\widetilde W\) are i.i.d. positive random variables, then
Note that independence is used to obtain the inequality. And further note that \((W, \widetilde W)\) and \((\widetilde W, W)\) have the same joint distribution; so, calculating \(\operatorname{Ent}(\widetilde W)\) and averaging with \(\operatorname{Ent}(W)\), we have the desired result (the expectation in (1) is with respect to the joint law of \(W\) and \(\widetilde W\)).