Support Recovery and Irrepresentability

Why Accurate Coefficients Do Not Guarantee the Right Variables

In high-dimensional regression, the Lasso is often used both to estimate coefficients and to select variables. These are different goals. An estimator can be close to the true coefficient vector overall while setting a small, genuinely nonzero coefficient to zero. Conversely, it can estimate the important coefficients reasonably well while including an irrelevant predictor. Support recovery asks the sharper question: did the procedure identify exactly which population coefficients are nonzero?

This distinction matters whenever selected variables are treated as substantive findings. Prediction and coefficient-error bounds, such as those studied for Lasso oracle inequalities, do not by themselves establish that every selected variable is relevant or every relevant variable has been retained. Exact selection needs conditions on both signal size and the dependence structure among predictors.

Definition: In the linear model $y=X\beta^0+\varepsilon$, the true support is $S=\{j:\beta^0_j\ne 0\}$, where $\beta^0$ is the coefficient vector generating the outcome. An estimator $\hat\beta$ recovers the support exactly if $\{j:\hat\beta_j\ne 0\}=S$. It recovers the signed support if, in addition, $\operatorname{sign}(\hat\beta_j)=\operatorname{sign}(\beta^0_j)$ for every $j\in S$.

For a fixed design $X$ with $n$ observations and $p$ predictors, use the Lasso objective

\hat\beta \in \arg\min_{b\in\mathbb{R}^p} \left\{\frac{1}{2n}\|y-Xb\|_2^2+\lambda\|b\|_1\right\},

where $\lambda>0$ is the penalty level. Let $\hat\Sigma=X^\mathsf{T}X/n$ denote the sample Gram matrix and $W=X^\mathsf{T}\varepsilon/n$ the vector of noise correlations with the columns of $X$. The calculations below assume the model is correctly specified as written, and use predictors on a common scale so that comparisons among penalty terms are meaningful. Exact recovery is not automatic from this objective: it depends on the true signals, the design, and the realized noise.

Beta-Minimum: Signals Must Be Large Enough

A nonzero coefficient that is very close to zero can be removed by the Lasso penalty without creating much coefficient error. The relevant signal-strength quantity is the smallest absolute nonzero coefficient,

\beta_{\min}=\min_{j\in S}|\beta^0_j|.

A beta-minimum condition requires this quantity to be large relative to the estimation error or penalty-induced shrinkage. Its role is direct: if each active coefficient is perturbed by less than its absolute value, none can cross zero. The precise threshold depends on the design and the error bound being used; there is no universal numerical cutoff that guarantees selection in every problem.

Worked Example: Small Estimation Error, Different Support

Suppose the true coefficient vector for two predictors is $\beta^0=(1,0.04)$, so the true support is $S=\{1,2\}$. An estimate is $\hat\beta=(1,0)$, with support $\{1\}$. The coefficient error is

\|\hat\beta-\beta^0\|_2 =\sqrt{(1-1)^2+(0-0.04)^2} =0.04.

The estimate is close in Euclidean distance, but it misses predictor 2, so it does not recover the support. Here $\beta_{\min}=0.04$: an error of just $0.04$ in that coordinate is enough to change the selection decision. This constructed example illustrates why a coefficient-error guarantee alone is not an exact-selection guarantee.

Irrepresentability: Can the Inactive Predictors Mimic the Active Ones?

Even when the nonzero coefficients are large, an inactive predictor that is strongly related to the active predictors may compete with them in the penalized fit. Irrepresentability measures whether the inactive columns can reproduce the signed active-column pattern in the geometry encoded by the Gram matrix.

Definition: Assuming the active Gram matrix $\Sigma_{SS}$ is invertible, the sign-specific irrepresentability condition is $$ \|\Sigma_{S^cS}\Sigma_{SS}^{-1}\operatorname{sign}(\beta^0_S)\|_\infty < 1. $$ Here $\Sigma$ is the population or target Gram matrix, $S^c$ is the set of inactive predictors, and $\|\cdot\|_\infty$ is the largest absolute entry. A margin form requires the quantity to be at most $1-\eta$ for some $\eta>0$. For a fixed design, the analogous condition uses $\hat\Sigma$.

This condition concerns the signed support, not just pairwise correlations. If it fails, the inactive predictors may have a large enough correlation with the active signed combination that the Lasso’s penalty cannot keep all of them at zero while satisfying its optimality conditions. A strict margin is important in noisy samples: noise correlations must fit inside the remaining margin.

Worked Example: Irrepresentability Fails for a Correlated Combination

Consider three standardized predictors with the following Gram matrix, partitioned so predictors 1 and 2 are active and predictor 3 is inactive:

\Sigma= \begin{pmatrix} 1&0&0.6\\ 0&1&0.6\\ 0.6&0.6&1 \end{pmatrix}, \qquad S=\{1,2\}.

The active block is $\Sigma_{SS}=I_2$, so its inverse is also $I_2$. Suppose the true active coefficients are both positive, giving $\operatorname{sign}(\beta^0_S)=(1,1)^\mathsf{T}$. The irrepresentability quantity for predictor 3 is

\Sigma_{3S}\Sigma_{SS}^{-1}\operatorname{sign}(\beta^0_S) =(0.6,0.6) \begin{pmatrix}1&0\\0&1\end{pmatrix} \begin{pmatrix}1\\1\end{pmatrix} =0.6+0.6=1.2.

Since $1.2>1$, the condition fails. This is a valid positive-definite Gram matrix: the squared length of the cross-correlation vector is $0.6^2+0.6^2=0.72<1$. The failure is not caused by an impossible design; predictor 3 is correlated with the combined direction of the two active predictors strongly enough to violate the selection condition.

A KKT Check for Exact Recovery

The KKT conditions provide a direct way to see how signal strength and irrepresentability work together. Write $\hat\Sigma_{SS}$ for the active block of the sample Gram matrix, assume it is invertible, and let $z=\operatorname{sign}(\beta^0_S)$. Consider the candidate Lasso solution that sets all inactive coefficients to zero and has active signs $z$. Its active coefficients must satisfy the active KKT equations. Solving those equations gives

\hat\beta_S =\beta^0_S+\hat\Sigma_{SS}^{-1}(W_S-\lambda z).

This candidate has the intended signs if every active coefficient remains on the correct side of zero. For inactive coordinates, the KKT condition requires the absolute residual correlation to be no greater than $\lambda$. Substituting the candidate into that residual correlation gives the following two checks.

\min_{j\in S}|\beta^0_j| > \|\hat\Sigma_{SS}^{-1}W_S\|_\infty +\lambda\|\hat\Sigma_{SS}^{-1}z\|_\infty,

\|W_{S^c}-\hat\Sigma_{S^cS}\hat\Sigma_{SS}^{-1}W_S\|_\infty +\lambda\|\hat\Sigma_{S^cS}\hat\Sigma_{SS}^{-1}z\|_\infty <\lambda.

The first inequality is a beta-minimum requirement: the active signals exceed the combined noise and shrinkage perturbation. The second requires the inactive residual correlations to remain strictly below the Lasso threshold. If both hold, the candidate satisfies the KKT conditions with nonzero active coefficients and strict inactive inequalities, yielding the intended signed support. In practice, such checks are sufficient conditions; they need not hold for every design on which selection happens to succeed.

Worked Example: Checking a Noisy Two-Predictor Fit

Suppose there are two standardized predictors, predictor 1 is active with $\beta^0_1=0.5$, and predictor 2 is inactive. Let the sample Gram matrix and noise correlations be

\hat\Sigma= \begin{pmatrix}1&0.3\\0.3&1\end{pmatrix}, \qquad W= \begin{pmatrix}0.02\\0.01\end{pmatrix}, \qquad \lambda=0.10.

Here $S=\{1\}$, $z=1$, and $\hat\Sigma_{SS}=1$. The active KKT equation gives the candidate coefficient

\hat\beta_1 =0.5+(0.02-0.10)=0.42.

It is positive, as required. Equivalently, the beta-minimum check is $0.5>0.02+0.10=0.12$. For the inactive predictor, its residual correlation under this candidate is

W_2-\hat\Sigma_{21}W_1+\lambda\hat\Sigma_{21}z =0.01-0.3(0.02)+0.10(0.3) =0.034.

Since $|0.034|<0.10=\lambda$, the inactive KKT inequality holds strictly. Thus the KKT check supports exact signed support recovery for this specified design, noise vector, and penalty. It does not imply that the same result holds for other noise realizations or a different penalty.

How Correlation Can Defeat Selection

The failed irrepresentability calculation above has a concrete KKT interpretation. Suppose the same Gram matrix applies, the true coefficients on predictors 1 and 2 are both 1, the error correlations are zero, and $\lambda=0.10$. If the Lasso were to retain exactly those two predictors with positive signs, the restricted active equations would give

\hat\beta_1=\hat\beta_2=1-0.10=0.90.

The residual is the penalty-weighted active combination, so its correlation with inactive predictor 3 is

0.10(0.6+0.6)=0.12>0.10=\lambda.

That violates the inactive KKT condition. Therefore, a solution with precisely the intended active variables and signs cannot satisfy the Lasso optimality conditions in this example. The design gives predictor 3 enough correlation with the active combination to compete for selection. Which alternative variables appear in a particular fit depends on the full optimization problem, but the intended signed support is ruled out by this check.

More generally, high correlation can create near-ties among predictors: small changes in the sample or noise can change which variable is selected even when fitted values remain similar. That instability is one reason to distinguish a predictive use of the Lasso from a claim that its selected variables are the uniquely important ones.

Common Mistake and Practical Interpretation

Mistake: treating a small prediction or coefficient error as proof of correct selection. The coefficient vector $(1,0.04)$ can be close to $(1,0)$ while having a different support. A bound on prediction or estimation loss does not, by itself, rule out missed small signals or extra variables.
Mistake: checking only the size of the nonzero coefficients. Large signals do not remove the inactive-variable KKT requirement. Correlation among predictors can still make the irrepresentability quantity exceed one.
Mistake: interpreting irrepresentability as a claim that all predictors must be weakly correlated pair by pair. The condition is about how inactive predictors relate to the signed combination of active predictors. The relevant calculation uses the active Gram matrix and the active signs.

For support recovery, ask two separate questions. First, is the weakest true signal large enough to survive shrinkage and noise? Second, can inactive predictors satisfy the KKT inequalities while remaining zero? Beta-minimum addresses the first question; irrepresentability and the inactive KKT check address the second. Their conditions clarify when exact selection is plausible, but should not be read as a guarantee without the stated design and noise requirements.

Key takeaway: Exact Lasso support recovery requires more than a small estimation error. Active signals must be sufficiently strong, and inactive predictors must not be able to mimic the signed active combination too closely.

Check Your Understanding

Use the definitions and KKT logic in this tutorial to answer the following.

If the true coefficients are $(2,0.02)$ and an estimate is $(2,0)$, why can a small coefficient error coexist with incorrect support recovery?
For one active predictor with sign $+1$, active variance 1, and inactive-active correlation $0.7$, calculate the sign-specific irrepresentability quantity.
In the two-active-predictor example, why does the inactive correlation of $0.12$ violate the KKT condition when $\lambda=0.10$?
What does a beta-minimum condition control that an irrepresentability condition does not?
Why is a strict margin below one useful when the sample includes noise?