Scaling Bayesian Variable Selection in High Dimensions

22 concepts22 papers1 proposal

In modern data science, we frequently encounter datasets where the number of potential explanatory variables $P$ is massive, often far exceeding the number of observations $N$. In fields ranging from genomics to macroeconomics, we operate under the assumption of sparsity: out of thousands or millions of candidates, only a small subset of variables truly drives the outcome.

Identifying this subset is the goal of variable selection. While frequentist methods often look for a single "best" model, the Bayesian paradigm embraces uncertainty. Instead of picking one model, Bayesian Variable Selection (BVS) computes a posterior probability distribution over the space of all possible models. This allows researchers to perform Bayesian Model Averaging (BMA), yielding more robust parameter estimates and honest measures of uncertainty, as detailed by van den Bergh et al..

However, BVS faces a fundamental mathematical barrier: a combinatorial explosion. If there are $P$ potential predictors, each can either be included or excluded from the model. This creates a discrete search space of $2^P$ possible model configurations. When $P=100$, $2^{100}$ is larger than the number of atoms in the observable universe. When $P$ reaches a million, as explored by Jankowiak, exhaustive evaluation becomes completely impossible.

The Failure of Naive Sampling

To understand why this space is so difficult to navigate, consider how traditional algorithms explore it. The gold standard for specifying sparsity in a Bayesian framework is the spike-and-slab prior. For each variable, a discrete latent indicator variable $\gamma_i \in \{0, 1\}$ determines whether the variable's coefficient is zero (the "spike") or drawn from a diffuse continuous distribution (the "slab").

Standard Markov Chain Monte Carlo (MCMC) algorithms, like Gibbs sampling, navigate this space by randomly selecting an indicator and proposing to flip its state. In high dimensions, this approach fails catastrophically for two reasons:

  1. The Needle in a Haystack Problem: The posterior probability landscape is incredibly sparse. It consists of isolated, sharp peaks of high probability separated by vast deserts of near-zero probability. Randomly flipping a variable almost always moves the sampler into a desert, resulting in a rejected proposal.
  2. Local Optima Entrapment: Because the variables are often highly correlated, changing one variable at a time requires passing through states of very low probability. The sampler becomes trapped in local modes, failing to explore alternative, equally plausible combinations of variables.

To make high-dimensional BVS practical, researchers have developed three core strategies: designing informed discrete proposals, smoothing the discrete space into a continuous one, and replacing sampling entirely with optimization.

Strategy 1: Informed and Adaptive Discrete Sampling

Instead of proposing random moves through the $2^P$ hypercube, modern discrete samplers use the history of the chain or the structure of the data to make highly informed proposals.

One approach is to dynamically learn which variables belong together. Lamnisos et al. and Liang et al. developed adaptive neighborhood MCMC methods. Instead of proposing global random flips, these algorithms construct a "random neighborhood" around the current model. By adapting the size and shape of this neighborhood based on past iterations, the algorithms achieve much higher acceptance rates and avoid getting trapped in local optima.

Alternatively, one can model the correlations between the selection indicators directly. Schäfer introduced a Sequential Monte Carlo (SMC) framework that utilizes a "logistic conditionals model." By capturing the dependencies between variables, the sampler learns which predictors act as substitutes or complements, allowing it to successfully navigate complex, multi-modal landscapes where standard MCMC fails.

When scaling to ultra-high dimensions (where $P$ is in the millions), even calculating local proposals can become a bottleneck. To solve this, Jankowiak combined a subset-based tempering scheme with Polya-Gamma augmentation. This mathematical restructuring achieves a sublinear computational cost per iteration relative to $P$, making full Bayesian uncertainty quantification tractable at an unprecedented scale.

Strategy 2: Smoothing the Discrete Landscape

Discrete spaces are notoriously difficult to search because they lack geometric structure; you cannot calculate a gradient on a discrete hypercube to see which direction makes the model better. A powerful alternative strategy is to eliminate the discrete indicator variables entirely, relaxing the problem into a continuous space where geometry can guide the sampler.

Discrete Space (Spike-and-Slab)         Continuous Relaxation (e.g., Neuronized)
       Model Probability                       Model Probability
             ▲                                       ▲
             │      █                                │       ┌─┐
             │      █                                │      /   \
             │  █   █                                │   ┌─/     \─┐
             └──┴───┴──────►                         └───┴─────────┴──►
             Discrete Models                         Continuous Parameters
     (No gradients, hard jumps)               (Gradients available, smooth paths)

Shin achieved this by introducing neuronized priors. By reparameterizing traditional sparse priors using neural-network-inspired activation functions (such as the Rectified Linear Unit, or ReLU), the discrete choice of inclusion/exclusion is transformed into a continuous optimization and sampling problem. This unification bypasses the need for discrete latent indicators, resulting in faster and more stable continuous MCMC sampling.

If the model must retain a trans-dimensional structure (explicitly jumping between models of different dimensions), geometry can still be leveraged. Schreck et al. proposed the Shrinkage-Thresholding Metropolis Adjusted Langevin Algorithm (STMALA). This method uses gradient information from the continuous parameters to propose moves, combined with a thresholding operator that smoothly pushes uninformative variables to zero, providing a guaranteed rate of convergence.

Taking this a step further, Davies et al. introduced Transport Reversible Jump (TRJ) proposals. Instead of hand-tuning the complex mathematical mappings required to jump between dimensions, the authors used normalizing flows to map complex, disjoint target distributions into a simple, continuous Gaussian reference space. This automates the generation of highly efficient dimension-hopping proposals.

Strategy 3: Optimization-Based Approximations

When the model space is too vast for even advanced sampling methods, we can pivot from sampling the posterior to fitting an analytical approximation to it via optimization.

Variational Bayes (VB) revalues the problem by finding a simpler, tractable distribution (the variational family) that minimizes the Kullback-Leibler (KL) divergence to the true posterior. Ray et al. provided a critical theoretical foundation for this approach in high-dimensional logistic regression. They proved that a mean-field VB approach using a spike-and-slab prior with heavy-tailed Laplace "slabs" avoids the computational pitfalls of MCMC while maintaining optimal, minimax-convergent variable selection.

Other frameworks combine optimization with deterministic pruning of the model space. For instance, Hubin introduced an adaptive simulated annealing Expectation-Maximization (ASA-EM) algorithm to navigate the trillions of potential structures inherent in non-homogeneous hidden Markov models. Similarly, Spyropoulou et al. combined EM and VB with an "Occam's window" approximation. By immediately discarding models whose posterior probabilities fall below a certain threshold relative to the best model, they achieved a 5-6x computational speedup without sacrificing accuracy.

Theoretical Guarantees and Complex Frontiers

For a long time, spike-and-slab formulations were treated as heuristic tools in high dimensions due to a lack of provable convergence bounds. This changed with work by Kumar et al., who developed the first provable, polynomial-time algorithms for sampling from spike-and-slab posteriors when $N \ll P$. By initializing the sampler using frequentist sparse recovery techniques and refining it with a denoised rejection sampling scheme, they bridged the gap between frequentist computational efficiency and Bayesian uncertainty quantification.

These algorithmic breakthroughs have allowed researchers to deploy BVS far beyond simple linear models:

  • Semiparametric Models: Liang extended variable selection to semiparametric regression, simultaneously identifying key variables in both the parametric and non-parametric components of a model.
  • Causal Inference: In large-scale causal studies, researchers often face hundreds of potential instrumental variables, many of which may be invalid. The MASSIVE framework, developed by Bucur et al., uses robust spike-and-slab model averaging to automatically isolate valid instruments and provide clean causal estimates.
  • Non-Linear Latent Models: To bring BVS to non-Gaussian data like counts and rates, Steel et al. introduced Univariate Link Latent Gaussian Models (ULLGMs). By placing a hidden Gaussian layer between the predictors and the outcome, they tamed the combinatorial explosion of predictor combinations in non-linear regression frameworks.

By moving away from blind random walks and toward geometry-informed sampling, continuous relaxations, and variational optimization, modern statistics has successfully tamed the exponential complexity of model spaces. Researchers can now rigorously quantify model uncertainty in dimensions that were once considered computationally impossible.

Key Foundational Work

Adaptive Monte Carlo for binary regression with many regressors (2009) — contributed 1 concept elements to this direction.
Variable selection in semiparametric regression modeling (2008) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_combinatorial_model_space_explosion_4c516e6f,
  title = {combinatorial model space explosion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-model-space-explosion/rdr_4c516e6f251f4fbfa8c54d07360c3180},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_combinatorial_model_space_explosion_4c516e6f_v1,
  title = {combinatorial model space explosion},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/combinatorial-model-space-explosion/rdr_4c516e6f251f4fbfa8c54d07360c3180/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake