Many of the most informative similarity measures in biology — Smith-Waterman sequence alignment scores, Levenshtein edit distances — are not valid kernels: their pairwise similarity matrices have negative eigenvalues, so they break the mathematical machinery that most learning and search algorithms assume. A separate line of work on multi-objective search assumes something equally fragile: that similarity forms a proper distance (non-negative, obeying the triangle inequality), which these biological measures also violate. Meanwhile, the peptide-discovery problems where such similarities excel are inherently multi-objective: a good antimicrobial peptide must kill a target pathogen while sparing human cells, and no single scalar score captures that tension. This proposal builds a screening algorithm that runs Pareto-front search natively over indefinite similarities, and validates it on real antimicrobial peptide datasets rather than the 2D toy benchmarks the field currently relies on.
The core mechanism is a simple decoupling. Any indefinite similarity can be split, via its eigenvalue spectrum, into two ordinary positive-definite parts, $K = K_+ - K_-$, which is exactly the decomposition underlying Krein-space learning Learning in Reproducing Kernel Krein Spaces and Scalable Learning in Reproducing Kernel Krein Spaces. We use the sum of the two parts, $k_M = k_+ + k_-$ (the "majorant" kernel), to define neighborhoods for exploration — this sum is always a valid positive-definite kernel, so distances derived from it form a genuine metric — while predictions themselves use the full indefinite inner product, preserving the structural information stored in the negative spectrum. In two sentences: we explore in a geometry where the search algorithm's assumptions hold, and predict with the similarity the domain expert actually gave us.
Core Claim
The claim is threefold. First, multi-objective bandit search of the type theorized by the Pareto Contextual Zooming (PCZ) algorithm Multi-objective Contextual Bandit Problem with Similarity Information — which partitions the space into metric balls, tracks one confidence bound per objective, and refines balls near the Pareto front — can be made to run over indefinite, non-metric similarities by defining its partitioning geometry through the majorant metric while its reward estimates live in the Krein space. Second, this can be validated empirically: PCZ itself has zero experiments, and every indefinite-kernel method in the literature optimizes a single scalar objective, so no existing result tells us whether similarity-guided Pareto search works at all on real structured data. Third, the standard practice of developing and tuning such algorithms on synthetic indefinite kernels has an unmeasured cost, which we quantify as an explicit synthetic-to-real "exchange rate": how many extra real evaluations a policy tuned on synthetic spectra needs to match the same policy tuned on real data.
Research Program
The algorithm, which we call majorant-zooming Pareto search, works as follows. Given candidates $x$ with an indefinite pairwise similarity $k(x, x')$ (Smith-Waterman or Levenshtein on peptide sequences), compute the decomposition
$$K = K_+ - K_-, \qquad k_M = k_+ + k_-,$$
where $K_+$ and $K_-$ collect the positive and negative eigenparts, and define the exploration metric $d_M(x, x')^2 = k_M(x,x) + k_M(x',x') - 2k_M(x,x')$. Maintain a vector-valued estimate $\hat{f}(x) \in \mathbb{R}^m$ of the $m$ objectives (efficacy against each pathogen strain, hemolytic toxicity), fit by regularized regression in the Krein space following the risk decomposition of Scalable Learning in Reproducing Kernel Krein Spaces, with each objective's confidence width tied to the radius of its majorant-metric ball under a Lipschitz-style smoothness assumption on $d_M$. Balls whose vector confidence intervals are non-dominated get refined, exactly as in PCZ; the difference is that the geometry PCZ assumed to be a metric actually is one, while the similarity doing the predictive work is not.
For scale beyond the $O(n^3)$ exact Krein solvers — a known limitation flagged by Scalable Learning in Reproducing Kernel Krein Spaces — we reuse the signed-measure random feature maps of Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures, which approximate indefinite kernels in linear time via a Jordan decomposition of their Fourier transform; the majorant kernel has its own (ordinary, unsigned) random features, so both geometries stay cheap.
The second deliverable is a validation protocol, not just an algorithm. The indefinite-kernel literature overwhelmingly demonstrates methods on synthetic 2D sets — rings, spirals, horseshoes — whose negative eigenspectra are low-rank and benign, as in Support vector machines with indefinite kernels and Large margin classification with indefinite similarities; no paper measures what that convenience costs. We formalize this with the substitutability lens of On the Equivalency, Substitutability, and Flexibility of Synthetic Data: the exchange rate is the additional number of real evaluations a synthetic-tuned policy needs to reach the hypervolume that a real-tuned policy reaches within budget, reported alongside the spectral statistics (rank and total mass of the negative spectrum) that we hypothesize predict it.
Baselines
The naive reference point is random peptide screening order with no learned surrogate: it lower-bounds achievable hypervolume per evaluation and calibrates how much of the method's value comes from the similarity structure rather than the bandit machinery. The strongest single-objective competitor is the Krein-SVM pipeline of Krein support vector machine classification of antimicrobial peptides, which trains directly on Smith-Waterman and Levenshtein similarities; we run it independently per objective (one model per pathogen, one for hemolysis) and screen by the minimum of the per-objective scores. This is the honest incumbent: it is the only method in the file validated on these exact datasets, reaching an AUC of 0.967 on AMPScan, 0.982 on the curated S. aureus set, and 0.891 on P. aeruginosa, and it already exposes the core failure we target — the P. aeruginosa number and the paper's own observation that general-activity models collapse on pathogen-specific targets. The strongest joint multi-objective competitor is a two-stage pipeline built from existing pieces: clip the negative eigenvalues of $K$ to zero (the standard spectrum-fixing heuristic benchmarked in Support vector machines with indefinite kernels), which restores a metric, then run PCZ unmodified on the clipped geometry. All methods get the same candidate pool, the same simulated evaluation budget, the same similarity matrices, and the same hyperparameter tuning budget (grid over smoothness and zooming constants, tuned on a held-out split for every method alike). Beating the incumbent means recovering strictly higher hypervolume at every budget on at least two of the three real tasks; beating clip-plus-PCZ means doing so on tasks where the negative spectrum carries signal, which we verify per dataset. Two ablations isolate the key ingredient: replace the majorant metric with the clipped-kernel metric while keeping everything else identical (isolating the geometry), and replace zooming with uniform partitioning at matched ball count (isolating the Pareto-directed refinement).
Why not just…?
Why not just clip, flip, or shift the kernel to make it PSD, then use standard tools? This is the first thing a practitioner does, and the literature is unusually clear that it loses information: Wilcoxon tests in Support vector machines with indefinite kernels show native indefinite formulations significantly outperform all three fixes, and on the Protein dataset the best spectrum-fixing method reached 6.3% error where a native method reached 2.5% Learning SVM Classifiers with Indefinite Kernels. Clipping also creates a train-test mismatch for new candidates that the transformation was not fit to, as Scalable Learning in Reproducing Kernel Krein Spaces notes. Still, we treat clip-plus-PCZ as the strongest baseline rather than dismissing it, because in screening the cost of a slightly worse similarity model may be small compared to the value of any competent bandit. The ablation above settles this empirically.
Why not just scalarize — optimize a weighted sum of the objectives? This is a real threat, not a strawman. Linear scalarization provably cannot reach concave regions of a Pareto front Extending Optimization Frameworks to Multi Objective Problems, but if the efficacy-toxicity front in peptides happens to be convex, a weight sweep over scalarized Krein-SVMs would recover it and would be simpler. We therefore include the weight sweep as a baseline and report front curvature directly; if the front is convex, the paper's contribution honestly shifts from "vector search beats scalarization" to "indefinite-aware geometry beats clipped geometry, plus the first measured synthetic-to-real exchange rate," and we will say so.
Why not just train separate single-objective models per pathogen and intersect the top hits? This is the incumbent baseline described above, and it may well be competitive when objectives are positively correlated (peptides broad enough to kill both pathogens). It fails exactly where the multi-objective formulation matters: when efficacy on one pathogen trades off against hemolysis or against efficacy on the other, a per-objective intersection has no way to spend its budget near the trade-off surface, and it inherits the pathogen-collapse the incumbent paper itself documents. The experiment that distinguishes them is simple: report hypervolume stratified by the degree of objective conflict in the candidate pool.
Why not just learn deep embeddings and use ordinary Euclidean geometry? Two pieces of evidence argue against it on these tasks: the Krein-SVM on raw alignment scores beat the deep networks published with AMPScan (AUC 0.967) on small-sample biological data Krein support vector machine classification of antimicrobial peptides, and the neural tangent kernel of a two-layer ReLU network is provably indefinite on the unit sphere Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures, so deep networks do not escape indefinite geometry — they hide it.
Why not just validate on synthetic data where the ground-truth Pareto front is known? Because synthetic convenience is precisely what the proposal measures, not what it relies on. Learning Real-Life Approval Elections shows synthetic generators can miss the correlations that dominate real human data, and synthetic 2D indefinite benchmarks have low-rank negative eigenspectra unlike real alignment matrices. We use synthetic spectra as a controlled diagnostic stage and then quantify the transfer penalty explicitly, so the field's reliance on synthetic validation becomes a measured quantity rather than an unexamined habit.
Proposed Experiments
Experiment 1 is the controlled diagnostic: synthetic indefinite kernels built by spectral simulation with tunable negative-spectrum rank and mass, following the Gaussian/Sigmoid truncation setup of Scalable Learning in Reproducing Kernel Krein Spaces, with known ground-truth vector rewards. We measure Pareto regret (the per-step gap to the true front, the quantity PCZ bounds in theory at $\tilde{O}(T^{(1+d_p)/(2+d_p)})$) for majorant-zooming against random order, weight sweeps, and clip-plus-PCZ, sweeping the negative-spectral mass to map where the geometry choice matters. Experiment 2 is the real test: offline screening simulations on AMPScan (3,556 peptides) and DeepAMP (3,246) for general activity, and on the curated DBAASP pathogen sets (S. aureus strains 29213 and 25923, P. aeruginosa 27853) used by the Krein-SVM paper, extended with hemolytic-toxicity labels curated from DBAASP under the same protocol; the objectives are the pathogen-specific efficacies and hemolysis, the metric is hypervolume of the recovered Pareto front as a function of simulated evaluation budget (100–1,000 assays), and the surrogate-quality checkpoint is matching or exceeding the incumbent's reported AUCs (0.967 AMPScan, 0.982 S. aureus, 0.891 P. aeruginosa). Experiment 3 measures the exchange rate: tune every method on synthetic spectra, deploy on the real tasks, and report the extra real evaluations needed to match real-tuned hypervolume, regressed against negative-spectrum statistics of the real kernels — the first quantitative answer to whether the field's synthetic habit is benign or costly. Experiment 4 checks generality beyond peptides with a second multi-objective task where prior work fixed the trade-off by a single hyperparameter: the accuracy-versus-sparsity front on Splice and CNAE-9, where the 1-norm SVM needed 224 support vectors against ESVM's 1,527 on Splice and only 2 against 233 on CNAE-9 Support vector machines with indefinite kernels], plus the structured non-metric sets (prodom, chicken, coilyork) standard in Krein-space evaluation Learning in Reproducing Kernel Krein Spaces; for these datasets, per-dataset headline numbers beyond those quoted above have no reported result found on Lacuna, so we will re-run all baselines ourselves under matched budgets rather than compare across papers.
The decisive checks are three. Majorant-zooming must beat clip-plus-PCZ on real tasks whose negative spectrum carries signal, at matched budgets, or the geometry claim fails. The vector search must beat the best weight sweep on at least one task with a demonstrably concave front, or the multi-objective claim narrows honestly to the incumbent-comparison. And the exchange-rate experiment must produce a predictive regression, or the synthetic-data contribution reduces to a negative finding — which, given how uniformly the literature leans on synthetic benchmarks, would still be worth publishing, but we would frame it as such.
References
- Learning in Reproducing Kernel Krein Spaces
- Scalable Learning in Reproducing Kernel Krein Spaces
- Multi-objective Contextual Bandit Problem with Similarity Information
- Fast Learning in Reproducing Kernel Krein Spaces via Signed Measures
- Support vector machines with indefinite kernels
- Large margin classification with indefinite similarities
- On the Equivalency, Substitutability, and Flexibility of Synthetic Data
- Krein support vector machine classification of antimicrobial peptides
- Learning SVM Classifiers with Indefinite Kernels
- Gaussian Process Optimization with Mutual Information