KKT Conditions and the Geometry of Lasso Solutions

Why the Lasso Has a Geometric Optimality Rule

The lasso minimizes a squared-error criterion while penalizing the sum of absolute coefficient values. The penalty is not differentiable when a coefficient is zero, and that corner is central rather than incidental: it is what permits exact zeros. The Karush–Kuhn–Tucker (KKT) conditions express this geometry as a set of residual-correlation rules. They tell us which coefficients can be nonzero, when a zero coefficient is optimal, and what can be said about uniqueness.

Work with a fixed design matrix $X$ having $n$ rows and $p$ predictor columns, and a response vector $y$. For clarity, suppose the response and predictors have been centered, the intercept is handled separately and is not penalized, and each predictor is standardized so that $x_j'x_j/n=1$. The lasso objective, for penalty level $\lambda>0$, is

Q(\beta)=\frac{1}{2n}\|y-X\beta\|_2^2+\lambda\|\beta\|_1, \qquad \|\beta\|_1=\sum_{j=1}^p|\beta_j|.

Here $\beta$ is a candidate coefficient vector and $x_j$ is column $j$ of $X$. No probability model for $y$ is needed to state these optimization conditions. Standardization makes the thresholding formulas comparable across predictors; without it, the coordinate-specific column norm must be retained.

Definition: A subgradient of the convex function $f$ at $b$ is a number $z$ such that $f(u)\geq f(b)+z(u-b)$ for every $u$. For $f(b)=|b|$, the subgradient is $z=\operatorname{sign}(b)$ if $b\ne0$, and any $z\in[-1,1]$ if $b=0$.

The Lasso KKT Conditions

The squared-error term is differentiable, with gradient $-X'(y-X\beta)/n$. The absolute-value penalty has the subgradient described above, applied separately to each coefficient. A vector $\hat\beta$ minimizes $Q$ if and only if there is a vector $z$ satisfying the following conditions. For a convex objective, a zero subgradient is necessary and sufficient for global minimization.

Theorem: A coefficient vector $\hat\beta$ minimizes the lasso objective if and only if, for each $j$, $$ \frac{x_j'(y-X\hat\beta)}{n}=\lambda z_j, \qquad z_j= \begin{cases} \operatorname{sign}(\hat\beta_j), & \hat\beta_j\ne0,\\ \text{some number in }[-1,1], & \hat\beta_j=0. \end{cases} $$ Equivalently, if $r=y-X\hat\beta$ is the residual vector, then an active coefficient has $x_j'r/n=\lambda\operatorname{sign}(\hat\beta_j)$, while an inactive coefficient satisfies $|x_j'r/n|\leq\lambda$.

The term active means $\hat\beta_j\ne0$; inactive means $\hat\beta_j=0$. For an active coefficient, the residual correlation must sit exactly at the penalty boundary, with a sign matching the coefficient. For an inactive coefficient, the absolute residual correlation cannot exceed that boundary. A violation of either rule rules out a proposed solution.

Why the Conditions Follow

For a convex function, a point minimizes it exactly when zero belongs to its subdifferential. Applying this fact to $Q$, the subdifferential condition is

0\in -\frac{X'(y-X\hat\beta)}{n}+\lambda\,\partial\|\hat\beta\|_1.

The $j$th component of $\partial\|\hat\beta\|_1$ is $\operatorname{sign}(\hat\beta_j)$ when $\hat\beta_j\ne0$, and any value in $[-1,1]$ when $\hat\beta_j=0$. Rearranging each component gives the stated KKT conditions. In particular, at a zero coefficient, the equality says that the residual correlation can be matched by some $\lambda z_j$ with $|z_j|\leq1$; this is possible exactly when its absolute value is at most $\lambda$.

Thresholding and the Geometry of the Penalty

For a standardized predictor $x_j$, hold all other coefficients fixed and define the partial residual $r_j=y-\sum_{k\ne j}x_k\beta_k$. The part of the objective that varies with the $j$th coefficient $b$, up to a constant, is

\frac{1}{2}b^2-q_jb+\lambda|b|, \qquad q_j=\frac{x_j'r_j}{n}.

The quadratic term prefers $b=q_j$. The absolute-value penalty creates a corner at zero. If $|q_j|\leq\lambda$, zero satisfies the subgradient condition. If $q_j>\lambda$, the minimizing coefficient is positive and its derivative condition is $b-q_j+\lambda=0$; if $q_j<-\lambda$, the coefficient is negative and its condition is $b-q_j-\lambda=0$. Thus the coordinate minimizer is the soft-thresholding rule.

\hat b=\operatorname{sign}(q_j)(|q_j|-\lambda)_+, \qquad (a)_+=\max(a,0).

Geometrically, the squared-error contours are ellipses in coefficient space, while the $L_1$ penalty favors points near the axes and has corners where one or more coefficients equal zero. At a solution, an ellipse can touch a corner of the penalty geometry; the KKT inequalities describe that contact. Correlated predictors tilt the ellipses, so the simple one-coordinate thresholding formula no longer gives the joint solution in one step, but the KKT conditions remain valid.

Worked Example: Soft-Thresholding With Orthogonal Predictors

Consider a hypothetical design with $n=4$ and three standardized, mutually orthogonal columns: $x_1=(1,1,-1,-1)'$, $x_2=(1,-1,1,-1)'$, and $x_3=(1,-1,-1,1)'$. Let $y=1.4x_1+0.6x_2-0.3x_3$, and choose $\lambda=0.8$. Each column has $x_j'x_j/n=1$, and $x_j'x_k/n=0$ for $j\ne k$, so the coordinate rules apply independently.

The unpenalized correlations are $q_j=x_j'y/n$, giving $q=(1.4,0.6,-0.3)'$. Applying the formula,

\hat\beta_1=\operatorname{sign}(1.4)(1.4-0.8)=0.6,\quad \hat\beta_2=0,\quad \hat\beta_3=0.

The residual is $r=y-0.6x_1=0.8x_1+0.6x_2-0.3x_3$. Therefore $x_1'r/n=0.8=\lambda$, agreeing with the positive active coefficient. The two inactive residual correlations are $x_2'r/n=0.6$ and $x_3'r/n=-0.3$, whose absolute values are both at most $0.8$. All KKT conditions hold, so this is a lasso minimizer.

Worked Example: Checking a Candidate With Correlated Predictors

Suppose a hypothetical standardized two-predictor design has Gram matrix $X'X/n=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix}$, and the correlations with the response are $X'y/n=(1.2,1.0)'$. At $\lambda=0.5$, test the candidate $\hat\beta=(0.6,0.2)'$. The matrix is positive definite: its determinant is $1-0.5^2=0.75>0$.

The candidate is positive in both coordinates, so both KKT equalities require residual correlations of $0.5$. Compute them directly:

\frac{X'(y-X\hat\beta)}{n} =\frac{X'y}{n}-\frac{X'X}{n}\hat\beta = \begin{pmatrix}1.2\\1.0\end{pmatrix} - \begin{pmatrix}1&0.5\\0.5&1\end{pmatrix} \begin{pmatrix}0.6\\0.2\end{pmatrix} = \begin{pmatrix}0.5\\0.5\end{pmatrix}.

Both correlations equal $\lambda$, with the signs of their coefficients, so the KKT conditions are satisfied. Since the Gram matrix is positive definite, the squared-error term is strictly convex in these two coefficients, and the minimizer is unique. Notice that the unpenalized correlations, 1.2 and 1.0, are not the relevant quantities for checking the candidate: the conditions use correlations with the residual.

Coefficient Uniqueness and Fitted-Value Uniqueness

The lasso objective is convex, so minimizers exist for $\lambda>0$, but convexity alone does not ensure a unique coefficient vector. When $p>n$, or when columns are linearly dependent, different coefficient vectors may produce the same fitted values and penalty. This distinction matters: a unique fitted vector $X\hat\beta$ does not automatically imply a unique allocation of that fit among coefficients.

In fact, fitted values are unique for any lasso minimizer, even if the coefficients are not. If two minimizers produced different fitted vectors, the squared-error term would be strictly smaller at their midpoint, while the $L_1$ penalty at the midpoint could not exceed the average of their penalties. The objective at the midpoint would then be strictly below the minimum, a contradiction.

A simple sufficient condition for coefficient uniqueness is that $X$ have full column rank. Then the squared-error term is strictly convex in $\beta$, and adding a convex penalty preserves strict convexity. Full column rank is not necessary. Another useful sufficient condition is that, for a minimizer with active set $S$, the active columns $X_S$ are linearly independent and every inactive coordinate satisfies the strict inequality $|x_j'r/n|<\lambda$.

Justification of the second uniqueness condition: For any other coefficient vector $\beta+\delta$, the KKT conditions give $$ Q(\beta+\delta)-Q(\beta) =\frac{\|X\delta\|_2^2}{2n} +\lambda\sum_{j=1}^p\bigl(|\beta_j+\delta_j|-|\beta_j|-z_j\delta_j\bigr), $$ where each summand is nonnegative by the subgradient inequality. If $\beta+\delta$ is also a minimizer, the whole difference is zero, so every nonnegative term is zero. For an inactive $j$, strict dual inequality $|z_j|<1$ makes its summand strictly positive whenever $\delta_j\ne0$; hence $\delta_j=0$ for all inactive coordinates. Then $X\delta=X_S\delta_S=0$. Linear independence of $X_S$ forces $\delta_S=0$, so $\delta=0$ and the minimizer is unique.

Worked Example: Duplicate Predictors and Nonunique Coefficients

Consider a hypothetical standardized design with two identical columns, $x_1=x_2=x$, where $x'x/n=1$, and suppose $x'y/n=1.2$. Set $\lambda=0.5$. The fit depends only on the coefficient sum $s=\beta_1+\beta_2$, and for a given sum the smallest possible $L_1$ penalty is $|s|$. The problem therefore reduces to minimizing $\frac12(1.2-s)^2+0.5|s|$.

Soft-thresholding gives $s=1.2-0.5=0.7$. Every split with $\beta_1,\beta_2\geq0$ and $\beta_1+\beta_2=0.7$ has the same fitted values and penalty. For example, $(0.7,0)$ and $(0.2,0.5)$ are both minimizers, so the coefficient vector is not unique.

For either split, the residual correlation with each duplicate column is $x'r/n=1.2-0.7=0.5$. This equals $\lambda$, as required for each positive coefficient; for a zero coefficient it also satisfies the inactive inequality. The KKT conditions allow both solutions, and the duplicated columns fail the active-column independence condition.

Common Mistakes and Practical Checks

Checking the response correlation instead of the residual correlation. The KKT conditions use $x_j'(y-X\hat\beta)/n$, not $x_j'y/n$. Correlations change as other coefficients enter the fit.
Requiring an inactive correlation to equal zero. It need only lie between $-\lambda$ and $\lambda$. The penalty can keep a coefficient at zero even when its residual correlation is nonzero.
Using a strict inequality for every inactive coefficient. The necessary KKT condition is $\leq\lambda$. Equality is allowed, though it can complicate uniqueness.
Assuming a unique fitted value means unique coefficients. Duplicate or dependent columns can permit different coefficient vectors with the same fit. Check the design and the relevant uniqueness conditions.
Ignoring scaling. The displayed soft-thresholding rule assumes $x_j'x_j/n=1$. With a different column norm, the quadratic coefficient changes, and so does the coordinate update.

The KKT conditions are both a characterization and a diagnostic: they verify a proposed solution and explain why zeros occur. They do not by themselves guarantee that a selected set of predictors is the true support, nor do they provide prediction or estimation error bounds. Those are separate questions from the optimization geometry considered here.

Check Your Understanding

Use the KKT conditions and the examples above to answer these questions.

For a lasso minimizer, what residual-correlation equality must hold for a negative active coefficient?
A zero coefficient has residual correlation $0.7$ when $\lambda=0.6$. Can the candidate satisfy the KKT conditions? Explain.
With standardized orthogonal predictors, what coefficient results when $q_j=-1.1$ and $\lambda=0.4$?
Why can two lasso coefficient vectors yield the same unique fitted values?
State the two conditions in the tutorial that together provide a sufficient condition for coefficient uniqueness beyond full column rank.