bracketing number vs covering number

Question

Just want to double check if the lemma on page 9 of this slides is correct: http://www.math.leidenuniv.nl/~avdvaart/talks/09hilversum.pdf

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

Proof: If $f$ is in the $2\epsilon$-bracket $[l,u]$, then it is in the ball of radius $\epsilon$ around $(l+u)/2$.

I think what the proof means is that, if 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$. Since there may be other sets of balls of radius $\epsilon$ that can cover $\cal F$, the covering number is no larger that the bracketing number.

I haven't found the same conclusion in any textbook I can find so far (not sure if it is because this conclusion is much too trivial), so I am not quite confident to say if it is right or wrong. I'd really appreciate it if anyone can enlighten me!!

Answer 1

Your elaboration is essentially right, except the brackets themselves are not $\|\cdot\|$-balls.

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.$$

Thus a cover of $2\epsilon$-brackets can be replaced by a cover of larger $\epsilon$-$\|\cdot\|$-balls of the same cardinality.

Answer 2

$$ \begin{aligned} \|f - (l+u)/2\| & = \| (f - l)/2 - (u - f)/2 \| \\ & \le \max \left\{ \frac{1}{2} \|f-l\| ,\frac{1}{2} \|u - f\| \right\}\\ & \le \frac{1}{2} \|u-l\| \\ &\le\epsilon. \end{aligned}$$ since $(f - l)/2 \ge 0$ and $(u - f)/2 \ge 0$.

Answer 3

Since my reputation is too low I could not add a comment. However, I recently met with this problem when I was reading Van der Vaart& Wellner (1996). According to this book, a hidden assumption for @angryavian's answer to hold is that the norm must satisfy the Riesz property ($L_r(Q)$-norms do possess this property), i.e., $$ |f| \le |g| \Rightarrow \|f\| \le \|g\|. $$ so that $$ \begin{aligned} |f - l| \le |u - l| &\Rightarrow \|f - l\| \le \|u - l\| \\ |f - u| \le |u - l| &\Rightarrow \|f - u\| \le \|u - l\| \end{aligned} $$

I hope this could serve as a supplement.