The Adaptive Subspace (AdaSub) algorithm of Staerk, Kateri and Ntzoufras (2021) solves the ℓ0\ell_0-type best-subset variable selection problem in high-dimensional linear regression by repeatedly solving exactly solvable low-dimensional subproblems on adaptively sampled subspaces of variables. Convergence to the criterion-optimal model is proven only under the Ordered Importance Property (OIP), a combinatorial condition on the selection criterion; iteration counts are known only in idealized best- and worst-case scenarios; nothing is proven about statistical consistency when the dimension diverges with the sample size. The paper's own theoretical agenda is to weaken OIP to broader verifiable conditions, derive non-idealized data-dependent iteration bounds, extend convergence guarantees to approximate subproblem solvers (including generalized linear models), prove high-dimensional model-selection consistency, and derive mixing-time theory for the Bayesian variant MAdaSub. Of these, only the Bayesian sampling extension has been substantially developed, with its ergodicity proven; the remaining theoretical components are, to our knowledge, open in the literature.

Background

Consider the linear regression model Y=Xβ+εY = X\beta + \varepsilon with nn observations and pp explanatory variables, where pp may greatly exceed nn. Variable selection asks for the subset SS of the index set P={1,…,p}P = \{1,\dots,p\} containing the relevant variables. A classical approach scores every candidate model SS by an ℓ0\ell_0-type criterion C(S)C(S) — a goodness-of-fit term minus a complexity penalty that grows with the model size ∣S∣|S| — such as the Akaike Information Criterion (AIC), the Bayesian Information Criterion (BIC), or the Extended BIC (EBIC), which adds an extra penalty proportional to log⁡p\log p per selected variable and is particularly suited to high-dimensional settings. Writing fC(V)f_C(V) for the best model contained in a subspace V⊆PV \subseteq P, that is fC(V)=arg⁡max⁡S⊆VC(S)f_C(V) = \arg\max_{S \subseteq V} C(S), the target is the criterion-optimal model S∗=fC(P)S^* = f_C(P). Finding S∗S^* exactly is in general NP-hard, since the model space has size 2p2^p.

The Adaptive Subspace (AdaSub) method of Staerk, Kateri and Ntzoufras (2021) is a stochastic search that reduces this intractable problem to a sequence of exactly solvable low-dimensional subproblems. It maintains a selection probability rj(t)∈(0,1)r_j^{(t)} \in (0,1) for each variable XjX_j. At iteration tt it draws a random subspace V(t)V^{(t)} by including each XjX_j independently with probability rj(t−1)r_j^{(t-1)}, computes the exact best submodel S(t)=fC(V(t))S^{(t)} = f_C(V^{(t)}) (feasible when V(t)V^{(t)} is small, e.g. via the 'leaps and bounds' branch-and-bound algorithm for best-subset linear regression), and updates rj(t)r_j^{(t)} proportionally to the relative frequency with which XjX_j has been selected whenever it was considered so far. Variables that repeatedly appear in optimal submodels of sampled subspaces thus become more likely to be considered again — an adaptive learning of variable importance. The tuning parameters are the initial expected subspace size q∈(0,p)q \in (0,p), the learning rate K>0K > 0 governing how strongly selection frequencies shift the probabilities, the number of iterations TT, and the output threshold ρ∈(0,1)\rho \in (0,1); the outputs are the best sampled model S^b\hat S_b and the thresholded model S^ρ={j∈P:rj(T)>ρ}\hat S_\rho = \{j \in P : r_j^{(T)} > \rho\}.

The main theoretical result (Theorem 4.1 of the source paper) states that AdaSub converges to S∗S^* — meaning rj(t)→1r_j^{(t)} \to 1 almost surely for j∈S∗j \in S^* and rj(t)→0r_j^{(t)} \to 0 otherwise — whenever the criterion satisfies the Ordered Importance Property (OIP) on the observed data: there exists an ordering (k1,…,ks∗)(k_1,\dots,k_{s^*}) of the variables of S∗S^* such that each kik_i belongs to fC(V)f_C(V) for every subspace VV that already contains k1,…,kik_1,\dots,k_i. OIP is a combinatorial 'stable learning path' condition; it is strictly weaker than the finite-sample property that every relevant variable is selected in every subspace containing it, which is an analogue of the partial faithfulness condition used by the PC-simple algorithm of Bühlmann, Kalisch and Maathuis (2010) (there, truly important variables retain non-zero partial correlation with the response given any conditioning subset). The appendix of the source paper additionally introduces a slightly weaker variant of this condition, OIP′' (Definition A.1 there), which imposes the same inclusion requirement only on subspaces that avoid the variables already excluded along the learning path; OIP implies OIP′', and convergence is proven under OIP′' (Theorem A.6). When OIP fails, only a partial guarantee survives: the thresholded model provably contains at least the variables along a maximal learning path. The number of iterations needed to recover S∗S^* has been analyzed only in two idealized scenarios — a best case (the finite-sample PF property) and a worst case (minimal OIP, where ki∈fC(V)k_i \in f_C(V) if and only if {k1,…,ki}⊆V\{k_1,\dots,k_i\} \subseteq V) — and no theory currently guides the choices of qq, KK, TT and ρ\rho.

The paper's discussion poses the missing theory as future work: weaker sufficient conditions than OIP; non-idealized, data-dependent iteration bounds; convergence guarantees when the subproblem optimizer fC(V)f_C(V) is only approximated — for generalized linear models (GLMs), regression models whose mean is linked to a linear predictor through a non-identity link such as logistic regression, no leaps-and-bounds analogue is known and subproblems must be solved numerically or heuristically; model-selection consistency when pp diverges with nn; and Bayesian extensions. On the last point the same authors subsequently proposed the Metropolized Adaptive Subspace (MAdaSub) algorithm — an adaptive independent Metropolis–Hastings sampler for high-dimensional posterior model distributions (a Markov chain Monte Carlo method that proposes a whole model at a time and accepts or rejects it), whose proposal probabilities adaptively converge to the posterior inclusion probabilities — and proved its ergodicity in serial and parallel versions; however, its mixing time, i.e. the time needed for the adaptive chain to approach its stationary distribution, is explicitly left open by that follow-up.

Problem Statement

Develop the missing convergence and statistical theory of adaptive subspace search for high-dimensional variable selection, as posed in the discussions of Staerk, Kateri and Ntzoufras (2021) (components (a)–(d)) and of their MAdaSub follow-up Staerk, Kateri and Ntzoufras (2024) (component (e)). For the AdaSub algorithm defined in the Background (criterion CC with subproblem optimizer fCf_C, criterion-optimal model S∗=fC(P)S^* = f_C(P), tuning parameters q,K,T,ρq, K, T, \rho), develop the following, where each of the five components (a)–(e) is an independent research question and a complete resolution of any one of them is a genuine resolution of the problem:

(a) Conditions. Find sufficient conditions for almost-sure convergence of AdaSub to S∗S^* (in the sense rj(t)→1{j∈S∗}r_j^{(t)} \to \mathbf{1}\{j \in S^*\} for all jj) that are strictly weaker than the Ordered Importance Property (OIP and its appendix variant OIP'), and that are verifiable or provable, so that the convergence guarantee applies in realistic finite-sample settings.

(b) Speed. Derive non-idealized, data-dependent bounds on the number of iterations needed for the thresholded model S^ρ\hat S_\rho to equal S∗S^* (or for S∗S^* to be sampled), going beyond the finite-sample-PF best case and the minimal-OIP worst case; in particular, rigorous rates under common high-dimensional random-design regimes.

(c) Approximate subproblems. Extend the convergence guarantees to settings where the exact subproblem optimizer fC(V)f_C(V) is replaced by an approximate solver — heuristic enumeration or ℓ1\ell_1-type methods (such as the Lasso, which penalizes the least-squares loss by the ℓ1\ell_1-norm of the coefficient vector) in linear models, or numerical optimizers for generalized linear model (GLM) subproblems where exact enumeration is impractical — with explicit error conditions under which convergence to S∗S^*, or to a certified approximation of it, still holds. It suffices to establish the result for one explicitly specified instance of these solver classes.

(d) Consistency. Prove model-selection consistency of AdaSub's output (e.g. of S^ρ\hat S_\rho or S^b\hat S_b) for concrete criteria such as BIC or EBIC when the dimension p=pnp = p_n diverges with the sample size nn at specified rates, in the sense that the true underlying model S0={j∈P:βj≠0}S_0 = \{j \in P : \beta_j \neq 0\} is recovered with probability tending to one as nn and the number of iterations grow, and characterize how the adaptive sampling interacts with these asymptotics. It suffices to establish the result for one explicitly specified instance of these criteria. (The source only sketches the fixed-pp BIC case.)

(e) Bayesian variant. For the MAdaSub algorithm, whose ergodicity is already proven, derive mixing-time or speed-of-convergence results for the adaptive Markov chain.

References

  1. Christian Staerk, Maria Kateri, Ioannis Ntzoufras (2021). High-dimensional variable selection via low-dimensional adaptive learning. Electronic Journal of Statistics 15(1), 830-879. DOI: 10.1214/21-EJS1797; arXiv:1905.00105. https://arxiv.org/abs/1905.00105
  2. Christian Staerk, Maria Kateri, Ioannis Ntzoufras (2024). A Metropolized Adaptive Subspace Algorithm for High-Dimensional Bayesian Variable Selection. Bayesian Analysis 19(1). DOI: 10.1214/22-BA1351; arXiv:2105.01039. https://arxiv.org/abs/2105.01039
  3. Peter Bühlmann, Martin Kalisch, Markus H. Maathuis (2010). Variable selection in high-dimensional linear models: partially faithful distributions and the PC-simple algorithm. Biometrika 97(2), 261-278. DOI: 10.1093/biomet/asq008. https://doi.org/10.1093/biomet/asq008
  4. Tianyi Yao, Genevera I. Allen (2020). Feature Selection for Huge Data via Minipatch Learning. arXiv:2010.08529. https://arxiv.org/abs/2010.08529
  5. Christian Staerk, Andreas Mayr (2021). Randomized boosting with multivariable base-learners for high-dimensional variable selection and prediction. BMC Bioinformatics 22, Article 441. DOI: 10.1186/s12859-021-04340-z. https://doi.org/10.1186/s12859-021-04340-z
  6. Carlo Maj, Christian Staerk, Oleg Borisov, Hannah Klinkhammer, Ming Wai Yeung, Peter Krawitz, Andreas Mayr (2022). Statistical learning for sparser fine-mapped polygenic models: The prediction of LDL-cholesterol. Genetic Epidemiology 46(8), 589-603. DOI: 10.1002/gepi.22495. https://doi.org/10.1002/gepi.22495
  7. Hannah Klinkhammer, Christian Staerk, Carlo Maj, Peter Michael Krawitz, Andreas Mayr (2023). A statistical boosting framework for polygenic risk scores based on large-scale genotype data. Frontiers in Genetics 13, Article 1076440. DOI: 10.3389/fgene.2022.1076440. https://doi.org/10.3389/fgene.2022.1076440
  8. Elena McDonald, Xin Wang (2023). Generalized regression estimators with concave penalties and a comparison to lasso type estimators. METRON 82(2), 213-239. DOI: 10.1007/s40300-023-00253-4. https://doi.org/10.1007/s40300-023-00253-4
  9. Alexander Beckers, Tim Hommen, Marco Becker, Mia J. K. Kornely, Eike Reuter, Gonsalves Grünert, Lucia Ortjohann, Jannis Jacob, Philipp Niemietz, Sebastian Barth, Thomas Bergs (2022). Digitalized manufacturing process sequences - foundations and analysis of the economic and ecological potential. CIRP Journal of Manufacturing Science and Technology 39, 387-400. DOI: 10.1016/j.cirpj.2022.09.001. https://doi.org/10.1016/j.cirpj.2022.09.001
  10. Djibril Ndiaye, Khader Khadraoui (2025). Bayesian Adaptive Variable Selection with a Generalized g-prior. Methodology and Computing in Applied Probability 27(4), Article 94. DOI: 10.1007/s11009-025-10226-x. https://doi.org/10.1007/s11009-025-10226-x
  11. Mahdi Nouraie, Connor Smith, Samuel Müller (2026). Bayesian stability selection and inference on selection probabilities. Statistics and Computing 36(2), Article 62. DOI: 10.1007/s11222-025-10820-6; arXiv:2410.21914. https://arxiv.org/abs/2410.21914
  12. Mahdi Nouraie, Houying Zhu, Samuel Müller (2025). A Stable Lasso. arXiv:2511.02306. https://arxiv.org/abs/2511.02306