Quote:
Originally Posted by scottedwards2000
Actually, now that I reread this part (I'm taking the course again!), I realize that I don't really follow this logic. Can you please expand on your last sentence above?

The sentence addresses the following concern. Hoeffding assumes a random sample from a bin. The different samples from multiple bins in the learning analogy are not "totally random" since they all depend on one sample of input points (which is random) but then all of them give red/geen values on that same sample according to the agreement/disagreement of their respective hypothesis with the target function.
The resolution of this dilemma is that while it is true, each bin in isolation sees the sample as random, and therefore each bin obeys Hoeffding inequality by itself. When we consider all the bins at once, it does not matter how they are correlated since we invoked the union bound which is always valid ragardless of the correlations.