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: The paper proposes two novel methods for combinatorial black-box optimization (i.e. over an unconstrained binary domain) based on optimistic tree search, one based on a known Lipschitz constant (OLTS) and another one when it is unknown (OCTS). The general idea of the OLTS is to evaluate nodes in a tree with large upper bounds in their subtrees, where the upper bound is based on the Lipschitz constant and the diameter of the subtree. This is extended in OCTS when the Lipschitz constant is not known by searching a superset of nodes that would contain the node in OLTS. Both methods are proven to have linear convergence rates (with a dependence on the Lipschitz constant). Computational experiments show that OCTS outperform several other heuristic-based methods.
strengths_and_weaknesses: The black-box methods proposed in the paper are very appealing: they are simple to implement, theoretically grounded, and appear to work well in practice. The approach appears to be original as far as I am aware. The computational section is sufficiently extensive, with six different problem classes and one experiment to illustrate the convergence rates, and the method generally outperforms the baselines. I particularly appreciate the theoretical guarantees and their computational analysis in Section 6.1.  The paper could have benefited from a comparison with model-based methods, but I believe it is not too unreasonable to omit them given that they typically have more expensive iterations. The presentation is overall clear, but there are several minor issues that need to be addressed below.

Most of my comments below are regarding presentation, which should be fixable. Assuming those are addressed, I recommend acceptance for this paper.
questions: These are only presentation issues, but they nevertheless should be addressed.

1. The introduction claims that these methods are "provable", which is unfortunately not discussed further. A natural interpretation might be that the algorithm finds the provably optimal solution for some reasonable budget. However, at least OCTS does not return a provably optimal solution without exhaustively searching all of the $2^d$ points. On the other hand, if one would include exhaustive search in the definition of "provable", then this is not a meaningful claim. If there is no reasonable explanation for what "provable" means in this context (and I believe there is not), this qualification only adds confusion and should not be used.

2. Could you include some discussion about solve/iteration time compared to the baselines, even if briefly? Preferably, if you have computational results on this, that would be best. My impression is that the iterations should be comparable to the baselines in the proposed method, but as is I cannot exactly verify if OCTS is indeed faster than other methods. This might be more suitable for the appendix but I would add a sentence referring to it in the main text.

3. The paper defines the algorithms relative to a class of tree structures. However, the computational section does not specify exactly which tree was used. Could you mention that in the paper? In addition, I would have liked a brief discussion on the effect of using different trees (e.g. does the tree really make a difference?), but this is not essential.

4. I would adjust the statement in p.9: "no efficient algorithm exists to find maximum independent sets". Although the problem is NP-hard, this is not accurate if this is interpreted as "efficient in practice". It is fine to say that there is no known polynomial-time algorithm (although this is already implied by the NP-hardness), but maximum independent set is reasonably tractable in practice.

5. In MaxSAT in p.9, please clarify that the "optimum that no other algorithm could find" is with respect to the baselines examined in the paper. Since the previous sentence talks about specialized solvers, this clarification would help avoid the misinterpretation that this statement includes them as well.

6. I am aware that this is mentioned in Section 2.1, but I suggest mentioning in the introduction that this method is tailored to black-box problems where evaluation is not expensive. This is so that, first, readers can quickly identify if this is a good approach for their black-box problem, and second, you immediately establish the scope of your method, i.e. you are not comparing against methods that may have expensive iterates such as model-based methods. If you have space, I would even briefly reiterate this when defining the baselines in Section 6.2.

7. Please run a spell checker for the camera-ready version, there are many typos in the paper. Here are some of them: l.54, "dimensionalitites"; l.154, "a-priory"; l.163, $x_{l,i}$ and $\mathcal{X}_{l,i}$ should be indexed by $l_t$ and $i_t$; l.195, "Moroever"; l.202, repeated "order", l.264: "bt", l.265: "iteration" should be plural; l.289: "dimensionailites"; l.318, "runing"; l.570: "maximimum"; l.782: "Real-word problems"; [18] and [19] are the same reference.
limitations: No limitations besides the ones discussed above.
review_title: null

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 presents an algorithm for solving combinatorial optimization problems where the objective function is a "black box" accessible only via an oracle. The algorithm is targeted at problems where this oracle is relatively cheap (as opposed to the standard Bayesian optimization setting), and is accompanied by finite time termination guarantees. The core algorithm relies heavily on Lipschitz constants to guide search and prune the tree; as this constant is often not known, the authors present a variant that instead only relies on the existence of a Lipschitz constant. The authors conclude with a computational analysis of the performance of the algorithms as a function of the number of function evaluations. 
strengths_and_weaknesses: The paper: presents a novel algorithm in an area of interest to the NeurIPS community, includes interesting theoretical results, and is clearly written. The only weakness I can identify is the lack of a computational comparison against Bayesian optimization techniques (see "Questions").
questions: * Please consider moving the qualification as to why Bayesian optimization methods are not included in the computational study from the Appendix to Section 6. I am also not sure how convincing I find the author's argument on this point: even if Bayesian optimization is much slower per iteration, if it nonetheless provides good solutions after relatively few function evaluations then this provides an interesting baseline for comparison with the new algorithms.
* p22 l756: There is a typo in at least one of the convergence rates (I think the first).
limitations: There is no explicit discussion of potential negative societal impact.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper considers the black-box optimization of combinatorial binary functions. The functions are assumed to obey a Lipschitz  condition given some metric on the hypercube. For the optimization problem, the authors propose two algorithms, depending on the knowledge of the Lipschitz constant. Both algorithms rely on tree search and optimistic upper bounds. Theoretical guarantees are provided for the convergence of the algorithms. The empirical work show that the algorithm with unknown Lipschitz constant (OCTS) outperforms the considered baselines on a variety of problems. 
strengths_and_weaknesses: The proposed algorithm is fairly natural given the Lipschitz assumption. The case of unknown Lipschitz constant is treated in a similar way as the DIRECT algorithm (although it is not referenced).

The theoretical results are straightforward, but nevertheless useful. 

The binary tree is assumed as provided, but I would assume that the ordering of the indices might have significant influence on the performance.    

Given the optimistic tree search approach, the problem is somewhat related to the combinatorial bandit problem. The main difference here is that the function is deterministic, which allows much stronger bounds, but I would assume some techniques from combinatorial bandits could carry over.   

The empirical performance is a strong argument for the paper. The baselines are difficult to evaluate, since there is little detail provided regarding their implementation and parametrization. 

questions: Algorithm 3 (referenced from Algorithm 2) is only in the supplementary material. This poses some problems in the readability of the paper that should be resolved.
limitations: It is not clear how meaningful the Lipschitz condition is for the practical problems considered (beyond the constant that results from the discrete nature of the problem).
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 addresses the problem of combinatorial black-box optimization. The solution is built upon a tree-structure search procedure with optimistic search strategy. The contribution of the paper in my opinion is two-fold: 1) Algorithmically, it designs a new combinatorial black-box optimization solver OLTS (and its practical variant, OCTS) by adapting the optimistic strategy applied on tree-search optimizer. 2) Theoretically, it provides convergence analysis on the proposed solver (and its variant OCTS) which is shown to be superior than random search. 
strengths_and_weaknesses: Strengths: 
1) The structure of the paper is clear and the paper is overall well-written. The clarity is in general good, except for a few points that will be discussed in the weakness part. 

2) The problem of combinatorial black-box optimization is an important problem that has vast applicability of various domains, including machine learning. 

3) The paper provides the first finite-time linear convergence rates for the problem. It is a significant improvement compared to the logarithmic rates of baselines (random search). 

4) The empirical results are promising. The algorithm, though simple, has been shown to be outperforming the baselines on a set of benchmark black-box combinatorial optimization problems, including LABS, MIS, Ising, MaxSAT, and Contamination. 


Weakness:
1) The novelty of the proposed solvers, OLTS and OCTS, is limited. Both the tree-based search and the optimistic strategy have been well studied under similar contexts. The main critique from me is not that the algorithms are not novel, but that the novelty is somewhat overclaimed.

For example, the tree based search has been discussed in a few previous papers (e.g., in [39] and also UCT -- UCB for trees). But this has not been acknowledged in the paper. It appears that the tree structure is first proposed in this paper. 

As another example, the optimistic strategy for estimating the potential of the tree nodes is also adapted from [39]. Though the paper lists three major differences of OLTS/OCTS vs [39], it still seems incremental. Also, it is not clearly explained why these differences are made to adapt to the tree structure and what are the advantages. 

2) It is not clear what are the intuitions of l(n) and n_c in the propositions and theorems, so that it is hard to understand how tight the derived convergence bounds are in the respective theorems/propositions. At least from a first look, the bounds do not seem tight, and therefore the theory is not as informative. The paper would be stronger if these are better explained/clarified. 

3) Bayesian optimization is an important category of methods for black-box combinatorial optimization problems, but it is not included in the set of baselines. Why is it? It would be good to explain.

4) The empirical results are promising in general. One question from me, though, is that, what are the reasons that certain problems are selected for evaluation. For example, reference [18] and reference [41] each provided a set of benchmark problems, but this paper selected a subset from each of these two references instead of evaluating all of the settings in either one of them. It does not seem that the proposed OCTS cannot work on the other problems, e.g., the neural architecture search benchmark which is of potential high interest to the ML community. 

Minor aspects: 
1) The introduction well motivates the paper, but is a bit too condensed. Perhaps better to split it into multiple paragraphs. 
2) Line 186: I_h seems to be a typo, it should be I_l
3) Line 270: Proposition A.3 -- is it a typo?

questions: Please see some questions in the detailed comments above. Below are some other questions. I would not expect the authors to answer all of them but I am listing them here nonetheless. 

1) Is the tree representation of the combinatorial space first proposed in this paper, or was it proposed by some existing papers but perhaps in a different setting and goal?

2) Why is Bayesian optimization not compared as a baseline? 

3) The definition of l(n) is a little bit involved, so that it makes it hard to understand how well bounded the solution of OLTS/OCTS would be. Could you illustrate a bit more about the intuition of l(n)? Perhaps using a concrete example to show what is a typical value of l(n). 

4) Similar question to n_c in Theorems 4.3 and 5.3: what is the intuition of n_c, and what is a typical value for it? This is important because if n_c is very large (which seems to be from its exponential form), then Theorems 4.3 and 5.3 would be less informative. 

5) In the empirical results, the MIS-30 setting yields no good strategy, but in the MIS-70 setting, OCTS and a few other methods achieve optimal performance in the first few iterations. Why does dimension make the structure of the problem so different so that the difficulty of finding a good solution is totally different?



limitations: The authors claimed that they discussed potential limitations (1.b) and negative societal impacts of the work (1.c) in the Appendix, but I cannot see any obvious discussions of this kind.
review_title: null

Meta-review: metareview: This paper proposes two methods for black box optimization of Lipschitz combinatorial binary functions. The reviewers agree that the paper is well written, the methods are sufficiently novel, and that the results are of interest to the NeurIPS community. The main drawback with the paper is that reviewer n1bW felt that the theoretical results are straightforward (but nevertheless useful). Several reviewers also had hoped for comparisons with Bayesian optimization techniques, but during the discussion period it was decided that this comparison can be omitted due to the much higher computational cost of Bayesian methods. I tend to agree with the reviewers that this paper is above the bar for NeurIPS.
confidence: Less certain
Decision: Accept