Karush-Kuhn-Tucker Conditions for Lasso

Why Lasso Optimality Needs a Special Condition at Zero

The lasso estimates regression coefficients by balancing fit to the observed response against a penalty on the absolute sizes of the coefficients. Its objective is convex, but the absolute-value penalty has a corner at zero. As a result, the usual differentiable first-order condition cannot be applied unchanged to every coefficient. A candidate coefficient that is zero must satisfy an inequality, while a nonzero coefficient must satisfy an equality.

These conditions are useful when a problem gives a proposed coefficient vector and asks whether it is optimal. The key is to calculate the residual correlations using the stated objective and then apply the condition appropriate to each coefficient. The factor in the condition depends on whether the residual sum of squares has been divided by two.

Definition: For response vector $y$, design matrix $X$, intercept $\beta_0$, coefficient vector $\beta=(\beta_1,\ldots,\beta_p)^\mathsf{T}$, and penalty parameter $\lambda\geq 0$, define the residual vector $r=y-\beta_0\mathbf{1}-X\beta$. Under the half-scaled lasso convention, the objective is $$ Q(\beta_0,\beta)=\frac{1}{2}r^\mathsf{T}r+\lambda\sum_{j=1}^{p}|\beta_j|. $$ The intercept is unpenalized. The KKT conditions state that $\mathbf{1}^\mathsf{T}r=0$ for an estimated intercept and, for each coefficient, $X_j^\mathsf{T}r=\lambda\operatorname{sign}(\beta_j)$ if $\beta_j\ne 0$, while $|X_j^\mathsf{T}r|\leq\lambda$ if $\beta_j=0$.

Deriving the Coordinatewise Conditions

For a differentiable least-squares objective, an optimum has zero derivative in each coefficient direction. Lasso retains this principle, but the absolute-value term is handled using its subgradient. For $b\ne 0$, the derivative of $|b|$ is $\operatorname{sign}(b)$. At $b=0$, the subdifferential of $|b|$—the set of valid supporting slopes—is the entire interval $[-1,1]$. This interval accounts for the corner rather than assigning an ordinary derivative there.

For the half-scaled objective, differentiating the squared-residual term with respect to $\beta_j$ gives $-X_j^\mathsf{T}r$. The subgradient condition for a minimum is therefore $-X_j^\mathsf{T}r+\lambda z_j=0$, where $z_j=\operatorname{sign}(\beta_j)$ for a nonzero coefficient and $z_j\in[-1,1]$ at zero. Rearranging gives the KKT conditions in the definition.

X_j^\mathsf{T}r=\lambda z_j,\qquad z_j\in \begin{cases} \{\operatorname{sign}(\beta_j)\},&\beta_j\ne 0,\\ [-1,1],&\beta_j=0. \end{cases}

The intercept has no penalty, so differentiating with respect to it gives $-\mathbf{1}^\mathsf{T}r=0$. If the response and all predictor columns have been centered, then a zero intercept satisfies this condition. If they have not been centered and the intercept is estimated, the residual sum must still be checked; the coefficient conditions alone are not enough.

Another common convention uses the unscaled objective $r^\mathsf{T}r+\lambda\sum_j|\beta_j|$. Its squared-residual derivative is twice as large, so its conditions are $2X_j^\mathsf{T}r=\lambda\operatorname{sign}(\beta_j)$ for nonzero coefficients and $|2X_j^\mathsf{T}r|\leq\lambda$ for zero coefficients. Do not mix the conditions from one convention with the objective from the other. Multiplying an objective by a positive constant does not change its minimizer, but the penalty parameter must be scaled with the entire objective if the same minimizer is to be represented.

Theorem: For either stated lasso objective, the KKT conditions are necessary and sufficient for a candidate to be a global minimizer. The objective is convex: squared error is convex, and the absolute-value penalty is convex. For a convex function, a point satisfying the subgradient condition has a supporting slope of zero and therefore cannot have a smaller objective value elsewhere. The KKT conditions certify global optimality, though they do not by themselves guarantee that the minimizing coefficient vector is unique.

Checking a Candidate Systematically

For each proposed coefficient vector, first calculate the residual using the proposed intercept and coefficients. Then calculate each residual correlation $X_j^\mathsf{T}r$. Compare it with the equality for a nonzero coefficient or the inequality for a zero coefficient, using the scaling in the stated objective. If the intercept is estimated, check its residual-sum condition as well.

Identify the objective convention.
Record whether the squared residual is $r^\mathsf{T}r$ or $\frac{1}{2}r^\mathsf{T}r$, and use the corresponding KKT conditions.

Compute the residual correlations.
Use $r=y-\beta_0\mathbf{1}-X\beta$, then calculate $X_j^\mathsf{T}r$ for each predictor.

Apply the right condition to each coordinate.
A nonzero coefficient requires equality with the signed penalty threshold; a zero coefficient requires the absolute correlation to be no greater than that threshold.

Check the intercept and conclude.
When an intercept is estimated, verify $\mathbf{1}^\mathsf{T}r=0$. If any condition fails, the candidate is not optimal; if all hold, convexity certifies a global minimum.

Worked Example: A Scaling Trap in the Unscaled Objective

Suppose centered predictors and response are used, the objective is $r^\mathsf{T}r+\lambda(|\beta_1|+|\beta_2|)$, and the cross-products are $X^\mathsf{T}X=\begin{pmatrix}3&0\\0&7\end{pmatrix}$ and $X^\mathsf{T}y=(5,1)^\mathsf{T}$. For $\lambda=2$, check the candidate $\beta=(1,0)^\mathsf{T}$. The method is to use the unscaled KKT conditions; this avoids applying the half-scaled conditions to the wrong objective.

Step 1: Calculate the residual correlations. Since $X^\mathsf{T}r=X^\mathsf{T}y-X^\mathsf{T}X\beta$, $$ X^\mathsf{T}X\beta= \begin{pmatrix}3&0\\0&7\end{pmatrix} \begin{pmatrix}1\\0\end{pmatrix} = \begin{pmatrix}3\\0\end{pmatrix}, \qquad X^\mathsf{T}r= \begin{pmatrix}5\\1\end{pmatrix} - \begin{pmatrix}3\\0\end{pmatrix} = \begin{pmatrix}2\\1\end{pmatrix}. $$

Step 2: Check the nonzero coefficient. For the unscaled objective, the condition is $2X_1^\mathsf{T}r=\lambda\operatorname{sign}(\beta_1)$. The left side is $2(2)=4$, while the right side is $2(1)=2$. Since $4\ne2$, the condition fails.

Step 3: Check the zero coefficient. The required inequality is $|2X_2^\mathsf{T}r|\leq\lambda$. Here $|2(1)|=2\leq2$, so the zero-coordinate condition passes, including at its boundary.

Conclusion. The candidate is not optimal because the first coordinate fails stationarity, even though the second coordinate satisfies its inequality. The common mistake is to see $X_1^\mathsf{T}r=2=\lambda$ and accept the candidate; that omits the factor of two required by this unscaled objective.

Worked Example: A Negative Coefficient and a Boundary Zero

Use the half-scaled objective with $\lambda=1$. The predictors and response are centered, $X^\mathsf{T}X=\begin{pmatrix}2&0\\0&4\end{pmatrix}$, and $X^\mathsf{T}y=(-5,1)^\mathsf{T}$. Check $\beta=(-2,0)^\mathsf{T}$. This example tests both the sign of an active coefficient and the inclusive inequality at a zero coefficient.

Step 1: Calculate the fitted cross-products. $$ X^\mathsf{T}X\beta= \begin{pmatrix}2&0\\0&4\end{pmatrix} \begin{pmatrix}-2\\0\end{pmatrix} = \begin{pmatrix}-4\\0\end{pmatrix}. $$

Step 2: Calculate the residual correlations. $$ X^\mathsf{T}r=X^\mathsf{T}y-X^\mathsf{T}X\beta = \begin{pmatrix}-5\\1\end{pmatrix} - \begin{pmatrix}-4\\0\end{pmatrix} = \begin{pmatrix}-1\\1\end{pmatrix}. $$

Step 3: Check both coordinates. Since $\beta_1=-2$, its required correlation is $\lambda\operatorname{sign}(-2)=-1$, which matches $X_1^\mathsf{T}r=-1$. Since $\beta_2=0$, its requirement is $|X_2^\mathsf{T}r|\leq1$; here $|1|=1$, so it passes at equality.

Conclusion. The intercept condition holds because the data are centered and the intercept is zero. Both coefficient conditions hold, so convexity certifies that the candidate is a global minimizer. Replacing the signed condition for the negative coefficient with $X_1^\mathsf{T}r=+\lambda$ would be a sign error.

Worked Example: Checking a Candidate with Correlated Predictors

For the half-scaled objective with $\lambda=3$, suppose the centered data have $X^\mathsf{T}X=\begin{pmatrix}5&2\\2&4\end{pmatrix}$, $X^\mathsf{T}y=(8,3)^\mathsf{T}$, and $y^\mathsf{T}y=16$. Check $\beta=(1,0)^\mathsf{T}$. The nonzero off-diagonal entries mean that the fitted value for one predictor contributes to both residual correlations.

Step 1: Calculate the fitted cross-products and residual correlations. $$ X^\mathsf{T}X\beta= \begin{pmatrix}5\\2\end{pmatrix}, \qquad X^\mathsf{T}r= \begin{pmatrix}8\\3\end{pmatrix} - \begin{pmatrix}5\\2\end{pmatrix} = \begin{pmatrix}3\\1\end{pmatrix}. $$

Step 2: Check the active coordinate. Since $\beta_1=1>0$, the required equality is $X_1^\mathsf{T}r=3$. The calculated correlation is $3$, so it passes.

Step 3: Check the zero coordinate. Since $\beta_2=0$, the required inequality is $|X_2^\mathsf{T}r|\leq3$. Here $|1|=1\leq3$, so it also passes. The intercept condition holds by centering. Therefore, the candidate is a global minimizer.

Check the residual sum of squares. The proposed residual satisfies $$ r^\mathsf{T}r=y^\mathsf{T}y-2\beta^\mathsf{T}X^\mathsf{T}y+\beta^\mathsf{T}X^\mathsf{T}X\beta =16-2(8)+5=5. $$ Thus the objective at this candidate is $\frac{1}{2}(5)+3(|1|+|0|)=2.5+3=5.5$. The KKT conditions, rather than this objective value alone, establish that it is globally minimizing.

Common Errors and What the Conditions Do Not Say

A zero coefficient does not have to have zero residual correlation. It can be zero at an optimum whenever its residual correlation lies within the allowed penalty threshold. At the boundary, the inequality still holds. Conversely, for a nonzero coefficient, merely being within that threshold is not enough: its residual correlation must equal the signed threshold exactly.

Mixing scaling conventions. The factor of two appears with the unscaled squared-error objective, not with the half-scaled objective.
Ignoring coefficient signs. A negative coefficient requires a negative signed threshold; a positive one requires a positive threshold.
Checking only zero coefficients. Every nonzero coefficient also needs its equality checked, and a failed equality rules out optimality.
Forgetting the intercept. With an estimated, unpenalized intercept, the residuals must sum to zero. Centering is one way to make this condition automatic.
Using strict inequality at zero. The condition is $\leq$, so equality at the threshold is valid.

The KKT conditions determine whether a proposed point is a lasso minimizer; they are not a rule that every zero coefficient must have a particular sign or that every satisfying coefficient vector is unique. The subject here is optimality: calculate the residual correlations, use the correct coordinate condition and objective scaling, and invoke convexity only after all required conditions have been checked. This material is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.

Check Your Understanding

For each problem, apply the KKT conditions for the stated objective and check the intercept condition when it is specified.

For the half-scaled objective with $\lambda=1$, centered data have $X^\mathsf{T}X=\begin{pmatrix}2&0\\0&3\end{pmatrix}$, $X^\mathsf{T}y=(3,2)^\mathsf{T}$, and candidate $\beta=(1,0)^\mathsf{T}$. Is the candidate optimal? (Answer: No; the first coordinate passes, but the zero-coordinate correlation is $2>1$.)
For the unscaled objective with $\lambda=6$, centered data have $X^\mathsf{T}X=\begin{pmatrix}4&0\\0&2\end{pmatrix}$, $X^\mathsf{T}y=(7,3)^\mathsf{T}$, and candidate $\beta=(1,0)^\mathsf{T}$. Is it optimal? (Answer: Yes; the residual correlations are $(3,3)^\mathsf{T}$, giving $2(3)=6$ for the active coordinate and $|2(3)|=6\leq6$ for the zero coordinate.)
For the half-scaled objective with $\lambda=2$, centered data have $X^\mathsf{T}X=\begin{pmatrix}4&1\\1&2\end{pmatrix}$, $X^\mathsf{T}y=(6,0)^\mathsf{T}$, and candidate $\beta=(1,0)^\mathsf{T}$. Is it optimal? (Answer: Yes; the residual correlations are $(2,-1)^\mathsf{T}$, so the active equality holds and the zero-coordinate absolute correlation is at most $2$.)
For the half-scaled objective with $\lambda=1$, centered data have $X^\mathsf{T}X=\begin{pmatrix}3&1\\1&2\end{pmatrix}$, $X^\mathsf{T}y=(0,-3)^\mathsf{T}$, and candidate $\beta=(0,-1)^\mathsf{T}$. Is it optimal? (Answer: Yes; $X^\mathsf{T}r=(1,-1)^\mathsf{T}$, so the zero coordinate is at its allowed boundary and the negative coefficient has the required correlation $-1$.)
An uncentered regression includes an estimated intercept and uses the half-scaled objective. A proposed candidate satisfies every coefficient KKT condition, but its residual vector has $\mathbf{1}^\mathsf{T}r=0.4$. Can it be a minimizer of the stated objective? (Answer: No; the unpenalized-intercept condition requires $\mathbf{1}^\mathsf{T}r=0$.)

What You'll Learn