Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel
Authors: Changyong Oh
Roberto Bondesan
Efstratios Gavves
Max Welling
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bayesian Optimization
Batch Acquisition
Permutation
Bandit
Regret Analysis
Information Gain
Determinantal Point Processes

Abstract: In this work we propose a batch Bayesian optimization method for combinatorial problems on permutations, which is well suited for expensive-to-evaluate objectives. We first introduce LAW, an efficient batch acquisition method based on determinantal point processes using the acquisition weighted kernel. Relying on multiple parallel evaluations, LAW enables accelerated search on combinatorial spaces. We then apply the framework to permutation problems, which have so far received little attention in the Bayesian Optimization literature, despite their practical importance. We call this method LAW2ORDER. On the theoretical front, we prove that LAW2ORDER has vanishing simple regret by showing that the batch cumulative regret is sublinear. Empirically, we assess the method on several standard combinatorial problems involving permutations such as quadratic assignment, flowshop scheduling and the traveling salesman, as well as on a structure learning task.

Batch Bayesian Optimization on Permutations using the Acquisition Weighted Kernel
Changyong Oh QUvA lab, IvI University of Amsterdam changyong. www2248gmail.ccoommmmoo
Roberto Bondesan Qualcomm AI Research" rbondesa@qti. qual comm. com
Efstratios Gavves QUvA lab, IvI University of Amsterdam egavves@uva. nl
Max Welling QUvA lab, IvI University of Amsterdam m. welling@uva.re nl
Abstract
In this work we propose a batch Bayesian optimization method for combinatorial problems on permutations, which is well suited for sepensive-to-evauuaee objec- tives. We first introduce LAW, an efficient batch acquisition method based on determinantal point processes using the acquisition weighted kernel. Relying on multiple parallel evaluations, LAW enables accelerated search on combinatorial spaces. We then apply the framework far received little attention in the Bayesian Optimization literature. despite their practical importance. We call this method LAW2ORDER. On the theoretical front, we prove that LAW2ORDER has vanishing simple regret by showing that the batch cumulative regret sublinear. Empirically, we assess the method on several stan- dard combinatorial problems involving permutations such quadratic assignment, flowshop scheduling and the traveling salesman, as well as on structure learning task.
permutation problems, which have
Introduction
From the celebrated traveling salesman problem[GPOG to flowshop and jobshop scheduling problems GJS76), permutations are ubiquitous representations in combinatorial optimization. Such combinatorial problems permutations arise in highly impactful application areas. For exam- ple, chip design, permutations specify relative placements of memories and logical gates on chip[AMS08) As another example, in 3D printing, scheduling is important factor to determine the production time CHHV1& GSE 19, SFZ 20). In both cases, as well as in many others, evaluating the cost associated given permutation is expensive.
In situations where the evaluation expensive, Bayesian optimization (BO) has shown good perfor- SLA12 mance in many pSoble SRS++1 15) Recently, BO combinatorial spaces has made signifi- cant progress for categorical variables [BP18] DBDF20 [TGWT9 SRDM20 DSR+ 20). However,
BO permutations is yet under-explored with few exceptions (ZSBB14 ZYLWI9 BBG 20).
In this work we present framework deal with BO on permutations where the evaluation of the objective is expensive. We extend batch Bayesian optimization, which allows one to speed up the optimization by acquiring batch of multiple points and evaluating the batch in parallel[AFFI] GDHL16), to the case of permutations. Then, motivated by the observation that both the diversity of
"Qualcomm AI Research is initiative of Qualcomm Technologies, Inc.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

the points in the batches and the informativeness of the individual points in the batch improve the performance [PLI9), we propose a new batch acquisition method which is applicable the search space of permutations and takes into account both the diversity of the batch and the informativeness of each point. This method is based on determinantal point processes (DPPs), which have been widely used to model sets of diverse points KT12), and can be conveniently incorporated into the Gaussian Process framework since DPPs are specified by a kernel. To overcome the lack of informativeness of DDP<(KDKIG (more specifically, the selection of points in batches relies solely on the predictive variance of the surrogate model), we enhance DPPs by using a kernel weighted by acquisition values. Therefore, we propose a new batch acquisition method using the so-called DPP L- ensemble (BsembleeBBR5] KT12) augmented with the Acquisition Weight, dubbed LAW. The whole procedure to find the optimal ordering (permutation) through LAW is thus dubbed LAW2ORDER. We compare LAW2ORDER and other competitors, firstly, on three combinatorial optimization benchmarks on permutations such quadratic assignment problem, the flowshop scheduling problem, and the traveling salesman problem. We also make comparisons on the structure learning problem. In the structure learing problem, LAW2ORDER performs the best and the performance gap is more significant for larger permutation spaces. Moreover, LAW2ORDER still outperforms significantly genetic algorithms which use twice as many evaluations.
2 Preliminaries
In this section, we briefly discuss some prerequisites for our proposed method and introduce notation. Below we will denote a function f with one input as f()., and function K with two inputs as K K(--). For B E N. [B] = {1.... BB while for a set X, X is the number of elements in X.
2.1 Batch Bayesian Optimization
Bayesian Optimization (BO) aims at finding the global optimum of a black-box function f over search space X, namely, Xopt argminxexx [x). Two main components are the probabilistic modeling of the objective (x) and the acquisition of new points to evaluate. Probabilistic modeling is performed by the surrogate model. At the t-th round, the surrogate model attempts approximate f(x) based on the evaluation data D._1, producing the predictive mean [x-1(x) = 5( (D=1)) and
the predictive variance (x) = a² (D.-)). )). In the acquisition of a new point, the acquisition function ar (x) aseg (x
(f)))))))))))) is specified, which is based on the predictive mean (--1(-) and the predictive variance (-) to score how informative points are for the optimization. Next, the point that maximizes the acquisition function is obtained, X = argmaxx a (x), and the objective evaluated, Ve = fxx).. Then, the new evaluation point is appended to the old dataset, D. = D (x(,, } and the process repeats by fitting the surrogate model with Dz. The process continues until the evaluation budget is depleted. To contrast with the proposed method, we call this basic BO as sequential BO. For more extensive overview of Bayesian optimization, please refer to ISSW+15 Fra18).
With more computational resources, such as more GPUs and CPUs, we can speed up Bayesian opti- mization by allowing multiple evaluations in parallel. For this, we acquire a batch of multiple points, a method known as Batch Bayesian Optimization (BBO) (AFFLO, GDHL16). In BBO, we need an acquisition function abatch scoring the quality of batches of B points (xobeel2) instead of individual points. At time I, a batch of B points is acquired [x = argmax axgmax(xx))enn (x))sejR) de((xo, Joe (2)). where ar (xx>))]))) = Obatch (fxb (e( be oi)(())). Then the points in the acquired batch are evaluated in parallel and the evaluation data updated by D. = D:-1 U((xx) v1,b) (be()))
2.2 Determinantal Point Processes
Determinantal point processes (DPPs) are stochastic point processes well-suited to model sets of diverse Points(KT]2] Let us assume that we want sample a set of diverse points from a finite set X. One way to define DPP is to use the so-called (enneemll|[TT] For a given kernel L(- on X, the L-ensemble is defined the random point process with density PPPP(XT where X C X and [L(x, yxx is a submatrix of restricted to X[BRO5).
det([L(xxy))l det(I+L)
For a batch of just two points, X = {x.y) it is easy to observe that DPP encourages diversity ((,,((x))) x L(x, x) - y) Indeed, for more similar points the value of L (x,y) y) is higher, resulting in lower density. In DPPs there is no cardinality constraint on X. We,
2

---

therefore, define k- k-DPP, which is a DPP with the restriction that sampled sets have precisely & points. Denoting the set of subsets of X with k points by Xx the k-DPP density is defined for X E Xx by PL-DPP(X)
Ex'ex, deu[ Therefore, X = argmaxxex* PE-DPP(X) is the most diverse set of k points with respect to the similarity encoded by the kernel L(.,).
det([/xx.)llvvex)
In algorithm, greedily maximized with approximation Caarantees/NNFFE Sak20 (See Supp.Subsec, F. for brief discussion).
that log of k-DPP density is submodular SKKS099 KT12 and can be
3 Method
Batch acquisition combinatorial space poses two difficulties. First, the batch acquisition objectives of existing batch Bayesian optimization are designed based on the properties and intuition applicable to continuous spaces[GDHLLE GPL19]. This may not always be suitable for discrete spaces. For instance, the method in [GHL 16 is defined by using Euclidean distance. Also, the difficulties of combinatorial optimization exacerbated when optimizing batch jointly. This is in stark contrast to the continuous case where gradient based optimization is easily extended to batch optimization of multiple points in paralle/[CCLPP
To cope with these challenges, we introduce new batch acquisition method for Bayesian optimization, the maximization of the determinantal point process (DPP) density defined by an L-ensemble with Acquisition Weights, dubbed LAW. We describe LAW in Subsec. 3.1 and its regret analysis is provided in Subsec. 3.2 and 3.3
3.1 Batch Acquisitionn using LAW
We start to define the main components of LAW.
Definition 3.1 (Weight function). We call function w R IR weight function if positive (r R, w(r)= > 0), increasing (r1 S 72 = w(r1) S w(r2)), and bounded below and above by positive number (w_ inffeR w(r) and W4 supres w(r) < 20).
Definition 3.2 (Posterior covariance function). Given (prior) kernel K(x,, X2). data D and noise variance o², the posterior (predictive) covariance function (xist(Xi, X2 D, a defined as xxx,,x)) - (x1, (D(, + o (D,xx))
Let us assume that we are running batch Bayesian optimization with Gaussian process surro- gate model using the kernel -(..)) and the acquisition function a(-), and that we acquire batch of B points in each round. At the t-th round, we have the evaluation data D,-1, the posterior covariance function K((-.))- Kpost( (-. Dr-1, 2 and the acquisition function
a.( ((())))e(()) = al (xx) be(B) ( ()), (f_,(-)) where (4-1(-) and of)(()) are the predicitve mean and the predictive variance conditioned on D,-1-
In the existing work on batch Bayesian optimization using DPP1KDKI6), the posterior covariance function is used as the kernel defining DPP. Even though the use of DPP in/KDK16 encourages diversity among points in batches, it essentially chooses points of high predictive variance.
However, the predictive mean also provides valuable information in Bayesian optimization. It the acquisition function which harmonizes the predictive mean and the predictive variance quantify how useful each point is. Therefore, we propose new batch acquisition method which actively uses the acquisition function while retaining the strength of DPP encouraging diversity in each batch.
We define the Acquisition Weighted kernel L LAW as follows
J,AW (x1, x2) = w=(((x)) I(x1, x2) w(((x2)).
Here w is positive weight function. We call the kernel L in LAW the diversity gauge of LAW
With the posterior covariance function as the diversity gauge L = K₁ and the acquisition function ag, the acquisition weighted kernel becomes
LA LAW (x), X2) = wr (xx(x))) K2(Xi, x2) (xa))xx))
(1)
Due to the dependency of = K, and a, to the round index t, we subscript L AW and L with t.
We optimize the density of DPP using the acquisition weighted kernel to choose the points in the batch. Before introducing how this optimization is actually performed, we provide an interpretation by rewriting the numerator of the density of the DDDPP defined by LAW
3

---

Algorithm Batch Acquisition by LAW
Input: weight fuunction w(-), diversity gauge ((: acquisition function a(-), batch size B
2: Output: batch of B points {x,,, Xx,B)
X1,1 = argmax a(x) argmaxxex w(a w(a(x))
4: for b = 2. do
5: Xt,6 argmaxx (o,. (x..x
6: end for
dct AW (x,, (5k, ())) det([K, x, x,)) s(()) II (x;())
This shows that the maximization of eq. det([L,(x, xy) {)))) and I (x,))x))) in a balanced way. Increasing the determinant term and increasing the product term promote diversity and acquisition values, respectively.
be obtained by increasing both
Now, we provide details how the optimization is implemented. In combinatorial spaces where the optimization of a single point is challenging, the joint optimization of multiple points is daunting. Thanks to the submodularity of the log of the (eterminant(KT12 the joint optimization of multiple points can be approximated by sequence of single point optimizations with an approximation guarantee (See Subpe.S F.I for submodularity).
The first point is obtained as in sequential Bayesian optimization by optimizing an acquisition function (line 3 in Alg. [ The rest of the B points obtained by maximizing the k-DPP density defined by the acquisition weighted kernel, which we approximately perform with a greedy method (line 4 in Alg. Db. Having chosen b points (xx,))ve(6-1)) 1I. the greedy maximization selects X₂ as follows:
X6 argmax log det (T,, (,, (x))))x))))))) = argmax log [x x (xx,))se(00)) w (x())))))2) xEX
xEx
where (x x (x,, is the posterior variance of the kernel Le conditioned on (xe
3.2 Regret Analysis
In this subsection, we provide a theoretical analysis on the performance of LAW with two acquisition functions, GP- (P-UBC(SKKSO9) and EST[WZJ16)
We begin with definitions needed in the analysis.
Definition 3.3. In the minimization of using batch acquisition, where xt' argmin f(x), Ti,b
((xx,)) is called instantaneous regret and (B) minse[B Ti, = minsera (x(xxx)) (xx))) called batch instantaneous regret. Simple regret is defined the minimum of batch instantaneous regrets (B))
ST
min
Ti
(B) min min Tt.6
t=1,
t=1.-
I be(B
Batch cumulative regret ( is defined as the sum of batch instantaneous regrets
T
T
R
(
(B)
min Tt.b-
Remark 3.4. Note that s
<
1 (B) Vanishing simple regret proved by showing 7 R(( - 0. T
Definition 3.5. For Gaussian processes with the kernel K and the variance of observation noise o². the maximum information gain 7r is defined as
TT = (T;,KXX
K,o²) = max X
log det deg 2KXX
(5)
For UCB and EST, have the following regret bound.
Theorem 3.6. Assume kernel such that K(,,)) 1, | and J X R is sampled from GP K). , In each round E [T] of batch Bayesian optimizution, LAW acquires a butch using the evaluation data D,-1. the diversity measure Lı(:,)) K((,)) (D,1), an acquisition function ac(-)
and a weight function w(-) (Def. (.II.
Let C₁ 1o
36 where o² is the variance of the observation noise and 8 E (0. 1).

---

(BBUCBB
(1X))"((( and Dt min (==(())-m the x(-1,1(x)
At round t, define Pi,
=2log
where my
66
1/2
the estimate of the optimum AWZJTOY, Ge 2 2
(+)
Re > 0 such that >i=1 Tt S
Then batch cumulative regret satisfies the following bound
RT
(B)
1
B W+
B
21-8
T
w-
TB
where for EST, (B) U2- + Se and for UBC, Mh Proof. See. Supp. Sec.
2
LBBBCBBBB1
and t = argmax Us-
sE(t.
Remark 3.7. This theorem shows that, for the same kernel, the regret bound of LAW also enjoys the same asymptotic behavior as the regret bound of existing works CBRVI3 DKB14 KDK16).
Remark 3.8. Note that Thm. i. about a bound on + Riy while the analysis in KKSPIS
KKSP18
is to bound TB AT, where RT,B = Ee,, Tt,b- Since + B) S TB RT bounding TB lT,B
implies bounding #2 For the purpose of showing vanishing simple regret, both approaches are viable. Technically, two approaches require different treatments. See Supp. Subsec. AA2 for the discussion on the differences between two approaches.
Remark 3.9. The ratio "t in Thm. detttrrnnss how LAW balances between the quality and the
diversity. If the ratio is large, then the acquisition value is more influential in Eq. [ Otherwise, Eq. 2 is dominated by the determinant of the diversity gauge, and the diversity of the batch is more emphasized. The bound in Eq. reveals the necessity of the upper bound of == Without w- the upper bound, i.e. virtually considering the acquisition value only, the batch acquisition may result in non-vanishing regret. However, the bound is not tight enough considering the extreme case u=+ = 1. Nonetheless, the necessity of the upper bound of 1+ guides how the weight function w(.) w-
w- is set (See for details). Moreover, the benefit of considering the acquisition weight is supported by the experimental results (Sec.
(B). (B) OOo/oog(TB) (See Supp.Subsec. A.3 for details). In Thm. 3.6 we need 7/T Note that 7/
TB + 0 prove vanishing simple regret. We provide bound for the maximum information gain Yr of kernel on a finite space, which we use later to show the vanishing simple regret.
Theorem 3.10. K is a kernel on a fintt set X ()X < 20), 0² the variance of the observation noise and A = Then
(An 2 An+1 2 0) is the set of eigenvalues of the gram matrix K ((X, X)..
1 Tr S min log det(1 o max K(a, x)), log(1 + -2 "Amaz T)}
2
#eX
where Xmaz is the largest eigenvalue of ((XxX).
Proof. See. Subsec B.I
3.3 Position Kernel
Based the comparative experiments in 7SBB 14] showing that the Position kernel outperforms others consistently 2
we use the position kernel in our BBO on permutations
K(m,, #2)7) exp
- - -1) (0))-
The positive definiteness of the position kernel was empirically tested via simulation (SBB14) and has not been shown rigorously. Therefore, we show the positive definiteness of the position kernel and bound its eigenvalues.
Theorem 3.11. The position kernel K())-T)) defined on Sy is positive definite and the eigenvalues of K(X, X) where X C X lie between
1+P) and
L+e T-P)
where p exp(-r).
Proof. See Supp.Subsec.
B.2
"We also compared different kernels on regression tasks, including Kendall, Mallow [VV55) Hamming. Manhattan, Position (ZSBB14) and Neural Kernel Network (NKN) iSzW using mentioned kernels as building blocks. The position kernel and NKN performs similarly the best. NKN uses the position kernel as a building block kernel which is attributed to the position kernel in the performance of NKN.
5

---

By utilizing the property of the position kernel, we provide bound on the maximal information gain which is tighter than the one obtained in Thm. 3.10
Theorem 3.12. -I- is the position kernel defined on SN, o² is the variance of the observation noise, p - exp(-xp and, D Dmaz= = (N² (N mod 22)
Then
Pr 2 min (A(T), X| log(1 + o AmaxT]}
where Amaz is the largest eigenvalue of (X X') and
A(T) = log((1 + + (T 1)p0max )) (T- log + to 20 -pmmr))
which is smaller than T log(1 -2 maxxex k)x,)))
Proof. See Supp.Subsec. B.3
Remark 3.1.. When P E (0, is close to one, i.e. log(1 1 + 00 (1-21--00 D = O, we can observe that even in the time regime, the regret is almost sublinear since it is dominated by log(1 + o (1 + (T - 1)p Pmax) )). In this case, the theorem provides a bound which is significantly tighter than the bound in Thm. even in the finite-time regime.
Remark 3.14. If Amaz is bounded, Thm. 3.10 can show the vanishing simple regret. For kernel K on a finite space X', Amas < ttraee K (() < oc. Therefore, YT = Ollog(T)) for any kernel. However, considering the magnitude of X and Amaa for large spaces, Eq. Es quite loose. Amez in Eq. Zeflects kernel- dernel-dependent behavior of rr- Therefore, in Thm. (312 we bound Amaz for specific kernel and analyze further pernelddpendentt
asyymtotmiiic behavior.
The regret bounds of LAW most informative in the asymptotic regime of large T. However, in Bayesian optimization where, typically, only a small number of evaluations can be afforded, the asymptotic bound may not be informative in terms of practical performance. In Sec. | we show that, in practice, LAW significantly outperforms other methods.
Related work
Most existing batch Bayesian optimization methods using Gaussian process surrogate models fo- cus on continuous search spaces. Many of them are not applicable to combinatoral spaces be- cause the algorithms use specific properties of Euclidean spaces, e.g, Euclidean distance [AFFIO
GDHL16 WF16 WZJ16, 16 LYY+ 18), grid partitioning [WLJK77 WGKJ18), projection
using Euclidean geometry WCLF20). The methods [SG15] KKSPI8 GPL19 using Thompson sampling (TS) [Th333, 20] random feature [RR+07 07] or entropy search [HS12 HLHG14
require either closed-form expression of eigenfunctions or Choleksy decomposition of the gram matrix on all points in the search space. In general, a closed-form expression of eigenfunctions (RBF) not available. For large combinatorial spaces, Choleksy decomposition is infeasible. LAW is batch acquisition method applicable to general spaces including permutation spaces.
Recently, BO on combinatorial spaces has made significant progress for categorical variables (BP18) DBDF20 OTGWI9 SRDM20, DSR 20). However, relatively few works in Bayesian optimization have focused on permutations ZSBB14 ZYLW19 BBG NGG+20) 20). While existing works focus on the effect of the kernel on performance, our focus is to scale up Bayesian optimization on permutations via batch acquisition, which has not been studied previous works.
The application of determinantal point processes (DPPs) to Bayesian optimization is not new. The of DPP and the regret analysis continuous search spaces [ (KDK 16) is closely related to our work. We focus on optimization problems on permutations rather than continuous spaces and use acquisition weighted kernels in our DPP. We provide regret bound, which includes the unweighted case as a special case. Moreover, we show the behavior of the information gain of the position kernel, which, in turn, helps to understand the behavior of BO on permutations.
The idea of using weighted kernels was investigated DPP [TTIO KT12), also recently in the context of active learning [BWAS19] and more recently in architecture search [NLYA02I]. In addition to the use of the acquisition weights, we provide a regret analysis and the bound on the information gain of the position kernel for BO on permutations.
In existing works on regret analysis of batch Bayesian optimization, the cumulative regret analyzed as end goal DDBB 14] and as a medium to show vanishing simple regret On the other

---

hand, we analyze the batch cumulative regret not the cumulative regret (see Def. 3.3 and remarks thereafter). The batch cumulative regret is analyzed in [CBRVT3] but without the acquisition weight. More detailed discussion on the difference among all these analyses is provided in Supp.Subsec, A.2
5 Experiments
We empirically demonstrate the benefit of LAW many optimization problems permutations
In all Gaussian process (GP) based BO including baselines, we use the position kernel (see. Sub- sec. 3.3p. At each round, evaluation outputs are normalized. GP surrogate models are trained with output normalized evaluation data by optimizing the marginal likelihood until convergence with 10 different random initializations. We use the Adam optimizer[KBB [B]]] with default PyTorch[PGCe 17 settings except for the learning rate of 0.1.
When the optimization is performed on a single permutation variable, for example in greedy optimiza- tion, hill climbing is used until convergence and the neighbors are defined as the set of permutations obtainable by swapping two locations.
5.1
Weight function
The motivation of the acquisition weight promote the quality of the queries in the batch by using acquisition weights. In order to refeect this motivation, the weight function should be monotonically increasing. The better the quality (acquisition value) is, the larger the batch acquisition objective is.
In Eq the batch acquisition objective is factorized into the DPP with the diversity gauge and the product of weights, thus the weight function should be positive to prevent the product of an even number of large negative values becomes a large positive value. Also, in Eq. [ zero weight value nullifies the diversity component, thus the weights function required to be nonzero.
In Thm. 3.6 for vanishing regret, the ratio "'L should be upper-bounded. Not only it facilitates the proof, but the upper bound is also intuitively appealing because we do not want to overly emphasize the quality of the queries. We want to balance quality and diversity. Weight functions with an unbounded ratio may erase the diversity consideration.
w-
Combining the rationale behind LAW and its regret analysis, we set the weight function to be, monotonically increasing, positive valued, bounded below, bounded above.
5.2 Combinatorial Optimization Benchmarks
We consider LAW with two acquisition functions EST (ZJ16) and UI LAW-EST and LAW-EI. Even though the regret bound of LAW-ETIs IS not provided in Thm. 3.6 we include LAW-EI because EI is the most popular acquisition function and this reveals the effect of the acquisition weights with different acquisition functions. We use the sigmoid w(a) = 0.01 + 0.99(1 + exp(- 0.2 a))
for LAW-EST and w(a) 0.01 for LAW-EI
The baselines are q-EI, q-EST BUCB ESTIKDK16 6 and MACE-UCB, MACE-ESTILYY+IS
DPP-MAX-EST. DPP-SAMPLE- Even though the original names of the baselines are used to emphasize their batch acquisition strategy, all baselines use the position kernel. Hence, the batch acquisition strategy is the only differentiating factor among baselines and LoW(orrs). Note that DPP-MAX-EST [DK16 corresponds to LAW-EST with w(-) = const., i.c., no acquisition weight.
'The code is available at httptttss///tthhie wwt. Boom/ChangYong Ob/LAW2ORDER *The 8e in UCB balaneing between exploitation and exploration increases as the size of the search space increases in the finite search space case[SKKS09). In the experiments, due to the size of the search space, GP-UCB virtually becomes the predictive variance. Thus we exclude LAW-UCB.
'LAW-ET is included to check the influence of different acquisition functions despite the lack of regret analysis. Therefore, the weight function chosen to prevent zero values from numerical truncation.
'PE(CHRVI3] is equivalent to DPP-MAX-UCB [DK16]. Since on continuous problems DPP-MAX-EST outperforms DPP-MAX- ----MAAX-UBBDBBEE
exclude PE.
'The MACE requires multi-objective optimization on permutations. We use NSGA DPAMO2 in (D20) MACE-UCA UCB uses the original set of acquisition functions: PI, El and UCB LYY 18 while MACE-EST replaces UCB with EST.
7

---

BUCB
DPP-MAX-SST
SPA-MAX-
MACE-UCB
NACE-EST
REST
LAW-EI
LAW-EST
FD 10
420
022
270
011
444
400
111
M12
210-
MBC
10.3
305-
165
301-
340-
202-
23
2000
Benchmarks
QAP-chriZa
QAP
QAP-esc32a
PSP-car3
heP
PSP-xeC19
ISP-bumal4
ESP-bayg29
TSP-an48
Batch
5
10
10
10
BUCB
18105 1 955
7857 1 (2)
1134 1 (8)
DPP-MAX-EST
14752
23
276.5
142.5
2262
7.7
3786
50
39539
487
DPP EST
19970
1: (9) 4416
319.6
3.8
7973
151
0.58
2410-
6.1.8)
1: 52 3853
29
40893
1: 26526660 (8)
MACE-UCB
13440
1: 348 (5) 4031
1 26
(6)
250.3
(5)
10(1
143
4.42
1252
2 5,8(5)
- 21
+ (6)
+ 50
25773
371 (4)
MACE-EST
14126
4: 506
4086
20
285.6
3.1
7791
95
4.
2282
3576 = 25 = 5.9.7)
2940
32711
212.6)
12769
457
172.1
7763
141
2231
2065
36 (0472
502
eEST
11790 + 498
(1) 3690
121.2
(.)
7782
(
141.0
49
2242
(4)
: 75
2060
48
(2)
21199
:: 620
LAW
11914 1 345 (2) 3724
(3) 192.5
5.3
7794
8
141.2
2
U.
45
(3)
E 4.5
E 26
2487
47 (4) 20864
1: (39
LAW-EST
238
140.7
4.2(1)
9846
Some numbers ure reported with less number of evalunsion. Please refer the figure above.
Table 1: Permutations Benchmarks (Mean + Str.EEr.(Rank over 15 runs)
Note that, due to the reasons discussed in Sec. A existing works based on Thompson sampling or the properties of Euclidean space are excluded from the baselines.
We consider three types of combinatorial optimization on permutations, Quadratic Assignment Problems(QAP), Flowshop Scheduling Problems(FSP) and Traveling Salesman Problems(TSP) (See Supp.Subsec. F.3 for data source).
For each benchmark, all methods share 5 randomly generated initial evaluation data sets of 20 points and for each initial evaluation data set, each method is run three times - 15 runs in total.
DPP-MAX-EST uses the position kernel as LAW-EST, this is equivalent to LAW-EST without the acquisition weight, i.c. w(a) 1. By comparing LAW-EST with DPP-MAX-EST, we can directly evaluate the benefits of using the acquisition weight.
As shown in Tab. 5.2, LAW-EI, LAW-EST, q-EI and q-EST are in top four except for FSP-car5 and TSP- attta. LAW-EST performs the best on FSP and TSP while q-EI or q-EST perform the best on QAP. Along with the experiment on the structure learning (Subsec. 5.3 we conjecture that QAP has a certain structure more friendly to q-EI and Q-EST. Also LAW-EI exhibits comparable performance with q-EI and ESE while outperforming other baselines, which supports the benefit of the acquisition weight. In terms of the average rank over all benchmarks, LAW-EST performs the best with the average rank of 1.89 against E-EST (2.44) and E-EI (2.78). Overall, among the baselines, LAW-EST exhibits stable and competitive performance across different benchmarks.
5.2.1 Comparison to the local penalization (LP)
Two additional variants of LAW, LAW-PRIOR-EST and LAW-PRIOR-FI, are also com- pared (Supp. Sec. G which use the prior covariance function as the diversity gauge, = K, of LAW These variants do not use evaluation data in the diversity gauge.
8

---

GA
QEI
QEST
LSW
0400
0700
1010
0000
1700
BN(#Node)
Sachs(11)
Childr2)
(nsurance(27)
Alarmi 37)
Sec. 10 eval.
60 m 80
120 140
130 170
200 220
Method
#Eval
C'= 76100
C 124000
C
135000
117000
GA
620 (C 53.46) = 4.99
C
1387.12) = 79.26
[C 603
= 406.92
[C
4826. 19) = 370.55
GA
1240 (C + 31.90) = 5.86
C
1368.07) + 92.26
[C
+ 2814.04) 414.18.00 49
[C C 4114.97) + 449.93
4-13
620 (C 55.96) 1. 10.11
(C
864.85) 1 0.16
[C 433,23)
1. 357.15
(C
2969.00) 1: 518.67
9-RST
620 (C + 70.67)
+ 16.31
C
028.83)
+ 32.97
(C + 1215.75)
+ 556.36
[C + 2739.77] (7) + 534.12
LAW-EST
620 29.58)
6.36
CC 866.64) + 0.39
[C 33.95)
174.04
1409. (7009.2))2 + 227.57
Table 2: Negative log NMI minimization for the structure learning (Mean + Std. over 5 runs)
Interestingly, LAW-PRIOR-EST and LAW-PRIOR-EI resemble LP(GDHLI6) (Supp. Sec. and thus this allows an indirect comparison to LP which is not applicable to combinatorial spaces
These variants using the prior covariance function performs worse than LAW using the posterior covariance function, which is natural since using more data for the diversity gauge enhances the performance. More importantly, --W--RIOR- and LAW-PRIOR -EI outperform DPP-MAX- EST which uses the posterior covariance function without the acquisition weight, which supports that the acquisition weight is key in the performance improvement.
Based on the empirical analysis above, we choose LAW-EST as our final recommendation, which we call LAW2ORDER.
5.3 Structure Learning
We apply LAW2ORDER to the score-based structure learning (DM77 Existing score-based methods assume a computationally amenable structure of the score to be opti- mized (decomposability) (FFO9 SGGI9). Distinctively our approach does not necessitate the decom- posability of the score to be optimized.
We consider the NML score below
(8) where PBN (-1 G, 9, is the density of Bayesian Network (BN) with DAG and the parameter 0, and REGNALL is the normalized marginal likelihood (NML) which is complexity measure from the minimum description length Aanciple/GGOy) NML is not decomposable, and thus the methods assuming a decomposable score are not applicable. Since is infeasible to compute NML exactly and we resort on MC estimate, the NMI. score evaluation is noisy. In addition to not being decomposable, noisy evaluation also makes existing methods inapplicable to the NML score objective. For more details of NML and its MC estimate, see Supp.Sec. [E]
SNML(G, D) = - PBN (DI G, dLL + REGNNL (D)
Similarly to (SWU17 RUI8 we search over permutations specifying topological order of DAGs and the existence of edges is determined by the conditional independence test. In addition to q- EI and Q-EST performing well on the benchmarks, we compare LAW2ORDER with the genetic algorithm (GA), which is one of the most popular choices for optimization problems on permutations including [SP(Po
We generated 5 sets of 20 random initial points. LAW2ORDER, q- q-EI and E-EST is run each of these 5 sets using a batch size 20. Assuming the same resource constraint (at most 20 evaluations in parallel), GA generates 20 off-springs in each generation. GA is also run 5 times with a population The first 20 points of each initial population in the 5 runs
size of 100 points using Pymoo are equal to the 20 initial points used in LAW2ORDER, q-EI and QEEST. Even though the real deployment of Bayesian optimization assumes that the cost of evaluation is expensive enough to render the time acquire new batches negligible, as stress test, allowed twice the evaluation budget for GA.
'LAW variants use the kernel of the GP surrogate model as the diversity gauge which is more guided by data while LP uses the local penalizer which is heuristically designed. We expect that this distinction will still make a difference the performance.

---

On data generated from 4 real-world [S SGGI91, the results are reported in Tab. 2 LAW2ORDER outperforms q-EI and q-EST with significant margin except for Child where all three find the putative optimum quickly. Still, in Child, LAW2ORDER finds point of negligible differences with the putative optimum the most quickly. Also, except for Sachs, we observe that the performance gap increases as the permutation size (the size of the search space) increases. On this realistic problem, our argument that LAW2ORDER is stable and efficient batch acquisition method on permutations is reinforced.
In comparison with GA, we consider GA(620) with the same evaluation budget and GA(1240) with twice large evaluation budget. LAW2ORDER dominates GA(620) in all problems with significant margin. Even compared with GA(1240), LAW2ORDER significantly outperforms except for Sachs which has one of the smallest search spaces (See Tab, and Supp. Sec.(G). Contrary to our expectation that BO has the sample efficiency higher than GA, GA(620) outperforms q-EI and q-EST on Sachs. LAW2ORDER shows robust performance even in the problem where the performance of q-EI and q-EST is degraded.
Together with the experiments on the benchmarks, LAW2ORDER is shown to be robust batch acquisition method on permutations. Moreover, promoting the diversity in batches while taking into account the acquisition weight appears more beneficial with larger batch size (20) as shown in the structure learning experiment.
6 Conclusion
In this paper we have focused on combinatorial optimization problems over permutations where each evaluation is assumed to be expensive. This class of problems has many interesting applications, ranging from chip design (where we wish to place cells while minimizing area and wire-length), warehouse optimization (where we need to order the retrieval of items from warehouse using robot), neural architecture search and so on. In spite of its practical significance, BO on permutations is under-explored in contrast to the recent progress on combinatorial BO with categorical variables.
In response to this, we have proposed batch Bayesian optimization algorithm on permutations, LAW2ORDER, which uses an extension of the determinantal point processes with the acquisition weighted kernel. This allows the search process over the surrogate function to make optimal use of all parallel available computational resources and be guided by both the expected objective value and its posterior uncertainty.
On the theory side we offer a regret analysis, which shows that the regret bound of LAW enjoys the same asymptotic behavior existing methods. On the empirical side, we show that LAW variants consistently exhibit competitive performance on a wide range of combinatorial optimization tasks, including a challenging structure learning problem.
From these we conclude that the acquisition weights are indeed a key factor in the success of the proposed method, and that the performance gains increase for large batch sizes.
LAW is applicable to general search spaces for which kernel can be defined. We leave the exploration of our method to applications outside searching over permutations for future work.
6.1 Limitations
LAW achieves improved sample efficiency in the sense that the quality of batches from LAW is maintained for large batch sizes. However, due to the sequential nature of the greedy maximization of LAW objective, its computational complexity is linear with respect to the batch size. Especially for large permutation spaces, this may be a nonnegligible cost. We hope that the sample efficiency of LAW is complemented by the computational efficiency allowing massive parallelization.
Even though the regret bound in Thm. 3.6jdsscribes the effect of the acquisition weight, as mentioned in Rmk. 3.9. it only sheds light on the demerit of excessive emphasis on the acquisition weights but it does not detect the demerit of considering the diversity only. We hope our work inspires the regret bound for acquisition methods taking into account properties other than diversity.
10

---

References
[AFFI0] Javad Azimi, Alan Fern, and Xiaoli Fern. Batch bayesian optimization via simulation matching. In Advances in Neural Information Processing Systems, pages 109-117. Citeseer, 2010.
[AGRI6] Nima Anari, Shayan Oveis Gharan, and Alireza Rezaci. Monte carlo markov chain al- gorithms for sampling strongly rayleigh distributions and determinantal point processes. In Conference on Learning Theory, pages 103-115. PMLR, 2016.
[AMS08]
C.J. Alpert, D.P. Mehta, and S.S. Sapatnekar. Handbook of Algorithms for Physical Design Automation. CRC Press, 2008
[BGG 20] François Bachoc, Baptiste Broto, Fabrice Gamboa, Jean-Michel Loubes, et al. Gaussian field on the symmetric group: Prediction and learning. Electronic Journal of Statistics, 14(1 (4(1):503-546 2020.
[BBKT17] Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of sun-uuumo functions with applications. In International conference on machine learning, pages 498-501 PMLR, 2017.
[BD20] Julian Blank and Kalyanmoy Deb. pymoo: Multi-objective optimization in python. IEEE Access, 8:89497-85509, 2020.
[BP18] Ricardo Baptista and Matthias Poloczek. Bayesian optimization of combinatorial
structures. In International Conference Machine Learning, pages 462-471. PMLR, 2018.
[BRO5] Alexei Borodin and Eric M Rains. Eynard-mehta theorem, schur process, and their pfaffian analogs. Journal of statistical physics, 121(3):291-311 2005.
[BWAS19] Erdem Bryik, Kenneth Wang, Nima Anari, and Dorsa Sadigh. Batch active learning using determinantal point processes. arXiv preprint arXiv:1906.07977 2019.
[Car78] Jacques Carlier. Ordonnancements a contraintes disjonctives. RAIRO-Operations Research, 12(4:3333-350, 1978.
[CB89] Nicos Christofides and Enrique Benavent. An exact algorithm for the quadratic assign- ment problem on tree. Operations Research, 37(5):760-768, 1989.
[CBRV13] Emile Contal, David Buffoni, Alexandre Robiequet, and Nicolas Vayatis. Parallel gaussian process optimization with upper confidence bound and pure exploration. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 25-2400.r Springer, 2013.
[CCD15] Eunice Yuh-Jie Chen, Arthur Choi, and Adnan Darwiche. Learning bayesian networks with non-decomposable scores. In International Workshop on Graph Structures for Knowledge Representation and Reasoning, pages 50-71. Springer, 2015.
[CHHVI8] Akram Chergui, Khaled Hadj- Hamou,, and Frédéric Vignat. Production scheduling and nesting in additive manufacturing. Computers & Industrial Engineering, 126:292-301, 2018.
[Chi02] David Maxwell Chickering. Optimal structure identification with greedy search. Journal of machine learning research, 3(Nov):507-554 2002.
[DBDF20] Aryan Deshwal, Syrine Belakaria, Janardhan Rao Doppa, and Alan Fern. Optimizing discrete spaces via expensive evaluations: A learning to search framework. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3773-3780. 2020.
[DKB14] Thomas Desautels, Andreas Krause, and Joel W Burdick. Parallelizing exploration- exploitation tradeoffs in gaussian process bandit optimization. Journal of Machine Learning Research, 15:3873-3923, 2014.

---

[DM17] Mathias Drton and Marloes H Maathuis. Structure learning in graphical modeling. Anmual Review of Statisties and Its Application, 4:365-393, 2017.
[DPAM02] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: Nsga-ii. IEEE transactions on evolutionary computation, 6(2):182 197, 2002.
[DSR 20] Hamid Dadkhahi, Karthikeyan Shanmugam, Jesus Rios, Payel Das. Samuel C Hoffman, Troy David Loeffler, and Subramanian Sankaranarayanan. Combinatorial black-box optimization with expert advice. In Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1918-1927, 2020.
[EW90] Bernhard Eschermann and Hans-Joachim Wunderlich. Optimized synthesis of self- testable finite state machines. 1990.
[MMV1]] Uriel Feige, Vahab S Mirrokni, and Jan Vondrák. Maximizing non-monotone submodu- lar functions. SIAM Journal on Computing, 40<4):1133-1153, 2011.
[Fra18] Peter Frazier. A tutorial on bayesian optimization. arXiv preprint arXiv: 2018.
[Fuj05] Satoru Fujishige. Submodular functions and optimization. Elsevier, 2005.
[GDHL16] Javier González, Zhenwen Dai, Philipp Hennig, and Neil Lawrence. Batch bayesian optimization via local penalization. In Artificial intelligence and statistics, pages 648-657. PMLR, 2016.
[GG07] Peter D Grünwald and Abhijit Grunwald. The minimum description length principle. MIT press, 2007.
[GJS76] Michael R Garey, David S Johnson, and Ravi Sethi. The complexity of flowshop and jobshop scheduling. Mathematics of operations research, 17-2197, 1976.
[GLRC08] David Ginsbourger, Rodolphe Le Riche, and Laurent Carraro. A multi-points criterion for deterministic parallel global optimization based on gaussian processes. 2008.
[GP06] Gregory Gutin and Abraham P Punnen. The traveling salesman problem and its variations, volume 12. Springer Science & Business Media, 2006.
[GPL19] Chengyue Gong, Jian Peng, and Qiang Liu. Quantile stein variational gradient descent for batch bayesian optimization. In International Conference on Machine Learning, pages 2347-2356. PMLR, 2019.
[GR19] Peter Grünwald and Teemu Roos. Minimum description length revisited. International journal of mathematics for industry, 11(01):193001, 2019.
[GS58] Ulf Grenander and Gabor Szegö. Toeplitz forms and their applications. Univ of California Press, 1958.
[GSE 19] Valeriya Griffiths,, James Scanlan, Murat H Eres, Antonio Martinez-Sykora, and Phani Chinchapatnam. Cost-driven build orientation and bin packing of parts in selective laser melting (slm). European Journal of Operational Research, 273(1):334-355 2019.
[Hel60] Jack Heller. Some numerical experiments for an mx j flow shop and its decision- theoretical aspects. Operations Research, 8(2):178-184 1960.
[LHHG14] José Miguel Hernández-Lobatee Matthew W Hoffman, and Zoubin Ghahramani. Predic- tive entropy search for efficient global optimization of black-box functions. Advances in neural information processing systems, 27, 2014.
[HS12] Philipp Hennig and Christian Schuler. Entropy search for information-efficien global optimization. Journal of Machine Learning Research, 13(6), 2012.
12

---

[JSW98] Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(4):455-492. 1998.
[JV15] Yunlong Jiao and Jean-Philippe Vert. The kendall and mallows kernels for permutations. In International Conference on Machine Learning, pages 1935-1944. PMLR, 2015.
[KB57] Tjalling C Koopmans and Martin Beckmann. Assignment problems and the location of economic activities. Econometrica: journal of the Econometric Society, pages 53-76, 1957.
[KB14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:/412.6980, 2014.
[KDK16] Tarun Kathuria, Amit Deshpande, and Pushmeet Kohli. Batched gaussian process bandit optimization via determinantal point processes. Advances in Neural Information Processing Systems, 29:4206-4214 4214,44244227. 2016.
[KF09] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[KKSP18] Kirthevasan Kandasamy, Akshay Krishnamurthy, Jeff Schneider, and Barnabás Póczos. Parallelised bayesian optimisation via thompson sampling. In International Conference on Artificial Intelligence and Statistics, pages 133- 142. PMLR, 2018
[KM07] Petri Kontkanen and Petri Myllymäki. linear- time algorithm for computing the multinomial stochastic complexity. Information Processing Letters, 103(6):227-233, 2007.
[KSG08] Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008
[KT10] Alex Kulesza and Ben Taskar. Structured determinantal point processes. Advances in neural information processing systems, 23:1171-1179, 2010.
[KT12] Alex Kulesza and Ben Taskar. Determinantal point processes for machine learning. Machine Learning, ((2-3))123-2886 2012.
[Lov83] László Lovász. Submodular functions and convexity. In Mathematical programming the state of the art, pages 235-257. Springer, 1983.
[LS20] Tor Lattimore and Csaba Szepesvári. Bandit algorithums. Cambridge University Press, 2020.
[LYY 18] Wenlong Lyu, Fan Yang, Changhao Yan, Dian Zhou, and Xuan Zeng. Batch bayesian optimization via multi-objective acquisition ensemble for automated analog circuit design. In International conference on machine learning, pages 3306-3314 3314. PMLR, 2018.
[MM07] Tommi Mononen and Petri Myllymäki. Fast nml computation for naive bayes models. In International Conference on Discovery Science, pages 151-160. Springer, 2007.
INLYA021] Vu Nguyen, Tam Le, Makoto Yamada, and Michael A Osborne. Optimal transport ker- nels for sequential and parallel neural architecture search. In International Conference on Machine Learning. PMLR, 2021.
[NVR68] Christopher E Nugent, Thomas E Vollmann, and John Ruml. An experimental compar- ison of techniques for the assignment of facilities to locations. Operations research. 16(1):150-173, 1968.
[NWF78] George I. Nemhauser, Laurence A Wolsey, and Marshall I, Fisher. An analysis of ap- proximations for maximizing submodular set functions Mathematical programming. 14(1):265-22 1978.
13

---

[9TGW19]
Changyong Oh, Jakub Tomezak, Efstratios Gavves, and Max Welling, Combinatorial bayesian optimization using the graph cartesian product. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bue E. Fox, and R. Garnett, editors, Advances in Newral Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[PGC-17 17] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
[Pot96] Jean-Yves Potvin. Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63(3):337-370, 1996.
[Ree95] Colin Reeves. A genetic algorithm for flowshop sequencing. Computers & operations research, 22(1):5-13, 1995.
[RR 07] Ali Rahimi, Benjamin Recht, et al. Random features for acage-scale kernel machines. In NIPS, volume 3, page Citeseer, 2007.
[RSKM08] Teemu Roos, Tomi Silander, Petri Kontkanen, and Petri Myllymaki. Bayesian network structure learning using factorized nml universal models. In 2008 Information Theory and Applications Workshop, pages 272-276. IEEE, 2008
[RU18] Garvesh Raskutti and Caroline Uhler. Learning directed acyclic graph models based on sparsest permutations. Stat, 7(1)xe183, 2018.
[Sak20] Shinsaku Sakaue. Guarantees of stochastic greedy algorithms for non- non-monotone sub- modular maximization with cardinality constraint. In International Conference Artificial Intelligence and Statistics, pages 11-21. PMLR, 2020.
[Scul0] Marco Scutari. Learning bayesian networks with the bnlearn r package. Journal of Statistical Software, 2010.
[0] Xu Song, Stefanie Feih, Wei Zhai, Chen-Nan Sun, Feng Li, Raj Maiti, Jun Wei, Yangzhan Yang, Victor Oancea, Leon Romano Brandt, al. Advances in additive manufacturing process simulation: Residual stresses and distortion predictions in complex metallic components. Materials & Design, 193:108779, 2020.
[SG15] Amar Shah and Zoubin Ghahramani. Parallel predictive entropy search for batch global optimization of expensive objective functions. In Proceedings of the 28th International Conference on Neural Information Processing Destems-Volunee 2, pages 3330-3338, 2015.
[SGG19] Marco Scutari, Catharina Elisabeth Graafland, and José Manuel Gutiérrez. Who learns better bayesian network structures: Accuracy and speed of structure learning algorithms. International Journal of Approximate Reasoning, 1 115:235-253. 253, 2019.
[SKD15] Dravyansh Sharma, Ashish Kapoor, and Amit Deshpande. On greedy maximization of entropy. In International Conference on Machine Learning, pages 1330-1338, PMLR, 2015.
[SKKS09] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.39995. 2009.
[SLA12] Jasper Snoek, Hugo Larochelle, and Ryan Prescott Adams. Practical bayesian opti- mization of machine learning algorithms. Advances in Neural Information Processing
Systems, 2012.
[SLAJR18] Tomi Silander. Janne Leppä-Aho, Elias Jääsaari, and Teemu Roos. Quotient normalized maximum likelihood criterion for learning bayesian network structures. In International Conference Artificial Intelligence and Statistics, pages 948-957. PMLR, 2018.
[SRDM20] Kevin Swersky, Yulia Rubanova, David Dohan, and Kevin Murphy. Amortized bayesian optimization over discrete spaces. In Conference on Uncertainty in Artificial Intelli- gence, pages 769-778. PMLR, 2020.
14

---

[SRS 15] Jasper Snoek, Oren Rippel, Kevin Swersky, Ryan Kiros, Nadathur Satish, Narayanan Sundaram, Mostofa Patwary, Mr Prabhat, and Ryan Adams. Scalable bayesian opti- mization using deep neural networks. In International conference machine learning. pages 2171-2180. PMLR, 2015.
[SSSI9] Mauro Scanagatta, Antonio Salmerón, and Fabio Stella. A survey on bayesian network structure learning from data. Progress in Artificial Intelligence, 8(4):425-439, 2019.
[SSW 15] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148-175, 2015.
[SWU17] Liam Solus, Yuhao Wang, and Caroline Uhler. Consistency guarantees for greedy permutation-based causal inference algorithms. arXiv preprini arXiv:1702.033: 2017.
[SZW] 18] Shengyang Sun. Guodong Zhang, Chaoqi Wang, Wenyuan Zeng, Jiaman Li, and Roger Grosse. Differentiable compositional kernel learning for gaussian processes, In International Conference on Machine Learning, pages 4828-4837. PMLR, 2018.
[Tho33] William R Thompson. On the likelihood that one unknown probability exceeds another in view the evidence of two samples. Biometrika, 25(3/4):285-29) 294, 1933.
[Tre99] William Trench. Asymptotic distribution of the spectra of class of generalized kac-murdock-szeggi matrices. Linear algebra and its applications, 294(1-3):111-192, 1999.
[WBT 20] James Wilson, Viacheslav Borovitskiy, Alexander Terenin, Peter Mostowsky, and Marc Deisenroth. Efficiently sampling functions from gaussian process posteriors, In International Conference on Machine Learning, pages 11292-10302. PMLR, 2020.
[WCLF20] Jialei Wang, Scott C Clark, Eric Liu, and Peter I Frazier. Parallel bayesian global optimization of expensive functions. Operations Research, 68(6): 1800:185508666 2020.
[WF16] Jian Wu and Peter I Frazier. The parallel knowledge gradient method for batch bayesian optimization. In Proceedings of the 30th International Conference Neural Informa- tion Processing Systems, pages 1144- 2016.
[WGKI18] Zi Wang, Clement Gehring. Pushmeet Kohli, and Stefanie Jegelka. Batched large-scale scale bayesian optimization in high- nigh-dimensional spaces. In International Conference on Artificial Intelligence and Statistics, pages 745-754. PMLR, 2018
[Wik20] Wikipedia contributors. Flow shop scheduling Wikipedia, the free encyclopedia, 2020. [Online; accessed 3-February-20211
[WLJK17] Zi Wang, Chengtao Li, Stefanie Jegelka, and Pushmeet Kohli, Batched high-dimensional bayesian optimization via structural kernel learning. In International Conference Machine Learning, pages 3656-3664. PMLR, 2017.
[WZJ16] Zi Wang, Bolei Zhou, and Stefanie Jegelka. Optimization as estimation with gaussian processes in bandit settings. In Artificial Intelligence and Statistics, pages 1022-1031.
PMLR, 2016.
[ZSBB14] Martin Zaefferer, Jörg Stork, and Thomas Bartz-Beielstein. Distance measures for permutations in combinatorial efficient global optimization. In International Conference on Parallel Problem Solving from Nature, pages 373-383. Springer, 2014.
[YLW199] Jianming Zhang, Xifan Yao, Min Liu, and Yan Wang. A bayesian discrete optimization algorithm for permutation based combinatorial problems. In 2019 JEEE Symposium Series on Computational Intelligence (SSCI), pages 874-881 IEEE, 2019.
15

---

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]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(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? Supp-Sec. Supp.Sec.AASupp.Seee Supp..Se..
[Yes]
Sec.
(b) Did you include complete proofs of all theoretical results? Supp.Sec. SJSupp.Sec.
[Yes]
Sec.
3. If you ran 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] Sec. S
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Sec. 5 Supp.Sec.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] Sec. Supp.Sec.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
Supp-Sec. F
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [Yes]
(c) 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 participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "x4XrnSdc3ft", "reviewer": "Reviewer_9inD", "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.", "questions": "Apart from my comments in the Weaknesses section that the authors can response, I have the following questions:\n\n1.\tIs the Acquisition Weighted kernel a valid kernel? Could you also give rigorous explanation for your answer?\n2.\tAre the lambda_{max} values in Theorems 3.9 and 3.12 upper bounded by constants when T goes to infinity?\n", "limitations": "I think the paper does not mention much about the limitations or the societal impacts of their proposed approach.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nWeaknesses: 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.\n\n•\tThe 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).\n\n•\tEven 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.\n\n       o\tThe 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\".\n      o\tThe 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.\n      o\tAgain, same problem with Theorem 3.12, is there any guarantee that the \\lambda_{max} of the position kernel is upper bounded?\n\n•\tThe 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. \n\n•\tBesides, 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.\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": "buE72QrjpdS", "reviewer": "Reviewer_SzBU", "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. \n\nIn 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. \n\nIn 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.\n\nIn 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).", "questions": "- LAW-UCB has not been evaluated experimentally, but how well can it be expected to perform?\n\n- 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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n- 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.\n\n- 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. \n\n- 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.\n\nWeakness\n\n- 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.\n\n- 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.\n\n\n\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": "KALUFVrX-AA", "reviewer": "Reviewer_CuLB", "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.\n", "questions": "How does the computational cost of LAW compare to the baselines?\n", "limitations": "I don't see any potential negative societal impact of this work. The authors did not address limitations of their work.\n", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nI'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.\n\nI don't feel confident in assessing how novel LAW is, or how significant it is in the context of combinatorial bayesian optimisation.", "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": "--96zbxj8lU", "reviewer": "Reviewer_DqJ6", "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.\n", "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? \n\nI 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.\n- No code released.\n", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- Study an important problem of applying batch Bayesian optimization to solve permutation problems.\n- Good theoretical analyses.\n- Comprehensive experimental evaluation.\n- Writing is easy to follow.\n\nWeaknesses:\n\n- No code released.\n- Unclear how to set the weight function.\n\nOriginality:\n\nThe 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.\n\n\nQuality:\n\nThe problem is well defined and the proposed method is complete. The algorithm is not complicated which makes the approach accessible to potentially wide audience.\n\nClarity:\n\nThe writing is clear and easy to follow.\n\nSignificance:\n\nThe paper studies a very important but rarely studied problem in solving permutation problems in batch Bayesian optimization.\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