Why Support Recovery Requires More Than a Good Fit
Lasso is often used both to predict an outcome and to select a compact set of predictors. These are different objectives. A model can predict well while including an irrelevant variable, omitting a truly active one, or choosing one of several strongly related predictors as a substitute for another. Reliable recovery of the active set therefore requires assumptions about the signal, the design matrix, and the noise—not merely a small prediction error.
The conditions in this tutorial are sufficient conditions: when they hold, they support a mathematical guarantee under the stated model. They are not a checklist that every useful Lasso fit must pass. Failure of a sufficient condition means that the guarantee is unavailable, not necessarily that selection must fail.
A Fixed-Design Setup and Its Conditions
For a precise discussion, consider \(n\) observations and \(p\) predictors in the linear model \(y=X\beta^*+\varepsilon\). Assume the response and predictor columns are centered, and the columns have been scaled so that their squared lengths equal \(n\). Use the Lasso objective
Here \(\beta^*\) is the data-generating coefficient vector, \(\varepsilon\) is the error vector, and \(\lambda\) controls the penalty. The normalization matters: changing the loss scaling changes the numerical meaning of \(\lambda\). Let \(\Sigma=X^\mathsf{T}X/n\) be the predictor Gram matrix, and write \(S^c\) for the inactive indices.
Three issues are central. First, the active predictors must be distinguishable in the design; a standard condition is that \(\Sigma_{SS}\), the active-predictor Gram matrix, is invertible. Second, inactive predictors must not be too well represented by active predictors in a way that defeats the penalty. Third, active coefficients must be large enough to remain nonzero after shrinkage and noise have acted.
The condition is most informative when read together with a signal-strength requirement. In a fixed design, define \(c=X^\mathsf{T}\varepsilon/n\), the vector of predictor-noise correlations. If the active signs are \(s\), a sufficient coordinatewise margin for preserving them is
This bound says that each active coefficient must exceed the largest penalty-induced shift and the largest noise-induced shift on the active coordinates. It is a convenient sufficient bound, not a necessary threshold. In applications, noise is not known exactly; one instead justifies a bound on its correlations under an appropriate error assumption. For example, independent mean-zero errors with controlled variance or tails can support probabilistic bounds, but the exact bound depends on the design and the noise distribution.
Why the Inactive-Predictor Condition Appears
The Lasso optimality conditions explain the role of both predictor dependence and signal size. For a minimizer, the residual correlations must satisfy
Thus, an inactive coordinate can remain zero only if its residual correlation has magnitude at most \(\lambda\). To see the design requirement, suppose temporarily that the noise is zero and that a candidate solution has the correct active signs \(s\) and no inactive coefficients. The active-coordinate optimality equations give
The candidate's residual is \(X_S(\beta_S^*-\hat{\beta}_S)=\lambda X_S\Sigma_{SS}^{-1}s\). Its correlation with an inactive predictor \(j\) is therefore \(\lambda\Sigma_{jS}\Sigma_{SS}^{-1}s\). The inactive-coordinate optimality condition requires its magnitude to be no more than \(\lambda\). Requiring it to be strictly less than \(\lambda\) gives the strict irrepresentable condition. If the inactive predictors track the active sign pattern too closely, their residual correlations may cross the penalty threshold and they can be selected instead.
The displayed active solution also shows shrinkage: even with no noise, the coefficients are shifted by \(\lambda\Sigma_{SS}^{-1}s\). The signal-strength bound ensures that this shift does not change any active sign. With noise, the shift additionally includes \(\Sigma_{SS}^{-1}c_S\). Together, the inactive-coordinate check and the active-sign check explain the two main ingredients of a support-recovery argument.
Worked Example: Checking Recovery in an Orthogonal Design
Suppose the standardized predictors are orthogonal, so \(\Sigma=I\). There are two active coefficients, \(\beta_1^*=0.20\) and \(\beta_2^*=-0.30\), and all other coefficients are zero. Let \(\lambda=0.12\). Assume the absolute noise correlation for each active coordinate is at most \(0.03\), and the largest absolute noise correlation among inactive coordinates is \(0.08\). Determine whether these bounds establish exact support recovery.
Method. With an orthogonal design, the Lasso estimate for coordinate \(j\) is soft thresholding of \(\beta_j^*+c_j\) at \(\lambda\): \(\hat{\beta}_j=\operatorname{sign}(\beta_j^*+c_j)\max(|\beta_j^*+c_j|-\lambda,0)\). The irrepresentable expression is zero because the active and inactive columns are orthogonal.
Active-coordinate check. The smallest possible magnitude of the first active coefficient after its adverse noise correlation is \(0.20-0.03=0.17\). Since \(0.17>0.12\), it remains selected. For the second, the smallest possible magnitude is \(0.30-0.03=0.27\), which also exceeds \(0.12\). In the worst adverse directions, the estimated magnitudes are at least \(0.17-0.12=0.05\) and \(0.27-0.12=0.15\), respectively.
Inactive-coordinate check. Every inactive noise correlation has magnitude at most \(0.08\), and \(0.08<0.12\), so no inactive coordinate crosses the threshold. Both checks hold; exact support recovery is established under these orthogonal-design assumptions.
Check. The active lower bounds exceed \(\lambda\), while the inactive upper bound is below \(\lambda\). The method avoids the mistake of checking only inactive variables and forgetting that Lasso shrinkage can remove weak active ones.
Worked Example: Evaluating Dependence and Noise in a Correlated Design
Suppose there are two active predictors and one inactive predictor. The active Gram matrix and the inactive-to-active correlations are \(\Sigma_{SS}=\begin{pmatrix}1&0.2\\0.2&1\end{pmatrix}\) and \(\Sigma_{3S}=(0.3,0.1)\). Let \(\beta_S^*=(0.8,-0.7)\), \(\lambda=0.10\), and suppose \(c_S=(0.01,-0.02)\) and \(c_3=0.005\). Check the strict dependence condition, the active signs, and the inactive-coordinate condition for the candidate support.
Method. The active signs are \(s=(1,-1)\). The inverse active Gram matrix is \(\Sigma_{SS}^{-1}=\frac{1}{0.96}\begin{pmatrix}1&-0.2\\-0.2&1\end{pmatrix}\), since \(1-0.2^2=0.96\).
Dependence check. Multiplying the inverse by \(s\) gives \((1.25,-1.25)\). The inactive dependence term is \(0.3(1.25)+0.1(-1.25)=0.25\). Its absolute value is \(0.25<1\), so the strict irrepresentable condition holds.
Active-coordinate check. First, \(\Sigma_{SS}^{-1}c_S=(0.0145833,-0.0229167)\), to seven significant digits. The penalty shift is \(\lambda\Sigma_{SS}^{-1}s=(0.125,-0.125)\). Hence the active candidate is \(\hat{\beta}_S=\beta_S^*+\Sigma_{SS}^{-1}c_S-\lambda\Sigma_{SS}^{-1}s=(0.6895833,-0.5979167)\). Both entries retain their true signs.
Inactive-coordinate check. The inactive residual correlation under this candidate is \(c_3+\lambda\Sigma_{3S}\Sigma_{SS}^{-1}s-\Sigma_{3S}\Sigma_{SS}^{-1}c_S\). The middle term is \(0.10(0.25)=0.025\). The last dot product is \(0.3(0.0145833)+0.1(-0.0229167)=0.0020833\). Therefore the inactive residual correlation is \(0.005+0.025-0.0020833=0.0279167\), whose magnitude is less than \(\lambda=0.10\). The KKT checks support the stated active set for these values.
Check. The inactive correlation is evaluated after accounting for both the penalty shift in the active fit and active-coordinate noise. Comparing \(c_3\) alone with \(\lambda\) would omit those effects.
Prediction Accuracy Does Not Identify the Support
Prediction metrics assess how close fitted values are to outcomes. Support recovery assesses whether the selected coefficient indices match the nonzero entries of \(\beta^*\). These targets can disagree, especially when predictor columns are highly correlated. A small change in fitted values may correspond to a large change in which variable is named as active.
Worked Example: Two Supports With Similar Predictions
Consider two centered predictors scaled to have squared length \(n\), with \(X_1^\mathsf{T}X_2/n=0.99\). Suppose the true outcome is \(y=X_1\), so the true coefficient vector is \(\beta^*=(1,0)\) and the true support is \(\{1\}\). Compare the true fitted values \(X_1\) with the alternative fitted values \(X_2\), which use support \(\{2\}\).
Method. The mean squared difference between the two sets of fitted values is \(\lVert X_1-X_2\rVert_2^2/n\). Expanding the square gives \(X_1^\mathsf{T}X_1/n+X_2^\mathsf{T}X_2/n-2X_1^\mathsf{T}X_2/n=1+1-2(0.99)=0.02\).
The alternative model's mean squared error against \(y=X_1\) is therefore \(0.02\), and its root mean squared error is \(\sqrt{0.02}\approx0.1414\). It has a different support from the truth even though its prediction error is small. This comparison does not claim that Lasso must choose predictor 2; it shows why a prediction score alone cannot certify which support is correct.
Check. The supports differ, but the predictors are nearly aligned. The example avoids the mistake of treating low prediction error as proof of correct variable selection.
What the Conditions Do—and Do Not—Promise
Reliable support recovery is most plausible when the active predictors are identifiable, inactive predictors are not too aligned with the active sign pattern, the active coefficients are sufficiently strong, and noise correlations are controlled. In high-dimensional settings, a penalty is often chosen large enough to control many noise correlations; the signal must then be large enough to exceed the resulting shrinkage and noise. The precise rates depend on the design, sample size, and error assumptions, so no single numerical signal threshold applies to every problem.
The conditions are stronger than what is needed merely to predict well. When predictors are redundant, several coefficient vectors may yield similar fitted values. Earlier material on correlated predictors and fitted-value uniqueness distinguishes the behavior of fitted values from the behavior of coefficient solutions; neither fact alone proves that the selected set equals the scientific or data-generating active set.
| Question | What it evaluates | What it does not establish by itself |
|---|---|---|
| Is prediction error small? | Agreement between predictions and observed outcomes under an evaluation metric | That every selected variable is truly active or every active variable was selected |
| Does the irrepresentable condition hold? | A form of dependence between inactive and active predictors | That active coefficients are large enough or noise is controlled |
| Does the signal exceed shrinkage and noise? | Whether active coefficients can remain nonzero with the correct signs | That inactive predictors satisfy their residual-correlation conditions |
A frequent exam error is to call a condition necessary when it is only sufficient, or to infer exact recovery from a good validation score. State the target first: prediction, support recovery, or sign recovery. Then identify the relevant assumptions. In particular, the strict irrepresentable condition plus adequate signal and controlled noise supports a recovery guarantee; prediction accuracy by itself does not.
Check Your Understanding
For each item, distinguish what the stated bounds establish from what they leave unresolved.
- In an orthogonal standardized design, \(\lambda=0.15\). An active coefficient is \(0.27\) with adverse noise correlation \(-0.04\), and all inactive noise correlations have magnitude at most \(0.11\). Do these bounds establish support recovery? (Answer: Yes. The active observed magnitude is \(0.27-0.04=0.23>0.15\), and \(0.11<0.15\) for inactive coordinates.)
- There are two active predictors with correlation \(0.4\), both true coefficients positive, and one inactive predictor whose correlations with them are \(0.2\) and \(0.1\). Compute the irrepresentable expression for that inactive predictor. (Answer: \(0.2143\), which is less than 1.)
- In an orthogonal design, an active coefficient has magnitude \(0.16\), its adverse noise correlation has magnitude \(0.07\), and \(\lambda=0.10\). Inactive noise correlations are at most \(0.04\). Do the bounds establish exact recovery? (Answer: No. The active observed magnitude can be \(0.16-0.07=0.09<0.10\), so the active variable may be removed.)
- For a fixed correlated design, suppose \(\lambda\lVert\Sigma_{SS}^{-1}s\rVert_\infty=0.06\), \(\lVert\Sigma_{SS}^{-1}c_S\rVert_\infty=0.03\), and the smallest active coefficient magnitude is \(0.12\). Does the stated sufficient active-signal bound hold? (Answer: Yes. \(0.12>0.06+0.03=0.09\).)
- Two centered, standardized predictors have correlation \(0.96\). The true response is \(y=X_1\), but a candidate uses fitted values \(X_2\). What are its mean squared error against \(y\) and its support? (Answer: The mean squared error is \(2(1-0.96)=0.08\); its support is \(\{2\}\), whereas the true support is \(\{1\}\).)