Clarification on VC bound
 

Hi,
I would like to request a little clarification on the VC bound from Lecture 6. For the slide entitled "What to do about Eout?", I understand that the Ein and Ein' both track Eout, although more loosely than Ein on just one sample. But I don't understand why having the Ein on two samples (Ein and Ein') allows us to characterize them in terms of dichotomies. What is so special about 2 samples (why not 1 or 3?)? Is this something that becomes clear in the proof (which I haven't looked at yet) or is this something that can be understood conceptually?

Sorry I wasn't able to ask this question in the Q&A but it is not practical for me to follow the lectures live.

Thanks a lot.

Re: Clarification on VC bound
 

The two samples are a technical trick that allows us to consider the dichotomies on a finite sample of data points ( of them), while still capturing the fact that with multiple hypotheses, the Hoeffding-type bounds become looser and looser. This gives us a concrete way of accounting for the overlaps in terms of a combinatorial quantity rather than full probabilistic analysis of dependence between events.

Having said that, what I did in the lecture was only a sketch of the proof to underline the main ideas in the formal proof. To pin it down completely, there is really no alternative to going through the formal proof which appears in the Appendix. It is not that hard, but certainly not trivial.

Re: Clarification on VC bound
 

So the proof is only available in the coursebook?

Re: Clarification on VC bound
 

There are different versions of the VC inequality and its proof in the literature. The version in the book follows the logic and notation I used in the lecture.

Re: Clarification on VC bound
 

I have a question regarding a statement made in the textbook. On page 51 in the second paragraph, it is said that the m_H grows logarithmically with N and so is crushed by the factor 1/N. First, igiven that (from page 50) m_H is bounded from above by N^d_vc + 1, how is it true that m_H grows logarithmically with N? Second, is the crushed part of the statement saying that a function that is of the form f1=log(N) is dominated by a function f2=1/x in the sense that f1/f2 tends to zero as N tends to infinity?

Thanks for your help in clarifying this point.

Re: Clarification on VC bound
 

The growth function grows polynomially, but the generalization bound has a logarithm in it, and the logarithm of a polynomial grows at a logarithmic rate itself, and hence gets crushed by the linear denominator. It is essentially the same as a polynomial getting crushed by a negative exponential, with the only difference being that we went into a logarithmic scale for both.