3.9 Rademacher complexity of intersection of concepts. Let H1 and H2 be two families of functions mapping X to f0; 1g and let H = fh1h2 : h1 2 H1; h2 2 H2g. Show that the empirical Rademacher complexity of H for any sample S of size m can be bounded as follows:

bR S(H)  bR S(H1) + bR S(H2):

Chapter 3 Rademacher Complexity and VCDimension Hint: use the Lipschitz function x 7! max(0; x????1) and Talagrand's contraction lemma.
Use that to bound the Rademacher complexity Rm(U) of the family U of intersections of two concepts c1 and c2 with c1 2 C1 and c2 2 C2 in terms of the Rademacher complexities of C1 and C2.