LFD Book Forum

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 07:56 AM

Why 2^N Makes Learning Unfeasible
I was going to ask what was wrong with 2^N growth function since 2^Ne^{-N}\rightarrow 0 but I think I figured it out:
The right hand side of the modified Hoeffding is really 2^{2N}/e^{\epsilon^2N/8} which goes to 0 only if 2^2/e^{\epsilon^2/8}<1, which would require \epsilon>3.3 which is meaningless since Ein and Eout are between 0 and 1.
Is this argument correct?

Michael Reach 04-21-2013 08:02 AM

Re: Why 2^N Makes Learning Unfeasible
I think that's right. You want to be able to make \epsilon 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 08:51 PM

Re: Why 2^N Makes Learning Unfeasible
If M=2^N, then you'd have 2\left(\frac{2}{e^{\varepsilon^2}}\right)^N on the right hand side. Any value of \varepsilon 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 11:18 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.