High-dimensional variable selection

Larry Wasserman; Kathryn Roeder

Source-linked AI summary

High-dimensional variable selection

Larry Wasserman, Kathryn Roeder

arXiv:0704.1139v2Apr 9, 2007math.STstat.ML

TL;DR

The paper asks what error-rate and power guarantees are possible for variable selection in high-dimensional regression. It combines model screening by lasso, marginal regression, or forward stepwise regression with cross-validation and hypothesis-test cleaning, and reports controlled type I error with reasonable power under stated conditions.

Problem
The paper addresses reliable recovery of the true sparsity pattern in high-dimensional regression while controlling type I error and retaining nontrivial power.
Method
The procedure fits candidate models, selects one by cross-validation, and removes variables by hypothesis testing; screening uses lasso, marginal regression, or forward stepwise regression.
Results
The multi-stage method controls type I error and provides reasonable power, with lasso and stepwise showing similar performance.
Takeaways & Limitations
The approach gives consistent variable selection under certain conditions and supports screening in one phase followed by cleaning in a follow-up phase.
Takeaways & Limitations
The theory assumes the linear model is correct, although in practice it may only be an approximation.

Abstract

from arXiv · show

This paper explores the following question: what kind of statistical guarantees can be given when doing variable selection in high-dimensional models? In particular, we look at the error rates and power of some multi-stage regression methods. In the first stage we fit a set of candidate models. In the second stage we select one model by cross-validation. In the third stage we use hypothesis testing to eliminate some variables. We refer to the first two stages as "screening" and the last stage as "cleaning." We consider three screening methods: the lasso, marginal regression, and forward stepwise regression. Our method gives consistent variable selection under certain conditions.

1. Introduction.

The paper targets reliable recovery of sparse regression supports in high-dimensional settings, separating this goal from prediction. Its screen-and-clean procedure fits candidate models, cross-validates among them, and then tests variables, using lasso, forward stepwise, or marginal regression screening.

The paper focuses on estimating the sparsity pattern—the covariates with nonzero regression coefficients—rather than optimizing prediction error.
The main goal is a variable-selection procedure with asymptotic type I error at most α and nontrivial power.
The procedure has three stages: fit candidate models, select one by cross-validation, and eliminate variables by hypothesis testing.The first two stages are screening; the final stage is cleaning.
Genetic studies motivate the setting because sample sizes are in the thousands, features can number in the hundreds of thousands, and detectable associations are sparse.For type I diabetes, the passage reports ten reproducible genes.
The three screening methods are lasso, forward stepwise regression, and marginal regression based on the absolute marginal coefficient.The marginal coefficient comes from regressing Y on X_j, equivalently ordering standardized covariates by absolute t-statistics.
The theory uses sparse signals, growing dimension, bounded covariates, random data splitting, and assumptions that can be weakened at the cost of more complicated proofs.The paper also assumes no intercepts and notes that normality and constant variance can be relaxed.

2. Error control.

Error control is difficult because of correlated covariates, high dimensionality, and unfaithfulness. The paper’s screening methods require sparsity and can lose variables through cancellation, especially marginal regression.

Correlation, high dimensionality, and unfaithfulness make control of variable-selection errors difficult.Unfaithfulness refers to cancellations of correlations caused by confounding.
The paper gives examples where controlling type I error at α forces power to be no more than approximately α.The stated bound is power less than α + ε for arbitrarily small ε under suitably close distributions.
The methods require a sparsity restriction: the paper fixes the number of nonzero coefficients while allowing p_n to grow, including exponentially.
Screening false negatives caused by correlation cancellations can lead to false positives during the second stage.
If correlated effects cancel so that µ_j ≈ 0, marginal association can miss a variable regardless of how large β_j is.The passage states that this can occur even when n is large and p is small.
Marginal regression is extremely susceptible to unfaithfulness; lasso and forward stepwise are less susceptible, while unobserved covariates can affect all methods.

3. Loss and cross-validation.

Cross-validation compares estimated and true model loss across candidate tuning parameters. Under a bound on candidate-model size, the estimated loss differs from true loss by a tuning-parameter-independent stochastic term plus vanishing error.

The fitted coefficient vector is extended to length p by setting coefficients outside the selected model to zero.
The data are split into groups D1, D2, and D3, with candidate models fitted using D1 before evaluating their losses.
Cross-validation seeks to order candidate models by estimated loss in the same way as their true loss.This requires the loss difference to be asymptotically approximately δ_n, independent of λ.
If every candidate model has size at most k_n, Theorem 3.2 provides a sequence δ_n = O_P(1) independent of λ and X in the loss approximation.

4. Multi-stage methods.

The paper uses multi-stage screening and cleaning: candidate models are generated, one is chosen by cross-validation, and hypothesis testing removes variables. Under assumptions, these methods control type I error, achieve consistent selection when α decreases, and yield a confidence sandwich for fixed α.

Multi-stage procedure: The three-stage procedure screens candidate models with D1, selects by cross-validation on D2, and cleans the selected model using t-tests on D3.The selected variables satisfy |Tj| > cn, with cn = zα/2m and m = |bSn|.
Multi-stage procedure: The candidate-model path is restricted to models with at most kn = A log n variables.This restriction defines Λn = {λ: |bSn(λ)| ≤ kn}.
Theoretical guarantees: The cleaning test controls asymptotic type I error at level α, and choosing α = αn → 0 makes bDn consistent for variable selection.The formal guarantee is limsupn→∞ P(Dc ∩ bDn ≠ ∅) ≤ α.
Theoretical guarantees: For fixed α, (bDn, bSn) forms a confidence sandwich, although its coverage may be much larger than 1 − α.The paper characterizes this conservativeness as expected rather than as an exact coverage result.
Screening methods: The same theorem statements apply to the specified forward stepwise and marginal-regression screening procedures.Marginal regression orders variables by absolute marginal coefficients, equivalently by absolute t-statistics under standardized covariates.
Screening methods: Marginal regression requires a faithfulness-type assumption preventing variables outside the true support from strongly dominating variables inside it.Increasing kn weakens the unfaithfulness restriction but reduces power.
Modifications: A two-way split uses D1 for candidate models and D2 for cross-validation, least-squares estimation, and testing, but its critical value is described as hopelessly large.The paper cautions that reusing the tri-split critical value may fail without extra conditions.

5. Application.

The application analyzes genetic associations with bone mineral density in 860 men using a reduced set of SNP main effects and interaction terms. Modeling all possible interactions was impractical, so the analysis selected two SNPs per gene as a compromise.

Application: The study measured 860 men on many genes and outcomes, then focused on 296 SNPs spanning 30 candidate genes for bone mineral density.The stated aim was to identify genes associated with bone mineral density relevant to understanding osteoporosis in men.
Application: Including all interactions would add 43,660 terms, which was impractical for the sample size.The analysis instead selected two SNPs per gene to model potential interactions.
Application: The reduced model contained 2,066 potential coefficients: 296 main effects and 1,770 interaction terms.An initial screen detected 10 terms, although the supplied passage truncates the remainder of that result.

6. Simulations.

Simulations compare lasso, stepwise, and marginal screening under several dependence and confounding structures, including three-stage and two-split designs. Type I error was generally controlled in models A–C, while unfaithfulness challenged all methods.

Simulation models: Models A–C examine null, triangular-signal, and correlated-triangular settings, whereas model D examines confounding and unfaithfulness.The simulations include moderate and large p in models A–C and focus on unfaithfulness in model D.
Three-stage design: Using three stages, each approach had type I error below α except stepwise regression in model C when n = p = 100.The simulations used one-third of the data for each stage and α = 0.05.
Three-stage design: False positive rates were about 10^-4 for p = 100 and 10^-5 for p = 1000, indicating few erroneous inclusions when type I errors occurred.The reported false positive rates were described as very low.
Comparative performance: The lasso had a slight power advantage over stepwise regression, and both outperformed marginal regression; model C particularly challenged the marginal approach.The correlated dependence structure in model C was identified as the source of difficulty for marginal screening.
Two-split design: With two data splits, screening and cleaning on separate halves produced a dramatic power increase, while type I error remained near α.Leave-one-out cross-validation selected the tuning parameter for screening.
Comparison with adaptive lasso: The adaptive lasso achieved greater power than the paper’s lasso screen-and-clean procedure, but with a much higher type I error rate.Its false positive rate was small, although the adaptive lasso did not control test size.

7. Proofs.

The proofs rely on Gaussian tail bounds, eigenvalue arguments, and established lasso results. The supplied passages primarily establish the technical tools used for the theoretical guarantees.

Proof tools: The proof framework uses bounds involving the smallest and largest eigenvalues of square matrices.These quantities are denoted φ(A) and Φ(A).
Proof tools: A standard Gaussian tail bound controls probabilities of large deviations for Z ∼ N(0,1).The bound is P(|Z| > t) ≤ t^-1e^-t^2/2.
Lasso results: The arguments invoke established lasso results for fixed designs and extend them to random covariates under assumptions (A1)–(A5).The extension holds with probability tending to one.
Supporting comparison: Table 2 reports size, power, and false positive rate for the two-stage adaptive lasso procedure.The table concerns a competing adaptive-lasso procedure rather than the proof tools themselves.

1. The squared error satisfies

The proofs establish that screening retains the true variables with high probability and that cleaning removes false positives while retaining true signals under the stated conditions. They combine prediction-error bounds, conditional testing arguments, and concentration results.

Screening: Prediction-error arguments show that the screening estimator can retain all true variables when its squared error is sufficiently controlled.The proof uses a second-half design matrix and a quadratic form involving the empirical covariance matrix.
Screening: The selected tuning parameter λ* includes the true support D with probability tending to one.The proof shows P(D ⊂ Ŝ_n(λ*)) → 1.
Cleaning: Conditional on the screened model containing D, variables outside D have t-distributed test statistics with n − m degrees of freedom.Here m is the screened model size.
Cleaning: The cleaning proof bounds false inclusions and concludes that the cleaned set is contained in D with probability tending to one.The false-positive probability is bounded by α_n, which tends to zero.
Cleaning: For each true variable, the testing argument shows the probability of exclusion tends to zero, yielding D ⊂ D̂_n with probability tending to one.The proof uses normal test-statistic representations and a finite-support argument.
Alternative screening methods: The screening proofs for lasso and marginal regression establish support retention through bounds on estimator error and marginal-coefficient estimates.The marginal-regression argument uses concentration of ĉμ_j − μ_j around zero.

8. Discussion.

The paper concludes that screen and clean controls type I error while retaining reasonable power, with stronger empirical performance when cross-validation reuses data. Its guarantees remain tied to restrictive modeling and unfaithfulness assumptions.

Conclusions: The multi-stage method successfully controls type I error while providing reasonable power, with lasso and stepwise showing similar performance.These are the paper’s main reported overall conclusions.
Conclusions: Simulations suggest that leave-one-out cross-validation preserves valid type I error rates and increases power despite theory assuming independent data across stages.The conclusion distinguishes empirical evidence from the theoretical assumption.
Experimental design: Using one experimental phase for screening and a follow-up phase for cleaning can produce an efficient experimental design.The paper says this approach merits further theoretical investigation.
Limitations: The main modeling limitation is the assumption that the linear model Y = X^Tβ + ε is correct, although reality may only be approximated by it.The paper identifies robustness to model misspecification as future work.
Limitations: Further extensions include nonnormal errors, nonconstant variance, optimized stage sample sizes, and screening methods beyond cross-validation.These are listed as possible extensions rather than established results.
Limitations: Unfaithfulness, caused by cancellations that make marginal correlations differ from regression coefficients, challenges all methods and remains underexplored.The authors note that this issue deserves attention even when p is small.

APPENDIX: PREDICTION

The appendix studies lasso prediction when the linear model may be misspecified, showing that cross-validation preserves predictive-risk consistency under stated high-dimensional conditions.

Cross-validation: Risk consistency can hold under model misspecification, and the appendix establishes that cross-validation preserves this property.The result extends the persistence property to a data-driven choice of tuning parameter.
Prediction target: The lasso estimator minimizes empirical predictive risk subject to an ℓ1-norm constraint, equivalently parameterized by λ or Ω.The appendix uses the constrained Ω formulation throughout.
Prediction target: The lasso targets the best linear predictor in B(Ωn), even without assuming E(Y|X) is linear.Persistence, or predictive risk consistency, compares the estimator with this constrained best linear predictor.
Related result: A related persistence result requires Ωn = o((n/log n)^(1/4)) for the lasso estimator.This earlier result motivates the appendix's cross-validated extension.
Proof strategy: The proof constructs lasso estimators over 0 ≤ ℓ ≤ Ωn, selects ℓ by cross-validation on a data split, and controls risk variation over a discretized grid.The argument uses monotonicity and Lipschitz control of population and empirical risks, with high-probability bounds.
Cross-validation: Under (A1), (A2), and (A3), if Ωn = O(n^(1−ξ−γ)/4) with ξ + γ < 1, the cross-validated lasso estimator is persistent.Theorem A.3 gives the main guarantee for the cross-validated estimator.