Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces

Summary

Most real-world optimization problems contain a mix of continuous, categorical, binary, and ordinal variables and might be high-dimensional. Although there are some methods that have investigated this problem, they are not always reliable with regard to finding a satisfactory optimum. In order to tackle this problem, the authors propose Bounce (Bayesian Optimization Using iNcreasingly high-dimensional Combinatorial and continuous Embeddings). This work seems to be a natural extension of BAxUS, which used a similar embedding strategy as for Bounce but only for continuous variables. It uses a novel trust region management system to grow or shrink the trust regions. The proposed method is tested on a representative range of test problems and compared with state-of-the-art benchmarks and shows convincing results.

Strengths

- Most real-world optimization problems have mixed spaces and are high-dimensional for which vanilla Bayesian optimization methods are not suited, this work thus addresses an important problem. - The proposed algorithm is tested on a broad range of problems and compared with state-of-the-art benchmarks and has a strong performance. - The authors provide proof that the algorithm converges in the limit of infinite iterations, making it a reliable method. - The paper is well-written and well-structured.

Weaknesses

- In general, the paper is very complete and well-written and contains a very complete related work section. However, the paper does expect the reader to have a significant amount of knowledge of previous work. Especially about BAxUS and papers using TR management strategies. Perhaps the authors could provide a little bit more information and illustrations in this work to make it more easily accessible. For instance, provide an illustration of the binning procedures and/or about the TR management.

Questions

- Although I do understand that this is a typical question in BO paper reviews, for most problems, benchmarks are performed for 200 iterations. Would you say that this is enough for the dimensionalities of the benchmark problems? For instance, for the 125-D MaxSAT, you would say you probably need a lot more data points for the surrogate model to model the objective function effectively. What are your thoughts on this and do you think some of the benchmarks can be better than Bounce at a higher budget? - It is mentioned in Appendix C that the original implementations for COMBO, BODi and Casmopolitan are used. And that you use the same setting as in those works, what kind of settings are these exactly? Do these approaches use the same kernels for the GP models for example? Could this influence the performance on the benchmarks? - Have the authors contacted Oh et al. regarding the bug in COMBO? If it is possible, it would of course be ideal if results using a bug-less version can be provided. - I really like the results shown in Figure 5 regarding the efficacy of batch acquisition. In general, I like that the # batch evaluations are used on the x-axis as this directly shows what is good to use for users who are optimizing parallel processes. However, I'm also interested in how these plots look as a function of function evaluations. My intuition would say that b=1 is always better, as in this way the model is as informed as it can for the next iteration. Just out of interest, could you elaborate on this here or could you add a plot to the appendix that shows these results as a function of iterations? - As a suggestion to your citations regarding chemical engineering and materials discovery. There also is a range of works regarding the optimization of lab equipment for sample analysis. See for instance [Hagan et al.](https://pubs.acs.org/doi/full/10.1021/ac049146x?casa_token=dnIitFW7lO4AAAAA%3Ado8InveDdcPw3TwtOVSQuRvM5NQhSFEo3M1jmpdpEHvRbzA0f1jYTJ2_bloYb7he8-Ofb8u96oMXvCvO), [Boelrijk et al.](https://scholar.google.nl/citations?view_op=view_citation&hl=nl&user=1z-BBwkAAAAJ&citation_for_view=1z-BBwkAAAAJ:9yKSN-GCB0IC). These problems can typically contain mixed spaces and many variables. Some small textual remarks: - Could it be that d_0 and d_{init} are interchangeably used? For instance lines 2 and 3 of Algorithm 1. - Line 90, 'sequencies' should be 'sequences' or was this the originally proposed name by the BODi paper? - Lines 277-278, as well should be as well as? - Typo in Ass. 5. in Appendix Section a. One should be once?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors describe the societal impact of their work. The authors do not describe the limitations of their work. Perhaps the authors could dedicate some sentences to this, for example, would the algorithm handle a noisy setting? Or does this violate the binning procedure to some extent?

Summary

The paper proposes a new BO method, namely Bounce, to tackle the problem of BO with combinatorial and mixed space. The key idea is based on the trust region approach (as with TurBO) and adaptive space (as with BAxUS), but is applied to the combinatorial and mixed variables. The proposed method is also enabled to work with batch. Experiments are conducted on various synthetic and real-world problems to evaluate the efficacy of the proposed method.

Strengths

+ The paper’s writing is generally clear and easy to understand + The paper tackles an interesting problem, which is to solve BO problems with categorical and mixed variables + The methodology developed in the paper seems to be sound to me. + The experiments are conducted with various benchmark optimization problems (synthetic and real-world)

Weaknesses

+ The proposed method seems to be largely an extension from existing methods: TurBO and BAxUS – normally this is alright if the results are impressive but there are some issues with the experiments which I will describe in more detail in the below bullets. + There is not much insight on why the proposed method, Bounce, works. There is a theoretical analysis in the appendix (Theorem 1) that shows the consistency of the Bounce. However, I think this theorem doesn’t have much meaning. It assumes that the search domain is finite, and the objective function is noiseless, and it states that Bounce will find a global optimum with probability of 1 when the number of samples N goes to infinity. But for a finite domain and noiseless observations, any algorithm will be able to find the global optimum? + One of the contributions of the paper is to conduct an in-depth analysis of two state-of-the-art algorithms for combinatorial BO, COMBO [45] and BODi [17], however, I don’t really find this to be interesting. Unless I missed it, it seems to be discussed in Section 4.6? But this is largely empirical and not much insight. + The experiments seem to lack of some well-known baselines for categorical and mixed search space, for example, SMAC, TPE, and some new BO methods like the work “Bayesian Optimization over Hybrid Spaces” by Deshwal et al (ICML 2021), and the work “Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization” by Daulton et al (NeurIPS 2022). + Also, in the experiments, the number of iterations is quite small very high-dimensional problems. The number of iterations evaluated in all problems is just 200, which is too small.

Questions

Please address my comments in the previous section (section Weakness)

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I don’t find any dedicated section describing the limitations of the work.

Summary

The paper proposes a new Bayesian optimization algorithm for combinatorial and mixed search spaces containing input variables of different types (continuous, binary, categorical, ordinal), which promises to be relevant for problems as varied as materials discovery, hardware design, neural architecture search, and portfolio optimization. Bounce relies on a Gaussian process (GP) model of the objective function, which is based on lower-dimensional subspaces of the original search space, generated by partitioning input variables into “bins”. Notably, the bins only contain input variables of the same type (e.g. continuous) and all variables in a bin are forced to take the same value during the optimization of the acquisition function, in effect operating in a lower-dimensional subspace. During the course of an optimization run, Bounce splits up bins into smaller ones, enabling the algorithm to propose candidates with increasingly finer structure. Bounce also leverages existing techniques for high-dimensional BO, including the trust-region approach.

Strengths

- Strong empirical results, comparing against published baselines, in addition to ablations on the batch optimization performance. - Performance is more robust to shifts of the solution than previously published methods. - Sheds light on a non-trivial structural assumption of prior methods. - Generally a well written paper.

Weaknesses

- No theoretical analysis. - Without a “modified” or “shifted” label for the left subplots of Figures 1, 2, 3, 4, the presentation is confusing and can easily be misread to suggest that the left subplots report results on the problems as defined in the literature, but they do not. Please add a “modified” or “shifted” label for the left subplots.

Questions

- In the first 60 or so iterations, Bounce is outperformed by BODi on the non-modified 125d MaxSAT problem, as well as the non-modified PestControl problem. Since sample-efficiency is a chief concern for BO methods, is there a way to leverage BODi’s inductive biases for Bounce? On a high level, something like this might be possible since both methods leverage embeddings of the input space. - Is there something more you can say about any theoretical aspects of the method? Does a global convergence guarantee hold? What can you say about the convergence rate, either local or global? How does the choice of embedding influence the convergence? - Are there other embeddings approaches that could be combined with Bounce? Suggestions: - The description of the cardinal and ordinal embeddings are a bit repetitive and verbose, especially since they formally use the same approach. Can you unify the presentation, possibly include a single math-mode version of the embedding formula? That would aid the readability of the section. - Line 191: “The embedding of ordinal variables follows [that of the] categorical variables”

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes

Summary

The paper considers the problem of optimizing black-box functions defined over high-dimensional combinatorial and mixed continuous-combinatorial spaces. The key idea is to use the Bayesian optimization framework specialized to increasingly large nested embeddings of input dimensions in order to tackle the high-dimensionality challenge. The paper proposes separate embeddings for different class of input variables i.e. continuous, binary, categorical and ordinal. A trust region based approach is employed to enable parallel candidate evaluations in the proposed approach. Experiments are performed on multiple benchmarks to demonstrate the efficacy of the approach.

Strengths

- The problem space considered in the paper is quite relevant and arises in multiple real-world applications. The paper is written really well describing the scope of the problem and associated applications. - The proposed idea (although building on BAxUS and TurBO) is principled and explained well. The method clearly outperforms all state-of-the-art baselines on several benchmarks demonstrating its efficacy. - The related work discussion and the amount of effort to compare with all the baselines in proper way is commendable and deserves credit. Overall, I think the paper will be useful and practical contribution to this problem space of high dimensional combinatorial spaces.

Weaknesses

Please see my question below.

Questions

The intuition or principle behind the embedding specific to categorical variable is not entirely clear to me. While for continuous variables, the embedding comes from the idea of count-sketches, it is not clear immediately what is captured by assigning categorical variables of eve different cardinalities to the same bin. For example, if there is an outlier variable with very large cardinality or if the range of cardinalities is quite large, the embedding would be very sensitive to the outlier? Please expand the description about the categorical embedding more if possible.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

Summary

This paper proposes an algorithm called Bounce, using nested embedding for mixed and combinatorial search space. Bounce partitions input variables into ‘bins’ and set all variables within the same bin to a single value to reduce the dimension. During the optimization, Bounce splits up bins into smaller bins for more refined optimization.

Strengths

1/ The combinatorial and mixed optimization is significant and has wide range of applications in the real world. 2/ The algorithm is reasonable. Bounce designs a reasonable mapping for binary, categorical and ordinal variables, while a similar algorithm, BAXUS, which also uses nested random subspaces, has shown good performance on continuous optimization.

Weaknesses

I don't have any major complaints. The proposed algorithm is a natural extension of BAXUS for categorical and mixed space. The experiments show that Bounce is reliable and can achieve good performance. Here are some minor comments: 1/ One minor weakness is the the high-dimensional continuous spaces part in Section 2. A recent survey paper [1] categorizes these works into several categories, i.e., low-dimensional embeddings, decomposition, and variable selection. This paper mainly discuss the work in low-dimensional embeddings I think discuss the recent works in decompostion [3-4] and variable selection [5-6] would further strengthen this paper. [1] A Survey on High-dimensional Gaussian Process Modeling with Application to Bayesian Optimization. ACM TELO, 2022. [2] High-Dimensional Bayesian Optimization via Tree-Structured Additive Models. AAAI, 2021. [3] Are Random Decompositions all we need in High Dimensional Bayesian Optimisation? ICML, 2023. [4] Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization. NeurIPS, 2022. [5] Fast and Scalable Spike and Slab Variable Selection in High-Dimensional Gaussian Processes. AISTATS, 2022. 2/ It would benificial to see the the disscussion (even experimental comparison) with a work with similar topic [6]. [6] Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces

Questions

I am puzzled about why the performance of BODi and COMBO can be sensitive to the location of the optima, which is equivalent to shuffling the labels of the categories of each variable. BODi uses Hamming distance and COMBO uses the combinatorial graph to model the relation of different labels for each variable. Different labels for the same variables are the same, so shuffling the labels will not impact the performance. Can you provide more explanation? I think the variable selection methods [4-5] maybe also can be applied in the mixed spaces tasks. I want to see some discussions. I'm glad to increase my score if you address the proposed isssues.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Thank you for the response

I would like to thank the authors for your response. The response has addressed many of my concerns so I decided to increase the score to 6. The reason I don't increas more is that I still have concerns regarding the very small number of iterations - normally I expect more for high-dim problems.

Response to Rebuttal

Thank you for your time in responding to my queries. I am happy with the response and would like to keep my score of acceptance.