LFD Book Forum - View Single Post

BojanVujatovic · #3 07-14-2014, 06:29 PM

Quote:

Originally Posted by magdon

It is simpler to show that if $\ell$ takes on the value in the second part of the min, the condition in (b) is satisfied.

I have difficulties solving this problem. If I assume that $\ell=d_{VC} \log_2 d_{VC} + (d_{VC}+1) \log_2 K$ , then the condition in (b) $2^\ell>K\ell^{d_{VC}+1}$ is not satisfied.
(e.g. when $d_{VC}=2, K=2$ , then $\ell=5$ and $2^5=32 \ngtr 2 \cdot 5^3=250$ ).

I believe the right thing to do would be to assume that $\ell \geq d_{VC} \log_2 d_{VC} + (d_{VC}+1) \log_2 K$ because the min bound will still hold and I believe the condition in (b) is then satisfied? But how do I prove that?

I appreciate any help.