Quote:
Originally Posted by timhndrxn
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
. But for large
, the exponentially decreasing term in Hoeffding would kill
and provides us some guarantee on learning. Hope this helps.