View Single Post
Old 02-07-2013, 10:49 AM
scottedwards2000 scottedwards2000 is offline
Junior Member
Join Date: Jan 2013
Posts: 9
Default Re: Is the Hoeffding Inequality really valid for each bin despite non-random sampling

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!
Reply With Quote