  A stochastic search method, the so-called Adaptive Subspace (AdaSub) method,
is proposed for variable selection in high-dimensional linear regression
models. The method aims at finding the best model with respect to a certain
model selection criterion and is based on the idea of adaptively solving
low-dimensional sub-problems in order to provide a solution to the original
high-dimensional problem. Any of the usual $\ell_0$-type model selection
criteria can be used, such as Akaike's Information Criterion (AIC), the
Bayesian Information Criterion (BIC) or the Extended BIC (EBIC), with the last
being particularly suitable for high-dimensional cases. The limiting properties
of the new algorithm are analysed and it is shown that, under certain
conditions, AdaSub converges to the best model according to the considered
criterion. In a simulation study, the performance of AdaSub is investigated in
comparison to alternative methods. The effectiveness of the proposed method is
illustrated via various simulated datasets and a high-dimensional real data
example.
