1
$\begingroup$

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!!

$\endgroup$
1
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.