a6a767bbb2e3513233f942e0ff24272c-AuthorFeedback.pdf

In a nutshell: For any pointx, the "advantage" adv(x) is equal to pγ2, where there is a ball centered atx that34 has probability massp and has averagey-value that is either 12 +γ or 12 γ. Given only this information about35 x, in order to predictx's label correctly with constant probability, we needγ 2 points in the ball; thus we need36 Ω(1/(pγ2))=Ω(1/adv(x))datapointsoverall.37