
#1




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. 
#2




Re: Clarification on VC bound
Quote:
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.
__________________
Where everyone thinks alike, no one thinks very much 
#3




Re: Clarification on VC bound
So the proof is only available in the coursebook?

#4




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.
__________________
Where everyone thinks alike, no one thinks very much 
#5




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. 
#6




Re: Clarification on VC bound
Quote:
__________________
Where everyone thinks alike, no one thinks very much 
Thread Tools  
Display Modes  

