Bayesian optimization (BO) is a popular approach to optimize expensive-toevaluate black-box functions. A significant challenge in BO is to scale to highdimensional parameter spaces whileretaining sample efficiency. Asolution considered in existing literature is to embed the high-dimensional space in a lowerdimensional manifold, often via a random linear embedding.

As explained in Sec. 4, with Within the first embedding, the optimal value of 0.398 can be reached. As described in Sec. 5, we show the importance of the Mahalanobis kernel using models fit to Fig. S2 compares model predictions for each of these models with the actual test-set outcomes; results Fig. S3 evaluates the predictive log marginal probabilities for the ARD RBF kernel and the Ma-halanobis kernel with posterior sampling across a wide range of training sets with different sizes Mahalanobis kernel is able to learn as the training set is expanded. This can be seen in the optimization results (Figs. 5 and S7) where ALEBO The implied kernel on the embedding is thus stationary. The argument follows that of Prop. 1. Linear embedding HDBO requires selecting a dimensionality for the embedding. The nature of the dimensionality vs. iteration budget trade-off is important in all These same considerations apply to multi-objective optimization.

We thank the reviewers for their detailed reviews and constructive feedback. We will add discussion of this in the extra page. Sensitivity is explored in S9, and ALEBO is shown to be better than prior work. Supplemental: Thanks for the suggestion, we will update to improve clarity! Clarifications: Thanks for pointing these out, we will clarify them.

We consider the problem of personalizing audio to maximize user experience. Briefly, we aim to find a filter $h^*$, which applied to any music or speech, will maximize the user's satisfaction. This is a black-box optimization problem since the user's satisfaction function is unknown. Substantive work has been done on this topic where the key idea is to play audio samples to the user, each shaped by a different filter $h_i$, and query the user for their satisfaction scores $f(h_i)$. A family of ``surrogate" functions is then designed to fit these scores and the optimization method gradually refines these functions to arrive at the filter $\hat{h}^*$ that maximizes satisfaction. In certain applications, we observe that a second type of querying is possible where users can tell us the individual elements $h^*[j]$ of the optimal filter $h^*$. Consider an analogy from cooking where the goal is to cook a recipe that maximizes user satisfaction. A user can be asked to score various cooked recipes (e.g., tofu fried rice) or to score individual ingredients (say, salt, sugar, rice, chicken, etc.). Given a budget of $B$ queries, where a query can be of either type, our goal is to find the recipe that will maximize this user's satisfaction. Our proposal builds on Sparse Gaussian Process Regression (GPR) and shows how a hybrid approach can outperform any one type of querying. Our results are validated through simulations and real world experiments, where volunteers gave feedback on music/speech audio and were able to achieve high satisfaction levels. We believe this idea of hybrid querying opens new problems in black-box optimization and solutions can benefit other applications beyond audio personalization.

Additional Feedback: I think this is a good paper that will inform future work on high-dimensional BO. Having highlighted a number of severe shortcomings of linear embeddings, I expect future work to either leverage the insights of ALEBO to develop a truly competitive baseline, or simply use these lessons learned to focus on different methods, such as the model-free ones. The robot locomotion experiment does suggest that linear embeddings, despite all improvements, are still not suited to be the default for high dimensional BO. Not only are they outperformed by model-free methods, such as CMA-ES, but also by some model-based ones such as TuRBO (despite the larger variance, as shown in the appendix). In any case, while we do not have a new state of the art method for high-dimensional BO out of this paper, the contribution is useful and will inform future work in this space.

Bayesian optimization (BO) is a popular approach to optimize expensive-to-evaluate black-box functions. A significant challenge in BO is to scale to high-dimensional parameter spaces while retaining sample efficiency. A solution considered in existing literature is to embed the high-dimensional space in a lower-dimensional manifold, often via a random linear embedding. In this paper, we identify several crucial issues and misconceptions about the use of linear embeddings for BO. We study the properties of linear embeddings from the literature and show that some of the design choices in current approaches adversely impact their performance. We show empirically that properly addressing these issues significantly improves the efficacy of linear embeddings for BO on a range of problems, including learning a gait policy for robot locomotion.