# Covering number after projection

In these lecture notes on Statistical Learning Theory we find the following definitions for covering numbers:

Definition. Let $$(\mathcal{W}, d)$$ be a metric space and $$\mathcal{F} \subset \mathcal{W}$$. For every $$\epsilon>0,$$ denote by $$N(\epsilon, \mathcal{F}, d)$$ the minimal number of open balls (with respect to metric $$d$$ ) needed to cover $$\mathcal{F}$$. That is, $$N(\epsilon, \mathcal{F}, d)$$ is the minimal cardinality of the set $$\left\{f_{1}, \ldots, f_{m}\right\} \subset \mathcal{W}$$ with the property that for every $$f \in \mathcal{F}$$ there is some $$f_{i}$$ such that $$d\left(f, f_{i}\right)<\epsilon .$$ The set $$\left\{f_{1}, \ldots, f_{m}\right\}$$ is called an $$\epsilon$$ -cover of $$\mathcal{F}$$.

and for uniform covering numbers:

We will be interested in metrics induced by samples. For every sample $$\left\{x_{1}, \ldots, x_{n}\right\}$$ let $$\mu_{n}$$ be the empirical measure of the sample. For $$1 \leq p \leq \infty$$ and a function $$f,$$ put $$\|f\|_{L_{p}\left(\mu_{n}\right)}=\left(\frac{1}{n} \sum_{i=1}^{n}\left|f\left(x_{i}\right)\right|^{p}\right)^{1 / p}$$ and in particular, we have $$\|f\|_{L \infty\left(\mu_{n}\right)}=\max _{1 \leq i \leq n}\left|f\left(x_{i}\right)\right| .$$ Let $$N\left(\epsilon, \mathcal{F}, L_{p}\left(\mu_{n}\right)\right)$$ be the covering number of $$\mathcal{F}$$ at scale $$\epsilon$$ with respect to the norm $$L_{p}\left(\mu_{n}\right)$$ Theorem 9 - $$1 .$$ For any class $$\mathcal{F}$$ of real-valued functions, any sample $$S=\left\{x_{1}, \ldots, x_{n}\right\}$$ and $$\epsilon>0$$ $$N\left(\epsilon, \mathcal{F}, L_{1}\left(\mu_{n}\right)\right) \leq N\left(\epsilon, \mathcal{F}, L_{2}\left(\mu_{n}\right)\right) \leq N\left(\epsilon, \mathcal{F}, L_{\infty}\left(\mu_{n}\right)\right)$$ Definition. For $$\epsilon>0,$$ define the uniform covering number $$N_{p}(\epsilon, \mathcal{F}, n)=\sup _{\mu_{n}} N\left(\epsilon, \mathcal{F}, L_{p}\left(\mu_{n}\right)\right)$$

Now assume $$x_1, ..., x_n$$ are samples of some random variable $$x$$ and that we addionally observe some random variable $$z$$ with samples $$z_1, ..., z_n$$. Let $$z$$ and $$x$$ be (jointly) distributed according to $$\mu$$, and let $$\mu_n$$ be the corresponding empirical measure. Consider the linear projection $$T[f](z_i)=\mathbb{E}[f(x)|z=z_i]$$ and more generally the class $$T[\mathcal{F}]=\{T[f]=\mathbb{E}[f(x)|z=\cdot]: f\in\mathcal{F}\}$$.

Question: Can I bound $$\mathcal{N}_2(\epsilon, T[\mathcal{F}], n)\leq \mathcal{N}_\infty(\epsilon, \mathcal{F}, n)$$?

It's easy to see that that $$\mathcal{N}(\epsilon, T[\mathcal{F}], L_{p}\left(\mu\right))\leq \mathcal{N}(\epsilon, \mathcal{F}, L_{p}\left(\mu\right))$$, where $$\|f\|_{L_{p}\left(\mu\right)}=\left(\mathbb{E}\left|f\left(x\right)\right|^{p}\right)^{1 / p}$$ since we can easily compare $$\|T[f]\|_{L_{p}\left(\mu\right)}$$ and $$\|f\|_{L_{p}\left(\mu\right)}$$ via Jensen's inequality. However, $$\mathcal{N}(\epsilon, T[\mathcal{F}], L_{p}\left(\mu_n\right))\leq \mathcal{N}(\epsilon, \mathcal{F}, L_{p}\left(\mu_n\right))$$ should not be true in general, since $$\|T[f]\|_{L_{p}\left(\mu_{n}\right)}=\left(\frac{1}{n} \sum_{i=1}^{n}\left|\mathbb{E}[f\left(x\right)|z_i]\right|^{p}\right)^{1 / p}$$ cannot be directly compared to $$\|f\|_{L_{p}\left(\mu_{n}\right)}$$. Now I wonder whether the supremum in the definition of the uniform covering numbers is enough to make this upper bound work.