Quote:
Originally Posted by sptripathi
In pocket PLA, we always choose the hypothesis which gave mindisagreement across experiments(~ bins). The probability of badevent in pocket case is still bound by hoeffdings inequality, right ?

It is bounded by the
multiplebin 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.
Quote:
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 insidebin 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.