View Single Post
Old 04-06-2013, 01:40 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Is the Hoeffding Inequality really valid for each bin despite non-random sampling

Originally Posted by scottedwards2000 View Post
Actually, now that I re-read 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.
Where everyone thinks alike, no one thinks very much
Reply With Quote