HOMEWORK 3 – V0 Solution

Description

1. Rademacher Complexity and Massart’s lemma.

1.1. Symmetrization for concentration [10pts]. For Q2.3 in Assignment 2, obtain a similar concentration result using a symmetrization argument. The steps will be as follows.

1. Use McDiarmid’s inequality on the empirical process.

2. Find the Rademacher complexity of F, linear functions constrained in ‘₂-ball.

3. Use Talagrands contraction to bound R_n(f F).

1.2. Rademacher complexity of linear functions constrained in ‘-1 ball [10pts]. For i = f1:2; :::; ng. we assume that data points z_i, have bounded coordinates, i.e., kz_ik₁ = max_j jz_ijj almost surely. Find an upper bound on the Rademacher complexity of linear functions constrained in a ‘₁ ball of radius r, i.e.,

(1.1) F = ff : f(z) = h ; zi; k k₁ rg:

Compare your result to the Rademacher complexity of the ‘₂ ball.

Hint: Region de ned by the ‘₁ ball has corners at re_j where e_j is the j-th standard basis vector. Therefore, f : k k₁ rg = convex-hull([_jf re_jg). First, nd the Rademacher complexity of the union (which is nite so Massart’s lemma can help), then argue that this is equal to the complexity of the convex hull.

1.3. Generalization of binary classi cation [10pts]. In a binary classi cation problem, we have a dataset of n iid (x_i; y_i) feature-response pairs where x_i 2 R^d with kx_ik₁ and y_i 2 f 1; +1g. Learning task involves tting a function of the form f (x) = sign(h ; xi) where k k₁ r. We noticed that 0-1 loss function is not smooth; therefore, we use capped-hinge loss as a relaxation which is given as l((y; x); ) = minf2; maxf0; 1 yh ; xigg.

Derive a generalization bound for the empirical risk minimizer.

1.4. Course evaluation [5pts]. Did you complete the course evaluation for this course? Your answer should be yes or no, and there is only one correct answer. Hint: I would really appreciate your feedback on the course.

1