View Single Post
  #4  
Old 09-19-2015, 02:56 AM
yaser's Avatar
yaser yaser is offline
Caltech
 
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,476
Default Re: Hoeffding Inequality

Quote:
Originally Posted by henry2015 View Post
Thanks for your quick reply Professor!

Now, I wonder why "we cannot just plug in g for h in the Hoeffding inequality". Given g is one of h's and for each h, Hoeffding inequality is valid for the upper bound of P[|Ein(h) - Eout(h)| > E]. Even g is picked after we look at all the outputs of all h's, g is still one of h's. So Hoeffding inequality should be still valid for g. No?

Thanks!
This is the main point of this part. Take the coin flipping example, with each of 1000 fair coins flipped 10 times. Hoeffding applies to each coin, right? Now if we pick "g" to be the coin that produced the most heads, we lose the Hoeffding guarantee because the small probability of bad behavior for each coin accumulates into a not-so-small probability of bad behavior of some coin (which we picked deliberately because it behaved badly).
__________________
Where everyone thinks alike, no one thinks very much
Reply With Quote