View Single Post
Old 10-22-2012, 11:54 PM
gah44 gah44 is offline
Invited Guest
Join Date: Jul 2012
Location: Seattle, WA
Posts: 153
Default Re: When the growth function = 2^N

Originally Posted by htlin View Post
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.
That is the way it always goes in theory.

In practice, we often don't have infinite N, and so it might be that in some cases exponential isn't so bad. There are plenty of NP hard problems that can, in fact, be solved for practical (small N) cases.
Reply With Quote