LFD Book Forum (http://book.caltech.edu/bookforum/index.php)
-   Homework 3 (http://book.caltech.edu/bookforum/forumdisplay.php?f=132)
-   -   Why 2^N Makes Learning Unfeasible (http://book.caltech.edu/bookforum/showthread.php?t=4228)

 nkatz 04-21-2013 06:56 AM

Why 2^N Makes Learning Unfeasible

I was going to ask what was wrong with growth function since but I think I figured it out:
The right hand side of the modified Hoeffding is really which goes to 0 only if , which would require which is meaningless since Ein and Eout are between 0 and 1.
Is this argument correct?

 Michael Reach 04-21-2013 07:02 AM

Re: Why 2^N Makes Learning Unfeasible

I think that's right. You want to be able to make small.

Note that this doesn't mean that learning is not feasible, only that this inequality won't help you prove that it is. There might be some other way to bound growth. The professor already hinted that there are sometimes more ways, based on an "average" growth function that works for "most" cases.

 jlaurentum 04-21-2013 07:51 PM

Re: Why 2^N Makes Learning Unfeasible

If , then you'd have on the right hand side. Any value of that makes the exponential denominator smaller than the numerator of 2 would make the whole expression bigger than 2, which is meaningless for a probabilistic bound. The case in point, any epsilon smaller than 0.83 makes this upper hoeffding bound useless. Of course, 0.83 is an useless value for epsilon because you want to be able to make epsilon as close to 0 as you want.

 All times are GMT -7. The time now is 05:50 PM.