The Lasso and MM Algorithms - 1 of 5

Part 1: The Lasso and Coordinate Descent

Anant Mathur · July 2026

1 · Lasso + CD 2 · Auxiliary KKT 3 · MM Algorithms 4 · A Separable Bound 5 · Optimal Weights

The lasso is one of the most familiar tools in sparse regression, and cyclic coordinate descent is the engine behind widely used implementations such as glmnet. The reason is simple: once every other coefficient is fixed, the remaining one-dimensional lasso problem has an exact soft-thresholding solution. Its KKT conditions then say precisely which coefficients should be zero and when the algorithm has reached the optimum.

Series. This series develops the scalar-predictor specialization of the MM framework introduced in our source paper with Sarat Moka and Zdravko Botev. Throughout, we work with the ordinary lasso: one standardized predictor per coefficient. [PDF]

The model

Let $\v y \in \bb{R}^n$ be a centred response and $\m X = [\v x_1,\ldots,\v x_p] \in \bb{R}^{n\times p}$ a centred design matrix. Following the standard lasso setup, scale every column so that $\|\v x_j\|_2=1$. The linear model is

$$ \v y = \m X\v\beta + \v\epsilon, \qquad \v\epsilon \sim \c N(\v 0,\sigma^2\m I_n). $$

The least-squares estimate uses every predictor. The lasso of Tibshirani (1996) adds an $\ell_1$ penalty:

$$ \begin{aligned} \widehat{\v\beta} &= \argmin_{\v\beta\in\bb{R}^p} f(\v\beta),\\ f(\v\beta) &:= \frac{1}{2n}\|\v y-\m X\v\beta\|_2^2 + \lambda\|\v\beta\|_1. \end{aligned} $$

Soft-thresholding

Write $\alpha:=n\lambda$ and define the soft-thresholding operator

$$ S_\alpha(z) := \operatorname{sign}(z)(|z|-\alpha)_+. $$

This operator is the exact solution of the scalar lasso problem

$$ \argmin_{u\in\bb R} \left\{\frac12(z-u)^2+\alpha|u|\right\} =S_\alpha(z). $$
The threshold performs selection. If $|z|\le\alpha$, the solution is zero. Otherwise $z$ is shrunk toward zero by exactly $\alpha$.

The lasso KKT conditions

For the full lasso with correlated predictors, $\v x_j^\top\v y$ does not tell the whole story. Whether coefficient $j$ should be zero depends on the residual left by all the other coefficients. Let $\v r(\v\beta):=\v y-\m X\v\beta$. Since the absolute value is not differentiable at zero, its coordinate-wise subgradient is

$$ \partial |\beta_j| = \begin{cases} \{\operatorname{sign}(\beta_j)\}, & \beta_j\ne0,\\[0.3em] [-1,1], & \beta_j=0. \end{cases} $$

Setting the subgradient of the convex lasso objective to zero gives the necessary and sufficient optimality certificate

$$ \v x_j^\top \v r(\widehat{\v\beta}) \in \alpha\,\partial|\widehat\beta_j|, \qquad j=1,\ldots,p. $$

Active coefficient

$$\widehat\beta_j\ne0 \quad\Longrightarrow\quad \v x_j^\top\widehat{\v r} =\alpha\operatorname{sign}(\widehat\beta_j).$$

The residual correlation sits exactly on a threshold boundary.

Zero coefficient

$$\widehat\beta_j=0 \quad\Longrightarrow\quad |\v x_j^\top\widehat{\v r}|\le\alpha.$$

The residual correlation may lie anywhere inside the threshold interval.

Coordinate descent: one coordinate at a time

Coordinate descent is a general strategy for minimizing a multivariable objective $F:\bb R^p\to\bb R$. At the current point $\v\beta$, choose a coordinate $j$, keep every other coordinate fixed, and minimize only along the $j$th axis:

$$ u_j^\star \in\argmin_{u\in\bb R} F(\beta_1,\ldots,\beta_{j-1},u,\beta_{j+1},\ldots,\beta_p), \qquad \beta_j\leftarrow u_j^\star. $$

The new point differs from the old one in just one entry, so the path consists of axis-aligned moves. A cyclic scheme visits $1,\ldots,p$ in order; randomized and greedy rules choose the next coordinate differently. One pass through all coordinates is called a sweep, and sweeps are repeated until the updates or an optimality measure are small.

For the lasso, the one-dimensional solution is explicit

Return now to the standardized lasso and write $\alpha=n\lambda$. When coordinate $j$ is selected, all other coefficients are fixed. Their contribution is removed from the response to form the partial residual

$$ \v r_{\neg j} :=\v y-\sum_{k\ne j}\v x_k\beta_k =\v r+\v x_j\beta_j. $$

The remaining one-dimensional lasso problem has the soft-thresholded solution

$$ \begin{aligned} \beta_j^{\mathrm{new}} &=\argmin_{u\in\bb R} \left\{\frac12\|\v r_{\neg j}-\v x_j u\|_2^2+\alpha|u|\right\}\\ &=S_\alpha(\v x_j^\top\v r_{\neg j}) =S_\alpha(\v x_j^\top\v r+\beta_j), \qquad \|\v x_j\|_2=1. \end{aligned} $$

Only one coefficient changes, so the residual is updated without recomputing $\m X\v\beta$:

$$ \v r\leftarrow\v r-\v x_j (\beta_j^{\mathrm{new}}-\beta_j^{\mathrm{old}}). $$

Thus the general coordinate-descent step becomes especially cheap for the lasso: compute one residual correlation, soft-threshold it, and update the residual. Cycling these exact scalar solutions drives the full objective downward.

Watch the fixed-coordinate updates

The example below follows coordinate descent with two correlated predictors. Each move minimizes one scalar subproblem exactly while the other coefficient stays fixed.

Left: coordinate descent traces an axis-aligned path because only one coefficient moves at a time; orange segments update $\beta_1$ and green segments update $\beta_2$. Right: the corresponding scalar objective is shown with the other coefficient fixed. The open point is the exact soft-thresholded minimizer used for the next update. The status line reports the largest remaining lasso KKT discrepancy.

Why look beyond coordinate descent?

Cyclic coordinate descent is reliable and often very fast. But a sweep moves one coefficient at a time. With strongly correlated predictors, information can pass slowly between coordinates, and many sweeps may be required before every KKT condition is tight.

The next move. Part 2 replaces $\v\beta$ by one nonnegative auxiliary scale $\gamma_j$ per coefficient. The resulting KKT system is equivalent to the lasso certificate above, but it opens the door to concurrent MM updates.
← Back to blog Part 2: Auxiliary KKT Conditions →