Quote:
Originally Posted by htlin
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. |
That is the way it always goes in theory.
In practice, we often don't have infinite
, 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
) cases.