3.10 Rademacher complexity of prediction vector. Let S = (x1; : : : ; xm) be a sample of size m and x h: X ! R.

(a) Denote by u the vector of predictions of h for S: u =

 h(x1) ...

h(xm)



. Give an upper bound on the empirical Rademacher complexity bR S(H) of H =

fh;????hg in terms of kuk2 (Hint: express bR S(H) in terms of the expectation of an absolute value and apply Jensen's inequality). Suppose that h(xi) 2 f0;????1; +1g for all i 2 [m]. Express the bound on the Rademacher complexity in terms of the sparsity measure n = jfi j h(xi) 6= 0gj. What is that upper bound for the extreme values of the sparsity measure?

(b) Let F be a family of functions mapping X to R. Give an upper bound on the empirical Rademacher complexity of F + h = ff + h: f 2 Fg and that of F  h = (F + h) [ (F ???? h) in terms of bR S(F) and kuk2.