View Single Post
Old 02-07-2013, 12:45 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
Thanks for responding. I think I see what you mean. However, I think it does impact the independence of those individual H. Inequalities. As a simple example, using the perceptron, imagine that your sample picks points that are very close together. This means that they are more likely than disperse points to be either all correctly classified together or all misclassified together. Therefore it would seem that the chance of at least one error bound being validated goes up, as compared to picking a separate sample for each bin (which is like the coin experiment you had us do). But I guess you deal with this by using the union bound right? Thanks again!
Correct. The behavior of each sample is indeed dependent on the other bin samples, but the Hoeffding inequality is valid for each bin by itself, and the union bound is valid whether they are independent or dependent.
Where everyone thinks alike, no one thinks very much
Reply With Quote