Optimality of Graphlet Screening in High Dimensional Variable Selection
From MaRDI portal
Abstract: Consider a linear regression model where the design matrix X has n rows and p columns. We assume (a) p is much large than n, (b) the coefficient vector beta is sparse in the sense that only a small fraction of its coordinates is nonzero, and (c) the Gram matrix G = X'X is sparse in the sense that each row has relatively few large coordinates (diagonals of G are normalized to 1). The sparsity in G naturally induces the sparsity of the so-called graph of strong dependence (GOSD). We find an interesting interplay between the signal sparsity and the graph sparsity, which ensures that in a broad context, the set of true signals decompose into many different small-size components of GOSD, where different components are disconnected. We propose Graphlet Screening (GS) as a new approach to variable selection, which is a two-stage Screen and Clean method. The key methodological innovation of GS is to use GOSD to guide both the screening and cleaning. Compared to m-variate brute-forth screening that has a computational cost of p^m, the GS only has a computational cost of p (up to some multi-log(p) factors) in screening. We measure the performance of any variable selection procedure by the minimax Hamming distance. We show that in a very broad class of situations, GS achieves the optimal rate of convergence in terms of the Hamming distance. Somewhat surprisingly, the well-known procedures subset selection and the lasso are rate non-optimal, even in very simple settings and even when their tuning parameters are ideally set.
Recommendations
- High-dimensional graphs and variable selection with the Lasso
- Assessment of Covariance Selection Methods in High-Dimensional Gaussian Graphical Models
- Feature selection based on the best-path algorithm in high dimensional graphical models
- Uniform joint screening for ultra-high dimensional graphical models
- Variable selection and regression analysis for graph-structured covariates with an application to genomics
- Ultra-high dimensional variable screening via Gram-Schmidt orthogonalization
- High-dimensional variable selection
- A robust variable screening method for high-dimensional data
- Variable selection in high-dimension with random designs and orthogonal matching pursuit
- Variable selection in high dimensional data analysis with applications
Cited in
(20)- Statistical limits of sparse mixture detection
- Covariance-insured screening
- UPS delivers optimal phase diagram in high-dimensional variable selection
- Covariate assisted screening and estimation
- Feature screening for network autoregression model
- Optimal screening and discovery of sparse signals with applications to multistage high throughput studies
- Estimation and variable selection with exponential weights
- High-dimensional variable selection with heterogeneous signals: a precise asymptotic perspective
- Covariate Information Number for Feature Screening in Ultrahigh-Dimensional Supervised Problems
- A selective overview of feature screening methods with applications to neuroimaging data
- Which bridge estimator is the best for variable selection?
- Nonparametric independence feature screening for ultrahigh-dimensional survival data
- Rare and weak effects in large-scale inference: methods and phase diagrams
- Weak Signal Identification and Inference in Penalized Likelihood Models for Categorical Responses
- Semi-Standard Partial Covariance Variable Selection When Irrepresentable Conditions Fail
- Variable selection with Hamming loss
- A stable and adaptive polygenic signal detection method based on repeated sample splitting
- Method of digraphs for multi-dimensional screening
- Enmsp: an elastic-net multi-step screening procedure for high-dimensional regression
- Higher criticism for large-scale inference, especially for rare and weak effects
This page was built for publication: Optimality of Graphlet Screening in High Dimensional Variable Selection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934100)
