Jacobian Descent for Multi-Objective Optimization

Thank you for your review. We are sorry to see that our work was not to your liking. In the following, we hope to address most of your concerns: 1. As convergence to the Pareto front is our most remarkable theoretical contribution, we have indeed introduced it in Section 2.4. To better reflect its content, we have renamed this section to "Convergence to the Pareto front". Regarding Figure 1, we have limited our representation to the simple case of a problem with two objectives to provide intuition while preserving clarity. If there is any issue on the presentation of our paper that you would like to discuss, please let us know. 2. To clarify, our use of the term "resolving conflict" does not imply that our method aligns future gradients. Rather, it follows from our Definition 1 (Non-conflicting property): our method ensures that updates have a non-positive inner product with all considered gradients. 3. In Section 5, we discuss specifically about MGDA's issues compared to our method, both theoretically and empirically. Regarding comparison with the SMG algorithm, it's important to notice that in the absence of constraint, SMG combines noisy gradients by solving the minimization problem defined in their equation 10, which is equivalent to the first maximization problem of Section 7 of [3]. We show in Appendix B.2. that this is equivalent to the MGDA aggregation rule. Our theoretical and empirical analyses of MGDA thus also apply to SMG. As mentioned in part 3 of our global comment, we have added a discussion about trajectories of various methods from the literature on the function $[x, y]^\top \mapsto [x^2, y^2]^\top$. This highlights the significant gap between Pareto optimality and stationarity, and demonstrates the limitations of MGDA and methods that are based on it. [3] Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 2000. 4. As stated in Section 4, we deliberately do not compare our method with MoCo, because this algorithm is stateful: the direction of the update depends not only on the current Jacobian matrix but also on past information. We think that this is a very interesting direction of research, but it goes beyond our formulation of Jacobian descent that we wanted to analyse rigorously and in isolation from additional complexity.

Thank you for your response. Unfortunately, it did not address my concerns. I would like to explain in detail why I must maintain my current score. 1.**Regarding Section 2.4**: The authors emphasize that their main contribution lies in converging to the Pareto front. However, the discussion of existing literature remains insufficient. For instance, under convex conditions, the Pareto stationary point to which MGDA converges is equivalent to weak Pareto optimality, whereas under strong convex conditions, it corresponds to Pareto optimality. This article only considers convex conditions yet continues to use Pareto stationarity for comparison instead of weak Pareto optimality. This choice makes it challenging for readers to fully appreciate the contribution of the work. As a case in point, the function $[x, y]^{\top} \mapsto\left[x^2, y^2\right]^{\top}$ provided in the authors’ global rebuttal exemplifies MGDA converging to a weak Pareto optimal point.[1,Lemma2.2] 2.**On "fully resolve conflict"**: I understand and agree with the definition of "no conflict". However, updating along the 'no conflict' direction does not mean resolving conflicts. I would recommend adopting phrasing such as "completely avoiding conflicts" instead of "completely resolving conflicts," as it would better align with the content and findings of this article. 3.**On comparisons with other algorithms**: As mentioned in my first point, this paper improves MGDA by enhancing its convergence from a Pareto suboptimal point to a Pareto optimal point. But, when compared to CAGrad, the primary difference lies in switching the order of operations—changing from "summation first, then project" to "project first, then summation." While this improvement is valid, it seems relatively straightforward and expected, as UPGrad inherently performs projection for each objective, naturally avoiding suboptimality. Thus, the novelty in this aspect appears limited. Furthermore, the lack of investigation into non-convex and stochastic cases raises concerns about the comprehensiveness of the study. The title of the paper implies a broader exploration of Pareto optimization, but these critical scenarios remain unexplored, which diminishes the scope and impact of the work. To conclude, I am interesting in the research on the convergence domain of Pareto optimization, and this article does present new ideas for this problem. I believe the proposed approach can achieve promising results, particularly in scenarios with relatively few objectives, and it holds potential for broad applicability. **However, this work focuses solely on convex conditions, improving the convergence point from Pareto suboptimality to Pareto optimality. It does not extend the exploration to the more general and challenging non-convex settings, where investigating whether Pareto stationarity can be elevated to Pareto optimality would significantly enhance the impact and novelty of the study.** Given these limitations, I must maintain my current score regarding the novelty and presentation of the work. That said, if the authors can extend their research to non-convex conditions, I would be pleased to provide a more positive evaluation.\ [1] Hiroki Tanabe, Ellen H. Fukuda, and Nobuo Yamashita. Proximal gradient methods for multi-objective optimization and their applications. Computational Optimization and Applications, 72(2):339–361, 2019.

We appreciate the time and effort you dedicated to reviewing our work, and we are pleased that your feedback has led to significant improvements of our paper. We will now address your concerns. --- ### Weaknesses 1. Since the definition of the Pareto concepts (optimality, set, front) depends on the selection of the partial order, we still think that these concepts should be defined after defining the relations ($\prec$, $\preceq$, etc.) in the beginning of Section 2. Because we mainly use those concepts in Section 2.4, we prefer to keep the definitions there. Nevertheless, we thank you for raising this concern and we agree that unfamiliar readers would benefit from an earlier introduction to those concepts. We have revised our introduction to provide some intuition about the Pareto front as early as the first paragraph. The added sentences are: "In opposition, multi-objective optimization methods typically attempt to optimize all objectives simultaneously, without making arbitrary compromises: the goal is to find points for which no improvement can be made on some objectives without degrading others." 2. Please refer to part 1 of our global comment for the discussion about the convergence rate. Regarding comparison to the state of the art, we have provided a proof of convergence to the Pareto front, which is a stronger result than the convergence proofs of the other methods from Table 1. Note that we have added evidence that some of these methods do not even converge to the Pareto front when the function to optimize is $[x, y]^\top \mapsto [x^2, y^2]^\top$ (see part 3 of our global comment). We have not analyzed nor experimented against some of the recent methods for stochastic MOO, such as CR-MOGM[1], MoCo[2] and MoDo[3], because these methods are stateful: the update direction also depends on the "accelerated" Jacobian for MoCo, and on the previous weights for CR-MOGM, MoCo and MoDo. Clearly, preserving some state over the iterations has the potential to improve the convergence guarantees in some settings (similarly as momentum-based SGD can improve the convergence rate compared to SGD). Generalizing Jacobian descent to support stateful aggregators is a promising future direction that would deserve further attention. [1] Zhou et. al. On the convergence of stochastic multi-objective gradient manipulation and beyond. [2] Fernando et. al. Mitigating gradient bias in multi-objective learning: A provably convergent approach. [3] Chen et al. Three-way trade-off in multi-objective learning: Optimization, generalization and conflict-avoidance. 3. We agree with this weakness. That being said, the goal of our paper is mostly to provide a solid theoretical framework for descent methods in multi-objective optimization. Our methods could be fairly easily adapted to be much more practical for real-world applications. For instance, we could alternate between a step of Jacobian descent and several steps of gradient descent, on the scalarization of the objective using the weights that the Jacobian descent step has used to combine the gradients. When the number of objectives is large, we could also group them into a smaller number of objectives depending on their average gradient similarity. Finally, we could use JD for a subset of the parameters and GD for the rest (See e.g. MGDA-UB [4]). These ideas are not really new, so we did not mention them in our article, but they would easily enhance the practicality of all methods that are expressable as Jacobian descent. [4] Sener et. al. Multi-task learning as multi-objective optimization. --- ### Questions 1. We do compare ourselves with 9 methods from the literature, both theoretically (Appendix B) and empirically (Section 5 and Appendix D). We also have a discussion about the drawbacks of MGDA in Section 5, and more specifically about the insufficiency of a proof of convergence to a Pareto stationary point in Section 2.4. Please refer to our answer to weakness 2 about why we do not compare against the stochastic variants of MGDA (CR-MOGM, MoCo and MoDo). We do not claim that Jacobian descent is an entirely new idea, but we rather propose this framework to unify many existing methods. The novel contributions that our paper provides are the UPGrad aggregator, the IWRM objective, the idea of SSJD and Gramian reverse accumulation algorithm. 2. Theorem 1 and the following discussion provide important theoretical improvements compared to the existing literature. Please refer to part 1 of our global comment for the discussion about the convergence rate. 3. Thank you for this constructive comment. We have added a visualization of the optimization trajectory of methods from Table 1 when optimizing $[x, y]^\top \mapsto [x^2, y^2]^\top$. Since this has led to very interesting results, and to the discrimination of some methods, we have decided to add those plots in Appendix D4. Please refer to part 3 of our global comment for more details.

We appreciate the time and effort you took to review our work, and we're grateful for your constructive feedback. Your review led to several improvements of the paper. We now address your concerns. 1. Thank you for this suggestion. We have improved the paper with a brief explanation in the introduction to outline the goal of multi-objective optimization, specifically to decrease every coordinate at each step, and to reach a point where this is no longer possible, i.e., a Pareto optimal point. We hope that this addition will improve clarity, and we welcome any further feedback on the presentation. 2. We have added a new experiment on a toy example in Appendix D4. See part 3 of our global comment for more details. Regarding the convergence rate, please refer to part 1 of our global comment. We have also added the computational complexity of $\mathcal A_{\text{UPGrad}}$ in Appendix E2. 3. Thank you for raising this concern. As mentioned above, we have added a new experiment on a toy problem in Appendix D4. Besides, we agree that exploring settings with high conflict (e.g. adversarial training) is a very promising direction. 4. We are currently developing a framework to improve the running speed of Jacobian Descent by incorporating Gramian-based methods, as outlined in Section 6. This has the potential to significantly reduce memory usage and increase speed, particularly in the context of IWRM. Moreover, this approach could benefit not only $\mathcal A_{\text{UPGrad}}$, but also other aggregators such as $\mathcal A_{\text{MGDA}}$, $\mathcal A_{\text{CAGrad}}$, etc. The full development of this method would deserve a separate paper. We would appreciate clarification on your suggestion to use "some accelerate techniques on approximating the Jacobian counterpart, instead of merely taking averages". Could you please provide more details on what you mean by this?

We would like to thank you for the time and effort you invested in reviewing our work. We are pleased to hear that you found our research valuable, and we appreciate your thoughtful feedback. We will now address your concerns. --- ### Weaknesses 1. Please refer to part 1 of our global comment for the discussion about the convergence rate. 2. Thank you for raising this point. The main overhead of SSJD on the IWRM objective comes from having to store the full Jacobian in memory. Remarkably, when we use SGD with ERM, every activation is a tensor whose first dimension is the batch size. Automatic differentiation engines thus also have to compute the Jacobian. Since the gradients can be averaged at each layer as soon as they are obtained, the full Jacobian does not have to be stored. In the naive implementation of SSJD, however, storing the full Jacobian costs memory, which, given the high parallelization ability of GPUs, increases the computational time. With the Gramian-based method proposed in Section 6, only the Gramian, which is typically small, has to be stored: the memory requirement would then be similar to that of SGD. We have included these considerations in a new subsection of Appendix E, called "Memory considerations of SSJD for IWRM". Note that since there is still some computational overhead from the aggregation, our method should be used in the presence of non-negligible conflict. 3. Please refer to our response to your third question. --- ### Questions 1. Please refer to part 1 of our global comment for the discussion about the convergence rate. 2. This empirical runtime comparison can be found in Appendix E, Table 7. To improve clarity, we have revised the table by adding and additional column with the objective (ERM or IWRM), and by improving its caption. 3. Since our goal was to analyze JD and aggregators in isolation, we have deliberately limited our scope to a pure optimization setting. This removed the complexity of having to select generalization-related hyper-parameters (e.g. dropout, regularization, etc.), which enabled a reproducible, precise and fair learning rate selection strategy, increasing the reliability of our experimental results. Still, we can reuse the results of our experiments to easily obtain test accuracies. In the following table, we have reported the test accuracies obtained by each model and on each problem, with the learning rates obtained in Section 5, averaged over the 8 random reruns. | Aggregator | SVHN | CIFAR-10 | EuroSAT | MNIST | F-MNIST | K-MNIST | Average | |-------------|----------|------------|----------|----------|----------|----------|----------| | Mean | 69.6 | 47.7 | 68.5 | **96.3** | 80.7 | 76.9 | 73.3 | | UPGrad | **69.7** | **48.1** | **73.0** | 96.0 | 80.8 | **77.1** | **74.1** | | MGDA | 41.7 | 32.9 | 62.5 | 85.2 | 73.4 | 53.7 | 58.2 | | Aligned-MTL | 61.3 | 47.3 | 65.3 | 88.3 | 78.5 | 67.9 | 68.1 | | PCGrad | 49.1 | **48.1** | 59.3 | 85.9 | 69.3 | 54.7 | 61.1 | | DualProj | 69.3 | 47.2 | 72.7 | 96.1 | 80.8 | 76.4 | 73.7 | | RGW | 66.2 | 39.5 | 67.9 | 94.0 | 77.1 | 73.6 | 69.7 | | GradDrop | 68.9 | 46.8 | 71.9 | **96.3** | **80.9** | 76.9 | 73.6 | | CAGrad | 60.7 | 42.4 | 68.1 | 90.3 | 78.1 | 65.3 | 67.5 | | IMTL-G | 58.7 | 44.8 | 65.2 | 87.2 | 75.0 | 65.9 | 66.1 | | Nash-MTL | 39.7 | 31.3 | 60.8 | 87.6 | 72.0 | 52.7 | 57.3 | Note that SSJD with Mean aggregator on the IWRM objective is equivalent to the standard SGD on the ERM objective. This gives a rough evidence that the improved optimization of our method does indeed translate into a better test performance. Having established the efficacy of our approach in a controlled setting, our next step will be to evaluate its performance in practice, assessing whether removing conflict in optimization can lead to improved outcomes in real-world scenarios.

### 4. Non-convex analysis Some reviewers raised concerns about the non-convex analysis. We thank them as it led to an improvement of the paper. Specifically, in the smooth (and possibly non-convex) case, one typically considers that convergence of $J_t^\top w_t$ to $0$ suggests convergence to a point where there exists $0\preceq w$ with $0\neq w$ such that $J^\top w=0$, i.e., a Pareto stationary point. We have updated the paper with the following inequality, which can be directly derived from the proof of Theorem 1: $$ \frac{1}{T}\sum_{t=1}^T \big\| J_t^\top w_t \big\|^2 \leq \frac{2\beta\sqrt{m}}{T}\mathbf 1^\top \big( f(x_1)-f(x^\ast) \big) $$ We therefore have convergence of $J_t^\top w_t$ to $0$. Remarkably, as $\frac{1}{n}\mathbf 1\preceq w_t$, this suggests convergence to a point such that there exists $w$ with $0\prec w$ such that $J^\top w=0$. Such a point is sometimes refered to as a **strong Pareto stationary point**. The gap between those two types of convergence can again be seen on our example function $[x,y]^\top\mapsto[x^2,y^2]^\top$, as only the origin is a strong Pareto stationary point, but the set of Pareto stationary points is the union of the two axes. Of course this gap remains in non-convex settings. We thus believe that algorithms expressable as Jacobian descent should aim for this stronger notion of convergence in the non-convex settings.

Thank you for your interest in our research and for sharing your concerns. We appreciate the opportunity to engage in a discussion about our work. We have read your paper and acknowledge that your method shares some similarities with ours, particularly in the consideration of the dual cone concept from convex analysis. We agree that this notion holds great importance for multi-objective optimization (MOO). However, we believe that your method may face challenges when generalizing to higher dimensions (it is limited to 2 objectives). Specifically, the projection of the average onto the orthogonal hyper space of a gradient may not lie within the dual cone in general. This could limit the applicability of your approach and in particular, as we consider many simulatenous objectives, we cannot use your method on our problems. **Non-convex setting** Regarding convergence in the non-convex case, note that if $\frac{1}{T} \sum_{t=1}^T\| \nabla\mathcal L(x_t)\|^2$ converges to $0$, this does not imply convergence to a Pareto stationary point or even convergence at all. For example, consider the function $\frac{1}{1+x^2}$, on which convergence of the gradient to $0$ implies divergence of $x_t$ (this example can easily be extended to any number of objectives). Nevertheless, we have also added a similar result to our paper, as it was a popular request from our reviewers. See our answer to reviewer G6p6. We also agree that convexity can make the problem easier, but we argue that failing to converge to a Pareto optimal point in the convex case is a significant limitation for a given MOO method. Our method, on the other hand, is designed to address this challenge. **Experimental setting** As indicated in our conclusion, working with datasets with very conflicting objectives is a very promising future direction. However, your claim that the objectives that we consider are not conflicting is false. This can be seen by the plots showing the cosine similarity between the update performed by UPGrad and the update performed by SGD. If the individual gradients were not conflicting, they would all be in the dual cone even without projection, and we would always observe a similarity of 1 between UPGrad and SGD. This is clearly not the case here. The results from Figure 2 show a clear advantage of our method over all over methods, that is easily reproducible accross all datasets that we have experimented with. In opposition, many multi-objective optimization methods from the literature fail drastically on this simple setting. This is a very interesting result, once again adding empirical evidence to our theoretical claims.