COMP6211E Assignment 1 Solved

Description

Theoretical Problems 

1.  Let 4, where x ∈R^d. Find its conjugate f^∗(x).
2.  Let x ∈R and y ∈R+. Is f(x,y) = x²/y a convex function? Prove your claim.
3.  Consider the convex set C = {x ∈R^d : kxk_∞ ≤ 1}. Given y ∈R^d, compute the projection proj_C(y).
4.  Compute ∂f(x) for the following functions of x ∈R^d
   • f(x) = kxk₂
   • f(x) = 1(kxk_∞ ≤ 1)
   • f(x) = kxk₂ + kxk_∞
5. Consider the square root Lasso method. Given X ∈ R^n×d and y ∈ Rⁿ, we want to find w ∈R^d to solve

 ,                                                              (1)

subject to ξ_j ≥ w_j,           ξ_j ≥−w_j                  (j = 1,…,d).                                            (2)

Lasso produces sparse solutions. Define the support of the solution as

S = {j : w_∗,j 6= 0}.

Write down the KKT conditions under the assumption that Xw_∗ 6= y. Simplify in terms of S,X_S,X_S¯,y,w_S. Here X_S contains the columns of X in S, X_S¯ contains the columns of X not in S, and w_S contains the nonzero components of w_∗.

Programming Problem 

We consider ridge regression problem with randomly generated data. The goal is to implement gradient descent and experiment with different strong-convexity settings and different learning rates.

• Use the python template “prog-template.py”, and implement functions marked with ’# implement’.
• Submit your code and outputs. Compare to the theoretical convergence rates in class, and discuss your experimental results.

1