Coordinate Descent for Ridge

Why Coordinate Descent for Ridge?

Ridge regression estimates slopes by balancing fit to the observed responses against a penalty on coefficient size. When predictors are numerous, a direct matrix solution may be inconvenient. Coordinate descent instead updates one coefficient at a time, holding the others fixed. For ridge, each such update has a closed form: it is a least-squares update with an additional penalty term in the denominator.

The result depends on the precise scaling of the objective. This tutorial uses one convention throughout its worked examples, then shows how to translate the update if the residual sum of squares is divided by the sample size. Predictors and response are treated as fixed data; no probability model is needed to derive the update.

Definition: For response vector $y$, predictor columns $x_1,\ldots,x_p$, slopes $\beta_1,\ldots,\beta_p$, and penalty parameter $\lambda \geq 0$, define the ridge objective by $$ Q(\beta)=\frac{1}{2}\left\|y-\sum_{j=1}^{p}x_j\beta_j\right\|^2+\frac{\lambda}{2}\sum_{j=1}^{p}\beta_j^2. $$ Here $\|z\|^2=z'z$. The intercept, if included, is not penalized. In the examples, it is either absent or handled separately.

The factors of $1/2$ make derivatives simpler. They do not change the minimizer relative to an objective written as residual sum of squares plus $\lambda$ times the sum of squared slopes, provided both terms are scaled consistently. The value of $\lambda$ is tied to the chosen objective convention.

Deriving the Coordinate Update

To update coefficient $\beta_j$, hold all other coefficients fixed. The partial residual for this coordinate is the response after subtracting the current fitted contributions from every predictor except $x_j$:

r_j=y-\sum_{k\ne j}x_k\beta_k.

With the other coefficients fixed, the terms of $Q$ that depend on $\beta_j$ are the squared distance between $r_j$ and $x_j\beta_j$, plus the penalty on $\beta_j$. Expanding this one-dimensional objective gives the update directly.

Keep only the terms involving $\beta_j$.
They are $\frac12(r_j-x_j\beta_j)'(r_j-x_j\beta_j)+\frac{\lambda}{2}\beta_j^2$. Terms involving only the fixed coefficients do not affect the minimizer.

Expand the quadratic.
The terms involving $\beta_j$ are $-\beta_j x_j'r_j+\frac12\beta_j^2 x_j'x_j+\frac{\lambda}{2}\beta_j^2$.

Differentiate and set the derivative to zero.
$-x_j'r_j+(x_j'x_j+\lambda)\beta_j=0$, so the minimizing update is $\displaystyle \beta_j \leftarrow \frac{x_j'r_j}{x_j'x_j+\lambda}$.

Coordinate-descent update: With the objective defined above, the exact minimizer in coordinate $j$, holding all other coefficients fixed, is $$ \beta_j \leftarrow \frac{x_j'\left(y-\sum_{k\ne j}x_k\beta_k\right)} {x_j'x_j+\lambda}. $$ For $\lambda>0$, the denominator is positive. If $\lambda=0$, the usual least-squares coordinate update applies when $x_j'x_j>0$; if $x_j$ is the zero vector, that coordinate is not determined by the residual fit.

The justification also explains the shrinkage mechanism. For an ordinary least-squares coordinate update, the denominator is $x_j'x_j$. Ridge adds $\lambda$, making the denominator larger for $\lambda>0$. The numerator is the association between $x_j$ and the partial residual; the penalty reduces the size of the update without changing that numerator.

An equivalent implementation maintains the current residual $e=y-\sum_k x_k\beta_k$. Before updating $j$, add the old contribution back to form $r_j=e+x_j\beta_j$. After replacing the coefficient, update $e$ by subtracting $x_j$ times the coefficient change. This bookkeeping is useful, but the partial residual must exclude the current contribution.

Scaling and the Intercept

Some texts define the ridge objective with the residual term divided by $n$, the number of observations. Under

Q_n(\beta)=\frac{1}{2n}\left\|y-\sum_{j=1}^{p}x_j\beta_j\right\|^2+\frac{\lambda}{2}\sum_{j=1}^{p}\beta_j^2,

the coordinate update is $\beta_j \leftarrow x_j'r_j/(x_j'x_j+n\lambda)$. This follows by multiplying the whole objective by $n$: the residual term becomes $\frac12\|y-X\beta\|^2$, while the penalty becomes $\frac{n\lambda}{2}\sum_j\beta_j^2$. Thus, omitting or adding $n$ without first checking the objective convention changes the fitted coefficients.

If the model includes an intercept $\alpha$, it is usually left unpenalized. Holding the slopes fixed, its least-squares update is the mean residual after accounting for those slopes:

\alpha \leftarrow \frac{1}{n}\sum_{i=1}^{n}\left(y_i-\sum_{j=1}^{p}x_{ij}\beta_j\right).

Equivalently, if both response and predictors are centered, the intercept is their response mean on the original scale and the coordinate updates apply to the centered response and predictors. Penalizing the intercept would define a different model.

Worked Coordinate Updates

Worked Example: One Sweep With Two Predictors

A hypothetical pricing analysis uses three observations, no intercept, and the objective $Q(\beta)=\frac12\|y-x_1\beta_1-x_2\beta_2\|^2+\frac{2}{2}(\beta_1^2+\beta_2^2)$. Let $y=(3,-1,-2)'$, $x_1=(1,-1,0)'$, and $x_2=(1,1,-2)'$. Starting at $(0,0)$, make one sweep in the order $\beta_1,\beta_2$, calculate the objective at the end, and check both coordinate conditions. Method: use each current partial residual. Common mistake avoided: calculating a fitted value with a response value included in place of a predictor contribution.

For the first update, the partial residual is $r_1=y$. We have $x_1'y=3+1+0=4$ and $x_1'x_1=1+1+0=2$. Therefore,

\beta_1=\frac{4}{2+2}=1.

Now form the partial residual for the second coordinate: $r_2=y-x_1\beta_1=(3,-1,-2)'-(1,-1,0)'=(2,0,-2)'$. Then $x_2'r_2=2+0+4=6$, and $x_2'x_2=1+1+4=6$. Thus,

\beta_2=\frac{6}{6+2}=\frac34.

The fitted values are $x_1\beta_1+x_2\beta_2=(7/4,-1/4,-3/2)'$. The residuals are $y-\hat y=(5/4,-3/4,-1/2)'$, so

\text{RSS}=\frac{25}{16}+\frac{9}{16}+\frac{1}{4}=\frac{19}{8}, \qquad Q=\frac12\left(\frac{19}{8}\right)+\frac{2}{2}\left(1+\frac{9}{16}\right) =\frac{19}{16}+\frac{25}{16}=\frac{11}{4}.

For a coordinatewise minimum, the residual inner product with $x_j$ must equal $\lambda\beta_j$. Here $x_1'e=5/4+3/4=2=2\beta_1$, and $x_2'e=5/4-3/4+(-2)(-1/2)=3/2=2\beta_2$. Both conditions hold after this sweep. As a check, the residual sum of squares and penalty parts add to $11/4$, as calculated.

Worked Example: Ridge Shrinkage With Orthogonal Predictors

A hypothetical study models a centered response $y=(2,0,-2)'$ using centered predictors $x_1=(1,0,-1)'$ and $x_2=(1,-2,1)'$, with no intercept and $\lambda=2$. Starting from zero, make one sweep, compare the first coefficient with its unpenalized coordinate update, and check the objective. Method: update using the partial residual. Common mistake avoided: assuming a ridge update equals the least-squares update just because predictors are orthogonal.

The initial partial residual for $\beta_1$ is $y$. The required inner products are $x_1'y=2+0+2=4$ and $x_1'x_1=2$, so $\beta_1=4/(2+2)=1$. Without the penalty, the corresponding coordinate update would be $4/2=2$.

For the second coordinate, $x_1'x_2=1+0-1=0$, so the predictors are orthogonal. The partial residual is $r_2=y-x_1=(1,0,-1)'$. Hence $x_2'r_2=1+0-1=0$, $x_2'x_2=1+4+1=6$, and $\beta_2=0/(6+2)=0$.

The fitted vector is $(1,0,-1)'$, giving residual $(1,0,-1)'$ and residual sum of squares $2$. The penalty is $2(1^2+0^2)/2=1$, so $Q=2/2+1=2$. The checks are $x_1'e=2=2\beta_1$ and $x_2'e=0=2\beta_2$. Orthogonality makes the coordinates independent of one another’s current values, but the ridge penalty still changes each least-squares update.

Worked Example: Why Correlated Predictors Require Repeated Sweeps

For a hypothetical two-observation analysis with no intercept, let $y=(2,1)'$, $x_1=(1,0)'$, $x_2=(1,1)'$, and $\lambda=1$. Starting from zero, carry out two sweeps in the order $\beta_1,\beta_2$, evaluate the objective after the second sweep, and decide whether both coordinates are at their conditional minima. Method: recalculate the partial residual after every update. Common mistake avoided: treating a full sweep as a guarantee that every coordinate remains optimal after later coefficients change.

At the start of the first sweep, $\beta_1=2/(1+1)=1$. Its update uses $x_1'y=2$ and $x_1'x_1=1$. For $\beta_2$, the partial residual is $y-x_1=(1,1)'$, so $x_2'r_2=2$ and $x_2'x_2=2$. Therefore $\beta_2=2/(2+1)=2/3$.

For the second sweep, update $\beta_1$ first. With $\beta_2=2/3$, its partial residual is $y-x_2(2/3)=(4/3,1/3)'$. Thus $\beta_1=(4/3)/(1+1)=2/3$. Next, the partial residual for $\beta_2$ is $y-x_1(2/3)=(4/3,1)'$. Since $x_2'r_2=7/3$, the new value is $\beta_2=(7/3)/(2+1)=7/9$.

At the end of the second sweep, the fitted vector is $(2/3+7/9,7/9)'=(13/9,7/9)'$, and the residual is $(5/9,2/9)'$. Therefore, the residual sum of squares is $25/81+4/81=29/81$. The penalty contribution is $( (2/3)^2+(7/9)^2 )/2=(36/81+49/81)/2=85/162$. The objective is $29/162+85/162=114/162=19/27$.

The second coordinate is at its conditional minimum because $x_2'e=5/9+2/9=7/9=\beta_2$. But the first is not: $x_1'e=5/9$, whereas $\lambda\beta_1=2/3$. A further sweep is needed. The first update in that sweep is $\beta_1=(2-7/9)/2=11/18$. This check shows why convergence is assessed across successive sweeps rather than assumed after one pass through the coefficients.

Reading the Updates Correctly

The coordinate formula is an exact minimizer for one coefficient at a time; it is not, in general, the simultaneous solution obtained by updating all coefficients from the same old residual. In a sweep, each update uses the most recently available values. With correlated predictors, changing one coefficient changes the partial residuals for the others, so a coefficient that was optimal earlier in a sweep may need updating again.

For $\lambda>0$, the full ridge objective is a strictly convex quadratic in the slopes, so it has a unique global minimizer. Repeated exact coordinate minimization is a way to reach that minimizer. In practical computation, one stops when coefficient changes or objective changes are sufficiently small; a small change is a numerical stopping rule, not a different coordinate formula.

Check the objective scaling. The denominator is $x_j'x_j+\lambda$ for the half-RSS convention used here, and $x_j'x_j+n\lambda$ for the half-mean-RSS convention.
Use the partial residual. It subtracts all other predictors’ current contributions, not the current contribution $x_j\beta_j$.
Do not penalize the intercept by default. Its update is the mean residual after accounting for the slopes.
Do not confuse one coordinate update with a complete solution. A later update can change the best value of an earlier coordinate.

Key takeaway: Ridge coordinate descent replaces the ordinary least-squares denominator $x_j'x_j$ with $x_j'x_j+\lambda$ under the half-RSS objective. The numerator remains the predictor’s inner product with its current partial residual. Correct scaling and residual bookkeeping are essential.

Check Your Understanding

For each problem, use the objective convention stated in the question and check the arithmetic before comparing with the answer.

With no intercept, let $x=(1,-1,1)'$, $y=(2,0,1)'$, and $\lambda=1$. Starting from coefficient zero, find the ridge coordinate update and the resulting residual vector. (Answer: $\beta=3/4$, residual $(5/4,3/4,1/4)'$.)
For $y=(2,1,0)'$, $x_1=(1,0,1)'$, $x_2=(0,1,1)'$, and $\lambda=1$, use the half-RSS objective and start at zero. Update $\beta_1$ and then $\beta_2$. (Answer: $\beta_1=2/3$, then $\beta_2=1/9$.)
An objective is $Q_n=\|y-X\beta\|^2/(2n)+\lambda\|\beta\|^2/2$, with $n=4$. For one coordinate, suppose $x_j'x_j=8$, $x_j'r_j=6$, and $\lambda=1/2$. Find the update and identify the denominator. (Answer: denominator $8+4(1/2)=10$; update $6/10=3/5$.)
A three-observation model has response values $(5,7,9)$, a single predictor with values $(0,1,2)$, slope fixed at $2$, and an unpenalized intercept. Find the intercept that minimizes residual sum of squares. (Answer: $\alpha=\bar y-2\bar x=7-2(1)=5$.)

What You'll Learn