Swarm-Searched Block Kernels for Gaussian Processes on Tiny, Wide Datasets

When a dataset has two thousand gene measurements but only sixty patients, a Gaussian process can still make useful predictions with calibrated uncertainty. A Gaussian process (GP) is a Bayesian regressor whose behaviour is fixed by a similarity function between inputs, called the kernel. What it cannot survive is a kernel that treats all two thousand features alike. Distances between samples become nearly identical, the covariance matrix flattens toward the identity, and predictions become uninformative. The usual fix gives every feature its own tunable length-scale ("automatic relevance determination"). With sixty samples, though, thousands of length-scales overfit, and gradient tuning of them gets stuck in poor local optima. Swarm search does not rescue this approach either, because particle swarm optimization (PSO) loses its footing once the search space reaches hundreds of dimensions.

We propose moving the search to a different level. We first sort features inside each training fold into roughly 10–30 blocks of correlated features. The kernel is then a weighted sum of per-block similarities plus one multiplicative interaction term. A binary gate for each block decides whether that block also enters the interaction term. The result is a mixed search space of about 50–100 parameters: continuous block length-scales and weights, plus discrete interaction gates. That space is small enough for a swarm to cover and has discrete structure that gradients cannot handle. Every hyperparameter setting the swarm evaluates is scored by the GP's closed-form leave-one-out predictive log-likelihood. Predictions average over all remembered settings, weighted by their scores, rather than trusting the single best particle. The claim is that this pairing of a coarse, gated block kernel with swarm search that averages its own history matches strong baselines on accuracy for high-dimensional low-sample-size (HDLSS) benchmarks. It should also give better-calibrated uncertainty and more stable feature attributions than GPs whose hyperparameters are tuned with gradients or picked as a single best point.

Core Claim

In the $p \gg n$ regime, the bottleneck for GP regression is not only poor local optima of the tuning objective. The objective itself is noisy, because sixty samples score each hyperparameter setting. An aggressive global optimizer that returns only its best point will exploit that noise. The proposal therefore makes two separable claims. First, a low-dimensional gated block kernel is the right place to spend search effort, rather than per-feature length-scales. Second, averaging over the swarm's full evaluation memory counteracts the noise that global search would otherwise overfit.

The kernel is

$$k(\mathbf{x},\mathbf{x}') = \sum_{b=1}^{G} w_b\, k_{\ell_b}(\mathbf{x}_b,\mathbf{x}'_b) \;+\; w_0 \prod_{b:\, z_b=1} k_{\ell_b}(\mathbf{x}_b,\mathbf{x}'_b),$$

where the symbols are defined as follows:

  • $\mathbf{x}_b$ is the sub-vector of features in block $b$.
  • $k_{\ell_b}$ is a Matérn kernel with length-scale $\ell_b$.
  • $w_b \ge 0$ are block weights.
  • $z_b \in \{0,1\}$ is the gate admitting block $b$ into the single interaction term, and $w_0$ is that term's weight.

The swarm's archive $\{\theta_j, s_j\}$ pairs each evaluated setting $\theta_j$ with its leave-one-out score $s_j$. Prediction uses the archive-weighted mixture

$$p(y_* \mid \mathbf{x}_*) = \sum_j \frac{e^{s_j/\tau}}{\sum_{j'} e^{s_{j'}/\tau}}\; p(y_* \mid \mathbf{x}_*, \theta_j),$$

where the temperature $\tau$ is chosen by inner cross-validation. Leave-one-out GP scores are exact and cheap here, since $n \le 200$ makes each $O(n^3)$ solve trivial.

Relation to Prior Work

Several papers motivate the gap.

Other work supplies methods we reuse.

Research Program

The build has three parts.

  1. In-fold block construction. Features are ordered by a correlation-graph heuristic and cut into $G$ contiguous blocks. $G$ is treated as a searched integer.
  2. Hybrid swarm. Continuous particles cover $\log \ell_b$, $\log w_b$ and $\log w_0$. Binary quantum-behaved particles cover $z_b$.
  3. Archive-weighted predictor. Predictions average over every setting the swarm has scored, as in the second equation above.

Classification benchmarks are handled as GP regression on $\pm 1$ labels, the same least-squares view as an LS-SVM. The predictive variance is then passed through a probit link for probabilities.

An analysis thread tests the assumption the design rests on. The assumption is that correlated blocks have low effective dimension, so that distance concentration within a block is mild. We measure the ratio of spread to mean of pairwise distances per block against the same ratio on the full feature set. If blocks still concentrate, each block is replaced by its top in-fold principal components. Every step that looks at data, including ordering, blocking and temperature choice, sits inside nested cross-validation.

Baselines

Naive reference points. The first is the majority-class rate on each dataset. The second is an isotropic Matérn GP on all standardized features with its three hyperparameters fit by marginal likelihood. The second shows how much of any gain comes from structure at all. Beating it by a wide margin is necessary but not interesting.

Filter-then-swarm. This is the approach of the Binary QPSO/SVM cancer paper, rerun here. Features are pruned to the top 50 by t-test, then binary swarm feature selection is combined with an SVM tuned by PSO. It uses our folds and the same budget of fitness evaluations. It is the most direct swarm competitor.

Lasso logistic regression. This is the strong linear reference. It is tuned by inner cross-validation on the same folds.

Full per-feature relevance GP. This GP has $p$ length-scales and an $L_1$ penalty on inverse length-scales, following the LassoBO objective. It is fit by multi-start L-BFGS, and the number of restarts is set to match our evaluation budget in wall-clock time.

Strongest existing methods. These are GOTabPFN, ProtoGate and Random forest kernel for high-dimension low sample size classification. The reported results available are:

Method Reported result Source
GOTabPFN 88.18±10.05% accuracy on Colon GOTabPFN paper
GOTabPFN Best average rank, 1.12, across 16 datasets GOTabPFN paper
ProtoGate Average rank 2.00 on its HDLSS biomedical suite ProtoGate paper
RFSVM Highest accuracy on 16 of 40 datasets RFSVM paper

No per-dataset accuracies for Prostate or the other suites were found on Lacuna. For those, we rerun public code where possible under our splits rather than quoting numbers. "Beating" GOTabPFN on accuracy means being within its reported standard deviation on Colon while clearly beating it on Brier score and expected calibration error. Given its ±10% spread, matching it is the realistic target and outright accuracy wins would be a bonus.

Ablations isolating the key ingredients. Each ablation keeps the same block kernel and the same evaluation budget, and changes one thing:

  • Multi-start L-BFGS with gates relaxed to sigmoids. This isolates the swarm against gradients.
  • Random search. This isolates the swarm against unguided sampling.
  • The single global-best particle instead of archive averaging. This isolates the averaging.
  • All $z_b = 0$. This isolates the interaction term.
  • Blocks formed at random rather than by correlation ordering. This isolates the blocking.

Why not just…?

Why not just tune per-feature length-scales with multi-start L-BFGS and an $L_1$ penalty? The additive-kernel study reports likelihood-maximization collapse at only $d \ge 12$. Elastic GP reports multi-start BFGS stalling on flat 50-dimensional terrain. At $p = 2000$ with $n = 62$, the problem is also statistical, since thousands of length-scales cannot be identified. The full relevance-GP baseline tests this directly on calibration and on bootstrap stability of the top-ranked features. We expect its attributions to be the least stable.

Why not just use random search or a Bayesian optimizer like Optuna over the same small block space? This is a genuine threat. At roughly 50–100 dimensions, random search and Bayesian optimization are reasonable. If random search matches the swarm at equal budget, we will report that the contribution lies in the gated block kernel and archive averaging, not in PSO. The equal-budget ablation settles it. The one place we expect the swarm to earn its keep is the discrete gates, where Bayesian optimization handles combinatorial structure poorly.

Why not just sample hyperparameters with MCMC instead of averaging a swarm archive? Averaging weighted by leave-one-out scores is a crude approximation of what a fully Bayesian GP does. A Metropolis-within-Gibbs sampler, flipping gates and slice-sampling the continuous parameters, is the principled version. We run it at the same number of GP solves. If it matches archive averaging, the swarm's role reduces to an efficient explorer. That is still useful, but a weaker claim. No reported result for such a sampler on these benchmarks was found on Lacuna.

Why not just use GOTabPFN? Its reported Colon accuracy is strong. However, it is capped at $n \le 1{,}000$ and gives no closed-form posterior variance, and its own feature ordering still needs Optuna tuning. Our proposal competes on uncertainty quality and interpretable block interactions, and we will state plainly if its accuracy is higher.

Proposed Experiments

Synthetic check. The decisive first experiment is synthetic. We generate $p = 2000$, $n = 60$ correlated Gaussian features in 20 blocks. The target is additive in three blocks plus a product of two other blocks that each carry no marginal signal. We then ask two questions. Does the swarm recover the two interaction gates? Does a t-test filter provably miss them?

Real benchmarks. The main evaluation uses the eight HDLSS suites from GOTabPFN (Colon, Lung, GLI-85, SMK_CAN_187, ALLAML, Prostate-GE, Arcene, TOX-171) plus the HDLSS subset of the RFSVM collection. The protocol is 5×5 nested cross-validation. We report accuracy, Brier score, expected calibration error, average rank, and Jaccard stability of the selected gated blocks across 50 bootstraps.

Outcomes that decide the claims.

  • The central claim fails if archive averaging does not beat the global-best particle on calibration.
  • The interaction term is unnecessary if all-zero gates perform as well.
  • The swarm is unnecessary if random search at equal budget matches it.

Each outcome is reported whichever way it falls.