Thread: Discussion of the VC proof View Single Post
#19
10-26-2016, 04:23 AM
 CountVonCount Member Join Date: Oct 2016 Posts: 17
Re: Discussion of the VC proof

Hi,

I have a question about the sentence on page 190:
Quote:
 Note that we can assume e^(-0.5*N*eps^2) < 1/4, because otherwise the bound in Theorem A.1 is trivially true.
While I understand the argument here, I don't understand, why it is especially the value 1/4?
When set the above term to 1/4 I will receive -2*ln(1/4) as value for N*eps^2.
Now I can set N*eps^2 to that value in Theorem A.1 and I will get on the RHS (assuming the growth function is just 1) 4*0,707... so it is much more than 1.

A value of 1 in the RHS would be sufficient to say the bound in Theorem A.1 is trivially true. And this would assume, that the above term is less than 1/256.
With this in mind 1 - 2*e^(-0.5*N*eps^2) is greater than 0,99... and thus instead of a 2 in the lemmas outcome, I would receive a value around 1, which is a much better outcome.

So why is the value 1/4 chosen for the assumption?

Best regards,
André