Lasso Optimality Conditions

Why Residual Correlations Matter

The lasso does more than shrink fitted coefficients: it can set some coefficients exactly to zero. Its optimality conditions explain when that can happen. At a solution, the residual must have a particular relationship with every predictor: for a nonzero coefficient, the residual correlation reaches the penalty threshold with a sign determined by that coefficient; for a zero coefficient, the residual correlation cannot exceed the threshold in magnitude.

These conditions are useful for understanding and checking a lasso fit, including when predictors are correlated. They do not require predictors to be orthogonal. The earlier material on Lasso Soft Thresholding for Orthogonal Predictors treated a special design in which coefficients can be calculated separately; the conditions here apply more generally.

Model and Objective

For observations \(i=1,\ldots,n\) and predictors \(j=1,\ldots,p\), write the fitted model as \(y_i=\beta_0+\sum_{j=1}^{p}x_{ij}\beta_j+r_i\), where \(r_i\) is the residual. The intercept \(\beta_0\) is not penalized. We use the lasso objective

Q(\beta_0,\boldsymbol{\beta}) = \frac{1}{2n}\sum_{i=1}^{n} \left(y_i-\beta_0-\sum_{j=1}^{p}x_{ij}\beta_j\right)^2 +\lambda\sum_{j=1}^{p}|\beta_j|, \qquad \lambda\geq 0.

The factor \(1/(2n)\) fixes the scaling used throughout this tutorial. Software that uses a different scaling for squared error or the penalty will report a differently scaled value of \(\lambda\); the conditions must be adjusted to match its objective. Unless stated otherwise, assume the predictor columns have been centered and scaled as appropriate for penalization, and the response has been centered, so the intercept can be set to zero. With an uncentered response, the unpenalized intercept is fitted separately.

Definition: For a coefficient vector \(\boldsymbol{\beta}\), define the residual correlation for predictor \(j\) as \(C_j=\frac{1}{n}\sum_{i=1}^{n}x_{ij}r_i\). This is the sample average product of predictor \(j\) and the residuals. It is evaluated at the coefficient vector being checked, so changing the coefficients can change \(C_j\).

The word “correlation” here means an average product, not necessarily a Pearson correlation coefficient: \(C_j\) is not divided by the sample standard deviations of the predictor and residual. Its scaling is chosen to match the derivative of the squared-error term in the objective.

The Lasso Optimality Conditions

The absolute-value penalty is not differentiable at zero. The correct first-order condition therefore uses the subgradient of \(|\beta_j|\), which is the set containing its possible supporting slopes. For a nonzero coefficient the subgradient is its sign; at zero it can be any number between \(-1\) and \(1\).

Theorem: A coefficient vector minimizes the lasso objective if and only if, for every predictor \(j\),

if \(\beta_j\neq 0\), then \(C_j=\lambda\,\operatorname{sign}(\beta_j)\);
if \(\beta_j=0\), then \(|C_j|\leq\lambda\).

For an unpenalized intercept, its additional condition is \(\sum_{i=1}^{n}r_i=0\). These conditions are necessary and sufficient because the objective is convex.

Thus a positive active coefficient requires \(C_j=\lambda\), and a negative active coefficient requires \(C_j=-\lambda\). A zero coefficient is allowed when its residual correlation is strictly below the threshold, or exactly on it. Equality does not force a coefficient to be nonzero.

Why the Conditions Hold

Hold all coefficients except \(\beta_j\) fixed and change \(\beta_j\) by a small amount \(t\). The residual becomes \(r_i-tx_{ij}\). The change in the squared-error part of the objective is

\frac{1}{2n}\sum_{i=1}^{n}(r_i-tx_{ij})^2 -\frac{1}{2n}\sum_{i=1}^{n}r_i^2 = -tC_j+\frac{t^2}{2n}\sum_{i=1}^{n}x_{ij}^{2}.

If \(\beta_j\neq 0\), sufficiently small changes do not cross zero, so the penalty changes at rate \(\lambda\operatorname{sign}(\beta_j)\) per unit increase in \(\beta_j\). The derivative of the objective in this coordinate is therefore \(-C_j+\lambda\operatorname{sign}(\beta_j)\). At a minimum it must equal zero, giving the active-coefficient condition.

At \(\beta_j=0\), examine changes from both directions. For \(t>0\), the first-order change is \(t(-C_j+\lambda)\); it cannot be negative at a minimum, so \(C_j\leq\lambda\). For \(t<0\), the first-order change is \(t(-C_j-\lambda)\); this also cannot be negative, which requires \(C_j\geq-\lambda\). Together, these inequalities give \(|C_j|\leq\lambda\).

These coordinate conditions are sufficient as well as necessary. In subgradient notation, they say that for each \(j\) there is a number \(z_j\) with \(z_j=\operatorname{sign}(\beta_j)\) when \(\beta_j\neq0\), and \(z_j\in[-1,1]\) when \(\beta_j=0\), such that \(-C_j+\lambda z_j=0\). This is the zero-subgradient condition for a convex objective, which guarantees a global minimum. If predictors are redundant, more than one coefficient vector can attain the minimum; the conditions characterize minimizers, but do not by themselves guarantee uniqueness.

Checking Conditions With Sufficient Statistics

For a centered design matrix \(X\), let \(G=X^\mathsf{T}X/n\) and \(a=X^\mathsf{T}y/n\). At any proposed coefficient vector, \(r=y-X\boldsymbol{\beta}\), so the vector of residual correlations is

\boldsymbol{C} = \frac{X^\mathsf{T}r}{n} = \frac{X^\mathsf{T}y}{n} -\frac{X^\mathsf{T}X}{n}\boldsymbol{\beta} = \boldsymbol{a}-G\boldsymbol{\beta}.

This identity makes it possible to check the KKT conditions using the predictor cross-products and predictor-response cross-products, without listing every residual separately. The following examples use hypothetical centered data summarized by these quantities. The stated matrices and vectors are the assumed summaries of those data.

Worked Example: One Active Coefficient and One Zero

Suppose a hypothetical centered data set has two predictors, with \(G=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix}\) and \(\boldsymbol{a}=(1.2,0.6)^\mathsf{T}\). At \(\lambda=0.4\), check the proposed coefficients \(\boldsymbol{\beta}=(0.8,0)^\mathsf{T}\).

First calculate the residual correlations from \(\boldsymbol{C}=\boldsymbol{a}-G\boldsymbol{\beta}\):

G\boldsymbol{\beta} = \begin{pmatrix}1&0.5\\0.5&1\end{pmatrix} \begin{pmatrix}0.8\\0\end{pmatrix} = \begin{pmatrix}0.8\\0.4\end{pmatrix}, \qquad \boldsymbol{C} = \begin{pmatrix}1.2\\0.6\end{pmatrix} - \begin{pmatrix}0.8\\0.4\end{pmatrix} = \begin{pmatrix}0.4\\0.2\end{pmatrix}.

The first coefficient is positive and active, and \(C_1=0.4=\lambda\), as required. The second coefficient is zero, and \(|C_2|=0.2\leq0.4\). Both conditions hold, so the proposed vector is a lasso minimizer. In particular, the nonzero correlation with predictor 2 does not prevent its coefficient from being zero: it is below the penalty threshold.

Worked Example: A Zero Coefficient at the Boundary

For another hypothetical centered data set, suppose \(G=\begin{pmatrix}1&0.5\\0.5&1\end{pmatrix}\), \(\boldsymbol{a}=(0.7,0.55)^\mathsf{T}\), and \(\lambda=0.4\). Check \(\boldsymbol{\beta}=(0.3,0)^\mathsf{T}\).

The product \(G\boldsymbol{\beta}\) is \((0.3,0.15)^\mathsf{T}\), so

\boldsymbol{C} = \begin{pmatrix}0.7\\0.55\end{pmatrix} - \begin{pmatrix}0.3\\0.15\end{pmatrix} = \begin{pmatrix}0.4\\0.4\end{pmatrix}.

For predictor 1, \(\beta_1=0.3>0\) and \(C_1=0.4=\lambda\), satisfying the active condition. For predictor 2, \(\beta_2=0\) and \(|C_2|=0.4=\lambda\), satisfying the zero-coefficient condition at equality. The second coefficient is still zero in this solution. The KKT conditions permit a zero coefficient at the threshold; they do not say that a coefficient must become active as soon as equality occurs.

Worked Example: Active Coefficients With Opposite Signs

Suppose a hypothetical centered data set has \(G=\begin{pmatrix}1&0.3\\0.3&1\end{pmatrix}\), \(\boldsymbol{a}=(-0.57,0.70)^\mathsf{T}\), and \(\lambda=0.25\). Test the proposed vector \(\boldsymbol{\beta}=(-0.5,0.6)^\mathsf{T}\).

Calculate the fitted cross-product contribution and residual correlations:

G\boldsymbol{\beta} = \begin{pmatrix} -0.5+0.3(0.6)\\ 0.3(-0.5)+0.6 \end{pmatrix} = \begin{pmatrix}-0.32\\0.45\end{pmatrix}, \qquad \boldsymbol{C} = \begin{pmatrix}-0.57\\0.70\end{pmatrix} - \begin{pmatrix}-0.32\\0.45\end{pmatrix} = \begin{pmatrix}-0.25\\0.25\end{pmatrix}.

Both coefficients are nonzero. For the negative first coefficient, the condition is \(C_1=-\lambda=-0.25\), which holds. For the positive second coefficient, it is \(C_2=\lambda=0.25\), which also holds. Therefore the proposed vector satisfies the lasso optimality conditions. The signs matter: an active coefficient is not required to have a positive residual correlation, but its residual correlation must equal the threshold with the coefficient’s sign.

Scaling, Units, and Interpretation

Under the stated objective, \(C_j\) and \(\lambda\) must be on the same scale. For example, if the response is measured in points and a predictor in hours, then \(C_j=(1/n)\sum_i x_{ij}r_i\) has units of point-hours. The term \(\lambda|\beta_j|\) must have units of points squared, like the squared-error term; since \(\beta_j\) has units of points per hour, \(\lambda\) has units of point-hours. The coefficient itself has units of points per hour, not point-hours.

With multiple predictors recorded in different units, using a common penalty on raw coefficients raises a scaling issue: the coefficient units differ across predictors. Standardizing predictors before penalization puts them on comparable scales and is a common practice. Interpretations of the penalty threshold must still follow the precise objective and predictor scaling used.

The conditions are statements about a fitted optimization problem, not tests of whether population regression coefficients equal zero. In particular, \(|C_j|\leq\lambda\) explains why a coefficient can be zero at the lasso solution; it does not provide a p-value or confidence interval for that coefficient.

Common Mistakes

Using equality for a zero coefficient. The condition is \(|C_j|\leq\lambda\), not necessarily \(|C_j|=\lambda\). Strict inequality and boundary equality are both allowed.
Ignoring the coefficient sign. For an active coefficient, \(C_j=\lambda\operatorname{sign}(\beta_j)\). A negative coefficient requires \(C_j=-\lambda\).
Checking correlations before fitting the candidate. The condition uses the residuals at the proposed coefficient vector. Recalculate \(C_j\) after accounting for all fitted coefficients.
Mixing objective conventions. The threshold \(\lambda\) in these conditions follows from the objective with squared error divided by \(2n\). Changing the objective’s scaling changes the corresponding threshold.
Calling a KKT condition a significance test. These are optimization conditions for a penalized fit, not ordinary least-squares inference.

Key takeaway: At a lasso solution, an active coefficient has residual correlation exactly \(\lambda\) times its sign; a zero coefficient has residual correlation with magnitude at most \(\lambda\). These conditions are necessary and sufficient for minimizing the stated convex objective.

Check Your Understanding

Use the objective and notation defined above to answer these questions.

If \(\lambda=0.3\) and a proposed coefficient is positive and nonzero, what residual correlation must it have?
Can a zero coefficient satisfy the KKT condition when its residual correlation equals \(-\lambda\)? Explain.
For a proposed coefficient vector, why must residual correlations be calculated after forming its residuals?
Suppose \(C_j=0.12\), \(\lambda=0.2\), and \(\beta_j=0.4\). Does this coefficient satisfy the active-coefficient condition?
If a predictor is measured in hours and the response in points, what are the units of \(C_j\), \(\lambda\), and \(\beta_j\) under the stated objective?

What You'll Learn