Thread: Question 2
View Single Post
Old 04-14-2013, 01:58 PM
sptripathi sptripathi is offline
Junior Member
Join Date: Apr 2013
Posts: 8
Default Re: Question 2

Originally Posted by yaser View Post
This is discussed here:

The main point is that once you consider the sample, the probability becomes conditional on how this sample came out, and that could violate the 2e^{-2\epsilon^2N} bound, whereas the probability before a sample was drawn always obeys the bound.
Is the Cmin coin of Q2 (HW2) not analogous to pocket PLA's final-hypothesis g ? 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 ?
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. Is that the key point?
Reply With Quote