Cross-Chain Substitute Proposals for High-Dimensional Bayesian Variable Selection

When a scientist asks which of a million genetic markers explain a trait, the honest answer is often "one of several near-equivalent sets." Two markers that are almost perfectly correlated can each stand in for the other. Bayesian variable selection is the approach that tries to report a probability for every candidate set rather than a single winner. It runs a Markov chain Monte Carlo (MCMC) sampler, a random walk that visits candidate sets in proportion to their posterior probability. In large problems that walk gets stuck. It adds whichever of the twin markers it happens to meet first, and it can then almost never switch, because every intermediate step is improbable: dropping the marker loses the signal, and adding its twin pays a heavy penalty for redundancy. This is premature convergence, the failure studied in swarm and population search. Here it has a statistical cost: the reported probability that each variable matters comes out confidently wrong.

We propose running a small population of exact samplers that do not share states but do share hints. When chain $i$ is updated, it may propose to swap one of its variables for a variable that another chain currently holds and chain $i$ does not. The proposal is also tilted toward variables that few chains hold. Because the other chains are frozen while chain $i$ moves, a standard Metropolis–Hastings correction makes every such move leave the true posterior unchanged. The population therefore pushes chains apart, as metaheuristic diversity methods do, without biasing the answer. The swaps are drawn from substitutes the population has actually found, a set of size roughly $K k$ for $K$ chains holding $k$ variables each. The cost of these block-like moves therefore does not grow with the number of candidate variables $P$.

Core Claim

The central claim concerns where the substitutes come from. They can be discovered by the population instead of precomputed from the design matrix. Interaction between chains can enter only through the proposal, so the target stays exact. Together these resolve a tension the literature leaves open. Scalable samplers need cheap one-variable or small-subset updates. Escaping traps formed by correlated variables needs joint swaps, and joint swaps are expensive when chosen over all pairs of variables.

The validity argument is the classical one for population MCMC on a product space. If the kernel used to move chain $i$, which may be any function of the other chains' current states $\gamma_{-i}$, leaves $\pi(\gamma \mid y, X)$ invariant for every fixed $\gamma_{-i}$, then a sweep over chains leaves $\prod_{i=1}^K \pi(\gamma_i \mid y, X)$ invariant. For a cross-chain swap $\gamma_i \to \gamma_i'$ the acceptance probability is

$$\alpha = \min\left\{1,\ \frac{\pi(\gamma_i' \mid y)\, q(\gamma_i \mid \gamma_i', \gamma_{-i})}{\pi(\gamma_i \mid y)\, q(\gamma_i' \mid \gamma_i, \gamma_{-i})}\right\}.$$

Here $q(\cdot \mid \gamma_i, \gamma_{-i})$ is the probability of proposing a swap given chain $i$'s state and the frozen states of the others. The reverse probability is computed with the same $\gamma_{-i}$, so it is well defined.

The repulsion lives entirely inside $q$. For each variable $j$, let $c_j$ be the fraction of other chains that currently contain it. The variable to add is drawn with weight proportional to a locally informed improvement times $(1 - c_j + \epsilon)^{\lambda}$, where $\epsilon$ is a small constant that keeps every weight positive and $\lambda \ge 0$ sets the repulsion strength. Setting $\lambda = 0$ gives pure substitute discovery with no repulsion.

Relation to Prior Work

Three lines of work motivate the proposal by showing the trap exists. Determinantal Regularization for Ensemble Variable Selection (DREVS) runs an ensemble of expectation–maximization searchers with a determinantal repulsion penalty that "punches holes" in model space. On 0.99-correlated blocks it recovers more than half the posterior mass where plain EM collapses to one mode. Its repulsion, however, changes the objective, so it returns modes rather than calibrated probabilities, and it was tested only up to $P = 88$. We keep its insight that searchers should repel each other, but we move the repulsion from the objective into the proposal and so keep the posterior exact.

Adaptive random neighbourhood informed MCMC (PARNI) reaches $P \approx 80{,}000$ by tracking inclusion probabilities to build informed neighbourhoods. Its authors state that one-variable updates cannot cross between near-duplicate predictors and that block moves are needed. Bayesian Variable Selection in a Million Dimensions (Subset wTGS) reaches $P = 10^6$ by fixing an anchor set of promising variables and sampling small random batches around it. Its anchor set, chosen during burn-in, can freeze an early false mode.

Both samplers supply the base moves that we reuse unchanged. Our contribution is a cross-chain move layered on top of each. For Subset wTGS, the batches of chain $i$ are augmented with variables from other chains' active sets. The tempered auxiliary target that wTGS samples, and later reweights, is preserved for every fixed $\gamma_{-i}$.

Mode jumping MCMC constrains the design. It shows that aggressive non-local proposals remain exact if reverse moves are accounted for. It also warns that hand-tuned jump kernels give high variance across replications, which is why our jumps are proposed from the population and not from a tuned kernel. The genetic population sampler of Subsampling MCMC for BGNLM evolves features through crossover but has no explicit diversity pressure. It also targets tall data with $P = 50$, which is a different regime.

From the optimization side, Multiple-Frequencies Population-Based Training shows that symmetric copying between agents collapses a population. Standard population-based training falls to 16,171 interquartile-mean reward on Humanoid, below random search at 17,713. Asymmetric copying instead reaches 23,793. We take the lesson that information should flow without cloning: chains read each other's variables but never copy each other's states.

Divergence-Guided PSO and DynAMO document the price of repulsion on easy landscapes. Swarm repulsion fails to settle on the unimodal Sphere function, and distribution matching lowers median batch quality. In our sampler the target is exact, so repulsion can cost only efficiency, never correctness. We measure that cost directly on easy designs instead of assuming it away.

Research Program

We will build the cross-chain move as a plug-in for two base samplers. The first is PARNI for conjugate linear regression. The second is Subset wTGS, using the authors' millipede GPU library, for linear and Pólya-Gamma logistic regression. A population of $K$ chains is updated in sequence. Each update is a mixture: with probability $1-\rho$ the chain takes its native base move, and with probability $\rho$ it takes a cross-chain swap. The swap removes one variable from chain $i$ and adds one variable from the union of other chains' active sets, which has at most about $Kk$ members. Removal weights use the residual correlation between chain $i$'s variables and the candidate. These correlations are computed only for the pooled candidates, at a cost of order $N K k^2$ per update with no dependence on $P$.

The mixture weight $\rho$ is held fixed within a run so that the analysis stays simple. We will also study a diminishing adaptation of $\rho$ and $\lambda$ driven by the swap acceptance rate. Low acceptance indicates a nearly unimodal posterior and should throttle repulsion. This is our answer to the unimodal-degradation problem.

The analysis has two parts. The first is a formal invariance proof for the mixture kernel, including the wTGS auxiliary target. The second is a short mixing argument on a stylized two-substitute posterior. On that posterior a one-variable sampler must pass through a state of probability on the order of $e^{-\Delta}$ to switch modes, where $\Delta$ is the log-posterior barrier between them. A cross-chain swap moves between modes directly whenever some other chain occupies the alternative. The interesting regime is therefore any regime where chains initially disagree, and the repulsion term exists to create and keep that disagreement.

Baselines

The naive reference point is the Add-Delete-Swap sampler. PARNI reports it as roughly $10^5$ times less efficient at $P = 50{,}000$ and stuck near the empty model on SNP data. It anchors the scale of difficulty, and we will run it at matched wall-clock time.

The strongest existing exact methods are PARNI, at $P \le 80{,}000$, and Subset wTGS, at $P$ up to $10^6$. For the strongest baseline the file reports efficiency only in relative or runtime terms. PARNI's gain is about $10^5$-fold in efficiency over Add-Delete-Swap on the $P = 50{,}000$, $n = 1{,}000$ synthetic benchmark. Subset wTGS completes inference at $P = 10^6$ on maize in about 35 minutes on one Tesla T4, with sensitivity, precision and RMSE stable from $P = 150{,}000$ to $750{,}000$, but no numeric values are given for those three metrics. No reported result was found on Lacuna for posterior-inclusion-probability error or mode coverage by either method on any of these benchmarks.

We will therefore rerun both under identical conditions. That means the same data, the same prior, and the same total compute, so that $K$ population chains are compared against $K$ independent chains of the base sampler on equal hardware time. Each method gets the same budget for tuning its own hyperparameters. Beating them means a lower error in posterior inclusion probabilities against a gold-standard reference, and more planted alternative modes visited, at equal time. The decisive comparison is against the independent-chain version, because that isolates interaction.

For the low-dimensional sets we also report DREVS, using its published figures as context. It captured more than 50% of posterior mass on the $P = 16$ blocks and the top three models carrying 16% of mass on protein data. It is not an exact sampler, however, so it is a reference rather than a competitor on calibration.

Two ablations isolate the ingredients. Setting $\lambda = 0$ keeps cross-chain swaps but removes repulsion. Replacing the population-derived candidate pool with a random pool of the same size removes the information the other chains carry.

Why not just…?

Why not just run parallel tempering or many independent restarts? Tempering flattens barriers but does not say which variable to swap in. PARNI's comparisons show that samplers without informed proposals remain stuck near the empty model at $p = 79{,}748$. Subset wTGS already tempers and still risks anchor freezing. This alternative remains a serious competitor, so independent chains at matched compute, and a tempered ladder of the same total size, are both arms of every experiment. If they match the population on mode coverage and inclusion-probability error, the claim fails.

Why not just precompute correlated neighbours and add static swap moves? This is the most serious threat. On designs built purely from pairwise near-duplicates it may tie with our method, and we will report that case honestly. Our method should win in two situations. The first is conditional substitutes, where the alternative to a variable is a combination of others that is weakly correlated with it marginally, so the design matrix does not reveal it but other chains' posterior states do. The second is scale: finding top neighbours for all $10^6$ variables costs on the order of $NP^2$, whereas the population pool costs nothing in $P$. A dedicated static-swap baseline, using top-$m$ correlated neighbours computed by the cheapest exact method we can afford, will run on both planted-pair and planted-conditional designs.

Why not just pre-filter with the Lasso, or run DREVS and reweight? The BAS/JASP tutorial notes that select-then-infer procedures give overconfident uncertainty. The Lasso hint underlying Spike-and-Slab Posterior Sampling in High Dimensions assumes conditions on the design matrix that collinear blocks violate, and under such blocks the Lasso arbitrarily keeps one member. We include a Lasso-screen-then-exact-sampling arm and expect it to miss planted alternatives that the screen discards.

Proposed Experiments

The low-dimensional checks use the DREVS benchmark of $P = 16$ with 0.99-correlated blocks, and the protein activity data with $P = 88$. For both we compute reference posteriors by exhaustive enumeration where feasible, or otherwise by very long runs. We measure posterior mass captured and inclusion-probability error.

The scaling checks use the PARNI synthetic design with $P = 50{,}000$ and $n = 1{,}000$, the PCR data with $p = 22{,}575$, and the SNP data with $p = 79{,}748$. We then move to the semi-synthetic maize data at $P$ from 150,000 to $10^6$ using millipede, with linear and logistic responses. Into each of these we plant two kinds of substitute structure, pairwise near-duplicates and conditional substitutes, so that the ground-truth set of equivalent models is known.

The metrics are mean absolute inclusion-probability error across 20 replicates, the number of planted alternative modes visited, effective sample size per second, and wall-clock overhead.

Two experiments decide the question. In the anchor-freeze test, every chain is initialized inside a planted false mode on maize, and we record the time until any chain's anchor-plus-batch set contains the true alternative, comparing Subset wTGS with and without cross-chain batches. In the unimodal-cost test, designs with orthogonal strong signals measure how much efficiency the swaps and repulsion lose, with and without adaptive throttling.

The proposal succeeds if it beats independent chains and static swaps on conditional-substitute designs at equal compute, and loses less than about 20% efficiency on unimodal designs. If static correlation swaps match it everywhere, we will conclude that population information adds nothing beyond the design matrix.