3.7 Two function hypothesis class. Let H be a hypothesis set reduced to two functions:

H = fh????1; h+1g and let S = (x1; : : : ; xm)  X be a sample of size m.

(a) Assume that h????1 is the constant function taking value ????1 and h+1 the constant function taking the value +1. What is the VC-dimension d of H?

Upper bound the empirical Rademacher complexity bR S(H) (Hint: express bR S(H) in terms of the absolute value of a sum of Rademacher variables and apply Jensen's inequality) and compare your bound with p

d=m.

(b) Assume that h????1 is the constant function taking value ????1 and h+1 the function taking value ????1 everywhere except at x1 where it takes the value

+1. What is the VC-dimension d of H? Compute the empirical Rademacher complexity bR S(H).