Venue: NeurIPS 2022 Conference

Reviews:

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 performs a systematic study of online multi-objective optimization.  The authors formulate the multi-objective online convex optimization, in which multi-objective dynamic regret and static regret are formulated.  
The authors further show that the vanilla min-norm method used in MGDA may incur linear regrets. The authors further proposed a regularized version of online mirror descent. The min-regularization-norm is inspired by the regularization in FTRL. Both static regret bound and static regret bound are derived for the proposed regularized multi-objective online mirror descent method. The regret bounds match the optimal regret bounds in the single-objective setting. 


strengths_and_weaknesses: Strength:
- The multi-objective online convex optimization framework is quite clean and helpful.
- The proposed algorithm is reasonable and sound. The theory is solid to me.
- Good empirical performance.



questions: Can the authors leverage more on what are the meaningful and high-impact applications of online convex optimization? 
limitations: - The empirical evaluation is not comprehensive enough. 
- The motivation and significance of the contribution need justification. 
- The proposed method is in fact quite straightforward. The novelty is kind of limited.
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: This paper focuses on the problem of multi-objective online convex optimization, where the losses are given in vectors and the scalarized objective is the Pareto suboptimality gap, which to some extent reflects the distance to the Pareto frontier. The authors proposed online mirror multiple descent, which is the generalized version of online multiple gradient descent by allowing different regularizers, and provably enjoy optimal dynamic regret. Experiments validate the effectiveness.
strengths_and_weaknesses: Strengths:
- Clear writing
- Standard techniques with strong results

Minor Weaknesses:
- There exists mainly two lines of work on multi-objective online learning. One line focuses on the Pareto frontier while another line focuses on deriving no-regret algorithms according to Blackwell's approachability theorem. Though slightly different in the explicit scalarized objective, I think both lines of work contribute a lot to the community. And thus some additional related works and contenders should be noticed.
- The implementation of projection with different types of regularizers in OMMD should be carefully discussed.
questions: Does the term the $\sum_t \lambda_t-\lambda_0$ in Thm 4.6 have some specific meaning?
limitations: See weaknesses above.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies multi-objective online learning. It proposes new notions of static regret and dynamic regret based on a Pareto suboptimality gap metric. They show that OMD with the min-norm solver has linear regret, motivating the design of new algorithms. They propose a novel algorithm, Doubly regularized Online Mirror Multiple Descent, that regularizes the composite weights. They show that it obtains static and dynamic regret bounds with the usual scalings in T and that match the optimal bounds when there is only one objective. They provide experiments comparing their algorithm to a linearization baseline and the OMD algorithm with the min-norm solver.
strengths_and_weaknesses: Strengths:

The paper is clearly written and provides a nice pedagogical overview of the field. 

Multi-objective online learning is an important problem with many real-world applications. The new algorithms could find widespread use. 

The paper develops seemingly new regret notions with new algorithms and provides experiments showing that their method is competitive. 

It is nice that they give a simple example showing that MGDA doesn't work in the multi-objective setting. This is useful motivation for the design of new algorithms. 

Weaknesses:

The theoretical comparison to the linearization baseline seems incomplete. It would be nice to understand what a standard analysis for linearization baseline yields for its regret bounds and how this may be suboptimal in comparison to the proposed algorithm. For example, it seems that in the static regret setting removing the inf in the display between lines 210 and 211 and applying the standard analysis also gives a $O(\sqrt{T})$ regret. Is that correct? In lines 299-301, there is some discussion of the differences, but it is unclear how large of a difference there is between the methods. Are there concrete examples as for MGDA?

In the experiments, although the proposed method performs strongly, the improvement over the linearization baseline does not seem significant. This is especially important since the proposed method is more computationally burdensome than the linearization baseline, requiring to solve the optimization problem in in lines 266-267. This makes it more important to show an improvement over linearization.

It seems like an attractive property of MGDA is that it balances between the objectives (lines 151-153). Is there a similar property for this work?

In Section 5.2, it is not clear to me what is the advantage of choosing the regularization strength in an adaptive way. Won't this just yield one point on Pareto Front, so it is not significant? Can you describe the advantage in more detail?

While the upper bounds have the attractive property of achieving the optimal rates in the single-objective setting, the authors give no lower bounds for the multi-objective setting, so optimality of the approach is unclear. Can the authors comment on optimality?


questions: What is the the definition of regret in figure 1: static or regret? This is important for interpreting the experimental results.

In several places, the authors mention the optimal weights (e.g., "...lin-2 uses thwe optimal lambda_0 for the last..." line 333 and the caption in Figure 2). What is meant by the optimal weight? 

I think explaining the improvements over the linearization baseline is very important. 
limitations: Yes.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: This paper studies the online multi-objective learning problem in the online convex optimization (OCO) framework. The main contribution of the paper is to show that the regret minimization problem over the Pareto suboptimal gap can be converted to a single-objective optimization problem. Then, the online mirror descent method can be applied to achieve the static and dynamic regret bound for the multi-objective learning problem.

strengths_and_weaknesses: ### Strength:
- Novelty: although the definition of Pareto suboptimal gap (PSG) has appeared in the bandits setting, the paper proposes an interesting reduction in the full information setting that the regret defined by PSG can be converted to a single-object optimization problem.
- Clarity: this paper is well-structured and clearly written in most parts, which makes it easy to follow.

### Weakness:
- the title of this paper is somewhat overclaimed to me. The focus of this paper is on the multi-objective optimization in OCO (full information), and a gradient-based algorithm is proposed, which is not that general enough to cover the entire multi-objective online learning. For example, as referred by the paper, there are many papers on multi-object optimization in the context of bandit. Besides, multi-objective learning does not only exactly mean multi-objective optimization. For instance, [1] considers the optimization of two objectives in MAB (best arm identification and regret minimization); other results can be found in the references therein. Even in the full information, there is work studying how to handle the Pareto-frontier in the absolute loss game [2]. So, I advise the author to place the paper in the right place of the contemporary literature to avoid misleading. 

- Although the reduction proposed in this paper is interesting, I still have some reservations about the main theorems and their proofs.
	- on Theorem 4.6: by the optimal step size, the method achieves an $O(T^{2/3}V_T^{1/3})$ dynamic regret bound. But in the full information online learning (i.e. there is no noise in the feedback), a simple algorithm by just playing $x_t^* = \\arg \\min_{x\\in\\mathcal{X}} f_{t-1}(x)$ can achieve $O(V_T)$ dynamic regret [3]. I am not sure whether the $O(T^{2/3}V_T^{1/3})$ bound is tight in the full information case. It would be nice if the author could provide a lower bound.
	- another concern is the technical contribution of this paper. It seems that the proofs of Theorem 4.4 and Theorem 4.6 follow the standard analysis of the OMD algorithm. I think it would be nice for the author to highlight their technique contributions.

- about the experiments: as shown by the authors in line 337, the learning rate $\eta$ and parameter $\alpha$ are set according to the theories. However, it seems that the setting of the step size $\eta$ requires the knowledge of $V_T$, which is unknown in advance in the practice. So, it is unclear to me how the authors choose the parameter in the experiments ( Maybe one can calculate the $V_T$ in advance of the online learning process, but this could make a somewhat artificial experiment setup.).

- about the reproducibility: it seems that only the supplementary material only provides the code on the min-norm solver, which is not the method proposed by this paper.

[1] R. Degenne, T. Nedelec, C. Calauzenes and V. Perchet. Bridging the gap between regret minimization and best arm identification. In: AISTATS 2019.

[2] Koolen W M. The pareto regret frontier. In: NeurIPS 2013.

[3] Yang, T., Zhang, L., Jin, R., and Yi, J. (2016, June). Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In: ICML 2016.


questions: - What is the gap between the alternative form of static regret (Line 210) and the static regret defined by PSG (Line 177)?  Can the gap between the two regrets be bounded?
- it seems the code in the supplementary material only contains the implementation of the min-norm solver rather than the whole code. 
- the optimal step size in Theorem 4.6. relies on the temporal variability $V_T$, which is unknown in advance. In the single-objective setting, some previous works try to solve this issue by grid search with a meta-algorithm [4,5,6]. How does the algorithm in this paper handle the non-stationarity to obtain the dynamic regret? 
- in Line 42-43, the authors have claimed that “the theoretical investigation of multi-objective online learning will lay a solid foundation for the design of new optimizers for multi-task deep neural networks.” However, it seems to me that the theoretical results in this paper do not have a strong connection with multi-task DNN ( in OCO framework, the function should always be convex). It would be better if the author could elaborate more on this issue. 


[4] P. Zhao, Y.-J. Zhang, L. Zhang, Z.-H. Zhou. Dynamic regret of convex and smooth functions. In: Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.

[5] D. Baby and Y.-X. Wang. Optimal dynamic regret in exp-concave online learning. In: Proceedings of the 34th Conference on Learning Theory (COLT), 2021.

[6] D. Baby and Y.-X. Wang. Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond. In: Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.

limitations: This paper has discussed its potential limitations in Line 370-372. But I think there are also some other limitations as I have listed in the weakness and question part.
review_title: null

Meta-review: metareview: First, I must say that this is quite an interesting and elegant work, and regardless of the decision on this paper, I would like the authors to continue along this path. The paper is nicely written with a good flow, and the authors naturally arrive at their new algorithm, Doubly Regularized Online Mirror Multiple Descent. In the static case, the regret bounds the authors can show are solid and there are no complaints from any of the reviewers. This is almost true for the dynamic regret case, except for the large caveat that (in terms of theory) the authors' algorithm needs to know $V_T$. I discuss this issue more below. From the experiments side, although the authors show some improvement over the linearization baseline, the sense from the reviewers is that this improvement is not that much. For this reason, I truly think this paper needs to be solid theoretically.

**Regarding knowledge of $V_T$:**
First, to make it seem fair to request adaptivity to $V_T$, let me mention that in, e.g., the work of Campolongo and Orabona (2021) — which the authors cited in the context of their assumption of known $V_T$ — there are algorithms that automatically adapt to unknown $V_T$. Now, the authors' current need for knowledge of $V_T$ wouldn't necessarily be a problem if a doubling trick or meta-algorithm could be used. It is quite unclear whether the former could work, and in the reviewer discussion we have doubts about whether VariationHedge could be used in order to get adaptivity to $V_T$. I strongly suggest the authors look into this. Also, I think it is worth mentioning that the authors mentioned in one of their responses to a reviewer that their algorithm only uses first-order (gradient) feedback. It seems that this would mean that, even at the end of the game, $V_T$ could not be computed.

In light of the currently unclear significant benefit over linearization empirically and also the issue with adapting to $V_T$ for the dynamic regret results, this paper does not quite meet the bar for acceptance. However, the decision was a close one, and I strongly encourage the authors to increase discussion of both issues (and technically address adaptivity to $V_T$, working out details using VariationHedge if the authors can indeed do this).
confidence: Less certain
Decision: Reject