Lasso KKT Conditions and Sparse Solutions

Why the Lasso KKT Conditions Matter

The lasso combines a model-fitting objective with a penalty proportional to the sum of the absolute coefficient values. Unlike a smooth penalty, the absolute value has a corner at zero. That corner makes exact zero coefficients possible, but it also means that the ordinary rule “set every derivative equal to zero” is not enough. The Karush–Kuhn–Tucker (KKT) conditions account for the corner and give a precise test for whether each coefficient can be zero at an optimum.

For a generalized linear model (GLM), the loss may be the negative log-likelihood or another convex fitting criterion. The conditions below apply whenever that loss is differentiable and convex in the coefficients. They explain which gradient values are compatible with exclusion from the fitted model and which are incompatible with optimality.

Objective and Subgradient

Let $\alpha$ denote an optional intercept and let $\beta=(\beta_1,\ldots,\beta_p)$ denote the coefficients to be penalized. Write $f(\alpha,\beta)$ for the fitting loss, and consider

Q(\alpha,\beta)=f(\alpha,\beta)+\lambda\sum_{j=1}^{p}|\beta_j|,\qquad \lambda\geq 0.

The intercept is not included in the penalty. We assume $f$ is finite, differentiable, and convex on the parameter space under consideration. These conditions hold for many canonical-link GLM negative log-likelihoods, but not automatically for every possible link and objective. The parameter space here is unconstrained; extra constraints would require additional KKT terms.

At a nonzero coefficient, the absolute-value penalty has an ordinary derivative. At zero, it has a set of valid subgradients rather than one derivative.

Definition: The subdifferential of $h:\mathbb R\to\mathbb R$ at $b$, written $\partial h(b)$, is the set of values $s$ such that $h(u)\geq h(b)+s(u-b)$ for every $u$. For $h(b)=|b|$, $$ \partial |b| = \begin{cases} \{1\}, & b>0,\\ [-1,1], & b=0,\\ \{-1\}, & b<0. \end{cases} $$

The Lasso KKT Conditions

Write $g_j(\alpha,\beta)=\partial f(\alpha,\beta)/\partial\beta_j$, the fitting-loss gradient for coefficient $j$. If an intercept is present, also write $g_\alpha=\partial f/\partial\alpha$. The KKT conditions give a coordinatewise description of an optimum.

Theorem: Suppose $f$ is finite, differentiable, and convex on an unconstrained parameter space. A pair $(\hat\alpha,\hat\beta)$ minimizes $Q$ if and only if $$ \frac{\partial f(\hat\alpha,\hat\beta)}{\partial\alpha}=0 $$ when an unpenalized intercept is included, and, for every $j$, $$ \begin{cases} g_j(\hat\alpha,\hat\beta)+\lambda\,\operatorname{sign}(\hat\beta_j)=0, & \hat\beta_j\ne 0,\\[3pt] |g_j(\hat\alpha,\hat\beta)|\leq\lambda, & \hat\beta_j=0. \end{cases} $$ For $\lambda=0$, the coefficient condition reduces to $g_j=0$ for every coordinate.

Proof. At a minimum, the one-sided directional derivative in every direction must be nonnegative. Along the positive and negative directions of a nonzero coordinate, the penalty has derivative $\lambda\operatorname{sign}(\hat\beta_j)$, with the sign reversed for the negative direction. The two directional derivatives can both be nonnegative only if $g_j+\lambda\operatorname{sign}(\hat\beta_j)=0$. At a zero coordinate, the directional derivatives in the positive and negative directions are $g_j+\lambda$ and $-g_j+\lambda$. Both must be nonnegative, which is equivalent to $|g_j|\leq\lambda$. The same two-direction argument gives the zero-gradient condition for an unpenalized intercept.

For sufficiency, suppose the stated conditions hold. For each $j$, choose $s_j=\operatorname{sign}(\hat\beta_j)$ when $\hat\beta_j\ne 0$. When $\hat\beta_j=0$ and $\lambda>0$, choose $s_j=-g_j/\lambda$, which lies in $[-1,1]$ by the zero-coordinate condition. If $\lambda=0$, the conditions give $g_j=0$, and any $s_j\in\partial|\hat\beta_j|$ can be used. In every case, $g_j+\lambda s_j=0$. Convexity and differentiability of $f$ imply its tangent inequality, and the subgradient definition gives the corresponding inequality for each absolute-value term. Thus, for any $(\alpha,\beta)$, $$ Q(\alpha,\beta)\geq Q(\hat\alpha,\hat\beta) +\frac{\partial f(\hat\alpha,\hat\beta)}{\partial\alpha}(\alpha-\hat\alpha) +\sum_{j=1}^{p}(g_j+\lambda s_j)(\beta_j-\hat\beta_j) =Q(\hat\alpha,\hat\beta). $$ The intercept term is absent if there is no intercept. Therefore $(\hat\alpha,\hat\beta)$ is a global minimizer. $\square$

What the Zero-Coefficient Condition Says

At a fitted zero coefficient, the loss gradient must be small enough to be balanced by some subgradient of the penalty: $|g_j|\leq\lambda$. If instead $|g_j|>\lambda$, moving away from zero in the appropriate direction lowers the objective. This gives a direct test for whether a predictor can remain excluded.

Theorem: At a point with $\beta_j=0$, if $|g_j|>\lambda$, then that point is not a minimizer of the lasso objective. Specifically, moving a small positive distance in the direction $-\operatorname{sign}(g_j)$ along coordinate $j$ decreases the objective.

Proof. Let $d=-\operatorname{sign}(g_j)e_j$, where $e_j$ is the $j$th coordinate vector. Since $f$ is differentiable, for $t>0$ the change in the fitting loss is $t g_jd_j+o(t)=-t|g_j|+o(t)$. The coefficient starts at zero, so the penalty increases by exactly $\lambda t$. Consequently, $$ Q(\beta+td)-Q(\beta)=t(\lambda-|g_j|)+o(t). $$ When $|g_j|>\lambda$, the coefficient of $t$ is negative. For all sufficiently small positive $t$, the displayed difference is therefore negative, contradicting minimality. $\square$

For a nonzero coefficient, the fitting gradient must equal $-\lambda$ for a positive coefficient and $+\lambda$ for a negative one. For a zero coefficient, the gradient may lie anywhere in the interval $[-\lambda,\lambda]$. Equality at either endpoint is allowed: it is a boundary case, not proof that the coefficient must be nonzero. In particular, a strict inequality at zero is compatible with exclusion, while a violation rules out exclusion at that point.

Worked Examples

Worked Example: Gaussian Loss With Two Orthogonal Directions

Consider the convex Gaussian fitting loss $f(\beta)=\tfrac12[(\beta_1-2)^2+(\beta_2+0.4)^2]$, with lasso penalty $\lambda(|\beta_1|+|\beta_2|)$. Find and check the minimizer for $\lambda=1$, then for $\lambda=0.2$.

The gradients are $g_1=\beta_1-2$ and $g_2=\beta_2+0.4$. At $\lambda=1$, take $\hat\beta=(1,0)$. Then $g_1=-1$, and $\hat\beta_1>0$, so $g_1+\lambda\operatorname{sign}(\hat\beta_1)=-1+1=0$. For the zero coefficient, $g_2=0.4$, so $|g_2|=0.4\leq1$. Both KKT conditions hold, and convexity makes this a global minimizer.

At $\lambda=0.2$, take $\hat\beta=(1.8,-0.2)$. The gradients are $g_1=-0.2$ and $g_2=0.2$. The first coefficient is positive, giving $-0.2+0.2=0$; the second is negative, giving $0.2+0.2(-1)=0$. Both are active and both satisfy their KKT equations. Thus lowering the penalty allows the second coordinate, whose loss gradient at zero has magnitude $0.4$, to become active.

Worked Example: A Logistic Coefficient at the Boundary

Use a logistic regression with no intercept and one coefficient $\beta$. The two observations are $(x,y)=(1,1)$ and $(x,y)=(-1,0)$. Minimize the unscaled negative log-likelihood plus $\lambda|\beta|$. Determine the solution at $\lambda=1$ and $\lambda=0.5$.

For the first observation the negative log-likelihood contribution is $\log(1+e^{-\beta})$. For the second, the linear predictor is $-\beta$ and the outcome is zero, so the contribution is also $\log(1+e^{-\beta})$. Hence $$ f(\beta)=2\log(1+e^{-\beta}),\qquad f'(\beta)=-\frac{2}{1+e^\beta}. $$ At zero, $f'(0)=-1$. With $\lambda=1$, $|f'(0)|=\lambda$, so $\hat\beta=0$ satisfies the zero-coefficient KKT condition. Convexity proves it is a global minimizer; the equality is a boundary case, not a requirement to include the predictor.

With $\lambda=0.5$, zero fails the condition because $1>0.5$. A positive coefficient must satisfy $f'(\beta)+0.5=0$, so $2/(1+e^\beta)=0.5$. Therefore $1+e^\beta=4$, $e^\beta=3$, and $\hat\beta=\log 3>0$. Substitution gives $f'(\log 3)=-2/4=-0.5$, which exactly cancels the penalty gradient $+0.5$. The KKT condition holds.

Worked Example: A Poisson Predictor That Must Be Active

For one Poisson observation with outcome $y=2$, use the log link and linear predictor $\beta$, with no intercept. Minimize the negative log-likelihood plus $\lambda|\beta|$, ignoring a constant that does not depend on $\beta$. Find the solution for $\lambda=0.5$, and check whether zero could be optimal.

The fitting loss is $f(\beta)=e^\beta-2\beta$, with gradient $f'(\beta)=e^\beta-2$. At zero the gradient is $-1$, so $|f'(0)|=1>0.5$. The zero-coefficient condition fails: zero cannot be optimal. For a positive coefficient, the KKT equation is $e^\beta-2+0.5=0$, or $e^\beta=1.5$. Thus $\hat\beta=\log(1.5)>0$. At this value $f'(\hat\beta)=1.5-2=-0.5$, which cancels the penalty gradient $+0.5$. Since the objective is convex, this verifies a global minimizer.

Interpreting Active-Set Changes

The active set is the set of indices $j$ for which $\hat\beta_j\ne0$. The KKT equations describe how membership is determined at a solution: active coefficients balance the penalty gradient exactly, while inactive coefficients have fitting gradients no larger than the penalty threshold in absolute value. If a proposed zero coefficient has a gradient outside that interval, moving in the opposite gradient direction decreases the objective, so it cannot remain inactive at the optimum.

As $\lambda$ changes, the gradients are evaluated at the corresponding fitted coefficients and can themselves change. Therefore, checking a gradient at one fit does not by itself establish what happens to that predictor at every other penalty value. Nor does the zero condition imply that coefficients must enter or leave in a fixed order. A coefficient that reaches zero must satisfy the zero-coordinate condition there; if it fails, that point cannot be an optimum. If it holds, zero is permitted, but the condition alone does not say that zero is the only possible optimum.

Common Mistake

Wrong reasoning: “A zero coefficient has derivative zero, so its loss gradient must also be zero.” The lasso objective is not differentiable at zero, so setting an ordinary derivative to zero is not the right test.
Correction: At zero, use the whole subgradient interval. The correct condition is $|g_j|\leq\lambda$. The penalty can balance a nonzero loss gradient, provided its magnitude is no greater than $\lambda$.
Another pitfall: If $|g_j|=\lambda$, it is tempting to conclude that the variable must enter. Equality merely satisfies the KKT boundary condition; the logistic example shows that zero can be optimal at equality.

Key takeaway: For the lasso, a nonzero coefficient requires a signed gradient balance, while a zero coefficient requires the fitting gradient to lie in $[-\lambda,\lambda]$. A gradient outside that interval proves that the coefficient cannot remain zero at a minimizer.

Check Your Understanding

Use the KKT conditions to answer each question.

For a zero coefficient with $\lambda=0.8$ and fitting gradient $g_j=-0.6$, does the coordinate satisfy the zero-coefficient condition?
For a zero coefficient with $\lambda=0.8$ and $g_j=1.1$, which direction gives a first-order decrease in the objective?
A fitted coefficient is $-0.4$ and $\lambda=0.3$. What value must its fitting gradient have?
Why does $|g_j|=\lambda$ at a zero coefficient not prove that the coefficient is nonzero?
State the KKT equation for an unpenalized intercept in a model that includes one.