The problem, though an overestimate seems correct.
Hint: If you have
points, then
can implement at most
dichotomies on those points. Now try to upper bound the number of dichotomies that all
hypothesis sets can implement on these
points and proceed from there.
Quote:
Originally Posted by vsthakur
The problem says,
(b) Suppose that satisfies . Show that .
I suppose it should say,
(b) Suppose that satisfies . Show that .
If this is indeed the case, then can you please clarify part (c) as well.
Thank you,
Vishwajeet.
