Coordinate Descent for Weighted Least-Squares Subproblems

Why Update One Coefficient at a Time?

Penalized Fisher scoring replaces a difficult GLM optimization step with a weighted least-squares subproblem. When there are many coefficients, solving that entire subproblem at once may be inconvenient. Coordinate descent instead updates one coefficient at a time, holding the others fixed. Each update is a one-dimensional minimization that can be computed from a partial residual.

The key bookkeeping matters: the working response and weights are fixed during a coordinate sweep, and a coefficient’s partial residual removes the contributions of all the other coefficients. The resulting update solves the current quadratic subproblem along one coordinate; it does not, by itself, solve the original GLM likelihood problem.

The Weighted Least-Squares Subproblem

Let $z_i$ be the working response, $w_i\geq 0$ its weight, $o_i$ a fixed offset, and $x_{ij}$ the value of predictor $j$ for observation $i$. Write $\beta_0$ for the intercept and $\beta_1,\ldots,\beta_p$ for the other coefficients. A typical penalized weighted least-squares criterion is

Q(\beta_0,\beta) = \frac{1}{2n}\sum_{i=1}^n w_i\left(z_i-o_i-\beta_0-\sum_{k=1}^p x_{ik}\beta_k\right)^2 +\lambda\sum_{k=1}^p p_k(\beta_k).

Here $\lambda\geq 0$ is the penalty multiplier, and each $p_k$ is the penalty contribution for coefficient $k$. The intercept is unpenalized in this displayed criterion. In a particular application, the $p_k$ and the scaling of the penalty are those specified by the penalized objective. The weights and working response are treated as fixed while minimizing $Q$.

Definition: For updating coefficient $\beta_j$, the partial residual for observation $i$ is $$ r_{ij} = z_i-o_i-\beta_0-\sum_{k\ne j}x_{ik}\beta_k. $$ It is the working response after subtracting the offset, the intercept, and every predictor contribution except the one currently being updated. Thus the residual when the candidate value of $\beta_j$ is $t$ is $r_{ij}-x_{ij}t$.

Define the weighted coordinate curvature and weighted partial-residual association by

a_j=\frac{1}{n}\sum_{i=1}^n w_i x_{ij}^2, \qquad b_j=\frac{1}{n}\sum_{i=1}^n w_i x_{ij}r_{ij}.

The value $a_j$ is positive when the predictor has nonzero weighted variation in this coordinate calculation. If $a_j=0$, the weighted least-squares term contains no information about $\beta_j$; a penalty might still determine an update, but the unpenalized least-squares formula below cannot be used.

Theorem: With all coordinates except $\beta_j$ fixed, minimizing $Q$ over $\beta_j=t$ is equivalent to minimizing $$ q_j(t)=\frac{a_j}{2}t^2-b_jt+\lambda p_j(t). $$ If this scalar objective attains its minimum, any coordinate update is a minimizer of $q_j$.

Proof. In $Q$, replace the fitted residual for observation $i$ by $r_{ij}-x_{ij}t$. The part of the objective that depends on $t$ is

\frac{1}{2n}\sum_{i=1}^n w_i(r_{ij}-x_{ij}t)^2+\lambda p_j(t).

Expanding the square gives

\frac{1}{2n}\sum_i w_i r_{ij}^2 -\frac{t}{n}\sum_i w_i x_{ij}r_{ij} +\frac{t^2}{2n}\sum_i w_i x_{ij}^2 +\lambda p_j(t).

The first term does not depend on $t$. The two remaining weighted sums are $b_j$ and $a_j$, so removing the constant gives exactly $q_j(t)$. Removing a constant does not change the set of minimizers. $\square$

Basic Coordinate Updates

With no penalty on $\beta_j$, if $a_j>0$, the scalar objective is a strictly convex quadratic. Setting its derivative to zero gives

a_jt-b_j=0, \qquad \beta_j^{\mathrm{new}}=\frac{b_j}{a_j} = \frac{\sum_i w_i x_{ij}r_{ij}}{\sum_i w_i x_{ij}^2}.

This is the weighted least-squares coefficient for the chosen predictor after the other fitted contributions have been removed. For a differentiable penalty $p_j$, an interior minimizer instead satisfies $a_jt-b_j+\lambda p_j'(t)=0$; whether that equation gives a convenient explicit update depends on the penalty.

Worked Example: An Unpenalized Slope Update

Suppose the partial residuals are $r=(2,-1,3)$, the predictor values are $x=(1,0,2)$, and the weights are $w=(1,2,1)$. There are $n=3$ observations. Hold every other coefficient fixed and update the unpenalized slope.

The weighted numerator, before division by $n$, is

\sum_i w_i x_i r_i =(1)(1)(2)+(2)(0)(-1)+(1)(2)(3)=8.

The corresponding denominator is

\sum_i w_i x_i^2=(1)(1^2)+(2)(0^2)+(1)(2^2)=5.

Therefore $\beta^{\mathrm{new}}=8/5=1.6$. To check the calculation, the weighted sum of squared partial residuals before the update is $1(2^2)+2((-1)^2)+1(3^2)=15$. After the update, the residuals are $2-1(1.6)=0.4$, $-1-0(1.6)=-1$, and $3-2(1.6)=-0.2$, giving $1(0.4^2)+2((-1)^2)+1((-0.2)^2)=2.2$. The weighted sum of squares has decreased by $12.8$.

An unpenalized intercept can also be updated as a coordinate. Define $s_i=z_i-o_i-\sum_k x_{ik}\beta_k$, holding the slopes fixed. The intercept minimizes $\sum_i w_i(s_i-\beta_0)^2$, so, provided $\sum_i w_i>0$, its update is the weighted mean $\sum_i w_i s_i/\sum_i w_i$.

Worked Example: Updating an Intercept

Suppose the working responses after subtracting the offset and all slope contributions are $s=(1,3,2)$, and the weights are $w=(1,2,1)$. The intercept update is

\beta_0^{\mathrm{new}} =\frac{\sum_i w_i s_i}{\sum_i w_i} =\frac{(1)(1)+(2)(3)+(1)(2)}{1+2+1} =\frac{9}{4}=2.25.

For example, if the old intercept was $1$, its weighted sum of squared residuals was $1(0^2)+2(2^2)+1(1^2)=9$. At $2.25$, it is $1((-1.25)^2)+2(0.75^2)+1((-0.25)^2)=2.75$. This confirms that the update reduces the intercept’s weighted least-squares contribution.

Quadratic Penalties and Coordinate Descent

For a ridge penalty contribution $p_j(t)=t^2/2$, the coordinate objective is $a_jt^2/2-b_jt+\lambda t^2/2$. If $a_j+\lambda>0$, differentiating and solving gives the explicit update

\beta_j^{\mathrm{new}}=\frac{b_j}{a_j+\lambda} = \frac{\sum_i w_i x_{ij}r_{ij}}{\sum_i w_i x_{ij}^2+n\lambda}.

The $n\lambda$ in the second expression follows from the criterion’s $1/(2n)$ scaling. Keeping track of this factor prevents updates from silently using a different penalty strength from the objective.

Worked Example: A Ridge Coordinate Update

Use the values $r=(2,-1,3)$, $x=(1,0,2)$, and $w=(1,2,1)$ from the slope example, with $n=3$. Use the criterion above and set $\lambda=1/3$, with $p_j(t)=t^2/2$. The sums already calculated give $a_j=5/3$ and $b_j=8/3$. Hence

\beta_j^{\mathrm{new}} =\frac{8/3}{5/3+1/3} =\frac{8/3}{2} =\frac{4}{3}.

The penalty reduces the update from the unpenalized value $8/5=1.6$ to $4/3$. Directly, the derivative of the coordinate objective is $(5/3)t-8/3+(1/3)t=2t-8/3$, which is zero at $t=4/3$. Its second derivative is $2>0$, so this value is the unique minimum.

A full coordinate sweep visits the intercept and coefficients in a chosen order, updating each using the latest available values of the other coordinates. For an unpenalized weighted least-squares objective, each coordinate update has a precise descent property.

Result: Suppose the weights are nonnegative and $a_j>0$. In an unpenalized weighted least-squares coordinate update, replacing the old value $t_{\mathrm{old}}$ by $t_{\mathrm{new}}=b_j/a_j$ reduces the objective by $$ Q_{\mathrm{old}}-Q_{\mathrm{new}} =\frac{a_j}{2}(t_{\mathrm{old}}-t_{\mathrm{new}})^2. $$ In particular, the update cannot increase the objective, and the decrease is strict if the coefficient changes.

Proof. The coordinate-dependent part of the objective is $q_j(t)=a_jt^2/2-b_jt$. Since $t_{\mathrm{new}}=b_j/a_j$, completing the square gives

q_j(t)=\frac{a_j}{2}\left(t-\frac{b_j}{a_j}\right)^2-\frac{b_j^2}{2a_j}.

The second term is constant in $t$. Subtracting the value at $t_{\mathrm{new}}$ from the value at $t_{\mathrm{old}}$ therefore gives $a_j(t_{\mathrm{old}}-t_{\mathrm{new}})^2/2$. All other terms in $Q$ are unchanged during this coordinate update, which proves the stated objective decrease. $\square$

How the Updates Enter GLM Optimization

In a GLM Fisher-scoring step, the current fitted means and linear predictors determine a working response and working weights. The penalized Fisher-scoring subproblem is then a weighted least-squares criterion of the form above, up to terms that do not depend on the coefficients. Coordinate descent solves that subproblem through a sequence of scalar minimizations. The subproblem’s working response and weights remain fixed during this inner sequence; they are recalculated only when the outer Fisher-scoring iteration moves to a new working approximation.

For example, in a binomial logistic model with a logit link and unit prior weights, the working weight at a current fitted mean $\mu_i$ is $\mu_i(1-\mu_i)$, and the working response is $\eta_i+(y_i-\mu_i)/[\mu_i(1-\mu_i)]$. These quantities define the weighted least-squares problem for the current outer iteration.

Worked Example: One Coordinate in a Logistic Working Subproblem

Consider three binomial observations with outcomes $y=(1,0,1)$. At the current outer iteration, suppose all three linear predictors are $0$, and update a slope with predictor values $x=(1,0,2)$, holding the intercept at $0$. The fitted means are all $1/2$. Thus every working weight is $1/4$, and the working responses are

z_i=0+\frac{y_i-1/2}{1/4}, \qquad z=(2,-2,2).

There are no other slope contributions, so these working responses are the partial residuals for this update. The weighted numerator is $(1/4)(1)(2)+(1/4)(0)(-2)+(1/4)(2)(2)=3/2$, and the weighted denominator is $(1/4)(1^2+0^2+2^2)=5/4$. The unpenalized coordinate update is therefore

\beta^{\mathrm{new}}=\frac{3/2}{5/4}=\frac{6}{5}=1.2.

This value minimizes the slope coordinate of the current logistic working least-squares problem. It is not necessarily the minimizer of the original logistic likelihood along that coordinate, because the working response and weights arose from a local Fisher-scoring approximation.

Practical Checks and Common Pitfalls

Hold the quadratic subproblem fixed.
Use the current working response, weights, offset, and penalty multiplier throughout the coordinate sweep.

Form the partial residual.
Subtract every fitted contribution other than the coefficient being updated, including the offset and intercept where applicable.

Minimize the scalar objective.
Use the weighted curvature and association, together with the actual penalty contribution for that coefficient.

Move to the next coordinate.
Use the newly updated coefficient when forming later partial residuals in the same sweep.

A common mistake is to leave the current coefficient inside its own partial residual. If one uses $z_i-o_i-\beta_0-\sum_k x_{ik}\beta_k$ and then subtracts $x_{ij}t$, the old contribution $x_{ij}\beta_j$ has already been removed and the coordinate is counted incorrectly. The correct partial residual excludes $j$ from the sum; its candidate residual is then $r_{ij}-x_{ij}t$.

Another mistake is to treat a coordinate update as a full GLM update. The weighted least-squares objective is the current quadratic subproblem, not the original likelihood. Likewise, changing the working weights after every coefficient update changes the subproblem mid-sweep. Recompute them in the outer GLM iteration, not during the inner coordinate minimizations.

Coordinate descent is useful because each step can be inexpensive even when the full coefficient vector is large. Its reliability depends on implementing the scalar objective consistently: use the correct weights, preserve the stated penalty scaling, and distinguish the fixed working subproblem from the GLM objective that generated it.

Check Your Understanding

Work through these questions using the coordinate objective and update rules.

For a fixed coordinate, explain which terms belong in its partial residual and why its current fitted contribution must be excluded.
If $a_j=4$, $b_j=6$, and the coordinate is unpenalized, calculate the update.
For a ridge contribution $p_j(t)=t^2/2$, write the coordinate update in terms of $a_j$, $b_j$, and $\lambda$.
Why must the working response and weights remain fixed during one coordinate sweep of a Fisher-scoring subproblem?
State the objective decrease for an unpenalized update and identify when that decrease is zero.