On the consistency theory of high dimensional variable screening
Variable screening is a fast dimension reduction technique for assisting high dimensional feature selection. As a preselection method, it selects a moderate size subset of candidate variables for further refining via feature selection to produce the final model. The performance of variable screening depends on both computational efficiency and the ability to dramatically reduce the number of variables without discarding the important ones. When the data dimension p is substantially larger than the sample size n, variable screening becomes crucial as 1) Faster feature selection algorithms are needed; 2) Conditions guaranteeing selection consistency might fail to hold. This article studies a class of linear screening methods and establishes consistency theory for this special class. In particular, we prove the restricted diagonally dominant (RDD) condition is a necessary and sufficient condition for strong screening consistency. As concrete examples, we show two screening methods SIS and HOLP are both strong screening consistent (subject to additional constraints) with large probability if n > O((ρs+σ/τ ) 2 log p) under random designs. In addition, we relate the RDD condition to the irrepresentable condition, and highlight limitations of SIS.
The authors propose a two-stage feature selection approach for linear regression. Candidate features are selected in the first stage and the selection is further refined in the second stage. They define "Strong screening consistency" as a criterion for performing the initial stage, and then investigate the implications of that definition when the screening values are computed by a linear operator.From the content and the references it appears that the authors address the statistics community. My expertise is more in machine learning/computer science, and my review is written from that perspective.My main point is the following:The vector beta to be estimated has 0 value for its ith coordinateiff the ith feature should not be part of the optimal selection. Therefore, identifying the 0 coordinates amounts to finding the optimal selection. My understanding of Definition 2.1 is thatit implies the existence of a threshold on the absolute values of beta_hat coordinates. All and only the zeros of beta are below that threshold. But this means that by trying all p-1 thresholds one can find the optimal solution. Since this problem is known to be NP-hard it is very unlikelythat such strong screening can be computed efficiently. Additional comments:The abstract uses many terms that are defined only much later in the paper. These include consistency, rho, sigma, thao, etc.The idea of (not necessarily consistent) variable screening appears to be, in principle, the same as filters (e.g., Guyon03). It may be a good idea to mention this and give references, or explain the differences.I am not sure that the O(n^2p) complexity (line 60) is acceptable for variable screening. Naive implementations of forward selection take O(n^2p), and fast implementations take O(np). In this sense O(n^2p) is very slow.--------------------------------------------------------------------------------------------Thanks for the rebuttal. It clarified most of the issues I had. I still find strong consistency to be too strong, as it correctly identifies the features to be selected. As explained in the rebuttal, this is an easy case, and may not help the challenge posed by feature selection. Still, I can now appreciate the result much better.Here is a reference to O(np) forward selection algorithm: Maung et,al. TKDE 2015.