Covering number of the conditional distribution function

Question

Suppose $Y$ is a random variable in $\mathbb{R}^d$, and we want to find the covering number \begin{equation*} \mathcal{F} = \big\{ F_{Y|W} (y | W) : y \in \mathbb{R}^d \big\} \end{equation*} where $W$ is another random variable in $\mathbb{R}^k$ and $F_{Y|W} (y | W)$ is the conditional distribution function. Denote $P_{Y, W}$ is the law of $(Y, W)$, what we want to find is the covering number $N(\epsilon, \mathcal{F}, L_2(P_{Y, W}))$.

At the first glimpse, this question is quite simple, since if we treat $W$ as a determined number, then \begin{equation*} \mathcal{F} = \overline{\operatorname{conv}}(\mathcal{G}), \end{equation*} where $\mathcal{G} := \big\{ 1(Y \leq y) : y \in \mathbb{R}^d \big\}$ with $N(\epsilon, \mathcal{G}, L_2(P_{Y})) \lesssim \epsilon^{- 2d}$ (This is because $F_{Y|W} (y | W) : \mathbb{R}^d \rightarrow [0, 1]$ is a distribution function). Then by the result for convex hulls, we have \begin{equation*} \log N \big( \epsilon, \mathcal{F}, L_2 (P_Y)\big) \lesssim \epsilon^{-2 d/ (d + 1)}. \end{equation*}

However, I think the randomness of $W$ complex this problem: what we want is $N(\epsilon, \mathcal{F}, L_2(P_{Y, W}))$ rather than $N ( \epsilon, \mathcal{F}, L_2 (P_Y))$. And I try to find some articles about this, but it is proved to be futile.

So can anyone help me with this question. Thanks in advance!

Answer 1

You need a different approach. Each function in your function space can be written as $$F_{Y|W}(y|W) = \int 1(s \leq y) P(Y = ds|W)$$ for some $y$. Thus, $$\|F_{Y|W}(y_2|W) - F_{Y|W}(y_1|W)\|_{L^1} = E_{P_W}|F_{Y|W}(y_2|W) - F_{Y|W}(y_1|W)| \leq E_{P_W}\int 1(y_1 \leq s \leq y_2) P(Y = ds|W) \lessapprox \|1(Y \leq y_2) - 1(Y \leq y_1)\|_{L^1}.$$ A similar argument probably works for $L^2$. In particular, your function space is obtained by a Lipschitz transformation applied to the function space $$\mathcal{F}_{ind} = \{s \mapsto 1(s\leq y): y \in \mathbb{R}\}.$$ So your covering number is essentially that of $\mathcal{F}_{ind} $.