Multi-Objective Multi-Solution Transport

Thank you for your review on MosT. We appreciate the opportunity to address your concerns and provide additional insights to enhance the understanding of our work.

Q1. Why not use a Pareto set learning (PSL) model?

• We acknowledge the existence of techniques like PSL. However, MosT was designed with a focus on handling problems with a large number of objectives (i.e., $n\ll m$, much more than the number of models), aiming for a comprehensive exploration of the Pareto front. We are open to discussing this further and would appreciate any specific objections or concerns you may have.

Q2. Optimal Transport (OT) vs. Divergence Measures:

• The choice of OT over other divergence measures was motivated by its ability to capture structural relationships between objectives, which cannot be provided by divergence measures.

Q3. Issues on non-smooth solutions:

• The weights assigned by Optimal Transport (OT) exhibit inherent smoothness properties. The optimization process guided by OT involves finding a transport plan that minimizes the loss while satisfying the marginal constraints. This characteristic ensures that the weights smoothly transition between different solutions, contributing to the overall smoothness of the optimization landscape. As a result, MosT benefits from the inherent smoothness of the OT weights, mitigating non-smooth and discontinuous behavior in the optimization process. This contributes to the algorithm's ability to handle a wide range of objective landscapes, promoting stability and reliability across diverse problem scenarios.

Q4. EPO Implementation:

• We compare the algorithms using their original implementations and a consistent experimental setup, including the use of reference points and the number of solutions. The performance gap may come from the fact that EPO needs to sample an extensive number of preference vectors (~100) and SVGD needs diverse initializations (~50). Comparing their numbers with our limited number of solutions (5 for ZDT problems), these two algorithms cannot work as reported. These results show the efficiency of MosT, which does not rely on diverse sampling to achieve well-distributed solutions over the Pareto fronts.

Q5. LS should perform well on MNIST/FMNIST because its PF is convex:

• Due to data heterogeneity and the large number of clients/objectives, it is unlikely that the Pareto front of FEMNIST (using the convolutional neural network) is convex.

Q6. The intuition behind weighted MGDA (Eq.4):

• By the definition of Pareto optimality, the Pareto optimal solutions identified for weighted objectives remain Pareto optimal for the original unweighted problem if all weights are positive. That being said, the weight vector for each model per step guides the MGDA to pursue solutions at a specific region of the Pareto front, similar to a reference/preference vector. Hence, different weight vectors lead to different solutions.
• OT-weighted MGDA leads to complementary and balanced solutions, due to the two marginal constraints in OT, which enforce the balance among the $m$ solutions and a fair coverage over all the $n$ objectives. A detailed explanation is provided in General Response #2. This controlled weighting achieves a delicate balance, uncovering solutions that uniquely contribute to a diverse and complementary Pareto front.

Q7. Distribution of Final Solutions:

• We have shown the distribution in Figure 1.

Q8. Computational Efficiency and OT Implementation:

• Optimal transport (OT) only costs a tiny fraction of the total runtime in MosT. Moreover, when compared to alternatives such as linearization and EPO, MosT remains more efficient overall. For comprehensive details and specific values of the runtime, please refer to General Response #3.

We hope these clarifications address your concerns and contribute to an improved understanding of MosT.

Sincerely,
Authors of Paper #8707

Another missing work is "Multi-Objective Deep Learning with Adaptive Reference Vectors", which use a similar bi-level optimization method by maximizing the hv. Since this paper seems that directly optimize the hv. This method should have better hv than Most. Since Most does not directly optimize hv.

Thanks for pointing out the work! We will look into it and discuss it in our paper. Since we cannot find the source code of the paper online, it might be hard to provide an empirical comparison with it within a short time.

That being said, most HV optimization methods only work for small-$n$ cases ($n$=2 or 3 objectives). They usually CANNOT scale to large-$n$ and $n\gg m$ cases with hundreds to thousands of objectives, which are the main focus of this paper and the gap we aim to bridge. The computation of HV and its gradient may also suffer from the curse of dimensionality when $n$ is large.

In Table 4 of the paper you mentioned, they already claimed that their method is hard to scale to merely $n=15$ objectives. Quoted from Table 4's caption, "GMOOAR-HV cannot be run on 15 tasks as it takes more than a month on our machine." In contrast, in Section 5.3 of our paper, MosT can easily scale to $n>200$ objectives.

Q1. What are the current chosen preferences?

The preference vectors used for EPO are generated using the exact pipeline as outlined in the official implementation of EPO (https://github.com/dbmptr/EPOSearch/blob/master/mtc/epo_train.py). That is, we follow the same process described as the "tricky way" in your review. We are committed to providing the implementation details of MosT, as well as all baseline methods, upon publication.

Q2. It seems that other solution is dominated by the proposed method on all objectives.

In Figure 2(c), we are not displaying the performance gap for each objective separately but rather for groups of objectives. So, the figure does not suggest that MosT dominates other solutions on all objectives. What it illustrates is that MosT outperforms the baselines by a larger margin for clients with worse performance. This underscores MosT's role in promoting fairness in federated learning by delivering superior results for those clients facing greater challenges.

Q3. Why does MosT win a lot in federated learning?

This is because we keep optimizing the assignment of solutions (models) to objectives (clients) in the training stage (by OT), while other methods do not optimize the assignments at all.

5. Experiment

Q5.1 Constraints in ZDT Problems and performance of EPO and SVGD:

• All algorithms in the experiments, including MosT, are originally designed to handle unconstrained multi-objective optimization problems. To enforce the constraints in the ZDT problem, all algorithms perform projected gradient descent, i.e., by clipping the variables back to [0,1] in every step if necessary. This operation ensures the fairness of the comparison and the constraints.

• We compare algorithms with their original implementations and consistent settings, including the same reference point and the same number of solutions. The performance gap may come from the fact that EPO needs to sample an extensive number of preference vectors (~100) and SVGD needs diverse initializations (~50). Comparing their numbers with our limited number of solutions (5 for ZDT problems), these two algorithms cannot work as reported. These results show the efficiency of MosT, which does not rely on diverse sampling to achieve well-distributed solutions over the Pareto fronts.

Q5.2 Realistic Application Problems with a Large Number of Objectives:

• Expansion to Multi-Task Learning Scenarios: We appreciate your suggestion to include more realistic application scenarios with a higher number of objectives. In response, we have expanded our experiments to include multi-task learning scenarios with two real datasets (n = 4 and 6, resp) and showed promising results. This addition aims to provide a more diverse and comprehensive evaluation of MosT's performance across different application domains. Detailed results and analysis are available in Appendix E and General Response #4.1.

Q5.3 Runtime Comparison:

• In response to your feedback, we have included detailed runtime metrics for MosT and other algorithms over two real datasets, detailed in General Response #3. The results show that MosT is more efficient compared to linearization and EPO, and comparable to MGDA.

Sincerely,
Authors of Paper #8707

References:
[1] Xie Y, Wang X, Wang R, et al. A fast proximal point method for computing exact wasserstein distance. Uncertainty in artificial intelligence. PMLR, 2020: 433-453.
[2] Cuturi M. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 2013, 26.
[3] Liu X, Tong X, Liu Q. Profiling pareto front with multi-objective stein variational gradient descent. Advances in Neural Information Processing Systems, 2021, 34: 14721-14733.
[4] Wang H, Deutz A, Bäck T, et al. Hypervolume indicator gradient ascent multi-objective optimization. Evolutionary Multi-Criterion Optimization: 9th International Conference, EMO 2017, Münster, Germany, March 19-22, 2017, Proceedings 9. Springer International Publishing, 2017: 654-669.
[5] Deist T M, Grewal M, Dankers F J W M, et al. Multi-objective learning to predict pareto fronts using hypervolume maximization. arXiv preprint arXiv:2102.04523, 2021.

2. Gap between MosT and the Metrics

Q2.1 Why not directly use gradient-based hypervolume maximization to find the solution set?

While gradient-based hypervolume maximization is effective for a small number of objectives, MosT is effective in both less-dimensional and high-dimensional scenarios. Combining multi-gradient descent algorithms with optimal transport, MosT navigates high-dimention Pareto front efficiently.

Additional, we want to highlight challenges with direct hypervolume maximization [3], facing issues such as dependence on reference points and susceptibility to bad local minima [4,5].

Q2.2 It is unclear why "During later stages, ..., every objective has to be covered by sufficient models (solutions)."

During later stages, the uniformity of objective marginals, coupled with performance-based solution marginals, enables each objective to select its best-performing solution(s).

We acknowledge that objectives may be covered by different optimal solutions, raising concerns about potential mutual exclusivity. However, MosT aims to harmonize these contributions rather than enforce exclusivity. MosT strategically balances marginal distributions in later stages as described. This design ensures that even if a solution excels on specific objectives, the overall objective coverage remains diverse and robust.

Q2.3 In addition, the final metric we care about is the mean(std) of average performance across all objectives (e.g., Table 2). Once the groups of objectives covered by different solutions are determined, why not just use simple uniform linear scalarization to optimize all objectives for each group?

Our main interest is in achieving diverse and complementary assignments from solutions to objectives, not just in terms of average accuracy. We want to make sure our solutions cover various objectives effectively.

Note that, even within the same group you mentioned, objectives may exhibit varying characteristics and trade-offs. Consequently, a one-size-fits-all approach, such as simple uniform linear scalarization, might not capture the intricacies of each objective grouping. In addition, such alternative approaches require additional design, such as stopping criteria, which can increase the complexity of the algorithm. In contrast, MGDA tailors the optimization process to the specific characteristics of each group. This fine-grained optimization approach ensures that each objective's contribution is considered with the attention it deserves.

3. Time Complexity

We acknowledge the importance of this aspect and have provided a detailed analysis in General Response #3. In summary, optimal transport constitutes only a small fraction of the total runtime in MosT. Moreover, when compared to alternatives such as linearization and EPO, MosT remains more efficient overall. For comprehensive details and specific values, please refer to General Response #3.

4. Extension to Few Objective Case (n<<m)

We empirically show that a relatively small $n'$ for interpolations of a few (i.e., $n$) original objectives is sufficient to achieve adequate performance. In the accuracy-fairness tradeoff ($n=2$), we conducted experiments sweeping over $n'\in \{10, 20, 30, 40, 50\}$. Our results indicate that utilizing $n' = 10$ yields comparable performance to those larger $n'$, as clarified in Appendix D.3. Consequently, we adopted the smaller $n' = 10$ in our experiments, obtaining the final results reported in Table 3.

1. Motivation

Q1.1 What is the relation of the Pareto sets for the problems with weighted objectives (1) with the Pareto set of the original unweighted problem? How the (optimal) weighted problem can lead to a set of "different but complementary and balanced" solutions that best cover all objectives?

By the definition of Pareto optimality, the Pareto optimal solutions identified for weighted objectives remain Pareto optimal for the original unweighted problem if all weights are positive. That being said, the weight vector for each model per step guides the MGDA to pursue solutions at a specific region of the Pareto front, similar to a reference/preference vector. Hence, different weight vectors lead to different solutions.

The complementary and balanced solutions are enforced through the weights achieved by OT and they are mainly due to the two marginal constraints in OT, which enforces the balance among the $m$ solutions and a fair coverage over all the $n$ objectives. This controlled weighting achieves a delicate balance, uncovering solutions that uniquely contribute to a diverse and complementary Pareto front.

Q1.2 If there is a set of optimal weights that can lead to a set of optimally distributed solutions, what properties such a set of weights should have? Is it unique? Why such optimal weights (if they exist) can be found by OT (e.g., eq.(2)) is also not clearly discussed.

Optimal weights in MosT are expected to achieve diverse and complementary assignments from solutions to objectives. The solution to entropic optimal transport, as employed in MosT, is unique [1]. OT seeks a transportation plan that minimizes loss (complementary) while meeting the marginal constraint (diversity) [2]. This offers a clear connection between the principles of OT and the optimal weights needed in MosT.

Q1.3 Why the (uncontrollable) solutions found by MGDA for each weighted problem (1) can be guaranteed to be complementary and evenly distributed?

MosT combines MGDA with strategic weight assignment for a balanced exploration of the Pareto front. While MGDA itself may not guarantee the location of solutions, the reweighted objective (with weights 'controlled' by OT) ensures that the algorithm converges to solutions that cover different regions of the Pareto front. The weights assigned to objectives are derived through Optimal Transport (OT), introducing a controlled and strategic weighting mechanism. This weighting process ensures that the solutions found by MGDA are not arbitrary but guided by a deliberate assignment of weights.

Thank you for your detailed response and additional experiments. However, many of my concerns remain.

1. Motivation: Many claims are not solid and not well-supported, such as "the weight vector for each model per step guides the MGDA to pursue solutions at a specific region of the Pareto front, similar to a reference/preference vector" and "this weighting process ensures that the solutions found by MGDA are not arbitrary but guided by a deliberate assignment of weights".

In MosT, the MGDAs can reach any Pareto optimal solution of each weighted problem, which is exactly the same Pareto optimal set of the original problem. In other words, the current theoretical guarantee of MosT is not stronger than the original MGDA. The reason why MosT can be ensured to find a set of diverse Pareto solutions does not have proper theoretical support.

2. Metrics: My main concern here is to clearly show why the solution set found by MosT can outperform other algorithms on different criteria for both the (n<<m) and (n>>m) cases with theoretical analysis.

3. Time Complexity: It is counter-intuitive to see linear scalarization require more runtime than MGDA. What is the computational overhead of linear scalarization over MGDA? In addition, since the main motivation for MosT is to address the problem with a much larger number of objectives (n >> m), the runtime comparison under this setting (e.g., with n = 205) is much more important.

5.1 Toy Problems: An immediate follow-up question is why compare all unconstrained multi-objective optimization algorithms on a set of constrained problems?

In addition, to my understanding, EPO is an exact preference-based optimization method, and the quality of each solution is agnostic to the number of preference vectors. Even only given a single preference vector, under a set of reasonable assumptions, EPO can also successfully find the Pareto solution with the specific trade-off. Therefore, EPO should work fine with 5 given preference vectors. The claim "EPO needs to sample an extensive number of preference vectors (~100)" is questionable.

5.2 More Problem with Large Number of Objectives: The main motivation for MosT is to handle the problem with a large number of objectives (e.g., m << n = 200). The added experiments with a small number of objectives (e.g., n = 4 and 6) are still far from the main motivation. Is it very hard to find a practical application for the n >> m setting?

In addition, recent works on MTL and multi-domain learning have shown that simple linear scalarization with proper regularization can perform comparably with advanced methods such as MGDA [4,5,6]. The linear scalarization is also fast and will not suffer from a large computational overhead for problems with many tasks (e.g., a large n) as considered in this work. Why is the performance of linear scalarization much worse than MGDA in the new experiments with a large gap?

[1] In Defense of the Unitary Scalarization for Deep Multi-Task Learning. NeurIPS 2022.

[2] Do current multi-task optimization methods in deep learning even help. NeurIPS 2022.

[3] Scalarization for Multi-Task and Multi-Domain Learning at Scale. NeurIPS 2023.

5.3 Runtime Comparison: Please report the runtime for the n >> m setting (e.g., n = 200).

Thanks to Reviewer SZEd for the insightful comments, and we provide our response below.

Q1. Why is $\epsilon$ needed in Algorithm 1?

Setting $\epsilon$ to be a small non-zero constant guarantees that any Pareto solutions for the re-weighted objective in Eq.(5) are also Pareto solutions for the original unweighted problem. Empirically, we found that it also provides numerical stability during the optimization process. Its effectiveness is also supported by our convergence, which incorporates a non-zero $\epsilon$. We will add more details in the revision.

Q2. Comparison with MGDA using diverse weight vectors $m$ times.

Following your suggestion, we conduct an ablation study in the context of federated learning with $n\gg m$, in order to compare MosT and MGDA with $m$ different weight vectors for $n$ objectives. Our ablation study shows MosT with OT-generated weights achieves higher accuracy averaged across all objectives than the MGDA alternative. This indicates the importance of optimal transport in simultaneously balancing multiple solutions and multiple objectives. Comprehensive details and results are available in Appendix C.3 and General Response #4.2.

Q3. Comparison with Previous Literature on Computational Aspects.

In our method, the number of solution $m$ is a predefined constant, while MosT aims to maximize their usage and fully exploit their capacity by the optimal transport assignment to the $n$ objectives. This leads to better model efficiency, for example, when $n\gg m$. In contrast, previous work usually requires the number of models $m$ to grow linearly or exponentially with $n$, without explicit optimization of their matching. Hence, our design aligns well with the practical need of computational efficiency and model efficiency. It also leads to scalability and computational tractability in scenarios with a large number of objectives ($n\gg m$). In General Response #3, we provide the end-to-end running time of our method and the baselines under the same $m$, showing that MosT is able to result in better solutions more quickly.

We hope these responses address your concerns and provide further clarity on the contributions of our work.

Sincerely,
Authors of Paper #8707

We express gratitude to Reviewer bAug for the evaluation of our submission. While we respect your perspective, we aim to address concerns and provide clarifications.

Q1. Literature Review:

• Our literature review in Section 2 did include discussions on Evolutionary Computation (EC) methods. We also compared MosT with SVGD [1], a recent approach that evolutionarily updates particles towards the Pareto front. Specifically, EC methods can be inefficient in practical MOO problems due to the absence of gradient information [1-3] and the poor exploration in high-dimensional spaces (when the number of objectives is large). This distinction positions our approach, which leverages gradient-based techniques, as a more suitable and efficient alternative.

• Question: Could you please specify which literature is missing?

Q2. Novelty and Significance:

• Our primary contributions and novelty: (1) the novel task and problem formulation of multi-objective multi-solution transport; (2) addressing a unexplored class of challenging problems when $n\gg m$ (but also appliable to cases when $n\ll m$); (3) intuitive and effective MosT algorithm; (4) thorough empirical evaluation on a diverse set of machine learning problems. Specifically, the marginal constraints in Optimal Transport (OT) are essential to achieve a balanced solution-objective matching, leading to a diverse and complementary ensemble of solutions.

• Question: Could you please specify which literature has explored our method?

Q3. Experimental Setup:

• The details of the experimental setup are introduced in Section 5.1, and additional information is provided in Appendix D for a more comprehensive understanding.

• Question: Could you please specify which part of the experimental setup is considered missing?

Q4. Results Significance:

MosT proves its application across federated learning, fairness-accuracy trade-offs, and multi-task learning (new to rebuttal) with multiple real datasets and also synthetic datasets.

• Our dataset selection aligns with established practices from previous papers in federated learning [4] and multi-objective optimization [1].
• In the new version, we have expanded our experiments to real-world datasets for multi-task learning, providing a more comprehensive evaluation for $2\leq n\ll m$ cases. Detailed results and analysis are available in Appendix E. We will discuss this in the manuscript to underscore the significance of our findings.

In conclusion, we appreciate the opportunity to address these concerns and are committed to enhancing the clarity and completeness of our manuscript based on your valuable feedback.

Sincerely,
Authors of Paper #8707

References:
[1] Liu X, Tong X, Liu Q. Profiling pareto front with multi-objective stein variational gradient descent. Advances in Neural Information Processing Systems, 2021, 34: 14721-14733.
[2] Mahapatra D, Rajan V. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. International Conference on Machine Learning. PMLR, 2020: 6597-6607.
[3] Momma M, Dong C, Liu J. A multi-objective/multi-task learning framework induced by pareto stationarity. International Conference on Machine Learning. PMLR, 2022: 15895-15907.
[4] Li T, Sahu A K, Zaheer M, et al. Federated optimization in heterogeneous networks[J]. Proceedings of Machine learning and systems, 2020, 2: 429-450.

We extend our sincere thanks to Reviewer YDRF for the insightful evaluation of our submission. We are encouraged by your recognition of the significance of our work in exploring a high-dimensional Pareto frontier. We hope the following replies resolve the concerns raised in your review.

Q1. "Are there experiments conducted with more than 2 objectives? Did the solution converge when n increased to 3 or 5?"

Following your suggestion, we've expanded our experiments to include multi-task learning scenarios with n << m and varying numbers of objectives beyond two ($n=4 \text{ and } 6$). Results show that MosT achieves promising performance over baselines, supporting the versatility of our proposed framework as n increases. Detailed results and analysis are available in Appendix E of the revised manuscript and also in General Response #4.1.

Q2. "What type of solver used to run needs to be detailed out."

We utilize IPOT [1] as an off-the-shelf OT solver for Eq.(2) and a min-norm solver (based on a Frank-Wolfe algorithm) used by the vanilla MGDA [2] for optimizing Eq.(1), as mentioned in Section 3. We found that these solvers are effective in handling the complexities of our proposed optimization tasks.

Q3. (also mentioned in [Weakness]) "Keen to understand federated learning in detail, how do clients receive training, and what's the effect of the number of local samples (vi)?"

Thanks for your question. Clients perform training by running local SGD updates, similar to standard federated optimization methods.

In response to your suggestion, we conducted experiments that involved varying numbers of local samples per client—specifically, 50, 75, and 100—utilizing the synthetic federated learning dataset. Experiments consistently demonstrated MosT's superior performance compared to all baseline methods, as shown in the table below. Notably, MosT exhibited greater efficacy, particularly with smaller local sample sizes, outperforming the best baseline (MGDA).

Sincerely,
Authors of Paper #8707

References:

[1] Xie Y, Wang X, Wang R, et al. A fast proximal point method for computing the exact Wasserstein distance. Uncertainty in artificial intelligence. PMLR, 2020: 433-453.
[2] Désidéri J A. Multiple-gradient descent algorithm (MGDA) for multiobjective optimization. Comptes Rendus Mathematique, 2012, 350(5-6): 313-318.