A Consistent and Scalable Algorithm for Best Subset Selection in Single Index Models
This addresses the problem of interpretable and sparse modeling in high-dimensional data for researchers and practitioners, offering a flexible solution without distributional assumptions, though it is incremental as it builds on existing SIM and subset selection frameworks.
The paper tackles the computational intractability of best-subset selection in high-dimensional single index models by proposing a provably scalable algorithm that directly recovers the best subset, with simulation results showing exact recovery in various settings like linear and Poisson regression.
Analysis of high-dimensional data has led to increased interest in both single index models (SIMs) and the best-subset selection. SIMs provide an interpretable and flexible modeling framework for high-dimensional data, while the best-subset selection aims to find a sparse model from a large set of predictors. However, the best-subset selection in high-dimensional models is known to be computationally intractable. Existing proxy algorithms are appealing but do not yield the bestsubset solution. In this paper, we directly tackle the intractability by proposing a provably scalable algorithm for the best-subset selection in high-dimensional SIMs. We directly proved the subset selection consistency and oracle property for our algorithmic solution, distinguishing it from other state-of-the-art support recovery methods in SIMs. The algorithm comprises a generalized information criterion to determine the support size of the regression coefficients, eliminating the model selection tuning. Moreover, our method does not assume an error distribution or a specific link function and hence is flexible to apply. Extensive simulation results demonstrate that our method is not only computationally efficient but also able to exactly recover the best subset in various settings (e.g., linear regression, Poisson regression, heteroscedastic models).