Thread: Question 2
View Single Post
Old 04-14-2013, 02:57 PM
yaser's Avatar
yaser yaser is offline
Join Date: Aug 2009
Location: Pasadena, California, USA
Posts: 1,478
Default Re: Question 2

Originally Posted by sptripathi View Post
In pocket PLA, we always choose the hypothesis which gave min-disagreement across experiments(~ bins). The probability of bad-event in pocket case is still bound by hoeffdings inequality, right ?
It is bounded by the multiple-bin version of Hoeffding inequality. If we apply that version of the inequality directly to this case, the result will be meaningless since there is an infinite number of bins (hypotheses) in this case. This is the reason we will develop the theory further in the coming two weeks; to deal with this dilemma.

The possible difference I can see is that in Cmin case, sample kept changing, while in pocket case sample does not change, only color of marbles inside-bin and outside bin changes, as the hypothesis changes.
Your observation is correct, and this is why we used the union bound which is valid for all cases regardless of the dependence or independence of the samples.
Where everyone thinks alike, no one thinks very much
Reply With Quote