Week 5

Throughout, \(\bfX\in\Rbb^{n\times d}\) has rank \(r\geq1\) and compact SVD \(\bfX=\sum_{i=1}^r\sigma_i\bfu_i\bfv_i^\top\), and \(\bfy\in\Rbb^n\). Let \(\lambda>0\), and let \(\widehat{\bftheta}_\lambda\) denote the ridge regression estimator \[ \widehat{\bftheta}_\lambda =\argmin_{\bftheta\in\Rbb^d}\Big\{\|\bfy-\bfX\bftheta\|_2^2+\lambda\|\bftheta\|_2^2\Big\}. \]

Problem 1

The ridge solution \(\widehat{\bftheta}_\lambda=(\bfX^\top\bfX+\lambda\bfI_d)^{-1}\bfX^\top\bfy\) requires solving a \(d\times d\) linear system. When there are many more features than observations (\(d\gg n\)), there is a better way! In this problem you will find a second formula that only requires an \(n\times n\) system.

  1. Show that \(\bfX\bfX^\top+\lambda\bfI_n\) is invertible.
  2. Show that \((\bfX^\top\bfX+\lambda\bfI_d)\bfX^\top=\bfX^\top(\bfX\bfX^\top+\lambda\bfI_n)\).
  3. Conclude that \[ \widehat{\bftheta}_\lambda=\bfX^\top(\bfX\bfX^\top+\lambda\bfI_n)^{-1}\bfy. \]
  4. A study measures the expression of \(d=10{,}000\) genes in each of \(n=100\) patients. Solving a \(k\times k\) linear system takes roughly \(k^3\) arithmetic operations. Roughly how many times faster is the formula of part 3 than the one from lecture?

Problem 2

It is tempting to choose \(\lambda\) by making the training error \(\|\bfy-\bfX\widehat{\bftheta}_\lambda\|_2^2\) as small as possible. This problem is a guided derivation of training error always prefers \(\lambda=0\), which shows that this never works. Let \(\bfP=\sum_{i=1}^r\bfu_i\bfu_i^\top=\bfU_r\bfU_r^\top\) be the orthogonal projection onto \(\Ccal(\bfX)\).

  1. Use ridge regression filters the singular values to show that the fitted values are \[ \bfX\widehat{\bftheta}_\lambda=\sum_{i=1}^r\frac{\sigma_i^2}{\sigma_i^2+\lambda}(\bfu_i^\top\bfy)\,\bfu_i. \]
  2. Show that \[ \bfy-\bfX\widehat{\bftheta}_\lambda =\sum_{i=1}^r\frac{\lambda}{\sigma_i^2+\lambda}(\bfu_i^\top\bfy)\,\bfu_i+(\bfy-\bfP\bfy). \]
  3. Conclude that \[ \|\bfy-\bfX\widehat{\bftheta}_\lambda\|_2^2 =\sum_{i=1}^r\Big(\frac{\lambda}{\sigma_i^2+\lambda}\Big)^2(\bfu_i^\top\bfy)^2+\|\bfy-\bfP\bfy\|_2^2, \] and that the training error never decreases as \(\lambda\) grows. Hint: What is \(\bfu_i^\top(\bfy-\bfP\bfy)\)?
  4. Find the limits of the training error as \(\lambda\to0^+\) and as \(\lambda\to\infty\), and interpret each.

Problem 3

Ridge regression was defined with a penalty, but it can also be read as least squares with a budget on the size of the coefficients. Let \(\bftheta^\dagger=\sum_{i=1}^r\frac{\bfu_i^\top\bfy}{\sigma_i}\bfv_i\) be the minimum-norm least squares solution.

  1. Use ridge regression filters the singular values to show that \[ \|\widehat{\bftheta}_\lambda\|_2^2=\sum_{i=1}^r\frac{\sigma_i^2}{(\sigma_i^2+\lambda)^2}(\bfu_i^\top\bfy)^2. \] Conclude that \(\|\widehat{\bftheta}_\lambda\|_2\) never increases as \(\lambda\) grows, and that \(\|\widehat{\bftheta}_\lambda\|_2\leq\|\bftheta^\dagger\|_2\).
  2. Let \(t=\|\widehat{\bftheta}_\lambda\|_2\). Show that \(\widehat{\bftheta}_\lambda\) solves the constrained problem \[ \min_{\bftheta\in\Rbb^d}\|\bfy-\bfX\bftheta\|_2^2 \quad\text{subject to}\quad \|\bftheta\|_2\leq t. \] Hint: If \(\|\bftheta\|_2\leq t\), compare the ridge objective at \(\bftheta\) and at \(\widehat{\bftheta}_\lambda\).
  3. Combine parts 1 and 2 with Problem 2 to describe, in a sentence or two, what happens to the budget \(t\) and to the training error as \(\lambda\) increases from \(0\) to \(\infty\).

Problem 4

For least squares with \(\operatorname{rank}(\bfX)=d\), the fit uses \(d\) parameters. Ridge regression also has \(d\) coefficients, but implicity adds the information that we should be ‘shrinking’ them. In theory, therefore, it should count as fitting “fewer” parameters. Let’s make that precise! \[ \bfH_\lambda=\bfX(\bfX^\top\bfX+\lambda\bfI_d)^{-1}\bfX^\top\in\Rbb^{n\times n}, \] so that the ridge fitted values are \(\widehat{\bfy}=\bfX\widehat{\bftheta}_\lambda=\bfH_\lambda\bfy\).

  1. Show that \[ \bfH_\lambda=\sum_{i=1}^r\frac{\sigma_i^2}{\sigma_i^2+\lambda}\,\bfu_i\bfu_i^\top. \]
  2. Let’s define the effective degrees of freedom for ridge regression as \(\operatorname{df}(\lambda)=\operatorname{tr}(\bfH_\lambda)\). Show that \[ \operatorname{df}(\lambda)=\sum_{i=1}^r\frac{\sigma_i^2}{\sigma_i^2+\lambda}. \] Moreover, show that \(\operatorname{df}\) is strictly decreasing in \(\lambda\), and that \(\operatorname{df}(\lambda)\to r\) as \(\lambda\to0^+\) and \(\operatorname{df}(\lambda)\to0\) as \(\lambda\to\infty\). What matrix does \(\bfH_\lambda\) approach as \(\lambda\to0^+\)?
  3. Suppose \(d=3\) and \(\bfX\) has singular values \(10\), \(1\), and \(0.1\). Compute \(\operatorname{df}(1)\). Roughly how many parameters is ridge regression with \(\lambda=1\) “really” fitting, and which directions \(\bfv_i\) does it keep?