The Price of Competition: Effect Size Heterogeneity Matters in High Dimensions
- 13 April 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 68 (8) , 5268-5294
Abstract
In high-dimensional sparse regression, would increasing the signal-to-noise ratio while fixing the sparsity level always lead to better model selection? For high-dimensional sparse regression problems, surprisingly, in this paper we answer this question in the negative in the regime of linear sparsity for the Lasso method, relying on a new concept we term effect size heterogeneity . Roughly speaking, a regression coefficient vector has high effect size heterogeneity if its nonzero entries have significantly different magnitudes. From the viewpoint of this new measure, we prove that the false and true positive rates achieve the optimal trade-off uniformly along the Lasso path when this measure is maximal in a certain sense, and the worst trade-off is achieved when it is minimal in the sense that all nonzero effect sizes are roughly equal. Moreover, we demonstrate that the first false selection occurs much earlier when effect size heterogeneity is minimal than when it is maximal. The underlying cause of these two phenomena is, metaphorically speaking, the “competition” among variables with effect sizes of the same magnitude in entering the model. Taken together, our findings suggest that effect size heterogeneity shall serve as an important complementary measure to the sparsity of regression coefficients in the analysis of high-dimensional regression problems. Our proofs use techniques from approximate message passing theory as well as a novel technique for estimating the rank of the first false variable.Keywords
Funding Information
- NSF through CAREER (DMS-1847415, CCF-1763314, CCF-1934876)
- Wharton Dean’s Research Fund
- Facebook Faculty Research Award
This publication has 28 references indexed in Scilit:
- Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processingPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2009
- Message-passing algorithms for compressed sensingProceedings of the National Academy of Sciences, 2009
- Simultaneous analysis of Lasso and Dantzig selectorThe Annals of Statistics, 2009
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)IEEE Transactions on Information Theory, 2009
- A Simple Proof of the Restricted Isometry Property for Random MatricesConstructive Approximation, 2008
- The Dantzig selector: Statistical estimation when p is much larger than nThe Annals of Statistics, 2007
- A second generation human haplotype map of over 3.1 million SNPsNature, 2007
- Least angle regressionThe Annals of Statistics, 2004
- Type S error rates for classical and Bayesian single and multiple comparison proceduresComputational Statistics, 2000
- Second moments of inverse Wishart-matrix elementsBiometrika, 1972