Coordinate Descent - The Statistics Notebook

The full LASSO problem couples the coefficients through the fitted values. Coordinate descent makes that problem manageable by optimizing one coefficient exactly while keeping the others fixed, then repeating the cycle.

Isolating one coefficient¶

Use the half sum objective defined in Sparse Regression and Trees. For coordinate $j$ , define a partial residual that omits its current contribution:

r^{(j)}=y−\sum_{\ell\ne j}x_\ell\beta_\ell.

(1)

Only the following part of the objective depends on the replacement value $b$ :

q_j(b)=\frac12\lVert r^{(j)}−x_jb\rVert^2+\lambda|b|.

(2)

Set $a_j=x_j^\top x_j$ and $c_j=x_j^\top r^{(j)}$ . Expanding the square gives

q_j(b)=\frac{a_j}{2}b^2−c_jb+\lambda|b|+\text{constant}.

(3)

Assume $a_j>0$ . A zero column contains no predictive information and can be removed.

Deriving the update¶

If $b>0$ , differentiation gives $a_jb−c_j+\lambda=0$ . The solution $b=(c_j−\lambda)/a_j$ is positive only when $c_j>\lambda$ .

If $b<0$ , the derivative is $a_jb−c_j−\lambda$ . The solution $b=(c_j+\lambda)/a_j$ is negative only when $c_j<−\lambda$ .

At $b=0$ , the subgradient contains zero precisely when $|c_j|\leq\lambda$ . Combining the cases,

\boxed{\beta_j\leftarrow\frac{S(c_j,\lambda)}{a_j}.}

(4)

If the column has squared norm one, the denominator disappears. Centering alone does not make this true. Scaling to empirical variance one commonly gives a squared column norm of $n$ or $n−1$ , depending on the convention.

Updating with the full residual¶

Maintaining $r=y−X\beta$ avoids rebuilding the partial sum. Since $r^{(j)}=r+x_j\beta_j$ ,

c_j=x_j^\top r+a_j\beta_j.

(5)

After replacing $\beta_j^{\mathrm{old}}$ by $\beta_j^{\mathrm{new}}$ , update

r\leftarrow r−x_j(\beta_j^{\mathrm{new}}−\beta_j^{\mathrm{old}}).

(6)

For example, with $a_j=4$ , $c_j=6$ , and $\lambda=2$ , the update is $(6−2)/4=1$ . With the same $a_j$ and $\lambda$ but $c_j=1.5$ , the update is zero. These are coordinate calculations with the other coefficients held fixed, not complete model fits.

Active sets and optimality checks¶

The active set is $A=\{j:\beta_j\ne0\}$ . Once a sparse candidate model is found, many iterations can concentrate on these coordinates. But a predictor outside the active set can become useful after the residual changes.

At convergence, check every coordinate against the optimality conditions. For inactive variables, $|x_j^\top r|\leq\lambda$ must hold. For active variables, the residual correlation must match $\lambda$ times the coefficient sign, within numerical tolerance.

A screening rule can temporarily omit variables, but its guarantees matter. Some rules require a later check that restores excluded variables if they violate optimality. Keeping only the first active set forever is not a valid general algorithm.

What may be precomputed¶

The identity

x_j^\top r=x_j^\top y−\sum_{\ell\in A}(x_j^\top x_\ell)\beta_\ell

(7)

connects the updates to feature inner products. Precomputing them can help when the design is moderate in size. Storing the entire Gram matrix costs on the order of $p^2$ entries, which can be impractical for very large $p$ . Residual updates and sparse matrix operations avoid that requirement.

Computation is reduced by sparsity, warm starts, and efficient checks, but it does not become completely independent of the original number of predictors. The data must still be read, and omitted variables must be screened or checked correctly.