View Single Post
Old 04-21-2013, 08:51 PM
jlaurentum jlaurentum is offline
Join Date: Apr 2013
Location: Venezuela
Posts: 41
Default 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.
Reply With Quote