Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: 1. This paper introduces the problem of multi-objective online convex optimization.
2. The authors propose to use PSG as the performance metric, and show that it is related to the dynamic regret. 
3. The authors develop algorithms that enjoy sublinear multi-objective regret, and also conduct experiments to show the effectiveness of the proposed methods. 
main_review: Writing: 

The writing of the paper is clear in general and easy to follow. 

Novelty:

1. This paper introduces multi-objective online convex optimization, which is a novel and very well-motivated. 

2. The performance metric proposed in the paper, i.e., Pareto suboptimality gap (PSG), has been used in the bandit setting. However, in the bandit case, people usually consider directly minimizing PSG through UCB+arm elimination techniques, which can only be applied to the setting when the arm set is **finite**. Thus, it was unclear to me how to generalize the results to the full-information setting. In this paper, the authors do a great job in Proposition 1, which shows an interesting connection between PSG and the dynamic regret and transforms the metric to a max-min form by introducing a weighting vector. Based on this formulation, the authors propose an algorithm which alternatively minimize $\lambda$ and $x_t$ based on regularized MGDA and OMD. I think the formulation in Proposition 1 and the proposed methods are novel. 

3. The authors successfully prove the proposed methods enjoy sublinear multi-objective regret, and the experiments also the effectiveness of the proposed methods. 

Some questions and minor points:
1. I am a bit confused when reading the proof of Lemma 1: To me, it seems that there should be two sequences of $\lambda_t$: the first sequence of $\lambda_t$ is from Proposition 1, and the second sequence is the $\lambda$ generated by the algorithm. I think the proof of Lemma 1 is mainly related to the second sequence, and my questions is how this related to the first sequence (and also the regret)?

2. It would be great if lower bound wrt m could be obtained. 

3. Since $\lambda$ is a m-D metrix and $\nabla F(x_t)$ is a $n\times m$ vector, it would be better to write $\nabla F(x_t) \lambda$ instead of $\lambda\nabla F(x_t)$ in the proof. 

4. Eq.(1): $x$ -> $x_t$


summary_of_the_review: I think the proposed problem, regret formulation and methods are interesting and novel, so I vote for acceptance. I have a minor question about the proof, and I hope the authors could help me understand it.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In the standard online learning model, the aim of the learning algorithm is to minimize its cumulative regret, defined by the difference in cumulative losses between the algorithm and the best decision taken with the benefit of insight in some reference set. In the generalized model of “multi-objective” online learning, the feedback is no longer a single scalar, but a vector of losses, each defined for a distinct objective. The performance of the learning algorithm is often defined in terms of “Pareto regret”, for which each instantaneous regret is captured by the notion of Pareto Suboptimality Gap (PSG). Although multi-objective online learning has been studied in the (possibly contextual and linear) bandit setting, many questions remain open. Notably, this paper focuses on the full-information setting where a vector-valued loss function is supplied at the end of each round. Based on the Online Mirror Descent (OMD) paradigm, two versions of multi-objective OMD are provided and analyzed for the dynamic version of Pareto regret (the static version being left as an open issue). Comparative experiments for both versions are performed on several benchmarks.

main_review: As indicated above, the multi-objective online learning problem has already been studied in the bandit setting, but the adversarial full-information setting was left open. The model of Pareto regret defined in terms of the Pareto Suboptimality Gap is relevant, but was already introduced in (Drugan & Nowe, 2013; Turgay et al., 2018; Lu et al., 2020). So, the real technical novelty of this paper does not lie in the formalization of the problem, but in the derivation of new (Pareto) regret bounds in the full-information setting. 

To this point, I was a bit confused by the results: using the online convex optimization framework, and more specifically the online mirror descent paradigm, the authors could derive a bound for the dynamic version of the regret, but not for the static version, which is actually a specific case (of the dynamic version). I understand that the key result, summarized in Proposition 1, only holds for the dynamic case, but this does not prevent us from finding a different approach to the static case. 

For the static version, it seems that one can still use the standard version of OMD by pursuing a single objective. Indeed, we know that for each $i \in [m]$, the point $x^*_i$ is Pareto optimal. Furthermore, unless I missed something, the definition of PSG (Definition 3), implies that the instantaneous Pareto regret $\Delta_t$ is upper bounded by the instantaneous regret $f^i_t(x_t) - f^i_t(x^*_i)$ of any objective $i$, provided that each comparator set $\mathcal X^*_t$ coincides with the Pareto set induced from the cumulative loss $\sum_t F_t$. Under this assumption, and using the optimal bound in $O(\sqrt T)$ achieved by OMD for the single-objective case, we should have a bound in $O(\sqrt T)$ for the multi-objective case.   

Nevertheless, for this dynamic version, the bound achieved by the online multi-objective mirror descent algorithm (second version) looks tight.  By the way, it would be nice to provide a lower bound here, in order to corroborate this tightness. Notably is $m^{1/3}$ tight? 

summary_of_the_review: This paper provides a non-trivial regret bound for the multi-objective online learning problem in the full-information, yet possibly adversarial, setting, using the online convex optimization framework. As far as I know, this is a novel result. However, I am not entirely convinced that this is significant enough for the ICLR conference since this Pareto regret bound only holds in the dynamic setting. Furthermore, it would be interesting to provide a lower bound in order to justify the tightness of this bound.

*** After Rebuttal Phase ***

The authors have addressed several issues, notably related to the tightness of the bound for the dynamic regret, and an $O(\sqrt T)$ bound for the static regret. So, I have slightly changed my score. I would recommend revising the paper by incorporating the interesting results obtained in Section D.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper formulates a novel framework for multi-objective online convex optimization. The novel framework, similarly to the single-objective online convex optimization framework, can be viewed as a two players repeated game where at each round the online learner selects a point $x_t$ and the (possibly adversarial) environment selects a vector valued loss function $F_t (\cdot )$. To extend the notion of regret to the multi-objective setting at each round the suboptimality of $x_t$ is measured using the Pareto suboptimality gap (PSG). Two algorithms (OMMD-I and OMMD-II) which upper bound the extension of the dynamic regret in the multi-objective setting are designed. The two algorithms can be viewed as extensions of the min-norm method for offline multi-objective optimization in the online setting. In both algorithms a composite gradient, which is a convex combination of the descent directions for every objective, is calculated. This composite gradient is used to select, together with a Bregman reguralization, the descent direction and consequently the point $x_{t+1}$. The main difference between the two algorithms OMMD-I and OMMD-II is that in the latter the composition of the descent directions in two consecutive rounds will possibly be "more similar" (due to the regularization term $|| \lambda - \lambda_{t-1}||_1$). 
main_review: Strengths: A novel framework is proposed. Two new algorithms which both theoretically and experimentally work in the latter framework are designed.
Weaknesses: 
(1) The suboptimality of $x_t$ in each round is measured using the Pareto suboptimality gap. A better measure of suboptimality could be the euclidean distance between the loss vector $F_t(x_t)$ and $F_t(x^*)$, where $x^*$ is the closest point to $x_t$ from the Pareto Optimal Decision set.
(2) The most common notion of regret is the static regret which is not bounded by the two proposed algorithms. Moreover, although I read the Remark at page 5, it is not clear to me why having a discrepancy metric which could be negative is a problem. In the classic online convex optimization setting it is possible to have $F_{t_0}(x_{t_0}) - F_{t_0}(x^*) < 0$ for a specific round $t_0$ since $x^*$ optimizes the overall sum $\sum_t F_t(x)$.
summary_of_the_review: The main weakness of the paper is that the static regret is not bounded by the proposed algorithms.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of multi-objective optimization in an online setting, where the objective functions are time-varying. An algorithm is proposed to solve this problem. The algorithm queries the gradient of all objective functions, and returns a convex combination of these gradients as the input to the mirror descent algorithm. The performance of the algorithm is measured compared to a sequence of Pareto optimal points, where a single component of the loss vector cannot be improved without causing harm to the other components. Under some set of assumptions, Theorem 1 provides an upper bound on the dynamic regret of the algorithm. 
main_review: The paper addresses an important question to bound the regret of online multi-objective optimization. The derived bound of O(mT^{1/3}V_T^{2/3}) is also an interesting result that scales with the number of objectives m, time horizon T, and the regularity metric V_T. Here are my comments and suggestions:

1 - The regret bound in Theorem 1 is a main result of the paper. However, the theoretical techniques used in its proof seem to be fairly standard. A summary of the key and challenging analytical steps in the derivation can be helpful.

2 - A deep review of the problem background is given in sections 1 and 2. However, the focus here is to describe the problem and its importance. As a consequence, several closely related works on the dynamic regret of online mirror descent are missed in the literature review, namely:

- Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online Optimization: Competing with Dynamic Comparators. Artificial Intelligence and Statistics (AISTATS), 2015.  

- Shahin Shahrampour and Ali Jadbabaie, Distributed Online Optimization in Dynamic Environments Using Mirror Descent. IEEE Transactions on Automatic Control (TAC), March 2018

- Nima Eshraghi and Ben Liang. On the dynamic regret of Online Multiple Mirror Descent. Publicly available at https://openreview.net/forum?id=RepN5K31PT3

The last reference seems to have a similar idea and even acronym OMMD, but in over a single-objective online learning domain. 

4 - Assumption 1 constrains the use of regularization function by imposing a Lipschitz condition. I wonder how often this assumption holds? Can the authors provide several examples and clarify the order of the parameter $\gamma$? Is this assumption satisfied in the examples used in the experiments?

5 - The dynamic regret described in section 3 compares the algorithm performance with a sequence of optimizers (single-objective case). However, there exists a more general form of dynamic regret introduced in the seminal work of (Zinkevich, 2003) which allows the use of arbitrary comparison targets. 
The paper extends the dynamic regret definition to multi-objective case by considering a sequence of pareto optimal points. However, the general form of dynamic regret still can be used in multi-objective case. Is it possible to bound the general form of dynamic regret (comparison against arbitrary target sequence) using OMMD algorithm?

6 - The paper is mostly clear, and I enjoyed reading it. However, there are some minor unclear parts:
In Lemma/Theorem statements the algorithm is referred to as OMMD. However, two different updates are provided in the algorithm block labelled as OMMD-I and OMMD-II. I suggest making this style uniform for ease of reading.
summary_of_the_review: The paper addresses an important question to bound the regret of online multi-objective optimization. The derived bound of O(mT^{1/3}V_T^{2/3}) is also an interesting result that scales with the number of objectives m, time horizon T, and the regularity metric V_T. There are some concerns about the connection to the literature, assumptions, technical and analytical steps, which are all detailed above.
review_title: null

Meta-review: This paper looks at a formulation of online multi-objective optimization problem.

All reviewers agree on the score, 6, which is quite rare but is not really informative; none of them are very excited about the paper, but they all find it interesting.

I have read it as well myself. The paper is rather clear and well written. I have three majors concerns.
1) I am not fully convinced by the objective R_{MOD} as it reduces to the dynamic regret in the single objective problem, as the later cannot be minimized unless we make strong stationarity assumption. This is obviously the case here (see Assumption 2). Then the choice of parameters would depend on some "stationarity" quantity (V_T). I am not really enthusiastic about this either.
2) The analysis is rather classical once the problem is reduced to a single-objective, so the analysis is not really breathtaking. Yet I admit that I quite enjoyed reading about this reduction, the idea is quite neat. 
3) Multi-objective online optimization has already been considered in online learning, but the related works did not really mention it. For instance, Blackwell approachability is such an example [1,2,3] (yet I am not sure that it can cover the Pareto front idea). It would be interesting to see how those approach compares (notably, the online mirror descent has been widely studied in that case).

All in all, I do understand the reviewers, and this paper is certainly borderline, but I do not think it reaches the acceptance bar yet. As a consequence, I would rather recommend rejection this year. 

[1] J. Abernethy, P. Bartlett, D. Hazan. Proceedings of the 24th Annual Conference on Learning Theory, PMLR 19:27-46, 2011.
[2] V. Perchet. Approachability, regret and calibration: Implications and equivalences, Journal of Dynamics & Games,181-254, 2014.
[3] A. Rakhlin, K. Sridharan, and A. Tewari. Online learning: Beyond regret. Proceedings of the 24th Annual Conference on Learning Theory, PMLR, 19:559–594, 2011.
Decision: Reject