Thread: Problem 2.14(c)
View Single Post
Old 07-14-2014, 06:29 PM
BojanVujatovic BojanVujatovic is offline
Join Date: Jan 2013
Posts: 13
Default Re: Problem 2.14(c)

Originally Posted by magdon View Post
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.
Reply With Quote