Understanding Best Subset Selection: A Tale of Two C(omplex)ities

2023-01-16 · Saptarshi Roy, Ambuj Tewari, Ziwei Zhu

We consider the problem of best subset selection (BSS) under high-dimensional sparse linear regression model. Recently, Guo et al. (2020) showed that the model selection performance of BSS depends on a certain identifiability margin, a measure that captures the model discriminative power of BSS under a general correlation structure that is robust to the design dependence, unlike its computational surrogates such as LASSO, SCAD, MCP, etc. Expanding on this, we further broaden the theoretical understanding of best subset selection in this paper and show that the complexities of the residualized signals, the portion of the signals orthogonal to the true active features, and spurious projections, describing the projection operators associated with the irrelevant features, also play fundamental roles in characterizing the margin condition for model consistency of BSS. In particular, we establish both necessary and sufficient margin conditions depending only on the identifiability margin and the two complexity measures. We also partially extend our sufficiency result to the case of high-dimensional sparse generalized linear models (GLMs).

📄 PDF Abstract BibTeX arXiv:2301.06259

Code (0)

등록된 구현이 없습니다.

Tasks

Model SelectionVariable SelectionVocal Bursts Valence Prediction

Methods 이 논문이 사용한 방법론

Linear Regression Linear Regression is a method for modelling a relationship between a dependent variable and independent variables. These models can be fit with numerous approaches. The most…

Toward Understanding the Impact of Staleness in Distributed Machine Learning

2018-10-08 · ICLR 2019 5 · Wei Dai, Yi Zhou, Nanqing Dong, Hao Zhang 외

Many distributed machine learning (ML) systems adopt the non-synchronous execution in order to alleviate the network communication bottleneck, resulting in stale parameters that do not reflect the latest updates. Despite…

BIG-bench Machine Learning Diversity

Subset selection in sparse matrices

2018-10-05 · Alberto Del Pia, Santanu S. Dey, Robert Weismantel

In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in po…

A Consistent and Scalable Algorithm for Best Subset Selection in Single Index Models

2023-09-12 · Borui Tang, Jin Zhu, Junxian Zhu, Xueqin Wang 외

Analysis of high-dimensional data has led to increased interest in both single index models (SIMs) and best subset selection. SIMs provide an interpretable and flexible modeling framework for high-dimensional data, while…

Model Selection regression

Best-Subset Selection in Generalized Linear Models: A Fast and Consistent Algorithm via Splicing Technique

2023-08-01 · Junxian Zhu, Jin Zhu, Borui Tang, Xuanyu Chen 외

In high-dimensional generalized linear models, it is crucial to identify a sparse model that adequately accounts for response variation. Although the best subset section has been widely regarded as the Holy Grail of prob…

Computational Efficiency Variable Selection

cf2vec: Collaborative Filtering algorithm selection using graph distributed representations

2018-09-17 · Cunha Tiago, Soares Carlos, de Carvalho André C. P. L. F.

Algorithm selection using Metalearning aims to find mappings between problem characteristics (i.e. metafeatures) with relative algorithm performance to predict the best algorithm(s) for new datasets. Therefore, it is of …

Collaborative Filtering Representation Learning