Ridge and Lasso Regression

Penalized least squares with full proofs. Why correlated inputs make least-squares coefficients unstable, read from the eigenvalues of X'X; the ridge estimator derived, its shrinkage of each principal direction and its effective degrees of freedom, the existence theorem of Hoerl and Kennard proved with an explicit range of penalties, ridge as a posterior mean, and its exact leave-one-out error; the lasso's optimality conditions proved, soft thresholding in the orthonormal case, unique fitted values, the piecewise-linear path and coordinate descent; all worked on the diabetes data, with the lasso path checked against least angle regression and seeded experiments on prediction and on the lasso's degrees of freedom. Worked problems solve ridge and the lasso by hand for two correlated inputs and find the best penalty in one direction.

In the diabetes study of Efron, Hastie, Johnstone and Tibshirani (2004), ten baseline measurements on 442 patients are used to predict a measure of disease progression one year later. Put all ten inputs on a common scale and fit them by least squares. The coefficient of S1 (total cholesterol) is $-37.7$ and that of S2 (LDL cholesterol) is $+22.7$, two large effects of opposite sign for two measurements whose correlation is 0.897. The standard error of the S1 coefficient is 19.8, and its variance inflation factor is 59.2 (39.2 for S2): the data say little about S1 separately from the other serum measurements. Can a deliberately biased estimate of the coefficients be more accurate than the unbiased least-squares one, and how should the bias be chosen?

Ridge regression and the lasso answer by adding a penalty on the size of the coefficients to the residual sum of squares. Ridge penalizes the sum of squared coefficients; it shrinks the coefficient vector toward zero and keeps every input. The lasso penalizes the sum of absolute values; it shrinks too, and sets some coefficients exactly to zero, so it also selects inputs. Both trade bias for variance, the tradeoff that The Bias-Variance Tradeoff measures by simulation and that Model Selection mentions as the continuous alternative to subset selection.

The route is as follows. First the source of the instability: the variance of least squares, read from the eigenvalues of $X^{\mathsf T}X$. Then ridge regression: its solution, its action on each principal direction of the inputs, its degrees of freedom, the theorem of Hoerl and Kennard that some amount of ridge always beats least squares, its Bayesian reading and its exact leave-one-out error. Then the lasso: the orthonormal case, where its soft thresholding can be seen whole, the optimality conditions that characterize it in general, the path of solutions and how coordinate descent computes it. Experiments on the diabetes data close the article. It assumes The Geometry of Least Squares and The Gauss–Markov Theorem, whose unbiasedness and covariance results the bias-variance calculation uses; Leverage, Influence and Residual Diagnostics supplies the leave-one-out algebra.

Notation and the data

The data are the 442 patients of the diabetes study, with the ten inputs age, sex, body mass index (BMI), average blood pressure (BP) and six serum measurements S1 to S6, as in Multiple Linear Regression, which also lists them. Every number on this page is computed by tools/experiments/statistics/ridge-and-lasso-regression.py.

Penalties compare coefficients with each other, so the inputs must be on a common scale. Each input is centered and scaled to variance 1 (divisor $n$), and the response is centered. In this article $X$ is the resulting $n \times p$ matrix of standardized inputs with $p = 10$, without a column of ones, and $\mathbf{y}$ is the centered response. (The unit's other articles count the intercept in $p$; here it is handled separately, as the next paragraph shows.) A coefficient is then the change in progression per standard deviation of its input. The intercept is never penalized: penalizing it would make the fit depend on where the origin of $\mathbf{y}$ is.

Proposition 1 (the intercept separates). For any penalty $\mathrm{pen}(\boldsymbol\beta)$ that does not involve the intercept, minimizing $\sum_i (y_i - \beta_0 - \mathbf{x}_i^{\mathsf T}\boldsymbol\beta)^2 + \mathrm{pen}(\boldsymbol\beta)$ over $\beta_0$ and $\boldsymbol\beta$, with the inputs centered, gives $\hat\beta_0 = \bar y$, and $\hat{\boldsymbol\beta}$ minimizes the same criterion for the centered response with no intercept.

Proof. For fixed $\boldsymbol\beta$, the criterion is a quadratic in $\beta_0$ minimized at the mean of $y_i - \mathbf{x}_i^{\mathsf T}\boldsymbol\beta$, which is $\bar y$ because $\sum_i \mathbf{x}_i = \mathbf{0}$ for centered inputs. Substituting $\beta_0 = \bar y$ leaves $\sum_i (y_i - \bar y - \mathbf{x}_i^{\mathsf T}\boldsymbol\beta)^2 + \mathrm{pen}(\boldsymbol\beta)$. $\square$

The least-squares estimate is $\hat{\boldsymbol\beta} = (X^{\mathsf T}X)^{-1}X^{\mathsf T}\mathbf{y}$, and with standardized inputs $X^{\mathsf T}X/n$ is the correlation matrix $R$ of the inputs. The penalty parameter $\lambda$ is reported as $\kappa = \lambda/n$, which puts it on the scale of the entries of $R$ for ridge, and on the scale of the covariances of the inputs with the response for the lasso.

Why least squares is unstable here

Under the Gauss–Markov conditions $\hat{\boldsymbol\beta}$ is unbiased with $\operatorname{Cov}(\hat{\boldsymbol\beta}) = \sigma^2(X^{\mathsf T}X)^{-1}$ (The Gauss–Markov Theorem). Write the eigendecomposition of the symmetric positive definite matrix $X^{\mathsf T}X = VD^2V^{\mathsf T}$, with $V$ orthogonal and $D^2 = \operatorname{diag}(d_1^2, \dots, d_p^2)$, $d_1^2 \ge \dots \ge d_p^2 > 0$. Equivalently, $X = UDV^{\mathsf T}$ is the singular value decomposition, with $U$ an $n \times p$ matrix of orthonormal columns; the columns $\mathbf{v}_j$ of $V$ are the principal component directions of the inputs (Principal Component Analysis). Then

$$\operatorname{Cov}(\hat{\boldsymbol\beta}) = \sigma^2 VD^{-2}V^{\mathsf T} = \sigma^2\sum_{j=1}^{p}\frac{\mathbf{v}_j\mathbf{v}_j^{\mathsf T}}{d_j^2}, \qquad E\lVert\hat{\boldsymbol\beta} - \boldsymbol\beta\rVert^2 = \operatorname{tr}\operatorname{Cov}(\hat{\boldsymbol\beta}) = \sigma^2\sum_{j=1}^p \frac{1}{d_j^2}.$$

The coefficient vector is most uncertain along the directions in which the inputs vary least. For the diabetes inputs, the eigenvalues of $R = X^{\mathsf T}X/n$ run from 4.024 down to 0.0086, so the ratio of the largest to the smallest singular value, the condition number of $X$, is 21.7. The smallest direction is a contrast among the serum measurements, with weights of absolute size 0.71 on S1, 0.56 on S2, 0.32 on S3 and 0.26 on S5 and almost nothing elsewhere. Taking the residual standard deviation $s = 54.15$ for $\sigma$, that one direction carries 84 percent of the total variance $\sigma^2\sum_j 1/d_j^2$ of the ten least-squares coefficients. The instability of the S1 and S2 coefficients is the instability of that single direction.

Ridge regression

Definition. For $\lambda \ge 0$, the ridge estimate minimizes $$\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2 + \lambda\lVert\boldsymbol\beta\rVert^2.$$

Theorem 1. For every $\lambda > 0$, and for any $X$ (of any rank, including $p > n$), the ridge criterion has the unique minimizer $$\hat{\boldsymbol\beta}_\lambda = (X^{\mathsf T}X + \lambda I)^{-1}X^{\mathsf T}\mathbf{y}.$$ It is also the least-squares estimate for the augmented data $\tilde X = \begin{pmatrix} X \\ \sqrt\lambda\,I \end{pmatrix}$, $\tilde{\mathbf{y}} = \begin{pmatrix}\mathbf{y} \\ \mathbf{0}\end{pmatrix}$.

Proof. $X^{\mathsf T}X + \lambda I$ is positive definite: $\mathbf{a}^{\mathsf T}(X^{\mathsf T}X + \lambda I)\mathbf{a} = \lVert X\mathbf{a}\rVert^2 + \lambda\lVert\mathbf{a}\rVert^2 > 0$ for $\mathbf{a} \ne \mathbf{0}$. Expanding, the criterion is $\boldsymbol\beta^{\mathsf T}(X^{\mathsf T}X + \lambda I)\boldsymbol\beta - 2\boldsymbol\beta^{\mathsf T}X^{\mathsf T}\mathbf{y} + \mathbf{y}^{\mathsf T}\mathbf{y}$. Completing the square with $A = X^{\mathsf T}X + \lambda I$ and $\mathbf{b} = A^{-1}X^{\mathsf T}\mathbf{y}$, it equals $(\boldsymbol\beta - \mathbf{b})^{\mathsf T}A(\boldsymbol\beta - \mathbf{b}) + \mathbf{y}^{\mathsf T}\mathbf{y} - \mathbf{b}^{\mathsf T}A\mathbf{b}$, which is minimized exactly at $\boldsymbol\beta = \mathbf{b}$ because $A$ is positive definite. For the augmented data, $\lVert\tilde{\mathbf{y}} - \tilde X\boldsymbol\beta\rVert^2 = \lVert\mathbf{y} - X\boldsymbol\beta\rVert^2 + \lVert\mathbf{0} - \sqrt\lambda\,\boldsymbol\beta\rVert^2$, the ridge criterion itself. $\square$

The augmented-data form says that ridge regression is least squares with $p$ extra observations, each with response 0 and with one input set to $\sqrt\lambda$: pseudo-data that pull every coefficient toward zero. Adding $\lambda$ to the diagonal of $X^{\mathsf T}X$ before inverting was Hoerl and Kennard's (1970) proposal for nonorthogonal inputs, according to their abstract, and Hastie, Tibshirani and Friedman (2009, §3.4.1) note that making the problem nonsingular in this way, even when $X^{\mathsf T}X$ is not of full rank, was the main motivation for ridge regression when it was first introduced in statistics.

Proposition 2 (the constraint form). If $\hat{\boldsymbol\beta}_\lambda$ minimizes the ridge criterion, it also minimizes $\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2$ among all $\boldsymbol\beta$ with $\lVert\boldsymbol\beta\rVert^2 \le t$, for $t = \lVert\hat{\boldsymbol\beta}_\lambda\rVert^2$. The same holds for the lasso with $\lVert\cdot\rVert_1$ in place of $\lVert\cdot\rVert^2$.

Proof. Suppose some $\boldsymbol\beta$ with $\lVert\boldsymbol\beta\rVert^2 \le t$ had a smaller residual sum of squares. Then its penalized criterion, $\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2 + \lambda\lVert\boldsymbol\beta\rVert^2$, would be smaller than that of $\hat{\boldsymbol\beta}_\lambda$, since both terms are no larger and the first is strictly smaller. That contradicts the minimality of $\hat{\boldsymbol\beta}_\lambda$. The argument uses nothing about the penalty except that it is the one being constrained. $\square$

So every penalized solution is a constrained one, a least-squares fit restricted to a ball. Hastie et al. (2009, eqs. 3.41 and 3.42) state the correspondence in both directions.

What ridge does to each principal direction

Here is the idea: in the coordinates of the principal directions, ridge divides each least-squares coordinate by the same factor $1 + \lambda/d_j^2$, so the poorly determined directions are shrunk the most.

Theorem 2. With $X = UDV^{\mathsf T}$, $$\hat{\boldsymbol\beta}_\lambda = \sum_{j=1}^p \frac{d_j^2}{d_j^2 + \lambda}\,\hat\alpha_j\,\mathbf{v}_j, \qquad X\hat{\boldsymbol\beta}_\lambda = \sum_{j=1}^p \mathbf{u}_j\,\frac{d_j^2}{d_j^2 + \lambda}\,\mathbf{u}_j^{\mathsf T}\mathbf{y},$$ where $\hat\alpha_j = \mathbf{u}_j^{\mathsf T}\mathbf{y}/d_j$ is the $j$th coordinate of the least-squares estimate in the basis $V$. The fitted values are $S_\lambda\mathbf{y}$ with $S_\lambda = X(X^{\mathsf T}X + \lambda I)^{-1}X^{\mathsf T}$, and $$\operatorname{df}(\lambda) = \operatorname{tr}S_\lambda = \sum_{j=1}^p\frac{d_j^2}{d_j^2 + \lambda},$$ which falls from $p$ at $\lambda = 0$ toward 0 as $\lambda \to \infty$. The length $\lVert\hat{\boldsymbol\beta}_\lambda\rVert$ decreases strictly in $\lambda$ unless $\hat{\boldsymbol\beta} = \mathbf{0}$.

Proof. $X^{\mathsf T}X + \lambda I = V(D^2 + \lambda I)V^{\mathsf T}$, so its inverse is $V(D^2 + \lambda I)^{-1}V^{\mathsf T}$, and $X^{\mathsf T}\mathbf{y} = VDU^{\mathsf T}\mathbf{y}$. Hence $\hat{\boldsymbol\beta}_\lambda = V(D^2 + \lambda I)^{-1}DU^{\mathsf T}\mathbf{y}$, whose $j$th coordinate in the basis $V$ is $d_j\,\mathbf{u}_j^{\mathsf T}\mathbf{y}/(d_j^2 + \lambda) = \hat\alpha_j\,d_j^2/(d_j^2 + \lambda)$. Multiplying by $X = UDV^{\mathsf T}$ gives the fitted values, and $S_\lambda = UD(D^2 + \lambda I)^{-1}DU^{\mathsf T}$ has trace $\sum_j d_j^2/(d_j^2 + \lambda)$ since $U^{\mathsf T}U = I$. Each term of the trace is strictly decreasing in $\lambda$. Finally $\lVert\hat{\boldsymbol\beta}_\lambda\rVert^2 = \sum_j d_j^4\hat\alpha_j^2/(d_j^2 + \lambda)^2$, a sum of terms each nonincreasing in $\lambda$ and strictly decreasing when $\hat\alpha_j \ne 0$. $\square$

The fitted-value form is equation 3.47 of Hastie et al. (2009), and the trace is their definition 3.50 of the effective degrees of freedom, which reduces to $p$, the number of coefficients, for least squares. For least squares the hat matrix $H$ of The Geometry of Least Squares has trace $p$; $S_\lambda$ is not a projection, and its trace counts how much fitting it does.

Ridge (left) and lasso (right) coefficients for the ten diabetes inputs as the penalty weakens from left to right, ending at least squares. Notice that the ridge paths are smooth and are all pulled to zero together only as the penalty grows without bound, while the lasso paths are piecewise linear and leave zero one input at a time, BMI first. Notice also that S1 and S2, the two cholesterol measurements, only separate into large coefficients of opposite sign at the weakest penalties. Dotted lines: ridge chosen by leave-one-out error; lasso chosen by the one-standard-error rule. Dashed: lasso at the minimum of cross-validated error.
Ridge (left) and lasso (right) coefficients for the ten diabetes inputs as the penalty weakens from left to right, ending at least squares. Notice that the ridge paths are smooth and are all pulled to zero together only as the penalty grows without bound, while the lasso paths are piecewise linear and leave zero one input at a time, BMI first. Notice also that S1 and S2, the two cholesterol measurements, only separate into large coefficients of opposite sign at the weakest penalties. Dotted lines: ridge chosen by leave-one-out error; lasso chosen by the one-standard-error rule. Dashed: lasso at the minimum of cross-validated error.

Example (a misreading of shrinkage). It is tempting to read "ridge shrinks the coefficients" as "each coefficient moves steadily toward zero". Theorem 2 promises only that the vector's length shrinks. Individual coefficients can grow, cross zero and change sign. At $\kappa = 1$ the effective degrees of freedom are 3.94, and the S1 and S2 coefficients are 0.28 and $-1.40$, both of the opposite sign to their least-squares values. The left panel of the figure shows S2 crossing zero twice: its ridge coefficient is exactly zero at $\kappa = 0.032$ and at $\kappa = 2.19$, and nonzero at every other penalty (its numerator, the polynomial of the proposition below, has degree 9 and exactly these two positive roots, as the script checks).

That is the general pattern. Proposition (isolated zeros). For each $j$, the ridge coefficient $\hat\beta_{\lambda,j}$ is either zero for every $\lambda > 0$ or zero for at most $p - 1$ values of $\lambda$.

Proof. By Cramer's rule, $\hat\beta_{\lambda,j} = \det B_j(\lambda)/\det(X^{\mathsf T}X + \lambda I)$, where $B_j(\lambda)$ is $X^{\mathsf T}X + \lambda I$ with its $j$th column replaced by $X^{\mathsf T}\mathbf{y}$. The denominator is positive for $\lambda > 0$ (Theorem 1). In the numerator, $\lambda$ appears in $p - 1$ columns, each entry at most linearly, so expanding the determinant gives a polynomial in $\lambda$ of degree at most $p - 1$. A polynomial that is not identically zero has at most that many roots. $\square$

So ridge can pass a coefficient through zero, but never holds one at zero over a range of penalties without holding it there for all of them; holding a coefficient at zero over a range is what the lasso does.

Bias, variance and the theorem of Hoerl and Kennard

Shrinkage introduces bias. The question is whether the variance it removes can outweigh the squared bias it adds. Here is the plan: in the principal coordinates every term separates, the mean squared error becomes an explicit function of $\lambda$, and its derivative at $\lambda = 0$ is negative.

Let $\boldsymbol\alpha = V^{\mathsf T}\boldsymbol\beta$ be the true coefficients in the principal basis. Under the Gauss–Markov conditions the least-squares coordinates $\hat\alpha_j$ are uncorrelated with means $\alpha_j$ and variances $\sigma^2/d_j^2$, because $\operatorname{Cov}(V^{\mathsf T}\hat{\boldsymbol\beta}) = \sigma^2 V^{\mathsf T}VD^{-2}V^{\mathsf T}V = \sigma^2D^{-2}$. Ridge multiplies coordinate $j$ by $f_j = d_j^2/(d_j^2 + \lambda)$, so its bias in that coordinate is $(f_j - 1)\alpha_j = -\lambda\alpha_j/(d_j^2 + \lambda)$ and its variance $f_j^2\sigma^2/d_j^2$. Since $V$ is orthogonal, the total mean squared error of the coefficient vector is

$$\mathrm{MSE}(\lambda) = E\lVert\hat{\boldsymbol\beta}_\lambda - \boldsymbol\beta\rVert^2 = \sum_{j=1}^p\frac{\sigma^2d_j^2 + \lambda^2\alpha_j^2}{(d_j^2 + \lambda)^2}.$$

Theorem 3 (Hoerl and Kennard). Under the Gauss–Markov conditions, $\mathrm{MSE}(\lambda)$ is strictly decreasing on $0 \le \lambda \le \sigma^2/\max_j\alpha_j^2$. In particular, some $\lambda > 0$ gives $\mathrm{MSE}(\lambda) < \mathrm{MSE}(0) = \sigma^2\sum_j 1/d_j^2$, whatever $\boldsymbol\beta$ and $\sigma^2$ are.

Proof. Differentiate one term. With $g(\lambda) = (\sigma^2d^2 + \lambda^2\alpha^2)(d^2 + \lambda)^{-2}$, $$g'(\lambda) = \frac{2\lambda\alpha^2(d^2 + \lambda) - 2(\sigma^2d^2 + \lambda^2\alpha^2)}{(d^2 + \lambda)^3} = \frac{2d^2(\lambda\alpha^2 - \sigma^2)}{(d^2 + \lambda)^3}.$$ This is negative whenever $\lambda\alpha^2 < \sigma^2$, which holds for every term when $\lambda < \sigma^2/\max_j\alpha_j^2$ (and for every $\lambda$ in a term with $\alpha_j = 0$). So the sum has a negative derivative on that interval, and is strictly decreasing on its closure. The bound is positive unless $\boldsymbol\beta = \mathbf{0}$, in which case every term decreases for all $\lambda$. $\square$

Hoerl and Kennard (1970) showed, in the words of their abstract, "how to augment $X'X$ to obtain biased estimates with smaller mean square error". Their existence theorem (Theorem 4.3) is proved the same way, from the derivative in the principal coordinates, and gives the same condition $\lambda < \sigma^2/\max_j\alpha_j^2$ (their equation 4.16). The same computation shows that term $j$ alone is minimized at $\lambda = \sigma^2/\alpha_j^2$, a large penalty for a direction whose true coefficient is small relative to the noise; Hoerl and Kennard (1970, §5) give these values for a general form of ridge regression with a separate penalty in each direction. A single $\lambda$ must compromise among the directions.

The theorem guarantees an improvement but not its size, and the best $\lambda$ depends on the unknown $\boldsymbol\beta$ and $\sigma^2$. To see the size on the diabetes inputs, take the least-squares fit as the truth: $\boldsymbol\beta = \hat{\boldsymbol\beta}$ and $\sigma^2 = s^2$. Then the least-squares coefficients have total mean squared error 927.0, the minimum of $\mathrm{MSE}(\lambda)$ is 744.0 at $\kappa = 0.00260$ (with 9.71 effective degrees of freedom), 80 percent of the least-squares value, and the theorem's guarantee holds up to $\kappa = 0.00254$. A seeded simulation checks this. It draws 1,000 responses from that truth per seed, for 30 seeds (17,000,000 + $s$). The simulated ratio of the two mean squared errors at the best $\kappa$ had median 80.4% (interquartile range 78.7% to 81.4%), in line with the exact calculation.

Total mean squared error of the ten ridge coefficients as a function of the penalty, when the truth is the least-squares fit to the diabetes data: variance (dashed), squared bias (dash-dot) and their sum (solid). Notice that the variance falls before the squared bias rises, so the sum dips by about a fifth; the dotted line marks the minimum, and the solid vertical line (yellow) the end of the range on which Theorem 3 guarantees a decrease, here almost the same penalty.
Total mean squared error of the ten ridge coefficients as a function of the penalty, when the truth is the least-squares fit to the diabetes data: variance (dashed), squared bias (dash-dot) and their sum (solid). Notice that the variance falls before the squared bias rises, so the sum dips by about a fifth; the dotted line marks the minimum, and the solid vertical line (yellow) the end of the range on which Theorem 3 guarantees a decrease, here almost the same penalty.

Almost all of the gain comes from the smallest principal direction, which carried 84% of the variance. At the best $\kappa$ its shrinkage factor is 0.77, while the other nine factors are 0.97 or more, and that one direction accounts for 97 percent of the reduction in mean squared error.

Ridge as a posterior mean

The penalty has a second reading. Suppose that, given $\boldsymbol\beta$, $\mathbf{y} \sim N_n(X\boldsymbol\beta, \sigma^2 I)$, and that before seeing the data the coefficients are independent $N(0, \tau^2)$, with $\sigma^2$ and $\tau^2$ known.

Proposition 3. The posterior distribution of $\boldsymbol\beta$ is normal with mean $\hat{\boldsymbol\beta}_\lambda$ for $\lambda = \sigma^2/\tau^2$ and covariance $\sigma^2(X^{\mathsf T}X + \lambda I)^{-1}$.

Proof. By Bayes' theorem the posterior density is proportional to the likelihood times the prior, $$\exp\Big(-\frac{\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2}{2\sigma^2}\Big)\exp\Big(-\frac{\lVert\boldsymbol\beta\rVert^2}{2\tau^2}\Big) = \exp\Big(-\frac{\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2 + \lambda\lVert\boldsymbol\beta\rVert^2}{2\sigma^2}\Big).$$ By the completed square in the proof of Theorem 1, the exponent is $-(\boldsymbol\beta - \hat{\boldsymbol\beta}_\lambda)^{\mathsf T}(X^{\mathsf T}X + \lambda I)(\boldsymbol\beta - \hat{\boldsymbol\beta}_\lambda)/(2\sigma^2)$ plus a term free of $\boldsymbol\beta$. That is the kernel of the normal density with the stated mean and covariance. $\square$

So ridge regression is the posterior mean, and also the posterior mode, under a normal prior centered at zero, with the penalty set by the ratio of noise variance to prior variance (Hastie et al., 2009, §3.4.1). The lasso is the posterior mode under independent double-exponential (Laplace) priors, but not the posterior mean (Hastie et al., 2009, §3.4.3). A Bayesian reading is a reason to standardize: an exchangeable prior on the coefficients only makes sense if they are on comparable scales.

Choosing the ridge penalty: exact leave-one-out error

The penalty is chosen to predict well, and prediction error is estimated by cross-validation (Cross-Validation). For ridge, leave-one-out cross-validation costs a single fit.

Theorem 4. Fit ridge with an unpenalized intercept: let $A$ be the $n \times (p + 1)$ matrix $[\mathbf{1}, X]$, of full column rank, $\Lambda = \operatorname{diag}(0, \lambda, \dots, \lambda)$, $M_\lambda = A^{\mathsf T}A + \Lambda$ and $S = AM_\lambda^{-1}A^{\mathsf T}$ with diagonal entries $S_{ii}$. If observation $i$ is deleted and the model refitted with the same penalty, its prediction error is $$y_i - \hat y_{(i)} = \frac{y_i - \hat y_i}{1 - S_{ii}}.$$

Proof. The proof of the deletion identities in Leverage, Influence and Residual Diagnostics used only two facts: the fit is $M^{-1}A^{\mathsf T}\mathbf{y}$ for a matrix $M$, and deleting row $\mathbf{a}_i$ replaces $M$ by $M - \mathbf{a}_i\mathbf{a}_i^{\mathsf T}$ and $A^{\mathsf T}\mathbf{y}$ by $A^{\mathsf T}\mathbf{y} - \mathbf{a}_iy_i$. Both hold for $M_\lambda$, because the penalty matrix $\Lambda$ does not involve the observations. With $S_{ii} = \mathbf{a}_i^{\mathsf T}M_\lambda^{-1}\mathbf{a}_i$ in place of $h_{ii}$, the Sherman–Morrison formula and the same algebra give the result, provided $S_{ii} < 1$. That holds for every $\lambda > 0$ and $n \ge 2$. By the matrix determinant lemma, $\det(M_\lambda - \mathbf{a}_i\mathbf{a}_i^{\mathsf T}) = \det M_\lambda\,(1 - \mathbf{a}_i^{\mathsf T}M_\lambda^{-1}\mathbf{a}_i) = \det M_\lambda\,(1 - S_{ii})$. (It follows from $\det\begin{pmatrix} M & \mathbf{a} \ \mathbf{a}^{\mathsf T} & 1\end{pmatrix}$ computed two ways, by the Schur complement of $M$ and by that of the 1.) Both determinants are positive. $M_\lambda$ is positive definite because $A$ has full column rank. And $M_\lambda - \mathbf{a}_i\mathbf{a}_i^{\mathsf T} = A_{(i)}^{\mathsf T}A_{(i)} + \Lambda$, with $A_{(i)}$ the design without row $i$, is positive definite too: if $\mathbf{v}^{\mathsf T}(A_{(i)}^{\mathsf T}A_{(i)} + \Lambda)\mathbf{v} = 0$ then $\lVert A_{(i)}\mathbf{v}\rVert^2 + \lambda\sum_{j \ge 1}v_j^2 = 0$, so $v_j = 0$ for $j \ge 1$, and then $A_{(i)}\mathbf{v} = v_0\mathbf{1}_{n-1} = \mathbf{0}$ forces $v_0 = 0$. Hence $1 - S_{ii} > 0$. $\square$

(The inequality $M_\lambda^{-1} \preceq (A^{\mathsf T}A)^{-1}$ holds because $M_\lambda - A^{\mathsf T}A = \Lambda$ is positive semidefinite, and inversion reverses the order of positive definite matrices.) Here the inputs are standardized once, with all 442 patients, and the standardization is treated as fixed; the script checks the identity against 442 explicit refits at three penalties. Hastie et al. (2009, §7.10.1, eq. 7.51) state this shortcut for many linear fitting methods. Golub, Heath and Wahba (1979) studied generalized cross-validation as a way to choose the ridge parameter. It replaces each $S_{ii}$ by the average $\operatorname{tr}S/n$, and they derive it as a rotation-invariant version of Allen's PRESS, the leave-one-out sum of squares.

On the diabetes data, the leave-one-out error is minimized at $\kappa = 0.0042$, with 9.58 effective degrees of freedom; generalized cross-validation chooses $\kappa = 0.0074$ (both found by a golden-section search refining a grid of 141 penalties). The minimum leave-one-out mean squared error is 3,000, against 3,002 for least squares (both in squared progression units). The shrinkage factors at the chosen $\kappa$ range from 0.999 to 0.673, the smallest belonging to the smallest principal direction. So the chosen ridge fit changes the prediction error by almost nothing and the coefficients substantially. S1 moves from $-37.7$ to $-25.8$ and S2 from 22.7 to 13.3, while BMI stays at 24.8 (least squares 24.7) and S5 moves from 35.7 to 31.2. On the full data, ridge changes the cholesterol contrast and leaves the leave-one-out error where it was. The held-out experiment below measures what happens with fewer patients.

The lasso

Definition. For $\lambda \ge 0$, the lasso estimate minimizes $$L(\boldsymbol\beta) = \tfrac12\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2 + \lambda\lVert\boldsymbol\beta\rVert_1, \qquad \lVert\boldsymbol\beta\rVert_1 = \sum_{j=1}^p|\beta_j|.$$

Tibshirani (1996) proposed it in the constraint form, minimizing the residual sum of squares subject to $\sum_j|\beta_j| \le t$, noting in the abstract that "because of the nature of this constraint it tends to produce some coefficients that are exactly 0". The factor $\tfrac12$ follows Hastie et al. (2009, eq. 3.52) and makes the formulas below cleaner. By Proposition 2 the two forms describe the same estimates.

The constraint form shows where the zeros come from. The residual sum of squares has elliptical contours centered at the least-squares estimate, and the constrained solution is the first point at which a contour touches the constraint region. A disk has no corners, so the contact point generically has every coordinate nonzero. A diamond has corners on the axes, and an ellipse expanding from outside often meets it first at a corner, where one coordinate is exactly zero.

The diabetes regression on BMI and BP alone. Elliptical contours of the residual sum of squares are centered at the least-squares estimate; the shaded regions are the lasso diamond (left) and the ridge disk (right) of the same size, 15. Notice that the lasso solution sits at the corner of the diamond, so the BP coefficient is exactly zero, while the ridge solution keeps both coefficients.
The diabetes regression on BMI and BP alone. Elliptical contours of the residual sum of squares are centered at the least-squares estimate; the shaded regions are the lasso diamond (left) and the ridge disk (right) of the same size, 15. Notice that the lasso solution sits at the corner of the diamond, so the BP coefficient is exactly zero, while the ridge solution keeps both coefficients.

On BMI and BP alone, least squares gives coefficients 37.6 and 19.1 for BMI and BP. With budget 15, the lasso solution is $(15, 0)$, at a corner; ridge with $\lVert\boldsymbol\beta\rVert \le 15$ gives $(12.3, 8.6)$ on the disk. The script checks the lasso corner against the optimality conditions of Theorem 6 below.

The orthonormal case

If the columns of $X$ are orthonormal, $X^{\mathsf T}X = I$, every method acts on each least-squares coefficient separately, and the three can be compared exactly.

Theorem 5. Let $X^{\mathsf T}X = I$, so that $\hat\beta_j = \mathbf{x}_j^{\mathsf T}\mathbf{y}$. Then the ridge estimate is $\hat\beta_j/(1 + \lambda)$; the lasso estimate is the soft threshold $S(\hat\beta_j, \lambda) = \operatorname{sign}(\hat\beta_j)(|\hat\beta_j| - \lambda)_+$; and best-subset selection of size $M$ keeps the $M$ largest $|\hat\beta_j|$ unchanged and sets the others to 0 (hard thresholding).

Proof. Since $\hat{\boldsymbol\beta} = X^{\mathsf T}\mathbf{y}$ and $X\hat{\boldsymbol\beta}$ is the projection of $\mathbf{y}$ onto $\mathcal{C}(X)$, Pythagoras gives $\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2 = \lVert\mathbf{y} - X\hat{\boldsymbol\beta}\rVert^2 + \lVert X(\hat{\boldsymbol\beta} - \boldsymbol\beta)\rVert^2 = \text{const} + \sum_j(\beta_j - \hat\beta_j)^2$. So each criterion is a constant plus a sum of separate terms in each $\beta_j$. Ridge: $(\beta - \hat\beta)^2 + \lambda\beta^2$ has derivative $2(\beta - \hat\beta) + 2\lambda\beta$, zero at $\beta = \hat\beta/(1 + \lambda)$. Lasso: minimize $\phi(\beta) = \tfrac12(\beta - \hat\beta)^2 + \lambda|\beta|$. For $\beta > 0$, $\phi'(\beta) = \beta - \hat\beta + \lambda$, zero at $\beta = \hat\beta - \lambda$, which is positive only if $\hat\beta > \lambda$; for $\beta < 0$, $\phi'(\beta) = \beta - \hat\beta - \lambda$, zero at $\hat\beta + \lambda$, negative only if $\hat\beta < -\lambda$. If $|\hat\beta| \le \lambda$, $\phi$ is decreasing on $(-\infty, 0)$ and increasing on $(0, \infty)$, so the minimum is at 0. Since $\phi$ is convex, these stationary points are the minima, which is the soft threshold. Best subset: with $M$ coefficients allowed to be nonzero, each kept coefficient contributes 0 at $\beta_j = \hat\beta_j$ and each dropped one contributes $\hat\beta_j^2$, so the cost $\sum_{\text{dropped}}\hat\beta_j^2$ is smallest when the dropped ones are the $p - M$ smallest in absolute value. $\square$

These are the entries of Table 3.4 of Hastie et al. (2009). Ridge shrinks every coefficient by the same proportion and never to zero. The lasso subtracts the same amount $\lambda$ from every coefficient's size and stops at zero. Best subset either keeps a coefficient untouched or removes it. The lasso is thus a continuous version of selection. The script checks all three formulas on a random orthonormal design.

Optimality conditions

Without orthogonality there is no closed form, but the solutions are characterized exactly. Here is the idea: $L$ is convex, so a point is a minimum if and only if no direction leads downhill, and the downhill test can be computed coordinate by coordinate.

Theorem 6 (Karush–Kuhn–Tucker conditions for the lasso). $\hat{\boldsymbol\beta}$ minimizes $L$ if and only if, with $\mathbf{g} = X^{\mathsf T}(\mathbf{y} - X\hat{\boldsymbol\beta})$, for every $j$: $$g_j = \lambda\operatorname{sign}(\hat\beta_j)\ \text{ if } \hat\beta_j \ne 0, \qquad |g_j| \le \lambda\ \text{ if } \hat\beta_j = 0.$$

Proof. The function $L$ is convex: the squared norm is convex, each $|\beta_j|$ is convex, and sums of convex functions are convex. For a convex function, $\hat{\boldsymbol\beta}$ is a minimum if and only if the one-sided directional derivative $L'(\hat{\boldsymbol\beta}; \mathbf{d}) = \lim_{\epsilon \downarrow 0}[L(\hat{\boldsymbol\beta} + \epsilon\mathbf{d}) - L(\hat{\boldsymbol\beta})]/\epsilon$ is nonnegative for every direction $\mathbf{d}$. (If it is, convexity gives $L(\hat{\boldsymbol\beta} + \mathbf{d}) - L(\hat{\boldsymbol\beta}) \ge [L(\hat{\boldsymbol\beta} + \epsilon\mathbf{d}) - L(\hat{\boldsymbol\beta})]/\epsilon$ for $0 < \epsilon \le 1$, and the right side tends to a nonnegative limit; conversely a negative directional derivative gives a smaller value at a small step.) The smooth part contributes $-\mathbf{g}^{\mathsf T}\mathbf{d}$. The term $|\beta_j|$ contributes $\operatorname{sign}(\hat\beta_j)d_j$ if $\hat\beta_j \ne 0$ and $|d_j|$ if $\hat\beta_j = 0$. So $$L'(\hat{\boldsymbol\beta}; \mathbf{d}) = \sum_{j:\,\hat\beta_j \ne 0}\big(\lambda\operatorname{sign}(\hat\beta_j) - g_j\big)d_j + \sum_{j:\,\hat\beta_j = 0}\big(\lambda|d_j| - g_jd_j\big).$$ If the conditions hold, the first sum vanishes and each term of the second is at least $\lambda|d_j| - |g_j||d_j| \ge 0$. Conversely, if $\hat\beta_j \ne 0$ and $g_j \ne \lambda\operatorname{sign}(\hat\beta_j)$, the direction $\mathbf{d} = \pm\mathbf{u}_j$ (the $j$th unit vector, with the sign chosen against the difference) gives a negative derivative; if $\hat\beta_j = 0$ and $|g_j| > \lambda$, the direction $\operatorname{sign}(g_j)\mathbf{u}_j$ gives $\lambda - |g_j| < 0$. $\square$

With standardized inputs, $g_j/n$ is the covariance of input $j$ with the current residual. The conditions say that every active input has covariance exactly $\pm\lambda/n$ with the residual, the sign of its coefficient, and every inactive input has covariance at most $\lambda/n$ in absolute value. Three facts about the solutions follow; the first and third come from the conditions, the second from convexity.

  • When all coefficients are zero. $\hat{\boldsymbol\beta} = \mathbf{0}$ satisfies the conditions exactly when $|\mathbf{x}_j^{\mathsf T}\mathbf{y}| \le \lambda$ for all $j$. So the lasso is entirely zero for $\lambda \ge \lambda_{\max} = \max_j|\mathbf{x}_j^{\mathsf T}\mathbf{y}|$, and the first input to enter is the one with the largest covariance with the response. For the diabetes data, $\lambda_{\max}/n = 45.160$, attained by BMI. Friedman, Hastie and Tibshirani (2010, §2.5) start their path algorithm at this value.
  • Unique fitted values. All solutions have the same fitted values $X\hat{\boldsymbol\beta}$. If two solutions had different fitted values $\mathbf{f}_1 \ne \mathbf{f}_2$, their average would have the average penalty or less (by convexity of $\lVert\cdot\rVert_1$) and a residual sum of squares strictly below the average of the two, since $\boldsymbol\mu \mapsto \lVert\mathbf{y} - \boldsymbol\mu\rVert^2$ is strictly convex; its criterion would be smaller than the minimum. When $X$ has full column rank, $L$ is strictly convex and the solution itself is unique. Tibshirani (2013) proves the uniqueness of the fit in general (Lemma 1) and, for $\lambda > 0$, the uniqueness of the solution whenever the columns of $X$ are in general position (Lemma 3); by his Lemma 4, for $\lambda > 0$ the solution is unique with probability one when the entries of $X$ are drawn from a continuous distribution.
  • A piecewise-linear path. On an interval of $\lambda$ over which the active set $\mathcal{A}$ and the signs $\mathbf{s}$ stay fixed, the conditions read $X_{\mathcal A}^{\mathsf T}(\mathbf{y} - X_{\mathcal A}\hat{\boldsymbol\beta}_{\mathcal A}) = \lambda\mathbf{s}$, so $\hat{\boldsymbol\beta}_{\mathcal A} = (X_{\mathcal A}^{\mathsf T}X_{\mathcal A})^{-1}(X_{\mathcal A}^{\mathsf T}\mathbf{y} - \lambda\mathbf{s})$, linear in $\lambda$ (when $X_{\mathcal A}$ has full column rank). The path bends only at the values of $\lambda$, called knots, where an input enters or leaves. Least angle regression computes the knots one after another (Efron et al., 2004).

Coordinate descent

The conditions also give an algorithm. Fix every coefficient except $\beta_j$. The criterion as a function of $\beta_j$ alone is $\tfrac12\lVert\mathbf{r}_j - \mathbf{x}_j\beta_j\rVert^2 + \lambda|\beta_j|$ plus a constant, where $\mathbf{r}_j = \mathbf{y} - \sum_{k \ne j}\mathbf{x}_k\beta_k$ is the partial residual. Expanding, this is $\tfrac12\lVert\mathbf{x}_j\rVert^2(\beta_j - z_j/\lVert\mathbf{x}_j\rVert^2)^2 + \lambda|\beta_j|$ plus a constant, with $z_j = \mathbf{x}_j^{\mathsf T}\mathbf{r}_j$. Dividing by $\lVert\mathbf{x}_j\rVert^2$ turns it into the one-coordinate problem of Theorem 5, so the minimizer is

$$\beta_j \leftarrow \frac{S(z_j, \lambda)}{\lVert\mathbf{x}_j\rVert^2}, \qquad z_j = \mathbf{x}_j^{\mathsf T}\mathbf{y} - \sum_{k \ne j}(\mathbf{x}_j^{\mathsf T}\mathbf{x}_k)\beta_k.$$

Cycling through the coordinates never increases $L$. Friedman et al. (2010, §2) build their software on this update. They compute it along a decreasing sequence of $\lambda$ values from $\lambda_{\max}$, with each solution as the starting point for the next, and they rely on the convergence of coordinate descent for convex problems whose nonsmooth part is a sum of functions of single coordinates (Tseng, 2001, as they cite it). The script uses the update with the second form of $z_j$, which needs only $X^{\mathsf T}X$ and $X^{\mathsf T}\mathbf{y}$. It finishes each solve by solving the equations of Theorem 6 exactly on the active set, and accepts the result only if every condition holds.

The lasso path on the diabetes data

The inputs enter the lasso in the order BMI, S5, BP, S3, sex, S6, S1, S4, S2, age, as the penalty weakens. The first four agree with the order 3, 9, 4, 7 that Efron et al. (2004, Fig. 1) report for the same data, and as in their example only those four are active when $\sum_j|\beta_j| = 1{,}000$ in their scaling, with inputs of unit length. S5 enters at $\kappa = 42.300$ and BP at $\kappa = 21.542$. The script computes the knots with scikit-learn's least angle regression and checks that its own coordinate descent reproduces the coefficients at every knot.

One input does something the proposition on isolated zeros rules out for ridge: S3 enters with a negative coefficient, returns to zero at $\kappa = 0.104$, stays at exactly zero down to $\kappa = 0.062$, and then re-enters with the positive sign of its least-squares coefficient. The script finds these knots by least angle regression and confirms them with coordinate descent just above, inside and just below the stretch. Theorem 6 describes the three stages: just above the stretch, S3's covariance with the residual equals $-\lambda/n$, the sign of its negative coefficient; inside it, the covariance lies within $\pm\lambda/n$; just below it, the covariance equals $+\lambda/n$. At $\lambda = 0$ the path reaches least squares, where $\sum_j|\hat\beta_j|$ in the unit-length scaling is 3,459.98 by our computation; Efron et al. report $t = 3460.00$ for the end of their path.

Ten-fold cross-validation over a grid of 100 penalties (folds assigned with seed 20261118, inputs standardized within each training fold) has its minimum at $\kappa = 0.074$, inside the stretch where S3 is zero, with cross-validated mean squared error 2,965.6 and 9 nonzero coefficients. Least squares on the same folds has cross-validated error 2,966.0. The lasso's best error is lower by 0.4, or 0.014%, and that best is the minimum over 100 penalties on the same folds, which flatters it; the improvement is negligible. The one-standard-error rule, which takes the largest penalty whose error is within one standard error of the minimum (Cross-Validation; Hastie et al., 2009, §7.10.1), chooses $\kappa = 5.83$ with error 3,134 and 5 nonzero coefficients: sex $-0.65$, BMI 24.10, BP 9.47, S3 $-5.91$ and S5 21.01. The cholesterol pair is gone. At this penalty, the KKT conditions can be read off the fit. Every active input has covariance $\pm 5.83$ with the residual, and the largest absolute covariance of an inactive input is 5.15, below $\lambda/n = 5.83$, so none of them is at the point of entering (the inactive bound is checked for every input).

Degrees of freedom. Zou, Hastie and Tibshirani (2007, Theorem 1) prove that for a fixed $\lambda$ the number of nonzero lasso coefficients is an unbiased estimate of the lasso's degrees of freedom, defined as $\sum_i\operatorname{Cov}(\hat y_i, y_i)/\sigma^2$, when $X$ has full column rank. A seeded check at the one-standard-error penalty takes the least-squares fit as the true mean and $\sigma = s$, simulates 200 responses for each of 30 seeds (19,000,000 + $s$), and estimates the covariance definition directly. Counting the intercept, the covariance estimate of the degrees of freedom had median 6.58 across seeds (interquartile range 5.81 to 7.43), and the average number of nonzero coefficients plus one had median 6.15 (interquartile range 6.12 to 6.19). The two agree within the simulation's noise, which is much larger for the covariance estimate. One way to read the theorem: a lasso fit with about 5 active inputs costs about as many degrees of freedom as least squares with 5 inputs fixed in advance, as if the shrinkage of the coefficients offset, on average, the cost of choosing which inputs to use. That reading is ours, not a statement of the paper.

Prediction on held-out patients

How much does shrinkage help prediction? A seeded experiment answers for these data. For each of 30 seeds (18,000,000 + $s$), it draws a random training set of patients and chooses the ridge and lasso penalties by 10-fold cross-validation inside the training set. It then measures the mean squared prediction error on the remaining patients.

With 50 training patients:

Method Median test MSE Interquartile range Better than least squares
Least squares 3,766 3,484 to 4,092
Ridge 3,439 3,298 to 3,754 26 of 30
Lasso 3,545 3,354 to 3,818 27 of 30

With 221 training patients (half the data):

Method Median test MSE Interquartile range Better than least squares
Least squares 3,067 2,974 to 3,159
Ridge 3,075 2,965 to 3,158 16 of 30
Lasso 3,081 2,977 to 3,162 14 of 30

With 50 training patients, both penalized methods beat least squares in most training sets: the median ratio of the penalized method's error to least squares' error in the same training set was 0.93 for ridge and 0.95 for the lasso, and the lasso kept a median of 6.0 of the ten inputs. With 221 training patients the three methods are indistinguishable (median ratio 1.00 for both), and the lasso kept a median of 8.0 inputs. In this experiment, the benefit of shrinkage depends on how much information each coefficient has: with 50 training patients and ten correlated inputs the least-squares variance is large, and with 221 it is already small. That matches the ridge leave-one-out result on the full data.

Which inputs the lasso keeps. BMI and S5 were selected in all 30 training sets of both sizes. S1 was selected in 9 of the 30 sets with 50 training patients and 22 of 30 with 221; S2 in 11 and 13. Among strongly correlated inputs the lasso tends to pick one somewhat arbitrarily, and which one changes from sample to sample. The elastic net of Zou and Hastie (2005) addresses this behavior. It adds a ridge penalty to the lasso's and, by their abstract, "encourages a grouping effect, where strongly correlated predictors tend to be in or out of the model together"; they also describe it as particularly useful when $p$ is much larger than $n$. A selected set is therefore a description of one fit, not a finding about which measurements matter. The usual $t$ tests computed after the lasso has chosen the inputs treat the chosen set as fixed in advance, so their stated error rates do not account for the selection.

What is proved here, what is cited, what the experiment shows

Proved on this page: the separation of the intercept (Proposition 1); the ridge solution, its existence for every design and its augmented-data form (Theorem 1); the equivalence of penalized and constrained solutions in one direction (Proposition 2); the action of ridge on principal directions, its effective degrees of freedom and the monotone length of the coefficient vector (Theorem 2); the isolated zeros of a ridge coefficient; the mean squared error of ridge and the Hoerl–Kennard existence theorem with an explicit range (Theorem 3); ridge as a posterior mean (Proposition 3); the exact leave-one-out error of ridge (Theorem 4); the orthonormal formulas, including soft thresholding (Theorem 5); the KKT conditions of the lasso (Theorem 6) with $\lambda_{\max}$, the uniqueness of the fitted values and the piecewise linearity of the path; and the coordinate descent update.

Cited: the existence theorem and its condition on the penalty, in their original form (Hoerl and Kennard, 1970); the uniqueness of lasso solutions under general position (Tibshirani, 2013); the unbiasedness of the count of nonzero coefficients as an estimate of degrees of freedom (Zou, Hastie and Tibshirani, 2007); the convergence of coordinate descent (Tseng, 2001, through Friedman et al., 2010); the lasso as a posterior mode under a Laplace prior and the forms of the criteria (Hastie et al., 2009); the order of entry on the diabetes data (Efron et al., 2004); the elastic net's grouping effect (Zou and Hastie, 2005).

Computed: every number for the diabetes data, with the lasso path checked against least angle regression and the ridge leave-one-out identity against explicit refits. The experiments' findings are observations about these data, these training sizes and these seeds: that shrinkage lowered held-out error with 50 training patients and not with 221, and that the selection of the cholesterol measurements varied across training sets.

Worked problems

These problems were written for this article; each is solved with results proved above, and the script checks every number.

Problem 1 (ridge by hand for two correlated inputs). Two standardized inputs on $n = 100$ observations have correlation 0.9, so $X^{\mathsf T}X = \begin{pmatrix} 100 & 90 \\ 90 & 100 \end{pmatrix}$, and $X^{\mathsf T}\mathbf{y} = (60, 50)^{\mathsf T}$. Find the least-squares and the ridge estimates for $\lambda = 10$, and the shrinkage factors of the two principal directions.

Solution. The determinant of $X^{\mathsf T}X$ is $100^2 - 90^2 = 1{,}900$, so least squares gives $\hat{\boldsymbol\beta} = \frac{1}{1900}(100 \cdot 60 - 90 \cdot 50,\ 100 \cdot 50 - 90 \cdot 60) = (1500, -400)/1900 = (15/19, -4/19)$: the two inputs with positive covariances with the response get coefficients of opposite sign, the pattern of S1 and S2. For ridge, $X^{\mathsf T}X + 10I$ has determinant $110^2 - 90^2 = 4{,}000$, so $\hat{\boldsymbol\beta}_{10} = \frac{1}{4000}(110 \cdot 60 - 90 \cdot 50,\ 110 \cdot 50 - 90 \cdot 60) = (2100, 100)/4000 = (0.5250, 0.0250)$. The eigenvectors of $X^{\mathsf T}X$ are $(1, 1)/\sqrt2$ and $(1, -1)/\sqrt2$, with eigenvalues $d^2 = 100 + 90 = 190$ and $100 - 90 = 10$. By Theorem 2 the shrinkage factors are $190/200 = 0.950$ along the sum and $10/20 = 0.500$ along the difference. Ridge halves the poorly determined contrast between the two inputs and barely touches their sum, and the second coefficient changes sign as a result.

Problem 2 (the lasso path for the same inputs). For the data of Problem 1, find $\lambda_{\max}$, the penalty at which the second input enters the lasso, and the lasso solution at $\lambda = 1$.

Solution. By Theorem 6, $\lambda_{\max} = \max(|60|, |50|) = 60$, and the first input enters first. While it alone is active with a positive sign, its condition $60 - 100\beta_1 = \lambda$ gives $\beta_1 = (60 - \lambda)/100$. The second input's covariance with the residual is then $g_2 = 50 - 90\beta_1 = 50 - 0.9(60 - \lambda) = -4 + 0.9\lambda$. It stays inactive while $|g_2| \le \lambda$. For $\lambda$ below $40/9$, $g_2$ is negative, and $|g_2| = 4 - 0.9\lambda \le \lambda$ holds exactly while $\lambda \ge 4/1.9 = 40/19$. So the second input enters at $\lambda = 40/19 = 2.11$, with a negative sign, when $\beta_1 = (60 - 40/19)/100 = 0.5789$. Below that, both are active with signs $(+, -)$, and Theorem 6 gives $X^{\mathsf T}X\boldsymbol\beta = X^{\mathsf T}\mathbf{y} - \lambda(1, -1)^{\mathsf T}$. At $\lambda = 1$ the right side is $(59, 51)$, and solving with the inverse from Problem 1, $\boldsymbol\beta = \frac{1}{1900}(100 \cdot 59 - 90 \cdot 51,\ 100 \cdot 51 - 90 \cdot 59) = (1310, -210)/1900 = (131/190, -21/190)$. The signs are $(+, -)$ as assumed, so this is the solution. Theorem 6's conditions can be checked directly: $g_1 = 60 - 100(131/190) + 90(21/190) = 1$ and $g_2 = 50 - 90(131/190) + 100(21/190) = -1$.

Problem 3 (the best penalty in one direction). In one principal direction, $d^2 = 4$, the true coefficient is $\alpha = 1$ and $\sigma^2 = 2$. Find the mean squared error of least squares in that direction, the penalty that minimizes the ridge mean squared error, and its value there.

Solution. The term of $\mathrm{MSE}(\lambda)$ for this direction is $(\sigma^2d^2 + \lambda^2\alpha^2)/(d^2 + \lambda)^2 = (8 + \lambda^2)/(4 + \lambda)^2$. At $\lambda = 0$ it is $8/16 = 1/2$, the least-squares variance $\sigma^2/d^2$. By the derivative in the proof of Theorem 3 it decreases while $\lambda < \sigma^2/\alpha^2 = 2$ and increases after, so the minimum is at $\lambda = 2$, where it equals $(8 + 4)/36 = 1/3$. In general the minimum value is $\sigma^2/(d^2 + \sigma^2/\alpha^2)$: substituting $\lambda = \sigma^2/\alpha^2$ makes the numerator $\sigma^2(d^2 + \lambda)$, and one factor $d^2 + \lambda$ cancels. Here that is $2/6 = 1/3$, a third less than least squares.

Summary

Ridge Lasso
Criterion $\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2 + \lambda\lVert\boldsymbol\beta\rVert^2$ $\tfrac12\lVert\mathbf{y} - X\boldsymbol\beta\rVert^2 + \lambda\lVert\boldsymbol\beta\rVert_1$
Solution $(X^{\mathsf T}X + \lambda I)^{-1}X^{\mathsf T}\mathbf{y}$ KKT conditions (Theorem 6); no closed form
Orthonormal case $\hat\beta_j/(1 + \lambda)$ $\operatorname{sign}(\hat\beta_j)(\lvert\hat\beta_j\rvert - \lambda)_+$
Exact zeros at most $p - 1$ values of $\lambda$ per coefficient, unless it is zero for every $\lambda$ some, all for $\lambda \ge \max_j\lvert\mathbf{x}_j^{\mathsf T}\mathbf{y}\rvert$
Degrees of freedom $\sum_j d_j^2/(d_j^2 + \lambda)$ expected number of nonzero coefficients
Bayesian reading posterior mean and mode, normal prior posterior mode, Laplace prior
Path smooth piecewise linear

What we have learned

Least squares is unbiased, and on correlated inputs its variance can be concentrated in the principal directions along which the inputs barely vary; on the diabetes data one direction, a contrast among the cholesterol measurements, carried 84% of it. Ridge regression shrinks each principal direction by $d_j^2/(d_j^2 + \lambda)$, and the theorem of Hoerl and Kennard guarantees that a small enough penalty always lowers the total mean squared error. The lasso replaces the squared penalty by the absolute one, and its optimality conditions show why some coefficients are exactly zero: an input whose covariance with the residual is smaller in absolute value than $\lambda/n$ must have a zero coefficient. On the full diabetes data, the ridge leave-one-out error and the lasso's best ten-fold error each differed from least squares' on the same data by less than 0.1%; with 50 training patients both methods beat least squares in most training sets. Both methods leave the inference questions open: which inputs matter, and with what uncertainty, after the data chose the penalty.

The penalties here act on linear models with squared error. The same penalties apply to models fitted by maximum likelihood, such as logistic regression, which is where the unit Generalized Linear Models continues, and the choice of the penalty is one case of the general problem of prediction error taken up in Model Selection. The unit's overview is Linear Models.

References