Linear, Ridge and Lasso Regression

The normal equations as orthogonal projection, the exact bias and variance of ridge, and why the unbiased estimator is rarely the best one.

Classical MLCore⏱ 3 hours12 min readleast squaresnormal equationsridgelassoprojection

5 problems →

AssumesLinear Algebra for Machine Learning · Expectation, Variance and Conditional Expectation

Least squares

Given $X\in\R^{n\times p}$ with $\rank X = p$ and $y\in\R^n$ , minimise $L(\beta) = \tfrac12\norm{y - X\beta}_2^2$ .

TheoremNormal equations and the projection interpretation

$L$ is minimised uniquely at

\hat\beta = (X^\top X)^{-1}X^\top y,

characterised by the normal equations $X^\top(y - X\hat\beta)=0$ . The fitted values are $\hat y = X\hat\beta = Hy$ with $H = X(X^\top X)^{-1}X^\top$ the orthogonal projector onto $\operatorname{col}(X)$ , and the residual $y-\hat y$ is orthogonal to every column of $X$ .

Key idea

Least squares is projection; no calculus is needed. The normal equations are the statement "the residual is orthogonal to the model space", which is the projection theorem. Everything else — the Pythagorean decomposition of the sum of squares, the $R^2$ statistic, the geometry of ANOVA — follows from the same picture.

TheoremGauss–Markov theorem

Suppose $y = X\beta^\star+\varepsilon$ with $\E\varepsilon = 0$ and $\Cov(\varepsilon)=\sigma^2I_n$ . Then $\hat\beta$ is unbiased, $\Cov(\hat\beta) = \sigma^2(X^\top X)^{-1}$ , and for every other estimator of the form $\tilde\beta = Ay$ that is unbiased for all $\beta^\star$ ,

\Cov(\tilde\beta) \succeq \Cov(\hat\beta) .

Ridge regression

\hat\beta_\lambda = \argmin_\beta\left\{\frac{1}{2}\norm{y-X\beta}_2^2 + \frac{\lambda}{2}\norm\beta_2^2\right\}.

PropositionRidge in closed form and in the SVD basis

\hat\beta_\lambda = (X^\top X+\lambda I)^{-1}X^\top y ,

and if $X = U\Sigma V^\top$ is the SVD with singular values $\sigma_j$ , then

\hat\beta_\lambda = \sum_{j}\frac{\sigma_j}{\sigma_j^2+\lambda}\,\ip{u_j}{y}\,v_j, \qquad \hat y_\lambda = \sum_j \frac{\sigma_j^2}{\sigma_j^2+\lambda}\ip{u_j}{y}u_j .

The solution exists and is unique for every $\lambda>0$ , even when $\rank X<p$ .

Key idea

The shrinkage factor $\sigma_j^2/(\sigma_j^2+\lambda)$ is near $1$ for $\sigma_j^2\gg\lambda$ and near $0$ for $\sigma_j^2\ll\lambda$ . Ridge leaves the well-determined directions alone and suppresses the poorly-determined ones — precisely the directions where, by Marchenko–Pastur, the sample covariance is least trustworthy. The effective number of parameters is $\sum_j\sigma_j^2/(\sigma_j^2+\lambda)$ , continuously interpolating between $p$ at $\lambda=0$ and $0$ as $\lambda\to\infty$ .

TheoremThere is always a ridge parameter that beats least squares

Under the Gauss–Markov assumptions with $\rank X = p$ , define $m(\lambda) = \E\norm{\hat\beta_\lambda - \beta^\star}_2^2$ . Then $m$ is differentiable at $0$ with

m'(0) = -2\sigma^2\tr\big((X^\top X)^{-2}\big) < 0 ,

so $m(\lambda)<m(0)$ for all sufficiently small $\lambda>0$ .

Key idea

Read the two terms. Bias grows like $\lambda^2$ — second order — while variance falls like $\lambda$ — first order. So at $\lambda = 0$ there is always a free lunch, and the unbiased estimator is inadmissible in mean squared error. The effect is largest when some $\sigma_j$ is small, since the derivative scales as $\sigma_j^{-4}$ , which is exactly the ill-conditioned case. This computation is the regression counterpart of the shrinkage result on the covariance estimation page, and both are instances of the James–Stein phenomenon.

Ridge versus lasso

PropositionWhy lasso is sparse and ridge is not

Consider the orthogonal design $X^\top X = nI$ , where both problems decouple across coordinates. With $z = X^\top y/n$ ,

\hat\beta^{\text{ridge}}_j = \frac{z_j}{1+\lambda}, \qquad \hat\beta^{\text{lasso}}_j = \sign(z_j)\max\big(|z_j|-\lambda,\ 0\big) .

Ridge multiplies; lasso subtracts and truncates. Only the second can return exactly zero.

	Ridge	Lasso
Penalty	$\lambda\norm\beta_2^2$	$\lambda\norm\beta_1$
Closed form	yes	only for orthogonal design
Sparse	no	yes
Strictly convex objective	yes	no (unique solution not guaranteed)
Works when $p>n$	yes	yes
Rate under sparsity	$p/n$	$s\log p/n$
Prox operator	scaling	soft threshold

The rate comparison is the content of the lasso theorem: when the truth is sparse, lasso's $s\log p/n$ beats ridge's $p/n$ ; when it is dense, ridge wins.

Problems

Least squares as orthogonal projectionProof · Foundation · 15 min Prove the Gauss–Markov theoremProof · Intermediate · 30 min Ridge regression in the SVD basisProof · Intermediate · 30 min There is always a ridge parameter beating least squaresProof · Advanced · 1 hour Implement ridge and find the optimal lambdaCoding · Intermediate · 1 hour

References

BookTrevor Hastie, Robert Tibshirani and Jerome Friedman (2009). The Elements of Statistical Learning
PaperArthur E. Hoerl and Robert W. Kennard (1970). Ridge Regression: Biased Estimation for Nonorthogonal Problems
PaperRobert Tibshirani (1996). Regression Shrinkage and Selection via the Lasso

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

TheoremNormal equations and the projection interpretationproof includedThe least-squares fit is the orthogonal projection of y onto the column space of X.
TheoremGauss–Markov theoremproof includedAmong linear unbiased estimators, least squares has the smallest variance.
PropositionRidge regression in closed form and in the SVD basisproof includedRidge shrinks each singular direction by a factor depending on its singular value.
TheoremThere is always a ridge parameter that beats least squaresproof includedThe derivative of the mean squared error with respect to the ridge parameter is strictly negative at zero.
PropositionWhy lasso is sparse and ridge is notproof includedThe geometry of the l1 and l2 balls, and the closed forms of the two proximal operators.

Problems (5)

All problems

Least squares

Ridge regression

Ridge versus lasso

Problems

References

Results stated on this page

Problems (5)

Papers that use this mathematics