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 a coefficient's activation from its sign.

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.$$

A positive scale puts its residual correlation exactly on the threshold.

Zero scale

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

A zero scale allows its residual correlation anywhere at or below $\alpha$.

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$.

Watch a scale switch on

For a single standardized predictor everything is explicit. Write $c:=\v x^\top\v y$. The Sherman-Morrison formula gives $\m G(\gamma)\v y=\v y-\frac{\gamma c}{1+\gamma}\v x$, so the residual correlation and the auxiliary objective (dropping the constant $\|\v y\|^2$) are

$$ \tau(\gamma)=\frac{|c|}{1+\gamma}, \qquad g(\gamma)-\|\v y\|_2^2=-\frac{\gamma c^2}{1+\gamma}+\alpha^2\gamma . $$

The derivative $\alpha^2-\tau(\gamma)^2$ is negative at $\gamma=0$ exactly when $|c|>\alpha$. So the minimizer is $\widehat\gamma=\max(|c|/\alpha-1,\,0)$, and the recovered coefficient $\widehat\gamma\,c/(1+\widehat\gamma)$ equals $S_\alpha(c)$, the soft-threshold of Part 1. Move the correlation $c$ across the threshold to watch the scale leave the boundary.

Left: the auxiliary objective in the single scale $\gamma$, with the dot at its minimizer on $\gamma\ge0$. Right: the residual correlation $\tau(\gamma)$ falls as the scale grows; the dashed line is the threshold $\alpha=1$. When $|c|>\alpha$ the curve crosses the threshold at $\widehat\gamma>0$ and the coefficient is active (green). When $|c|\le\alpha$ it never reaches the threshold, the minimizer sits on the boundary $\gamma=0$, and the coefficient is zero (blue).

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 →