View Single Post
Old 04-26-2012, 06:33 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Clarification on VC bound

Originally Posted by View Post
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.
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.
Where everyone thinks alike, no one thinks very much
Reply With Quote