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

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