Overview

• Linear Regression
• Regularized Linear Regression
• Demo

Linear Regression

• Linear regression, hypothesis class: $\mathcal{H}$
• $X \in \mathbb{R}^{mxd}$
• $J(\theta) = \sum |\theta^Tx_i-y_i|^2_2$
• $\nabla J(\theta) = 2\sum (\theta^Tx_i - y_i)x_i$

Closed Form

$\nabla J(\theta) = -2X^T(y-X\theta) = 0$

$2X^TX\theta = 2X^Ty$

$\theta = (X^TX)^{-1}X^Ty$

Regularized Linear Regression

$\tilde J(\theta) = \sum (\theta^Tx_i - y_i)^2 + \dfrac{\lambda}{2}||\theta||^2_2$

$\theta^* = (X^TX+\lambda I_d)^{-1}X^Ty$

If $X^TX$ is invertible, is $X^TX + \lambda I_d$ also invertible?

Yes, since $\mathrm{det}( X^TX - t I)$ is only 0 (and noninvertible) when $t$ is an eigenvalue of $X^TX$.