Aligned Multi Objective Optimization

Thank you for the feedback and recognizing the positive aspects of our work. We appreciate the detailed and useful feedback. We will address the questions in their chronological order.

1. In Section 6 – where we generalize AMOO to approximate AMOO – we are not assuming a unique minimizer for all objectives. In addition, the linear convergence without dependence on the number of objectives is not natural; for example, if one chooses the weights to be uniform (1/m), the linear convergence depends on the number of objectives. Since this wasn't clear, we will add a section in the appendix that demonstrates this. Also, see section B in the appendix. Further, we believe that this work offers a new and rigorous perspective on the multi-task setting that becomes increasingly important in machine learning applications (e.g., in LLMs and RL research practitioners often use multiple reward functions or datasets).

2. It is a good question, thanks for raising it. Yes, in Section 6 we provide results for the setting in which functions are only approximately aligned, and show CAMOO and PAMOO both converge to an approximately optimal point for all objectives. The additional experiments we attached to the rebuttal corroborate these theoretical findings (see this anonymous link https://docs.google.com/document/d/e/2PACX-1vRbT_IuVcnR-RHPy95d9sIuiHa07DUmjA57HvWKjjWFUjST5udLeTUygnpnQ3AvSmiuc_y-r4JpiGYI/pub).

3. We agree that CAMOO is less practical compared to PAMOO. However, such an algorithm is very natural for the AMOO setting, given the intuition we provide in Figure 1, and gives useful intuition that may help deriving algorithmic improvements. Additionally, as the open source implementation we shared showcases, it is possible to make use of modern approaches for Hessian estimation (e.g., Hutchinson method) for implementing such an approach.

4. Our work focused on foundational work: formulating the AMOO setting, developing intuition and providing new algorithms with provable guarantees for the setting, as well as showing these algorithms are robust to the alignment assumption. The code we share with the research community showcases the feasibility of implementing the algorithms. We believe the next step of our work is conducting large-scale experiments in different domains (e.g., LLM, RL and computer vision) while also developing the theoretical foundations of the AMOO setting.

5. We also believe the stochastic setting is of interest and importance. Due to the significant contributions this work has put forward (see response to question 4) we believe such extension is proper for future work. We will expand the existing discussion on such a future extension further (see the Conclusions section) to highlight the importance of this direction. Thank you for raising this point.

Thank you for your interest in this work and the questions you raised! We will address them in their chronological order.

1. We will make the local curvature example figure clearer – thank you for pointing this out!

2. We provided results on inaccuracy of $f_i(x_{\star})$ in Section 6, where we assume the multi-objectives are only approximately aligned (we derived two results, one for the PAMOO and one for CAMOO algorithms). We conducted additional experiments, for providing additional empirical evidence, for the approximate AMOO to be included in the final version of the paper (see this anonymous link https://docs.google.com/document/d/e/2PACX-1vRbT_IuVcnR-RHPy95d9sIuiHa07DUmjA57HvWKjjWFUjST5udLeTUygnpnQ3AvSmiuc_y-r4JpiGYI/pub). Lastly, we note several prior works explored the question on designing gradient-descent based methods in which the learning rate is chosen via a Polyak method and the optimal value of a function is estimated adaptively (Hazan and Kakade 2019, Gower et al., 2021; Orvieto et al., 2022). We believe that generalizing these to the AMOO setting is a fertile ground for future research work, which we also mentioned in the main text.

Thank you for the feedback and recognizing the positive aspects of our work. We appreciate the detailed and useful feedback.

We wish to mention additional contributions of this work, beyond those that were mentioned in the review:

1. In Section 6 we study the approximate AMOO framework. There we showed that both CAMOO and PAMOO are robust to violations of the alignment assumptions (see this anonymous link https://docs.google.com/document/d/e/2PACX-1vRbT_IuVcnR-RHPy95d9sIuiHa07DUmjA57HvWKjjWFUjST5udLeTUygnpnQ3AvSmiuc_y-r4JpiGYI/pub).

2. The implementation of the CAMOO and PAMOO algorithms (see the supplementary material) showcases the feasibility of both algorithms. Additionally, our experiments go beyond the theoretical results when using neural networks with SGD or ADAM optimizers. This implementation allows future researchers to build upon our work and provides evidence for the usefulness of CAMOO and, even more so, of PAMOO, as the empirical results show.

We will address the comments in their chronological order.

References. Thank you for sharing the references. We will include them in the final draft (we also point out that reference [5] is included in the current draft and mentioned in Section 2).

Weakness (1).

1. We agree that modern machine learning applications are not well described by a convex optimization framework. Nevertheless, the design of all modern optimization algorithms – SGD, ADAM and many more – is motivated by algorithms from the convex optimization framework. For example, ADAM is intimately related to the AdaGrad algorithm, which is designed for the convex setting (see https://arxiv.org/abs/1412.6980). Similarly, we believe that establishing the correctness of optimizers in the convex optimization framework is useful towards designing practical algorithms.

Weakness Major.

1. Yes, you are correct and we will add this clarification to the paper. Since there is no tradeoff – by assumption all objectives can be simultaneously optimized – the Pareto front is a point. We provided a formal description of the general setting in Section (3), as well as a more nuanced description in Section (4) (e.g., Proposition (1) is an additional structural result about the setting).
2. In the specification example, the functions are strongly convex and smooth; for this case, the convergence of GD is (1-\Delta)^k. We will use this precise description in the text. Thank you!

Minor.

1. This is one of the interesting findings in the paper in our opinion. The convergence rate does not dependent on $m$, the number of objectives. We will add clarification about this in the caption of Table (1) as it seems it is not properly conveyed to the reader.
2. We provided a formal definition in the Appendix. We will move it to the main text for improved clarity.
3. Most practical algorithms in multi-task learning specify different ways for choosing weights to output weighted loss (e.g., "Multi-task learning as multi-objective optimization" by Sener et al., "Conflict-averse gradient descent for multi-task learning" by Liu et al., and "Multi-Task Learning Using Uncertainty to Weigh Losses for Scene Geometry and Semantics" by Kendall et al.).

Thank you for your positive feedback and recognizing the positive aspects of our work! We will address the questions that were raised in their chronological order.

1. Since prior work did not directly investigate the Aligned Multi-Objective Optimization (AMOO) setting, we focused on comparing our performance to the equal-weights baseline, which is an intuitive algorithmic approach in the multi-objective setting. We also note that recent work showed the equal-weights baseline is competitive compared to other multi-task learning algorithms on multi-task benchmarks (see https://dl.acm.org/doi/pdf/10.5555/3648699.3648908). We also provided an extensive discussion about prior work on multi-task learning research and prior results are different from ours in Section 2.

2. Thank you for this suggestion! We include here additional results for the approximate AMOO setting in which objectives are only approximately aligned (see this anonymous link https://docs.google.com/document/d/e/2PACX-1vRbT_IuVcnR-RHPy95d9sIuiHa07DUmjA57HvWKjjWFUjST5udLeTUygnpnQ3AvSmiuc_y-r4JpiGYI/pub). We will include new results these in the final version of the paper.

3. In this work we focused on foundational work, namely, properly defining the setting, developing intuitive understanding, and theoretically grounded algorithms. Additionally, the empirical investigation we made is already outside the scope of the theory work: we test the new algorithms on non-convex optimization problems, with SGD and ADAM optimizer. We believe our empirical investigation and open source implementation of the algorithms lay the ground for more extensive empirical investigation in different domains (multi task, LLM, RL, computer vision, etc.).

4. We will explain the results more explicitly for readers' understanding. These results reflect the Mean Squared Error (MSE) metric (that measures distance between current iterate and optimal point) of different algorithms. Interestingly, PAMOO-ADAM, where the weights are chosen via PAMOO and the optimizer is the ADAM optimizer, has the best performance by a significant margin compared to other alternatives.

Additional comments: Thank you for these comments, we will adjust the paper accordingly.