PABBO: Preferential Amortized Black-Box Optimization

Comments that can be answered through additional experiments will be posted as soon as possible when the latter are completed. With respect to the reviewer's comments, these include:

• Consider higher dimensional examples.
• Performing an ablation study on $\lambda$ in the computation of the loss $\mathcal{L} = \mathcal{L}^{(q)} + \lambda\mathcal{L}^{(p)}$.
• Performing an ablation study on the discount factor $\gamma$ (Equation 3)
• Performing an ablation study on the query budget $T$ used during pre-training.
• Performing an ablation study on the percentage of $D^{\text{ctxpred}}$ and $D^{\text{tarpred}}$ Additional comments can be found in the global comment.

A critical issue is that the paper lacks a theoretical foundation or even a mathematical intuition for its approach, focusing primarily on reporting numerical results without a deeper analytical context.

We would like to begin by emphasizing that unlike the BO field, PBO itself has long been functioning without formal theoretical guarantees. These are made cumbersome by the preferential nature of the feedback, which entails that the black-box function can only be identified up to a monotonic transformation. The first results are only a few months old: [1] established asymptotic consistency for the Dueling Thompson Sampling acquisition function for a finite query set, and [2] provided the first regret bound. Such theoretical results make strong assumptions about the black-box function, which in turn requires care when selecting a GP surrogate kernel and acquisition strategy. PABBO avoids these considerations by directly learning the acquisition function in a data-driven manner, at the loss of theoretical results.

Nevertheless, we can provide some mathematical justification. At the center of our method is Transformer Neural Process (TNP) [3], a well-suited model class for PBO due to several key properties:

• The optimization history in PBO is inherently a set of preference pairs, meaning that the order of observations should not affect the acquisition decision. TNPs naturally handle this through self-attention mechanisms, maintaining permutation equivariance in the intermediate layers and invariance in the final output.
• The attention mechanism allows adaptive computation where each preference pair's representation is influenced by the entire optimization history. This is crucial for PBO as the relative importance of each pair varies depending on the current stage of optimization.
• TNPs inherit the universal approximation capabilities of transformers [4], and can learn arbitrary continuous mappings from sets of preferences to acquisition values, allowing direct learning of a joint surrogate model and acquisition function in an end-to-end manner.

We will briefly mention some of these mathematical insights in the main text, in section 3.3.

Why did you choose the Gaussian distribution in equation (4)?

We followed the common practice in the neural processes literature of using independent (diagonal) Gaussian likelihoods [5]. If modeling correlations between points is crucial for the downstream task, we can replace the output with a joint multivariate normal distribution (similar to GNP [6]) or predict the output autoregressively (like AR-CNP [7]). For modelling multimodal predictive distributions, we could replace the Gaussian head with a mixture-of-Gaussians head. These modifications can be easily implemented. Additionally, in PBO, a likelihood often used is the probit likelihood, which assumes Gaussian noise [1, Section 3.1]. As our goal is to amortize PBO, a Gaussian noise model is a relevant assumption. A short sentence summarizing this answer will be added as a justification for Equation 4 in the main text.

[1] Astudillo et al. Preferential Multi-Objective Bayesian Optimization.

[2] Xu et al. Principled Preferential Bayesian Optimization

[3] Nguyen & Grover. Transformer neural processes: Uncertainty-aware meta learning via sequence modeling.

[4], Yun et al. Are transformers universal approximators of sequence-to-sequence functions?

[5] Garnelo et al. Conditional neural processes.

[6] Markou et al. Practical conditional neural processes via tractable dependent predictions.

[7] Bruinsma et al. Autoregressive conditional neural processes.

[8] Brochu et al., A Tutorial on Bayesian Optimization of Expensive Cost Functions, with Application to Active User Modeling and Hierarchical Reinforcement Learning

Comments that can be answered through additional experiments will be posted as soon as possible when the latter are completed. With respect to the reviewer's comments, these include:

• Considering additional test functions, such as those used in Astudillo et al., qEUBO: A decision-theoretic acquisition function for preferential Bayesian optimization.

Additional comments can be found in the global comment.

The pretraining in this method requires a large amount of data, which could be costly for certain tasks.

We are not sure if by ''costly'', the reviewer is referring to the time-consuming pre-training on large amounts of data, or to the cost linked to gathering such large amounts of data. We address both concerns below:

• For the former, by definition of Amortized Inference, one trades a long but offline pre-training time for fast inference at test time. If the model is to be used on many related tasks afterward, this is a highly beneficial strategy. Typically, for optimizing human preferences, the speedup obtained at inference time allows for seamless interaction with users.
• For the latter, we would assume that a pre-training dataset, containing the numerous optimization runs done before, would be available from the start. Most importantly, the dataset can feature synthetic examples, e.g. generated with draws of many different Gaussian Processes, as we outlined in Appendix A.1. Our empirical results demonstrated the soundness of this approach. Leveraging synthetic data from amortized inference is now a widely used practice for diverse tasks such as time-series prediction [1, Section 4], mixed-effect models inference [2], and, more to the point, Bayesian Optimization [3, Section 5.2 and Appendix E].

PABBO is currently limited to tasks with a fixed input dimensionality.

This is a current bottleneck of the approach, as PABBO needs to be retrained from scratch when switching between tasks of different input dimensionality. The whole amortized optimization field is facing this challenge. There has now been recent work [4, 5, 6] to tackle this issue. Shortly, the idea is to utilize a bi-dimensional attention mechanism that can accept data with different dimensions. At the moment, integrating this new architecture within PABBO represents one of the most relevant avenues for future work. Leveraging such approaches in black-box optimization holds great potential, as one could use knowledge acquired on previous lower-dimensional tasks to inform high-dimensional tasks.

PABBO only supports pairwise preference queries, limiting its ability to handle queries with multiple options, which could reduce the efficiency of information gathering. While existing works could handle queries with multiple options.

We agree with the reviewer. Our architecture could be extended to contain as many data embedders as there are points to compare. However, preferences over $q>2$ queries ultimately reduce to $\frac{q(q-1)}{2}$ pairwise preferences. Given the speedup provided by PABBO, this alternative remains amenable when interacting with humans.

[1] Ansari et al. Chronos: Learning the Language of Time Series.

[2] Arruda et al. An amortized approach to non-linear mixed-effects modeling based on neural posterior estimation.

[3] Huang et al. Practical Equivariances via Relational Conditional Neural Processes.

[4] Anonymous. Dimension Agnostic Neural Processes. https://openreview.net/forum?id=uGJxl2odR0

[5] Dutordoir et al. Neural diffusion processes.

[6] Liu et al. Task-agnostic amortized inference of Gaussian process hyperparameters.

Comments that can be answered through additional experiments will be posted as soon as possible when the latter are completed. With respect to the reviewer's comments, these include:

• Carry out experiments involving a higher number of iterations.

Additional comments can be found in the global comment.

How does preference based optimization work when users have varying preferences? Is it possible to incorporate personal user-preferences in this framework.

We ask for clarifications: is the reviewer talking about handling multiple users, each with distinct preferences, or about a single user whose preferences evolve over time, as in nonstationary Bayesian Optimization [1]? The former case is naturally handled by our framework; different users are simply considered as different tasks that are assumed to share some similarities with those seen during pre-training. The latter is more complex and is currently not accounted for by our method, even though PABBO can be readily applied to this setting. Investigating suitable training procedures for that scenario as well as dedicated pre-training datasets constitutes a relevant avenue for work if one wants to further advance the field of human preference learning from an amortized perspective.

Line 237, Is the same MLP applied to $x_{i,1}, x_{i,2}$ and $l_i$ individually? Why should $l_i$ be encoded into the same embedding space as $x_{i,1}$ and $x_{i,2}$? Or does the statement mean to encode the concatenation of the triple using an MLP?

To clarify, PABBO employs separate MLPs for $x_{i, 1}, x_{i, 2}$ and $l_i$, mapping each of them to separate embeddings of Transformer input dimension as $**E**^{x_{i, 1}}$, $**E**^{x_{i, 2}}$, and $**E**^{(l_i)}$, with $\oplus$ denoting the component-wise addition. When working on the context set $\mathcal{D}^{(c)}$ and prediction context set $\mathcal{D}^{\text{(ctxpred)}}$, which consists of duels $(x_{i, 1}, x_{i, 2}, l_i)$, the token embedding is obtained by adding the individual embeddings up, i.e. $**E** = **E**^{x_{i, 1}}\oplus **E**^{x_{i, 2}}\oplus**E**^{(l_i)}$. When processing a single design from the query set $\mathcal{D}^{(q)}$ or prediction target set $\mathcal{D}^{\text{(tarpred)}}$, we directly use the individual embedding for that design as the token embedding, i.e., $**E** = **E**^{x_{i, 1}}$. Because $(x_{i,1}, x_{i, 2}, l_i)$ forms a single atomic element in our context set, Transformer architecture requires all elements in its input sequence to live in the same embedding space: to pass these preference observations to the transformer, we need to make sure their dimensions are aligned.

Given that PABBO encodes elements separately, for the same type of elements, like $x$, a shared embedder can be used across all three sets. This enables parameter sharing for the embedders, as the same embedder processes all $x$-type input, regardless of which set they belong to. This reduces model complexity because it avoids the need to train separate embedding functions for each set. If inputs were concatenated to obtain a joint embedding, this ability to reuse a shared embedded for the same type of elements would be lost, resulting in redundant parameters, since the embedder would need to relearn shared patterns for each set independently. Finally, separate embeddings confer distinct semantic meanings to features $x$ and preference labels $l$. Thus, separate MLPs can specialize in their respective tasks: Feature embedders can focus on capturing spatial relationships, and preference embedders can focus on binary relationship encoding. This leads to an increased representation power. For all these reasons, we restrained from employing concatenation to obtain a joint embedding.

This being said, a legitimate question to ask now is ''why not use the same embedding for $x_{i,1}$ and $x_{i,2}$''. Basically, in this case, upon summing $**E**^{x_{i, 1}}$ and $**E**^{x_{i, 2}}$ the order information would be lost: the network would not know whether $x_{i,1} > x_{i,2}$, or the opposite. That is why we used separate embedders for $**E**^{x_{i, 1}}$ and $**E**^{x_{i, 2}}$.

These details were missing from the main text, and we thank the reviewer for helping us identify them. As a result, we will modify the main text, briefly elaborating on the benefits of addition and separate embedders.

[1] Deng et al., Weighted Gaussian Process Bandits for Non-stationary Environments.

First, we would like to point to the global comment we posted, which tackles several remarks made by the reviewer.

This paper seems to treat simple and cumulative regret as interchangeable, although I am sure the authors know the difference. If the policy is optimized to minimize cumulative regret, why is cumulative regret not reported? On the other hand if simple regret is really what you care about, why are none of the baselines aimed at best-arm identification? For example, Thompson sampling is optimal w.r.t. cumulative regret, not simple regret. Top-two thompson sampling is optimal in the discrete case, although translating to the continuous case requires some thought (what epsilon is sufficiently large to constitute a different arm?).

Answer:

About Thompson sampling:

In our experiments, we evaluated PABBO against a Gaussian process-based acquisition strategy, $q$TS. This baseline was originally proposed by [1] and subsequently used by [2] in their experiments. $q$TS is a straightforward application of a batch BO acquisition function to the PBO case: for $q=2$, the strategy samples two continuous draws from the posterior distribution of the GP, optimizes each draw, and yields a batch containing the two maximizers. Translating this AF to the PBO setting, preferential feedback is obtained by comparing the two queries of the batch. As noted by [2], adapting batch BO strategies to the PBO setting remains heuristic, as such strategies do not acknowledge that the optimized designs are meant to be compared. Still, the diversity provided by maximizing two different draws of the posterior might yield informative comparisons, which is why this baseline remains used in current benchmarks. As a matter of fact, recent work established that Dueling Thompson sampling ($q$TS with $q=2$) is asymptotically consistent, for a finite query set [3]. While this result is not as strong as a regret bound, it provides some mathematical justification for this strategy. Additionally, regarding best-arm identification the GP-based strategy qEUBO [2], which we compare against, is one-step Bayes optimal.

With all that said, we emphasize that applied to PBO, $q$TS is not a top-two Thompson sampling algorithm, which favors exploration by randomizing among two candidate arms. We agree with the reviewer that contrarily to ''vanilla Thompson sampling'', top-two Thompson sampling is optimal in terms of simple regret in the discrete case, due to the added exploration. Additionally, we apologize for the confusion and warmly thank the reviewer for pointing us toward this quite interesting literature, which was unknown to us. We will clarify how the baseline $q$TS works in the updated PDF. As a side note, this discussion raises the point of whether we should consider an additional baseline actually implementing top-two Thompson sampling in the preferential black-box optimization setting, using a discrete query set. This would imply randomizing among two candidate pairs. While the idea sounds interesting, it is not a priority for this work.

About cumulative and simple regret:

During pre-training, we use the (discounted) cumulative simple regret as a reward (Equation 3, main text), since it sends a stronger and less sparse signal than simple regret. Now, at inference time, when encountering a new task, we report simple regret. This is because the use cases we have in mind for PABBO are human preferences optimization. For instance, we might want to find the best sushi product for a given user, or the best visual design for a website, tasks where typically the notion of cumulative regret matters less than simple regret. We added a sentence in the PDF to justify our choice of the cumulative simple regret as a training reward, and we will provide cumulative regret plots for some of the experiments carried out, in the Appendix.

[1] Siivola et al., Preferential batch Bayesian optimization

[2] Astudillo et al., qEUBO: A Decision-Theoretic Acquisition Function for Preferential Bayesian Optimization

[3] Astudillo et al., Preferential Multi-Objective Bayesian Optimization

Comments that can be answered through additional experiments will be posted as soon as possible when the latter are completed. With respect to the reviewer's comments, these include:

• Consider higher dimensional examples.
• Perform an ablation study on the composition pre-training dataset.

Additional comments can be found in the global comment.

The performance advantage vs baseline methods are not significant in many cases.

While we do not always reach a clear statistical significance, our proposed method consistently ranks among top performers in every experiment. This consistency is a key takeaway, as it suggests that once pre-trained, we can effortlessly apply PABBO to a wide range of problems, whereas other methods require specifying a kernel and an acquisition function, choices that are typically heavily task-dependent and need to be thought thoroughly. We speculate that the versatility of our algorithm stems from the rich dataset used for pre-training, combined with the fact that we are learning the acquisition function from data.

While it is true that estimating the true posterior of a preference model’s posterior might be expensive, variational inference or Laplace approximation with some clever implementation can go quite far and allows for gradient-based optimization for acqf value. On the other hand, for larger models like PABBO1024, the inference time advantage of amortized learning might be diminishing when compared to GP-based model according to Figure 3 and 5.

We agree with the reviewer. However, in our experiments, the GP baselines do employ Laplace approximation for posterior approximation. The implementation is that of BoTorch [1], a state-of-the-art library for GP-based modeling and BO. Even though we did not carefully check that the implementation is ''as fast as possible'', we remain confident that the issue is mitigated, from this side. Regarding PABBO, we acknowledge that larger models like PABBO1024 require longer inference time as seen in Figures 3 and 5. However, an important distinction arises when scaling the tasks (e.g., increased dimensionality or number of iterations). The inference time of PABBO grows linearly with the size of the task, whereas GP-based methods typically exhibit superlinear growth with respect to task dimensionality. This makes PABBO particularly advantageous in scenarios with many iterations, where the gap in total runtime between PABBO and GP-based methods becomes increasingly significant.

[1] Balandat et al. BoTorch: A framework for efficient Monte-Carlo Bayesian optimization.

Algorithm 1 seems to only describe the meta-learning/pre-training part of PABBO as we are still updating the PABBO model at the end of the loop. What’d be the algorithm for applying PABBO on new, unseen dataset? I’d assume that’d be the same as the inner loop of the algo, but it’d be nice to have some clarification from the author.

The reviewer is correct, we forgot to include an algorithm description of how PABBO operates at test time. This is now corrected and constitutes an additional section of the Appendix.