Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes to use MCTS to enhance existing algorithms for Multi-Objective Optimization problems.
Experimental results on a wide range of benchmark problems show the improving performance of the proposed method, LaMOO.

main_review: Strengths.
- The proposed method uses an interesting combination of algorithms.
- The results are compelling.
- The paper is well written. It is easy to understand, well-organized, and the illustrations help understand the behavior of the algorithm.

Weaknesses.
- It is possible to criticize that it is a combination of existing techniques
(which is not a serious issue, in my opinion).
- Some papers propose Multi-Objective optimization using A* search.
I think the related work section should mention these.
The following short paper covers some of such papers as of 2011.
https://www.ijcai.org/Proceedings/11/Papers/483.pdf
- A part of the algorithm that "updating all previous samples" may take a long time for larger-scale problems because the time will be O(N^2) to the sample size N.
summary_of_the_review: In my opinion, the significant improvement in performance with a simple method is highly valuable.
The idea is simple, well-explained, and the results are promising.
This paper should be valuable for many applications.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper develops an enhancement to multiobjective solvers so to find better Pareto solutions. The idea is to learn a proxy of the distance of samples to the Pareto frontier, and leverage such information to split the search space via a tree structure, Samples can then be extracted from promising nodes of the tree from other multiobjective algorithms. Numerical results investigate the performance of the method for both synthetic and practical benchmarks.


main_review: The paper is well-written and, in my view, it offers a simple but effective "meta" perspective for multiobjective programming. In particular, it resembles many criterion-search space techniques that split the objective space for strategic exploration. However, here authors use the dominance metric to partition the primal space, which leads to interesting properties and a tree encoding.

I also appreciate the theoretical aspects investigated by the authors, which are sound to the best of my analysis and give a more concrete justification to the results we observe in the numerical setting. 

My major concern, however, is that it is somewhat unclear when the proposed meta-algorithm is applicable or more beneficial. In particular:

(a) Are there (combinatorial) problems where the tree would need to be significantly large to ensure high-quality points are actually found? I was somewhat confused as to how the tree may grow depending on the underlying structure of the problem.

(b) What are the properties that a multiobjective algorithm would need to satisfy to apply the split partition? For example, suppose one is using a multiobjective mixed-integer linear program to enumerate the frontier. Is it possible to represent complex splits in a way that they encode true partitions? It seems that broader split definitions, for instance in larger-dimension criteria space, could be high non-linear (or perhaps I misunderstood some concept?).

(c) What are the guidelines to set the exploration factor C_p empirically? It seems that it is highly optimized for the numerical experiments that were performed in the paper
summary_of_the_review: A well-written paper that provides an interesting and relevant contribution to multiobjective optimization. One of the key benefits of the method is its generality, in that it can be incorporated into existing multiobjective solvers, and simple implementation. Numerical results suggest significant improvements with little implementation work.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work proposes a novel learning-based method called  LaMOO to partition the search space for the multi-objective optimization problem. With the learned partition, the computational budget can be allocated to the small promising regions (e.g., the region close to the Pareto frontier) rather than the whole search space. It is a direct generalization from the closely related works (e.g., LaNAS, LaMCTS, and LaP^3) to multi-objective optimization. The proposed LaMOO has promising experimental results on both synthetic functions and real-world optimization problems.
main_review: **Strengths:**

+ This work is well-organized and generally well-written.

+ The studied problem, multi-objective optimization, is important and could be useful for many real-world applications. 

+ The proposed LaMOO method is a reasonable generalization from LaMCTS to multi-objective optimization.

**Weakness:**

*Method:*

**1. Novelty:** 

- **Incremental Contribution:** The proposed LaMOO is a direct generalization from the LaMCTS method to multi-objective optimization (MOO). The novel part is to use dominance number as criteria for search space partition and hypervolume for promising region selection. These are all straightforward generalizations for MOO. The contribution of this work is somewhat incremental along the line of LaNAS, LaMCTS, and LaP^3. 

- **Missing Closely Related Approaches:** This work claims the proposed approach to learn the promising region is *fundamentally different* from the previous works. However, many classification-based search space partition methods have been proposed in the machine learning community, see [1][2][3] (classification + random sampling). (Tree-based) space partition methods have been widely used for black-box optimization [4][5][6]. In addition, there are also different works on classification-based MOO [7] (SVM + NSGA-II/MO-CMA-ES) [8] (Ordinal SVM + NSGA-II) [9]. 


**2. Theoretical Analysis:**

A large part of this work is on the theoretical understanding for space partition and LaMCTS. However, the analysis is mostly for single-objective optimization, and the extension to multi-objective optimization is much less promising.

**3. Why LaMOO Works:** 

Further discussions are needed to clearly clarify the properties of LaMOO.

- **Dominance-based Approach for Many Objective Optimization:** LaMOO uses the dominance number as the split criteria to train the SVM models and partition the search space. However, the dominance-based method is typically not good for many objective optimization due to the lack of dominance pressure (e.g., all solutions are non-dominated with each other, and all have the same dominated number). Why is LaMOO still good for many objective optimization? 

- **Combination with Multi-Objective Bayesian Optimization (MOBO):** It is straightforward to see the benefit of using LaMOO with model-free optimization (e.g., NSGA-II and MO-CMA-ES). However, it is not so clear to understand why it also works for MOBO (e.g., qEHVI). The qEHVI approach already builds (global) Gaussian process models to approximate each objective function, and uses hypervolume-based criteria to select the most promising solution(s) (e.g., maximizing the expected hypervolume improvement) for evaluation. Therefore, its selected solution(s) should be already on the approximate Pareto front without the LaMOO approach.  Is the good performance due to only use solutions in the promising region to build the models (but I think GP would work well with all data as in the setting considered in this work)? Or because LaMOO restricts the search in the region close to the current best non-dominated solutions (then what is the relation to the trust-region approach [10])?
 
- **Exploitation v.s. Exploration:** With LaMOO, the solutions can only be selected from the most promising region (e.g., around the current Pareto front), which is good for exploitation. However, will this approach lead to worse overall performance due to the lack of exploration (e.g., cannot find more diverse Pareto solutions far from the current Pareto front)?

**4. Time Complexity:**

What is the time complexity of the proposed algorithm? In each step of LaMOO, it has to repeatedly calculate the hypervolume of different regions for promising region selection. However, the computation of hypervolume could be time-consuming, especially for problems with many objectives (e.g., >3). Would it make LaMOO impractical for those problems?

**5. Inaccurate Description for MOO Methods:**

- **CMA-ES:** CMA-ES is a widely-used single objective optimization algorithm [11]. The multi-objective version proposed in (Igel et al., 2007a) is usually called MO-CMA-ES. It is also confusing why most citation for the MO-CMA-ES (in the main paper and Table 1) is for the steady-state updated version (Igel et al., 2007b) but not for the original paper (Igel et al., 2007a).

- **ParEGO:** The seminal algorithm proposed in Knowles (2006) is called ParEGO and the qParEGO is a parallel extension recently proposed in Daulton et al. (2020). It is not suitable to refer the algorithm in Knowles (2006) as qParEGO in Table 1 and the main text.

- **MOEA/D:** In my understanding, MOEA/D is suitable for many objective optimization (objectives > 3), see its performance in the NSGA-III paper (Deb & Jain, 2014), while the main challenge is how to specify the weight vector for a new problem with unknown Pareto front as correctly pointed out in this work. 

- **Hypervolume-based Method:** This work indicates the indicator-based method is better for many objective optimization. However, the time complexity and expensive calculation could make the hypervolume-based method impractical for many-objective optimization.

*Experiment:*

**6. Missing Experimental Setting:** 

Many important experiment settings are missing in this work, such as the number of initial solutions for MOBO (and its generation method), the number of batched solutions for MOBO (e.g., q), the reference point for hypervolume (during the optimization, and for the final evaluation), the ground truth Pareto front used for calculating the log hypervolume difference for real-world problems (e.g., Nasbench 201).

**7. Comparison to Model-Free Evolutionary Algorithm:**

It is reasonable that LaMOO can improve the MO-CMA-ES performance since it builds extra models to allocate computation to the most promising region. However, in my understanding, the model-free evolutionary algorithms are not designed for expensive optimization, and their typical use case is with a large number of cheap evaluations with a fast run time. It is more interesting to directly compare LaMOO with other model-based methods (e.g., MO-CMA-ES with GP models).  

**8. MOBO Performance:** 

What are the hyperparameters for qEHVI? It seems its performance on VehicleSafty problem is worse than those reported in the original paper Daulton et al. (2020). 

**9. Wall Clock Run Time:** 

Please report the wall clock run time for both LaMOO and other model-free/model-based algorithms, as in Daulton et al. (2020). 


**Minor Issues:**

When citing multiple works, please put them in chronological order.

**Reference:**

[1] Hashimoto, Tatsunori, Steve Yadlowsky, and John Duchi. Derivative free optimization via repeated classification. AISTATS 2018.

[2] Kumar, Manoj, George E. Dahl, Vijay Vasudevan, and Mohammad Norouzi. Parallel architecture and hyperparameter search via successive halving and classification. arXiv:1805.10255.

[3] Yu, Yang, Hong Qian, and Yi-Qi Hu. Derivative-free optimization via classification. AAAI 2016.

[4] Munos, Rémi. Optimistic optimization of a deterministic function without the knowledge of its smoothness. NeurIPS 2011.

[5] Ziyu Wang, Babak Shakibi, Lin Jin, and Nando de Freitas. Bayesian multi-scale optimistic optimization. AISTATS 2014.

[6] Kenji Kawaguchi, Leslie Pack Kaelbling, and Tomas Lozano-Perez. Bayesian optimization with exponential convergence. NeurIPS 2015.

[7] Loshchilov, Ilya, Marc Schoenauer, and Michèle Sebag. A mono surrogate for multiobjective optimization. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, 2010.

[8] Seah, Chun-Wei, Yew-Soon Ong, Ivor W. Tsang, and Siwei Jiang. Pareto rank learning in multi-objective evolutionary algorithms. In 2012 IEEE Congress on Evolutionary Computation, 2012.

[9] Pan, Linqiang, Cheng He, Ye Tian, Handing Wang, Xingyi Zhang, and Yaochu Jin. A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization. IEEE Transactions on Evolutionary Computation 2018.

[10] Daulton, Samuel, David Eriksson, Maximilian Balandat, and Eytan Bakshy. Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces. arXiv:2109.10964, 2021.

[11] Hansen, Nikolaus, and Andreas Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 2001.

[12] Ishibuchi, Hisao, Yu Setoguchi, Hiroyuki Masuda, and Yusuke Nojima. Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes. IEEE Transactions on Evolutionary Computation 21, no. 2 (2016): 169-190.




summary_of_the_review: This work tackles an important research problem that could be useful for different partitioners in the community (e.g., multi-objective optimization, Bayesian optimization, and NAS). The proposed method is a reasonable generalization from the LaMCTS method. However, due to the concerns listed above on both the method and the experimental results, I cannot give a clear acceptance to the current manuscript.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper presents a learning space partitions-based multi-objective optimization framework by using Monte Carlo tree search and an innovatively proposed metric, i.e., dominance number. Solid theoretical analysis on single-objective optimization (SOO) and some observation on multi-objective optimization (MOO) for the space partitions are given. Extensive experiments are conducted based on synthetic functions, vehicle safety problem, Nasbench201 neural architecture search problem, and molecular design. Comparative results with other baselines show the superiority and effectiveness of the proposed LaMOO.
main_review: This paper seems to be the first work by extending the space-partition approach for SOO to MOO. The metric of dominance number is reasonable and easy-to-follow. This paper is well organized, with good background understanding and proper motivations. Sufficient theoretical analysis and experimental demonstration are provided.
However, this paper still suffers from the issue of insufficient presentation. Some revisions are need to further improve the quality of the paper, listed as:
1.	The full name of UCT should be given.
2.	In Algorithm 1, the sample budget T is used as the termination condition. But it is unclear how to set it in the experiments.
3.	The computational overhead of LaMOO is not very clear. It is better to give a time complexity analysis for LaMOO.
4.	In LaMOO with CMA-ES, the generated solution is constrained to be within the leaf region, but how? In addition, if such a constrain is frequently implemented, does it deteriorate the search efficiency?
5.	It is unclear why the optimization dimension of Nasbench201 is 6. More interpretations are needed.
6.	In page 8, the authors said there are 1000 samples given for three different tasks. But in Fig. 4, only 200 samples are shown. Why?
7.	How to set Cp when HV_max is unknown?
8.	Please have your submission proof-read for English style and grammar issues. For example, there are syntax errors in “LaMOO+qEHVI achieve”, “Thanks to MCTS, LaMOO also considers …are given 1000 samples”, “LaMOO help”, “to performs”, just mention a few. 
9.	The paper “Learning space partitions for path planning” was cited twice. 

summary_of_the_review: A good paper with clear motivation, interesting idea, solid theoretical and experimental demonstration, but some presentations are not very clear.
review_title: null

Meta-review: Multi-objective learning is an increasingly important topic. This paper presents a method for better finding parts of the Pareto frontier through a new method to estimate the distance to the frontier and use this proxy to refine the state space partition.  The reviewers found this paper interesting and compelling and generally well written. The reviewers also thought the work could be further improved by better clarifying in the text where the proposed approach might fail, and what properties of the domain are needed, and also to better situate this paper within the related work, potentially including additional experimental comparisons. The authors provided detailed responses to the proposed questions and the authors are encouraged to ensure that these suggestions and discussions are well represented in the revised version.
Decision: Accept (Poster)