The Lasso and MM Algorithms - 2 of 5

Part 2: Auxiliary KKT Conditions

Anant Mathur · July 2026

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

The lasso KKT conditions from Part 1 can be reproduced in a different variable: one nonnegative scale $\gamma_j$ per coefficient. This auxiliary system separates activation from sign and gives the MM construction its natural coordinates.

From coefficients to nonnegative scales

Introduce $\v\gamma=(\gamma_1,\ldots,\gamma_p)^\top\in\bb{R}_+^p$ and define

$$ \m\Gamma:=\operatorname{diag}(\sqrt{\gamma_1},\ldots,\sqrt{\gamma_p}), $$ $$ \begin{aligned} \m G(\v\gamma) &:=(\m I+\m X\m\Gamma^2\m X^\top)^{-1}\\ &=\left(\m I+\sum_{j=1}^p\gamma_j\v x_j\v x_j^\top\right)^{-1}. \end{aligned} $$

Recover a coefficient vector from $\v\gamma$ by

$$ \begin{aligned} \v\beta(\v\gamma) &:=\m\Gamma^2\m X^\top\m G(\v\gamma)\v y,\\ \beta_j(\v\gamma) &=\gamma_j\v x_j^\top\m G(\v\gamma)\v y. \end{aligned} $$

The identity $(\m I+\m X\m\Gamma^2\m X^\top)\m G=\m I$ then gives

$$ \v r(\v\gamma) :=\v y-\m X\v\beta(\v\gamma) =\m G(\v\gamma)\v y. $$

Thus the same quantity controls both the coefficient and its residual correlation. Write

$$ \tau_j(\v\gamma):= |\v x_j^\top\m G(\v\gamma)\v y| =|\v x_j^\top\v r(\v\gamma)|. $$

The auxiliary objective

Consider the convex objective on the nonnegative orthant

$$ \begin{aligned} g(\v\gamma) &:=\v y^\top\m G(\v\gamma)\v y +\alpha^2\v 1^\top\v\gamma,\\ &\hspace{6em}\v\gamma\in\bb{R}_+^p. \end{aligned} $$

Because $\partial\m G/\partial\gamma_j=-\m G\v x_j\v x_j^\top\m G$, its coordinate derivative has the particularly simple form

$$ \begin{aligned} \frac{\partial g}{\partial\gamma_j} &=\alpha^2-(\v x_j^\top\m G(\v\gamma)\v y)^2\\ &=\alpha^2-\tau_j(\v\gamma)^2. \end{aligned} $$

The auxiliary KKT conditions

The constraint $\gamma_j\ge0$ requires a zero derivative in the interior and a nonnegative one at the boundary. Since $\alpha$ and $\tau_j$ are nonnegative, the KKT conditions reduce to

Positive scale

$$\widehat\gamma_j>0 \quad\Longrightarrow\quad \tau_j(\widehat{\v\gamma})=\alpha.$$

An active scale sits exactly on the auxiliary KKT boundary.

Zero scale

$$\widehat\gamma_j=0 \quad\Longrightarrow\quad \tau_j(\widehat{\v\gamma})\le\alpha.$$

An excluded scale may lie anywhere below the boundary.

It is useful to name the signed auxiliary KKT gap $\xi_j(\v\gamma):=\alpha-\tau_j(\v\gamma)$. A positive scale requires $\xi_j=0$; a zero scale is valid when $\xi_j\ge0$ and violating when $\xi_j<0$.

Why this is the same certificate

If $\gamma_j>0$, then $\beta_j=\gamma_j\v x_j^\top\v r$ has the same sign as the residual correlation. The equality $\tau_j=\alpha$ therefore becomes $\v x_j^\top\v r=\alpha\operatorname{sign}(\beta_j)$. If $\gamma_j=0$, then $\beta_j=0$ and $\tau_j\le\alpha$ becomes $|\v x_j^\top\v r|\le\alpha$. These are exactly the two lasso KKT cases from Part 1.

Exact recovery. If $\widehat{\v\gamma}$ minimizes $g$, then $\widehat{\v\beta}=\widehat{\m\Gamma}^2\m X^\top \m G(\widehat{\v\gamma})\v y$ minimizes the original lasso objective, with $\widehat\beta_j=0$ exactly when $\widehat\gamma_j=0$.
The computational question. The auxiliary objective is convex, but the inverse inside $\m G(\v\gamma)$ couples every coordinate. Part 3 introduces the general majorize-minimize framework used to replace that difficult objective by a tractable upper bound.
← Part 1: Lasso and Coordinate Descent Part 3: MM Algorithms →