Metric Entropy Method — A Guided Tour of Modern Statistics

Notes / Function Spaces

6.2 Metric Entropy Method

6.2.1 Entropies of Function Classes

We want to understand the \(\varepsilon \)-covering number for \(T \subseteq \mathbb {R}^d\). The intuition is that \[ \log N(\varepsilon ; T, \rho ) \asymp \log \frac {\mathrm {Vol}(T)}{\mathrm {Vol}(B_\rho (\varepsilon ))}, \]

Now we discuss a more complicated example.

Proof. Fix \(\delta = \epsilon ^{\frac 1 \alpha } \le 1\) and a \(\delta -\)net \(x_1, \cdots ,x_m\). For each \(k=(k_1,\cdots , k_d)\) with \(k_{\cdot }=\sum k_i \le \lfloor \alpha \rfloor \), define the vector \[ A_k f = \left ( \left \lfloor \frac {D^k f(x_1)}{\delta ^{\alpha -k}} \right \rfloor , \ldots , \left \lfloor \frac {D^k f(x_m)}{\delta ^{\alpha -k}} \right \rfloor \right ). \] If \(Af=Ag\), then we have \(\|f-g\|_\infty \lesssim \epsilon \). Now we count the number of vectors. Each column of the matrix can have at most \((2\delta ^{-\alpha }+2)^{(\beta +1)^d}\) different values.

Assume WLOG that \(x_1, \ldots , x_m\) have been chosen and ordered such that for each \(j > 1\) there is an index \(i < j\) with \(\|x_i - x_j\| < 2\delta \). Then use the crude bound obtained previously for the first column only. For each later column, indexed by \(x_j\), there exists a previous \(x_i\) with \(\|x_i - x_j\| < 2\delta \). By Taylor’s theorem, \[ D^k f(x_j) = \sum _{k_\cdot + l_\cdot \leq \beta } D^{k+l} f(x_i) \frac {(x_i - x_j)^l}{l!} + R, \] where \(|R| \lesssim \|x_i - x_j\|^{\alpha - k_\cdot }\). Thus with \(B_k f = \delta ^{\alpha - k_\cdot } A_k f\), \begin{align*} \left | D^k f(x_j) - \sum _{k_\cdot + l_\cdot \leq \beta } B_{k+l} f(x_i) \frac {(x_i - x_j)^l}{l!} \right | &\lesssim \sum _{k_\cdot + l_\cdot \leq \beta } \left | B_{k+l} f(x_i) - D^{k+l} f(x_i) \right | \frac {\|x_i - x_j\|^l}{l!} + \delta ^{\alpha - k_\cdot } \\ &\lesssim \sum _{k_\cdot + l_\cdot \leq \beta } \delta ^{\alpha - k_\cdot - l_\cdot } \cdot \frac {\delta ^{l_\cdot }}{l!} + \delta ^{\alpha - k_\cdot } \lesssim \delta ^{\alpha - k_\cdot }. \end{align*}

Thus given the values in the \(i\)th column of \(Af\), the values \(D^k f(x_j)\) range over an interval of length proportional to \(\delta ^{\alpha - k_\cdot }\). It follows that the values in the \(j\)th column of \(Af\) range over integers in an interval of length proportional to \(\delta ^{k_\cdot - \alpha } \delta ^{\alpha - k_\cdot } = 1\). Consequently, there exists a constant \(C\) depending only on \(\alpha \) and \(d\) such that \[ \#Af \leq (2\delta ^{-\alpha } + 2)^{(\beta +1)^d} C^{m-1}. \] The theorem follows upon replacing \(\delta \) by \(\varepsilon ^{1/\alpha }\) and \(m\) by its upper bound \(\lambda (\mathcal {X}^1) \varepsilon ^{-d/\alpha }\), respectively, taking logarithms, and bounding \(\log (1/\varepsilon )\) by a constant times \((1/\varepsilon )^{d/\alpha }\). □

6.2.2 One-step Discretization Bound

Now we are going to discuss the metric entropy method for obtaining bounds on empirical processes. We have a metric space \((T, \rho )\), and we want to control \[ \mathbb {E}\left [\sup _{\theta \in T} X_\theta \right ] \quad \text {or} \quad \mathbb {E}\left [\sup _{\theta \in T} |X_\theta |\right ], \] where \(X_\theta \) is usually mean 0 and sub-Gaussian. We introduced the metric entropy is \(\log N(\varepsilon ; T, \rho )\), where \(N(\varepsilon ; T, \rho ) = \inf \{N : |T_\varepsilon | = N, T_\varepsilon \text { is an } \varepsilon \text {-cover}\}\) is the \(\varepsilon \)-covering number.

Here is the one-step discretization bound that the maximal inequality gives us:

Example 6.18 (Gaussian Complexity). Consider \(W_i \overset {\text {iid}}{\sim } N(0, 1)\), so \(\langle W, \theta \rangle \sim \mathrm {sG}(\|\theta \|_2)\). Then we know that \[ \mathcal {G}(B_2(1)) = \mathbb {E}\left [ \sup _{\theta \in B_2(1)} \langle W, \theta \rangle \right ] = \mathbb {E}[\|W\|_2] \asymp \sqrt {d}. \] Here is another way to get this computation: \begin{align*} \mathcal {G}(B_2(1)) &\leq C \left [ \sup _{\theta \in B_2(1)} \underbrace {\|\theta \|_2}_{=1} \underbrace {\sqrt {\log N(\varepsilon ; B_2(1), \|\cdot \|_2)}}_{\leq \sqrt {d \log (1 + 2/\varepsilon )}} + \mathbb {E}_W \left [ \sup _{\|\theta - \theta '\|_2 \leq \varepsilon } |W_\theta - W_{\theta '}| \right ] \right ] \\ &\leq C \left [ \sqrt {d \log (1 + 2/\varepsilon )} + \mathbb {E}_W \left [ \sup _{\|\theta - \widetilde {\theta }\|_2 \leq \varepsilon } \langle W, \theta - \theta ' \rangle \right ] \right ] \\ &= C \left [ \sqrt {d \log (1 + 2/\varepsilon )} + \mathbb {E}_W \left [ \sup _{\|r\|_2 \leq \varepsilon } \langle W, r \rangle \right ] \right ] \\ &= C \left [ \sqrt {d \log (1 + 2/\varepsilon )} + \varepsilon \, \mathbb {E}_W \underbrace {\left [ \sup _{\|\widetilde {r}\|_2 \leq 1} \langle W, \widetilde {r} \rangle \right ]}_{\mathcal {G}(B_2(1))} \right ]. \end{align*}

This tells us that \[ \mathcal {G}(B_2(1)) \leq C \sqrt {d \log (1 + 2/\varepsilon )} + C \varepsilon \mathcal {G}(B_2(1)). \] If we take \(\varepsilon \leq \frac {1}{2C}\), then we get \[ \mathcal {G}(B_2(1)) \leq 2C \sqrt {d \log (1 + 4C)} \asymp \sqrt {d}, \] which is the same order as before.

6.2.3 Chaining Method

We have been using the bound \[ \mathbb {E}\left [\sup _{\theta \in T} |X_\theta |\right ] \lesssim \inf _{\varepsilon } \underbrace {\inf _{\varepsilon \text {-cover } T_\varepsilon } \mathbb {E}\left [\sup _{\theta \in T_\varepsilon } |X_\theta |\right ]}_{\text {bdd by covering number}} + \underbrace {\mathbb {E}\left [\sup _{\rho (\theta , \widetilde {\theta }) \leq \varepsilon } |X_\theta - X_{\widetilde {\theta }}|\right ]}_{\text {how to give tight control?}} \] Controlling the right term can require ad-hoc arguments. The chaining method gives a way to bound this effectively.

Here, \(J(\varepsilon ; D; T, \rho )\) is known as Dudley’s entropy integral.

Proof. Take a sequence of \(\varepsilon \)-coverings corresponding to \(\varepsilon _m = D/2^m\) for \(m = 0, 1, 2, 3, \ldots , L\). Let \(U_m\) be the minimal \(\varepsilon _m\)-covering of \(T\), so \(|U_m| \leq N(\varepsilon _m; T_\rho )\). Then define the projection operation \(\pi _m(\theta ) = \arg \min _{\beta \in U_m} \rho (\theta , \beta )\).

This allows us to bound \begin{align*} |X_\theta - X_{\widetilde {\theta }}| &\leq |X_\theta - X_{\pi _2(\theta )}| + |X_{\pi _2(\theta )} - X_{\pi _1(\theta )}| + |X_{\pi _1(\theta )} - X_{\pi _1(\widetilde {\theta })}| \\ &\quad + |X_{\pi _1(\widetilde {\theta })} - X_{\pi _2(\widetilde {\theta })}| + |X_{\pi _2(\widetilde {\theta })} - X_{\widetilde {\theta }}|. \end{align*}

Then we can take the expectation of \(\sup _{\theta , \widetilde {\theta }}\) on both sides. What is the purpose of having all these interpolation points? The first and the last terms have infinitely many choices, so these are the discretization terms, while the middle terms have only finitely many choices, so we can apply the maximal inequality. \begin{align*} \mathbb {E}\left [\sup _{\theta , \widetilde {\theta } \in T} |X_\theta - X_{\widetilde {\theta }}|\right ] &\leq \mathbb {E}\left [\sup _{\theta , \widetilde {\theta } \in T} |X_{\pi _1(\theta )} - X_{\pi _1(\widetilde {\theta })}|\right ] + 2\mathbb {E}\left [\sup _{\theta \in T} |X_{\pi _2(\theta )} - X_{\pi _1(\theta )}|\right ] \\ &\quad + \cdots + 2\mathbb {E}\left [\sup _{\theta \in T} |X_{\pi _L(\theta )} - X_{\pi _{L-1}(\theta )}|\right ] + 2\mathbb {E}\left [\sup _{\theta \in T} |X_\theta - X_{\pi _L(\theta )}|\right ]. \end{align*}

These terms on the right correspond to \(\varepsilon _0, \varepsilon _1, \ldots , \varepsilon _{L-1}, \varepsilon _*\), respectively. This process will define a Riemann sum. For the remaining details, see the textbook. □

6.2.4 Examples of Rademacher Complexity Bounds

We begin with the proposition.

Proposition 6.24. Let \(\mathcal {R}_n(\mathcal {F}) := \mathbb {E}_{\varepsilon _i, X_i}\!\left [\sup _{f\in \mathcal {F}}\left |\tfrac {1}{n}\sum _{i=1}^{n}\varepsilon _i f(X_i)\right |\right ]\). Then

1.: \[ \mathcal {R}_n(\mathcal {F}) \;\lesssim \; \frac {D_{\mathbb {P}}}{\sqrt {n}}\int _{0}^{1} \sup _{Q} \sqrt {\log N\!\left (D_{Q}\,u;\,\mathcal {F},\,L^2(Q)\right )}\,du, \]
2.: \[ \mathcal {R}_n(\mathcal {F}) \;\lesssim \; \frac {D_{\infty }}{\sqrt {n}}\,\inf _{\varepsilon }\,\varepsilon \;+\; \frac {1}{\sqrt {n}}\int _{\varepsilon }^{1} \sup _{Q} \sqrt {\log N\!\left (D_{\infty }\,u;\,\mathcal {F},\,L^\infty \right )}\,du, \]

where \(D_{\mathbb {P}} = \sup _{f\in \mathcal {F}}\|f\|_{L^2(\mathbb {P})}\) and \(D_{\infty } = \sup _{f\in \mathcal {F}}\|f\|_{\infty }\).

Example 6.25. Let \(\mathcal {F} = \{f_\theta (x) = 1 - e^{-\theta x},\ x \in [0,1] : \theta \in [0,1]\}\) be a parametric function class. Then taking the derivative gives us \[ |f_{\theta _1}(x) - f_{\theta _2}(x)| \;\leq \; \sup _{\theta \in [\theta _1, \theta _2]} \underbrace {|x e^{-\theta x}|}_{\leq \, x}\,|\theta _1 - \theta _2| \;\leq \; |\theta _1 - \theta _2|. \] The covering number for the unit interval with \(|\cdot |\) is bounded as \[ N(\varepsilon ;\,[0,1],\,|\cdot |) \;\leq \; \frac {1}{2\varepsilon } + 1, \] so we get a covering number bound for the parametric function class \[ N(\varepsilon ;\,\mathcal {F},\,L^\infty ) \;\leq \; N(\varepsilon ;\,[0,1],\,|\cdot |) \;\leq \; \frac {1}{2\varepsilon } + 1. \] Using the chaining bound with \(D_\infty = \sup _{f\in \mathcal {F}}\|f\|_\infty = \sup _{f\in \mathcal {F}}\sup _{x\in [0,1]}|1 - e^{-\theta x}| \leq 1\), \begin{align*} \mathcal {R}_n(\mathcal {F}) &\leq \frac {D_\infty }{\sqrt {n}} \int _{0}^{1} \sqrt {\log N\!\left (u D_\infty ;\,\mathcal {F},\,L^\infty \right )}\, du \;=\; \frac {1}{\sqrt {n}} \int _{0}^{1} \sqrt {\log N\!\left (u;\,\mathcal {F},\,L^\infty \right )}\, du \\ &= \frac {1}{\sqrt {n}} \int _{0}^{1} \sqrt {\log \!\left (\tfrac {1}{2u} + 1\right )}\, du \\ &\lesssim \frac {C}{\sqrt {n}}. \end{align*}

Example 6.26 (Lipschitz parameterization). Consider a function class \(\mathcal {F} = \{f_\theta : \mathcal {X} \to \mathbb {R} : \theta \in B_2^d(1)\}\) with \(\|f_0(x)\|_\infty = c_0 = 0\). If \(|f_{\theta _1}(x) - f_{\theta _2}(x)| \leq L\|\theta _1 - \theta _2\|_2\), then we can use the bound \[ \log N(\varepsilon ;\,\mathcal {F},\,L^\infty ) \;\leq \; \log N\!\left (\varepsilon ;\,B_2^d(1),\,\|\cdot \|_2\right ) \;\lesssim \; d\log \!\left (\tfrac {1}{\varepsilon }\right ) \;\lesssim \; d\log \!\left (\tfrac {1}{\varepsilon } + 1\right ) \] to get \[ \mathcal {R}_n(\mathcal {F}) \;\lesssim \; L \,\frac {D_\infty }{\sqrt {n}} \int _{0}^{1} \sqrt {\log N(\varepsilon ;\,\mathcal {F},\,L^\infty )}\, d\varepsilon , \] where \(D_\infty = \sup _\theta \|f_\theta \|_\infty \leq c_0 + L = L\). Continuing, \begin{align*} \mathcal {R}_n(\mathcal {F}) &\lesssim \frac {L}{\sqrt {n}} \int _{0}^{1} \sqrt {d\log (1/u)}\, du \\ &\lesssim L\sqrt {\frac {d}{n}}. \end{align*}

Example 6.27 (Rademacher complexity of Lipschitz functions on \([0,1]^d\)). For \(L > 0\) and \(d \in \mathbb {Z}_{\geq 1}\), consider the function class \[ \mathcal {F}_L^d = \bigl \{g : [0,1]^d \to \mathbb {R} \;:\; g(\mathbf {0}) = 0,\ |g(\mathbf {x}) - g(\mathbf {y})| \leq L\|\mathbf {x} - \mathbf {y}\|_\infty \bigr \}. \] With \(\mathbf {x}_i \stackrel {\mathrm {iid}}{\sim } \mathbb {P}\) and \(\varepsilon _i \stackrel {\mathrm {iid}}{\sim } \mathrm {Unif}(\{\pm 1\})\), we wish to bound the Rademacher complexity \[ \mathcal {R}_n(\mathcal {F}_L^d) \;=\; \mathbb {E}_{\mathbf {x}_i,\varepsilon _i}\!\left [\sup _{f\in \mathcal {F}_L^d}\left |\tfrac {1}{n}\sum _{i=1}^n \varepsilon _i f(\mathbf {x}_i)\right |\right ] \] independently of \(\mathbb {P}\), using two methods.

The two ingredients common to both arguments are the metric entropy bound \[ \log N\!\left (\varepsilon ;\,\mathcal {F}_L^d,\,\|\cdot \|_\infty \right ) \;\lesssim \; \left (\tfrac {L}{\varepsilon }\right )^d, \] and the fact that, conditionally on \((\mathbf {x}_i)\), the quantity \(\tfrac {1}{n}\sum _{i=1}^n \varepsilon _i f(\mathbf {x}_i)\) is sub-Gaussian with parameter \(L/\sqrt {n}\).

Method 1: one-step discretization. Let \(\mathcal {N}\) be an \(\varepsilon \)-cover of \(\mathcal {F}_L^d\). Splitting the supremum across the cover and its residual, \[ \mathcal {R}_n(\mathcal {F}_L^d) \;\leq \; \varepsilon + \sqrt {\tfrac {2\sigma ^2}{n}\,\log |\mathcal {N}|} \;\leq \; \varepsilon + \sqrt {\tfrac {2L^2}{n}\left (\tfrac {L}{\varepsilon }\right )^d} \;\asymp \; \varepsilon + \frac {L^{1+d/2}}{\sqrt {n}}\,\varepsilon ^{-d/2}. \] Choosing \(\varepsilon = L\, n^{-1/(d+2)}\) to balance the two terms yields \[ \mathcal {R}_n(\mathcal {F}_L^d) \;\lesssim \; L\,n^{-\frac {1}{d+2}}. \]

Method 2: Dudley’s entropy integral. The chaining bound gives \[ \mathcal {R}_n(\mathcal {F}_L^d) \;\lesssim \; \varepsilon + \frac {1}{\sqrt {n}}\int _{\varepsilon }^{2L}\!\left (\tfrac {L}{u}\right )^{d/2}\!du \;=\; \varepsilon + \frac {L}{\sqrt {n}}\int _{\varepsilon /L}^{2} u^{-d/2}\, du, \] whose evaluation depends on \(d\): \[ \begin {array}{c|c|c|c} \hline d & \displaystyle \int _{\varepsilon /L}^{2} u^{-d/2}\, du & \text {optimal } \varepsilon & \text {rate} \\ \hline 1 & \leq 2\sqrt {2} & 0 & \mathcal {R}_n \lesssim L/\sqrt {n} \\[2pt] 2 & \log 2 + \log L - \log \varepsilon & L/\sqrt {n} & \mathcal {R}_n \lesssim \tfrac {L}{\sqrt {n}}(1 + \log n) \\[2pt] \geq 3 & \leq \tfrac {2}{d-2}(L/\varepsilon )^{d/2 - 1} & L\,n^{-1/d} & \mathcal {R}_n \lesssim L\,n^{-1/d} \\ \hline \end {array} \]

Example 6.28 (Boolean Function Classes). Consider a Boolean function class \(\mathcal {F} \subseteq \{f : \mathcal {X} \to \{0,1\}\}\), VC theory tells us that \(\mathcal {F}\) has PD(\(\nu \)), where \(\nu = \mathrm {VC}(\mathcal {F})\). Using the maximal inequality, we have the bound \[ \mathcal {R}_n(\mathcal {F}) \lesssim \sqrt {\frac {\nu \log (n+1)}{n}}. \] We have mentioned that the log factor in this bound makes the bound not tight.

Proposition 6.29 (Covering Number for Boolean Function Class). For a boolean function class with \(\nu = \mathrm {VC}(\mathcal {F})\), \[ \sup _{\mathbb {P}} \log \bigl (N(\varepsilon ; \mathcal {F}, L^2(\mathbb {P}))\bigr ) \lesssim \nu \log \left (\frac {e}{\varepsilon }\right ) \] for \(\varepsilon < 1\).

For a sharp but difficult proof of this bound, see theorem 2.6.4 from [Van der Vaart and Wellner, 1996]. A weaker but easier version of this bound can be found in the notes [Sen, Theorem 7.9].

If we use the chaining argument, we get the bound \[ \mathcal {F}_n(\mathcal {F}) \lesssim \frac {1}{\sqrt {n}} \int _0^1 \sqrt {\nu \log (e/\varepsilon )} \, d\varepsilon \propto \sqrt {\frac {\nu }{n}}. \]