Page 281 - Understanding Machine Learning
P. 281
21.7 Exercises 263
that for every round t, the prediction of the algorithm is based on a hypothesis
h t : X →{0,1}. Show that
M A (H)
E[L D (h r )] ≤ ,
T
where the expectation is over the random choice of the instances as well as a ran-
dom choice of r according to the uniform distribution over [T ].
Hint: Use similar arguments to the ones appearing in the proof of Theorem 14.8.
