This note contains a reprise of the eigenvalue arguments to understand how variance is reduced by regularization. We also describe different ways regularization can occur including from the algorithm or initialization. This note contains some additional calculations from the lecture and Piazza, just so that we have typeset versions of them. They contain no new information over the lecture, but they do supplement the notes.

Recall we have a design matrix $X\in {\mathbb{R}}^{n\times d}$$X\in {\mathbb{R}}^{n\times d}$X inR^(n xx d)X \in \mathbb{R}^{n \times d} and labels $y\in {\mathbb{R}}^n$$y\in {\mathbb{R}}^n$y inR^(n)y \in \mathbb{R}^{n}. We are interested in the underdetermined case $n<d$$n<d$n < dn<d so that rank $(X)\le n<d$$(X)\le n<d$(X) <= n < d(X) \leq n<d. We consider the following optimization problem for least squares with a regularization parameter $\lambda \ge 0$$\lambda \ge 0$lambda >= 0\lambda \geq 0:

Computing derivatives as we did for the normal equations, we see that:

By setting ${\mathrm{\nabla }}_{\theta }\ell (\theta ,\lambda )=0$${\mathrm{\nabla }}_{\theta }\ell (\theta ,\lambda )=0$grad_(theta)ℓ(theta,lambda)=0\nabla_{\theta} \ell(\theta, \lambda)=0 we can solve for the $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta} that minimizes the above problem. Explicitly, we have:

To see that the inverse in Eq. 1 exists, we observe that $X^{T}X$$X^{T}X$X^(T)XX^{T} X is a symmetric, real $d\times d$$d\times d$d xx dd \times d matrix so it has $d$$d$dd eigenvalues (some may be $0$$0$00). Moreover, it is positive semidefinite, and we capture this by writing eig $\left(X^{T}X\right)=\{{\sigma }_1^2,\dots ,{\sigma }_d^2\}$$\left(X^{T}X\right)=\left\{{\sigma }_1^2,\dots ,{\sigma }_d^2\right\}$(X^(T)X)={sigma_(1)^(2),dots,sigma_(d)^(2)}\left(X^{T} X\right)=\left\{\sigma_{1}^{2}, \ldots, \sigma_{d}^{2}\right\}. Now, inspired by the regularized problem, we examine:

Since ${\sigma }_i^2\ge 0$${\sigma }_i^2\ge 0$sigma_(i)^(2) >= 0\sigma_{i}^{2} \geq 0 for all $i\in [d]$$i\in [d]$i in[d]i \in[d], if we set $\lambda >0$$\lambda >0$lambda > 0\lambda>0 then $X^{T}X+\lambda I$$X^{T}X+\lambda I$X^(T)X+lambda IX^{T} X+\lambda I is full rank, and the inverse of $(X^{T}X+\lambda I)$$\left(X^{T}X+\lambda I\right)$(X^(T)X+lambda I)\left(X^{T} X+\lambda I\right) exists. In turn, this means there is a unique such $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta}.

Recall that in bias-variance, we are concerned with the variance of $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta} as we sample the training set. We want to argue that as the regularization parameter $\lambda$$\lambda$lambda\lambda increases, the variance in the fitted $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta} decreases. We won't carry out the full formal argument, but it suffices to make one observation that is immediate from Eq. 1: the variance of $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta} is proportional to the eigenvalues of ${(X^{T}X+\lambda I)}^{-1}$${\left(X^{T}X+\lambda I\right)}^{-1}$(X^(T)X+lambda I)^(-1)\left(X^{T} X+\lambda I\right)^{-1}. To see this, observe that the eigenvalues of an inverse are just the inverse of the eigenvalues:

Now, condition on the points we draw, namely $X$$X$XX. Then, recall that randomness is in the label noise (recall the linear regression model $y\sim X{\theta }^{\ast }+$$y\sim X{\theta }^{\ast }+$y∼Xtheta^(**)+y \sim X \theta^{*}+ $\mathcal{N}(0,{\tau }^{2}I)=\mathcal{N}(X{\theta }^{\ast },{\tau }^{2}I))$$\left.\mathcal{N}\left(0,{\tau }^{2}I\right)=\mathcal{N}\left(X{\theta }^{\ast },{\tau }^{2}I\right)\right)${:N(0,tau^(2)I)=N(Xtheta^(**),tau^(2)I))\left.\mathcal{N}\left(0, \tau^{2} I\right)=\mathcal{N}\left(X \theta^{*}, \tau^{2} I\right)\right).

Recall a fact about the multivariate normal distribution:

Using linearity, we can verify that the expectation of $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta} is

The last line above suggests that the more regularization we add (larger the $\lambda$$\lambda$lambda\lambda), the more the estimated $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta} will be shrunk towards $0$$0$00. In other words, regularization adds bias (towards zero in this case). Though we paid the cost of higher bias, we gain by reducing the variance of $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta}. To see this bias-variance tradeoff concretely, observe the covariance matrix of $\hat{\theta }$$\widehat{\theta }$hat(theta)\hat{\theta}:

Notice that the entire spectrum of the covariance is a decreasing function of $\lambda$$\lambda$lambda\lambda. By decomposing in the eigenvalue basis, we can see that actually $\mathbb{E}[\parallel \hat{\theta }-{\theta }^{\ast }{\parallel }^2]$$\mathbb{E}[\parallel \widehat{\theta }-{\theta }^{\ast }{\parallel }^2]$E[|| hat(theta)-theta^(**)||^(2)]\mathbb{E}[\|\hat{\theta}-\theta^{*}\|^{2}] is a decreasing function of $\lambda$$\lambda$lambda\lambda, as desired.

We show that you can initialize gradient descent in a way that effectively regularizes undetermined least squares-even with no regularization penalty $(\lambda =0)$$(\lambda =0)$(lambda=0)(\lambda=0). Our first observation is that any point $x\in {\mathbb{R}}^d$$x\in {\mathbb{R}}^d$x inR^(d)x \in \mathbb{R}^{d} can be decomposed into two orthogonal components $x_0,x_1$$x_0,x_1$x_(0),x_(1)x_{0}, x_{1} such that

Recall that $\mathrm{Null}(X)$$\mathrm{Null}(X)$Null(X)\operatorname{Null}(X) and $\mathrm{Range}\left(X^T\right)$$\mathrm{Range}\left(X^T\right)$Range(X^(T))\operatorname{Range}\left(X^{T}\right) are orthogonal subspaces by the fundamental theory of linear algebra. We write $P_0$$P_0$P_(0)P_{0} for the projection on the null and $P_1$$P_1$P_(1)P_{1} for the projection on the range, then $x_0=P_0(x)$$x_0=P_0(x)$x_(0)=P_(0)(x)x_{0}=P_{0}(x) and $x_1=P_1(x)$$x_1=P_1(x)$x_(1)=P_(1)(x)x_{1}=P_{1}(x).

If one initializes at a point $\theta$$\theta$theta\theta then, we observe that the gradient is orthogonal to the null space. That is, if $g(\theta )=X^T(X\theta -y)$$g(\theta )=X^T(X\theta -y)$g(theta)=X^(T)(X theta-y)g(\theta)=X^{T}(X \theta-y) then $g^T{P}_0(v)=0$$g^T{P}_0(v)=0$g^(T)P_(0)(v)=0g^{T} P_{0}(v)=0 for any $v\in {\mathbb{R}}^d$$v\in {\mathbb{R}}^d$v inR^(d)v \in \mathbb{R}^{d}. But, then:

That is, no learning happens in the null. Whatever portion is in the null that we initialize stays there throughout execution.

A key property of the Moore-Penrose pseudoinverse, is that if $\hat{\theta }={\left(X^{T}X\right)}^{+}{X}^{T}y$$\widehat{\theta }={\left(X^{T}X\right)}^{+}{X}^{T}y$hat(theta)=(X^(T)X)^(+)X^(T)y\hat{\theta}=\left(X^{T} X\right)^{+} X^{T} y then $P_0(\hat{\theta })=0$$P_0(\widehat{\theta })=0$P_(0)( hat(theta))=0P_{0}(\hat{\theta})=0. Hence, the gradient descent solution initialized at ${\theta }_0$${\theta }_0$theta_(0)\theta_{0} can be written $\hat{\theta }+P_0\left({\theta }_0\right)$$\widehat{\theta }+P_0\left({\theta }_0\right)$hat(theta)+P_(0)(theta_(0))\hat{\theta}+P_{0}\left(\theta_{0}\right). Two immediate observations:

We've argued that there are many ways to find equivalent solutions, and that this allows us to understand the effect on the model fitting procedure as regularization. Thus, there are many ways to find that equivalent solution. Many modern methods of machine learning including dropout and data augmentation are not penalty, but their effect is understood as regularization. One contrast with the above methods is that they often depend on some property of the data or for how much they effectively regularization. In some sense, they adapt to the data. A final comment is that in the same sense above, adding more data regularizes the model as well!