KKT Conditions for Lasso Selection

Why the KKT Conditions Matter

Lasso does more than shrink regression coefficients: its absolute-value penalty can set coefficients exactly to zero. The Karush–Kuhn–Tucker (KKT) conditions give a precise way to tell whether a proposed coefficient vector minimizes the lasso objective and to characterize which predictors are active, inactive, or at the boundary of selection.

These conditions are especially useful when predictors are correlated. A coefficient cannot be assessed from its own association with the response alone: the relevant quantity is its association with the residual after accounting for all the other fitted coefficients. The conditions express that distinction directly. The discussion is aligned with the SOA Exam PA (Predictive Analytics) syllabus.

Definition: Let $y$ be a response vector with $n$ observations, let $X$ be a design matrix with $p$ predictor columns, and let $\beta=(\beta_1,\ldots,\beta_p)^\mathsf{T}$ be the coefficient vector. Assume the response and predictor columns have been centered, so an intercept can be fitted separately and is not penalized. For $\lambda>0$, use the lasso objective $$ Q(\beta)=\frac{1}{2n}\|y-X\beta\|_2^2+\lambda\sum_{j=1}^{p}|\beta_j|. $$ The residual vector at $\beta$ is $r=y-X\beta$. A coefficient is active if it is nonzero and inactive if it is zero.

The factor $1/(2n)$ is part of the objective convention used here. Changing the objective’s scale changes the numerical scale of $\lambda$, so the KKT equations must always be matched to the objective actually being minimized. Define the scaled predictor–response and predictor–predictor products $z=X^\mathsf{T}y/n$ and $G=X^\mathsf{T}X/n$. The residual correlation for predictor $j$, in this convention, is $X_j^\mathsf{T}r/n$.

Deriving the Lasso KKT Conditions

The squared-error part of $Q$ is differentiable, but $|\beta_j|$ is not differentiable at zero. Its subgradient is the ordinary sign when $\beta_j\ne 0$, and the interval $[-1,1]$ when $\beta_j=0$. This interval is what allows the lasso optimum to have zero coefficients.

Theorem: A vector $\hat\beta$ minimizes the lasso objective if and only if, for every predictor $j$, $$ \frac{X_j^\mathsf{T}(y-X\hat\beta)}{n}= \begin{cases} \lambda\,\operatorname{sign}(\hat\beta_j), & \hat\beta_j\ne 0,\\ \text{a value in }[-\lambda,\lambda], & \hat\beta_j=0. \end{cases} $$ Equivalently, an active coefficient has residual correlation equal to $\lambda$ in its sign direction, while an inactive coefficient must have absolute residual correlation at most $\lambda$.

Here is why the condition holds. The gradient of the squared-error term is $X^\mathsf{T}(X\beta-y)/n$. At a minimum, the negative of this gradient must be balanced by $\lambda$ times a subgradient of the absolute-value penalty. In coordinate $j$, that balance is $(X_j^\mathsf{T}r/n)=\lambda s_j$, where $s_j=\operatorname{sign}(\beta_j)$ if $\beta_j\ne 0$, and $s_j\in[-1,1]$ if $\beta_j=0$. Substituting these two forms of $s_j$ gives the stated cases.

This condition is sufficient as well as necessary: the objective is convex, and a zero subgradient is a global-minimum condition for a convex function. Thus a candidate satisfying all coordinates’ conditions is a lasso minimizer. If $G$ is positive definite, the squared-error term is strictly convex, so the minimizer is unique. If $G$ is not positive definite, KKT still characterizes minimizers, but the coefficient vector need not be unique.

\frac{X^\mathsf{T}(y-X\hat\beta)}{n} =z-G\hat\beta

This expression makes the role of the other fitted coefficients explicit: the residual correlation for predictor $j$ is $z_j-\sum_{k=1}^p G_{jk}\hat\beta_k$. When predictors are correlated, changing one coefficient can change the residual correlations of other predictors, because the off-diagonal entries of $G$ are not zero.

Compute the residual correlations.
For a proposed $\hat\beta$, calculate $c_j=X_j^\mathsf{T}(y-X\hat\beta)/n$, or use $c=z-G\hat\beta$.

Check active coordinates.
If $\hat\beta_j>0$, require $c_j=\lambda$. If $\hat\beta_j<0$, require $c_j=-\lambda$.

Check zero coordinates.
If $\hat\beta_j=0$, require $|c_j|\leq\lambda$. A strict inequality means the coordinate is strictly inactive at this solution; equality places it on the KKT boundary.

Verify the whole vector.
Every coordinate must pass. A failed condition means the proposed vector is not a minimizer, even if some individual coordinates appear plausible.

Worked Applications

Worked Example: Checking an Active Predictor and a Strictly Inactive Predictor

Suppose the scaled predictor products and predictor–response products are $G=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix}$ and $z=(1.5,0.5)^\mathsf{T}$. For $\lambda=0.5$, test the proposed coefficient vector $\hat\beta=(1,0)^\mathsf{T}$. State which predictor is active and whether the vector is a minimizer.

Method. Compute $G\hat\beta$, then subtract it from $z$ to obtain the residual correlations. The matrix is positive definite because its determinant is $1-0.5^2=0.75>0$.

First, $G\hat\beta=(1,0.5)^\mathsf{T}$. Therefore, $c=z-G\hat\beta=(1.5-1,\;0.5-0.5)^\mathsf{T}=(0.5,0)^\mathsf{T}$.

Predictor 1 is active and its coefficient is positive. Its required residual correlation is $+\lambda=0.5$, which matches $c_1=0.5$. Predictor 2 is inactive, and its residual correlation satisfies $|c_2|=0<0.5=\lambda$. Both KKT conditions hold, so $\hat\beta=(1,0)^\mathsf{T}$ is a minimizer. Since $G$ is positive definite, it is the unique minimizer. The method avoids the mistake of judging predictor 2 using its original product $z_2$ alone; the relevant value is its residual correlation after fitting predictor 1.

Worked Example: Determining When a Single-Predictor Selected Set Is Valid

Let $G=\begin{pmatrix}1&0.6\\0.6&1\end{pmatrix}$ and $z=(1.4,0.9)^\mathsf{T}$. Consider the proposed selected set containing predictor 1 only, with $\hat\beta=(1.4-\lambda,0)^\mathsf{T}$ and a positive first coefficient. Find the range of positive $\lambda$ values for which this proposed form satisfies KKT. Then check what happens at $\lambda=0.1$.

Method. For the active first predictor, its residual correlation must equal $\lambda$. With the second coefficient zero, the first residual correlation is $1.4-\hat\beta_1$. Setting it equal to $\lambda$ gives $\hat\beta_1=1.4-\lambda$, as proposed. Positivity requires $\lambda<1.4$.

The second predictor’s residual correlation is $c_2=0.9-0.6\hat\beta_1$. Substituting the proposed coefficient gives $c_2=0.9-0.6(1.4-\lambda)=0.06+0.6\lambda$. For the zero coefficient to satisfy KKT, $|c_2|\leq\lambda$. Since $\lambda>0$, $c_2>0$, so this reduces to $0.06+0.6\lambda\leq\lambda$, or $\lambda\geq0.15$. Thus the proposed one-predictor form satisfies KKT for $0.15\leq\lambda<1.4$.

At $\lambda=0.15$, $\hat\beta_1=1.25$ and $c_2=0.06+0.6(0.15)=0.15$. The zero coefficient is on the boundary. For $\lambda=0.1$, the proposed value is $\hat\beta=(1.3,0)^\mathsf{T}$, and $c_2=0.9-0.6(1.3)=0.12>0.1$. This violates the zero-coordinate condition, so that proposed selected set is not valid at $\lambda=0.1$.

To verify the alternative with both coefficients positive at $\lambda=0.1$, their active KKT equations are $G\hat\beta=z-0.1(1,1)^\mathsf{T}=(1.3,0.8)^\mathsf{T}$. Solving gives $\hat\beta_1=(1.3-0.6(0.8))/(1-0.6^2)=0.82/0.64=1.28125$ and $\hat\beta_2=(0.8-0.6(1.3))/(1-0.6^2)=0.02/0.64=0.03125$. Both are positive. Substitution gives $1.28125+0.6(0.03125)=1.3$ and $0.6(1.28125)+0.03125=0.8$, so both residual correlations equal $0.1$, as required. The calculation checks the candidate directly rather than assuming that a failed one-predictor set must be repaired in only one particular way.

Worked Example: Avoiding a Residual-Correlation Sign Error

Suppose $G=\begin{pmatrix}2&0.5\\0.5&1\end{pmatrix}$, $z=(1.25,0.45)^\mathsf{T}$, and $\lambda=0.25$. Test $\hat\beta=(0.5,0)^\mathsf{T}$, and explain why the sign of the active residual correlation matters.

Method. Calculate $G\hat\beta=(1,0.25)^\mathsf{T}$, so $c=z-G\hat\beta=(1.25-1,\;0.45-0.25)^\mathsf{T}=(0.25,0.20)^\mathsf{T}$. The first coefficient is positive, so its correlation must be $+\lambda=0.25$, which it is. The second coefficient is zero, and $|0.20|<0.25$, so it satisfies the inactive condition. The vector is a minimizer. The matrix is positive definite because its determinant is $2(1)-0.5^2=1.75>0$, so this minimizer is unique.

A common sign error is to differentiate the squared-error term as $X^\mathsf{T}(X\beta-y)/n$, obtain the negative of the residual correlation, and then incorrectly require the residual correlation itself to be $-\lambda$ for a positive coefficient. The stationarity equation is $X^\mathsf{T}(X\beta-y)/n+\lambda s=0$. Rearranging it gives $X^\mathsf{T}(y-X\beta)/n=\lambda s$, so a positive coefficient requires $+\lambda$, not $-\lambda$. The method here avoids that error by defining the residual correlation first and applying its sign rule consistently.

Interpreting Zero and Boundary Coefficients

The zero-coordinate condition has two useful cases. If $|c_j|<\lambda$, the KKT inequality is strict: predictor $j$ is inactive at the candidate solution and is not at the selection boundary for that value of $\lambda$. If $|c_j|=\lambda$ while $\hat\beta_j=0$, the coordinate is on the boundary and is eligible to enter the selected set as the optimization or penalty level changes. Boundary status does not by itself guarantee that the coefficient becomes nonzero; the other predictors’ coefficients and residual correlations also matter.

For an active coefficient, equality is mandatory, not optional. A positive coefficient must have residual correlation $+\lambda$, and a negative coefficient must have residual correlation $-\lambda$. Conversely, merely observing a predictor–response correlation with magnitude greater than $\lambda$ does not determine the final coefficient or prove that a particular proposed vector is optimal. KKT applies to residual correlations computed using the full candidate vector.

KKT conditions are tied to the chosen predictor scale and objective convention. If the squared-error term is written without division by $n$, the corresponding residual-correlation equations have a different scale. Similarly, rescaling a predictor changes its correlations and can change which coefficients satisfy the conditions for a fixed numerical penalty. Before interpreting a numerical $\lambda$, identify both the objective convention and the predictor scaling.

Key takeaway: For the objective $ \|y-X\beta\|_2^2/(2n)+\lambda\|\beta\|_1 $, an active coefficient must match its signed penalty with its residual correlation, while a zero coefficient’s residual correlation must lie between $-\lambda$ and $+\lambda$. Check every coordinate using the same candidate coefficient vector.

Check Your Understanding

For each item, apply the KKT conditions under the objective convention defined above.

Let $G=I$, $z=(0.7,-0.2)^\mathsf{T}$, and $\lambda=0.3$. Does the all-zero vector satisfy KKT? (Answer: No; the first zero coefficient has residual correlation $0.7>0.3$.)
Let $G=\begin{pmatrix}1&0.4\\0.4&1\end{pmatrix}$, $z=(1.1,0.2)^\mathsf{T}$, and $\lambda=0.3$. Test $\hat\beta=(0.8,0)^\mathsf{T}$. (Answer: It satisfies KKT; the residual correlations are $(0.3,-0.12)^\mathsf{T}$, so predictor 1 is active and predictor 2 is strictly inactive.)
Let $G=I$, $z=(-0.6,0.1)^\mathsf{T}$, and $\lambda=0.2$. Test $\hat\beta=(-0.4,0)^\mathsf{T}$. (Answer: It satisfies KKT; the residual correlations are $(-0.2,0.1)^\mathsf{T}$, matching the negative active coefficient and the zero-coordinate bound.)
Let $G=I$, $z=(0.5,-0.1)^\mathsf{T}$, and $\lambda=0.5$. For $\hat\beta=(0,0)^\mathsf{T}$, identify any boundary coordinate. (Answer: Predictor 1 is on the boundary because its residual correlation is $0.5=\lambda$; predictor 2 is strictly inactive.)
Let $G=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix}$, $z=(1,0.7)^\mathsf{T}$, and propose $\hat\beta=(1-\lambda,0)^\mathsf{T}$ with a positive first coefficient. Find the positive $\lambda$ range for which this form satisfies KKT. (Answer: $0.4\leq\lambda<1$; at $0.4$ the second coordinate is on the boundary, and above $0.4$ it is strictly inactive.)

What You'll Learn