View Single Post
  #3  
Old 04-19-2012, 04:12 PM
htlin's Avatar
htlin htlin is offline
NTU
 
Join Date: Aug 2009
Location: Taipei, Taiwan
Posts: 601
Default Re: When the growth function = 2^N

Quote:
Originally Posted by timhndrxn View Post
Please elaborate a little bit more in the text why this is an issue. It is crucial that the bound be polynomial. So why is 2^N bad, but N^9999 good?
They are both bad for small N. But for large N, the exponentially decreasing term in Hoeffding would kill N^{9999} and provides us some guarantee on learning. Hope this helps.
__________________
When one teaches, two learn.
Reply With Quote