#1




Why 2^N Makes Learning Unfeasible

#2




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. 
#3




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.

Thread Tools  
Display Modes  

