# Covering numbers for products of functions from two spaces?

Exercise (HW1): Let $$\mathcal{F}$$ and $$\mathcal{G}$$ be classes of measurable function. Then for any probability measure $$Q$$ and any $$1 \leq r \leq \infty$$, (i) $$N_{[]}\left(2 \epsilon, \mathcal{F}+\mathcal{G}, L_{r}(Q)\right) \leq N_{[]}\left(\epsilon, \mathcal{F}, L_{r}(Q)\right) N_{[]}\left(\epsilon, \mathcal{G}, L_{r}(Q)\right)$$; (ii) provided $$\mathcal{F}$$ and $$\mathcal{G}$$ are bounded by 1 , $$N_{[]}\left(2 \epsilon, \mathcal{F} \cdot \mathcal{G}, L_{r}(Q)\right) \leq N_{[]}\left(\epsilon, \mathcal{F}, L_{r}(Q)\right) N_{[]}\left(\epsilon, \mathcal{G}, L_{r}(Q)\right)$$

This is the question. I need to proof part (ii) for my work.Assume those Ns are coverning numbers and not bracketing numbers as he considers

Reference. Question is taken from page 21,2nd HW1 part (ii)

I am getting no clue. Can anyone help me in this?

$$2.2$$ Bracketing numbers Let $$(\mathcal{F},\|\cdot\|)$$ be a subset of a normed space of real functions $$f: \mathcal{X} \rightarrow \mathbb{R}$$ on some set $$\mathcal{X}$$. We are mostly thinking of $$L_{r}(Q)$$-spaces for probability measures $$Q$$. We shall write $$N\left(\varepsilon, \mathcal{F}, L_{r}(Q)\right)$$ for covering numbers relative to the $$L_{r}(Q)$$-norm $$\|f\|_{Q, r}=\left(\int|f|^{r} d Q\right)^{1 / r}$$. Definition $$2.9$$ ( $$\varepsilon$$-bracket). Given two functions $$l(\cdot)$$ and $$u(\cdot)$$, the bracket $$[l, u]$$ is the set of all functions $$f \in \mathcal{F}$$ with $$l(x) \leq f(x) \leq u(x)$$, for all $$x \in \mathcal{X}$$. An $$\varepsilon$$-bracket is a bracket $$[l, u]$$ with $$\|l-u\|<\varepsilon$$.

Definition 2.10 (Bracketing numbers). The bracketing number $$N_{[]}(\varepsilon, \mathcal{F},\|\cdot\|)$$ is the minimum number of $$\varepsilon$$-brackets needed to cover $$\mathcal{F}$$.

Definition $$2.11$$ (Entropy with bracketing). The entropy with bracketing is the logarithm of the bracketing number.

In the definition of the bracketing number, the upper and lower bounds $$u$$ and $$l$$ of the brackets need not belong to $$\mathcal{F}$$ themselves but are assumed to have finite norms.

## 1 Answer

Given two functions $$l(\cdot)$$ and $$u(\cdot)$$, the bracket $$[l, u]$$ is the set of all functions $$f \in \mathcal{F}$$ with $$l(x) \leq f(x) \leq u(x)$$, for all $$x \in \mathcal{X}$$. An $$\varepsilon$$-bracket is a bracket $$[l, u]$$ with $$\|l-u\|<\varepsilon$$.

If $$[l,u]$$ is a $$2\epsilon$$-bracket, then it is contained in the $$\|\cdot\|$$-ball of radius $$\epsilon$$ centered at $$(l+u)/2$$, since $$l \le f \le u$$ implies $$\|f - (l+u)/2\| \le \frac{1}{2} \|f-l\| + \frac{1}{2} \|f - u\| \le \|u-l\| = \epsilon.$$

Hence $$N(\epsilon,\cal F,||\cdot||)\leq N_{[]}(2\epsilon,\cal F,||\cdot||).$$

This means a set of $$2\epsilon$$-brackets covers $$\cal F$$, then this set is also a set of balls of radius $$\epsilon$$ that can cover $$\cal F$$.

For any $$f\in \mathcal{F}$$ and $$g\in\mathcal{G}$$, we can find $$\epsilon-$$bracket $$[l_1, u_1]$$ and $$[l_2,u_2]$$ contain $$f$$ and $$g$$ respectively.

And the largest distance is \begin{align*} ||u_1u_2 - l_1l_2||_{Q,r} & = ||u_1u_2 - l_1u_2 + l_1u_2 - l_1l_2||_{Q,r}\\ & \le ||u_1u_2 - l_1u_2||_{Q,r} + ||l_1u_2 - l_1l_2||_{Q,r}\\ &\le 2\epsilon \end{align*}

So, $$N_{[]}(2\epsilon,\mathcal{F}\cdot\mathcal{G},L_{r}(Q))\leq N_{[]}(\epsilon,\mathcal{F},L_{r}(Q))N_{[]}(\epsilon,\mathcal{G},L_{r}(Q)).$$

Hence we can write,

So, $$N(\epsilon,\mathcal{F}\cdot\mathcal{G},||\cdot||)\leq N(\frac{\epsilon}{2},\mathcal{F},||\cdot||)N(\frac{\epsilon}{2},\mathcal{G},||\cdot||).$$

N.B:-

Sincere thanks to these answers

[I am new to this field, requesting experts to check the proof and give the feedback,TIA]

• This is a one-way inequality. This is obviously not enough to get the required inequality for covers from brackets. I guess one needs to prove the analogous homework for covers.
– XYZ
Commented Jul 13, 2022 at 10:30