Problem 1. True or False

Decide whether the following statements are true or false. Justify your answers.

• If classifier A has smaller training error than classifier B, then classifier A will have smaller generalization (test) error than classifier B.
• The VC dimension is always equal to the number of parameters in the model.
• For non-convex problems, gradient descent is guaranteed to converge to the global minimum.

Problem 2. Multiple choice questions

Choose the correct answer and justify your answer.

(a) (20 pt) Which of the following is not a possible growth function m_H(N) for some hypothesis set? (1) 2^N

(2) 2 ^N (3) 1 (4) N² N + 2 (5) none of the other choices

Problem 3. Proximal Gradient Descent

Consider solving the following problem

,

w

where X R^nd is the feature matrix (each row is a feature vector), y Rⁿ is the label vector, kwk₁ := ^P_i |w_i| and > 0 is a constant to balance loss and regularization. This is known as the Lasso regression problem and our goal is to derive the proximal gradient method for solving this.

• (10 pt) The gradient descent algorithm cannot be directly applied since the objective function is nondifferentiable. Discuss why the objective function is non-differentiable.
• (30 pt) In the class we showed that gradient descent is based on the idea of function approximation. To form an approximation for non-differentiable function, we split the differentiable part and non-differentiable part. Let, as discussed in the gradient descent lecture we approximate g(w) by

.

In each iteration of proximal gradient descent, we obtain the next iterate (w_t+1) by minimizing the following approximation function:

w_t+1 = argming(w) + kwk₁. w

Derive the close form solution of w_t+1 given w_t,g(w_t),,. Whats the time complexity for one proximal gradient descent iteration?

1