Consider a binary classification problem (y {0,1}), where the iid examples

D={(x^(1), y^(1)),(x^(2), y^(2)), . . . ,(x^(N), y(^N))}are divided into two disjoint setsD(train)andD(val).

• Suppose you fit a modelhusing the training set,D(train), and then estimate its error using the validation set,D(val). If the size ofD(val)was 100 (i.e.|Dval|= 100), how confident are you the true error ofhis within 0.1 of its average error onD(val)?
• Repeat the previous question where now|Dval|= 200 (i.e you have 200 examples in your validation set).
• Now, suppose you fit two modelsh1andh2(both fit usingD(train)) and then you selected the model that had the smallest error on your validation set,D(val).

If|Dval|= 100, how confident are you that the model you selected is within 0.1 of its average error onDval?

In solving this problem, use the Hoeffding bound. An additional resource ishttps://www.cs.cmu.edu/~avrim/ML14/inequalities.pdf