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

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?

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