Many optimization problems can only be scored by asking a person, or a noisy instrument, which of two options is better. Examples include tuning a thermostat for comfort, picking a funnier caption, and choosing among molecules when lab batches disagree on absolute values. Gaussian processes (GPs) are the standard tool for this kind of preferential Bayesian optimization. A GP is a Bayesian model over functions that gives calibrated uncertainty, which guides which comparison to ask next. Exact GP inference, however, costs cubic time in the number of comparisons. So current preferential methods stall at a few hundred duels and about a dozen dimensions. The standard fix is a sparse GP, which summarizes the data through $m$ learned "inducing points." Its training objective spreads that small summary evenly over the whole input space, including regions no one will ever query.
We propose to train a sparse preference GP so that its inducing points and variational posterior serve the next comparison to be asked, rather than global fidelity. Concretely, we add to the usual variational objective a term for the expected utility of the proposed pair, and optimize the model and the query jointly. The model uses a single latent utility over the $d$-dimensional input, not a GP over pairs. This avoids the dimension doubling of duel-space models. The bet is that, at a fixed and small inducing budget, this "decision-aware" sparse model finds better optima from comparisons than a standard sparse preference GP, even one given several times more inducing points.
Core Claim and Its Lineage
Three pieces of prior work supply the method. Scalable Variational Gaussian Process Classification introduced a Gaussian variational distribution over inducing values whose objective splits into a sum over data points. That split is what allows minibatch training on millions of points. Predicting Humorousness and Metaphor Novelty with Gaussian Process Preference Learning carried this inducing-point machinery over to pairwise probit likelihoods on static text corpora. It reached Spearman $\rho = 0.56$ on humor and metaphor rankings, but it had no active querying and optimized inducing points only for global fit. Approximation-Aware Bayesian Optimization showed that for scalar-feedback optimization, this global objective wastes the inducing budget. Its fix, the expected utility lower bound (EULBO), reached target rewards with "up to 10 times fewer function evaluations" than standard sparse GPs on Guacamol molecule design.
Nobody has made that fix work for comparisons. The step is not mechanical, because the preference likelihood is non-conjugate and the query is a pair. Let $g$ be the latent utility and $q(u)$ a Gaussian over inducing values at locations $Z$. Let $(a_k, b_k)$ be the $k$-th observed duel, oriented so that $a_k$ won. Let $(x, x')$ be the candidate next pair. We maximize
$$\mathcal{L}(q, Z, x, x') = \sum_k \mathbb{E}_q\!\left[\log \Phi\!\left(\tfrac{g(a_k) - g(b_k)}{\sqrt{2}\,\sigma}\right)\right] - \mathrm{KL}\big(q(u)\,\|\,p(u)\big) + \log \mathbb{E}_q\big[\max(g(x), g(x')) - c\big].$$
Here $\Phi$ is the normal CDF, $\sigma$ is the comparison noise, and $c$ is a constant below the incumbent that keeps the utility positive so its log is defined. The last term is the expected utility of the best option (EUBO) in the pair. Under a Gaussian $q$ it has a closed form, since the expected maximum of two correlated Gaussians is known analytically. The whole objective therefore remains a sum over duels plus one pair term, and minibatch training still applies.
A second paper constrains the design. Towards Practical Preferential Bayesian Optimization with Skew Gaussian Processes proves that the exact posterior after comparisons is a skewed rather than symmetric distribution. It also shows that expectation propagation, a symmetric approximation, can misrank candidates. Our $q(u)$ is also symmetric, so this result is a direct threat to the proposal and we measure it rather than assume it away. Our hypothesis is limited. Pulling posterior mass toward the queried region should shrink the local error that causes misranking, because the pair term penalizes a posterior that is wrong about exactly the two points being compared. If that fails, the fallback is to apply the Hallucination Believer idea from the same paper on top of the sparse model. Hallucination Believer draws one sample of the latent utilities and conditions on it, which turns the problem back into ordinary GP regression.
Research Program
The model follows the single-latent Bradley–Terry-style likelihood of Principled Preferential Bayesian Optimization and Active Preference-Based Gaussian Process Regression for Reward Learning, not the duel-space classifier of Preferential Bayesian Optimization. The kernel therefore lives in $d$ dimensions rather than $2d$.
Each iteration alternates two steps. First, a few gradient steps update $q$ and $Z$ on minibatches of past duels. Second, the query pair $(x, x')$ is optimized jointly with them under $\mathcal{L}$. We start from the pair chosen by standard EUBO so that the procedure can only move away from a sensible default. Per-iteration cost is $O(bm^2 + m^3)$ for minibatch size $b$, independent of the total number of duels.
Beyond regret, we will build a small-scale diagnostic. On problems with at most 300 duels, we run the Gibbs sampler of Takeno et al. as ground truth for the skewed posterior. We then compare pairwise ranking agreement near the incumbent under three posteriors: the ELBO-trained Gaussian, the decision-aware Gaussian, and the exact skewed posterior. We also test a warm-start variant. There, the model is first fit on a large offline preference corpus and then continues active elicitation, which addresses the gap between large preference datasets and Bayesian elicitation.
Baselines
The naive reference point is uniformly random duels feeding the same sparse model. Any method that does not clearly beat it has learned nothing from its acquisition.
The strongest direct competitor is a standard ELBO-trained sparse preference GP in the style of Simpson et al., using the same kernel, likelihood, and EUBO acquisition. It differs from our method only in training inducing points and $q$ for global fit. It is the strongest competitor because it is the existing scalable preference GP and isolates exactly our ingredient. We run it at our inducing budget $m$ and also at $2m$ and $4m$, with an equal hyperparameter-tuning budget. Beating it means lower simple regret at matched $m$, and matching or beating its $4m$ version at matched wall-clock time. No reported result was found on Lacuna for this baseline on preferential BO benchmarks. The file reports it only for static ranking, at Spearman 0.56.
For small problems, we compare against exact-GP methods. These are POP-BO, reported to run "up to 10 times faster" than Thompson-sampling GP baselines with sublinear regret up to 12 dimensions, and Hallucination Believer with EI or UCB. Both are run with their full cubic inference up to the duel count where they fit our compute budget. They mark the accuracy ceiling that sparsity must approach.
Two further references complete the comparison. PABBO (PABBO: Preferential Amortized Black-Box Optimization) is run on the dimensions it was pre-trained for, where it reports a 12-fold speedup in query time over qEUBO. Scalar-feedback EULBO-SVGP is included as an upper reference that shows the size of the preference tax.
Two ablations isolate the ingredient. The first drops the pair term but keeps joint optimization of $Z$. The second keeps the pair term but freezes $Z$ at k-means centers.
Why not just…?
Why not just give the standard sparse preference GP more inducing points? This is the most serious threat. If ELBO-trained models with $4m$ points match our regret at equal wall-clock time, the idea is not worth its complexity. Maus et al. found the gap persists in scalar optimization with 256-dimensional inputs. Comparisons carry less information per query, and it is unknown whether that shrinks or widens the gap. The $m$-sweep settles it directly, and we will report it whichever way it goes.
Why not just run exact Hallucination Believer or POP-BO on a sliding window of recent duels? Windowing discards old comparisons, and those comparisons are what rule out distant regions in 60- or 256-dimensional spaces. Still, it is cheap and could be competitive in low dimensions. We include windowed Hallucination Believer at the same wall-clock budget, and we expect our method's advantage to appear only as dimension and duel count grow.
Why not just fit Bradley–Terry scores to the duels and run scalar EULBO on those scores? This two-stage approach is simple and scalable. It throws away uncertainty in the fitted scores, and those scores are relative to whichever items happened to be compared. That is the batch-shift pathology Multi-task Bioassay Pre-training for Protein-ligand Binding Affinity Prediction had to handle with within-batch ranking. We run it as a baseline. If it matches us, the contribution reduces to "fit scores, then optimize."
Why not just use PABBO? It needs synthetic pre-training at a fixed dimensionality and provides no GP posterior. It cannot run on our 60- and 256-dimensional tasks without retraining, so we compare against it only where it applies.
Proposed Experiments
The optimization suite uses tasks from Maus et al. with simulated probit duels on the true objective: Lunar Lander (12D), Rover trajectory (60D), and Guacamol Osimertinib and Fexofenadine MPO in a 256D latent space. Each task runs thousands to tens of thousands of duels. We add Hartmann6 and Ackley for comparison with exact methods, and the Thermal Comfort problem from POP-BO as a real preference task. The warm-start study uses the SemEval humor comparisons (28,210 pairs) and a subset of yguooo/newyorker_caption_ranking with pairs derived from ratings. On these, we measure Spearman correlation against held-out rankings and the quality of actively chosen follow-up queries.
Metrics are simple regret against the number of duels and against wall-clock time, over 20 seeds. The decisive checks are three. First, at matched $m$ and wall-clock time, the decision-aware model must beat the $4m$ ELBO model on the 60D and 256D tasks. Second, in the skew diagnostic, its ranking agreement with the Gibbs posterior near the incumbent must be at least as high as the ELBO model's. If it is lower, we adopt the Hallucination Believer fallback and report the negative result. Third, the pair-term ablation must account for most of the gain. If joint optimization of inducing locations alone explains it, the claim narrows accordingly.
References
- Scalable Variational Gaussian Process Classification
- Predicting Humorousness and Metaphor Novelty with Gaussian Process Preference Learning
- Approximation-Aware Bayesian Optimization
- Towards Practical Preferential Bayesian Optimization with Skew Gaussian Processes
- Principled Preferential Bayesian Optimization
- Active Preference-Based Gaussian Process Regression for Reward Learning
- Preferential Bayesian Optimization
- PABBO: Preferential Amortized Black-Box Optimization
- Multi-task bioassay pre-training for protein-ligand binding affinity prediction