Fourier Representations for Black-Box Optimization over Categorical Variables
Authors: Hamid Dadkhahi
Jesus Rios
Karthikeyan Shanmugam
Payel Das
Venue:  (2021)

Abstract: Optimization of real-world black-box functions defined over purely categorical variables is an active area of research. In particular, optimization and design of biological sequences with specific functional or structural properties have a profound impact in medicine, materials science, and biotechnology. Standalone acquisition methods, such as simulated annealing (SA) and Monte Carlo tree search (MCTS), are typically used for such optimization problems. In order to improve the performance and sample efficiency of such acquisition methods, we propose to use existing acquisition methods in conjunction with a surrogate model for the black-box evaluations over purely categorical variables. To this end, we present two different representations, a group-theoretic Fourier expansion and an abridged one-hot encoded Boolean Fourier expansion. To learn such models, characters of each representation are considered as experts and their respective coefficients are updated via an exponential weight update rule each time the black box is evaluated. Numerical experiments over synthetic benchmarks as well as real-world RNA sequence optimization and design problems demonstrate the representational power of the proposed methods, which achieve competitive or superior performance compared to state-of-the-art counterparts, while improving the computational cost and/or sample efficiency substantially.

Under review as a conference paper at ICLR 2021
FOURIER REPRESENTATIONS FOR BLACK-BOX OPTIMIZATION OVER CATEGORICAL VARIABLES
Anonymous authors Paper under double-hlind review
ABSTRACT
Optimization of real-world black-box functions defined over purely categorical variables is an active area of research. In particular, optimization and design of biological sequences with specific functional or structural properties have a profound impact in medicine, materials science, and biotechnology. Standalone acquisition methods, such as simulated annealing (SA) and Monte Carlo tree search (MCTS), are typically used for such optimization problems. In order to improve the performance and sample efficiency of such acquisition methods, we propose existing acquisition methods in conjunction with surrogate model for the black-box evaluations over purely categorical variables. To this end, we present different representations, grruup-theorete Fourier expansion and abridged one-hot encoded Boolean Fourier expansion. To learn such models, characters of each representation are considered as experts and their respective coefficients are updated via an exponential weight update rule each time the black box is evaluated. Numerical experiments over synthetic benchmarks as well world RNA sequence optimization and design problems demonstrate the representational power of the proposed methods, which achieve competitive or superior performance compared to state-of-the-ar counterparts, while improving the computational cost and/or sample efficiency substantially.
INTRODUCTION
A plethora of practical optimization problems involve black-box functions, with no simple analytical closed forms, that can be evaluated at any arbitrary point in the domain. Optimization of such black-box functions poses unique challenge due to restrictions on the number of possible function evaluations, as evaluating functions of real-world complex processes is often expensive and time consuming, Efficient algorithms for global optimization of expensive black-box functions take past queries into account in order to select the next query to the black-box function more intelligently. While black-box optimization of real- world functions defined over integer, continuous, and mixed variables has been studied extensively in the literature, limited work has addressed incorporation of purely categorical type input variables.
Categorical type variables are particularly challenging when compared to integer or continuous variables, as they do not have natural ordering. However, many real-world functions are defined over categorical variables. One such problem, which is of wide interest, is the design of optimal chemical or biological (protein, RNA, and DNA) molecule sequences, which are constructed using vocabulary of fixed size, e.g. 4 for DNA/RNA. Designing optimal molecular sequences with improved or novel structures and/or functionalities is paramount importance in material science, drug and vaccine design, synthetic biology and many other applications (see Dixon et al. (2010); Ng et al. (2019): Hoshika et al. (2019); Yamagami et al. (2019)) Design of optimal sequences is difficult black-box optimization problem over combinatorially large search space (Stephens et al. (2015)). in which function evaluations often rely on either wet-lab experiments, physics-inspired simulators, or knowledge-based computational algorithms, which are slow and expensive in practice. Another problem of interest is the constrained design problem, e.g. find sequence given a specific structure (or property), which is inverse of the well-known folding problem discussed in Dill & MacCallum (2012). This problem is complex due to the strict structural constraints imposed on the sequence. In fact one of the ways represent such complex structural constraint is constrain the next choice

---

Let 24 be the f-th sequence evaluated by the black box function f. The key question in both settings is the following: Given prior queries 21, 21,22 .....;.; and their evaluations f(x1)... ((z))...((z))) f(x,), how to choose Under review as a conference paper at ICLR 2021
sequentially based the sequence elements that have been chosen a priori. Therefore, divide the black box optimization problem into two settings, depending on the constraint set: (1) Generic Black Box Optimization (BBO) problem referring to the unconstrained case and (it) Design Problem that refers to the case with complex sequential constraints.
the next query Tz-1? ? This acquisition must be devised so that over a finite budget of black-box evaluations, one is closest to the minimizer in an expected sense over the acquisition randomness.
In the literature, for design problems with sequential constraints, MCTS (Monte Carlo Tree Search) based acquisitions are often used with real function evaluations f(z)). In the generie BBO problems in the unconstrained scenario, Simulated Annealing (SA) based techniques are typically used as acquisition functions. A key missing ingredient in the categorical domain is surrogate model for the black-box evaluations that can interpolate between such evaluations and use cost-free approximate evaluations from the surrogate model internally (in acquisition functions) in order to reduce the need for frequently accessing real evaluations. This leads to improved sample efficiency in acquisition functions. Due to the lack of efficient interpolators in the categorical domains, existing acquisition functions suffer under a finite budget constraint, due to reliance on only real black-box evaluations.
Contributions:
We address the above problem in our work. Our main contributions are follows: 1. We present two representations for modeling real-valued combinatorial functions over categorical variables, which we then use in order to learn a surrogate model for the generic BBO problem and the design problem. The surrogate model is updated via a hedge algorithm where the basis functions our representations act as experts. The latter update happens once for every real black-box evaluation. To the best of our knowledge, the representations and/or their use in black-box optimization of functions over categorical variables are novel to this work.
2. In the BBO problem, the proposed method uses a version of simulated annealing that utilizes the current surrogate model for many internal cost-free evaluations before producing the next black-box query.
3. In the design problem, the proposed method uses version of MCTS in conjunction with the current surrogate model as reward function of the terminal states during intermediate tree traversalsbackkus in order improve the sample efficiency of the search algorithm.
4. Numerical results, synthetic benchmarks well real-world biological (RNA) sequence optimization and design problems demonstrate the competitive or superior performance of the proposed methods over state-of-the-art counterparts, while substantially reducing the computation time and sample efficiency, respectively.
2 RELATED WORK
Hutter et al. (20TT) suggests a surrogate model based on random forests to address optimization problems over categorical variables. The proposed SMAC algorithm uses randomized local search under the expected improvement acquisition criterion order to obtain candidate points for black-box evaluations. |Bergstra al. (2011) suggests tree-structured Parzen estimator (TPE) for approximating the surrogate model, and maximizes the expected improvement criterion to find candidate points for evaluation. For optimization problems over Boolean variables, multilinear polynomials Ricardo Baptista (2018); Dadkhahi et al. (2020) and Walsh functions Leprêtre et al. (2019) have been used in the literature.
Bayesian Optimization (BO) is a commonly used approach for optimization of black-box functions (Shahriari et al. (2015)). However, limited work has addressed incorporation of categorical variables in BO. Early attempts based on converting the black-box optimization problem over categorical variables to that of continuous variables have not been very successful (Gómez- Bombarelli al. (2000). A few BO algorithms
(2018): Goloovin et (201)): Saarido-Merchal & Hernández- have been specifically designed for black-box functions over combinatorial domains. In particular, the BOCS algorithm Ricardo Baptista (2018), primarily devised for Boolean functions, employs sparse monomial representation to model the interactions among different variables, and uses a sparse Bayesian linear regression method to learn the model coefficients. The COMBO algorithm of Oh (et al. (2019) uses Graph Fourier Transform (GFT) over a combinatorial graph, constructed via graph cartesian product of variable subgraphs, gauge the smoothness of the black-box function. However,
2

---

Under review as a conference paper at ICLR 2021
both BOCS and COMBO are hindered by associated high computational complexities, which grow polynomially with both the number of variables and the number of function evaluations.
More recently, computationally efficient black-box optimization algorithm (COMEX) (Dadkhahi ct al. 2020j) was introduced to address the computational impediments of its Bayesian counterparts. COMEX adopts Boolean Fourier representation as its surrogate model, which is updated via an exponential weight update rule. Nevertheless, COMEX limited to functions over the Boolean hypercube. We generalize COMEX handle functions over categorical variables by proposing two representations for modeling functions over categorical variables: an abridged one-hot encoded Boolean Fourier representation and Fourier representation on finite Abelian groups. The utilization of the latter representation as a surrogate model in combinatorial optimization algorithms is novel to this work. Factorizations based on one-hot encoding has been previously (albeit briefly) suggested in Ricardo Baptista (2018) to enable black-box optimization algorithms designed for Boolean variables to address problems over categorical variables. Different from Ricardo Baptista (2018), we show that we can significantly reduce the number of additional variables introduced upon one-hot encoding, and that such a reduced representation is in fact complete and unique.
For design problems, we focus on the RNA sequence design problem (RNA inverse folding). The goal is to find an RNA sequence consistent with a given secondary structure, as the functional state of the RNA molecule is determined by the latter structure (Hofacker et al. (1994)). Earlier RNA design methods explore the search space by trial and error and use classic cost function minimization approaches such adaptive random walk (Hofacker (a0accker((003))) (2003)), probabilistic sampling (Zadeh et al.) (2011)) and genetic algorithms (Tanedal (2015)). )) Recent efforts employ more advanced machine learning methods such different Monte Carlo Tree Search (MCTS) algorithms, e.g. MCTS-RNA (Yang et al. (2017) or Nested MCTS (Portela (2018), and reinforcement learning that either performs a local search as in Eastman et al.] (2018) or learns complete candidate solutions from scratch (Runge et al. (2018)) ). In all these approaches, the assumption is that the algorithm has access to a large number of function evaluations, whereas we are interested in sample efficiency of each algorithm.
As an alternative to parameter free search methods (such as SA). (wwessyy et al. (2020) suggests to use a parameterized policy to generate candidates that maximize the acquisition function in Bayesian optimization over discrete search spaces. Our MCTS acquisition method is similar in concept to Swersky et al. (2020) in the sense that the tabular value functions are constructed and maintained over different time steps. However,
maintaining value functions rather than a policy network.
3 BLACK- Box OPTIMIZATION OVER CATEGORICAL VARIABLES
Problem Setting: Given the combinatorial categorical domain X' = [k]" and a constraint set C C X, with n variables each of cardinality k; the objective is find
r" arg min f1: =EC
(1)
where f '''+> + IR is real-valued combinatorial function. We assume that f is black-box function, which is computationally expensive to evaluate. As such, we are interested in finding x in as few evaluations as possible. We consider two variations of the problem depending on how the constraint set C is specified.
Generic BBO Problem: In this case, the constraint set = X. For example, RNA sequence optimization problem that searches for an RNA sequence with a specific property optimized lies within this category. A score for every RNA sequence, reflecting the property we wish optimize, is evaluated by a black box function.
Design Problem: The constraint set is complex and is only sequentially specified. For every sequence of 2 22 .2... consisting of i characters from the alphabet [k], the choice of the next character Ii+1 E C(x)222... ..,) C [k] specified by a constraint set function C(z) ((x))...,). The RNA inverse folding problem in Runge et al. (2018) falls into this category, where the constraints on the RNA sequence are determined by the scquential choices one makes during the sequence design. The goal is to find the sequence that is optimal with respect to pre-specified structure that also obeys complex sequential constraints.
Our Techniques: In order address this problem, adopt surrogate model-acquising function based learning framework, where estimate for the black-box function f (i.e. the surrogate model)
3

---

Under review as a conference paper at ICLR 2021
is updated sequentially via black-box function evaluations observed until time step t. The selection of candidate points for black-box function evaluation is carried out via an acquisition function, which uses the surrogate model f as an inexpensive proxy (to make many internal calls) for the black-box function and produces the next candidate point be evaluated. The sequence proceeds follows:
Surrogate model updated on f(z)) - Acquisition function makes (many) calls to Surrogate model to propose 2+41 >> Surrogate model updated on (#++1: (x)-1)
In the sequel, we propose two representations that can be used as surrogate models for black-box combinatorial functions over categorical variables. These representations serve as direct generaliza- tions of the Boolean surrogate model based on Fourier expansion proposed in Dadkhahi et al. (2020) in the sense that they reduce to the Fourier representation for real-valued Boolean functions when the cardinality of the categorical variables is two. In addition, both approaches be modified to address the more general case where different variables are of different cardinalities. However, for ease of exposition, we assume that all the variables are of the same cardinality. Finally, we introduce two popular acquisition function to be used in conjunction with the proposed surrogate models in order to propose new queries for subsequent black-box function evaluations.
3.1 REPRESENTATIONS FOR THE SURROGATE MODEL
We present two representations for combinatorial functions : [K]* - R and an algorithm to update from the black-box evaluations. The representations use the Fourier basis in two different ways.
Abridged One-Hot Encoded Boolean Fourier Representation: The one-hot encoding of each variable xy i E [n] can be expressed as a (A- - -ttuee (Ia1, T42..... #T(k=-)), where Tij E {-1,, 1} Boolean variables with the constraint that most such variable can be equal to -1 for any given 2; E [
We consider the following representation for the combinatorial function f:
fa(z) = fa(=)=E>> Σ Σ
(2)
m=o (I!)) 1|
where [k 1 denotes fold cartesian product of the set [k: 1] (1,2....,
1}.
(!))
designates the set of m-subsets of the set [n), and the monomials (II,(()) (x) can be written as
(x) =
II
Fij
[(.j)a (--))==L-JJJ..lll
A second order approximation (i.e. at 2) of the representation in can be expanded in the following way:
[a(x)= or Σ Σ
Σ
Σ
(4)
(E(M) FE[k-1]
(I)))((())) (p-9)E(K-1P
Example. For n. 2 variables and I2, each of which with cardinality k = 3, we have the one-hot encoding of (121) and (I',, x222) respectively. From Equation (4), the one-hot encoding factorization for this example can be written as
f(x) = oz + 01 + 12 + 02 + 04222 + 115 + 06 + 27 + 0g
Note that the representation in Equation (2) has far less terms than vanilla one-hot encoding with all the combinations of one-hot variables included (as suggested in Ricardo Baptistal (2018)). The reason for this reduction is two-fold: (i) (k 1) Boolean variables model each categorical variable of cardinality k. and more importantly (it) each monomial term has at most one Boolean variable Tig from its corresponding parent categorical variable z;. The following theorem states that this reduced representation is in fact unique and complete.
Theorem 3.1. The representation in Equation complete and unique for any real- valued combinatorial function.
4

---

Under review as a conference paper at ICLR 2021
Proof. See Appendix.
Fourier Representation on Finite Abelian Groups: We define a cyclic group structure // 22 over the elements each categorical variable z; [n]), where is the cardinality of the latter variable. From the fundamental theorem of abelian groups Terras (1999), there exists an abelian group G which is isomorphic to the direct sum (a.k.a direct product) of the eyclic groups 2/ 2 corresponding to the categorical variables:
G G 02////
(5)
where the latter group consists of all vectors (a1, .2,...., group isomorphism. We assume that k; = k (vi E [nl) for simplicity, but the following representation could be easily generalized the case of arbitrary cardinalities for different variables.
an) such that a; E Z/ and = denotes
The Fourier representation of any complex-valued function f(x) on the finite abelian group G' is
given by Terras 1999)
f(x) = Σ (T))(x))
(6)
IE(A]"
where or are (in general complex) Fourier coefficients, [k]* is the n-fold cartesian product of the set [k] and (ar) are complex exponentials (k-th roots of unity) given by
y (z) = exp(2r)(e.I1/1))
Note that the latter complex exponentials the characters of the representation, and reduce to the monomials (i.e. in {-1,1]) when the cardinality of each variable two. A second order approximation the representation (6) can be written as:
fa(2) = ao +
Σ
Σ
ass (x)(2))z((
Σ Σ
Oijpy exp (xp(2t)laaptt (7)
iE|m] RE(A-1]
(L)) (p-
For a real-valued function (x) (which is of interest here), the representation in 6 reduces to
fa(x) 3R
Σ
orvir(1))
Σ (,,
Σ (,IV
IE(K
ZE(k)
IE(K
where
(x) cos((2((.21))) and 0r, = R(az) and 05.7 3==33(a) ((T)
(). (1n(2)(+
(9)
(10)
We note that the number of characters utilized in this representation almost twice as many as that of monomials used in the previous representation.
Surrogate Model Learning: We adopt the learning algorithm of combinatorial optimization with expert advice Dadkhahi et al. (2020) in the following way. We consider the monomials d/z, (I)) in (3) and the characters (x)) in (10) as experts. For each surrogate model, we maintain pool of such experts, the coefficients of which are refreshed sequentially via exponential weight update rule. We refer to the proposed algorithm as Expert-Based Categorical Optimization (ECO) and the two versions of the algorithm with the two proposed surrogate models are called ECO-F (based on the One-Hot Encoded Boolean Fourier Representation) and ECO-G (based on Fourier Representation on Finite Abelian Groups), respectively. A summary of the algorithm given in the Appendix.
3.2 ACQUISITION FUNCTIONS
In this subsection, discuss how two popular acquisition functions, namely Simulated Annealing (SA) and Monte Carlo Tree Search (MCTS), work with surrogate model and use cost-free evaluations of the surrogate model to select the next query for the black box evaluation. In the literature, SA has been used for the generic BBO problems whereas MCTS has been used for the design problems.
Note that in the general case of different cardinalities for different variables. I E [Ki] [k2] x... x [kn] where denotes the cartesian product and the exponent denominator in the complex exponential character is replaced by LCM ki, k2,..., kp).

---

Under review as a conference paper at ICLR 2021
SA as Acquisition Function: Our acquisition function is devised so as to minimize fa(x), the current estimate for the surrogate model. A simple strategy to minimize (x) to iteratively switch each variable into the value that minimizes Sa given the values of all the remaining variables, until no more changes occur after sweep through all the variables 2; (Vi E [r]).. A strategy escape local minima in this context Pincus 1970) is to allow for occasional increases in fa by generating a Markov Chain (MC) sample sequence (for æ), whose stationary distribution is proportional to exp(-5.(#)/.) where 8 is gradually reduced to zero. This optimization strategy was first applied by Kirkpatrick et al. (1983) their Simulated Annealing algorithm to solve combinatorial optimization problems. We use the Gibbs sampler Geman & Geman (1944) to generate such a MC by sampling from the full-conditional distribution of the stationary distribution, which in our case is given by the softmax distribution over {-Ja (ar; = f, x xix==///a eE(A]. for each variable x; conditional on the values of the remaining variables z=,. By decreasing s from high value to a low one, we allow the MC to first search at a coarse level avoiding being trapped in local minima.
Algorithm I presents our simulated annealing (SA) version for categorical domains, where s(t) an annealing schedule, which is a on-increasing function of t. We use the annealing schedule suggested in Spears (1993). which follows an exponential decay with parameter & given by s(t) exp(-"/n) In each step of the algorithm, we pick variable x; (i E [n]) uniformly at random, evaluate the surrogate model (possibly parallel) I times, once for each categorical value E [k] for the chosen variable 2, given the current values r-, for the remaining variables. We then update I, with the sampled value in [A:] from the corresponding softmax distribution.
MCTS as Acquisition Function: We formulate the design problem as an undiscounted Markov decision process AS, R). Each state s E S corresponds to a partial or full sequence of categorical variables of lengths in [0, n]. The process in each episode starts with empty sequence so, the initial state. Actions are selected from the set of permissible additions to the current state (sequence) 8; each time step L, A, A(*x) C A. The transition function T is deterministic, and defines the sequence obtained from the juxtaposition of the current state 8, with the action dt, i.c. Si+1 Tss az) = 8t o ag. The transitions leading to incomplete sequences yield a reward of zero. Complete sequences are considered as terminal states, from which no further transitions (juxtapositions) can be made. Once the sequence is complete (i.e. a terminal state), the reward obtained from the current surrogate reward model Fa- Thus, the reward function is defined as R(st, Gt 1t-1) = (s if St+1 is terminal, and zero otherwise.
MCTS is a popular search algorithm used for design problems. MCTS is rollout algorithm which keeps track of the value estimates obtained via Monte Carlo simulations in order to pro- gressively make better selections. The UCT selection criteria, see Kocsis & Szepesvári (2006), is typically used as tree policy, where action a, at state St in the tree search is selected via: r (s:) = arg m(x. ((s2, a) + /n/in N(s.)/((s.. where T is the search tree, is the explo- ration parameter, Q(s, a) is the state-action value estimate, and (ss) and N(s, a) are the visit counts for the parent state node and the candidate state-action edge, respectively. For the selection of actions in states outside the tree search, a random default policy is used: π T (s:) = un.f((A.).
summary of the proposed algorithm is given in Algorithm 2 Starting with an empty sequence so at the root of the tree, we follow the tree policy until leaf node of the search tree is reached (selection step). At this point, we append the state corresponding to the leaf node to the tree and initialize a value function estimate for its children (extension step). From the reached leaf node we follow the default policy until a terminal state is reached. At this point, we plug the sequence corresponding to this terminal state into the surrogate reward model - fa and observe the reward r. This reward is backed up from the leaf node the root of the tree in order to update the value estimates Q(s, a) via Monte Carlo (i.e. using the average reward) for all visited (s, a) pairs along the path. This process is repeated until a stopping criterion (typically a max number of playouts) is met, at which point the sequence Sees with maximum reward Tbest is returned as the output of the algorithm.
6

---

Under review as a conference paper at ICLR 2021
Algorithm 2 MCTS with Surrogate Reward
Algorithm 1 SA for Categorical Variables with Surrogate Model
1: Inputs: surrogate model Far search tree T Initialize Spett - U, Ubest -00
1: Inputs: surrogate model Ja. annealing schedule s(t), categorical domain X
3: repeat
Sleaf t -election(T")
2: Initialize x E 2
5: T < TU (Mlea)
3: t t=0
8, <- Simulation
81est)
4: repeat
7: Y + (s))s)
5: d~ unif((nl)
Backup(sieat,"
6: 2=/x_;
Softmax -
9: if > Toest then
10: Theat + and Spat + St
7:
1-t+1
11: end if
8: until Stopping Criteria
12: until Stopping Criteria
9: return
13: return Sbeat
Computational Complexity:
The computational complexity per time step associated with learning
the surrogate model, for both representations introduced in 3.1 is in O(d) = O(k"mInn")) and thus linear in the number of experts d. Moreover, the complexity of the simulated annealing Okd)), assuming that the number of iterations in each SA run is in (n)). As result, the overall complexity of the algorithm is in (kd)). Finally, the computational complexity of each playout in Algorithm 2 in (K)),,) leading to an overall complexity of (O)k assuming (O/) playouts per time step.
algorithm (Algorithm 1p is in O(kkm=11r"" (("
4 EXPERIMENTS AND RESULTS
In this section, we measure the performance of the proposed representations, when used as sur- rogate/reward model in conjunction with search algorithms (SA and MCTS) in BBO and design problems. The learning rate used in exponential weight updates is selected via the anytime learning rate schedule suggested in Dadkhahi et al. (2020) and Gerchinovitz & Yu (20TT) (see Appendix). The maximum degree of interactions used in our surrogate models is set to two for all the problems; increasing the max order improved the results only marginally. The sparsity parameter À in exponen- tial weight updates is set to 1 in all the experiments following the same choice made in Dadkhahi et al. 2020). Experimentally, the learning algorithm is fairly insensitive to the variations in the latter parameter. In each experiment, we report the results averaged over multiple runs (20 runs in BBO experiments and 10 runs in design experiments) + one standard error the mean. The experiments were on machines with CPU cores from the Intel Xeon E5-2600 v3 family.
We compare the performance our ECO algorithms in conjunction with SA with two baselines, random search (RS) and simulated annealing (SA), well state-of-the of-the-art Bayesian combinatorial optimization algorithm (COMBO) et al. (2019). In particular, we consider two synthetic benchmarks (Latii square problem and pest control problem) and real-word sequence design problem in biology: RNA sequence optimization. In addition to the performance of the algorithms in terms of the best value of fx) observed until given time step t, we measure the average computation time per time step of our algorithm versus that of COMBO, The decay parameter used in the annealing schedule of SA is set & = 3 all the experiments. In addition, the number of SA iterations in our surrogate models is set to T = 3 x n. Intuitively, each of these parameters creates trade-ofi. The smaller (larger) the value of , the more exploratory (exploitative) is the behavior of SA. The selected values seem to create reasonable balance; tuning these parameters may improve the performance of the acquisition function.
BBO Experiments:
an wttloorttioneeploittttti
We consider two synthetic problems: Latin square problem Colbourn & Dinitz (2066), a commonly used combinatorial optimization benchmark, and the pest control problem considered in Oh et al. (2019) (see Appendix for the latter results). In both problems, we have n 25 categorical variables, each of cardinality i = 5. A Latin square order & is & x & matrix of elements Ziy [k). such that each number appears in each and column exactly once. When = 5, the problem of finding a Latin square has 161, 280 solutions in a space of dimensionality 525 We formulate the problem of finding a Latin square of order & black-box optimization by
Synthetic Benchmarks:
7

---

Under review as a conference paper at ICLR 2021
CG2P
100+
-10
17.5
Best (0x)
-18
15.0
-20
12.5
-25
7.5
-30
5.0
100
200
300
420
500
100
250
300
400
503
Time Stup
Time Step
Figure 1: RNA BBO Problem with n = 30
Figure 2: Eterna100 puzzle #41 (n = 35)
imposing an additive penalty of one for any repetition of numbers in any row or column. Hence, function evaluations are in the range [0, 2k(k - 1)], and function evaluation of zero corresponds to a Latin square of order k. We consider a noisy version of this problem, where an additive Gaussian noise with zero mean and standard deviation of 0.1 is added to function evaluations observed by each algorithm. Both ECO-F and ECO-G outperform the baselines with considerable margin. In addition, ECO-G outperforms COMBO until time step f 190. At larger time steps, COMBO outperforms the other algorithms, however, this performance comes at the price of far larger computation time. ECO-F and ECO-G offer a speed-up over COMBO by a factor of roughly 100 and 50, respectively.
RNA Sequence Optimization Problem: Consider an RNA sequence
string A ai a..... an of
letters (nucleotides) over the alphabet = {A, U, G, C}. A pair of complementary nucleotides a; and aj. where (i j), can interact with each other and form a base pair (denoted by (i.j)). A-U, C-G and G-U being the energetically stable pairs. Thus, the secondary structure, i.e. the minimum free energy structure, of an RNA can be represented by an ensemble of pairing bases. A number of RNA folding algorithms Lorenz et al. (201T): Markham & Zuker (2008) use thermodynamic model (e.g. [ukker& & Stiegler (1981) Ih) and dynamic programming estimate MFE of sequence. However, the (nn") time complexity of these algorithms prohibits their use for evaluating substantial numbers of RNA sequences Gould et al. (2014) and exhaustively searching the space to identify the global free energy minimum, as the number of sequences grows exponentially as 4"
We formulate the RNA sequence optimization problem as follows: For sequence of length n, find the RNA sequence which folds into secondary structure with the lowest MFF. In our experiments, we initially set n = 30 and 4. We then use the popular RNAfold package[Lorenz Lorenz et al. (01T to evaluate the MFF for given sequence. The goal is to find the lowest MFE sequence by calling the MFE evaluator minimum number of times. As depicted in Figure [ both ECO-F and particularly ECO-G outperform the baselines as well as COMBO by considerable margin.
The problem to find a primary RNA sequence & which folds into target structure w, given folding algorithm F. Such target structures can be represented as a sequence of dots (for unpaired bases) and brackets (for paired bases). In our algorithm, the action sets are defined as follows. For unpaired sites A, {A, G, C, U} and for paired sites At = {GC, CG, AU, A). At the beginning of each run of our algorithm (ECO-F and ECO-G in conjunction with MCTS acquisition), we draw random permutation for the order of locations to be selected in each level of the tree. The reward value offered by the environment (i.e. the black-box function) any time step & corresponds the normalized Hamming distance between the target structure w and the structure
RNA Design Experiments:
F(x:) of the sequence 2, found by each algorithm, i.e. dı (w, yt).
We compare the performance of our algorithms against RS as a baseline, where random search is carried out over the given structure (i.c. default policy 755 rather than over unstructured random sequences. We also include two state-of-the-arr algorithms in our experiments: MCTS-RNA of Yang et al. 2017) and LEARNA Runge et al. (2019). MCTS-RNA has an exploration parameter, which we tune in advance (per sequence). LEARNA has a set of 14 hyper-parameters tuned a priori using training data and is provided by the authors of Runge et al. (2019). Note that the latter training phase (for LEARNA) as well as the former exploration parameter tuning (for MCTS-RNA, is offered to the respective algorithms an advantage, whereas for our algorithm choices for the two aaper-parameters, rather than attempting to tune the two apper-paramttrr.. In particular, we set the exploration parameter 0.5 and the number of MCTS playouts at each time
global set of heuristic
8

---

Under review as a conference paper at ICLR 2021
step to 30 x h, where h is the height of the tree (i.e. number of dots and bracket pairs). The latter heuristic choice is made since the bigger the tree, the more playouts are needed to explore the space.
We point out that the entire design pipeline in state-of-the-an algorithms typically also includes local improvement step (as post-proe post-procsssing step), which is either a rule-based search (e.g. in Yang et al. (2017) or exhaustive search (e.g. in [Runge et al. (2019)) over the mismatched sites. We do not include the local improvement step in our experiments, since we are interested in measuring sample efficiency of different algorithms. In other words, the question is the following: given fixed and finite evaluation budget, which algorithm is able to get closer to the target structure.
For our experiments, we focus three puzzles from the Eterna- 100 dataset Anderson- Lee al. (2016). Two of the selected puzzles (# 15 and #41 of lengths 30 and 35, resp.). despite their fairly small lengths, are challenging for many algorithms (see Anderson- our algorithms ECO-F and ECO-G (with MCTS acquisition) are able to significantly improve the performance of MCTS when limited number of black-box evaluations is available. All algorithms outperformed RS as expected. Within the given 500 evaluation budget, ECO-G, and especially ECO-F, are superior to LEARNA by a substantial margin (see Appendix). puzzle number 41 (Figure 2) again both ECO-G and ECO-F significantly outperform LEARNA, over the given number of evaluations. Interestingly, ECO-F is able to outperform LEARNA throughout the evaluation process, and in average finds far better final solution than LEARNA. See Appendix for the third puzzle.
al. (2016)) In both puzzles,
5 CONCLUSIONS AND FUTURE WORK
In summary, propose novel Fourier representations surrogate models for black box optimiza- tion over categorical variables and show performance improvements over existing baselines when combined with state-of- oof-the-ar art acquisition methods.
Considering the performance variability of the two surrogate model representations introduced in this paper across different problems, an important research avenue would be to incorporate an ensemble of surrogate models rather than a single one. Such an ensemble model would then update and explore both models simultaneously and draw samples from either individual models or a combination of both at any given time step. It would be interesting to see if such an ensemble model would in fact be able to outperform both individual models over different combinatorial problems.
Our ECO algorithm incorporates an online estimator learnt via Hedge, rather than Bayesian posterior mean function which is commonly used in conjunction with Thompson Sampling (TS) and UCB for uncertainty quantification in Bayesian optimization algorithms. The Hedge algorithm has strong adversarial guarantees (see Dadkhahi et al.. (2020) for theoretical results in the Boolean case), which can be shown carry over to our setting well. More precisely, given any additional black box evaluation, is guaranteed to move closer to the true black-box model. However, the exploration bonus used in the acquisition process via SA, used in our algorithm, can be shown to be domain independent, i.e. sampled i.i.d from the same distribution regardless of the query point. The terms that account for uncertainty in both TS and UCB are domain dependent and depend the query point. As such, domain dependent uncertainty incorporation would be an interesting next step, which is left for future work.
REFERENCES
Jeff Anderson-Lee, Eli Fisker, Vineet Kosaraju, Michelle Wu, Justin Kong, Jeehyung Lee, Minjae Lee, Mathew Zada, Adrien Treuille, and Rhiju Das. Principles for predicting raa secondary structure design difficulty. Journal of Molecular Biology, 428(5, Part A):748 - 757, 2016. Challenges in RNA Structural Modeling and Design.
Frances H Amood. Design by directed evolution. Accounts of chemical research, 1153)1125-131, 1998.
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for Soper-parameter op- timization. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS'1 11, pp. 2546 2554, 2011.

---

Under review as a conference paper at ICLR 2021
Nicholas Bogard, Johannes Linder, Alexander B Rosenberg, and Georg Seelig. A deep neural network for predicting and engineering alternative polyadenylation. Cell, 178(1))11-166 2019.
David H Brookes, Hahnbeom Park, and Jennifer Listgarten. Conditioning by adaptive sampling for robust design. arXiv preprint arXiv:/901. 10060, 2019.
J Ross Buchan and Ian Stansfield. Halting cellular production line: responses to ribosomal pausing during translation. Biology of the Cell, 99(9):475-477, 2007.
Charles J. Colbourn and Jeffrey H. Dinitz, Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications). Chapman & Hall/CRC, 2006.
Hamid Dadkhahi, Karthikeyan Shanmugam, Jesus Rios, Payel Das, Samuel Hoffmman, Troy David Loeffler, and Subramanian Sankaranarayanan. Combinatorial black-box optimization with expert advice. In KDD, 2020.
Matthew Davis, Selena M Sagan, John P Pezacki. David Evans, and Peter Simmonds. Bioinformatic and physical characterizations of genome-scale ordered maa structure mammalian ma viruses. Journal of virology, 82(23):1 1824 11836, 2008.
Ken A Dill and Justin L MacCallum. The motein-folddng problem, 50 years science, 338(6110): 1042-1046, 2012.
Neil Dixon, John N Duncan, Torsten Geerlings, Mark S Dunstan, John EG McCarthy, David Leys, and Jason Micklefield. Reengineering orthogonally selective riboswitches. Proceedings of the National Academy of Sciences, 107(7):283--283) 2010.
Peter Eastman, Jade Shi, Bharath Ramsundar, and Vijay Pande. Solving the maa design problem with reinforcement learning. PLoS computational biology, 14(6)=e100617)) 2018.
Eduardo C Garrido-Merchán and Daniel Hernández-Lobato. Dealing with categorical and integer- valued variables in bayesian optimization with gaussian processes. Neurocomputing, 380:20-35, 2020.
Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on pattern analysis and machine intelligence, 6:721-741, 1984.
Sébastien Gerchinovitz and Jia Yuan Yu. Adaptive and optimal online linear regression é1-bblls. In Algorithmic Learning Theory, pp. 99-113. Springer Berlin Heidelberg, 2011.
Daniel Golovin, Benjamin Solnik, Subhodeep Moitra, Greg Kochanski, John Karro, and D Sculley. Google vizier: A service for black-box optimization. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1487-1495, 2017.
Rafacl Gómez--ombarrlli, Jennifer N Wei, David Duvenaud, José Miguel Hernández- Benjamín Sánchez- Dennis Sheberla, Jorge Aguilera-Iparragunnee Iparraguirre, Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using a data-driven continuous representation of molecules. ACS central science, 4(2):268-276. 2018.
Nathan Gould, Oliver Hendy, and Dimitris Papamichail Computational tools and algorithms for designing customized synthetic genes. Frontiers in bioengineering and biotechnology, 2:41, 2014.
Anvita Gupta and James Zou. Feedback gan for dna optimizes protein functions. Nature Machine Intelligence, 102):005-111, 2019.
Ivo L Hofacker. Vienna secondary structure server. Nucleic acids research, 31(13):3429-3433 2003.
Ivo L Hofacker, Walter Fontana, Peter F Stadler, L Sebastian Bonhoeffer, Manfred Tacker, and Peter Schuster. Fast folding and comparison of secondary structures. Monatshefte für Chemie/Chemical Monthly, 125(2):167-188, 1994.
John Holland and Judith Reitman. Cognitive systems based on adaptive algorithms. In Pattern- directed inference systems, pp. 313-329. Elsevier, 1978.
10

---

Under review as a conference paper at ICLR 2021
Shuichi Hoshika, Nicole A Leal, Myong-Jung Kim, Myong-San -ang Kim, Nilesh B Karalkar, Hyo-Joong Kim, Alison M Bates, Norman Watkins, Holly SantaLucia, Adam J Meyer, et al. Hachimoji dna and ma: A genetic system with eight building blocks. Science, 363(6429):8848888) 2019.
Frank Hutter, Holger H. Hoos, and Kevin Leyton- Leyton-Brown. Brown. Sequential model-based optimization for general algorithm configuration. In Proceedings of the 5th International Conference on Learning and Intelligent Optimization, LION 05, pp. 507-523, 2011.
J. Kennedy and R. Eberhart. Particle swarm optimization. In Proceedings of ICNN'95 International Conference on Neural Networks, volume 4, pp. 1942-1948 vol.4, 1995.
Nathan Killoran, Leo J Lee, Andrew Delong, David Duvenaud, and Brendan Frey. Generating and designing dna with deep generative models. arXiv preprint arXiv: arXiv: 17/2006148, 2017.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220 (4598):671-680, 1983.
Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Proceedings of the 17th European Conference on Machine Learning, ECML'06, pp. 282 293. Springer-Verlag. 2006.
Florian Leprêtre, Sébastien Verel, Cyril Fonlupt, and Virginie Marion. Walsh functions surrogate model for pseudo-boolean optimization problems. In The Genetic and Evolutionary Computation Conference (GECCO 2019), Proceedings of the Genetic and Evolutionary Computation Conference, pp. 303-311, ACM, 2019.
Hui Li, Tack Lee, Thomas Dziubla, Fengmei Pi, Sijin Guo, Jing Xu, Chan Li, Farzin Haque, Xing-Jic Liang, and Peixuan Guo. Rna stable polymer to build controllable and defined nanostructures for material and biomedical applications. Nano today, 10(5):631 1-65,, 2015.
Johannes Linder and Georg Seelig. Fast differrentiable DNA and protein sequence optimization for molecular design. Available at: hutps://arkiv.or////t//0005.... 1275, 2020.
Ge Liu, Haoyang Zeng, Jonas Mueller, Brandon Carter, Ziheng Wang, Jonas Schilz, Geraldine Horny, Michael E Birnbaum. Stefan Ewert, and David K Gifford. Antibody complementarity determining region design using high-capacity machine learning. Bioinformatics, 36(7):2126-2133, 2020.
Ronny Lorenz, Stephan H. Bernhart, Christian Höner Siederdissen, Hakim Tafer, Christoph Flamm, Peter F. Stadler, and Ivo L. Hofacker. Viennarna package 2.0. Algorithms for Molecular Biology, 6(1):26, 2011.
Nicholas R Markham and Michael Zuker. Unafold. In Bioinformatics, pp. 3-31, Springer, 2008
Andrew H Ng. Taylor H Nguyen, Mariana Gómez-Schiavon, Galen Dods, Robert A Langan, Scott E Boyken, Jennifer A Samson, Lucas M Waldburger, John E Dueber, David Baker, et al. Modular and tunable biological feedback control using de novo protein switch. Nature, 572(7768):265-26)) 2019.
Changyong Oh, Jakub Tomezak, Efstratios Gavves, and Max Welling. Combinatorial bayesian optimization using the graph cartesian product. In Advances in Neural Information Processing Syssems 32, pp. 2910-2920, Curran Associates, Inc., 2019.
Martin Pincus. Letter to the editor-a monte carlo method for the approximate solution of certain types of constrained optimization problems. Operations Research, 1866):1225-1228. 1970.
Fernando Portela. An unexpectedly effective monte carlo technique for the inverse folding problem. BioRxiv, pp. 345587, 2018.
Matthias Poloczek Ricardo Baptista. Bayesian optimization of combinatorial structures. In ICML, 2018.
Frederic Runge, Danny Stoll, Stefan Falkner, and Frank Hutter. Learning to design ma. arXiv preprint 1812. 1951, 2018.
Frederic Runge, Danny Stoll, Stefan Falkner, and Frank Hutter. Learning to design RNA. In International Conference Learning Representations, 2019.
11

---

Under review as a conference paper at ICLR 2021
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.
William M. Spears. Simulated annealing for hard satisfiability problems. In DIMACS Workshop: Cliques, Coloring, and Satisfiability, pp. 533-557, 1993.
Zachary D Stephens, Skylar Y Lee, Faraz Faghri, Roy H Campbell, Chengxiang Zhai, Miles J Efron, Ravishankar Iyer, Michael C Schatz, Saurabh Sinha, and Gene E Robinson. Big data: astronomical or genomical? PLoS biology, 13(7)xe1002195 2015.
Kevin Swersky, Yulia Rubanova, David Dohan, and Kevin Murphy. Amortized bayesian optimization over discrete spaces. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124, pp. 769-778, 2020.
Akito Taneda. Multi-objective optimization for ma design with multiple target secondary structures. BMC bioinformatics, 16(1):280, 2015.
Audrey Terras. Fourier Analysis Finite Groups and Applications. London Mathematical Society Student Texts. Cambridge University Press, 1999.
Edoardo Trotta On the normalization of the minimum free energy of mas by sequence length. PloS one, 9(1),, 2014.
Ryota Yamagami, Mohammad Kayedkhordeh, David H Mathews, and Philip C Bevilacqua. Design of highly active double-pseudoknotted ribozymes: a combined computational and experimental study. Nucleic acids research, 47(1):29 42, 2019.
Xiufeng Yang, Kazuki Yoshizoe, Akito Taneda, and Koji Tsuda. Rna inverse folding using monte carlo tree search. BMC Bioinformatics, 8:468, 2017.
Joseph N Zadeh, Conrad D Steenberg, Justin S Bois, Brian R Wolfe, Marshall B Pierce, Asif R Khan, Robert M Dirks, and Niles A Pierce. Nupack: Analysis and design of nucleic acid systems. Journal of computational chemistry, 32(1):170-I1) 173,1773,15 2011.
Michael Zuker and Patrick Stiegler. Optimal computer folding of large ma sequences using thermo- dynamics and auxiliary information. Nucleic acids research, 9()::133-448 1981.
12

---

Under review as a conference paper at ICLR 2021
A PROOF OF THEOREM 3.1
We first assume that the one-hot variables Tij E {0, 13. Plugging different choices of x E X = [ into Equation (2) leads to system of linear equations with k" unknowns (coefficients az.5) and km equations. We can express this system in matrix form as the product of the matrix of monomials (where each column j corresponds to a monomial B/ and each element (i,j) corresponds to the evaluation of the monomial 12y at the i-th choice for æ)) and the vector of unknown coefficients, which is set equal to the function values at the corresponding choices for z. We claim that there exists a permutation of the rows and columns of the matrix of monomials such that the latter becomes unit lower triangular, and is thereby full rank. As a result, the representation in for Zig E {0, 1) is
complete and unique.
To formally show that this permutation for the monomials' matrix exists, we use a construction by induction over the number of variables ni included in the representation. We denote the monomials' matrix over E variables with Φr, and define the one-hot variables rig(ū E [K 1]) as the descendants of the parent categorical variable 2; (vi E [n]). It easy to see that such a construction for the base case of only one variable exits, as the monomials' matrix is a & x &o matrix. In this case, we use the following permutation of the monomials (columns): (1, T11, T12 (kk-11) We also use the following permutation of the 2 values in rows: (k; 1, ,,....k k - 1). As result, in this matrix only the elements of the first column and the main diagonal are non-zero and equal to one, and thus the matrix & is unit lower triangular.
Assuming that the induction hypothesis holds for n variables, we show that it also holds for n + 1 variables. Starting from a unit lower triangular matrix Pn. we can construct the matrix 2,+1 as follows. Note that all the kn columns of 4,, correspond to the monomials composed of the descendants of the first n variables {azy : Vi E [m] and Vj E [k- 1]}, whereas each of the additional
kn+1 lnd columns introduced in Pn-1 involves exactly one term from (m(n-1) Vj [k 1]}
(possibly also containing factors from the previous n variables). We can express kn+1 k" using the following binomial expansion:
#+1 Σ
m 10-11 ==)Ck= 1)m-1
kn+1 k. = (k: 1)
(11)
In words, the additional k=+1 - ke columns can be considered as a collection of (mn") 1) m-th order monomials (m E [n + 1)), each of which includes one out of the k - 1 descendant variables I(x+1) Gj E [k - 1) together with m - 1 variables from the (descendants) of the previous n variables. Each of the latter m variables can take values in [R= 1]. whereas the remaining
m + variables are set to k.
Starting with m 1, we have (k- - 1) first order terms (z(n-1)1 () -(a+1)(k-1)) which we assign columns +6"+1...., km (k- 1)). The x values associated with rows (k*+1,.... km (k- - 1)) are constructed by assumiig that (i) #n+1 takes values from 1 to k - 1 (in order), while (fi) all the remaining æj (j E (ml) variables are set k. As a consequence of (i), all the elements on the main diagonal are ones; also, as a consequence of (ii), all the higher degree monomials involving Tn+1 (which occupy the elements after the diagonal ones) are equal to zeros. Thus the augmented matrix, until this point, remains unit lower triangular.
We then consider the second degree terms m = 2, where we have n(k - 1) terms (choice of one out of the other n variables, each taking values from [k: (6-1] 1J) for each of the k: - 1 choices for the variable In+1- Starting with second order monomials involving I and Tx41. we again assume that all the remaining variables x; (i & {1, + 13) are equaB] to k. For any choice of (I1, E [k- 1J3, we add a new column corresponding to the monomial 21y2(n+ 1)z as well as a new row in which r; = j and 1 = e, whereas the remaining variables are set to k. As a result, we have that: (i) the diagonal clement in the new row/column is equal to one, and (it) all the elements in the futurd columns are zeros, since any combination of one of the descendants of Iz+1 with the remaining
Note that this assumption is necessary in order ensure that monomials in future columns for the same row are evaluated to zero; choices x where this assumption not valid is addressed in next rows.
Note that the elements in the previous columns in the same row corresponding to monomials involving the selected m variables are non-zeros well.
13

---

Under review as a conference paper at ICLR 2021
variables (any variable except 21 and Tn+1) is zero. We continue this construction strategy for the remaining variables until all the second degree terms involving In+1 and one out of the remaining 1 variables is exhausted. We then repeat the same idea for terms with orders up to n + 1, as defined by the binomial expansion in (11). As result of this construction strategy, the monomial matrix P is unit lower triangular.
Now, we use this result to show the completeness and uniqueness of the representation with one-hot variables in 1 in the following way.
We showed that the representation 2 over {0, }} is complete, i.e. we can express any function using the representation in (2) where have at most one descendant term from the same parent in each monomial. Now, we replace each žij (from {0, 13) in the latter representation with (1/2, where z'y E -1.. The new representation can also be expressed via the expansion (2) since no two descendants from the same parent variable are being multiplied with each another.
Completeness:
Assume that the uniqueness condition is not satisfied. Then we have two distinet polynomial representations f1 and fz that have the same value for every z. However, since fi and /2 are distinct polynomials, (x) - fa((r) a polynomial p(z) which non-zero in at least one input x². This implies that fi(x") - f2(x²) is also non-zero, which is contradiction, and the proof complete.
Uniqueness:
Remark 1. The group-theoretic Fourier representation defined in Equation 6 is unique and com- plete.
Proof. Let x = [k]" be the categorical domain. Let the true function be f. For generality, let us consider a complex valued function f + C where C is the field of complex numbers. The basis functions are u/y (z). Now, one can view function as a [k]]"-engthh vector, one entry each for evaluating the function at every point in the domain X. We denote the vector for function f. thus obtained, by fx E Ck". Similarly, denote the vector for evaluations of the basis function dy by vix C Let A be matrix created by stacking all vectors corresponding to basis vectors in the columns. Then, the Fourier representation can written as f Aa where a is the vector of Fourier coefficients in group-theoretic theoretic representation. Now, due to the use of complex exponentials, one can show that [xe (z)))) (z) = I + I'. Therefore, the columns of the matrix A are orthogonal. Hence, A is a full rank matrix. Therefore, our representation is merely representing a vector in another full rank orthogonal basis. Hence, it is unique and complete.
B DESCRIPTION OF ALGORIHHS
Surrogate Model Learning Algorithm:
Let n and denote the number of variables and the cardi- nality of each variable, respectively. The surrogate models used in ECO-F and ECO-G correspond to approximations of the representations given in 2 and (8) respectively, where each approximation is obtained by restricting the maximum order of interactions among variables to m. We consider each term in the latter surrogate models, i.e. monomials VII. from (3) in ECO-F and characters (00) in ECO-G, an expert, denoted by th (i E [d]). The number of such experts in ECO-F is d Di ()) 1) which coincides with the dimensionality of the space knd when m n. whereas the number of experts in ECO-G is equal to d = 2 coefficient of each expert vy is designated by ar Since the exponential weights, utilized to update the coefficients ag are nen-negative we maintain two nog-tvgative coefficients a, and a, which yield a, = a, a;
( E {r, 2}) from
m
1) 1. The
We initialize all the coefficients with a uniform prior, i.e. of = 1/2d (Vi E [d] and 7 E (-,+)), In each time step t, we draw sample 2, via Algorithm with respect to our current estimate for the surrogate model fa. The latter sample is then plugged into the black-box function to obtain the evaluation f(xx). This leads to a mixture loss L as the difference between the evaluations obtained by our surrogate model and the black-box function for query 2,. Using this mixture loss, we compute update each coefficient in the model via an
the individual loss E for each expert th. Finally, exponential weight obtained according to its incurred individual loss. We repeat this process until stopping criteria are met.
14

---

Under review as a conference paper at ICLR 2021
Algorithm 3 Expert Categorical Optimization
1: Inputs: sparsity X, max model order
2: 160, O, Vy (-,+} Vi E
[d] oi,
2d
3: repeat
4: 24 ~ fat via Algorithm 1
Algorithm
5: Observe f(x))
6:
(2) + -ie( (a - - (b)(z)
gr+l (z) f(x))
7:
8:
for E [d] and y E {-+ do
gt1 + 22 2 (2i(
9:
10:
biyy + oi exp y17 E, g++1) 2+1 1. d Exel- Ene
1+1
12:
end for
13:
+
14:
until Stopping Criteria
15:
return I+ arg (in Well) (a;;
Number of Experts: The number of terms in vanilla one-hot encoded Fourier representation is 2 whereas our abridged representation reduces this number to An matching the space dimensionality. thereby making the algorithm computationally tractable and efficient. When max degree of m is used in the approximate representation, the number of terms in the abridged representation is equal to 2i (?) (k 1)s. The corresponding number in a vanilla one-hot encoded representation equal to Li=o (*h)). Finally, the numbers of terms in the full and order-m group-theoretis Fourier expansions equal to 2k 1 and d =2 >Σ (k) 1) 1, respectively.
m
MCTS Algorithm: For a complete version of Algorithm 2 see Algorithm
Learning Rate: The anytime learning rate (at time step t) used in Algorithm 3 is given by Gerchi
novitz& Yu 2011] Dadkhahi et al. (2020):
(2d)
1/h min
(12)
ct-1
11-1
where A / 22(V2 - (ex(ex)(1) -2) and
=3, A -2 X le (x+))
e₁
inf
2 2
max 2E(d]
max J.KE 7-mE-
123,
=
2
0/1 Σ
Σ
a3 2/
Σ
at $ #
aE[t] -E(-,+)
jEld]
keid -
C CONTINUED RELATED WORK
variety of discrete search algorithms and meta-heuristics have been studied in the literature for combinatorial optimization over categorical variables. Such algorithms, including Genetic Algorithms Holland & Reitman (1978), Simulated Annealing Speaass (993)., and Particle Swarms Kennedy & Eberhart (1995), are generally inefficient in finding the global minima. In the context of biological sequence optimization, the most popular method is directed evolution Arnold (1998). which explores the space by only making small mutations to existing sequences. In the context of sequence optimization, a recent promising approach consists of fitting a neural network model to predict the black box function and then applying gradient ascent on the latter model Killoran et al.
15

---

Under review as a conference paper at ICLR 2021
Algorithm 4 MCTS with Surrogate Reward Model
1: Inputs: surrogate reward model fa, exploration parameter search tree T
2: Speat = O}. Nrest -00
3: repeat
4: Initialize episode 0, 81 =
5: while $ T do
6: G₁ 4- π (st) = arg max.eA, Q(s;, + c N(sl//NN))))
7:
St+1 - (st, ae) 0a
8:
t ++t+1
9:
end while
10: Steat 8t
T TU(t
12:
Va Alt1 (s) = 0, Q(sr.a)
repeat
14:
at t π (st)
8:11 - T(s,, az) = 8t at
16:
/-t+1
17:
until 5; is terminal
18:
r - (s)
19:
+ 8leaf
20:
repeat
21:
(ss + N(s,a)+1 +1
22:
a + (() + N(.aj (r (r-
Q(s, a))
23:
parent(s);
visited action
24:
until s is the root node
25:
if Toast then
26:
Thest f- and Bbost f 8t
27:
end if
28:
until Stopping Criteria
29:
return Speat
16

---

Under review as a conference paper at ICLR 2021
(2017); Bogard al. (2019): Liu al. (2020). This approach allows for continuous relaxation of the discrete search space making possible step-wise local improvements to the whole sequence at once based gradient direction. However, these methods have been shown to suffer from vanishing gradients [inder Seelig (2020). Further, the projected sequences the continuous relaxation space may not be recognized by the predictors, leading poor convergence. Generative model-basee optimization approaches aim to learn distributions whose expectation coincides with evaluations of the black box and try maximize such expectation Gupta & Zou 2019); Brookes al. (2019). However, such approaches require a pre-trained generative model for optimization.
D BBO EXPERIMENTS
Latin Square Problem: A latin square of order k k matrix elements Tity E [kt], such that each number appears in cach row and column exactly once. When k 5, the problem of finding latin square has 161, 280 solutions
space dimensionality 525, formulate the problem of black-box function by imposing additive penalty of one for any repetition of numbers in any row or column. As a result, function evaluations are in the range [0, 2k(k 1),, and function evaluation of zero corresponds to latin square of order k. We consider a noisy version
finding latin square of order
of this problem, where an additive Gaussian noise with zero mean and standard deviation of 0.1 is added function evaluations observed by each algorithm.
Figure SaareBdemmooe demonstrates the performance of different algorithms,, in terms of the best function value found until time over 500 time steps. Both ECO-F and ECO-G outperform the baselines with considerable margin. In addition, both ECO-G and ECO-F match COMBO's performance closely until time step 190. At larger time steps, COMBO outperforms the other algorithms, however, this performance comes at the price of far larger computation time. As demonstrated in Table [ ECO-F and ECO-G offer a speed-up over COMBO by a factor of approximately 100 and 50, respectively.
RS
SA
COMBO
ECO-F
ECO-G
17.5
15.0
12.5
Best of f(x)
10.0
7.5
2.5
0.0
100
200
300
400
500
Time Step
Figure 3: Best function evaluation seen so the Latin Square problem.
In the pest control problem, given stations and pesticide types, the idea is to maintain the spread of pest (with minimum cost), which is propagating throughout the stations in an interactive and probabilistic fashion. The k-th category for each variable corresponds to the choice of pesticide at all. Controlling the spread of the pest is carried out via the choice of the right type pesticide subject to a penalty proportional to its associated cost. A closed form definition of this problem is given in Oh et al. (2019).
Pest Control Problem:
The results for different algorithms are shown in Figure Despite the fact that COMBO is able to find the minimum in fewer time steps (in Rs 200 steps) than ECO-F (in as 360 steps) average,
17

---

Under review as a conference paper at ICLR 2021
ECO-F outperforms COMBO during initial time steps (until = 180). SA performs competitively, but eventually is unable to find the optimal solution to this problem over the designated 500 steps. The poor performance of ECO-G G can be explained by the interactive nature of the problem, where early mistakes are punished inordinately. Early mistakes made by ECO-G can also be attributed to the large number of experts (with noisy coefficients) in its model, which in turn promotes early exploratory behavior.
RS
SA
COMBO
ECO-F
ECO-G
19
18
17
Best of f(x))
16
15
14
13
12
100
300
500
Time Step
Figure 4: Best function evaluation seen so far for the pest control problem.
Structured RNA molecules play a critical role in many biological applications, ranging from control gene expression to protein translation. The native secondary structure of RNA molecule is usually the minimum free energy (MFE) structure. Consider an RNA sequence as a string {A, U, G, C}. A pair of complementary nucleotides and aj. where (i < j), can interact with each other and form base pair (denoted by (i,j)), A-U, C-G and G-U being the energetically stable pairs. Thus, the secondary structure of an RNA can be represented by ensemble of pairing bases.
RNA Sequence Optimization Problem:
a1 ... Gn of letters (nucleotides) over the alphabet Σ
Finding the most stable RNA sequences has immediate applications in material and biomedical applications Li et al. (2015). Studies show that by controlling the structure and free energy of RNA molecule, one may modulate its translation rate and half-life in cell Buchan & Stansfield (2007) al. (2008, which is important in the context of viral RNA. A number of RNA folding algorithms Lorenz et al. (201T): Markham & Zuker (2088) use thermodynamic model (e.g. Zuker & Stiegler 1981)) and dynamic programming to estimate MFE of sequence. However, the (n)) time complexity of these algorithms prohibits their use for evaluating substantial numbers of RNA
sequences Gould et al. (2014) and exhaustively searching the space to identify the global free energy minimum, as the number of sequences grows exponentially as 4".
Here, formulate the RNA sequence optimization problem follows: For sequence of length find the RNA sequence that will fold into the secondary structure with the lowest minimum free energy. In our experiments, we initially set n 30 and k 4. We then use the popular RNAfold package Lorenz et al. (2011) to evaluate the MFE for a given sequence. The goal is to find the lowest MFE sequence by calling the MFF evaluator minimum number of times. The performance of different algorithms is depicted in Figure where both ECO-F and particularly ECO-G outperform the baselines as well as COMBO by considerable margin.
Energy-optimized RNA Structures: Sample RNA sequences obtained via ECO-G after 4000 time steps for n = 30 and n 60 are shown in Figures 6 and 7 respectively. The resulting energy- optimized sequences (as obtained using RNAfold service) have high (> 90%) GC content that makes the strongest positive contribution to lowering MFE Trotta (2014), as pairings between G and C have three hydrogen bonds and more stable compared A and U pairings, which
18

---

Under review as a conference paper at ICLR 2021
RS
SA
COMBO
ECO-F
ECO-6
-
-10
Best of f(x))
-15
-20
-25
-30
0
100
200
300
400
500
Time Step
Figure 5:
Best function evaluation seen so far for the RNA sequence optimization problem with n = 30.
Table 1:
Average computation time per step (in Seconds) over different problems and algorithms.
DATASET
k
COMBO
ECO-F
ECO-G
LATIN SQUARE
25
170.4
1.5
3.6
PEST CONTROL
25
151.0
1.4
3.3
SEQUENCE PREDICTION
253.8
2.0
5.7
have only two. The final single-strand RNA sequence folds into a GC-paired double helix and nucleotide long hairpin loop in the middle, which a tetraloop reported literature (http: / 7/www. rna. cmb uutuutexeo exas edu/ S SIM/ 4C/ hC/energeti cs cs_new/j Figures 10 and show two sample structures the ECO-G optimized sequences for n 31, again showing the same trend. For odd values of n, there is presence of loop with odd number of residues base at the end, but there still a GC-rich double helix. In contrast, the structures generated by the under-performing algorithms do show presence of unpaired bases and are less in GC content, leading to high energy structures (e.g. Figures and 9 are obtained via SA after 4000 steps for n 30 and 60, respectively).
single unpaired
E DESIGN EXPERIMENTS
For our experiments, we focus three puzzles from the Eterna-100 dataset Anderson-Lee al. 2016).. Two of the selected sequences (puzzles 15 and 41 of lengths 30 and 35, resp.), despite their fairly small lengths, are challenging for many algorithms (see Anderson-Lee al. (2016)) In both puzzles, our MCTS variants (ECO-F and ECO-G) are able to significantly improve the performance of MCTS when limited number of true rewards are available. All algorithms outperformed RS as expected. Within the given 500 evaluation budget, both ECO-G, and especially ECO-F, are superior to LEARNA by substantial margin (see Figure 12). In puzzle number 41 (Figure [3], again both ECO- G and ECO-F significantly outperform LEARNA, over the given number of evaluations. Interestingly, ECO-F able to outperform LEARNA throughout the evaluation process, and in average finds far better final solution than LEARNA.
The final sequence is puzzle # 70 of length 184. The results of different algorithms over the latter puzzle is shown in Figure 14 As can from this figure, MCTS-RNA and LEARNA perform very similarly over the given 500 evaluation budget. ECO-F able to outperform the remaining algorithm throughout the evaluation steps. Initially, ECO-G has similar performance to those of
19

---

Under review as a conference paper at ICLR 2021
Figure 6: RNA Structure via ECO-G for 30 Figure 7: RNA Structure via ECO-G for 60
MCTS-RNA and LEARNA, but offers an improved performance over the latter two just after 400 steps.
F CHOICE OF THE ACQUISITION METHOD
Throughout the experiments, we designated SA and MCTS as acquisition methods for generic BBO and design problems, respectively. The latter choice made in accordance with the literature, where SA is typically used as a baseline and method choice for the generic BBO problem, whereas MCTS has been commonly used for the design problem. For instance, SA has been considered baseline and/or acquisition method in Dadkhahi et al. (2020). Ricardo Baptista (2018), and Oh et al. (2019) (albeit with different algorithm than ours). On the other hand, MCTS (i.e. RNA-MCTS as well as its variations) is perhaps the most popular RNA design technique in the literature. Here, we point out that both SA and MCTS can be used for both generic BBO and design problems. In this section, we compare the performance of different acquisition methods in each problem.
First, we consider the generic BBO problem of RNA sequence optimization with 30 (considered in Section[4). Figure [5 demonstrates the performance of ECO-F and ECO-G when SA or MCTS are used as acquisition methods. As we can see from this figure, the counterparts over 500 steps. In particular,
acquisition-metilee
variants
perform slightly better than although the performance gap initially moderately large, over time this performance gap becomes smaller.
Next, we consider two design problems considered in Section puzzles # 15 and #41. Note that, when using SA as the acquisition method, apply the softmax operator (in Algorithm I over the set of (GC, CG, AU, UA} if the corresponding variable is part of a paired base. As we can see from Figure 16 for puzzle # #5,, ECO-F with MCTS outperforms the remaining algorithms. The rest of the algorithms have very similar performances, with ECO-F (MCTS) marginally surpassing the SA variants. As can from Figure 17 for puzzle #41, the MCTS variant of ECO-F slightly
20

---

Under review as a conference paper at ICLR 2021
Figure 8: RNA Structure via SA for 30
Figure 9: RNA Structure via SA for 60
Figure 10: RNA Structure via ECO-G for n = 31 Figure 11: RNA Structure via ECO-G for n = 31
outperforms its SA variant, whereas the MCTS variant of ECO-G maintains a bigger gap with its SA variant.
21

---

Under review as a conference paper at ICLR 2021
MCT8
LEARNA
ECG-F
EC0-6
18
16
14
f()
2
100
200
300
400
500
Time Step
Figure 12: Best function evaluation for RNA Design of puzzle 15 with 30.
RS
MCTS
LEARNA
ECO-F
ECO-G
22.5
20.0
17.5
Min of f(x)
15.0
12.5
10.0
7.5
5.0
100
200
300
400
500
Time Step
Figure 13: Best function evaluation RNA Design of puzzle #41 with n 35.
G ORDER OF THE SURROGATE MODEL
As mentioned in Section we used m 2 as the maximum order of the representations in all the experiments. In this section, focus the generic BBO problem of RNA optimization and investigate the impact of the model order on the performance of the proposed ECO algorithms. In particular, we compare the performance of the algorithm m 3 with that of 2. As we can see from Figure 18 at smaller evaluation budgets, the order 2 models moderately outperform the order 3 counterparts both ECO-F and ECO-G. we increase the number of samples, this performance gap becomes smaller. At the 500 evaluation budget, ECO-G3 outperforms ECO-G2 by small margin of 0.1. At the same evaluation budget, ECO-F3 is slightly inferior to ECO-F2 by a margin of 0.2. Considering the convergence behavior of the curves at order 3 versus those of order 2, we expect the former models to eventually outperform the latter models at higher number evaluations. However, since in BBO problems sample efficiency is typically of main concern, it would make sense to low-order approximations. We point out that a similar observation was made in Ricardo Baptista (2018) for the Boolean case, where higher order models suffer from slower start due the higher
22

---

Under review as a conference paper at ICLR 2021
MCT8
LEARNA
ECG-F
EC0-6
80
Min f(x)
60
60
40
100
200
300
400
500
Time Step
Figure 14: Best function evaluation for RNA Design of puzzle #70 with 184.
ECO-G ISA)
ECO- (SA)
ECO-G GMCTS(MCTS)
ECOF (MCTS)
-10
Min f(x
-15
-20
-25
-30
0
100
200
300
400
500
Time Step
Figure 15:
Comparison of different acquisition methods the generic BBO problem RNA sequence optimization with 30.
dimensionality of the parameter space. From our experiments categorical problems, this behavior seems to be even more pronounced due to the higher dimensionality of the categorical domains.
summary of the computation times for ECO algorithms different model orders is given in table 2 Since the complexity of ECO is linear in the number of experts, which exponentially grows with the model order m, we observe an increase in the computational complexity of ECO-F3 (ECO-G3) versus that of ECO-F2 (ECO-G2) by factor of 9.7 (16.3).
Table 2: Average computation time per step (in Seconds) at different model orders.
ECO-F2
ECO-F3
ECO-G2
ECO-G3
2.0
19.4
5.7
93.1
23

---

Under review as a conference paper at ICLR 2021
ECO-G (SA)
ECO-F (SA)
ECO.G (MCTS)
ECD (MCTS)
16
14
Min of f(x)
10
8
100
200
300
400
500
Time Step
Figure 16: Comparison different acquisition methods for design puzzle #15 with n 30.
(SA)
(SA)
(MCTS)
22.5
20.0
17.5
of ftx)
15.0
12.5
10.0
7.5
5.0
Time Step
Figure 17: Comparison of different acquisition methods for design puzzle #41 with 35.
24

---

Under review as a conference paper at ICLR 2021
ECD-F2
ECO-G2
ECO-F3
-5
-10
Best of f(x.)
-20
-25
-30
0
100
200
300
400
500
Time Step
Figure 18:
Impact of model order on the performance of ECO-F/G in the RNA optimization problem with
30.
25


Reviews:
[{"review_id": "aKPyautVyYX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper proposes two representations, namely one-hot encoded Boolean expansion and group-theoretical Fourier expansion, for the surrogate model used for the black-box evaluations on purely categorical variables. With the two surrogate models, the authors tackle both the black-box optimization problem and the design problem. Two forms of acquisition functions are applied for query selection – simulated annealing and Monte Carlo Tree Search. The new algorithms are compared with the existing methods in simulations and have advantage for the objective value and speed-up.\n\nThe paper has many contributions, and I would be inclined to recommend the paper for acceptance, after the rebuttal.\n\nMy concerns are three-folds.\n1. The paper seems not to have clearly abundant novelty, as far as I understand. The author should highlight what is new for one-hot encoded function and group-theoretical Fourier expansion. Also, the simulated annealing and Monte Carlo Tree Search are not fully novel and I seem not to fully see the major changes to these methods. It would be great if the authors could list the major changes to these algorithms to fully show novelty.\n2. The one-hot Boolean expansion could have a certain degree of lack of scalability if the order of approximation is large. If the order $m$ has a large value, then all $m$-subset of set $[n]$ might have too many terms for the representation to be efficient. A method to prune the $m$-subset should be needed. \n3. The one-hot encoded Boolean function and group-theoretical expansion should have applications that they fit well and problems that they are less applicable. It seems critical to identify the superb properties of these functions than other alternatives, and a rough range of the problems that work better with these surrogate functions. Without such identification, the surrogate functions have reduced significance.\n\nPlease fix the following unimportant typos. The variable $j$ is overloaded in Eq (7), as it is both the complex number unit and the integer pair.  The r and i subscript in Eq (8) are not defined, for real and imaginary part of the function $f_{\\alpha}(x)$.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Um-hbeKlCXq", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "**Summary**\nThis paper proposes a model-based black-box function optimization on purely categorical variables. Two different representations for categorical variables are proposed, one is an improved pseudo-boolean function form capable of representing non-binary categorical variables in a compact way and another is to rely on (mathematical) group representation theory after mapping each categorical variable to a cyclic group. In acquisition function optimization, SA is used for generic BO and MCTS is used for design problems. The proposed EGD-F/G are compared with baselines and shown to have competitive computational efficiency with comparable performance.\n\n\n**Strengths**\n1. A compact representation for general (including non-binary) categorical variables is proposed and the strengths of the compact representation are theoretically supported, which is an improvement upon a bit ad-hoc approach to handle non-binary categorical variables proposed in BOCS.\n2. The proposed algorithm is more efficient than COMBO with comparable performances. EGO-F/G may find more useful applications in problems where more evaluations are affordable than classical BO settings.\n\n\n**Weaknesses**\n1. EGO-F/G does not provide explicit uncertainty in its surrogate modeling, which is crucial in balancing exploitation-exploration trade-off. And the acquisition function is kind of just predictive mean of the surrogate model, it seems that balancing exploitation-exploration is the full responsibility of the acquisition function optimizer, which makes me think that the performance is attributed more to different choices of an acquisition function optimizer and less to surrogate models. However, if there is some stochasticity in surrogate model training, then this can be interpreted as Thompson sampling as NN trained with SGD can be regarded as a posterior sample, then it seems OK to say that surrogate model plays its part for exploitation-exploration trade-off. It would be good if the authors can clarify this. \n2. Since, typically, not much information about an objective is available in advance, choosing a different acquisition function optimizer is not practical. Even though the test problems are divided into generic BBO and design problems, it seems that both SA and MCTS can be used in all experiments. For example, SA for the constrained problem can simply mask softmax values corresponding to invalid ones and MCTS for unconstrained ones is easier to adapt. If EGO-F/G is shown to be less sensitive to the choice of the acquisition function optimizer, then the argument for the strong representational power of the surrogate models will be supported more strongly. Therefore, it is recommended that the authors compare SA and MCTS in experiments where possible as BOCS(Ricardo Baptista, 2018) compares BOCS-SA and BOCS-SDP. \n3. In spite of the benefits from Fourier transform on finite Abelian groups, giving a cyclic group structure to each categorical variable impose a random structure on values of the categorical variable. For example, if a categorical variable has 6 categories and is mapped to Z_6, then the categorical value corresponding to 2 and the categorical values corresponding to 4 are the inverse to each other due to the mapped group structure but this relation is not natural with regard to original categorical values. I was not able to find any theoretical/empirical analysis in the paper.\n4. Up to the experiment section, the paper is presented in a way that the ultimate goal is to find an optimum as few evaluations as possible. However, in synthetic benchmarks, EGO-F/G are argued to be better than baselines because of the computational efficiency, which sounds a bit contradicting.\n\n\n**Recommendation**\nBecause of the concern on the consistency of the performance from using different acquisition function optimizers, the empirical demonstration has points to be improved. And even though a mathematically elegant expert is given by Fourier transform on a finite abelian group, the correspondence between a categorical variable and a (finite) cyclic group needs more investigation. Therefore, in spite of its interesting idea, I think the paper needs some improvement for acceptance.\n\n\n**Questions**\n- SA and MCTS are acquisition function optimizers, not acquisition function itself. In contrast to typical BO where the acquisition function is a function of the predictive distribution given by the surrogate model, the acquisition function of EGO-F/G is the surrogate model itself (in other words, identity function on kind of predictive mean), isn't it?\n- In regard to weakness 2, the correspondence between categorical values of a categorical variable and the elements of a group seems arbitrary. Does this mapping affect performance? Do you have any reasonable interpretation of this?\n- In each experiment, which m (max model order) is used? Does the choice of m have a significant impact on runtime and optimization performance?\n- Maybe on Eterna-100 dataset, COMBO is not applicable?\n\n\n**Additional feedback** (Irrelevant to the decision assessment)\n- The last sentence of the first paragraph of the introduction is a bit confusing. Since mixed variable problems include pure categorical ones as subproblems, intuitively, mixed variable problems look more challenging than purely combinatorial ones.\n- It would be better if 'Proof, see appendix' is added under thm 3.1.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JQ1CeqY5Vw", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This seems like a very interesting paper and perhaps quite impactful indeed, if it achieves what it claims to. Unfortunately, assessing the novelty and merit of this paper relies heavily on expertise in Group theory, which I certainly lack. Here are some scattered thoughts, for whatever they're worth.\n\nOn the one hand, assuming a surrogate function that is equipped with this ability to generalize, leveraging MCTS and the UCT selection criterion as an acquisition function seems reasonable to me. On the other hand, it seems to me that using SA, targeting a tempered surrogate, might be too greedy and not align with the latest approaches in black box optimization, where some measure of uncertainty is used in the acquisition decision-making process. It would be good to have a discussion on how one could obtain an uncertainty quantification from the decomposition (e.g. uncertainties around each coefficient alpha and how that extends to uncertainty in f).\n\nIn terms of experimentation, since this paper introduces a new decomposition that is complete and unique, I would've expected to see some results concerning how well a truncated decomposition fits a known function of categorical variables. Some toy experiments would provide valuable evidence that the surrogate learned from such a truncated decomposition is likely good even for relatively short truncations.\n\nAs I cannot pass judgement on the novel aspects of this paper, I will be generous with my score and let my confidence score reflect my lack of expertise. Looking forward to reading other reviews and comments on this manuscript.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AuqT4pEgdWr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Paper Summary\n\nThe paper considers the problem of black-box optimization of expensive functions defined over categorical variables. A surrogate model-based optimization approach is proposed to tackle this problem. Fourier representations are proposed as surrogate model by treating the categorical input as the direct sum of cyclic groups Z/kZ (k is the arity/category size). The coefficients of this representation are learned via exponentially-weighted update rule. The selection of each subsequent input for evaluation is performed via direct optimization of the surrogate model built over inputs collected previously. Simulated Annealing and Monte Carlo Tree Search is proposed as the acquisition function optimization procedure for unconstrained and constrained problems respectively. Experiments are performed on two synthetic problems and RNA-sequence optimization.\n\nDetailed Comments\n\n- The paper considers an important problem which has multiple applications (for e.g. biological sequence design) in practice. \n\n- Although the proposed method is a natural generalization of the COMEX [5] approach which was proposed for binary variables, it shows good performance on two benchmarks and can be useful for end users because of its simplicity. \n\n- Regarding the two proposed representations, isn't the first one (Equation (2)) a special case of the second (Equation (6))? What are the tradeoffs in choosing one among them?\n\n- There are many important and relevant related work (both for surrogate modeling and acquisition function optimization) that are not discussed in the paper.  Please provide a detailed discussion comparing proposed approach with the below methods otherwise it comes across as if there is limited existing work for the considered problem. They are very relevant to the paper because all of them consider the setting of \"small\" data with expensive function evaluations.\n  - Surrogate modeling\n\t- SMAC [1] is the most natural approach that handles categorical variables nicely. \n\t- Tree structured Parzen Estimator (TPE) [2] is another approach that can easily handle categorical variables. \n\t- Walsh functions [3] have been used effectively for surrogate modeling over discrete variables. \n  - Acquisition function optimization\n  \t- Amortized Bayesian Optimization over Discrete Spaces [4]\n\n- The proposed one-hot encoding in Equation (2) is said to have \"far less terms than a vanilla encoding\". Please provide a quantitative description of this reduction of number of terms. \n\n- It is not entirely clear how the representation for a real-valued function reduces to (8) from (6). Do we just ignore the complex part similar to the common approach in random Fourier features used for kernel methods? Please provide a clear derivation.\n\n- Is the choice of n=30 for RNA sequence optimization motivated by some real-world implication?\n\nReferences\n\n[1] Hutter, F. and Hoos, H. H. and Leyton-Brown, K. Sequential Model-Based Optimization for General Algorithm Configuration In: Proceedings of the conference on Learning and Intelligent OptimizatioN (LION 5)\n\n[2] Bergstra, J. S., Bardenet, R., Bengio, Y., & Kégl, B. (2011). Algorithms for hyper-parameter optimization. In Advances in neural information processing systems (pp. 2546-2554).\n\n[3] Leprêtre, F., Verel, S., Fonlupt, C., & Marion, V. (2019, July). Walsh functions as surrogate model for pseudo-boolean optimization problems. In Proceedings of the Genetic and Evolutionary Computation Conference (pp. 303-311).\n\n[4] Swersky, K., Rubanova, Y., Dohan, D., & Murphy, K. (2020, August). Amortized Bayesian Optimization over Discrete Spaces. In Conference on Uncertainty in Artificial Intelligence (pp. 769-778). PMLR.\n\n[5] Dadkhahi, H., Shanmugam, K., Rios, J., Das, P., Hoffman, S., Loeffler, T. D., & Sankaranarayanan, S. (2020). Combinatorial Black-Box Optimization with Expert Advice. arXiv preprint arXiv:2006.03963.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of black-box optimization over categorical variables using expensive function evaluations. 
- Fourier representation is proposed as surrogate model by treating the categorical input as the direct sum of cyclic groups. The parameters are learned using exponentially-weighted update algorithm.
- To select the inputs for evaluation, simulated annealing and MCTS are employed as search algorithms to optimize the learned surrogate function. 
- Experiments are performed on two synthetic problems and RNA sequence design problems.

The proposed fourier representation is novel and the results show the promise of this method in terms of computational-efficiency over state-of-the-art COMBO method.

There are two unsatisfactory aspects of this paper.
1. In expensive black-box optimization problems, number of function evaluations to find better solutions is critical. This paper takes a non-Bayesian approach to improve computational-efficiency (over prior Bayesian optimization methods), but this same advantage comes at the expense of sample-efficiency (number of function evaluations) due to lack of exploration. 
2. In fourier representation, mapping categorical values to different group elements may change which basis are used for modelling. From a practitioner's perspective, it is important to verify that the performance is not significantly affected by this choice. This can be verified empirically. Even though one reviewer raised this point, authors' haven't responded though it is an easy experiment to do.

Due to the above shortcomings, the paper is judged to be not ready for publication at the current stage. I strongly encourage to resubmit the paper after addressing the above two concerns.
Decision: Reject