  We study the problem of exact support recovery for high-dimensional sparse
linear regression under independent Gaussian design when the signals are weak,
rare, and possibly heterogeneous. Under a suitable scaling of the sample size
and signal sparsity, we fix the minimum signal magnitude at the
information-theoretic optimal rate and investigate the asymptotic selection
accuracy of best subset selection (BSS) and marginal screening (MS) procedures.
We show that despite the ideal setup, somewhat surprisingly, marginal screening
can fail to achieve exact recovery with probability converging to one in the
presence of heterogeneous signals, whereas BSS enjoys model consistency
whenever the minimum signal strength is above the information-theoretic
threshold. To mitigate the computational intractability of BSS, we also propose
an efficient two-stage algorithmic framework called ETS (Estimate Then Screen)
comprised of an estimation step and gradient coordinate screening step, and
under the same scaling assumption on sample size and sparsity, we show that ETS
achieves model consistency under the same information-theoretic optimal
requirement on the minimum signal strength as BSS. Finally, we present a
simulation study comparing ETS with LASSO and marginal screening. The numerical
results agree with our asymptotic theory even for realistic values of the
sample size, dimension and sparsity.
