Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: This paper proposes a Bayesian optimization method over mixed spaces, i.e., discrete space and continuous space, via probabilistic reparameterization.  Since optimizing an acquisition is a challenging task where discrete variables exist, probabilistic reparameterization is used to allow us to optimize the acquisition function with gradient information.  The authors provide the theory that the proposed method serves a consistent optimizer.  Finally, they demonstrate that the proposed method works well in diverse experiments.
strengths_and_weaknesses: ## Strengths

+ It solves an interesting topic regarding discrete and mixed spaces.

+ It proposes a solid method using probabilistic reparameterization.

+ The experimental results are reasonable.

## Weaknesses

- I think this work is quite novel, but some previous work such as [20, 50] should be discussed more thoroughly.

Please see the text box described below.
questions: I would like to ask the authors some questions.

1. In Table 1, ordinal variables have the form of continuous relaxation $z' \in [0, C - 1]$ and categorical variables have the form of continuous relaxation $z' \in [0, 1]^C$.  Are they correct?  For ordinal variables, $[0, 1) \to 0, [1, 2) \to 1, \ldots [C-2, C-1) \to C-2, [C-1, C-1] \to C-1$.  Thus, $C-1$ has a smaller range than the other integers.  I think it should be $[0, C)$.  Moreover, for categorical variables, $[0, 1]^C$ should be a simplex.  More precisely, a probability vector for categories has to sum to one, so I think it should be $[0, 1]^{C-1}$ where a sum-to-one constraint is assumed.  It is a generalization of binary case, which implies that its continuous relaxation is $[0, 1]^1$.

1. I am not sure if the continuous relaxations are changed, other parts are still same.  Or the current version is just equivalent to the continuous relaxations I described.  If updates are required, please describe in the rebuttal.
limitations: I do not think that this work has any negative societal impacts and any specific limitations.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work proposes a method for optimization of acquisition functions in Bayesian optimization (BO), where at least some of the input variables are discrete (binary, integer, or categorical). The method is based on a probabilistic reformulation, whereby the discrete variables are cast as random variables, drawn from probability distributions. Optimization can then performed on the expected value of the acquisition function, using the parameters of the assumed probability distributions as inputs instead of the original (discrete) variables. This reformulation enables the use of gradient-based optimization; the authors propose a Monte Carlo approach to estimate the gradients.
strengths_and_weaknesses: STRENGTHS:

1. The method and significance are well presented, and the introduction and case studies show why the setting of BO over mixed variable spaces is both challenging and important.

2. The computational studies demonstrating the method are very thorough, with a wide range of case studies and tests considered.

3. The authors prove mathematically that the proposed reformulation does not affect the convergence guarantees of standard BO.

WEAKNESSES:

1. I am not very familiar with probabilistic reformulation, but it seems the proposed reformulation effectively inherits the weaknesses of BO on discrete inputs that it purports to avoid. For example, a binary variable is recast as a binomial distribution, which must be again "discretized" (in Algorithm 1) to create feasible values for $z_n$. Moreover, the secondary transformation in Table 3 introduces similar techniques used to relax discrete variables for optimization.

2. While the main advantage of the proposed method is that it enables gradient based optimization, the accuracy of the gradients relies on Monte Carlo estimation, which must be evaluated over the original discretized space (eg. 6). This introduces the same curse of dimensionality that would arise from optimization over a mixed variable space (e.g., by enumeration or branch-and-bound), and, as a result, the computational results may be unfair as the proposed method is given much more information in the form of MC samples. 
questions: Could a comparison be added to show that the proposed MC method results in more sample-efficient (in terms of optimization) performance than existing methods? E.g., when 1024 MC samples are used, would it be a more fair comparison to allow the multi-start methods to have 1024 starts?

Since the proposed method effectively updates continuous parameterizations used to compute the "discretized" values of the original updates, is there an equivalent relaxation and iterative optimization method in the original space?
limitations: Yes, provided in supplementary material.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper addresses BO in mixed decision spaces, where part of the space is continuous and part is discrete. Namely, it focuses on the problem where the discrete space is large and cannot be exhaustively evaluated. The proposed strategy reparametrize the objective with a parametrized discrete probability distribution over the discrete decision space, which can be optimized using continuous optimization tools. Further extensions with MC sampling and extensive benchmark is provided. 
strengths_and_weaknesses: Strengths
----------
- I think this is a very practical algorithm if certain conditions are met (see Limitations). Authors identify problems where these conditions are met. 
- solid empirical analysis beyond the standards of the BO field. 
- optimization of AF is indeed an elephant in the room, nice to see that it is being recognized as a problem. 

Weakness
---------
- I feel the contribution to the field does not warrant publication at the most prestigious venue. I think people were aware of the reparameterization trick in this context. The problem with it is that for discrete spaces its complexity is larger than evaluating the whole \mZ once. In mixed spaces, there are conditions where it could be better, but how much better is not addressed in this paper. 
- The paper cites a lot of by now folclore theorems, such as unbiasedness of monte carlo, SGD convergence and regret rates of algorithms depending on AF. I think the paper could be explained in 1 page and experiments take 2 pages, exactly suitable for a workshop paper. 
- The best performing algorithm PR+TR is not mentioned in the main text.
- Convergence of SGD on the non-convex objective is also not ideal, but I guess this is not addressed in the paper since the “discrete part” is the challenge. But its good to point out that by creating a continuous relaxation not all issues are removed. 

questions: - In Fig. 1, AF evaluates the expectation exactly? I would not expect there to be no spread if used with monte-carlo sampling.
- Why not use Comsopolitan and HyBO on more realistic benchmarks? Could you not just add the constraint in the AF selection?
- Why on Ackley PR-TR performs better?
- Can in any of these experiments exhaustive search be performed? It would be nice to understand the effect of MC sampler. 

limitations: 1. The whole approach is sensible only if one of these two conditions are met:
a) mixed space. Let me denote the effort to optimize \mathcal{X} given a specific z to B. If B*|\mZ| is less than optimizing \mathcal{Z}, \mathcal{X} jointly with the Monte-Carlo or exact calculation
b) discrete space, but very efficient evaluation of MC sampling exists 

My conjecture is that b) does not occur in practice much, and a) can be indeed practical. 

2. Effect of MC sampling is not investigated in the experiments and in the motivating Figure.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Maximizing Bayesian optimization acquisition function (AF) over mixed or high-cardinality discrete search spaces is challenging when the space is too large to enymerate directly. This is important because the theoretical regret bounds that come with certain AFs only apply if the AF can be maximized. The paper proposes to reparameterize the discrete parameters into probability distribution defined by continuous parameters, and then to maximize a probabilistic objective (PO) consisting of the expectation of the AF over those continuous parameters. The authors call this a probabilistic reparameterization (PR) of the AF. The paper then proves that maximizing this objective also maximizes the original AF, providing the same guarantees as maximizing the AF. They then derive unbiased and efficient Monte Carlo estimates of the PO and its gradients and show empirically that their method outperforms other mixed-variable optimizers on both maximizing the AF and the overall Bayesian optimization task. 

strengths_and_weaknesses: ## Strengths

- The idea of inducing a distribution with continuous parameters and then optimizing the expectation of the AF over the new parameters is both performant and elegant. It's the kind of solution that seems obvious once written down.
- The paper addresses an important limitation when applying Bayesian optimization to many (most?) real-world problems. 
- The paper is well-contextualized in relation to previous work. 
- The writing is generally clear, and the importance of the theorems is easy to see. 
- The experiments seem sound, and the conclusions are supported by the results. 

## Weaknesses
- I understand that there is limited space, but section 4.3 is very difficult to understand without a lot of prior knowledge.
- The experiments would be stronger with comparisons to non-BO black-box optimization methods, such as evolutionary algorithms or to methods that use eg a VAE to embed the discrete variables into a continuous space. 

questions: - In the middle and right panels of Figure 1, what does the color represent? I think it's the AF value, but in that case, why is it so different between the two panels?

limitations: The primary limitation is the computational cost of the MC estimation and maximization, which the authors address. This could be improved by explicitly stating the compute required for their experiments.
review_title: null

Meta-review: metareview: This paper studies a Bayesian optimization method where some of the variables are discrete and some are continuous and proposes using probabilistic reparameterization. Reviewers unanimously agreed that the paper is well-written, solves an important real-world problem, and most reviewers found the experimental results to be convincing. In addition, the reviewers found the rebuttal and revision to be convincing and clarified many of the initial questions. 

Several reviewers pointed out that some of the results referenced in the paper could be more explicitly referenced in the paper and/or explained in the appendix. For the final version, please make an effort to address reviewers feedback to make the paper more self-contained. 
confidence: Certain
Decision: Accept