Stanford UniversitySTATS 231hw0-solutions

Homework 0 solutions CS229T/STATS231 1. Linear algebra (0 points) a (dual norm of L1 norm) The L1 norm k · k1 of a vector v 2 Rn is defined as kvk1 = nX i =1 jvij: (1) The dual norm k · k∗ of a norm k · k is defined as kvk∗ = sup kwk≤1 (v · w): (2) Compute the dual norm of the L1 norm. (Here v · w denotes the inner product between v and w: v · w , Pn i=1 viwi) Solution: We will prove that sup kwk1≤1 (v · w) = max i2[n] vi = kvk1 (3) which implies that the dual norm of L1 norm is L1 norm. Towards proving (3), we first observe that v · w = nX i =1 viwi ≤ nX i =1 jvij · jwij (4) ≤ nX i =1 kvk1 · jwij (5) = kvk1kwk1 (6) (7) Therefore, sup kwk1≤1 (v · w) ≤ kvk1 (8) 1We argue equality can be attained: let i? be such that vi? = arg maxi jvij = kvk1, then setting w = ei? (where ei denotes the vector with 1 on the i-th coordinate and 0 elsewhere) gives (v · w) = kvk1. Thus we complete the proof of equation (3). Remarks: dual norms are useful to bound inner products: u · v ≤ kukkvk∗, which follows directly from the definition of the dual norm. This is a generalization of the Cauchy-Schwartz inequality (which is for the L2 norm). In general, the Lp norm and the Lq norm are dual when 1=p + 1=q = 1. b (trace is sum of singular values) The nuclear norm of a matrix A 2 Rn×n is defined as Pn i=1 jσi(A)j, where the σ1(A); : : : ; σn(A) are the singular values of A. Show that the nuclear norm of a symmetric positive semi-definite matrix A is equal to its trace (tr(A) = Pn i=1 Aii). (For this reason, the nuclear norm is sometimes called the trace norm.) (Hint: use the fact that tr(AB) = tr(BA).) Solution: As A is PSD, the SV D of A has the form A = USU>. Using the trace rotation trick, tr(A) = tr(USU>) = tr(U>US) = tr(IS) = X i σi(A) = X i jσi(A)j: (9) The last equality used that singular values are non-negative. c. (3 bonus points) (trace is bounded by nuclear norm) Show that the trace of a square matrix A 2 Rn×n is always less than or equal to its nuclear norm. Solution: Suppose the SVD decomposition of A is A = UΣV >. Using the trace rotation trick, tr(A) = tr(V >UΣ) (10) Let R = V >U. Let Ui and Vi denote the i-th column of U and V respectively. Since Ui and Vi are unit vectors by the property of SVD, we have jRiij = j hUi; Vii j ≤ 1. Therefore, tr(A) = tr(RΣ) = nX i =1 RiiΣii (because Σ is a diagonal matrix) ≤ nX i =1 jΣiij (because jRiij ≤ 1) = kAk? Remark: The equality is achieved when the left and right singular subspaces are aligned (Ui = Vi) | which is exactly the case in part (b). SVD is generally a very powerful tool to deal with various linear algebraic quantities. 22. Subgradients of loss functions (0 points) Consider the prediction problem of mapping some input x 2 Rd to output y (in regression, we have y 2 R; in classification, we have y 2 f−1; +1g). A linear predictor is governed by a weight vector w 2 Rd, and we typically wish to choose w to minimize the cumulative loss over a set of training examples. Two popular loss functions for classification and regression are defined (on a single example (x; y)) as follows: • Squared loss: ‘(w; x; y) = 12(y − w · x)2. • Hinge loss: ‘(w; x; y) = maxf1 − yw · x; 0g. Let’s study some properties of these loss functions. These will be used throughout the entire class, so it’s important to obtain a good intuition for them. a (convexity of loss functions) Show that each of the two loss functions is convex. Hint: whenever possible, use the compositional properties of convexity (i.e., sum of two convex functions is convex, etc.). Solution: (Squared loss). First, the function g(t) = 12t2 is convex since g00(t) = 1 ≥ 0. Recall the following composition property of convexity: if a function g(t) is convex, so is the function f(w) = g(a>w + b). In other words, composition of a convex function with an affince mapping is still convex. Consequently, ‘(w; x; y) = g(y−w·x) is convex. (Hinge loss). First, the function g(t) = max(t; 0) is convex, as it is the supremum of two linear functions (i.e. g1(t) = t and g2(t) = 0. ) Since ‘(w; x; y) = g(1 − yw · x) is an affine mapping of g(t), we can conclude that ‘(w; x; h) is convex. b (subgradients of loss functions) Compute the subgradient of each of the two loss functions with respect to w. Recall that the subgradient of a convex function f(w) at a point w, denoted @f(w), is the set