A prognostic gene signature is a short list of genes, usually 3 to 22, whose combined expression sorts cancer patients into higher- and lower-risk groups. Signatures are usually found by screening each gene on its own and then running an L1-penalized (LASSO) survival regression on the genes that pass. They often fail to hold up on new patients. This note argues that the scarce resource in signature discovery is not computation. It is the finite, reusable stock of patients used to score candidate signatures. Each candidate panel scored on the same patients makes the best-looking panel look better than it really is, much as the luckiest of many coin-flippers looks skilled. Under that view, choosing which candidate panel to score next is a sequential decision with a real cost, which is exactly what Bayesian optimization's acquisition functions are built for. These are the rules that weigh "refine what already looks good" (exploitation) against "try something different" (exploration). The setting also exposes a failure that those rules were never designed to handle.
The proposal has three parts. It searches over subsets of co-expressed gene modules rather than individual genes. It uses a sparse Bayesian surrogate with pairwise interaction terms to guide that search. It returns the panel the surrogate believes is best, rather than the panel that scored highest. The central empirical question is how the exploration setting of the acquisition function controls the gap between a signature's in-search score and its score on an independent cohort. The proposal also tests whether this design finds smaller, better-calibrated panels than elastic-net Cox regression and simple greedy search. It has to win on cases with real gene interactions, and it should not lose on additive ones.
Core Claim
Treating signature selection as combinatorial Bayesian optimization is the obvious bridge between these fields, and the file confirms nobody has done it. The bridge is only worth building with one change. The objective must be framed as a noisy estimate drawn repeatedly from a fixed patient pool, not as an expensive but exact black box. In that setting, the observed incumbent best $y^+$ that Expected Improvement and Probability of Improvement chase is inflated by selection. A rough guide to the size of that inflation comes from the expected maximum of $N_{\text{eff}}$ independent Gaussian noise draws:
$$\mathbb{E}[\text{optimism}] \approx \sigma \sqrt{2 \log N_{\text{eff}}}.$$
Here $\sigma$ is the standard deviation of the cross-validated score of one panel, and $N_{\text{eff}}$ is the effective number of roughly independent panels evaluated.
Exploration changes this quantity in two directions at once. Exploratory search evaluates diverse panels, which raises $N_{\text{eff}}$. Exploitative search re-scores near-duplicates, which keeps $N_{\text{eff}}$ low, but it can climb a noise peak specific to one cohort. Which effect dominates in transcriptomic survival data is unknown. The claim is that a surrogate which pools evidence across overlapping panels, together with a final pick made on posterior mean, substantially reduces this optimism. The claim also expects an intermediate exploration level to minimize external error, and that level should be measurable with a discrete version of existing exploration metrics.
What Prior Work Does and Does Not Do
The motivating evidence comes from omics survival work. Unbiased Prediction and Feature Selection in High-Dimensional Survival Regression (SurvRank) uses repeated nested cross-validation to obtain honest accuracy estimates. In its simulation ($n=100$, $p=500$), Cox-Lasso lost about 6% of its concordance (Uno's C) from training to test. On breast cancer microarrays, Cox-Lasso selected 53 genes against 24 for survLasso. SurvRank makes the estimate honest but still selects passively. Our proposal keeps its nested structure and changes how the inner search chooses what to score. Sparse Feature Selection for Prognostic Survival Models describes the standard two-stage pipeline. It notes that LASSO keeps one arbitrary member of a correlated group, and that univariate screening discards genes whose effect only appears jointly. That observation motivates searching over modules formed without using the outcome.
Bayesian optimization has touched survival modeling in two ways, and neither searches gene subsets. AutoPrognosis tunes whole modeling pipelines on low-dimensional clinical registries, reaching AUC-ROC 0.78 on MAGGIC against 0.75 for Cox. Active Learning based Survival Regression for Censored Data (ARC) chooses which patients to label, using a greedy gradient criterion. Our proposal works in the feature space instead and uses explicit uncertainty-driven acquisition.
The method comes from Bayesian Optimization of Combinatorial Structures (BOCS). BOCS fits a second-order polynomial surrogate over binary inputs with a horseshoe shrinkage prior, a prior that pushes most coefficients toward zero. It then uses Thompson sampling, which picks the next point by optimizing a random draw from the posterior, solved with semidefinite relaxation or simulated annealing. BOCS has never seen censored outcomes, and like standard BO it reports the observed best. We change the objective, the dimension scaling, and the final recommendation. The search-diversity measure is adapted from Exploring Exploration in Bayesian Optimization. That paper defines the observation traveling salesman distance (OTSD) for continuous domains and leaves discrete spaces open. It also warns that Thompson sampling degenerates into near-random search above roughly 20 dimensions. Two findings constrain how far exploration can be pushed: that warning, and the observation in Large-scale Pretraining Improves Sample Efficiency of Active Learning based Molecule Virtual Screening that UCB weights above 2 reduce hit recovery.
Position: Stop Chasing the C-index when Evaluating Survival Analysis Models shows that concordance can reward miscalibrated models under non-random censoring. This constrains the objective. Optimizing concordance inside a search loop invites the search to exploit artifacts of how patients drop out of follow-up, so we optimize a likelihood-based score instead.
Research Program
Expression profiles are first grouped into $M \approx 100$–$200$ co-expression modules using only expression data. Each module is summarized by its first principal component. This module-level search replaces outcome-based univariate screening. It also tests whether co-regulation reduces the effective dimension enough to escape the high-dimensional exploration trap.
A candidate is a binary vector $z \in \{0,1\}^M$ with at most $k$ active modules. To score it, we fit a small survival model on the active modules inside inner cross-validation folds of the training cohort. The model is a discrete-time hazard model with main effects plus pairwise products, lightly penalized. The score is the held-out censored log-likelihood, a proper scoring rule under independent censoring. Concordance is logged but never optimized.
The surrogate is the BOCS quadratic form $f(z) = \alpha_0 + \sum_j \alpha_j z_j + \sum_{i<j} \alpha_{ij} z_i z_j$ with horseshoe priors. Its noise variance is estimated from fold-to-fold spread rather than assumed to be zero. We compare three acquisition rules: Thompson sampling, UCB over a sweep of $\beta$ values, and Expected Improvement computed against the posterior-mean incumbent rather than the observed one.
At the end of the budget, the recommended panel is $\arg\max_z \mathbb{E}[f(z) \mid \mathcal{D}]$ under the cardinality constraint, rather than the highest observed score. Each chosen module is then reduced to its one to three genes most correlated with the module summary, which yields a compact panel for clinical use. Exploration is measured with a Jaccard-distance OTSD on the sequence of queried subsets. This is a direct discrete analogue of the continuous metric and lets the $\beta$ sweep be plotted on a common diversity axis.
Baselines
The naive reference point is the standard two-stage pipeline: univariate Cox screening at a fixed threshold followed by LASSO-Cox, as described in Sparse Feature Selection for Prognostic Survival Models. It is run on the same training cohort with the penalty chosen by inner cross-validation. It represents what most published signatures actually do.
The strongest linear competitor is elastic-net Cox fit directly on the module summaries and on all genes, together with SurvRank's survLasso and survRand with weighted final selection (Unbiased Prediction and Feature Selection in High-Dimensional Survival Regression). These are the methods most likely to match ours whenever the true signal is additive.
The strongest search competitors use our exact evaluator and our exact evaluation budget, so any difference comes from how candidates are chosen. They are random search over module subsets and greedy forward selection over modules. A gradient-based competitor is a DyS-style model with smooth-step gates and RPS loss (Interpretable Prediction and Feature Selection for Survival Analysis), trained on module summaries with matched panel size and wall-clock budget.
As a dense upper reference, we run DeepSurv (DeepSurv) on all module summaries. DeepSurv reports a METABRIC C-index of 0.867 against 0.816 for linear Cox. That figure was obtained on DeepSurv's own METABRIC feature set, not a genome-wide panel search, so it is not directly comparable. We will rerun DeepSurv under our splits rather than quote it.
Two ablations isolate the key ingredients. The first is standard BOCS with observed-best recommendation, which isolates the posterior-mean pick. The second is the full method run on gene-level inputs after lenient univariate screening, which isolates the role of the modules.
All methods share splits, hyperparameter-tuning budgets, and panel-size limits. Beating a baseline means a better external-cohort censored log-likelihood at equal or smaller panel size, a smaller optimism gap, and confidence intervals from bootstrap resampling of the external cohort that exclude zero.
Why not just…?
Why not just use elastic-net Cox or stability selection? If prognostic signal in breast cancer transcriptomes is essentially additive, this alternative will probably match us, and that is a real threat. The answer has to come from the experiments rather than argument. The semi-synthetic test below plants module pairs with weak marginal effects but a strong joint effect. LASSO is structurally unable to recover those pairs when it starts from univariate screening (Sparse Feature Selection for Prognostic Survival Models), and it handles them poorly even without screening. On real cohorts, if elastic net on module summaries ties us, we report that the surrogate search adds nothing for additive signal. The remaining contribution would then be the optimism analysis.
Why not just run greedy forward selection or random search inside nested cross-validation? Nested cross-validation gives an honest number for whatever was selected. It does not make the selection better. Greedy search is a pure-exploitation policy, and random search is a pure-exploration policy. Both appear as endpoints of our exploration sweep under identical budgets, so this alternative is tested directly. If either one matches the surrogate method on external error, the surrogate is not earning its cost.
Why not just use differentiable gates as in DyS? Gradient descent over relaxed gates follows a single trajectory and carries no uncertainty over subsets it has not tried. Its final panel is therefore effectively an observed-best choice along that trajectory. DyS reports a mean AUC of 0.826 with about 50 features against DeepHit's 0.829 with all 2,410 features on a clinical heart-failure cohort (Interpretable Prediction and Feature Selection for Survival Analysis). It has not been run on genome-wide expression. We run it at matched panel size. If it matches us on both external error and optimism gap, the explicit exploration machinery is unnecessary.
Proposed Experiments
The first experiment is semi-synthetic. We take real METABRIC expression, so that real co-expression structure is preserved, and simulate survival outcomes from known module sets. The planted signal is either additive or a set of interaction pairs with weak marginals. Censoring is either independent or dependent on the outcome. Because the true risk model is known, we can measure recovery of the true modules, the excess risk of the recommended panel, and the optimism gap exactly. The decisive check here is whether the posterior-mean recommendation shrinks the optimism gap relative to observed-best BOCS. A second check is whether optimizing concordance instead of log-likelihood under dependent censoring yields panels with worse true calibration, as the position paper predicts.
The second experiment uses real data. We discover on one METABRIC partition and validate on a disjoint partition. We repeat the analysis on the public breast cancer microarray cohorts used by SurvRank. We report external log-likelihood, integrated Brier score, calibration slope, C-index, and panel size.
The third experiment is the exploration sweep. We plot Jaccard-OTSD against the optimism gap and against external error across UCB $\beta$ values, Thompson sampling, greedy search, and random search. The hypothesis predicts an interior minimum in external error. A monotone curve would falsify it, and either outcome is informative about Gap 3, the question of whether co-regulation tames high-dimensional exploration.
No reported result on Lacuna covers combinatorial BO for survival signatures, so every number for the proposed method will be new. The success criterion is concrete. Across seeds, the method should beat elastic net and greedy search on external log-likelihood in the interaction scenarios, should not lose in the additive scenarios, and should show a smaller optimism gap than observed-best selection.
References
- Unbiased Prediction and Feature Selection in High-Dimensional Survival Regression
- Identification of a microRNA signature associated with risk of distant metastasis in nasopharyngeal carcinoma
- AutoPrognosis: Automated Clinical Prognostic Modeling via Bayesian Optimization with Structured Kernel Learning
- Active Learning based Survival Regression for Censored Data
- Bayesian Optimization of Combinatorial Structures
- Exploring Exploration in Bayesian Optimization
- Large-scale Pretraining Improves Sample Efficiency of Active Learning based Molecule Virtual Screening
- Position: Stop Chasing the C-index when Evaluating Survival Analysis Models
- Interpretable Prediction and Feature Selection for Survival Analysis
- DeepSurv: personalized treatment recommender system using a Cox proportional hazards deep neural network