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 new method of batch Bayesian optimization for combinatorial optimization problems, especially permutation problems. The authors found that the density function of L-ensemble, one definition of a determinantal point process (DPP), can be used as a measure of batch point diversity to ensure the diversity of batch points acquired in each round of Bayesian optimization. 

In order to guarantee the diversity of batch points while taking advantage of the proposal using the ordinary acquisition function, the authors introduced the Acquisition Weight Kernel (AWK) and proposed to acquire batch points by maximizing the density of L-ensemble induced by the AWK. Here, as an actual optimization method, since the determinant of the AWK matrix, which is the numerator of the L-ensemble density induced from AWK, can be written as the product of the determinant of the original kernel matrix and the monotonic transformation of the acquisition function, and since log det is submodular, a greedy algorithm is proposed to repeat the operation of maximizing the above product by one point at a time and then acquiring it batch size times. 

In terms of theoretical contributions, it is first shown to achieve asymptotic riglet vanishing for UCB and EST strategies, similar to existing Bayesian optimization based on maximum information gain. The positive definiteness of the position kernel is rigorously proved, and an upper bound on the maximum information gain when using it as the kernel function is also derived.

In the experiments, the proposed method is compared with existing methods by three benchmark problems: the quadratic assignment problems (QAP), the flowshop scheduling problems (FSP), and the traveling salesman problems (TSP).
strengths_and_weaknesses: Strength

- For the BO problems on permutation space, the authors propose a batch point acquisition strategy that successfully extends the existing batch Bayesian optimization. The proposed method, LAW, can be used in combination with existing acquisition functions. In this paper, the combination with EST, EI, and UCB is considered, but it is also possible to combine with other acquisition functions.  indicating that it has high applicability. In addition, although the main focus of this paper is BO on permutation space, this batch acquisition strategy can also be used in batch Bayesian optimization on ordinary continuous space, suggesting its high applicability.

- Although the position kernel, the kernel for BO on the permutation space used in this study, has been proposed in existing studies, the authors proved its positive definiteness and show that using this kernel provides a theoretically tighter upper bound for the maximum information gain compared to the existing analysis. 

- In the evaluation experiments with benchmark problems and structural learning problems, the proposed method showed good overall performance. The evaluation experiments also include an ablation study for the weignt function, which clearly demonstrates the importance of the introduction.

Weakness

- The setting of the weight function is arbitrary. While there are comparisons between cases without weights and with weights, there is a lack of discussion on how performance varies depending on how the weights are set.

- The EST on which the proposed method is based can be interpreted as evaluating the conditional probability that the candidate point x is the optimal solution, but the relationship with entropy search, which is one of the main acquisition functions with similar ideas, is unclear.




questions: - LAW-UCB has not been evaluated experimentally, but how well can it be expected to perform?

- Entropy search acquisition functions and ESTs seem similar, but can the former be used for search on permutation spaces (or especially can ES use in the proposed method)?
limitations: The authors adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a new approach for BO to solve expensive permutation problems. The idea is to use batch BO to acquire a batch of data points and evaluate them in parallel. To this end, the paper proposes the use of determinantal point process (DPPs) combined with a weighting scheme to construct the batch acquisition function. Besides, the position kernel is suggested to use within the acquisition function to enhance the performance of the proposed methods. Theoretical analysis is conducted to evaluate the efficacy of the proposed approach. Numerical experiments on three combinatorial optimization benchmarks on permutations, and the structure learning problem.
strengths_and_weaknesses: Strengths: I think developing new BO methods for permutation problems is important and is worth to investigate. I also think the idea of using DPP is interesting. The authors also put effort on analysing the theoretical properties of their proposed approach.

Weaknesses: Although I like the general idea of using DPP, I found there are various issues with the current version of the paper. Please see my detailed comments as follows.

•	The paper specifically targets the permutation problems, but I don't see how this permutation property is incorporated into the design of the proposed acquisition function (except the fact that batch BO is used so that we can evaluate multiple data points parallel and thus can avoid the issue of large search space for permutation problems).

•	Even though the paper provides various theoretical analysis, but these analyses seem not to be rigorous, and might not really help to answer the analytical properties of the proposed approach.

       o	The Acquisition Weighted Kernel L^{AW} defined in Line 122 seems to not be a real (valid) kernel? As it depends on any acquisition function a(x), so it seems impossible to me that it is a valid kernel for all cases. Besides, this seems to be like a component of the proposed acquisition function, rather than to be called a "kernel".
      o	The regret analysis in Theorem 3.6 depends on the maximum information gain \gamma_T, but this \gamma_T value is not properly bounded in Theorem 3.9. Theorem 3.9 only shows that \gamma_T is smaller than a function of \lambda_{max} but there is no guarantee that \lambda_{max} is bounded when T goes to infinity. This is a key analysis in any BO analysis. In the literature, only several kernels have been shown that their \lambda_{max} is bounded when T goes to infinity.
      o	Again, same problem with Theorem 3.12, is there any guarantee that the \lambda_{max} of the position kernel is upper bounded?

•	The performance of the proposed approach on the permutation optimization problems are not that good though (Section 5.1). LAW-EI performs pretty bad, much worse than other baselines in various cases, while LAW-EST is on par with other baselines and only performs well in one problem. Besides, I don't understand why LAW-UCB is not added as one of the baselines. The justification regarding the size of search space does not seem reasonable to me. 

•	Besides, the experiments seem not too strong and fair to me. I don't understand why all the baselines use the position kernels, why don't we use the default settings of these baselines in the literature? Besides, it seems like some baselines related to BO with discrete & categorial variables are missing. The paper also needs to compare its proposed approach with these baselines.

questions: Apart from my comments in the Weaknesses section that the authors can response, I have the following questions:

1.	Is the Acquisition Weighted kernel a valid kernel? Could you also give rigorous explanation for your answer?
2.	Are the lambda_{max} values in Theorems 3.9 and 3.12 upper bounded by constants when T goes to infinity?

limitations: I think the paper does not mention much about the limitations or the societal impacts of their proposed approach.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of batch Bayesian optimization for combinatorial problems on permutations. The main idea is determinantal point processess using the acquisition weighted kernel. The proposed method LAW2ORDER is applied to solve permutation problems using Bayesian optimization. The paper provides theoretical guarantee that the batch cumulative regret is sublinear. Extensive evaluations on several standard combinatorial problems and a structure learning task demonstrate the effectiveness of LAW2ORDER.

strengths_and_weaknesses: Strengths:

- Study an important problem of applying batch Bayesian optimization to solve permutation problems.
- Good theoretical analyses.
- Comprehensive experimental evaluation.
- Writing is easy to follow.

Weaknesses:

- No code released.
- Unclear how to set the weight function.

Originality:

The originality of the paper is two folds. First, it introduces a new efficient batch acquisition method based on DPP using the acquisition weighted kernel. Second, it applies LAW to solve permutation problems.


Quality:

The problem is well defined and the proposed method is complete. The algorithm is not complicated which makes the approach accessible to potentially wide audience.

Clarity:

The writing is clear and easy to follow.

Significance:

The paper studies a very important but rarely studied problem in solving permutation problems in batch Bayesian optimization.

questions: - It in unclear how to get or set weight function during joint optimization. Could you elaborate more on this? Is setting weight function problem-dependent? 

I would like to hear more justifications on these from the authors.
limitations: - How to set the weight function is unclear. Therefore, it is unclear how to use it in practice without a principled way to set it.
- No code released.
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 paper provides a novel batch selection method, LAW, for bayesian optimisation over permutations. The authors give theoretical regret bounds and compare LAW against some baselines on three combinatorial optimisation problems.

strengths_and_weaknesses: The introductory and background sections provide good motivation and compactly cover prerequisites for the rest of the paper. The theoretical results from section 3 are put into context, with their significance and their relation to other work clearly explained by remarks within section 3. The paper as a whole is generally well written.

I'm not convinced by the claim at the end of section 3 that LAW "significantly outperforms other methods". The results in section 5 appear to show that LAW is competitive with the baselines, but do not show a definitive advantage over the best competing baselines. I do, however, think that the performance demonstrated in section 5 is sufficiently good to justify publication.

I don't feel confident in assessing how novel LAW is, or how significant it is in the context of combinatorial bayesian optimisation.
questions: How does the computational cost of LAW compare to the baselines?

limitations: I don't see any potential negative societal impact of this work. The authors did not address limitations of their work.
review_title: null

Meta-review: metareview: This work introduces a new method, based on Bayesian optimization, for solving combinatorial problems. It uses determinantal point processes in their LAW method, which is applied to permutation problems. 

The authors provide a theoretical analysis of their method, as well as empirical evidence on several of these problems.

The authors appropriately addressed the comments that the reviewers had, and they all feel comfortable to recommend to accept, and so do I.
confidence: Certain
Decision: Accept