Problem 1: Suppose X = [0, 1] ⊆ R and H is the class of all predictors h : [0, 1] → {0, 1}. Suppose D is the uniform distribution over [0, 1]. Prove that there is some h∗ ∈ H and some ERM-strategy L such that for every ?nite sample set S for h∗ we obtain errD(hS) = 0.9, where hS is the hypothesis returned by L on S.
Problem 2: Can you think of stronger versions of the above claim? If yes, give one such claim and a reason. If no, give a reason as well. No formal proof required.