Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work explores three gradient alteration methods: MGDA, PCGrad and CAGrad  used for multi-objective optimization and  shows that these methods are not guaranteed to converge to Pareto optimal/critical point in the stochastic cases, and illustrates that in a simple 2 stochastic quadratic functions case.
In fact, the included example showed that all three methods generate a direction that would degrade all objective functions. To remedy this issue, the authors proposed a momentum inspired algorithm that would reduce correlation of the stochastic gradients and the composite weights the stochastic gradients calculated to generate a descent direction.
The main claim is that this correlation issue does not become apparent until several iterations of the algorithms, therefore while MGDA, PCGrad and CAGrad will generate a good descent direction in early iterations, they will fail to do so as the algorithms proceeds. and therefore using momentum coefficient that starts close to 0 and convergences to 1 will solve this issue. The authors provide analysis for both convex and nonconvex cases with no assumptions of the lipschitzness of the composite weights .
strengths_and_weaknesses: Strenghts:
This paper serves as a general framework that includes many methods used MOO. 
Very straight forward example of a stochastic case where MGDA, PCGrad and CAGrad do not generate a descent direction.
This paper avoids unrealistic assumptions such as gradient-wise lipschitzness of composite weights.
Analysis for two important classes of functions: convex and nonconvex.
Illustrative experiments showing the effectiveness of the proposed approach.
Weaknesses:
No analysis for strongly convex functions.
Assumption of bounded gradients. 
Hard to understand analysis. 
Critical typos:
225: $E[d_k] = (0,-\epsilon)$  should be $E[d_k] = (0,\epsilon)$ i think.
240: the direction is $- \nabla F(x_k) \lambda_k$.
691: missing $\Sigma$ and added $-$?
716: the bound for the first term is not correct.
Additional typos:
128: $\mu$ should be in subscript.
47: coefficients plural
168: R is in calligraphic style 
197: asymptotically converge
581: missing brackets
672: $=$ instead of $\leq$
294: MODA ?
495: Pareto optimal is always weakly Pareto optimal.
702: Double sum $\sum_{i=1}^m$
725: missing sum (second line)
727: $\lambda_k^i \in [0,B]$
747: Before the final proof
766; double $E_{\zeta_k}[\| d_k\|]$
806: missing $n_k^2$
questions: 302: added sum in the theorem ? $\sum_{i=1}^m$.
760 (second line): why $||E_{\zeta_k}[\| \sum_{i=1}^m (\lambda_i^k \nabla f^i(x_k) )+  d_k\|] || \leq \sqrt{\|||E_{\zeta_k}[\| \sum_{i=1}^m (\lambda_i^k \nabla f^i(x_k) )+  d_k\|] ||\|}$?
limitations: The property of the momentum coefficient $\alpha_k$ i.e. it starts close $0$ and converges to $1$ and decreasing step size $\eta_k$ propose slower convergence speed than methods that does not use momentum and fixed step-size.
 No comparison with the convergence rate of vanilla MOGA alogorithms is provided.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The main claim of the paper is that the stochastic gradient alteration algorithms do not always converge to Pareto optimal solutions. 
The authors focus on multi-objective settings and present a unified algorithmic framework consisting of various gradients with respect to multiple objectives. The authors further propose a novel scheme that averages the previously calculated weights exponentially. 
The authors also show that gradient alteration algorithms can converge to an optimal value with the same rate as single objective stochastic optimization by using a momentum-like exponentially averaging mechanism.
strengths_and_weaknesses: ## STRENGTHS
- Multi objective optimization is an important topic, since there are many real life scenarios, applications and this is explained well in the paper. 
- The conjecture "altering the stochastic gradients yields a direction that even degrades all the objectives in expectation" is novel and presents a different way of looking at the problem 
- The paper is well-written.
## WEAKNESSES
- The presented results seem promising but I kindly request minor extensions for a slightly more convincing experimental results. 
- The error bar is missing for the experimental results, since the numerical values are very close it is important to do the analysis for different stochastic settings multiple times.  It is mentioned that the reported value is the mean of 3 runs but it would be still nice to see the error bar and maybe more number of iterations. 
- Similarly time analysis along with the accuracy and error values would be great. 
- Minor: In the checklist the limitations are said to discussed in Appendix but it is not discussed. 

questions: - Could the authors include the error bars for Table 1 and 2 and also in the Figures?
- Could the authors also maybe adjust the Figures to have time in x axis?
limitations: The limitations are not discussed. There is no potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies the conflicting gradient problem in multi-objective optimization in the stochastic (minibatch) setting. The authors survey some recent gradient alterations algorithms, put them under one general framework (or update rule), and then construct a counter-example that shows that such algorithms can fail to converge to a Pareto optimal solution in the stochastic setting. They propose to deal with this using a momentum-based update for the gradient composite weights.
strengths_and_weaknesses: The paper is well-written and has a clear structure that makes it easy to read. It starts by stating the problem, then summarizes known approaches and pointing the common problem in them, and finally proposing a solution and validating it experimentally. The problem is well-posed and is clearly illustrated in the counter-example and in Figure 1. The improvements of the proposed fix in this specific example are significant.

The fix employs an exponential average of gradient composite weights. It is simple, practical, and easy to implement. Works just like momentum in SGD, so it can be added to any gradient alteration algorithm. The additional compute and memory footprint are not significant.

The results overall are better, but not significantly so. Perhaps this is because the situation in the counter-example is not as serious in real-world data as is thought to be. In any case, the adjustment can be made to any gradient alteration algorithm without affecting performance, so this is not a big problem. Still, it would be nice to see real-world situations where this adjustment can yield clear and significant improvements just to account for the additional complexity,

Minor issues:
* There is a typo in Assumption 2 (line 193): “… which are unbiased estimates of $f^1$ …”. There should be a $\nabla$ before $f^1$, and so on.
* Figure 1 is a bit too small, especially the font. I had to zoom in to see clearly.
* Are the results in Figure 2 for MultiMNIST done for multiple seeds? If so, then it should be mentioned somewhere and the std bands should be plotted.
* As for Table 1, reporting the std would be better. Also, some acronyms are not explained, such as mIoU and Pix Acc. And finally, the relative error under Depth->Testing->Rel Err for CR-PCGrad is larger than PCGrad but is in bold. Looking at the absolute errors, I assume there is a mistake in the calculation.
* I think the bounds in Theorem 2 and Theorem 3 can be written a bit more clearly. The third term in the right hand side of Theorem 1 has an $\eta_k$ in the denominator, but the summation of the index $k$ is in the numerator.
* The conclusion is also a bit lacking. It would be nice for the readers to discuss future directions and room for improvements.
questions: How well does the counter-example translate to real-world data? It seems to be specifically constructed to make convergence fail. It is mentioned that a similar situation can happen with “more general Gaussian noise”, but wouldn’t the noise from SGD(+momentum) help mitigate getting into such rigid suboptimal situations?

Perhaps proposing a reasonable assumption on the data distribution can avoid such a counter-example altogether?
limitations: This work has no apparent limitations and potential negative societal impact.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Multi-objective optimization (MOO) has been an area of research interest lately, where the goal is to optimize multiple objectives simultaneously, using some optimality condition (e.g. Pareto optimality). One popular MOO algorithm is the multi-objective gradient alteration (MOGA) algorithm, where a common descent direction is chosen for all the objectives by manipulating objective gradients. In most MOGA literature, analysis is only provided using deterministic gradients, although in practice only stochastic gradients are used for calculating the common descent direction. This work addresses this issue. The authors propose an optimizer-agnostic framework to reduce the correlation between the aforementioned weights and the stochastic gradients, which can be applied to many MOGA algorithms. The authors specify the convergence criteria and provide theoretical guarantees for the convergence of the proposed algorithm for convex and non-convex cases. The authors also provide some empirical results to support their claims.

strengths_and_weaknesses: ***Strengths***
- Investigate a key and important issue in the current MOO line of research;
- Provide rigorous evidence of the non-convergence problem, and provide key insights into the source of the problem;
- Propose a simple solution to the problem which has insignificant computational overhead compared to existing MOGA algorithms;
- Provide theoretical and empirical justification for the performance improvement using the proposed algorithm.

***Weaknesses***
- The main theoretical results provided in the main text are inaccurate or different from those in the supplementary;
- Some strong assumptions are not standard without providing a clear justifications. Specifically, the authors use a bounded objectives assumption for Theorems 2 and 3 (line 739,  798), which is not standard in optimization literature and prior work on MOGA algorithms.
- It is not clear how the unified framework still guarantees the benefits of the original MOGA algorithms. Specifically, the assumptions on $\lambda_k$ do not reflect the special properties of different MOGA algorithms, thus it is unclear how the modification will allow behavior similar to the original algorithm.
- Seemingly incorrect/unclear proof steps possibly resulting in weaker dependence on the number of objectives $m$ in final results (e.g. lines 671, 687). Specifically, a factor of $m$ seems missing when upper bounding the squared norm. 
- Some claims on the relation between Pareto criticality and weak Pareto optimally in the convex setting need to be justified (line 542. Refer to the “Questions” for further elaboration of the concern).
- Missing definition of notations (e.g. $[m]$ in text, possibly meaning $\{1, 2, , …, m}$; p in toy example, probably meaning probability of occurrence) 
- Inconsistent notations used ( e.g. line 688, $\leq$ used for comparing scalers and vectors without clarification)

questions: * Could you justify the use of bounded objective assumption in the convergence analysis of the non-convex case, since it may not be true in general?

* Could you provide justification/proof for the claim in line 542? Specifically, the concern is that a Pareto stationary point need not be a weakly Pareto optimal point in general even in a convex setting.

* Could you provide any insight into how close $\lambda_k$ in CR-MOGA is to the actual $\lambda_k$ that is calculated by the corresponding MOGA? The work does not seem to provide adequate insight in this regard. If this closeness is not significant, could you explain the reason?

* Could you provide an intuition for the expected value of $\lambda_k$? By the variance reduction, $\lambda_k$ becomes closer to the expected value, yet it is unclear what this value represents. This might be related to the previous question.
limitations: - Authors have identified the limitations of the examples they have used to introduce the problem, but provide additional experiments in a more practical setting that support their claims.

- Authors may need to address the limitations of the work due to the strong assumptions such as the boundedness of the objectives.

- There is no potential negative societal impact from this work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposed a new algorithm for stochastic multi-objective learning that solves some non-convergence issues in existing multi-objective learning algorithms. At each iteration, the update direction is computed as the weighted combination of gradient directions of every objective, and the weight is an exponential average of weights in past iterations. Such a weight scheme aims at reducing the correlation between the weight and stochastic gradient at each iteration. The convergence analysis is provided for the proposed algorithm and experiments show its advantages over existing algorithms.

This paper is clearly written. The proposed algorithm is simple and shows great improvement over existing algorithms. Therefore I recommend "Accept"
strengths_and_weaknesses: This paper gives an excellent introduction to multi-objective learning, identifies convergence issues in existing approaches, and proposes a new algorithm as the solution. The paper is clearly written and easy to follow even for a non-expert in multi-objective optimization. Theoretical results on convergence are also provided together with experiments showing improvement over existing approaches. I can not assess the novelty of the paper as I'm less familiar with the literature on multi-objective learning.
questions: All of them are minor:

1. line 105, the author may want to clarify here what "$F$ is convex" means, it only gets clear when I read Theorem 2.
2. line 315/316, probably add citations for the convergence rate in the single-objective setting?

limitations: The author claimed that there are discussions on limitations in the appendix but it is hard to find. Maybe it is better to put the discussions in a separate section.
review_title: null

Meta-review: metareview: This paper analyses a multi-objective minimization problem. Author(s) show that several methods, such as PCGrad, MGDA, and CAGrad, can fail to even converge to Pareto optimal solutions. On top of that, they are mostly analyzed in a batch setting. 
Therefore, the author(s) design a carefully crafted problem where these phenomena can be studied. 
By averaging past weights with a carefully designed scheme, they proposed a new algorithm that can provably converge to a Pareto optimal solution. I believe that the NeurIPS community will benefit from this paper, and therefore I recommend acceptance.

Please, for the camera-ready version, please incorporate the suggestions from the authors and explain better parts that were not clear.

Thanks

confidence: Less certain
Decision: Accept