MoSH: Modeling Multi-Objective Tradeoffs with Soft and Hard Bounds

Authors: Edward Chen, Natalie Dullerud, Thomas Niedermayr, Elizabeth Kidd, Ransalu Senanayake, Pang Wei Koh, Sanmi Koyejo, Carlos Guestrin
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords: multi-objective, multi-criteria, decision-making, preference learning, bayesian optimization

Abstract:
Countless science and engineering applications in multi-objective optimization (MOO) necessitate that decision-makers (DMs) select a Pareto-optimal solution which aligns with their preferences. Evaluating individual solutions is often expensive, necessitating cost-sensitive optimization techniques. Due to competing objectives, the space of trade-offs is also expansive --- thus, examining the full Pareto frontier may prove overwhelming to a DM. Such real-world settings generally have loosely-defined and context-specific desirable regions for each objective function that can aid in constraining the search over the Pareto frontier. We introduce a novel conceptual framework that operationalizes these priors using $soft-hard functions$, SHFs, which allow for the DM to intuitively impose soft and hard bounds on each objective -- which has been lacking in previous MOO frameworks. Leveraging a novel minimax formulation for Pareto frontier sampling, we propose a two-step process for obtaining a compact set of Pareto-optimal points which respect the user-defined soft and hard bounds: (1) densely sample the Pareto frontier using Bayesian optimization, and (2) sparsify the selected set to surface to the user, using robust submodular function optimization. We prove that (2) obtains the optimal compact Pareto-optimal set of points from (1). We further show that many practical problems fit within the SHF framework and provide extensive empirical validation on diverse domains, including brachytherapy, engineering design, and large language model personalization. Specifically, for brachytherapy, our approach returns a compact set of points with over 3\% greater SHF-defined utility than the next best approach. Among the other diverse experiments, our approach consistently leads in utility, allowing the DM to reach $>$99\% of their maximum possible desired utility within validation of 5 points.

Decision: reject
Reviewer scores: 5, 3, 5, 3

Reviews and discussion:
<thread>
creation date:
1729737354165

thread_type:
official_review

<thread_object>
creator: reviewer_wjhw

<content>
summary:
The authors proposed a two-step framework for MOO that incorporates user defined soft and hard bounds on objectives and generates a compact set of Pareto optimal solutions for human decision makers to review. The framework consists of 

1. MoSH-Dense: a Bayesian optimization approach using random scalarizations and soft-hard functions to densely sample the Pareto frontier. 
2. MoSH-Sparse: a submodular optimization method that is robust to unknown human preference, to select a small, diverse subset of solutions from the dense set.

The authors evaluated this framework on a set of synthetic problems and real-world applications, including brachytherapy treatment planning, and showed merit of this method.

strengths:
Originality:
1. This approach creatively incorporates the concepts of hard constraints and soft preferences into BO formulation, providing a more nuanced way to express decision-maker preferences.
2. The two-step framework is more user friendly: through sparcification of the originally found Pareto optimal solutions, it is easier for human DMs to pick the solutions to their preferences. Therefore, I would image there is fair amount of practical usage of this approach.

Quality:
1. This paper provides comprehensive theoretical analysis of the MoSH-Sparse algorithm, with provable guarantees on the near-optimality of the selected sparse set.

Clarity:
1. I think this paper is pretty well structured, and the proposed method is clearly presented.

Significance:
1. MoSH addresses a practical challenge in MOO by providing a way to generate a small but diverse set of solutions that respect user defined constraints. This has great potential impact to MOO applications.

weaknesses:
1. The algorithmic novelty is fairly limited: for the dense sampling procedure, the primary modification is the incorporation of SHFs into the acquisition function, while the rest largely follow existing techniques from Paria et al (2019). The sparcification procedure follows standard active learning approach. While the problem formulation is novel and interesting, I do not think there is enough methodological innovation to meet the high standard of ICLR.

2. The paper lacks discussion of design choices of SHFs given it is quite important in the proposed method. Specifically, is it the case that decision-makers are always able to meaningfully specify soft and hard bounds? What if the bounds are uncertain or change over the exploration of the experiments? Any alternative utility function classes other than the piecewise-linear SHF discussed in this paper, and is the overall method robust to the choice of SHFs?

questions:
1. The piecewise linear SHF seems somewhat arbitrary. Have you explored other functional forms, and what motivated this particular choice? The reasons need to be justified.

2. For the brachytherapy application, please add discussion about how the clinical experts use this system and their feedback. Additionally, compared with other MOO interactive solutions mentioned in this paper’s related works section, what is the advantage of using the proposed method here instead of those interactive mechanisms? The experiment section lacks comparisons against those interactive MOO methods.
</content>
</thread_object>

</thread>
<thread>
creation date:
1729966079504

thread_type:
official_review

<thread_object>
creator: reviewer_qibo

<content>
summary:
This paper considers when performing multi-objective optimization, for each objective $f(x)$ there is a soft lower bound $\alpha_{lS}$ that is ideally satisfied and a hard lower bound $\alpha_{lH}$   that must be satisfied. Additionally, it proposes a max-min framework for scalarization-based multi-objective optimization, aiming to find solutions that are robust against variations in the scalarization weights $\lambda$ within a bounded set $\Lambda$ to enhance solution diversity. 

The paper first proposes to leverage a pice-wise linear scalarization function to incorporate the soft and hard objective constraints. For the max-min formulation of optimization, given the computational challenges of directly solving the max-min problem, the paper introduces a two-step approximation process. The first step involves solving a max-average problem to generate a set of promising candidate solutions. The second step refines this set by removing points that do not significantly affect the worst-case utility ratio, leveraging the submodular properties of the utility function to apply the Robust Submodular Observation Selection (RSOS) framework and the submodular saturation algorithm.

The proposed algorithm is empirically tested on synthetic and real-world problems, demonstrating its practical applicability.

strengths:
- The paper presents an interesting problem of multi-objective optimization considering soft and hard lower bounds.
- Perhaps the more interesting thing is the max-min framework to achieve robustness against user preference weights is novel, which might provide a new perspective of enhancing diversity in Pareto frontier search. 
- The practical approximation using a two-step process and leveraging submodular optimization techniques is sound, as it offers a feasible solution to an otherwise intractable problem.

weaknesses:
- Theoretical Analysis: The main drawback of this paper is, though heavily constructed on relaxations/approximations, does not provide adequate theoretical insights about the method itself, to elaborate:  
    - The transformation from the max-min to the max-average problem is presented as a practical approximation, but the paper lacks theoretical analysis regarding its impact on the optimization results. Also, it is expected to be increasingly difficult for the expectation to be conducted when the number of objectives is increasing.  
    - Similarly, which might also be because of a writing issue, the relaxation to a decomposable form to apply the RSOS framework is sound but without any theoretical insight.  
     - If such analysis is non-trivial, a more pragmatic workaround could be to use some grid (or Monte Carlo) based approximation of the original min in max-min framework, such that it provides a good reference of the ground truth behavior of the original framework, but seems has not been done in the paper. 

- Clarity: 
    - All the plot quality is rather poor; please increase the size of all the image's legends and label and title font size. Also please consider avoiding snake case name style (e.g., consider avoiding using MOBO_RS_UCB_Lin)

questions:
- It seems in experiments, it is compared with other acquisition functions with step 1 only (Sec 323), I am puzzled by such a motivation here, cause this is essentially comparing max-average with other MOBO acq instead of max-min (which is originally thought to be approximated by the combination of two steps)
- The objective constraints and the scalarization weights $\mathbf{\lambda}$ are handled almost independently, however, it is natural that they should share some dependence, why this is not considered. 
- The explainability of the utility function definition: The utility function definition is more complicated than necessary at least when originally read Eq. 1, especially because of the not well-motivated saturation points, why this is needed here, is that because of the suitableness of the submodular saturation algorithm? please state it clearly after Eq. 1.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730757281173

thread_type:
official_review

<thread_object>
creator: reviewer_vzpb

<content>
summary:
The authors consider sampling the Pareto frontier of a multi-objective optimization problem. They first sample the Pareto frontier by random scalarizations (which does not seem to come with any guarantees, at least for non-convex problems). Subsequently, they "sparsify" the sample. They show that for some preferences lambda, the latter problem is submodular and propose to use an algorithm of Krause for robust submodular observation selection (JMLR, 2008).

strengths:
The problem is of considerable practical interest.

weaknesses:
The paper is rather confusingly written. While the method does not come with any guarantees overall, the fact may be lost on the casual reader. 

The empirical results are not convincing. Specifically, the comparison does not utilize any standard benchmarks, such as the one from CEC 2009 (Zhang et al. 2008). 

The comparison does not extend to any methods with overall guarantees, e.g., by Christos Papadimitriou and Mihalis Yannakakis (e.g., https://dl.acm.org/doi/10.1145/375551.375560, https://link.springer.com/chapter/10.1007/3-540-44634-6_1). 

The "Related work" discussion is rather biased and methods with overall guarantees are not even cited.

questions:
How would your performance compare to the performance of the methods of Christos Papadimitriou and Mihalis Yannakakis (e.g., https://dl.acm.org/doi/10.1145/375551.375560, https://link.springer.com/chapter/10.1007/3-540-44634-6_1), or at least to the guarantees they have?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730970989008

thread_type:
official_review

<thread_object>
creator: reviewer_mtmt

<content>
summary:
The paper proposes incorporating real-world constraints into multi-objective optimization tasks by converting the reward function into a newly introduced soft-hard function (SHF). Existing Multi-Objective Bayesian Optimization algorithms and Greedy Submodular Partial Cover algorithms are then employed to achieve sparse coverage of the Pareto frontier with respect to the introduced SHF utility ratio.

strengths:
a. The algorithm is motivated by real-world applications, with a careful illustration of the objective design.

b. The sample efficiency and sparsification efficiency are justified with theoretical analysis and empirical results on various tasks.

weaknesses:
a. Questionable Necessity of SHF Utility Ratio: The necessity of introducing the SHF utility ratio is debatable. The algorithm essentially aims to offer sparse coverage of the Pareto frontier. Existing work by Zuluaga et al. (2016), as mentioned by the authors, focuses on sample-efficient identification of the $\epsilon$-accurate Pareto set. The notion of an $\epsilon$-accurate Pareto set is a more principled and interpretable objective for sample-efficient algorithms. I respectfully disagree with the authors' claim that it resembles hypervolume-based heuristics.

b. Limited Novelty of the Proposed Algorithm: The novelty of the proposed algorithm is arguable. The algorithm essentially converts the multi-objective optimization objective using the introduced SHF utility function to incorporate constraints, and the SHF utility ratio measures the coverage of the SHF Pareto frontiers. Beyond these introduced notions, components like random scalarization, the Bayesian Optimization acquisition procedure, and submodular optimizations, along with their theoretical results, are mostly off-the-shelf. Additionally, the use of existing methods—especially the MOBO algorithm by Paria et al. (2019) and the GPC algorithm by Krause et al. (2008)—is not clearly stated in the main paper but deferred to the appendix.

c. Clarity and Readability Issues: There are clarity and readability issues in the current presentation. Key components of the algorithm, including Algorithm 3 and the acquisition function, are deferred to the appendix, which hinders understanding. Furthermore, the figures, especially those in Section 5, need to be polished for better readability.

d. Classification of Related Work: A minor point—another reference by Malkomes et al. (2021) is arguably classified as a Level Set Estimation (LSE) method. From my perspective, it also addresses identifying sparse, diversified coverage of constrained optimal candidates.

***References***
- Zuluaga, Marcela, and Andreas Krause. "e-pal: An active learning approach to the multi-objective optimization problem." Journal of Machine Learning Research 17, no. 104 (2016): 1-32.
- Malkomes, Gustavo, Bolong Cheng, Eric H. Lee, and Mike Mccourt. "Beyond the pareto efficient frontier: Constraint active search for multiobjective experimental design." In International Conference on Machine Learning, pp. 7423-7434. PMLR, 2021.

questions:
A follow-up work by Zhang and Golovin (2020) builds on Paria et al. (2019) and could allow for a more consistent analysis in terms of optimization performance, rather than assuming Algorithm 1 offers sufficiently dense coverage. The authors might consider incorporating methods from Zhang and Golovin (2020) to improve the completeness of their analysis.

***Reference***

Zhang, Richard, and Daniel Golovin. "Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization." In International Conference on Machine Learning, pp. 11096-11105. PMLR, 2020.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732232262803

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
High-Level Comment From Authors

comment:
Thank you to all of the reviewers for your thoughtful feedback! We’ve worked to address all of your comments and questions in the individual threads and wanted to highlight two high-level points to all of the reviewers.

1. **Novelty Of Our Proposed Method**

**Our primary contribution is the novel conceptual framework of soft-hard bounds for multi-objective optimization (formalization of the problem, our proposed method, soft-hard evaluation metrics, and broad set of experiments (across cancer treatment, LLM personalization, deep learning model selection, and more), all native to this novel setting).** To the best of our knowledge, this setting has not been studied before in the multi-objective optimization setting, yet is ubiquitous in many real-world problems. As a result, we are the first to formalize this problem with a simple two-step process which returns an easily interpretable, small set of points to the user according to the soft-hard bounds they had specified. As part of this novel conceptual framework, we also introduced novel evaluation metrics which are native to this soft-hard setting – rather than reusing existing ones. We additionally rigorously evaluated our setting, both theoretically and empirically, while also introducing a novel experiment on multi-objective personalization for LLMs (which had previously not been evaluated on in the multi-objective optimization literature, but shows our setting’s broad relevance).

2. **Additional Theoretical And Empirical Analyses/Experiments**

In response to the valuable feedback, we have added the following three key changes:
- **Theoretical analyses for step 1 of our proposed method, MoSH-Dense, which guarantees its behavior** (as suggested by Reviewers mTMT, vZPB, and qibo) (Appendix A.3 of the paper)
- **Empirical results demonstrating the impact of our max-min to max-average conversion for MoSH-Dense** (as suggested by Reviewer qibo) (Appendix A.1.1 of the paper)
- **Experimental results for the novel multi-objective large language model (LLM) personalization setting** (to showcase our method’s broad applicability and novelty, as mentioned by Reviewer wJhw) (Section 5.3.2 of the paper). For the LLM experiment, we use soft-hard bounds on two competing objectives - conciseness and informativeness - and demonstrate our method's superior ability in consistently sampling output responses within such soft and hard bounds.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732911361572

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Official Comment From Authors

comment:
We sincerely thank all the reviewers for their time and effort in evaluating our work. As the updated discussion deadline approaches (Dec. 2), we would appreciate any feedback on our rebuttal, especially if there are remaining concerns that have not yet been addressed. Thank you!
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper studies multi-objective optimization, with an emphasis on incorporating soft and hard constraints into the optimization framework. The paper introduces a two-stage approach that first generates a set of potential solutions and it then refines this set by leveraging algorithms for robust submodular optimization.

The reviewers appreciated the importance of the problem studied for practical applications. The proposed approach via submodular optimization provides a sound approach for a problem that is intractable in general. The reviewers raised significant concerns regarding  the strength and novelty of the contribution and the clarity of the exposition, as detailed in the reviews. Overall, the consensus among the reviewers was that this work does not meet the high bar for acceptance.