Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

The paper has many contributions, and I would be inclined to recommend the paper for acceptance, after the rebuttal.

My concerns are three-folds.
1. 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.
2. 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. 
3. 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.

Please 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)$.  

review_title: Official review

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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.

On 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).

In 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.

As 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.
review_title: The authors offer a Fourier representation for categorical variables that allows for generalization of observations of the response surface across categories.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Paper Summary

The 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.

Detailed Comments

- The paper considers an important problem which has multiple applications (for e.g. biological sequence design) in practice. 

- 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. 

- 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?

- 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.
  - Surrogate modeling
	- SMAC [1] is the most natural approach that handles categorical variables nicely. 
	- Tree structured Parzen Estimator (TPE) [2] is another approach that can easily handle categorical variables. 
	- Walsh functions [3] have been used effectively for surrogate modeling over discrete variables. 
  - Acquisition function optimization
  	- Amortized Bayesian Optimization over Discrete Spaces [4]

- 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. 

- 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.

- Is the choice of n=30 for RNA sequence optimization motivated by some real-world implication?

References

[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)

[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).

[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).

[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.

[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.
review_title: Official Review #4

final_score: rating: 5: Marginally below acceptance threshold
review_content: **Summary**
This 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.


**Strengths**
1. 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.
2. 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.


**Weaknesses**
1. 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. 
2. 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. 
3. 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.
4. 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.


**Recommendation**
Because 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.


**Questions**
- 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?
- 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?
- In each experiment, which m (max model order) is used? Does the choice of m have a significant impact on runtime and optimization performance?
- Maybe on Eterna-100 dataset, COMBO is not applicable?


**Additional feedback** (Irrelevant to the decision assessment)
- 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.
- It would be better if 'Proof, see appendix' is added under thm 3.1.
review_title: The idea is interesting but there are some theoretical and empirical parts that need to be clarified more.

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