Optimistic Tree Searches for Combinatorial Black-Box Optimization
Authors: Cedric Malherbe
Antoine Grosnit
Rasul Tutunov
Haitham Bou Ammar
Jun Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Optimization
Black-box
Combinatorial
Tree Search

Abstract: The optimization of combinatorial black-box functions is pervasive in computer science and engineering. However, the combinatorial explosion of the search space and lack of natural ordering pose significant challenges for current techniques from a theoretical and practical perspective, and require new algorithmic ideas. In this paper, we propose to adapt the recent advances in tree searches and partitioning techniques to design and analyze novel black-box combinatorial solvers. A first contribution is the analysis of a first tree-search algorithm called Optimistic Lipschitz Tree Search (OLTS) which assumes the Lipschitz constant of the function to be known. Linear convergence rates are provided for this algorithm under specific conditions, improving upon the logarithmic rates of baselines. An adaptive version, called Optimistic Combinatorial Tree Search (OCTS), is then introduced for the more realistic setup where we do not have any information on the Lipschitz constant of the function. Similar theoretical guarantees are shown to hold for OCTS and a numerical assessment is provided to illustrate the potential of tree searches with respect to state-of-the-art methods over typical benchmarks.

Optimistic tree search strategies for black-box combinatorial optimization
Cedric Malherbe', Antoine Grosnit', Rasul Tutunov', Jun Wang 1.2
Haitham Bou-Ammar
Huawei Noah's Ark Lab, University College London firstname wwwtname@huwwii.coommm
Abstract
The optimization of combinatorial black-box functions is pervasive in computer science and engineering. However, the combinatorial explosion of the search space and the lack of natural ordering pose significant challenges for the current techniques from both theoretical and practical perspectives. In this paper, we propose to introduce and analyze novel combinatorial black-box solvers that are based on the recent advances tree search strategies and partitioning techniques. A first contribution is the analysis of an algorithm called Optimistic Lipschitz Tree Search (OLTS) which assumes the Lipschitz constant of the objective function to be known. We provide linear convergence rates for this algorithm which are shown to improve upon the logarithmic rates of the baselines under specific conditions. Then, an adaptive version of OLTS, called Optimistic Combinatorial Tree Search (OCTS), is introduced for a more realistic setup where we do not have any information on the Lipschitz constant of the function. Again, similar linear rates are shown to hold for OCTS. Finally, a numerical assessment provided illustrate the potential tree searches with respect to sate-of-the-arr methods over typical benchmarks.
Introduction
Finding optima of combinatorial black-box systems an old problem with ubiquitous applications including but not limited to hyperparameter tuning [29], object detection [49], radar engineering [41] or model sparsification [7]. When facing such problems, two routes can generally be distinguished: 1) model-based techniques such as Bayesian methods [6, 14, 19, 26, 39] or 2) heuristic-based methods such as genetic and evolutionary algorithms [4, 21]. However, there is consistent gap between those two types of approaches. While relying Bayesian modeling, the optimization only focuses functions that align with the model and, more importantly, the heavy cost optimizing the inner model restricts their use systems where can only afford few hundred function evaluations. On the other hand, heuristics methods are generally too coarse and tend to exploit very few information the objective function which can get them easily stuck in local optima [31]. Further, the theoretical analysis of these approaches are generally loose when predicting their performance and limited to specific functions [16, 18, 20].
In this work, we aim at filling this gap by proposing the first provable black-box solver for combina- torial functions that rely minimal assumptions. More precisely, design novel solvers that come with provable guarantees and are tailored to optimize functions with moderate or cheap-to-evall to-evaluate cost. To do so, follow novel route and propose to develop approach that employs ideas from tree searches and partitioning techniques. Precisely, we build upon the works DIRECT [30] and SOO [37] and show how to optimistic tree searches combinatorial spaces. However, the application of these techniques to combinatorial structures is limited by three major draw backs related to the absence of well suited trees for combinatorial spaces and the use of continuous notions that are further detailed in the next section.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Providing solutions to these problems, our contributions can be summarized as follows. First, we identify novel conditions create combinatorial trees tailored for the optimization of combinatorial structures (Section 3). Second, we show how to use these trees and develop the first combinatorial black-box solver with provable guarantees that rely on optimistic tree searches (Sections 4 & 5). Third, from theoretical perspective, we obtain the first finite-time linear convergence rates that drastically improve upon the logarithmic rates of baselines, and explain the fast convergence of the solvers (Theorems 4.3 & 5.3). Finally, we provide a numerical assessment that illustrates the potential of tree searches with regards to existing techniques (Section 6).
Problem setting & related work
Setup. We focus on the problem of maximizing black-box function over the Boolean hypercube
[6, 43). We denote by X = (0, 1 the binary input space of dimensionality d' 2 1 and by f ; + R
real-valued objective function we wish to optimize. Our goal is to find optimum x² E X' solving:
argmax f(x)). =EX
(1)
It is important to note that the paper adopts the standard black-box perspective in that f cannot be assumed to have desirable characteristies such as linearity, quadraticity or submodularity that may facilitate the search for z². In fact, it is only assumed that the values of the objective function f() can be evaluated at any candidate solution x E X through an oracle that generally corresponds to a numerical evaluation of the function.
Prelininaries. first strategy solve Problem (1) would be systematically enumerate and evaluate all possible candidates in the search space. Since the cardinality | =ddi((2) grows exponentially with d, fully exploring X' quickly becomes impractical even for moderate dimensionalities d. As such, standard optimization strategies attempt approximate the global optimum by only evaluating n < | candidate solutions. To carefully choose those n points, effective strategies rely on sequential procedures that choose the next evaluation point T E X' depending on information collected so-far (41, (x1)),..., (II,, (xx)) with denoting the iteration count.
For any ax))²) E {0, (0,1)xx2, we denote by d = Ei=i..d Taa; * x/) their Hamming distance where I[-} is the indicator function. We also utilize Lip(k) = {f: f0, 1] - R [f(x) - ((x)) < k dz (z), V(x,,²)) E {0, 1] ]xx2] represent the set of k-Lipschitz functions. For any subset A C {0, 1]d, we further define its diameter DA max du (x,
Notations.
Lastly, [x] and [x] denote the floor and ceil operations and A y min(x, y).
2.1 Related solution strategies
Bayesian optimization has emerged as powerful technique for the opti- mization of popensive-to-cvaluee functions [13, 19] and has recently been extended to combinatorial spaces [6, 39, 48]. It relies on surrogate models and Bayesian probabilities carefully selects the next evaluation point Tz+1 E arg m a₂ (z) by solving an inner optimization problem where (-) is an acquisition function that depends on the chosen model. However, solving this inner optimization problem (often treated as black-box box problem) can be computationally as hard as directly optimizing the black-box function f when its evaluation cost is cheap, which restricts their use to expensive-to-evaluae systems where we can typically only afford few function evaluations. Thus, the novelty of our work is complementary to Bayesian optimization in the sense that (1) develops novel algorithmic ideas that aim at optimizing functions with moderate or cheap evaluation cost and (2) it provides novel theoretical insights for the generic problem of optimizing combinatorial black-box functions which are model-free.
Bayesian optimization.
Evolutionary algorithms. Evolutionary algorithms use mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection to optimize black-box functions [44]. They are generally the first line of algorithms attempted when facing black-box problems due to their flexibility. However, when compared to other techniques they do not always identify the global optimum of the function, can get stuck in local optima and are not necessarily sample-efficient (see, e.g., [25] and Section 6). In terms of theory, most works focus specific synthetic problems such as the OneMax or LeadingOnes functions [16, 18, 20). To the best of our knowledge, no finite-time time- bounds or samplc-complexity results are known for these strategies. Thus, with regards to

---

evolutionary algorithms, the novelty of our work is (1) to propose novel and orthogonal approach to combinatorial black-box optimization that relies on tree searches and (2) derive generic finite-time analyses of the algorithms which hold for large class of functions.
Optimistic tree search strategies. Optimistic tree search strategies [37] refer approaches that implement optimism in face of uncertainty. This principle originated in the multi-armed bandit literature [2] and was later extended tree searches. Similarly, tree based searches have also been discussed and analyzed in different settings such as UCT [11] and UCB [2]. The seminal work in [36] then adapted the optimistic principle to black-box optimization and introduced notions to analyze the convergence of these strategies in continuous spaces. More precisely, they provided sample complexity results characterized by two coefficients: d and C, where d is the near-optimality dimension (defined therein) and C' is a corresponding constant. Precisely, they show that objective functions with near-optimality dimension zero enable exponentially decreasing rates of optimistic tree search on continuous spaces. This, of course, opposes the polynomial rates attained by grid-search-liks algorithms, for example. Later, this work was extended to settings with noisy evaluations [8, 23, 46], robust considerations [1] and Brownian optimization [24]. Though successful in isolated instances, none of the aforementioned algorithms are equipped to handle combinatorial spaces due to difficulties steming from the finite nature of the problem and the lack of natural ordering in discrete spaces. Succinctly, we identify the following three obstacles: (1) Contrary to continuous settings, is not possible to define infinitely finer partition of the search space restricting algorithmic design; (2) We cannot adopt continuous measures (e.g., optimmttt dimension) which depend on arbitrarily small neighborhoods around the optima to define complexities of combinatorial functions; (3) It is difficult to rely on bounds of the (rather standard) form: maxrex (x) max;=1...n f(x;) S Cn- with large constants C and attempt to analyze their exponent a. This is due the fact that in combinatorial spaces n is (generally) upper bounded by X the cardinality of the search space X. Hence, the associated upper-bound C'|x|-
not necessarily informative under finite n. In this work, we fill this gap and show how to use optimistic machinery in combinatorial spaces. First, we introduce novel tree representations using hierarchical partitioning of combinatorial spaces. We then make the observation that all combinatorial functions are Lipschitz with kmin = max [f(z)) fz (('))/dx(xx which we utilize to obtain discrete upper bounds of the form (d- (n)) with 1(n) E N. Importantly, our bounds only depend on the intrinsic properties of the black-box function like the conditioning of Definition 4.2. As a byproduct, we demonstrate that our optimistic tree search techniques can achieve linear decreasing rates compared to the logarithmic one exhibited by "naīve" strategies.
3 Tree representation of the combinatorial space
To implement optimistic tree search strategies [37], we need a hierarchical partition of the combinato- rial space. A key ingredient of our approach lies in a specific nested tree representation of the input space X' {0, 1)dd Precisely, we consider fully-balanced binary tree, T, of size 2d+1
and depth d. The nodes of tree T, denoted by node (1, i). are indexed by the values of the level I E (o..... .d) and the corresponding index E (O,..., , 2 - 1} within that level. Each node (1, i) is associated with a candidate solution 2i,1 E X where the objective function f may be evaluated. Whenever node is not terminal (i.c., < d). each node (1, i) is associated with a left child node (I + 1, 21) and a right child node (1 + 1, 2: + 1) at level I + 1. Moreover, since there are 2d+1
| nodes in the tree, a first specificity we consider is imposing that the value of the left child node 1/4 is equal to its parent node 2,,; for any node.
Assumption 3.1. For any level / E {O...., d 1} and i E 2 - 1}. we have +125 = 31,
Importantly, this condition will be used in our approach to perform only one function evaluation when traversing levels in the tree. Additionally, we define the set Xr, of child candidates associated with a node (1, as the union of the candidate solution at this node and all the candidate solutions associated to its children.
Definition 3.2. (Child nodes). For any node (I, E T, we define the set XG,s S X of children candidates recursively as follows:
Xr; == ( U X4412 U X41,2441 WE (O,..,, d d-13, 1},
where by convention, Xa, { for all terminal nodes with i (.....2 2d -1}.
3

---

100
D.0
0
0
A6
161
0.0
2214
FULL
30.0
Nia
000
001
OLD
OLI
100
101
110
111
Figure 1: Left: example of the tree representation of the combinatorial space X' {0, 1] used when 3. The arrows represent the links between the nodes, and the nodes contain the value of ø Right: The set of children nodes Xr associated with each node(1, i) of the tree forming a hierarchical partition of the search space satisfying the decreasing diameter property (Assumption 3.3).
It is important to note that the input space X' can be partitioned into the disjoint sub-spaces Xi, satisfying X' U Nt, ; at any level / 0. The last crucial property of the tree representations we consider is that of exhibiting decreasing diameter in the following sense.
Assumption 3.3. (Decreasing diameter). We say that a tree satisfies the decreasing diameter property if, for any node(l, i) E T,, its set of children nodes Xr,; satisfies:
Diam Diam(Xr,)) := max dy (z, x²) d- (a,x'))X?,
Informally, this condition states that one picks any pair of candidates (x1, E X2, in a cluster Xr,s at any level I, we have that d (II, S L. This, turn, ensures that the deeper we go in the tree, the closer the points bundle within single cluster.
Applicability of the assumptions. Of course, the above conditions are not met by all trees. However, we can show that very natural representations of combinatorial spaces do, in fact, satisfy these assumptions. Actually, we identify that the trees which start at any root node and are split among I components of either values of ( or 1 do satisfy these conditions. Formally speaking, those trees (illustrated in Figure 1) can easily be constructed using the points Iı,; Bin, (i) 0²-11 where Bin (i) [0, 1, 0)
denotes the binary representation of i on bits (e.g., (0) = [0, 0, 0j and Bina(2) and 02-1 denotes the vector filled with d - zeros. On top of this construction, it is also important to note that adding vector permuting the index of all the elements of these trees preserves these conditions (i.e., transformations π (x115) + c on all nodes the tree for any E (0, 1]d and permutation (1..... d) + (1....,d))
Comparison with continuous trees. Finally, we point out that a comparison of the trees we propose to the trees used in continuous structures can be found in Appendix C.
4 Optimism in face of combinatorics: the known Lipschitz constant case
We now introduce a first algorithm to optimize combinatorial black-box functions given a priori knowledge of being Lipschitz, i.e., f E Lip(k) for given constant A: 2 0. The aim of this section to understand whether exploiting this information enables faster converging algorithms compared to exhaustive and random search. With those developed. then extend our analysis to functions with unknown Lipschitz constants in Section 5.
4.1 The optimistic Lipschitz tree search (OLTS) algorithm
The OLTS algorithm (Algorithm 1) implements the optimistic principle [37] over combinatorial trees and aims maximizing any function defined on the binary input space given known Lipschitz constant & 2 0. It starts by evaluating the function f ( at the root node (0. 0) of the tree and initiate the tree search by setting the root node as starting point (line 2). At each iteration > from Ti-1- Once
the algorithm selects node (4, it) with the highest value ( + 4dDiam(X,,.) (le, &e) is selected, OLTS evaluates the function on children nodes adding them to the list of nodes of the current search. Note that the function is only evaluated on the right child as the value its

---

Algorithm 1 Optimistic Lipschitz Tree Search (OLTS)
Require:
Tree representation of the search space {0. 1)" Lipschitz constant & 2 0, budget n 2 1: Evaluate the objective function at the root node (
2: Initialize the tree search at the root node of the tree Ti (0)
3: for = 2. do
4: Get the index of the node from the tree search with the highest upper confidence bound:
(4, it) E arg max (f(21,)) + &Diam(&t.))
(1,0)Ti-1
5: Evaluate the objective function on the right child of the selected node I ((11,+122541))
6: Remove the selected node from the tree search and add its child nodes if they are not terminal:
Te - Tr-1/111,, ie) U {(4 + -,1, 2i2)), (4e + +,, 24g + 1)}
7: return oi with (n) E
() f(22.)
arg max
left child +12,,) already known according to Assumption 3.1, whereby +1,4, &t, Thus, the tree search is guided by two different quantities: (1) f(1,;) which represents the value of the function at node and (2) (ii,() which indicates the size of the remaining children nodes below the (1, 1)th node (Definition 3.2). Formally, this node selection rule can be explained by observing that since f E Lip(k)), for any node (1, i) T in the search list, any of its child nodes satisfy: f(x) < (x) := f((1.)) a.,) Vx E Xi, As such, OLTS explores the part of the tree 4e) that exhibits most promising values according to the previous upper bound. This selection process is often referred to "optimism in the face of computational uncertainty" where the uncertainty comes from the potential function values. Although using a similar selection switch strategy to DOO [37]. OLTS manifests three main differences: (1) once node is selected, one component of the node by evaluating the function on its right child and do not make several evaluations that depend d, (2) we keep the left node value unchanged while only changing its level in the tree search when moving along the tree, (3) upon reaching level d 1, we do not add any nodes to the tree.
4.2 Theoretical guarantees for OLTS
Due to space constraints, we only present here the main results of our analysis and refer to Appendix D for more details. We start by casting generic convergence results for the algorithm.
Proposition 4.1. (Convergence of the OLTS algorithm) Let f E Lip(k) be any objective function and let I, = {nodes(l, i) E T fII + kDiam f(="). Then, if ff,...., In. denote the set of evaluation points generated by OLTS tuned with constant ls after n iterations over f and the tree representation of Section 3, we have;
max f(x) max f(z,) S k. (d ((n))
x
==
where (()) == min L EL 4 n
This result provides generic finite-time bound on the approximation error that only depends on the cardinality the set of potentially optimal nodes (further described in the Appendix D) and through the definition of I(n). Here, I(n) corresponds to the minimum depth at which the tree search will be after n iterations. Of course, since the set k-Lipschitz functions contains very distinct functions, we expect the algorithm to display different behaviors captured here through the values of [1].
To gain a finer understanding, we thus bound this term using the following key complexity measure that describes the behavior of the function around its optimum x: through local one-sided Lipschitz assumption.
R be any k-Lipschitz function. Then, if admits a unique global optimum x= E X, we denote by h 2 0 the largest value such that, for all r X, we have:
Definition 4.2. (Conditioning number). Let
f(x) fx()) 1e (x,x
21 20,0 and 21,+1.2 for t
5

---

[10)- -lote.))
Mininomn distinne E. 4AT0 Fte)
(e) dalat.
Figure 2: Computation of conditioning num- ber on two functions f(x) -d (2, x²) /d [I, with [1]+5 and [(x) The black dots represent the and minimum value of the function in terms of distance to the optimum x'.. The green and red lines represent the slopes of the Lipschitz constant & and local smoothness coefficient k." With k = 1, for the left function we have c and c = v for the second function.
and we denote by c= k/kk its conditioning number.
This conditioning number is closely related to measures used in continuous spaces [10, 34, 37]. However, it is interesting to note that since the input space X' is discrete, the conditioning number is always defined 2 as opposed to the continuous space case. Moreover, Figure 2 provides an example of such computation. Equipped with Definition 4.2, derive the following fast rate for OLTS.
Theorem 4.3. (Fast convergence rates). Let J E Lip(k) be any combinatorial function with unique maximiser with conditioning number c = k/k" <, sd11. 1. Then, if y..-.. ; In denotes the series of evaluation points generated by OLTS tuned with constant k: 2 O after n iterations, there
exists some ne S -2 and C 2((22t))) )4 such that
d+1-1
In(n)
in S ne
max f(x) max f(x)) S k ZE
[2
i= 1....
d+1-
In(ne) In(2)
in > ne.
To gauge the importance of OLTS, we compare the convergence rate from Theorem 4.3 to those of exhaustive and random search of order In())/ In())) that we derive in Appendix B. Our results indicate that we obtain improved linear rates over the logarithmic ones of such baselines and highlight two regimes of operation that depends on the value of log(n..) which corresponds to the level after which the number of potential optima per level stops to explode and the algorithm will get linear behavior. Namely, when < Ree attain similar rates to exhaustive search. But upon passing this threshold n Te. the OLTS starts achieving linear rates with a constant C by exploiting previous evaluations and focusing promising areas. Hence, there is exponential gain with regards to the convergence of naïve methods. To the best of our knowledge, it is the first result of this kind. Moreover, the conditioning number has both an impact the length of the exploration phase no and on the rate of convergence C. Thus, we deduce that to enjoy best convergence rates, the value of the Lipschitz constant k 0 has to be chosen small possible.
5 Optimism in face of combinatorics: the unknown Lipschitz constant case
In this section, we introduce an extension of the previous algorithm to black-box settings where no knowledge of the Lipschitz constant is provided.
Potentially optimal nodes. Similar to the previous case, our algorithm will perform a search on the tree representation of Section 3. We thus require technique to identify the set of potentially optimal nodes to guide the search. Since the Lipschitz constant is not known, we cannot get an upper bound indicating the potential values of the function as conducted in Section 4. To overcome this issue, we propose to define a novel set of potentially optimal nodes that do not explicitly depend on the Lipschitz constant of the objective function.
Definition 5.1. (Potentially optimal nodes) Let T ((1, ((1,,)...... ii).... (4,, 4c)} be any set index of the tree where have evaluation of the objective function f(r,, s. ). Then, node(1, i) from the tree search T is said to be potentially optimal if there exists some Lipschitz constant > such that f(1,,) &Diam(Xi. (),,) > [xr ,x) DDiam(Xe.p Xx,x) for all (1',")) T.
Informally, this definition states that node is potentially optimal if there exists some Lipschitz constant such that the standard upper confidence bound evaluated on this node will be the highest
with kn = maxigiga (f(x)) min (odn (x))

---

(xx) - max (xx) < Kmin (d 1(n) - 1) max x Algorithm 2 Optimistic Combinatorial Tree Search (OCTS)
Require: Tree representation T of {0, 13", budget n 2 2
1: Evaluate [x 1
2: Ti & {(0.0)}
3: while t < do
4: Get the potentially optimal nodes of the tree search (Algorithm 3 in the Appendix): T + OptimalNoodss7.)
5: for node(l", it) in Ti" do
6: Evaluate the function f(x)+ +1,25 41) on the right child of the node .f".. t t+1 Remove the node(l", 1²) from the tree search and add its children if they exist:
7:
T Ti-1 10" + 1,22"") (1" + 1,22 + 1)3/(1,7 ,*)
8: if 1= n2 then Return dh with (bes in) E arg maxu, 12) Ti f(11))
among all other nodes of the tree search. Although it involves check the existence of Lipschitz constant, such computation can easily be executed from a simple geometric perspective. Indeed, node potentially optimal if belongs to the set of Pareto points of the graph representing the levels I of the nodes and their values fZt1s). J. For more details on this topic, we refer to Appendix E where an illustration and Algorithm compute the potentially optimal nodes are presented.
5.1 The optimistic combinatorial tree search (OCTS) algorithm
The OCTS algorithm (Algorithm 2) implements the optimistic principle [37] over combinatorial trees and aims at optimizing any black-box objective function f defined the combinatorial space X = 13d. It only takes as input the tree representation T of the search space (Section 3) and the evaluation budget
Similar to OLTS, it starts to evaluate the function f=0.0) at the root node (0, 0) of the tree and initiates tree search Ti. At each round, OCTS selects the set of all potentially optimal nodes (line 4) and evaluates the function over their right child nodes (line 6) and updates the tree search (line 7). The main trick here is that since the Lipschitz constant & 2 0 is unknown, we select larger sets of nodes (i.e.. the set of potentially optimal nodes, line 4) that will nonetheless contain the node maximising the upper bound of the OLTS algorithm with known Lipschitz constant. Indeed, denoting by Kmin min {k 2 0: f E Lip(k) the smallest (unknown) Lipschitz constant of the objective function, one can easily show that at each round:
arg max {f(I),)) + kmin Diam E OptimalNodess(T). (L.))TT
Thus, with regards to the selection procedure with known Lipschitz constant (line 5 of OLTS), we still select the node that maximises the upper confidence bound with the best possible Lipschitz constant most d' - other nodes (one per level)
kmin at the extra cost of evaluating the objective function which are also potentially optimal. Although using a similar selection strategy to SOO [37], OCTS manifests three main differences: (1) at each round the selection of potentially optimal nodes is static and does not add the ongoing evaluations of line 6, (2) we do not have a parameter ln()) that controls the maximum depth of the tree, and (3) when a node is selected, we simply switch one component by evaluating the function on its right child and do make several evaluations that depends on the dimensionality of the problem.
5.2 Analysis of the OCTS algorithm
As noted above, one of the key features of the algorithm is that each round, we have the guarantee that it selects the node maximising the upper bound with the best possible Lipschitz constant kmin- Therefore, possible to recover the following theoretical result:
Proposition 5.2. (Convergence of OCTS). Let f X + R be any combinatorial funniioooiialuuncionn function and let Ie := {node(L, i) T f(1,,)+ Kmin Diam x) 2 f(=")} with kmin min(k 2 0: f E Lip(k)) Then, if x1, ..,..., Fn, denotes the series of evaluation points generated by OCTS over J, we have that
==1...
where ((n) =max(0 L v d 1: (n/d) EL= 171..
7

---

By comparing this results to Proposition 4.3 of Section 4 with known Lipschitz constant, it is interesting to note that here we now use the smallest Lipschitz constant Kmin which ensures that [4;] has minimal size while having a division by d in the definition of ((n) which slows down the rate. This trade-off is further detailed the next result:
Theorem 5.3. (Fast convergence rates). Let f X - R be any combinatorial function with unique maximiser and let с = Omin/k < d - be its conditioning number. Then, if æ1...... In denotes the series of evaluation points generated by OLTC after n iteration, there exists some
ne S d2) 1 and C < 2 x-)= such that:
In(n/d) In(2)
if S npe
max f(z) - max f( S Emin x #EX
1=1...
In(n./d /d)
d in > The
Surprisingly, although the Lipschitz constant is not known, the same conclusions still hold to the case when & is known. The main difference is the apparition term d which slows down the linear convergence rate at the price of allowing target objective functions with unknown smoothness.
6 Numerical experiments
In this section, we conduct two sets of experiments to 1) show how the theoretical insights provided in the paper are aligned with practice and 2) illustrate the potential of tree search strategies with regard to existing state-of-the-art solvers.
6.1 Convergence rates and scaling
First, we compare the empirical performance of OCTS to the baseline Random Search (RS) for which convergence rates are known on three synthetic functions: OneMax f(z) = EEi=11zz (z,== 1}. Harmonic f(x) Σ -i= iz, and LeadingOnes f(x) Σ Ei=l I Zj. Note that using synthetic functions allows to exactly know the approximation error and rates. Figure 3 displays the approxi- mation error in terms of the number of evaluations averaged over ten rums as well as the number of evaluations required to identify the global optimum. As it can be seen in the first row, the convergence rate of RS is indeed of order (nn)n())) as suggested by Proposition B.3 in the Appendix while OCTS achieves exponentially faster rate of order ((-n) after certain threshold suggested by Theorem 5.3. Moreover, as displayed the second row, it is important to note that this fast convergence allows us to identify the global optimum in at most (d In evaluations instead of O(2") evaluations using RS. This, thus, validates the insights provided by the analysis and shows that it is possible to identify the global optimum on problems with large dimension using tree searches.
OneMax
Harmonic
Leading
Figure 3: First row: approx- imation eтror max f(x) maxi=1...n fx:; in terms of num- ber of function evaluations in log scale dimensions 30, 50 and (=0.11 standard deviation in trans- parent). Second row: expected num- ber of function evaluations required identify global optimum log scale in terms of dimension d. The curve d² log(d) ()) is plotted in dashed lines for comparison.
22"
30
307
30
32*
30
13
35
327
31+
327
247
Ordfftx
Leaiingtiees
2014
10
10
Nittrr
20
03
80
40
82
23
60
100
6.2 Comparison on real-world problems
Here, our goal is to compare the algorithms on several real-world problems with moderate or cheap- to-evaluate objective functions. We compare the performance of OCTS with six methods commonly used solve combinatorial black-box problems: Simulated annealing [45] (SA), Random Search [9] (RS), Randomized Local Search [38] (RLS), Genetie Algorithm [43] (GA), Evolutionary Algorithm

---

LABS 30
LABS 70
Concatenated trap 30
20000
10000 61000
80002
100002
200000 200000 #30000
20000
.0026
55000
00002
100002
200.03 20003 400030
MIS 50
MIS- 73
5 X 5 R
MaySAT 28
MuISAT 60
20000 ciece 99530 10000
190153 20:000 2000 000.02
20030
60000
100000
20ec60 330092
Nember of tuntis coduliioa
Namber of lund or enduciona
Norbo offerter wodaaiors
Number of bector wvllutioo
(gn 30
15ng 70
Contamn indooot 00030
100003 200000 200030 400002 200
23020 40300
63030
80302
31001 10001 cheen 50002 Numser seceete extlation
sarve dress 18900 Narber evilaaioe
Narber
Tuneman and wolastins
Norbbrr offeect mvll
Figure 4: Best valued observed far in terms of number of function evaluations over ten runs on each problem with 10.1 standard deviation in transparent. Title of the plots: problem name- dimension.
[43] (EA) and Greedy Hill-Climbnng [27] (GHC). We point out that Bayesian optimization algorithms omitted from the benchmark due to their heavy computational cost sample the next evaluation points, as detailed in Appendix F where the computational cost of each methods are provided. Moreover, all the details regarding baselines, test problems, code and additional plots can be found in Appendix F. The algorithms are compared on six problems described below. For each problem, record the best value max (sr,) observed each iteration 1 I t n ten runs with various dimensionalities d when possible and an evaluation budget set to n = 100 x d2 following [18]. Figure 4 displays the results for two dimensions on each problem.
Low autocorrelation binary sequences (LABS) [17]. Obtaining binary sequences possessing a high merit factor constitutes grand combinatorial challenge with practical applications in radar engineering and measurements [41, 42]. Given a binary sequence of length d, the merit factor is proportional to the reciprocal of the sequence's 's autocorrelation. The problem consists of searching over the sequence space to yield the maximum merit factor. This hard, non- non-linear problem has been studied over several decades and still carries open questions concerning its mathematical nature [35, 40). We ran our algorithms to find the maximum merit factor in various dimensions. As it can be seen, OCTS outperforms all the baselines (see, Figure 4, LABS 30-70). More importantly, OCTS is able to identify sequences with merit factors that none of the other methods could identify.
Concatenated trap [17]. Concatenated trap is an extension of the LABS problem which consists of partitioning binary sequence of length df into segments length and concatenating m = d/k trap functions that takes each segment input. Following [17], considered the trap function (z) if contains & ones and (k- 1 dh (z, 6x)) otherwise with k 5. This is a highly non-trivial optimization problem. Again, OCTS consistently outperforms all competitors and is able to find sequences with values that no other algorithm was able reach.
Maximum independent set (MIS) [17]. The MIS problem is the task of finding the largest inde- pendent set in graph, where an independent set is set of vertices such that no two vertices are adjacent. This problem has applications network analysis [22] and signal transmission [47], is known to be NP-hard [32]. We compared the algorithms on standard problem instances provided in [5] by maximizing the associated objective of [18]. Here, OCTS is able to identify the best function values in par with other algorithms. However, it is interesting to note that most algorithms perform similarly to RS when d = 30, indicating that the problem presents few structure that can be exploited by the different techniques.
MaxSAT [39]. The satisfiability (SAT) problem is an important combinatorial optimization problem, where one decides how to set variables of a Boolean formula to make the formula true. Many other optimization problems can be reformulated as SAT/MaxSAT problems. Although specialized solvers exist [3], we followed [39] and used MaxSAT as a testbed by running the algorithms on three benchmarks from the MaxSAT Competition 2018 On these problems, OCTS successfully obtains the best score and is able to identify an optimum that no other baseline could find (i.e. MaxSat 28).

---

Ising model [17]. The Ising spin glass model arose in solid-state physics and statistical mechanics, aiming to describe simple interactions within many-particle systems. The classical Ising model considers a set of d spins directing up down placed on regular lattice, where each edge is associated with an interaction strength. The configuration's 's energy is described by the system's Hamiltonian, as quadratic function of those spins variables. The optimization problem is the study of the minimal energy configurations. This is a challenging combinatorial problem, which is known to be NP-hard and holds connections with other NP problems [33]. Again, as it can be seen, the OCTS consistently finds the best configurations in par with SA and is the fastest algorithm.
Contamination [39]. The contamination control in food supply chain is binary optimization problem with 25 binary variables [28], where one can intervene each stage of the supply chain to quarantine uncontaminated food with cost. The goal is to minimize food contamination while minimizing the prevention cost. We followed the setup of [39] with values of = 0.01, 0.0001 and we observe that OCTS is able to identify novel optimum.
These results show that OCTS consistently outperforms existing methods on a wide range of different problems. More importantly, it also shows that using the novel tree search method allows to discover novel optima that could not previously be reached by existing methods (e.g.. LABS, Concatenated).
7 Conclusion and Extensions
In this work, we introduced novel combinatorial black-box solvers that rely on tree search. Ideas for future extensions include: (1) designing budget dependent node selection strategies, (2) using a different Lipschitz constant on each dimension and (3) extending the approach to mixed continuous- combinatorial, noisy, contraint and parallel settings.
References
[1] Haitham Ammar, Victor Gabillon, Rasul Tutunov, and Michal Valko. Derivative-free & order- robust optimisation. In International Conference on Artificial Intelligence and Statistics, pages 2293 2303. PMLR, 2020.
[2] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed handit problem. Machine learning, 47(2):235-256, 2002.
[3] Fahiem Bacchus, Jeremias Berg, Matti Järvisalo, and Rubens Martins. Maxsat evaluation 2020: Solver and benchmark descriptions. 2020.
[4] Thomas Back. Evolutionary algorithmss in theory and practice: evolution strategies, evolution- ary programming, genetic algorithms. Oxford university press, 1996.
[5] Thomas Back and Sami Khuri. An evolutionary heuristic for the maximum independent set problem. In Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, pages 531-535. JEEE, 1994.
[6] Ricardo Baptista and Matthias Poloczek. Bayesian optimization of combinatorial structures. In International Conference on Machine Learning, pages 462-471. PMLR, 2018
[7] Ricardo Baptista, Youssef Marzouk, Karen Willcox, and Benjamin Peherstorfer. Optimal approximations of coupling in multidisciplinary models. AIAA journal, 56(6):2412-2428. 2018.
[8] Peter L Bartlett, Victor Gabillon, and Michal Valko. A simple parameter-free and adaptive approach to optimization under a minimal local smoothness assumption. In Algorithmic Learning Theory, pages 184-206, PMLR, 2019.
[9] Christian Blum and Andrea Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM computing surveys (CSUR), 35(3):2683300 -0088 2003.
[10] Clément Bouttier, Tommaso Cesari, and Sébastien Gerchinovitz. Regret analysis of the piyavskii- shubert algorithm for global lipschitz optimization. arXiv preprint arXi::2002.023390 2020.
[11] Pieare-Arnaud Coquelin and Rémi Munos. Bandit algorithms for tree search, arXiv preprint cs/0703062, 2007.
10

---

[12] Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
[13] Alexander Imani Cowen-Rivers, Wenlong Lyu, Zhi Wang, Rasul Tutunov, Jianye Hao, Jun Wang, and Haitham Bou-Ammar. HEBO: heteroscedastic evolutionary bayesian optimisation. CoRR, 2020.
[14] Hamid Dadkhahi, Jesus Rios, Karthikeyan Shanmugam, and Payel Das. Fourier representations for black-box optimization over categorical variables. 2020.
[15] Carola Doerr, Hao Wang, Furong Ye. Sander van Rijn, and Thomas Bäck. Iohprofiler: A benchmarking and profiling tool for iterative optimization heuristics, arXiv e-primts:/810.052886 October 2018. URL. https::/ichhrofllllce..
github.io.
[16] Carola Doerr, Furong Ye, Sander van Rijn, Hao Wang, and Thomas Bäck. Towards a theory- guided benchmarking suite for discrete black box optimization heuristics: profiling (I+ A) ea variants on onemax and leadingones. In Proceedings of the Genetic and Evolutionary Compulation Conference, pages 951-955 2018.
[17] Carola Doerr, Furong Ye, Naama Horesh, Hao Wang, Ofer M. Shir, and Thomas Bäck. Bench- marking discrete optimization heuristics with iohprofiler. Applied Soft Computing, 88, 2020.
[18] Carola Doerr, Furong Ye, Naama Horesh, Hao Wang. Ofer M Shir, and Thomas Bäck. Bench- marking discrete optimization heuristics with iohprofiler. Applied Soft Computing, 88: 106027, 2020.
[19] Peter Frazier. tutorial on bayesian optimization. arXiv preprint arXiv: | 110711807//11111 1, 2018.
[20] Josselin Garnier, Leila Kallel, and Mare Schoenauer. Rigorous hitting times for binary mutations. Evolutionary Computation, 7(2):173-200 1999.
[21] David E Goldberg and John Henry Holland. Genetic algorithms and machine learning. 1988.
[22] M Goldberg, D Hollinger, and Malik Magdon-Ismail Experimental evaluation of the greedy and random algorithms for finding independent sets in random graphs. International Workshop on Experimental and Efficient Algorithms, pages 513-523. Springer, 2005.
[23] Lean-Bastien Grill, Michal Valko, and Rémi Munos. Black-box optimization of noisy functions with unknown smoothness. Advances in Neural Information Processing Systems, 28:667-675. 2015.
[24] Jean-Bastien Grill, Michal Valko, and Remi Munos. Optimistic optimization of a brownian. Advances Neural Information Processing Systems, 31:3005-3014 2018
[25] Antoine Grosnit, Cedric Malherbe, Rasul Tutunov, Xingehen Wan, Jun Wang, and Haitham Bou Ammar. Boils: Bayesian optimisation for logic synthesis. Design Automation and Test in Europe (DATE), 2021.
[26] Antoine Grosnit, Rasul Tutunov, Alexandre Max Maraval, Ryan-Rhy Griffiths, Alexander I Cowen-Rivers, Lin Yang, Lin Zhu, Wenlong Lyu, Zhitang Chen, Jun Wang, et al. High- dimensional bayesian optimisation with variational autoencoders and deep metric learning. arXiv preprint (0Niv::206603600000 2021.
[27] Robert C Holte. Combinatorial auctions, knapsack problems, and hill-climbing search. In Conference of the canadian society for computational studies of intelligence, pages 57-66. Springer, 2001.
[28] Yingjie Hu, JianQiang Hu, Yifan Xu, Fengchun Wang, and Rong Zeng Cao. Contamination control food supply chain. In Proceedings of the 2010 Winter Simulation Conference, pages IEEE, 2010.
[29] Frank Hutter. Automated configuration algorithms for solving hard computational problems. PhD thesis, University British Columbia, 2009.
[30] Donald R Jones, Cary Perttunen, and Bruce Stuckman. Lipschitzian optimization without the lipschitz constant. Journal of optimization Theory and Applications, 79(1):157-181, 1993.
11

---

[31] Oliver Kramer. Genetic algorithms. In Genetic algorithm essentials, pages 1 11-19. Springer, 2017.
[32] Yu Liu, Jiaheng Lu, Hua Yang, Xiaokui Xiao, Zhewei Wei, et al. Towards maximum independent sets massive graphs. Proceedings of the VLDB Endowment, 2015.
[33] Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, page 5, 2014.
[34] Cédric Malherbe and Nicolas Vayatis. Global optimization of lipschitz. functions. In Interna- tional Conference on Machine Learning, pages 2314-2323, PMLR, 2017.
[35] Burkhard Militzer, Michele Zamparelli, and Dieter Beule. Evolutionary search for low auto- correlated binary sequences. IEEE Transactions on Evolutionary Computation, 2(1):34-39, 1998.
[36] Rémi Munos. Optimistic optimization of deterministic function without the knowledge of its smoothness. Advances in neural information processing systems, 24:783-791, 2011.
[37] Rémi Munos. From bandits to monte-carlo tree search: The optimistic principle applied to optimization and planning. Foundations and Trends@ in Machine Learning, 7(1):1-129, 2014.
[38] Frank Neumann and Ingo Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science,
2007.
[39] Changyong Oh, Jakub M Tomezak, Efstratios Gavves, and Max Welling. Combinatorial bayesian optimization using the graph cartesian product. arXiv preprint arXiv:1902.000 00448, 2019.
[40] Tom Packebusch and Stephan Mertens. Low autocorrelation binary sequences. Journal of Physics A: Mathematical and Theoretical, 49(16):16500,, 2016.
[41] IA Pasha, PS Moharir, and N Sudarshan Rao. Bi-alphabetic pulse compression radar signal design. Sadhana, 25(5):481 1884488188811- 2000.
[42] Irwin I Shapiro, Gordon H Pettengill, Michael E Ash, Melvin L Stone, William B Smith, Richard Ingalls, and Richard A Brockelman. Fourth test of general relativity: preliminary results. Physical Review Letters, 20(22): 1968.
[43] Ofer M Shir, Carola Doerr, and Thomas Bäck. Compiling benchmarking test-suite for combinatorial black-box optimization: position paper. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1753-1760, 2018.
[44] Andrew N Sloss and Steven Gustafson. 2019 evolutionary algorithms review. Genetic Program- ming Theory and Practice XVII, page 307, 2020.
[45] William M Spears. Simulated anncaling for hard satisfiability problems. Cliques, Coloring, and Satisfiability, 26:533-558. 1993.
[46] Michal Valko, Alexandra Carpentier, and Rémi Munos. Stochastic simultaneous optimistic optimization. In International Conference on Machine Learning, pages 19-27. PMLR, 2013.
[47] Peng-Jun Wan, Xiaohua Jia, Guojun Dai, Hongwei Du, and Ophir Frieder. Fast and simple approximation algorithms for maximum weighted independent set of links. In IEEE INFOCOM 2014-IEEF Conference on Computer Communications, pages 1653-1661. IEEE, 2014.
[48] Xingchen Wan, Vu Nguyen, Huong Ha, Binxin Ru, Cong Lu, and Michael A Osborne. Think global and act local: Bayesian optimisation over high-dimensional categorical and mixed search spaces. arXiv preprint arXiv:2102.07188. 2021.
[49] Yuting Zhang, Kihyuk Sohn, Ruben Villegas, Gang Pan, and Honglak Lee. Improving object detection with deep convolutional networks via bayesian optimization and structured prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 249-258, 2015.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Appendix
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Appendix
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vHpY-aULDH7", "reviewer": "Reviewer_S1XN", "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. ", "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.\n* 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.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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\").", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VVyfDbYztk5", "reviewer": "Reviewer_Luwu", "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. ", "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. \n\n1) 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?\n\n2) Why is Bayesian optimization not compared as a baseline? \n\n3) 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). \n\n4) 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. \n\n5) 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?\n\n\n", "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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1) 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. \n\n2) The problem of combinatorial black-box optimization is an important problem that has vast applicability of various domains, including machine learning. \n\n3) 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). \n\n4) 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. \n\n\nWeakness:\n1) 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.\n\nFor 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. \n\nAs 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. \n\n2) 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. \n\n3) 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.\n\n4) 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. \n\nMinor aspects: \n1) The introduction well motivates the paper, but is a bit too condensed. Perhaps better to split it into multiple paragraphs. \n2) Line 186: I_h seems to be a typo, it should be I_l\n3) Line 270: Proposition A.3 -- is it a typo?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SXqhojOaJPB", "reviewer": "Reviewer_3NSu", "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.", "questions": "These are only presentation issues, but they nevertheless should be addressed.\n\n1. 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.\n\n2. 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.\n\n3. 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.\n\n4. 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.\n\n5. 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.\n\n6. 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.\n\n7. 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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nMost of my comments below are regarding presentation, which should be fixable. Assuming those are addressed, I recommend acceptance for this paper.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PJ672Qkdxk", "reviewer": "Reviewer_n1bW", "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. ", "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). ", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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).\n\nThe theoretical results are straightforward, but nevertheless useful. \n\nThe binary tree is assumed as provided, but I would assume that the ordering of the indices might have significant influence on the performance.    \n\nGiven 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.   \n\nThe 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. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept