Multi-Objective Online Learning
Authors: Jiyan Jiang
Wenpeng Zhang
Shiji Zhou
Lihong Gu
Xiaodong Zeng
Wenwu Zhu
Venue: ICLR 2022 Submitted (2022)
Keywords: online algorithm
online learning
multi-objective optimization

Abstract: This paper presents a systematic study of multi-objective online learning. We first formulate the framework of Multi-Objective Online Convex Optimization, which encompasses a novel multi-objective dynamic regret in the unconstrained max-min form. We show that it is equivalent to the regret commonly used in the zero-order multi-objective bandit setting and overcomes the problem that the latter is hard to optimize via first-order gradient-based methods. Then we propose the Online Mirror Multiple Descent algorithm with two variants, which computes the composite gradient using either the vanilla min-norm solver or a newly designed $L_1$-regularized min-norm solver. We further derive regret bounds of both variants and show that the $L_1$-regularized variant enjoys a lower bound. Extensive experiments demonstrate the effectiveness of the proposed algorithm and verify the theoretical advantage of the $L_1$-regularized variant.

Under review as a conference paper at ICLR 2022
MULTI-OBIECTIVE ONLINE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
This paper presents a systematic study of multi-objectivv online learning. We first formulate the framework of Multi-Ohjective Online Convex Optimization, which encompasses a novel multi-objective dynamic regret the unconstrained max-min form. We show that is equivalent the regret commonly used in the zero-order multi-objective bandit setting and overcomes the problem that the lat- ter hard optimize via first-order gradient- based methods. Then we propose the Online Mirror Multiple Descent algorithm with two variants, which computes the composite gradient using either the vanilla min-norm solver or a newly de- signed L1 regeulaard min-norm solver. We further derive regret bounds of both variants and show that the regralulrd variant enjoys a lower bound. Extensive experiments demonstrate the effectiveness of the proposed algorithm and verify the theoretical advantage of the Le-reullarized variant.
INTRODUCTION
Traditional optimization methods for machine learning are usually designed optimize a single objective. However, in many real-world machine learning applications, we are often required to optimize multiple correlated objectives simultaneously. For example, in autonomous driving (Huang et al. 2019 Lu et al. (0019)). the self-driving vehicle needs to learn to solve multiple tasks such as self-localization and object identification the same time. In online advertising (Ma et al. 2018a b). the advertiser aims to choose the exposure of items to different users so that both the Click- Throuhh Rate (CTR) and the Post-Click Conversion Rate (CVR) are maximized simultaneously. In many multi-objective scenarios, the objectives may conflict with each other (Kendall et al. 2018). Hence, there may not exist any single solution that optimizes all the objectives simultaneously. For example, in the online advertising scenario, merely optimizing either CVR or CTR will incur the degradation of performance of the other (Ma et al. 2018a|b)
Multi-objective optimization (MOO) (Marler and Arora 2004 Deb 2014) is concerned with opti- mizing multiple conflicting objectives simultaneously. Many different approaches for MOO have been proposed, which include evolutionary methods (Murata al. 1995| Zitzler and Thiele 1999). scalarization methods (Fliege and Svaiter 2000) and gradient- based iterative methods (Desidéri 2012). Recently, due the great success of training multi-task deep neural networks, the first-order gradient-based iterative methods, i.c., Multiple Gradient Descent Algorithm (MGDA) and its vari- ants, have regained significant amount of research interest (Sener and Koltun| 2018 Lin et al.) 2019 Yu et al. 2020). These methods compute a composite gradient based on the gradient in- formation of all the individual objectives and then apply the composite gradient to model update. The determination of the composite gradient is based on min-norm solver (Désidéri) 2012) which yields the common descent direction of the objectives.
However, compared to the increasingly wide application prospect, the first-order gradient-based iterative algorithms are relatively understudied, especially for the online learning setting. Multi- objective online learning is very important due to reasons in two main aspects. First, due to the data explosion in many real-world scenarios such as various web applications, making in-time prediction requires to perform online learning. Second, the theoretical investigation will lay solid foundation for the design of new optimizers of multi-task deep neural networks, such as multi-objective Adam.
In this paper, conduct systematic study of multi-objective online learning. To begin with, we first formulate the framework of Multi-Objective Online Convex Optimization (MO-CCO.. The biggest challenge in the design of MO-OCO is the derivation of an appropriate regret definition in

---

Under review as a conference paper at ICLR 2022
the multi-objective setting. Since the multiple objectives form a vector space, need discrepancy metric to scalarize the loss vector. Specifically, we adopt the Pareto suboptimality gap (PSG), which is distance- -ased discrepancy metric extensively used in multi-objective bandits (Turgay et al. 2018 Lu et al.] 2019a). Then analogously to the single-objective online setting, we define the multi-ojeective static regret and the multi-objective dynamic regret. However, since PSG is metric motivated purely from the geometric view, it is intrinsically difficult to directly optimize using first- order gradient-basee iterative methods. To remedy this problem, for the multi-objective dynamic regret, via highly non-trivial transformation, we derive its equivalent regret in the unconstrained max-min form, which is much easier to optimize. Unfortunately, we further show that such an equivalence does not hold for the multi-objective static regret since PSG always yields non-negative measurements. Hence, this paper, we mainly focus on studying the multi-objective dynamic regret and leave the complete treatment of its static counterpart as an open problem.
Based on the proposed MO-OCO framework, we develop the Online Mirror Multiple Descent (OMMD) algorithm. The key module of OMMD is the gradient composition scheme, which uti- lizes the information of all the individual gradients to compute a composite gradient that tends to descend all the losses simultaneously. By directly applying the min-norm solver (Désidéri 2012) in the offline setting to determine the composition weights, we give the first variant of OMMD termed as OMMD-I. However, the min-norm solver only uses the instantaneous gradients and ignores the historical information, which can be very unstable in the online setting where the losses and the gra- dients at different rounds can vary wildly. To make the learning process more stable, we introduce a carefully designed L L1-regularizer to the vanilla min-norm solver, which results in the second variant of OMMD, namely OMMD-II.
We then give the theoretical analysis of the proposed OMMD algorithm. Specifically, we derive a non-trivial dynamic regret bound of OMMD-II, which includes that of OMMD-I as a special case.
The dynamic regret bound is in the same order OVV where T' is the time horizon and VT the temporal variability at T, as that of its single-objective counterpart(Zhang et al. 2018). We further show that the regret bound of OMMD-II is lower than that of OMMD-I.
To evaluate the effectiveness of our proposed algorithm, we conduct extensive experiments using both simulation datasets and real-world datasets. Specifically, we first design simulation experi- ments to verify the capability of OMMD-II to track the dynamic online data streams. Then we suc- cessfully realize adaptive regularization for online learning using our MO-OCO formalism, which demonstrates the effectiveness of OMMD-II in the convex setting. We further conduct online multi- task learning experiments with deep neural networks, the results of which show that both OMMD-I and OMMD-II are effective in the non-convex setting. Moreover, in both simulation and multi-task deep experiments, OMMD-II yields better performance than OMMD-L, which verifies the theoreti- cal superiority of the regularized min-norm method over the vanilla min-norm method.
In summary, in this paper, we give the first systematic study of multi-objective online learning, which includes novel framework, algorithm design and theoretical analysis. We believe that our paper paves the way for future research multiple-objective optimization and multi-task learning.
2
PRELIMINARIES
In this section, we briefly review the necessary background knowledge of online convex optimization and multi-objective optimization.
2.1 ONLINE CONVEX OPTIMIZATION
Online Convex Optimization (OCO) Zinkevich 2003 Hazan 2019 is the most commonly adopted framework for designing online learning algorithms. It can be viewed as a structured re- peated game between a learner and an adversary. At each round & E required to generate a decision x, from a convex compact set X' C IR". Then the adversary replies the learner with convex function f; X + R and the learner suffers the loss fz(2)). The goal of the learner is to minimize the regret with respect to the best fixed decision in hindsight, i.e..
T). the learner is
T
T
Rs(T) = Σ f((x)) - min Σ fe(x").
EX t=1
2

---

Under review as a conference paper at ICLR 2022
Note that the above regret is the static regret (Hall and Willeti 2013), which compares the learner's cumulative loss with that of a fixed decision. There is another version of regret, namely the dynamic regret (Hall and Willett 2013; Zhang et al. 2018), which compares the learner's cumulative loss with that of a sequence of changing decisions, i.e.,
T (T( = 1e - Σ 1=1
T
min f((x)).
Any meaningful regret is required to be sublinear in T. i.c., lim RS/D(T)/T = 0, which implies that when T' is large enough, the learner can perform as well as the best fixed decision in hindsight (for static regret) or the changing optimal decisions at each round (for dynamic regret).
Online Mirror Descent (OMD) (Hazan 2019) is classic first-order online learning algorithm. At each round & E {I,.... T}. OMD yields its decision using the following formula
Ie+1 1 arg min (V fxx)), + Bn(x,
=EX
where 77 is the step size, R X' R is the regularization function, and Br(Zzx') R(x)
R(x') (V R(x'), x²) is the Bregman divergence induced from R. As a generic algorithm. by instantiating different regularization functions, OMD induce two important algorithms, i.e., On-
line Gradient Descent (Zinkevich) 2003) and Online Exponentiated Gradient (Hazan) 2019). Several
papers work on the dynamic regret of online mirror descent (Jadbabaie al. 2015 Shahrampour
and Jadbabaie 2017).
2.2 MULTT--BJJECTIVE OPTIMIZATION
Multtple-objective optimization (MO0) is concerned with solving the problems of optimizing multiple objective functions simultaneously (Zizzler and Thiele, 1999 19999 Sener and Koltun 2018). In general, since different objectives may conflict with each other, there is no single solution that can optimize all the objectives at the same time. Instead, MOO seeks to find solutions that achieve Pareto optimality. In the following, we exposit Pareto optimality and related definitions more formally using vector-valued loss H (h-,...,,h) )TT as objectives, where m 2 2 and h K. - R i E {I.....m) mm), IC C R. is the i-th loss function.
Definition 1 (Pareto optimality). (a) For any two solutions x, E K, we say that x dominates x', denoted as x - or x' > x, if (x)) S W(('') for all i, and there exists one such that 1e (x:) < (2');); otherwise, we say that does not dominate x', denoted as A x' or x' & x. (b) A solution x² E IC is called Pareto optimal if it is not dominated by any other solution in K.
There may exist multiple Pareto optimal solutions. For example, it is easy to show that the optimizer of any single objective, say, xj E arg min,ek h' (x), is Pareto optimal. Different Pareto optimal solutions reflect different trade-offss among the objectives (Sener and Koltun 2018 Lin et al.) 2019).
Definition (Pareto front). (a) All Pareto optimal solutions form the Pareto set, denoted as (H(
(b) The image of Px((H) constitutes the Pareto front, denoted as P(H) = (x() x E (x))
Now that we' ve established the notion of optimality in MOO, we proceed to introduce the metrics that measure the discrepancy of an arbitrary solution x E from being optimal. Recall that, in the single-objective setting with merely one loss function h
R, where Q c R. for any the loss gap h[(2) - min h(a²)) is directly the discrepancy measure. However, in MOO with more than one loss, for any x E K, the loss gap (xx) Ho*"), where x" (H) is vector. Intuitionally, the desired discrepancy metric shall scalarize the vector-valued loss gap and yield the value 0 for any Pareto optimal solution. In general, there are two commonly used discrepancy metrics in MOO. namely Pareto suboptimality gap (PSG) (Turgay et al. 2018) and Hypervolume (HV) (Bradstreet, 2011). As HV is a volume-bart based metric, it is very difficult to optimize or analyze via iterative algorithms (Zhang and Golovin 2020). Hence in this paper, we adopt PSG, which has been extensively used in -ujti-objective bandits (Turgay et al. 2018 Lu al. (0119)).
Q
Definition 3 (Pareto suboptimality gap). For any x E K., the Pareto suboptimality gap to a given comparator set K* C K, denoted A(x; KS, H), is defined as the minimal scalar e Z that needs to be subtracted from all entries of H Hxx), such that H - cl is not dominated by any point in K where 1 denotes the all-one vector in R i.e.,
(xx; KS H)- = inf 6 s.t. Vx" E K", Ei E (1...., h)) (1....,m)),( << (2").
<20
3

---

Under review as a conference paper at ICLR 2022
Clearly, PSG is distance- bissence-based discrepancy metrie that motivated from purely geometrie view- point. In practice, the comparator set IC* often set to be the Pareto set Pic ( (Turgay et al. 2018 Then for any IC, its PSG is always non-negative and equals to zero if and only if E (H)
Multiple Gradient Descent Algorithm (MGDA) is an offline first-order algorithm for MOO (Fliege and Svaiter 2000 Désidéri 2012). At each iteration E (1..... L), where L is the maxi- mum number of iterations, it first computes the gradient (1'(zt) for each objective E {l.....m, m. and then derive the composite gradient şt = -- XzV)((z)) as the convex combination of these multiple gradients; it applies the composite gradient to execute the gradient descent step to update the decision, i.e., 21+1 = 24 ngt. where n, is the step size. The core module of MGDA is the determination of the weights X = (A)..... Alr)
for the gradient composition, which is given as
A arg min A.Edm
Σ (x)
where Am = {X E R X 2,0, (I.....m) m), and Σ X' 1} denotes the probabilistic simplex in R This is a min-norm solver which finds the weights in the simplex that yields the minimum L2 norm of the composite gradient. Thus MGDA is also called the min-norm method. Existing works (Désidéri) 2012 Sener and Koltun 2018) have shown that MGDA is guaranteed to decrease all the objectives simultaneously until it reaches a Pareto optimal decision (under the convex setting where all h are convex functions).
3 MULTI-OBJECTIVE ONLINE CONVEX OPTIMIZATION
In this section, we formally formulate the framework of multi-objective optimization in the online setting, termed Multi- multi-Ohhective Online Convex Optimization (MO-OCO).
We tailor the famous online convex optimization (OCO) framework to the multi-objective setting, which can be viewed as a repeated game between an online learner and the adversarial environment. At each round & E {I...., T}. the learner generates a decision I; from given convex compact decision set X' C R". Then the adversary replies the decision with a vectoral loss function Fi(z): : X' + RT,. where its i-th component fx() X - R belongs to the i-th objective, and the learner suffers the loss F2 (2,, E R. The goal of the learner is to generate a sequence of decisions {2, |
1 < t t T so that the cumulative loss ΣT= (zz) can be optimized.
Recall that, in the single-objective setting, the performance metric R(T) Ii f((x;), i.e., the regret, compares the actual decisions with some comparator 27 E X' at each round E {1..... T). In general, there are two common types of regret which differ in the comparators, i.e. the static regret and the dynamic regret. For the static regret, all comparators 2 Vt E {1...., T} are identically set as the fixed optimal decision xx w.r.t. all losses in hindsight, i.e., x = x² E arg min ΣT= fe(z). For the dynamic regret, the comparator ot at each round t is selected as the optimal decision w.r.t. the instantaneous loss ft at that round, i.e., xu E arg min fe(x).
In analogy, in the multi-objective setting, we define the regret as R(T) = Σ A., where the quantity A, each round compares the actual decisions I, with some comparator x; E X. However, in general, no single decision can optimize all the objectives at the same time. Hence, it is reasonable compare xa with all the Pareto optimal decisions that constitute comparator set Xt C X. Specifically, we introduce the Pareto suboptimality gap (PSG) (Turgay et al. 2018). i.c.,
A F
Ft) = inf e s.t. Vx" E X; Ei (1,...,m),, f((.) - c < f((x"). e20
(1)
Then the multi-objective regret can be defined as R(T) Et A(r;; XT, Ft). Given the above definitions, we can formulate the multi-objective variants of the static and dynamic regret respec- tively, by using different comparator set X2 at each step. Specifically, if we set all X; to be the Pareto set of the cumulative loss Dd Fr, then we can formulate a regret metric termed the multi- objective static regret (recall that Px denotes the Pareto set of F)
T RMOS (T) = Σ Aax;; X", ,'),, where X" = -xx Σ F.). t=
T
1=1
4

---

Under review as a conference paper at ICLR 2022
Alternativlly, if set X2 to be the Pareto set of the instantaneous loss F₁ each round then can give a regret metric termed the multi- cultri-objective dynamic regret
T
RMOD(T) (T)
= Af where X = Px (I....,Ty.
Recall that, PSG is zero-order metric motivated in purely geometric sense, namely, its calculation can be viewed as constrained minimization problem (1) with an unknown boundary fi (a"", " Vz" e X7 Hence, it is intrinsically complex to design first-order algorithm to optimize PSG given its unknown constraints, not to mention the regret analysis.
Surprisingly, specific to the multi-objective dynamic regret RMOD. we can transform it into an un- constrained max-min form as follows. The derivation utilizes Pareto optimality of X and is highly non-trivial, which is given in the appendix due the space limit. The equivalent form is closely related the dynamic regret, as recovers the dynamic regret defined for A, Fr. t E fI...., T if we determine A at each round E (I....,]] ,T} beforehand. Moreover, it exactly reduces to the standard dynamic regret Ro in the single-objective setting.
Proposition The multi-objective dynamic regret has an equivalent form, i.e.,
RMOD (T)
sup EX ISEST Ag... EA
inf
EOI F((z)) - -A7 -TFF((x)))
(2)
where Am represents the probabilistic simplex in R
Remark. In the single-ohjective setting where m 1, the probabilistic simplex A., collapses into single point {1}. Moreover, the Pareto set X2 of the scalar loss function Pt X + R. reduces to (F((x)) min F(())),
the optimal set arg min Fz)).. Hence we have (T)) which is exactly the dynamic regret (T) in the standard online setting.
Unfortunately, for the multi-objective static regret RMos. such a correspondence does not exist. Here the reason. RMOS, the comparator set X the Pareto set the cumulative loss Σ Fr rather than the instantaneous loss Fr. Hence, at some specific round I, the actual decision 2i may Pareto dominate all decisions in X w.r.t. the instantaneous Fú, and so we expect the discrepancy metric A, give negative measurement. However, PSG (as well other commonly used discrepancy metrics such as Hypervolume) is always non-negative, so the induced RMOD is not aligned with Rg- For example, when m = 1, we have RMOs (T) sup=* ET= max (e(e)) F((x)), which can be much looser than the static regret Rs sup=' 1 -x F(())) Therefore, the analysis of RMOD is intrinsically complex if we only use existing discrepancy metrics; its analysis may require completely new discrepancy metric A, that allows to give a negative measurement.
Given the limits of existing discrepancy metrics to characterize RMos- in this paper, we mainly focus on the dynamic variant RMOD. Indeed, the algorithm design and theoretical analysis w.r.t. RMOD are already highly non-trivial. We will leave the analysis of RMOS for future works.
4 ONLINE MIRROR MULTIPLE DESCENT
In this section, we first present the Online Mirror Multiple Descent (OMMD) algorithm, then provide theoretical analysis for it.
4.1 THE ALGORITHM
The protocol of OMMD is given in Algorithm [
At each round t, the learner computes the gradient for each loss V (xxe) then determines the weights for the composition of these multiple gradients, and finally executes online mirror descent step using the composite gradient. For simplicity, define the matrix form the multiple gradients as Fz( = [V (x))........... Vf." ) E IR 1m
The core module of OMMD is the composition of the multiple gradients. In intuition, the composite gradient ge shall elaborately utilize the information of all the individual gradient. As illustrated in Preliminary (see the MGDA part), in the offline setting, there one simple yet effective scheme,
5

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Online Mirror Multiple Descent (OMMD)
Input: Convex set X, time horizon T, regularization parameter a, learning rate n, regulariza- tion function R.
2: Initialize: 21 X, Ag E A..
3: for t = .,...,,7 do
4: Predict with 2i and receive the vector loss function P. X + R
5: Compute the multiple gradients (x; = (v.) V (2+)] E Raxm. A = arg min F, (1. 2 + aaI2 1-1I
6: Determine the weights for the gradient composition
A arg min [
(OMMD-I)
(3)
A
(OMMD-II)
(4)
AE
7: Compute the composite gradient 9r VF((Ee))e.
8: Perform online mirror descent using the composite gradient
1++1 = arg min 179,, x) + BR(x,
(5)
9: end for
ie., the min-norm method (Désidéri 2012 Sener and Koltun 2018), which computes common descent direction that can descend all the losses simultancously. We directly apply it to the online setting, which results in the first variant of OMMD, i.e., OMMID-I, shown in Algorithm []
Despite its simplicity, OMMD-I may not yield optimal decisions in the online setting, since the min-norm method is designed in the offline setting, which does not capture the characteristics of the online setting. Specifically, the composition weights A given by the min-norm solver are deter- mined solely by the gradients at the instantaneous round regardless of the historical information. Indeed, this makes sense in the offline setting, where the optimized loss function does not change too much. In the online setting, however, the losses at different rounds can vary wildly and so are the gradients consequently. Hence, directly applying the min-norm method will yield very different drs at different rounds, which makes the learning process unstable and even fail to converge.
To fix this issue, we propose to add regularizer r(A, λ to the min-norm solver when deter- mining the composition weights X, where A denotes the composition weights at the precedent round. Such a regularizer ensures that the new weights A will not move too far away from the precedent weights A In principle, r(A, A-- can take many forms such as -nomm, L2-norm and KL divergence etc. Here use the L1 norm since it aligns well with the simplex constraint of A. This L1 Legguulariee min-norm method results in the second variant of OMMD, i.c., OMMD-II, shown in Algorithm [ Later we will show that OMMD-II attains lower theoretical regret bound than OMMD-I, and it is also much more robust in experiments.
4.2 ANALYSIS
We first provide general bound for OMMD, which agnostic of the choice of X at each round. Assumption 1 (Bregman divergence). The regularization function R. is 1-strongly convex with respect to a norm || ||. In addition, the Bregman divergence is 7-Lipschitz continuous, i.e., Bu(I, 2) 2n(y,2) < 7/1x yll, Vx, y, 2 domR, where domR denotes the domain of the regularization function R and satisfies X' C domR C RR.
Lemma 1. Suppose the diameter of the decision set is bounded by D. Assume F, bounded, i.e., [x]] < F' for any x E Xt, (1...., .T, i E {l...., .... Then for any 8 E {l.....T} OMMD-I or OMMD-II with composition weights de at each round attains the following regret
T-1
ROOD (T) $26
Σ
sup [1((x)) (x))(0) 48FT
1| detilli
FEX
T
+
7
A 12
DD T
2
t=1

---

Under review as a conference paper at ICLR 2022
The bound can be further simplified under the assumptions of temporal variability and Lipschitz continuity, which are commonly used in dynamic regret analysis (Besbes et al. 2015 Yang et al. 2016 Campolongo and Orabona 202I).
Assumption 2 (Temporal variability). For each i E (1....,m). there exists some positive and finite VT such that Σt= supzex [f(()) - fi+1 $ Vr.
Assumption 3 (Lipschitz continuity). For each E (),...,m), there exists some positive and finite G such that, the i-th loss Sū at each round I. E (1....,T) is G-Lipschitz continuous w.r.f. II i.e., (z) - fi('') S Gi|z= 1 -''l-
In the convex setting, Lipschitz continuity guarantees bounded gradients, i.e., [ < G for any E {T....,T}. E (L...., ....,,,,, x E X. We can now derive a general regret bound for OMMD. AVr
Theorem 1. Assume the step size II satisfies G S 1 S G.. Then OMMD-I or OMMD-II with weights d at each round t attains the following regret
RMOD (T) GTT 2
7
Σ (IVEE 8FG2T2 V/r
T
11 )-1111) 1
DyDVT
The above theorem shows the theoretical superiority of OMMD-II over OMMD-I or naive linear scalarization that always uses fixed composition weights X = X at each round. In particular, with the proper choice of FGPT OMMD-II adaptively selects A, to minimize the
Remark.
Vr
term ( + allA; - A--1111- This term will become larger with any other choice of A
Finally, specific to OMMD-II, have the following regret bound. Note that, this bound actually relies on the assumption that 211) I Vr < o(T). which is implicitly assumed in other works for dynamic online learning (Beshes et al. 2015 Yang al.] [0066] Campolongo and Orabona 2021
We also extend the bound to arbitrary value of Vr 2 O (see Corollary in the appendix).
Corollary 1. With 17 (2 )/3 and a
TFG V7
OMMD-II achieves the following regret
RMOD (T) S OVV
EXPERIMENTS
In this section, conduct extensive simulation and real-world experiments to evaluate the effec- tiveness of our proposed algorithm. In our experiments, we mainly compare our proposed OMMD-II with two baseline algorithms: (i) linear optimal (lin-opt) performs single-objective online learning using the linearized loss F at each round f, where the linearization weights À is fixed and decided by a grid search on Am; note that, it is equivalent to using a fixed composition weight X; À in OMMD. (ii) min-norm extends the famous min-norm method (Désidéri 2012, Sener and Koltun 2018 to the multi-objeccive online setting, which has been described as OMMD-I in Algorithm
5.1 SIMULATION EXPERIMENTS: TRACKING THE PARETO FRONT
In the simulation setup, the goal is to track two points E, & moving on the plane IR. The two points cycle along a circle with a ratius of I, i.e., C = {E E R² || = 13, namely, for each i E (1,2), çi (cos 6/, sin 0)) is determined by some angle 8. For each i {1,2). we set positive integer pi as the rotating period, which is unknown to the learner. The two points are initialized by 0 0 and of = 7/2, and iteratively generated as follows: each round for each
(1,2), the adversary independently samples an angle 8i from Gaussian distribution (/(2 Pi 1/VPi), then generates the next point Ei+1 via 0/ 0j 6t. Note that, we have E0 = 0f + 2x P which implies that in average & rotates clockwise uniformly along the circle C, with period of pi
At each round f, the learner generates a decision x, from X = {z E g²
||>||| S 2). which is a L2-
norm ball with a radius of 2. Then it acquires the positions of a E and suffer two losses f/ (xxz =
||, - E fl/2/2 for i E {1, 2}. In this problem, the Pareto set of the vectoral loss f: = (ft f() at each
round is exactly the line segment linking & and EZ i.c., X² For any decision F, E X. its PSG exactly equals to the squared distance between a, and the line segment. The setup and PSG measurement summarized in Figure (left plot).
{XE! + (1 A)E² X E [0. 1]).
7

---

Under review as a conference paper at ICLR 2022
OMMDAI 9m
Hose Posk
Auarage LCEN
2006
5603
1000
Rounty
Reunds (K) (b) coviype
(a) simulation setup
(b) runtime performance
(6) protein
Figure 1: Simulation setup and results. Left: Tar- get points Ct E, cycle along the circle. At each round I, the Pareto set is the line segment ( and PSG measures the distance between Te and the line segment. Right: Performance compari- son of OMMD-II and baselines.
Figure 2: Results to verify the effectiveness of adaptive regularization using OMMD-II in real- world online classification tasks. The two plots compare the performance of adaptive regulariza- tion (OMMD-II) and fixed regularization (lin- opt) on protein and covtype datasets.
In our experiments, we set T = 10, 000. To simulate the adversarial dynamic change, we further set pl = 10, p2 = 20 for the first Ti = 3, 000 rounds, and pa = 20, p2 10 for the remaining T2 7,000 rounds. As our goal is the track the Pareto front, we adopt the average PSG, namely Elerry (z,)) as the performance metric. Accompanying the lin-opt baseline, we also consider its two variants: lin-/ which sets À as the optimal weights for the first Tj rounds, and lin-2 which set À to be optimal regarding the last T2 rounds. The learning rates v) in all algorithms and the regularization parameter a in OMMD-II are set as what the corresponding theories suggest.
Figure I (right plot) shows the performance of all the examined algorithms. From the results, we observe that OMMD-II achieves the lowest PSG, showing its ability to track the Pareto front; mean- while, min-norm appears very unstable in the dynamic setting, even worse than linear scalarization. In particular, by comparing OMMD-II and lin-l, we find that linear scalarization with carefully selected weights may attain performance comparable to our algorithm during some certain phase; however, in the dynamic setting where the pattern drifts over time, the performance of linear scalar- ization may become very unstable or even drop severely, while our algorithm much more robust.
5.2 ONLINE CONVEX EXPERIMENTS: AN APPLICATION TO ADAPTIVE REGULARIZATION
In many real-world online applications, regularization is often applied to avoid overfitting. A most common way is to add regularization term r(x) to the loss fe(x) in each round, and optimize the regularized loss [xx) + or(xx) instead (McMahan) 2011). The strength of regularization is often treated as a hyperparameter that needs to be decided carefully beforehand, e-g., via grid search. The formalism of multi-objective online learning provides an another way to realize regularization. Since r(z) often measures the complexity of x, it can be viewed as the second objective to be optimized. Specifically, by constructing a vectoral loss (x)) = (f((z))r(xzr) in each round, we can cast the regularized online learning into a two-objective online optimization problem. Compared to the previous approach with fixed strength a, in our approach, the strength implied by the weights in gradient composition, namely o = ///A which is adaptive at each round t.
We run experiments two online benchmark datasets. (i) protein: bioinformaties dataset for protein type classification (Wang) 2002). which has 17 thousand instances with 357 features. (ii) covtype: biological dataset collected from a non-stationary environment, whose goal is to predict the cover type of forests at particular location (Blackard and Dean 1999), which has 50 thousand instances with 54 features. For both classification tasks, we use the logistic loss as the first objective, and the squared L2-norm of model parameters (i.e., the I.2-reullarizer as the second objective.
In the experiments, we adopt L2-norm balls as the decision set and set the diameter K 10. For OMMD-II, the parameter or is simply set as 0.2. For fixed regularization, the strength o = A is determined by a grid search over (Nt, X?) E A2, and we denote this method as lin-opt. Moreover, for both OMMD-II and lin-opt, learning rates 17 are decided via grid search over (0.1,
0.2, ... 2.0}.
Since the ultimate goal of regularization is to enhance predictive performance, we adopt the average of cumulative loss, namely Everzy 4 (xx))/ / where (xx)) is the classification loss at round f, as the performance metric. The performance of both algorithms are reported in Figure 2 The results show that OMMD-II attains lower loss than lin-opt in all the examined tasks, which shows the superiority of adaptive regularization using our online MOO technique over fixed regularization.
8

---

Under review as a conference paper at ICLR 2022
Average Lo3s
1.2
OMMMD-I
nin norm (0.5.0.5)
Training Loop
1.0
min norm
GHKD-1 8
1.2-
min norm
GMND-I
1.0
Text Lixs
In 19.5.0.5)
2.7
0.8
0..8
0.6
0.6
20000
40003
60000
20000
40000
50000
20000
40000
5C0C0
Rounds
Rounds
Rounds
(a) Task L, Average Cumulative Loss
(b) Task L, Training Loss
(c) Task L, Test Loss
CMMMD
OMKD B
OMND II
Agenge Lode
1.2
nin-nrem in (0.5,0.51
1.2
minetomm Iin (8.5.0.5)
1:2
mineroomm
1.0
(.75.25)
Training
1.0
1.0
In
lin 10.5.0.5)
0.8
9.6
20000
.0000
60000
20000
40000
00000
20000
40000
00000
Rounds
Rounds
Rounds
(d) Task R, Average Cumulative Loss
(4) Task R. Training Loss
(1) Task R, Test Loss
Figure 3: Results to verify the effectiveness of OMMD-II for online deep learning. The plots show the average cumulative loss, training loss and test loss for both tasks (lask L/R) on MultiMNIST.
5.3 ONLINE NON-CONVEX EXPERIMENTS; MULTI-TASK DEEP LEARNING
Finally, we evaluate OMMD-II in the online non-convex setting. We choose to use the MultiMNIST dataset (Sabour et al., 2017), which is a multi-objective version of the famous MNIST dataset for image classification and commonly used in deep multi-task learning (Sener and Koltun 2018 Lin et al. 2019). In MultiMNIST, each sample is constructed by putting a random image at the top-left and another image the boihom-right. Our goal classify the digit the top-left (task L) and to classify the digit on the bottom-right (task R) at the same time.
We follow Sennrr and Koltun (2018)'s 's setup and adopt the LeNet architecture. For linear scalariza- tion, we consider two choices of weights, namely (0.5, 0.5) and (0.75, 0.25). For all the examined algorithms, the learning rates 1 selected via grid search over (0.0001, 0.001, 0.01, 0.1). For OMMD-II, the parameter a is set according to our theory. Note that, in online experiments, the sam- ple arrives one after another sequential manner, which is different from stochastic optimization where sample batches are randomly sampled from the whole training set (Sener and Koltun 2018).
Figure 3 compares the average cumulative loss, training loss and test loss of all the examined al- gorithms for both tasks. Note that, the first metric is typically used in online experiments and the last two are commonly used in stochastic experiments (Reddi et al., 2018). The results show that OMMD-II outperforms OMMD-I (min-norm) and linear scalarization (lin) in all metrics, which shows that our proposed algorithm is also effective in the online non-convex setting.
6 CONCLUSIONS
In this paper, we conduct a systematic study of multi-objective optimization in the online setting. We first formulate the framework of Multi-Objective Online Convex Optimization. Then we devise the Online Mirror Multiple Descent algorithm, which is the first gradient- multi-objective online learning algorithm and has special design when tailoring multiple gradient algorithm to online learning, namely regularized min-norm solver. Theoretically, we provide the first paradigm of regret analysis for multi-objective online convex optimization. We finally conduct extensive experiments to demonstrate the effectiveness of our proposed algorithm. Future works may include developing a framework based on the Hypervolume metric, or giving analysis of multi-objective static regret.
ETHICS STATEMENT
As study general learning problem, work will not incur ethical issues by itself. However, ethical issues may arise if our learning method is improperly applied to some application fields just any other general learning method if it is misused.

---

Under review as a conference paper at ICLR 2022
8 REPRODUCIBILITY STATEMENT
For every theoretical statement in our paper (including proposition, lemma, theorem and corollary), give a detailed proof in Appendix C in the supplementary materials.
The codes reproduce our empirical results are provided
REFERENCES
Amir Beck and Mare Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations research, 622421127- 2015.
Jock A Blackard and Denis J Dean. Comparative accuracies of artificial neural networks and dis- criminant analysis predicting forest cover types from cartographic variables. Computers and electronics in agriculture, 24(3):131-151, 1999.
Lucas Bradstreet. The hypervolume indicator for multi-objective optimisation: calculation and use. University of Western Australia Perth, 2011.
Nicolò Campolongo and Francesco Orabona. A closer look temporal variability in dynamic online learning. arXiv preprint arXiv:2102.07666, 2021.
Nicolo Cesa- BisncBi Pierre Gaillard, Gábor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). arXiv preprint arXiv: 1202.3333. 2012.
Kalyanmoy Deb. Multi-objective optimization. In Search methodologies, pages 403-449. Springer, 2014.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comptes Rendus Mathematique, 350(5-6):313-318 2012.
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathe- matical Methods of Operations Research, 51()):479 2000.
Eric Hall and Rebecca Willett. Dynamical models and tracking regret in online convex program- ming. International Conference on Machine Learning, pages 579-587, PMLR, 2013.
Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv: 20199, 2019.
Xinyu Huang, Peng Wang, Xinjing Cheng, Dingfu Zhou, Qichuan Geng, and Ruigang Yang. The apolloscape open dataset for autonomous driving and its application. IEEE transactions on pat- tern analysis and machine intelligence, 42(10):2702 2719, 2019.
Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimiza- tion: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398- 406, 2015.
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-tash learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 7482-7491, 2018
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qingfu Zhang, and Sam Kwong, Pareto multi-task learning. In Thirty-third Conference on Neural Information Processing Systems (NeurIPS 2019), 2019.
Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Multi-objective generalized linear bandits. arXiv preprint arXiv: 1905. / /2899, 2019a.
Weixin Lu, Yao Zhou, Guowei Wan, Shenhua Hou, and Shiyu Song. L3-net: Towards learning based lidar localization for autonomous driving. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pages -399, 2019b.
10

---

Under review as a conference paper at ICLR 2022
Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed H Chi. Modeling task relation- ships in multi-task learning with multi-gate mixture-of-exe -feeeeettte.......e. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 1930-1939, 2018a.
Xiao Ma, Liqin Zhao, Guan Huang, Zhi Wang, Zelin Hu, Xiaoqiang Zhu, and Kun Gai. Entire space multi-task model: An effective approach for estimating post-click conversion rate. In The st International ACM SIGIR Conference on Research & Development in Information Retrieval, pages 1137-1140, 2018b.
R Timothy Marler and Jasbir S Arora. Survey of multi-objective optimization methods for engineer- ing. Structural and multidisciplinary optimization, 26(6):369-33) -35, 2004.
Brendan McMahan. gollow-tth-rrggulaiiee---e
and mirror descent: Equivalence theorems and 11 regularization. In Proceedings of the Fourteenth International Conference on Artificial Intelli- gence and Statistics, pages 533. JMLR Workshop and Conference Proceedings, 2011.
Tadahiko Murata, Hisao Ishibuchi, al. Moga: multi-objective genetic algorithms. In IEEE inter- national conference on evolutionary computation, volume 1, pages 289-294, 1995.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In International Conference Learning Representations, 2018.
Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. Dynamic routing between capsules. arXiv
preprint arXiv:1710.0980 199.2999...099 2017.
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 525-536, 2018.
Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions on Automatic Control, 63(3):714-725, 2017.
Nathan Srebro, Karthik Sridharan, and Ambuj Tewari. On the universality of online mirror descent. arXiv preprini arXiv: 107.10044440 4080, 2011.
Eralp Turgay, Doruk Oner, and Cem Tekin. Multi-objective contextual bandit problem with sim- ilarity information. In International Conference on Artificial Intelligence and Statistics, pages 1673-1681 PMLR, 2018.
Jung-Ying Ying Wang. Application of support vector machines in bioinformatics. Taipei: Department of Computer Science and Information Engineering, National Taiwan University, 2002.
Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret online learning with true and noisy gradient. In International Conference on Machine Learning, pages 449-457. PMLR, 2016.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances Neural Information Processing Systems, 33, 2020.
Lijun Zhang, Shiyin Lu, and Zui-Hua Zhou Adaptive online learning in dynamic environments. arXiv preprint arXiv:1810.100 10815, 2018
Richard Zhang and Daniel Golovin. Random hypervolume scalarizations for provable multi- objective black box optimization.
In International Conference on Machine Learning, pages
11096-11105 PMLR, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE transactions on Evolutionary Computation, 3(4):257- 271, 1999.
11

---

Under review as a conference paper at ICLR 2022
APPENDIX
The appendix is organized follows. Appendix provides more details of OMMD, including discussion on the lazy version of mirror descent and how to efficiently compute the composition weights for the regularized min-norm solver. Appendix supplements the theoretical results with more general regret bounds for arbitrary temporal variability VI E [0, oo); such general setting is often not considered in typical analysis of dynamic online learning (Besbes et al., 2015 Zhang et al,, 2018), but we believe that adding such general bounds will make the analysis more self- contained. Appendix provides detailed proofs of all theoretical claims in this work, which have been omitted in our main paper due to the space limit.
A MORE DETAILS OF THE ALGORITHM
In this section, we provide more details to help better understand the design of OMMD.
First, note that, our proposed OMMD is actually based the agile version of online mirror descent (Hazan 2019), where the updated model directly moves to its projecting point onto the decision set at each round. However, we can easily make analogy and devise lazy version of OMMD. Specifically, we only need to use lazy projection operation in the mirror descent step with the composite gradient instead of the agile projection operation (line in Algorithm [T). Note that, the analysis of the lazy version is very similar to that of the agile version (Hazan 2019).
Next, show that, when calculating the weights Xe for gradient composition, our regularized min- norm solver only need very light computation, just as the original min-norm solver in stochastic optimization (Sener and Koltun| 2018 Lin al. 2019). Specifically, similar to (Sener and Koltun 2018), we first consider the setting of two objectives, namely m 2. In this case, when X, A Az the LI regularizer || 1 equals to 2 X/-ll- Then the optimization problem on at round reduces (since there are only two objectives, the superscripts of A and \ are omitted)
min xE[O.1]
Pg (1 1) 2a/A d=-1l-
Interestingly, we find that, the above problem also has an closed-fort solution as below.
Proposition 2. Set År. = (gz (g2 91) + +x) - gil?? and An = (9z (g2 91) - (0))///ll ll/2 91 1|. Then the above optimization problem has closed-form solution, i.e.,
max(0, A min
A S A-1i
AR 2 A-1 otherwise.
X-11
Proof. We solve the following two quadratic sub- sub-problems respectively, namely,
min |1 + 11))g221? 2 +
2a(Ax11 A),
AE(0,A.
well
min |gg + (1 >>gg2122 20(1 dr-1). xe(Ac-111]
The former problem produces x max(minf (rz, > and the latter one gives max max(min (min (AR, 1}. A Therefore, the solution to the original optimization problem can then be derived by comparing the optimal values of the sub-problems, which gives the desired solution in the proposition.
Now that we have derived the closed-form solution to the regularized min-norm solver with any two gradients, in priciple, we can apply Sener and Koltun (2018) 's technique to efficiently compute the solution to the solver with more than two gradients. Specifically, method, namely, iteratively choose a pair of gradients and update the composition weights with these two gradients.
adopt the Frank- Frank-Wolfe
12

---

Under review as a conference paper at ICLR 2022
B MORE DETAILS OF THEORETICAL ANALYSIS
In this section, we provide more details and highlight technical lemmas in theoretical analysis, which are omitted in our main paper due to space limitation.
B.I A MORE DETAILED REGRET BOUND FOR OMMD-II
In Corollary II only give the order of OMMD-II's regret bound w.r.t. the core factors m, and Vr. In the following theorem, we supplement a more detailed regret bound for OMMD-II which explicates the dependency of other factors on the regret. The proof is presented in Appendix C
Theorem 2. Set ( 1/33 and a 8FG Then OMMD-II altains the following regret
7D G4
413 T
8FG-T²
ROOD (T) S
1/3
Σ
inf (IVER AEA
+ Vr
M1A
Ac-1lli)
T1/3
1=1
(V
Note that, we have discussed in our main paper, just like its simplified version Corollary 1 the above theorem is derived under the assumption of "regular" temporal variability, namely 22(1) < Vr o()). which implicitly assumed in other works for dynamic online learning (Besbes al., 2015 Yang et al. 2016, Campolongo and Orabonal 2021). To give more general analysis, in the following subsection, we also provide strict regret bounds that are valid for arbitrary Vr [0, oo).
B.2 REGRET BOUNDS FOR OMMD-II UNDER ARBITRARY TEMPORAL VARIABILITY
We here provide a more strict regret bound for OMMD-II under arbitrary temporal variability Vr [0, oo). Specifically, we first give detailed regret bound in analogy to Theorem 2 theorem is given in Appendix C
The proof of this
Theorem 3. In OMMD-II, set r min(max ( it attains the regret bound
(
DVr
1/33
41- GT J.
4V G
and 8FG Then
RMOD (T) max D
113) 1/3
8FGPT2
1/3
inf xEAm
1 + |
T1/3
VT
3G
2(
6VT,
(2
2
The above bound can be rewritten into a simpler form, if we are only interested in its order w.r.t m, T and Vr. just as in Corollary
2r Corollary 2. In OMMD-II, set n min(max DD 1/3 @ V and a STG it attains the following regret
Then
Vr
((V+) BMOD S maxx(0Vv)13r111)00000..
C OMITTED PROOFS
In this section, we provide the detailed proofs of Proposition Lemma Theorem and Corollary in main paper well Theorem 2 Theorem and Corollary the appendix.
C.I PROOF OF PROPOSITION
Proof. We first analyze the PSG measurement (xx)) at each round E {1,..., T). Specifically, for any comparator x E X, we first define the pair-wise suboptimality gap between decisions d; and v, namely,
(x)))) = inf F((x,) al + F((x)).
<20
13

---

Under review as a conference paper at ICLR 2022
Then A((r)) can be evaluated via the pair-wise suboptimality (UP)EPx((I) 61(21,
gap
Ae(r))
We then focus on the pair-wise gap ( x)) w.r.t any Pareto optimal decision I E X = Px(FF) Since is Pareto optimal decision of Ft, from the definition of Pareto optimality, there must exist some i E (l,...,m) m such that (xx) (x) 2 0.
The pair-wise suboptimality gap has equivalent expression, namely,
& (x)5x)=
min
-
Ke (E()..,,m)
where (1)+ max 0), E R is the truncation operator. Denote Un {ex 1 S k m} as the set of all unit vector in IR",, then we equivalently have
6, (x)
min A (F((z))) - F+(x))++ xelmm.
Note that, we here slightly abuse the truncation operator (4)+ to allow to be a vector in R", which represents the vector whose i-th coordinate equals to max(I', 0} for any i E {1....,ml) m).
Now the calculation of (x(x;;)) x)) becomes a minimization problem over À E Um- Since Um is discrete set, can apply linear relaxation trick. Specifically,
now turn to minimize the quantity p(A) = AT (F& (z+) - F(()))+ over the convex curvature of Um. which exactly the probability simplex Am {} E RM | 0, || 1}. Note that, Um contains all vertexes of Am- Since infx= p(A) a linear optimization problem, the minimal point X; must be a vertex of the simplex, i.c., Xi E Um. Thus the relaxed problem is equivalent to the original problem, namely,
min XEll...
inf X (T(((())) F((x))+
xEA..
For now, we have transformed the calculation of wiir suboptimality gap ( x) into opti- mization problem of finding the minimal linear scalarization of at each round & can be expressed as
Hence, the PSG
A+(x)) = sup inf X (F(((1z)) - Fr(x))+ xEX; AEAm
In the above expression, the existence of truncation operator (-)+ will incur irregularity (i.e., non- linearity) when we try to optimize the loss F,. Suprisingly, we find that such operator can be dropped when we compute A (It)) w.r.t. the Pareto set X;, as shown in the following.
Lemma 2. Let X; be the Pareto set of F; X + R Then for any xe E X, it holds that
sup inf A (F)(2))) F((z)) sup inf (T((((z:) F((z)). = AEAm
ZEX* AEAm
Proof. Define the alternative "gap" metric without the truncation operator as 6((2;; = infxes,. A (F. (x)).. Moreover, define the supremum of (x);)) over x E X7 as
(1(1,) = suPsEx; () Then from the definition of truncation operator (+),, we have 5(1;;z)= 2 2) and (x().) 2 (z))).
then suffices prove that, for any given 2; E X, there exists some certain x; E X such that the value of 8' ("x1;; can be large as (.(ar). Indeed, if this is the case, then (x,))) < (2x)), and hence the two quantities (xx).) and (x(x)) are equal. We consider the following two cases:
(i) xt is already Pareto optimal point of Ft, i.e., directly have (xx = O. Notice that 8' (2(x xx) = 0, and hence Ac(x;) = sup 8'(xx;z) 2
Xx Then from the definition of PSG, we
5' (x)) = O. Consequently, the relation (x(x:) < (xx) holds in this case.
(ii) is not Pareto optimal point of F,, i.e., 24 XT. Then have A.(x)) > 0. Set Ac(ara) ) and denote xf E arg max xx (x(), then 6e (x);;) = = > O. Therefore, from the definition of b,( x+) we know that, for any E {1,.... m.) we have (2x) fx(x))
Thus all entries of (x Fx(x*) are positive, and we have (F,(x;) F((x"))+ = =F((z,) F,(x*). Consequently,
have (x.) supaex; K(1))) 2 8' (x)))]) = 5(x15²))) = -A(xx))
14

---

Under review as a conference paper at ICLR 2022
From the above lemma, the PSG measurement round has equivalent form (x())) = sup inf X (F)(()) - Fi(x)), = AEAm
and correspondingly, the multi-objective dynamic regret becomes
RMOD (T) Σ (.)))) = E sup inf (F((((a))) Ft(x)).
Ex AEAm
Since the time horizon 7 is finite, we can first swap the summation over and the supremum over x, then swap the summation over and the infimum over X. Then the multi-objective dynamic regret further equals to
[(x:T P((xs) - F,(x)))
ROOD (T)
inf "eex Af A7mm
sup
which proves the proposition.
C.2 PROOF OF LEMMA 1
Proof. For OMMD whose the composition weights are de at round t, before analyzing its regret bound, we first introduce two useful lemmas.
Lemma 3. For OMD with stepsize v and loss X, Ft(x), we have the following recursion
Ne (...)) - X. F((()) < (Bn(x;;m) - Bn(r)i + (IFF(())))..
(6)
for any t E TT..
Proof. Our proof is similar to the analysis of OMD in the single-objective setting (Srebro et al. 2011 Cesa-Bianchi et al. 2012). Specifically, fix ft = Ae T Fr and = Ax T (x.)). From the convexity of Jt, have
fe(ax)) [x;)) s o. (xt xt) = De (#++1 xx))= + De T (x+ r(+1).
From the first-order optimal condition of rx+1, for any x' X. have
(z:)) + VR(=++1) - Vi((x)) (x' Tx' xe+1) 2 0. We set x' = x in the above inequality, and consequently derive
- -(zz))((zz) = (VR(z+1)) vR(xz) (x; - I+41) + ge (xz x(+1)).
Recall the definition of Bregman divergence BR. We can check that (also see (Beck and Teboulle 2003))
BR(xi; 2x) - BR(xi x141) - Bn(x++1, = (VR(21+) 1) VR(aa)) (xt x(+)).
Since R is 1-strongly convex, we have B (2( 21) 2 || x Hence
fzx)) - fe(xt) < - (BR(ai B BR x++1) 5 || 2rll gt (xt 2(+1).
7)
Moreover, from the Cauchy-Schwand inequality have
g. (x. Ie+1) < Combining the above two inequalities, we can prove the lemma.
77 9g. 11 2
1 ||,, x 11.
2n
Lemma 4. For arbitrary comparator sequence ui,..., UT X, have
T
T
Xe -(F((z))-Fat
<
2 |ue |l + 7
u
BR(uI, 21) +
[V.(T.)A.11
17
t=1
15

---

Under review as a conference paper at ICLR 2022
Proof. Summing the inequality in Lemma
over t {1....,TY T). we have
T
A (F((z)) Fi(ue)) - (BR(u,, - Pa(ue,I(+1)) + "t VFc(x))Aell
1
(Bn(441, - Bx(u, x+1)) 1
Bn(ui, + T [VF((m)))
"
Recall the assumption that BR(œ, 2) - BR(y, 2) S 5 vll y, E N. We then obtain
T
T --1
a|lur u+11l 1l - -B(( 21) + (F
Σ (F(( F((ue)) -
"
which proves the lemma.
We now return to prove Lemma Notice that, for arbitrary comparator sequence U1...., uT E X, the Pareto tracking regret can be decomposed as
T
T
M T F((()))) - Σ Ae M F(()))
Σ X T F((1.)
Σ t=1
A T
F((u))
Ne T Fi(w)) Σ X N F((t))
1=1
term
We now instantiate the comparator sequence to be piece-wise stationary sequence, i.e.,
{ui,..., WT} =
w wi
WI, 1 1-1
WT
W (1+ -+ ITA times
W
A times
limes
which starts with wi and only changes for every A steps (A is an integer such that A < T). More
specifically, for any E {l...., [T/.. denote p: = (i - 1)A and qi = iA, and then
I; [ps, qi] is exactly the i-th stationary piece of the comparator sequence.
For any piece E (I...., [T/A]], we set all u,, E I, to be the best fixed decision o.. regarding the cumulative linearized losses during interval Z,, i... U 2 arg minzex E X Fx()), for any t I (1,.... [T]]]}. Then can apply Lemma to such comparator sequence and bound the term A as
T/41-1
T
A < 2 17
Σ
|uuz UI 11 + BR(UZ, 11) +
17
2
1m1
1=1
? (T T
7D 1)D
n Σ [VF((M))
7D
n A 1+
T
" 2
Σ
T
"
Notice that, the second term B measures the difference between the cumulative linearized loss of the best decisions o regarding each interval Z, and that of the comparators {x To analyze this term, we consider such difference B, restricted to any interval I,, i E (1,..,, [T/..,
Σ de T F((me) - -E Exe EXTTF((R Fe(x))
B. =
(EL
LEI.
Σ X T F(())) - >m Ap (p. + Σ Ap, (p)()))))
Σ Nr F((2)). VEI
IEI:
LEI;
IEI:
Recall our definition of u, and at, then we have EIET, X T Fr(we) S ELeT, de Pr((z)) and Ap. T Fp. (xx2)) < Ap. T Fp. (2t). Hence we further have
Bi < Σ Xr T Fl(1%))
Σ Ap. (x, (xx).) +
Ap. T Fp, (z7)
Exe TTF()))))
I
TEI.
EEI.
16

---

Under review as a conference paper at ICLR 2022
Moreover, for any t I, X, we have
|A. | F(())~ T Px, = E (Ae+1 T ( Fn(x)) <
Σ
sup Au T - xex
FR++ (2))
Recall that Zg has at most A elements, further have
B, 2A
Σ
sup De Fk(x)) - Act1 Fk+1(x))
#EX
A=
Hence the term B can be bounded
T/A B= Σ
[T/
2A 2A
Σ sup =EX
AA Fa(x)) Aut1 (xt1(x)).
k=p:
From the definition of pt and gi we further have
T-1
B 2A
Σ sup |d= Fe(x) det1 T Fet1(1)
S 24
sup((A,
F+41(1)) 1(2 ((+1(()))
Combining the above two inequalities on terms A and B, we finally derive
[2/A1-1
RMOD (T) S
?
Σ
WI + 17 Iuz,
1 Br( 21) " 2
T-1
+ 2A
sup (lA (F((z) zEX
+I - A (+))
Assume that the diameter the decision domain X' is upper bounded by some D > 0, then | WI D and BreWU,, (Z, 21) S ylluz, In >D. Hence we have
TT/ -1
Y
Σ
luz,
WT + BR(UT, 21) < 7D (T/A] 1) 1)
1
DD T 7D
1
"
1 A
Further assume that each loss function F; is coordinate-wise G-Lipschitz continuous, i.e., (f((y)
Glly - ælI, Va,y E X, E (1....,m), m... Without loss of generality, we suppose 0 E X and (0) 0, vi E (1,..., T) E (I,...,m). Then for any x X, [ff(x)] GD, and consequently
< [+))
T-1
T-1 A4t1llI.
Σ 10 - F(41(1) < F
Σ [ - (ealla S 2F
1
then remains to tackle the term the following lemma.
ET= supeex [X] (F((() ((+1(x)) To this end, we introduce
Lemma 5. For OMMD with composition weights A Am each round t, it holds that
T-1
Σ sup Dxe T (F((z) F++1(x)) 2F(T
Da detill + Vr.
xE
17

---

Under review as a conference paper at ICLR 2022
Proof. Denote π
Σt
We then decompose 7
suprex De (F.(z) - Fet1 as
sup Aee (F)()))))))))))
sup 1(A (A) - (2+1(1)) + +X ZER'
+ (Fr(x) P(t(
sup - (LF(() (+)1
Σ sup | (Fi(z) Pi+ (z)) ZEx
ZEN'
Since we have assumed that [f]( s F for any x E X, E that [f) - (x)) & 2F. Consequently, we can bound the term A as
m.....,m.. it holds
sup Σ ( ())))(())))))))))))))))))))))))) f(+((=))
term
m sup
{x - (5)1))1((() f41(11)
i=1
| (1)1
sup (f((z)) sup xEX
(z)
t= t=1
m
T-1
M (1)4 2F
Σ 2F| XI[1
where Xi and (A)' represents the i-th entry of de and X. respectively. Also notice that for any t t {I...., T}.
1 A111 = E d
-ell2 = Ek=r(de (de de)
111
T
T
beck (Ag - (0t11)
T
A
k=
T
k=1 s
T-1
T-1
T-1 Σ
Aa Xo+1
= T
Σ
Aa
A041
1> Ast1
A=
Therefore, we have
T-1 T-1
T-1 - 1) Σ
term A <
2F
AA - A411l11
As for term B, we have
term B-
Σ
sup A (F((z) (+t1()))1
Σ sup
(T)* 1f((x) (1+1
ZEX
xEX i=
m
m
<
M
Σ sup xex
[z(()) fin
(A) Vi = Vr;
where the last inequality is derived from the assumption of temporal variability, and the last equation comes from the fact that En (A) = + En Σ X = Enr Em X = 1. Combining the above bounds for term A and term B, we finally prove the lemma.
18

---

Under review as a conference paper at ICLR 2022
Plugging the above terms into the above bound for RMoD(T), and replace the quantity A (I...., T by 8, we have
1 A441l1 (F((()))))) ?D T RMOD(T) (T) $20V + 45FT
1. 17 8
for any 8 (I....,,T T).
Note that El= sup S (F((z)
( - F1+1(2))) + 1(
A F++1(x)]) = ET- supeex (1de (F((z)) - (z)1 + +(Ae - --41) Fe+1 because
the regret does not depend on FT+1, Ar+1. We thus prove the lemma.
C.3 PROOF OF THEOREM
Proof. This theorem can be directly derived from Lemma
Specifically, when GPT S S G we can set =G into Lemma and rearranging the inequality, we can directly derive the theorem.
Vr which satisfies s 8 < T. Plugging
C.4 PROOF OF THEOREM 2
Proof. Since this theorem is a special case of its following Theorem 3 when M(1) S Vr S (T)),
can be proved
derive Theorem B in the following subsection.
In fact, as we assume (2(1) < VT S (T)), in the following derivation of Theorem
we are we exactly have
always in the case of (i). In addition, when (1(1)= I Vr I o(T) in Theorem
n (DV1)// Hence this theorem be directly derived from Theorem
C.5 PROOF OF THEOREM 3
Proof. Denote To 2 DV 11/3, GT
We consider the following three cases:
(i) When GTT S ?1 S r
we can directly apply the above lemma.
(ii) When To < G3T or equivalently Vr > (2 1/2) we have 17 G2T then it can be verified that
4Vr
4Vr.
Set 8 = in Lemma 1,
2V
DDGT2 DDG2T
BMOD (T)) < 2V +
(all> - x -
G2T
4VT
2V
4Vr +
[VF((s))<e-11
G2T
t=1
2V T
$ 4V +
Σ
G² = 6V1.
GTT
1=1
(ii) When No > AVr then it can be verified that
@ or equivalently Vi (22)) we have 7 c Set T in Lemma 1,
2V T G
(a (all>-~110 - - - + DD2
RPT (T) < 2TV, +
4V,
1=1
2V T
< G(27D)
+
[F((z))
G
t=1
2V
3G
I 122-1
Σ
G² <
12/1)//
G
1=1
Combining (i)-(iii) we prove the theorem.
19

---

Under review as a conference paper at ICLR 2022
C.6 PROOF OF COROLLARY
Proof. Since this corollary is special case of its following Corollary when Q(1) Vr S o(T), it can be directly derived from Corollary 2
Specifically, since Vr 2 Q(1), we have Vi 22233 2 O(T Moreover, since V/ - o have /1/372/3 o((r). Therefore, the dominating term in the bound of Corollary 2 is V 11/372/3 which proves the corollary.
C.7 PROOF OF COROLLARY 2
Proof. We start from the general bound derived in Theorem 3 Specifically, in the first regret term, since x is selected to minimize axl A Ae-1l11 + [v, at each step t, we further have
min fallA d--1l12 [+)(())) < [V ((A=)lllIFF(())))))) G AEA...
Plugging it into the bound in Theorem directly proves the corollary.
D MORE DETAILS IN MULTI-OBJECTIVE STATIC REGRET
As we have discussed before, the multi-ohjective static regret cannot be formulated using most existing discrepancy metrics, since these metrics always give non-negative measurements, and the static regret based on any non-negative metrie will fail reduce to the standard static regret (T) in the single-objective setting, In this section, we give possible form of multi-objective static regret and provide an analysis for it.
The static regret is enlightened by the equivalent form of dynamic regret derived in Proposition 1. Recall that in Proposition I, the comparator =f at each round is selected from the Pareto set X;" of the instantancous loss F;; in addition, the weights X at each round is generated separately. To derive a static version, we can use a fixed comparator x from the Pareto set X of the cumulative loss E, F; and fixed weights X at all rounds. Now the static regret takes
T
T
RMos (T) = sup inf T E- Emm
F((x))
E(())) 1=1
where X" = Px Fr). Note that when m = 1. the probabilistic simplex Am reduces to single point [1}. and the Pareto optimal X coincides with the optimal set of the cumula- tive scalar loss ΣT Fe, i.c., X = arg min F()). Hence the multi-objective static regret takes RMos(T) suP (Ei- P((x.) - F+(x)))= Ein
Σ F((x), which exactly reduces to the standard static regret Rs(T) the single-objective setting.
Surprisingly, with proper choices of and a sublinear bound w.r.t. T for the static regret, as shown the following theorem. Note that the derived regret bound for OMMD-II is tight w.r.t T. since matches the lower bound O(VT) of the standard static regret in the oingle-objective setting (Hazan 2019).
proposed OMMD-II algorithm can still achieve
Theorem 4, OMMD-IL with composition weights x attains the following static regret
T-1
T
RMos(T) (T) < 2FT)
Σ
De A4tall + - BB( x1) (1)+ " (V
71
1=1
By setting 7 GvT
V2D
and
1FT,
the regret bound reduces O(VT), which is sublinear w.E.t. T.
20

---

Under review as a conference paper at ICLR 2022
Proof. We start from the definition of (T)s(T). Specifically, for any X Am and Ap Ams it holds that
RMOS (T) sup inf Σ x E (F((2)) - F((x)) sup EX- ED 1=1
Σ - -((()))F((("))
x-Ex*
Fx())) - d (.(())) + + (F)(a))) - F((2")) (Ae FF((x)) - FTF((=)))
T
T
T
1
FIA
1111 Σ do (F((z)) -((x=)) + Σ FILA - 1dl1
1m1
T
2F
A
Σ
(F((E)) Fi(z))).
t=1
1=1
To tackle the second term in the above inequality, we set 01 which results in
U2 = =...
ur x in Lemma
T - BR(x" x1) + Σ [VF 1
Ae (F S
To analyze the static regret for OMMD-II, we relate the first term ΣL /| regularization in the regularized min-norm solver each round. Specifically, we denote the average weights Ā = Ei= \.TT and set À À in the first term. Then for any t {I,...,T) have
dellz with the L1
Σ
(Ax
de)
11 = EL Ek
AA
AKt1)
J - Ael12 = 1==1
112
T
T
T
A
Aut1
A
A6+1
T
k=
1=1 k=1
T-1
Au+
| A411l11
k=1
Consequently, the static regret can be bounded
T
T-1
T
RMos (oos(T))20) 2F
Σ
||
A411l1
+ B
+
1
[VF(MM))
2
t=1
1=1
T-1
T
= 2FT
Σ
1 - Ae+illi + BBx("" an +
1 2
Σ
(
which proves the full static regret bound. Now we prove the reduced bound. From the full bound, we equivalently have
RMOS (T) S _ Bn(x", mn) + " 2 1=1
E
T
4FT 1|
We now set X 4FT in OMMD-II, and specify X, to be the composition weights generated by the algorithm at round Then we know that d, E arg minxes, (v;((;)) + 4FT I| - A In particular, have (( + 4FT that
" [| A-1l11 ( Therefore, it holds
T
RMOS (T) s - ;B(x,,,))))
17 2
Utilize Assumption
1 and Assumption and set 17
2D GV7
then we have
T
7 RMoss (T)) < BB( x1)
2
which proves the reduced bound.
21

---

Under review as a conference paper at ICLR 2022
Fr (Xpros)
Apro: (-1,0)
-,0x)) (0.0)
Fj (Xpss)
(2x x² 2x x2
Fe(x)xx²)
3
Pi
Xasn (-1,-1)
Xi
Figure 4: Illustration of an example in which the projection-baset metric A,roo fails to measure the Pareto optimality of the generated decision Ty-- The light blue area and the orange area represent the decision set X' and its image (X)), respectively. The blue line segments constitute the Pareto optimal set X². The red line segments constitute the Pareto front Pt. As shown in the plot, in this example, the projection-based metric A!roi compares (1x))) with the farthest point (x(rrr))) in Pareto front; the comparator "rro does not even dominate Ty. In contrast, PSG compares F ((())) with the nearest point (IPPS)) in the Pareto front; the comparator TPSG indeed dominates 2t.
Note that the newly introduced static regret is no longer based on PSG. It can be understood as in- (1:) ) Fr(x") where X" A Such a metric compares the generated decision I, each round with the fixed comparator x= X Hence, in particular, it is able to produce a negative value when dy dominates x= regarding the instantaneous loss Fe, making general extension of PSG. Although this property desired in the definition of static regret, is rarely utilized in the discrepancy metrics in multi-objectio optimization. Thus it looks bit strange as a Pareto suboptimality metric and hence its physical meaning needs to be justified further. Be- sides, there are undoubtedly many other possible ways to define such metrics. Therefore, regarding the multi-objective static regret, much work remains to be done in the future. We hope our initial attempt paves the way for future research.
duced from new discrepancy metric 6(x;; x", )", (X*)
We thus have RMoss (T) = sup,* EX. Ex- infx*eA,, 2 8(x;; Fr,
E DISCUSSION ON AN ALTERNATIVE METRIC BASED ON PROJECTION
In this section, we discuss an alternative discrepancy metric based on projection onto the Pareto optimal set. Then we explain why it is unsuitable to measure the Pareto suboptimality in some cases.
The metric is formulated as follows, which we term Aproj At each round t, we project the generated decision 2, onto the Pareto optimal set X namely xproj E arg min "xx; || 1|,, and then mea-
sure the Euclidean distance between Fx(x) and F((ppro)) ), i.e., Apros (z,) [x,)) FF (T I| Different from the PSG metric A, that directly measures the distance between the actual loss Fy (2t)
and the entire Pareto front Pf in the loss space, the projection based metric A proj only compares the actual loss F((x)) with the loss Fx(xpro)) evaluated at single comparator Tproj.
In intuition, prros ignores the landscape of the Pareto front, since the choice of æproj only depends on the Pareto set, whose structure in the decision domain does not necessarily align with the land- scape of the Pareto front in the loss space. Therefore, the comparator prroj may not be a good point measure the Pareto suboptimality of 24 in the loss space. In comparison, PSG directly compares
22

---

Under review as a conference paper at ICLR 2022
(zz) with the entire Pareto front, thus is always able to measure the Pareto suboptimality of the generated decision Z2.
In the following, we provide example in the two-objective convex setting to corroborate this point. In our example, the loss Ft (((po)))) induced by the projected decision Zproj is actually the most remote point from (1(2))) in the Pareto front Pr. Moreover, for the second objective, have (I > fo (zx). Therefore, Tproj is not a proper point to measure the Pareto suboptimality of 2t regarding Pt. Notably, measuring the Euclidean distance between (xproj) and F((r)) is meaningless, since Zproj performs even worse than in the second objective.
5, S 0}, which is rectangle in R We assume there two objectives, and at round t, the loss function F: R
Concretely, we consider the decision set = ((x) 2²)] -1
takes F, .x²) = (2 2m x² 2nd 2=²==²), Since F; is linear transformation, is convex. The decision set X and the image set (x) are shown in Figure. It is easy to verify that, the Pareto optimal set X² ((-1,2²) -1 S x² S 0} U {(x -1) -1 S x1 S 0), which consists of two = (0,0) at this round t, which incurs the
line segments. We assume the generated decision loss F((xz) = (0, 0). Then the projection of Ie on the Pareto set is Zproj = (-1,0) 0) or (0, -1). Due to symmetry,
only consider Tproj (-1,0), then the loss evaluated the comparator is Fo (- 3 3.. From the plot in Figure, it is obvious that Fi(Zpro)) is the most remote point from (x( in the Pareto front. Moreover, regarding the second objective, fl (Eproo) > (2x),
which means Tproj does not even dominate Ti--
As comparison, also investigate PSG in the above example. Recall that, in Proposition PSG (x, equals s xnf A (1(x)))F,(x)))) or equivalently suPrex; min (1,)- and the comparator 2 attaining the supremum is (-1,-1), which we denote as ZPSG. Then the compared loss (T (-). }). which is exactly the closest point to Fe(xe) in the Pareto front. Moreover, TPSG dominates 24. Hence, compared to the projection-basee metric Ap"oJ that compares (z;) with the most remote point the Pareto front, PSG obviously more reasonable to measure the Pareto suboptimality in the multi-obeective setting.
f+)))) It is easy to verify that 4x(x))
23


Reviews:
[{"review_id": "l_Z65KNYFhT", "reviewer": "Reviewer_ieZJ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Writing: \n\nThe writing of the paper is clear in general and easy to follow. \n\nNovelty:\n\n1. This paper introduces multi-objective online convex optimization, which is a novel and very well-motivated. \n\n2. 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. \n\n3. The authors successfully prove the proposed methods enjoy sublinear multi-objective regret, and the experiments also the effectiveness of the proposed methods. \n\nSome questions and minor points:\n1. 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)?\n\n2. It would be great if lower bound wrt m could be obtained. \n\n3. 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. \n\n4. Eq.(1): $x$ -> $x_t$\n\n", "summary_of_the_paper": "1. This paper introduces the problem of multi-objective online convex optimization.\n2. The authors propose to use PSG as the performance metric, and show that it is related to the dynamic regret. \n3. The authors develop algorithms that enjoy sublinear multi-objective regret, and also conduct experiments to show the effectiveness of the proposed methods. ", "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. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "SHg6mCRb9y", "reviewer": "Reviewer_Qnvq", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n1 - 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.\n\n2 - 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:\n\n- Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online Optimization: Competing with Dynamic Comparators. Artificial Intelligence and Statistics (AISTATS), 2015.  \n\n- Shahin Shahrampour and Ali Jadbabaie, Distributed Online Optimization in Dynamic Environments Using Mirror Descent. IEEE Transactions on Automatic Control (TAC), March 2018\n\n- Nima Eshraghi and Ben Liang. On the dynamic regret of Online Multiple Mirror Descent. Publicly available at https://openreview.net/forum?id=RepN5K31PT3\n\nThe last reference seems to have a similar idea and even acronym OMMD, but in over a single-objective online learning domain. \n\n4 - 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?\n\n5 - 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. \nThe 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?\n\n6 - The paper is mostly clear, and I enjoyed reading it. However, there are some minor unclear parts:\nIn 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_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. ", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QClXhRoiX9i", "reviewer": "Reviewer_3rTx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: A novel framework is proposed. Two new algorithms which both theoretically and experimentally work in the latter framework are designed.\nWeaknesses: \n(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.\n(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_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$). ", "summary_of_the_review": "The main weakness of the paper is that the static regret is not bounded by the proposed algorithms.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LrdZwbcBy4W", "reviewer": "Reviewer_9N6u", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nTo 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. \n\nFor 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.   \n\nNevertheless, 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? \n", "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.\n", "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.\n\n*** After Rebuttal Phase ***\n\nThe 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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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