Let F = {f1, . .., fN} with fi : R -+ {0, 1} for each i E [N]. Suppose X1, . .., Xn+1 are i.i.d. and Yt = f1(Xt) for each t E [n+1]. Prove that for all E, d E (0, 1) and n > log(N/S)/E, if n f ( arg min > If(Xt) # Ytl, fEF t=1 then P P[ f ( X n + 1 ) # Yn+ 1 | X 1, Y1 , . . . , Xn, Yn] Se| 21-8. Hint: f is probably not unique