  The early solution path, which tracks the first few variables that enter the
model of a selection procedure, is of profound importance to scientific
discoveries. In practice, it is often statistically hopeless to identify all
the important features with no false discovery, let alone the intimidating
expense of experiments to test their significance. Such realistic limitation
calls for statistical guarantee for the early discoveries of a model selector.
In this paper, we focus on the early solution path of best subset selection
(BSS), where the sparsity constraint is set to be lower than {the true
sparsity}. Under a sparse high-dimensional linear model, we establish the
sufficient and (near) necessary condition for BSS to achieve sure early
selection, or equivalently, zero false discovery throughout its early path.
Essentially, this condition boils down to a lower bound of the minimum
projected signal margin that characterizes the gap of the captured signal
strength between sure selection models and those with spurious discoveries.
Defined through projection operators, this margin is independent of the
restricted eigenvalues of the design, suggesting the robustness of BSS against
collinearity. Moreover, our model selection guarantee tolerates reasonable
optimization error and thus applies to near best subsets. Finally, to overcome
the computational hurdle of BSS under high dimension, we propose the "screen
then select" (STS) strategy to reduce dimension for BSS. Our numerical
experiments show that the resulting early path exhibits much lower false
discovery rate (FDR) than LASSO, MCP and SCAD, especially in the presence of
highly correlated design. We also investigate the early paths of the iterative
hard thresholding algorithms, which are greedy computational surrogates for
BSS, and which yield comparable FDR as our STS procedure.
