LFD Book Forum Is the Hoeffding Inequality really valid for each bin despite non-random sampling?
 Register FAQ Calendar Mark Forums Read

#1
01-31-2013, 12:57 AM
 scottedwards2000 Junior Member Join Date: Jan 2013 Posts: 9
Is the Hoeffding Inequality really valid for each bin despite non-random sampling?

The multiple bin analogy of picking the best h is a very helpful way of visualizing the situation, and I totally get how the union bound sets an upper limit on the probability of exceeding the error threshold. What I am actually questioning is whether those individual probabilities that compose the union bound are correct. I can see that they are just the individual Hoeffding Inequalities for each h, but is the Hoeffding Inequality really valid for all those h's in spite of the fact that we are NOT taking random samples from each "bin"? We are only picking our marbles (x's) ONCE, and then re-picking the same marbles from each bin (yes, the red-green colors of those marbles can change, based on the specific h, but aren't they the same marbles (x's)?).