Which bridge estimator is the best for variable selection?

Shuaiwen Wang, Haolei Weng, Arian MalekiThe Annals of Statistics 2020 · DOI

Abstract

We study the problem of variable selection for linear models under the high-dimensional asymptotic setting, where the number of observations $n$ grows at the same rate as the number of predictors $p$. We consider two-stage variable selection techniques (TVS) in which the first stage uses bridge estimators to obtain an estimate of the regression coefficients, and the second stage simply thresholds this estimate to select the "important" predictors. The asymptotic false discovery proportion (AFDP) and true positive proportion (ATPP) of these TVS are evaluated. We prove that for a fixed ATPP, in order to obtain a smaller AFDP, one should pick a bridge estimator with smaller asymptotic mean square error in the first stage of TVS. Based on such principled discovery, we present a sharp comparison of different TVS, via an in-depth investigation of the estimation properties of bridge estimators. Rather than "orderwise" error bounds with loose constants, our analysis focuses on precise error characterization. Various interesting signal-to-noise ratio and sparsity settings are studied. Our results offer new and thorough insights into high-dimensional variable selection. For instance, we prove that a TVS with Ridge in its first stage outperforms TVS with other bridge estimators in large noise settings; two-stage LASSO becomes inferior when the signal is rare and weak. As a by-product, we show that two-stage methods outperform some standard variable selection techniques, such as LASSO and Sure Independence Screening, under certain conditions.

Introduction

In high-dimensional statistics, identifying a small subset of relevant predictors from a massive pool of candidates is a fundamental challenge. While the LASSO is the conventional choice for simultaneous estimation and selection, it often struggles in the "linear asymptotic regime" where the number of observations ($n$) and predictors ($p$) scale proportionally. In this regime, LASSO cannot achieve perfect selection consistency and must navigate a strict trade-off between False Discoveries (FDP) and True Positives (TPP).

This research explores whether separating estimation from selection can yield better results. By employing a Two-Stage Variable Selection (TVS) framework—first estimating coefficients with a bridge estimator and then applying a hard threshold—we can optimize selection performance by focusing on estimation accuracy.

The Two-Stage Variable Selection Framework

The TVS approach analyzed in this study consists of two distinct steps:

  1. Stage 1 (Estimation): Solve a bridge regression problem: $\text{argmin}_\beta \frac{1}{2}\|y - X\beta\|_2^2 + \lambda\|\beta\|_q^q$. This family of estimators includes LASSO ($q=1$), Ridge ($q=2$), and other $\ell_q$ penalties.
  2. Stage 2 (Selection): Apply a hard threshold to the Stage 1 estimates to identify "important" variables.

To provide a precise analysis, the study utilizes Approximate Message Passing (AMP) theory. This allows for the derivation of asymptotically exact expressions for the False Discovery Proportion (AFDP) and True Positive Proportion (ATPP), moving beyond loose "order-wise" bounds. A critical component of the methodology is a debiasing step in the first stage, which is essential for enabling the LASSO to achieve higher true positive rates.

Key Insights: The AMSE-AFDP Connection

The central theoretical discovery of this work is the fundamental link between estimation and selection: for a fixed True Positive rate, the False Discovery rate is minimized by the bridge estimator that achieves the lowest Asymptotic Mean Square Error (AMSE) in the first stage. This finding effectively transforms the complex variable selection problem into a more tractable estimation problem.

Ridge vs. LASSO: The Impact of Noise

Contrary to the common intuition that LASSO is always superior for selection due to its sparsity-inducing property, this research proves that in high-noise (low SNR) environments, Ridge regression ($q=2$) is actually the optimal first-stage estimator. Ridge provides more stable estimates in the presence of heavy noise; when these stable estimates are thresholded, they produce fewer false positives than the LASSO.

Conversely, LASSO remains the optimal choice in high SNR regimes or when signals are very sparse and strong. However, in "rare and weak" signal transitions, other bridge estimators like Ridge can take the lead.

Performance Comparison

The superiority of the two-stage approach is most evident when compared to standard one-stage methods. As shown in Figure 1, Two-Stage LASSO (2S-LASSO) consistently improves the FDP-TPP trade-off compared to standard LASSO across various noise levels.

Comparison of AFDP vs. ATPP for LASSO and Two-Stage LASSO (2S-LASSO) across different noise levels (sigma).

In Figure 1, the vertical dotted line represents the maximum ATPP achievable by standard LASSO. The 2S-LASSO, by incorporating debiasing and thresholding, is able to surpass this "wall," reaching significantly higher true positive rates while maintaining lower false discovery proportions, especially as the noise level ($\sigma$) decreases.

Furthermore, the TVS approach outperforms Sure Independence Screening (SIS). Unlike SIS, which evaluates predictors individually, TVS accounts for the joint influence of all predictors, leading to more accurate selection in complex high-dimensional settings.

Conclusion and Future Directions

This work provides a rigorous framework for selecting the best bridge estimator for variable selection. By establishing the AMSE-AFDP connection, it offers a principled way to choose estimators based on the signal-to-noise ratio and sparsity of the data.

Future research will look to extend these findings beyond linear models to Generalized Linear Models (e.g., Logistic Regression) and address the computational challenges associated with non-convex bridge estimators ($q < 1$). Additionally, testing the robustness of these theoretical insights on highly structured real-world datasets remains an important next step.

Summary updated

Abstract

We study the problem of variable selection for linear models under the high-dimensional asymptotic setting, where the number of observations n grows at the same rate as the number of predictors p. We consider two-stage variable selection techniques (TVS) in which the first stage uses bridge estimators to obtain an estimate of the regression coefficients, and the second stage simply thresholds this estimate to select the "important" predictors. The asymptotic false discovery proportion (AFDP) and true positive proportion (ATPP) of these TVS are evaluated. We prove that for a fixed ATPP, in order to obtain a smaller AFDP, one should pick a bridge estimator with smaller asymptotic mean square error in the first stage of TVS. Based on such principled discovery, we present a sharp comparison of different TVS, via an in-depth investigation of the estimation properties of bridge estimators. Rather than "orderwise" error bounds with loose constants, our analysis focuses on precise error characterization. Various interesting signal-to-noise ratio and sparsity settings are studied. Our results offer new and thorough insights into high-dimensional variable selection. For instance, we prove that a TVS with Ridge in its first stage outperforms TVS with other bridge estimators in large noise settings; two-stage LASSO becomes inferior when the signal is rare and weak. As a by-product, we show that two-stage methods outperform some standard variable selection techniques, such as LASSO and Sure Independence Screening, under certain conditions.
BibTeX
@article{wang2020which,
  author = {Shuaiwen Wang and Haolei Weng and Arian Maleki},
  title = {{Which bridge estimator is the best for variable selection?}},
  journal = {The Annals of Statistics},
  year = {2020},
  doi = {10.1214/19-aos1906},
}
Figure