HW4, Question 1

[stordoff]

For the VC bound, we have a m_H(2N) term. Should this be replaced with (2N)^dvc, or merely N^dvc?

I presume the former, but both give answers around 400,000-500,000, so confirmation would be useful.

[sakumar]

Originally Posted by stordoff

For the VC bound, we have a m_H(2N) term. Should this be replaced with (2N)^dvc, or merely N^dvc?

I presume the former, but both give answers around 400,000-500,000, so confirmation would be useful.

The VC Generalization bound is defined in terms of m_H(2N), so that's what I used. Specifically m_H(2N) <= (2N)^dvc + 1, so I substituted the Right hand term for m_H(2N).

[rodrigo]

I used the bound we derived in lecture 6: sum(i=0 to dvc, of N choose i ). This should yield a tighter bound on e as sum(i=0 to dvc of, N choose i ) <= (2N)^dvc

[yaser]

Originally Posted by rodrigo

I used the bound we derived in lecture 6: sum(i=0 to dvc, of N choose i ). This should yield a tighter bound on e as sum(i=0 to dvc of, N choose i ) <= (2N)^dvc

I take it you used since you are evaluating the growth function at .

[rodrigo]

Originally Posted by yaser

I take it you used since you are evaluating the growth function at .

Yes indeed! On my previous post I was referring to how one can substitute mH(N), as shown on lecture 6. But reading through the thread again I can see how that may have been misleading given the context.

Thanks professor.