  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
best subset selection aims to find a sparse model from a large set of
predictors. However, best subset selection in high-dimensional models is known
to be computationally intractable. Existing methods tend to relax the
selection, but do not yield the best subset solution. In this paper, we
directly tackle the intractability by proposing the first provably scalable
algorithm for best subset selection in high-dimensional SIMs. Our algorithmic
solution enjoys the subset selection consistency and has the oracle property
with a high probability. 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).
