Multi-Objective Online Learning
Authors: Jiyan Jiang
Wenpeng Zhang
Shiji Zhou
Lihong Gu
Xiaodong Zeng
Wenwu Zhu
Venue: ICLR 2023 notable top 25% (2023)

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 regret. This regret is built upon a sequence-wise extension of the commonly used discrepancy metric Pareto suboptimality gap in zero-order multi-objective bandits. We then derive an equivalent form of the regret, making it amenable to be optimized via first-order iterative methods. To motivate the algorithm design, we give an explicit example in which equipping OMD with the vanilla min-norm solver for gradient composition will incur a linear regret, which shows that merely regularizing the iterates, as in single-objective online learning, is not enough to guarantee sublinear regrets in the multi-objective setting. To resolve this issue, we propose a novel min-regularized-norm solver that regularizes the composite weights. Combining min-regularized-norm with OMD results in the Doubly Regularized Online Mirror Multiple Descent algorithm. We further derive the multi-objective regret bound for the proposed algorithm, which matches the optimal bound in the single-objective setting. Extensive experiments on several real-world datasets verify the effectiveness of the proposed algorithm.

Published as a conference paper at ICLR 2023
MULTI-OBIECTIVE ONLINE LEARNING
Jiyan Jiang"
Wenpeng Zhang"1 Ant Group Beijing, China
Shiji Zhou
Tsinghua University Beijing, China sejiys5eeut.ook.oo com
Tsinghua University
Beijing, China
changkenpengg@gmal.ccc com
2houshh_1100@gmall.coo com
Lihong Gu, Xiaodong Zeng
Wenwu Zhu
Ant Group
Tsinghua University
Hangzhou, China
Beijing, China
[iihong, , glb, xiaodong. zxd]eantgroup..
wwzhuêtsinghua, edu.
ABSTRACT
This paper presents systematic study of multi-objective online learning. We first formulate the framework of Multi-Objective Online Convex Optimization, which encompasses novel multi-objective regret. This regret is built upon sequence- wise extension of the commonly used discrepancy metric Pareto suboptimality gap in zero-order multi-objective bandits. We then derive an equivalent form of the regret, making it amenable to be optimized via first-order iterative methods. To motivate the algorithm design, we give an explicit example in which equipping OMD with the vanilla min-norm solver for gradient composition will incur a linear regret, which shows that merely regularizing the iterates, as in singlc-objective online learning, is not enough to guarantee sublinear regrets in the multi-objective setting. To resolve this issue, we propose novel min min-regularized-nne norm solver that regularizes the composite weights. Combining min-regularized-non norm with OMD results the Doubly Regularized Online Mirror Multiple Descent algorithm. We further derive the multi-objective regret bound for the proposed algorithm, which matches the optimal bound in the single-objective setting. Extensive experiments on several real-world datasets verify the effectiveness of the proposed algorithm.
INTRODUCTION
Traditional optimization methods for machine learning are usually designed optimize single objective. However, in many real-world applications, we are often required to optimize multiple correlated objectives concurrently. For example, in autonomous driving (Huang et al., 2019 Lu
et al. 2019b), self-driving vehicles need to solve multiple tasks such as self-localization and object identification the same time. In online advertising (Ma al. 2018a b), advertising systems need to decide on the exposure of items to different users to maximize both the Click-Throuse Through Rate (CTR) and the Post-Click Conversion Rate (CVR). In most objti-objectivv scenarios, the objectives may conflict with each other (Kendall et al. 2018). Hence, there may not exist any single solution that can optimize all the objectives simultaneously. For example, merely optimizing CTR or CVR will degrade the performance of the other (Ma et al. 2018a
Multi-objective optimization (MOO) (Marler & Arora 2004 Deb 2014) is concerned with opti- mizing multiple conflicting objectives simultaneously. It seeks Pareto optimality, where sin- gle objective can be improved without hurting the performance of others. Many different meth- ods for MOO have been proposed, including evolutionary methods (Murata et al. 1995 Zitzler & Thiele 1999), scalarization methods (Fliege & Svaiter, 2000). and gradient-basee iterative methods [Désidéri[2011 Recently, the Multiple Gradient Descent Algorithm (MGDA) and its variants have been introduced to the training of multi-task deep neural networks and achieved great empirical success (Sener Koltun 2018). making them regain a significant amount of research interest (Lin) ct al. 2019 Yu et al. 2020 Liu et al. 20211. These methods compute composite gradient based on
"Equal contributions.
'Corresponding author.

---

Published as a conference paper at ICLR 2023
the gradient information of all the individual objectives and then apply the composite gradient to up- date the model parameters. The composite weights are determined by a min-norm solver (Désidéri. 2012) which yields common descent direction of all the objectives.
However, compared to the increasingly wide application prospect, the gradient- iterative algo- rithms are relatively understudied, especially in the online learning setting. Multi-objective online learning is of essential importance for reasons in two folds. First, due to the data explosion in many real-world scenarios such as web applications, making in-time predictions requires performing on- line learning. Second, the theoretical investigation of multi-objective online learning will lay a solid foundation for the design of new optimizers for multi-task deep learning. This is analogous to the single-objective setting, where nearly all the optimizers for training DNNs are initially analyzed in the online setting, such as AdaGrad (Duchi et al. 2011) ), Adam (Kingma & Ba 2015), and AMS- Grad (Reddi et al. 2018).
In this paper, we give systematic study of multi-objective online learning. To begin with, we formulate the framework of Multi-Objective Online Convex Optimization (MO-OCO). One major challenge in deriving MO-OCO is the lack of a proper regret definition. In the multi-objective set- ting, in general, no single decision can optimize all the objectives simultaneously. Thus, to devise the multi-objeccivve regret, we need to first extend the single fixed comparator used in the single- objective regret, i.e., the fixed optimal decision, to the entire Pareto optimal set. Then need an appropriate discrepancy metric to evaluate the gap between vector-valued losses. Intuitively, the Pareto suboptimality gap (PSG) metric, which is frequently used in zero-order multi-objective ban- dits (Turgay et al. 2018 Lu et al. 2019a), is a very promising candidate. PSG can yield scalarized measurements from any vector-valued loss given comparator set. However, we find that vanilla PSG is unsuitable for our setting since it always yields non-negative values and may be too loose. In a conerete example, we show that the naive PSG-based regret R1 (T) can even be linear w.r.t. T when the decisions are already optimal, which disqualifies it as regret metric. To overcome the failure of vanilla PSG, we propose its sequence-wise variant termed S-PSG, which measures the suboptimality of the whole decision sequence to the Pareto optimal set of the cumulative loss func- tion. Optimizing the resulting regret (T') will drive the cumulative loss to approach the Pareto front. However, as zero-order metric motivated geometrically, designing appropriate first-order algorithms to directly optimize it is too difficult. To resolve the issue, we derive a more intuitive equivalent form of (T) via highly non-trivial transformation.
Based on the MO-OCO framework, we develop a novel multi- multi-objective online algorithm termed Doubly Regularized Online Mirror Multiple Descent. The key module of the algorithm is the gradi- ent composition scheme, which calculates a composite gradient in the form of a convex combination of the gradients of all objectives. Intuitively. the most direct way determine the composite weights is to apply the min-norm solver (Désidéri 2012) commonly used in offline multi-objective optimiza- tion. However, directly applying min-norm is not workable in the online setting. Specifically, the composite weights in min-norm are merely determined by the gradients at the current round. In the online setting, since the gradients are adversarial, they may result in undesired composite weights, which further produce a composite gradient that reversely optimizes the loss. To rigorously verify this point, we give an example where equipping OMD with vanilla min-norm incurs linear regret, showing that only regularizing the iterate, as in OMD, is not enough to guarantee sublinear regrets in our setting. To fix the issue, we devise a novel min-regularized-nnnm -orm solver with an explicit regularization composite weights. Equipping it with OMD results in our proposed algorithm.
In theory, we derive a regret bound of O(vT) for DR-OMMD, which matches the optimal bound in the single-objective setting (Hazan et al., 2016) and is tight w.r.t the number of objectives. Our analysis also shows that DR-OMMD attains a smaller regret bound than that of lincarization with fixed composite weights. We show that, in the two-objective setting with linear losses, the margin between the regret bounds depends on the difference between the composite weights yielded by the two algorithms and the difference between the gradients of the two underlying objectives.
To evaluate the effectiveness of DR-OMMD, we conduct extensive experiments on several large- scale real-world datasets. We first realize adaptive regularization via multi-objective optimization, and find that adaptive regularization with DR- OR-OMMD sigmificantly outperforms fixed regularization with linearization, which verifies the effectiveness of DR-OMMD over linearization in the convex setting. Then we apply OMMD deep online multi-task learning. The results show that DR- OMMD is also effective in the non-convex setting.
2

---

Published as a conference paper at ICLR 2023
2
PRELIMINARIES
In this section, we briefly review the necessary background knowledge of two related fields.
2.1 OULTI-OBIECTIVE OPTIMIZATION
Multiple-objective optimization (MOO) is concerned with solving the problems of optimizing multiple objectives simultancously Fliege & Svaiter, 2000, Deb 2014). In general, since different objectives may conflict with each other, there no single solution that can optimize all the objectives at the same time, hence the conventional concept of optimality used in the singlc-objective setting is no longer suitable. Instead, MOO seeks to achieve Pareto optimality. In the following, we give the relevant definitions more formally. We use a vector-valued loss F = (f',...,,f') to denote the objectives, where m 2 and f : X + IR, E {I,... (I,....,, m). X R. the i-th loss function.
Definition 1 (Pareto optimality). (a) For any two solutions x, x' E X. we say that æ dominates a', denoted as x or x! > æz if (ax) S (ax') for all and there exists one i such that (*)x)) < (z"); otherwise, we say that a does not dominate x', denoted as x A x' or x' y x. (b) A solution x" E X is called Pareto optimal if is not dominated by any other solution X'.
Note that there may exist multiple Pareto optimal solutions, For example, it is easy to show that the optimizer of any single objective, i.e., x, E arg min f'( i E {1....,m) mm. is Pareto optimal. Different Pareto optimal solutions reflect different trade-offs among the objectives (Lin et al. 2019).
Definition 2 (Pareto front). (a) All Pareto optimal solutions form the Pareto set (x
(b) The image of Px (F) constitutes the Pareto front, denoted as P(H) (F(x) x E (F)).
Now that we have established the notion of optimality in MOO, we proceed to introduce the metrics that measure the discrepancy of an arbitrary solution æ E X' from being optimal. Recall that, in the singlc-objective setting with merely one loss function f Z - R. for any 2 E Z, the loss difference f()) - min f2z") is directly qualified for the discrepancy measure. However, in MOO with more than one loss, for any E X', the loss difference F(x) F(z"), where x" E Px is a vector. Intuitionally, the desired discrepancy metric shall scalarize the vector-valued loss difference and yield 0 for any Pareto optimal solution. In general, in MOO, there are two commonly used discrepancy metrics, i.c., Pareto suboptimality gap (PSG) (Turgay et al. 2018) and Hypervolume (HV) (Bradstreet 2011). As HV is complex volume- based metric, is more difficult to optimize via gradient-based algorithms (Zhang & Golovin| (020).. Hence in this paper. we adopt PSG, which has already been extensively used in multi-objective bandits (Trray al. 2018 Lu et al. 2019a). Definition (Pareto suboptimality gar.). For any æ E X. the Pareto suboptimality gap to a given comparator set Z C X. denoted as A(x; Z, F), is defined as the minimal scalar 2 0 that needs to be subtracted from all entries of F F(x), such that F(x) - el is not dominated by any point in Z, where 1 denotes the all-one vector in Rmm, i.e.,
A (x;2 Z, F) = inf e, s.t. V x" E 2, Die (1,..,,,,, -<<)) e00
Clearly, PSG is a distance- based discrepancy metric motivated from purely geometric viewpoint. In practice, the comparator set Z is often set to be the Pareto set X = xP)(F Turgay et al. 2018); therein for any x: K., its PSG is always non-negative and equals zero if and only if x: Px
Multiple Gradient Descent Algorithm (MGDA) is an offline first-order MOO algorithm (Fliege
& Svaiter 2000; Désidéri 2012). At each iteration I E {1...., L} (L is the number of iterations), comp
first computes the gradient V (2)) of each objective, then derives the composite gradient g)
Em / as a convex combination of these gradients, and finally applies gi comp (n is the step size). The core part of MGDA is the module that determines the composite weights A (A, ..,,.,,1 X²"), given by
comp to execute a
gradient descent step update the decision, i.e., 11-1 at ng;
A arg min A:ES...
Σn 1-1 XVVl
where Sn = R X = 1,X 0, (1..... m)} is the probabilistic simplex in RRM. This is min-norm solver, which finds the weights in the simplex that yield the minimum L2- norm the composite gradient. Thus MGDA is also called the min-norm method. Previous works
Our definition looks bit different from
Turgay et al. 2018 In Appendix B we show they are equivalent.
3

---

Published as a conference paper at ICLR 2023
Sener & Koltun 2018) showed that when all f convex functions, MGDA is guaranteed to decrease all the objectives simultaneously until it reaches a Pareto optimal decision.
Désidéri 2012
2.2 ONLINE CONVEX OPTIMIZATION
Online Convex Optimization (OCO) Zinkevich, 2003 Hazan et al. 2016) is the most commonly adopted framework for designing online learning algorithms. It can be viewed as a structured re- peated game between learner and an adversary. At each round & E {l...., T), the learner is required to generate a decision Øt from a convex compact set X' C IR". Then the adversary replies the learner with convex function ft : the learner is to minimize the regret with respect to the best fixed decision in hindsight, i.c..
and the learner suffers the loss f( The goal of
R(T) = - f((z))
min Σ fx
E
meaningful regret is required to be sublinear in T. i.e., limy-+ R(T)/T= O, which implies that when 7' is large enough, the learner can perform as well the best fixed decision in hindsight.
Online Mirror Descent (OMD) (Hazan et al. 2016) is a classic first-order online learning algo- rithm. At each round t {1, (1,..., T,, OMD yields its decision via
Ft+1 arg min ( (<.)), æ) + Bn(ax,
where 1) is the step size, R: X R is the regularization function, and BR x') (())) R(x')) (VR(('), ) x - x²) is the Bregman divergence induced by R.. As a meta-algorithm, by instantiating different regularization functions, OMD can induce two important algorithms, i.e. Online Gradient Descent (Zinkevich] 2003) and Online Exponentiated Gradient (Hazan et al. 2016).
MULTI-OBIECTIVE ONLINE CONVEX OPTIMIZATION
In this section, we formally formulate the MO-OCO framework.
Framework overview. Analogously to single-objective OCO, MO-OCO can be viewed as a re- peated game between online learner and the adversarial environment. The main difference is that in MO-OCO, the feedback is vector-valued. The general framework of MO-OCO is given as follows. At each round & E [l...., T}, the learner generates decision 2, from given convex compact decision set X' C R". Then the adversary replies the decision with a vector-valued loss function F; + R whose i-th component fi X' + is convex funetion corresponding to the i-th objective, and the learner suffers the vector-valued loss (x:). The goal of the learner is to generate a sequence decisions {
12" to minimize a certain kind of multi-objective regret.
The remaining work in framework formulation is give an appropriate regret definition, which is the most challenging part. Recall that the single-objective regret R(T) Σ f((x)) -I fe(x") is defined as the difference between the cumulative loss of the actual decisions {x, and that of the fixed optimal decision in hindsight objective analogy to RRTT), we encounter two issues. First, in the multi-objective setting, no single decision can optimize all the objectives simultaneously cumulative loss with that of any single decision. Instead, we use the the Pareto optimal set X of the cumulative loss function ΣT, Fú, i.e., X Px(ETT, Ft), which naturally aligns with the optimality concept in MOO. Second, compare (æx, ). and X" in the loss space, we need a dis- crepancy metric to measure the gap between vector losses. Intuitively, we can adopt the commonly used PSG metric (Turgay al. (218).. But we find that vanilla PSG is not appropriate for OCO, which is largely different from the bandits setting. We explicate the reason in the following.
E arg min ΣT f(x)). When defining the multi-
general, hence we cannot compare the
3.1 THE NAIVE REGRET BASED ON VANILLA PSG FAILS IN MO-OCO
By definition, at each round the difference between the decision 2; and the Pareto optimal set can be evaluated by PSG A(x;; X", F,). Naturally, we can formulate the multi-objective regret by accumulating A(R;; X", Ft) over all rounds, i.e.,
RT) = Σn T
A
1=1
4

---

Published as a conference paper at ICLR 2023
Recall that the single-objective regret can also expressed as R(T) (T) essentially extends the scalar discrepancy fe( (( to the PSG metric A ( X Fi). However, these two discrepancy metries have a major difference, i.e., fa(x,) fx(')) f can be neg- ative, whereas A ( X", Fe) is always non-negative. In previous bandits settings (Turgay et al.) 2018), the discrepancy is intrinsically non-negative, since the comparator set is exactly the Pareto optimal set of the evaluated loss function. However, the non-negative property of PSG can be prob- lematic in our setting, where the comparator set X' is the Pareto of the cumulative loss function, rather than the instantaneous loss Ft that is used for evaluation. Specifically, at some round t, the de- cision ze may Pareto dominate all points in X w.r.t. Ft. which corresponds to the single-objective setting where it is possible that f((x)) < (a(")) at some specific round. In this case, we would expect the discrepancy metric at this round to negative. However, PSG can only yield this case, making the regret much looser than we expect. In the following, we provide an example in which the naive regret (T) is linear w.r.t. T even when the decisions Fy are already optimal.
(f=()((()))
Hence,
Problem instance. Set X' |-2, 2]. Let the loss function be identical among all objectives, i.e., (z) = ... [z)) and alternate between æ and -r. Suppose the time horizon T is an even number, then the Pareto optimal set X = X. Now consider the decisions 2; 1, {1....T} T). In this case, it can easily be checked that the single-objective regret of each objective is zero. indicating that these decisions objectives are identical, PSG reduces to (xx;; X [ = suPw+ex max (xx) - fx at each round t. Hence, in this case we have (T")) LIsksT/2 (sup: max x², 0} +
optimal for each objective. To calculate (T),), notice that when all the
sup=*e[-2.2 2.2] max - 1, 0}:) = 37, which linear w.r.t. T. Therefore, [T) too loose to measure the suboptimality of decisions, which is unqualified as a regret metric.
3.2 THE ALTERNATIVE REGRET BASED ON EEQUENCE-WISE PSG
In light of the failure of the naive regret, need modify the discrepancy metric in our setting. Recall that the single-objective regret can be interpreted as the gap between the actual cumulative loss Ei= fe f((z)) and its optimal value min Σ/=1 fe(x). In analogy, we can measure the gap between ΣT (x;) and the Pareto front p = = P Fi). However, vanilla PSG a point- wise metric, i.c., it can only measure the suboptimality of a decision point. To evaluate the decision sequence { we modify its definition and propose sequence-wise variant of PSG.
Definition 4 (Sequence-wise PSG). For any decision sequence {ax))=1,, the sequence-wist wise PSG (S-PSG) to a given comparator se X w.r.t. the loss sequence ( (F:) is defined as
A(f=))TEXX" (FF)T= inf e, s.t. Va" E e20
fl,.... m), Σ fl(z)) Ef((e")
1=1
Since X is the Pareto set of Σ Fr, S-PSG measures the discrepancy from the cumulative loss of the decision sequence to the Pareto front P Now the regret can be directly given
RT(T)= A((..)_. X", (FF)T=.)
Rn(TT) has a clear physical meaning that optimizing it will impose the cumulative loss to be close to the Pareto front Pt. However, since PSG (or S-PSG) is zero-order metric motivated in purely geometric sense, i.e., its calculation needs to solve a constrained optimization problem with an unknown boundary (F((x") x" E x'), is difficult to design a first-order algorithm to optimize PSG-based regrets, not to mention the analysis. To resolve this issue, we derive an equivalent form via highly non-trivial transformations, which is more intuitive than its original form.
Proposition 1. The multi-objective regret RU(T)) based on S-PSG has an equivalent form, i.e.,
Σx_ 1-1 A (F((())) - F((x")) 0).
(T) = max sup
inf x' E- XTES
Remark. (i) The above form is closely related to the single-objective regret R(T). Specifically, when m = we can prove that RT((") = max F((x,) - min Fi("), =
'I is equivalent either X X the comparator set. See Appendix C for the detailed proof.
5

---

Published as a conference paper at ICLR 2023
Algorithm 1 Doubly Regularized Online Mirror Multiple Descent (DR- (DR-OMMD)
Input: Convex set X, time horizon T' regularization parameter ag, learning rate T/e regulariza- tion function R, user preference Ao-
2: Initialize: 21 E X.
3: for t = .,, do
4: Predict e; and receive a loss function F. + I
5: Compute the multiple gradients (x;)) [ (mt), .... (x,)) E R
6: Determine the weights for the gradient composition via min-regularizee--nom
A arg min [V
+ ael|> - Aollı-
AES
7: Compute the composite gradient g: VFi(
8: Perform online mirror descent using 9:
I1+1 arg min 77 (gt, x) + BR( x1).
#EA
9: end for
max ( RR()).0. Note that in the regret analysis, we are more interested in the case of R(T) 2 (where (T) R(T)), since when R(T) < 0, it is naturally bounded by any sublinear regret bound. Hence, RT((T') is essentially aligned with R(TT) in the single-objective setting.
(ii) At its first glance, (T) can be optimized via linearization with fixed weights Xn Sm. or al- ternatively, optimizing a single objective i E {1,.... m... We remark that this is not a problem of our regret definition, but an intrinsic requirement of Pareto optimality. Specifically, Pareto optimality characterizes the status where no objective can be improved without hurting others. Hence merely optimizing a single objective naturally achieves Pareto optimality. Please refer to Proposition 8 in (Emmerich & Deutz] 2018) for the rigorous proof. As general performance metric, our regret should incorporate this special case. Later, we will design a novel algorithm based on the concept of common descent, which outperforms linearization in both theory and experiment.
4 DOUBLY REGULARIZER ONLINE MIRROR MULTIPLE DESCENT
In this section, we present the Doubly Robust Online Mirror Multiple Descent (DR-OMMD) algo- rithm, the protocol of which is given in Algorithm [ At each round 6, the learner first computes the gradient of the loss regarding each objective, then determines the composite weights of all these gradients, and finally applies the composite gradient the online mirror descent step.
4.1 VANILLA MIN-NORM MAY INCUR LINEAR REGRETS
The core module of DR-OMMD is the composition of gradients. For simplicity, denote the gradients round t matrix form (x,) f. (zt). f! (z:)] R=xm. Then the composite gradient is 9, (x,)) where X; is the composite weights. As illustrated in the preliminary, in the offline setting, the min-norm method (Désidéri 2012 Sener & Koltun 2018) a classic method to determine the composite weights, which produces common descent direction that can descend all the losses simultancously. Thus, it is tempting to consider applying it to the online setting.
However, directly applying min-norm to the online setting is not workable, which may even incur linear regrets. In vanilla min-norm, the composite weights A are determined solely by the gradients (x, at the current round t, which are very sensitive the instantaneous loss Ft. In the online setting, the losses at each round can be adversarially chosen, and thus the corresponding gradients can be adversarial. These adversarial gradients may result in undesired composite weights, which may further produce a composite gradient that even deteriorates the next prediction. In the following, provide example in which min-norm incurs linear regret. We extend OMD (Hazan al.) 2016) to the multi-objective setting, where the composite weights are directly yielded by min-norm.
Problem instance. + v < 2 u < 2,0 2 0} and the loss function at each round is
We consider a two-objective problem. The decision domain is X' {(u, v)
(I|æ: all || b1l2);
t = 2k - 1, = 1,2,... t = 2k,
(x)
(||æ b1l2, || - cll?),
k = 1, 2, ....

---

Published as a conference paper at ICLR 2023
where -1), (0, (2, -1). For simplicity, first analyze the case where the total time horizon T an even number. Then we can compute the Pareto set of the cumulative loss Ei Fr. i.c., X = {(u,0) - < - } which locates at the r-axis. For conciseness of analysis, we instantiate OMD with L2-regularization, which results in the simple OGD algorithm [McMahan 2011). We start at an arbitrary point æ1 (u1, 21) X satisfying > 0. At each round t, suppose the decision 2t (4n, vt), then the gradient of each objective w.r.t. 2y takes
g - [(2ue + 4, 20 + 2), 1 = 2h 1; (2we:
9e - { - -,
(2
20r 2), 2h
20 2), 1 = 2k.
2v + 2),
1 = 2k.
Since S v4 S 2. we observe that the second entry either gradient alternates between positive and negative. By using min-norm, the composite weights X can be computed as
((1 U4 v2)/4, A. ((3 u4 + vz)/4, (1 + u4 - 04)/4),
(3 + u + ux)/4), t = 2k 1:
2k:
We observe that both entries of composite weights alternative between above and below }. and ||Ac+1 >r111 1 2 Recall that || 11 1, hence the composite weights at two consecutive rounds change radically. The resulting composite gradient takes
(w: + 1, Ue + - 1), 1= 2k 1;
g comp
((-u,
U4 D2 - 1), 2k.
The fluctuating composite weights mix with the positive and negative second entries of gradients, making the second entry of g:
comp always negative, i.e., -u, + 0/ - < and Ut - < 0. Hence gi comp always drives D2 away from the Pareto set X that coincides with the r-axis. This essentially reversely optimizes the loss, hence increasing the regret. In fact, we can prove that it even incurs linear regret. Due to the lack of space, we leave the proof of linear regret when an odd number in Appendix H The above results of the problem instance are summarized follows.
Proposition 2. For OMD equipped with vanilla min-norm, there exists multi-objective online convex optimization problem. in which the resulting algorithm incurs a linear regret.
Remark. Stability is basic requirement to ensure meaningful regrets in online learning (MMMa- han 2017). In the single-objective setting, directly regularizing the iterate (e.g., OMD) is enough. However, as shown in the above analysis, merely regularizing D; is not enough to attain sublinear regrets in the multi-objective setting, since there is another source of instability, i.e., the composite weights, that affects the direction of composite gradients. Therefore, in mujti--bjeective online learn- ing, besides regularizing the iterates, also need to explicitly regularize the composite weights.
4.2 THE ALGORITHM
Enlightened by the design of regularization in FTRL (McMahan 2017). consider the regularizer r(x, Ao), where Xo is the pre-defined composite weights that may reflect the user preference. This results in new solver called min minn-regulrizzd-nnmm i.e.,
A arg min (a.)()))) + o (eT((A XES...
where ot is the regularization strength. Equipping OMD with the new solver, we derive the proposed algorithm. Note that beyond the regularization the iterate x, that is intrinsic in online learning, there is another regularization on the composite weights A, in min-regularized-nore larizations are fundamental, and they together ensure stability in the multi-objective online setting. Hence we call the algorithm Doubly Regularized Online Mirror Multiple Descent (DR-OMMD).
Both regu-
In principle, since it aligns well with the simplex constraint of X. Min-regularized norm can be computed very efficiently. When
take various forms such Ll-norm, L2-norm, etc. Here adopt Ll-norm
2, has closed-form solution. Specifically, suppose the gradients at round t
are gf and gf2 Set 71 = [g] (g2 9t) / - 9 I|2 and 7n = (g) (g2 91) (n)++))/lle) 1algg--00 9i 1| Given any Ao (10, 1 70) S2. we can compute the composite weights X, as (7,, - 77) where
7t max(min 1), 0}, where ," max kR),1.)

---

Published as a conference paper at ICLR 2023
When > 2, since the constraint Sm. is simplex, introduce Frank-Wond solver (Jaggi 2013) (see detailed protocol Appendix E.I We also discuss the L2-norm case in Appendix E.2
Compared to vanilla nin-norm, the composite weights in min-regularized-nont mined by the adversarial gradients. The resulting relative stability of composite weights makes the composite gradients more robust the adversarial environment. In the following, we give general analysis and prove that DR-OMMD indeed guarantees sublinear regrets.
not fully deter-
4.3 THEORETICAL ANALYSIS
Our analysis based on two conventional assumptions (Jadbabaic et 2013 Hazan et al.) 2016).
Assumption 1. The regularization function R is 1-strongly convex. In addition, the Bregman diver- gence is y-Lipschitz continuous, i.e., Bn (z. z) - (n. S 71|x | -yll. Væ, y, E domR, where domR. is the domain of R and satisfies X' C domR R. C TR.
Assumption 2. There exists some finite G > O) such that for each E (1...., m), the i-th loss fi at each round E (1....; ..,, Т) is differentiable and G-Lipschitz continuous w.r.t. || 1|2, i.e., (x) fi (x') < G æ'112. Note that in the convex setting, this assumption leads to bounded gradients, i.e., [V((()) S G for any E [I....,T},
{l,..., m), æ X.
Theorem 1. Suppose the diameter of X is D. Assume F; is bounded, i.e., [f]())) F, Ve E X, (I....,T], i m.). For any do E Sm. DR-OMMD attains
7D
I
T (IVF((
4F
R(T)
1| Aoll1).
2
Th
1F the bound attains O(VT). It matches the optimal single-objective bound w.r.t. T Hazan al. 2016) and is tight w.r.t. (justified in Appendix F2).
Remark. When 22n GVT or
22 Gvi
Comparison with linearization. Lincarization with fixed weights Ao E Sm essentially optimizes the scalar loss A F, with gradient g: (FF(x;) Ag. From OMD's tight bound (Theorem 6.8 in T nts 2
Orabona 2019)) ), we can derive a bound 2D
(zx,) for linearization. In compar-
fr
DR- FRROMMDD attains regret bound 2D + ET_ 2 minxes,. ( ) Vr which is smaller than that of linearization. Note that although the bound of lineariza- tion refers to single-objective regret R(T), the comparison is reasonable due to the consistency of the two regret metrics, i.e., RT'( max | [R(T), O} when m = 1, as proved in Proposition [ further investigate the margin in the two-objective setting with linear losses.
ison, when Cr
- 10---ol11 Aoll1): a
In the following, Suppose the loss functions are f( (x) x g, and (z) x 9 for some vectors g..gā of e R at each round. Then we can show that the margin
least (see Appendix F.3 for the detailed proof)
Th |A - Ao |1g! g 11:
M 2
4
which indicates the benefit of DR-OMMD. Specifically, while lincarization requires adequate Ao- DR-OMMD selects more proper A, adaptively; the advantange is more obvious as the gradients of different objectives vary wildly. This matches our intuition that linearization suffers from conflict gradients Yuu et 2020), while DR-OMMD can alleviate the conflict by pursuing common descent.
5 EXPERIMENTS
In this section, we conduct experiments to compare OR-OMMD with two baselines: (i) linearization performs
online learning on scalar losses X with pre-defined fixed Xo E Smi (ii) min-norm equips OMD with vanilla min-norm (Désidéri 2012 for gradient composition.
5.1 CONVEX EXPERIMENTS: ADAPTIVE REGULARIZATION
Many world online scenarios adopt regularization to avoid overfitting. A standard scheme is to add term r(x) to the loss f(( at each round and optimize the regularized loss f(( + or(z) (McMahan 201T), where a is a pre-defined fixed hyperparameter. The formalism of multi-objectivve online learning provides novel way of regularization. As r(æe) measures model complexity, it can
8

---

Published as a conference paper at ICLR 2023
Incorizelion Ce GPMD
In-gi:
12-
Averyye Los
0.25
70
66-
0.
10
2001 1920 Zic 18000 12u0
2000 40093
2300 40300
5009
(a) Efffect of Preference
(b) Leariing Curve
(3) Task
(b) Tack R
Figure 1: Results to verify the effectiveness of adaptive regularization on protein. (a) Perfor- mance of DR-OMMD and linearization under varying A (Ap: -x)). (b) Performance us- ing the optimal weights Ao = (0.1,0.9)
Figure 2: Results to verify the effectiveness of DR-OMMD in the non-convex setting. The two plots show the performance of DR-OMMD and various baselines on both tasks (Task and Task R) of MultiMNIST.
be regarded as the second objective alongside the primary goal fx(x). We can augment the loss to F((x)) = (fe(z), r(x)) and thereby cast regularized online learning into a two-objective problem. Compared to the standard scheme, our approach chooses o, X2/X/ in adaptive way.
We use two large-scale online benchmark datasets. (i) protein is a bioinformatics dataset for protein type classification (Wang 2002), which has 17 thousand instances with 357 features. (ii) covtype is a biological dataset collected from a non-stationary environment for forest cover type prediction (Blackard & Dean 1999), which has 50 thousand instances with 54 features. We set the logistic classification loss as the first objective, and the squared L2-norm of model parameters as the second objective. Since the ultimate goal of regularization is lift predictive performance, measure the average loss, i.e., Eist 4 (Tt)/T, where (xx, is the classification loss at round t.
We adopt a L2-norm ball centered at the origin with diameter K = 100 as the decision set. The learning rates are decided by a grid search over (0.1, 3.0). For DR-OMMD, the parameter Or is simply set as 0.1. For fixed regularization, the strength o = (1 - / is determined by some A E [o, 1J, which exactly linearization with weights Åo = (A 1 Ab). We run both algorithms with varying AI E O0,0...... }}. In Figure [
we plot (a) their final performance w.r.t. the choice of Ao and (b) their learning curves with desirable Ao (e.g.. (0.1, 0.9) on protein). Other results are deferred to the appendix due to the lack of space. The results show that DR-OMMD consistently outperforms fixed regularization; the gap becomes more significant when Ag is not properly set.
5.2 NON-CONVEX EXPERIMENTS: DEEP MULTI-TASK LEARNING
We use MultMNISS (Sabour et al. 2017), which is a multi-task version of the MNIST dataset for image classification and commonly used in deep multi-task learning (Sener & Koltun 2018 Lin et al. 2019). In MultiMNIST, each sample is composed of a random digit image from MNIST at the top-left and another image at the bottom-right. The goal is to classify the digit at the top-left (lask L) and that at the bottom-right (lask R) at the same time.
We follow (Sener & Koltun 2018)'s 's setup with LeNet. Learning rates in all methods are selected via grid search over [0.0001, 0.001, 0.01, 0.1}. J. For linearization, we examine different weights (0.25, 0.75). (0.5, 0.5), and (0. 0.25). For DR-OMMD, a, is set according Theorem D and the initial weights are simply set as A (0.5, 0.5). Note that in the online setting, samples arrive in sequential manner, which is different from offline experiments where sample batches are randomly sampled from the training set. Figure 2 compares the average cumulative loss of all the examined methods. We also measure two conventional metries in offline experiments, i.e., the training loss and test loss (Reddi et al. 2018): the results are similar and deferred to the appendix due to the lack of space. The results show that DR-OK RRMM outperforms counterpart algorithms using min-norm or linearization in all metrics both tasks, validating its effectiivnees in the non-convex setting.
CONCLUSIONS
In this paper, we give a systematic study of multi-objective online learning, encompassing a novel framework, new algorithm, and corresponding non-trivial theoretical analysis. We believe that this work paves the way for future research on more advanced multi-objective optimization algorithms, which may inspire the design of new optimizers for multi-task deep learning.

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGMENTS
This work was supported in part by the National Key Research and Development Program of China No. 2020AAA0106300 and National Natural Science Foundation of China No. 62250008. This work was also supported by Ant Group through Ant Research Intern Program. We would like to thank Wenliang Zhong, Jinjie Gu, Guannan Zhang and Jiaxin Liu for generous support on this project.
REFERENCES
Jacob Abernethy, Peter Bartlett, and Elad Hazan. Blackwell approachabbly and no-regret learning equivalent. In Conference Learning Theory, pp. pp. 27-46, 2011.
Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167-175, 2003.
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-11,, 1999.
David Blackwell. An analog of the minimax theorem for vector payoffs. Pacific Journal of Mathe- matics, 6(1):1-8, 1956.
Lucas Bradstreet. The hypervolume indicator for multi-objecctive optimisation: calculation and use. University of Western Australia Perth, 2011.
Róbert Busa-Fekete, Balázs Szörényi, Paul Weng, and Shie Mannor. Multi-ohjective bandits: Op- timizing the generalized gini index. In International Conference on Machine Learning, pp. 625- 634, 2017.
Nicolò Cesa-bianchi, Pierre Gaillard, Gabor Lugosi, and Gilles Stoltz. Mirror descent meets fixed share (and feels no regret). In Advances in Neural Information Processing Systems, pp. 980-988, 2012.
Zhao Chen, Jiquan Ngiam, Yanping Huang, Thang Luong, Henrik Kretzschmar, Yuning Chai, and Dragomir Anguelov. Just pick a sign: Optimizing deep multitask models with gradient sign dropout. In Advances Neural Information Processing Systems, pp. 2039-2050, 2020.
Sayak Ray Chowdhury and Aditya Gopalan. No-regret algorithms for multi-task bayesian opti- mization. In International Conference on Artificial Intelligence and Statistics, pp. 1873-1881, 2021.
Samuel Daulton, David Eriksson, Maximilian Balandar, and Eytan Bakshy. Multi-objective bayesian optimization over high nigh-dimensional search spaces. In Uncertainty in Artificial Intelligence, pp. 507-517, 2022.
Kalyanmoy Deb. Multi-objective optimization. In Search methodooogies, pp. 403-449, 2014.
Rémy Degenne, Thomas Nedelec, Clément Calauzènes, and Vianney Perchet. Bridging the gap between regret minimization and best arm identification, with application to a/b tests. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 1988-1996, 2019.
Jean-Antoine Désidéri. Multiple-gradient descent algorithm for multiobjective optimization.
Comptes Rendus Mathematique, 350(5-6)331-3118, 2012.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL/http://archiie
icss www.uuiiiiuuueee edu/ml
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12()):121-2155, 2011.
Michael TM Emmerich and André H Deutz. A tutorial on multiobjective optimization: Fundamen- tals and evolutionary methods. Natural Computing, 17(3):585-66) 609, 2018.
10

---

Published as a conference paper at ICLR 2023
Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathe- matical Methods of Operations Research, 51(3):479-455 2000.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2(3-4):157-325, 2016.
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, 22(10):2722-2113 2019.
Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimiza- tion: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pp. 2015.
Martin Jaggi. Revisiting Frank-Wolfee Projection-free sparse convex optimization. In International Conference Machine Learning, pp. 427-435, 2013.
Adrián Javaloy and Isabel Valera. Rotograd: Gradient homogenization in multitask learning. In International Conference on Learning Representations, 2021.
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In IEEE Conference on Computer Vision and Pattern Recog- nition, pp. 7482-7491, 2018.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
Mina Konakovic Lukovic, Yunsheng Tian, and Wojciech Matusik. Diversity-guided multi-objective bayesian optimization with batch evaluations. In Advances in Neural Information Processing Systems, pp. 17708-17720 2020.
Wouter Koolen. The Pareto regret frontier. In Advances in Neural Information Processing Systems, pp. 1-9, 2013.
Wouter M Koolen and Tim Van Erven. Second-order quantile methods for experts and combinatorial games. In Conference Learning Theory, pp. 155-1175, 2015.
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing-Fu Zhang, and Sam Kwong. Pareto multi-task learning. In Advances in Neural Information Processing Systems, pp. 12060-12070, 2019.
Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning. In Advances in Neural Information Processing Systems, pp. 18878-18890, 2021.
Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Multi-objective generalized linear bandits. In International Joint Conference Artificial Intelligence, pp. 3080-3086, 2019a.
Weixin Lu, Yao Zhou, Guowei Wan, Shenhua Hou, and Shiyu Song. L3-net: Towards learning based lidar localization for autonomous driving. In IEEE Conference on Computer Vision and Pattern Recognition, pp. 6389-6398, 2019b.
Jiaqi Ma. Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed H Chi. Modeling task relation- ships multi-task learning with multi-gate mixture-of-exee of-experts. In International Conference on Knowledge Discovery & Data Mining, pp. 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 In- fernational ACM SIGIR Conference Research & Development in Information Retrieval, pp. 1137-1140, 2018b.
Wesley J Maddox, Maximilian Balandat, Andrew G Wilson, and Eytan Bakshy. Bayesian optimiza- tion with dimeesiimniio outputs. In Advances in Neural Information Processing Systems, pp. 19287.192277, 2021.
11

---

Published as a conference paper at ICLR 2023
Shie Mannor, Vianney Perchet, and Gilles Stoltz. Approachability in unknown games: Online learning meets multi-objective optimization. In Conference on Learning Theory, pp. 339-355, 2014.
Timothy Marler and Jasbir S Arora. Survey of multi-bjeective optimization methods for engineer- ing. Structural and Multidhssiplinnary Optimization, 26(6):369-392) 2004.
Brendan McMahan. Follow-the follow-the-regulaiizee wew.lrrizze--eeaaaeeeeeeeo and mirror descent: Equivalence theorems and L1 regularization. In International Conference on Artificial Intelligence and Statistics, pp. 525-
533, 2011.
H Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research, 18( 1811)3111733166 2017.
Tadahiko Murata, Hisao Ishibuchi, et al. MOGA: multi-objective genetic algorithms. In IEEE International Conference on Evolutionary Computation, pp. 289-294, 1995.
Francesco Orabona. A modern introduction to online learning. arXiv preprint arXiv: 1oXiv:1912.132111 2019.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018.
Sara Sabour, Nicholas Frosst, and Geoffrey E Hinton. Dynamic routing between capsules. In Advances in Neural Information Processing Systems, pp. 3859-3869, 2017.
Ozan Sener and Vladlen Koltun. Multi-task learning multi-objective optimization. In Advances in Neural Information Processing Systems, pp. 525-536, 2018.
Nati Srebro, Karthik Sridharan, and Ambuj Tewari. On the universality of online mirror descent, In Advances in Neural Information Processing Systems, pp. 2645-2653, 2011.
Cem Tekin and Eralp Turgay. Multi-objective contextual mumdi-armed bandit with dominant ob- jective. IEEE Transactions on Signal Processing, 66( (6(14):3799-3813 2018.
Eralp Turgay, Doruk Oner, and Cem Tekin. Multi-objective contextual bandit problem with similar- ity information. In International Conference on Artificial Intelligence and Statistics, pp. 1673-
2018.
Yuanyu Wan, Wei-Wer Tu, and Lijun Zhang. Online strongly convex optimization with unknown delays. Machine Learning, 111(3):771-95., 2022.
Jung- Ying Wang. Application of support vector machines in bioinformatics. PhD thesis, National Taiwan University, 2002.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. In Advances in Neural Information Processing Systems, pp. 5824-5836, 2020.
Richard Zhang and Daniel Golovin. Random hypervolume scalarizations for provable multi- objective black box optimization. In International Conference on Machine Learning, pp. 11096 11105, 2020.
Peng Zhao and Lijun Zhang. Improved analysis for dynamic regret of strongly convex and smooth functions. In Learning for Dynamics and Control, pp. 48-59, 2021.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference Machine Learning, pp. 928-936. 2003.
Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: comparative case study and the strength Pareto approach. IEEE transactions Evolutionury Computation, 3(4):257- 271, 1999.
12

---

Published as a conference paper at ICLR 2023
APPENDIX
The appendix is organized as follows. Appendix A reviews related work. Appendix B validates the correctness of our definition of PSG. Appendix discusses the domain of the comparator in S-PSG, indicating that it makes no difference whether the comparator is selected from the Pareto optimal set or from the whole domain. Appendix D provides the detailed derivation of the equivalent form of RT"T). Appendix discusses how to efficiently compute the composition weights for the min- regularized-norm solver. Appendix [ discusses the order of DR-OMMD's regret bound with fixed or adaptive learning rate, shows the tightness of the derived bound, and provides more details on the regret comparison between DR-OMMD and lincarization. Appendix G
E
supplements more details provide detailed proof's of the remaining theoretical claims in the main paper. Finally, Appendix supplements regret analysis of DR-OMMD in the strongly convex setting.
in the experimental setup and empirical results. Appendix H and |
A RELATED WORK
In this section, we review previous work in some related fields, i.e., online learning, multi-objective optimization, multi-objeecivv multi-armed bandits, and multi-objective Bayesian optimization.
A.1 ONLINE LEARNING
Online learning arms to make sequential predictions for streaming data. Please refer to the introduc- tion books (Hazan et al. 2016 Orabona 2019) for more background knowledges.
Most of the previous works on online learning are conducted the single-objective setting. As far are concerned, there are only
lines of work concerning multi-objeccive learning. The first line of works provides a multi-objective perspective of the prediction- vitrrion-iiii--eepee----iiiiiiii (PEA) problem (Koolen 2013 Koolen & Van Erven 2015). Specifically, they view each individual expert as multi-objective criterion, and characterize the Pareto optimal trade-offs among different experts. These works have two main distinctions from our proposed MO-OCO. First, they are still built upon the original PEA problem where the payoff of each expert (or decision) is a scalar, while we focus on vectoral payoffs. Second, their framework is restricted to an absolute loss game, whereas our framework is general and can be applied to any coordinate- wise convex loss functions.
The second line of work studies online learning with vectoral payoffs via Blackwell approachability (Blackwel] 1956, Mannor et al.) 2014 Abernethy et al.) 2011). In their framework, the learner is given a target set m and its goal is to generate decisions (æx ) to minimize the distance be- tween the average loss E Le (zxe) and the target set T. There are two major differences between Blackwell approachability and our proposed MO-OCO: previous works on Blackwell approachabil- ity are zero-order methods and the target set T is often known beforehand (also see the discussion in (Busa-Fekete et al., (2017)) while in MO-OCO we intend to develop a first-order method reach the unknown Pareto front.
A.2 MULTI-OBJECTIVE OPTIMIZATION
Multi-objective optimization aims to optimize multiple objectives concurrently. Most of the previ- ous works on multi-objective optimization conducted in the offline setting, including the batch optimization setting (Désidéri 2012 iu et al. (222)) and the stochastic optimization setting (Sener & Koltun 2018 Lin et al. 2019 Yu 2020 Chen et al., (2020) Javaloy Valera [202I). These methods are based on gradient composition, and have shown very promising results in multi-task learning applications.
Despite the existence of previous works multi-objective optimization, as the first work of multi- objective optimization in the OCO setting, our work is largely different from them in three aspects. First, we contribute the first formal framework of multi-objective online convex optimization. In par- ticular, our framework is based on a novel equivalent transformation of the PSG metric, which is in- trinsically different from previous offline optimization frameworks. Second, we provide showcase in which a commonly used method in the offline setting, namely min-norm (Désidéri 2012) Sener & Koltun 2018), fail to attain sublinear regret in online setting. Our proposed min-regularized--nom
13

---

Published as a conference paper at ICLR 2023
is novel design when tailoring offline methods to the online setting. Third, the regret analysis of multi-objective online learning is intrinsically different from the convergence analysis in the offline setting (Yu et al. 2020).
A.3 MULTI-OBJECTIVE MULTI-ARMED BANDITS
Another branch of related works study multi-objective optimization in the multi-armed bandits set- ting -Bus--Fekete et al. 2017 Tekin& & Turgay 2018 Turgay et al. 2018; Lu al. 2019a Degenne eet al,120011 Among these works, the most relevant one to ours is (Tugay et al. 2018). which introduces the Pareto suboptimality gap (PSG) metric to characterize the multi-objective regret in
the bandits setting, and proposes a zero-order zooming algorithm to minimize the regret.
In this work, regret definition also utilizes the PSG metric (Turay al., 2018). However, as the first study of multi-objective optimization in the OCO setting, our work is intrinsically different from these previous works in the following aspects. First, as PSG is zero-order metric, perform a novel equivalent transformation. making it amenable to the OCO setting, Second, our proposed al- gorithm a first-order multiple gradient algorithm, whose design principles are completely distinct from zero-order algorithms. For example, the concept of the stability of composite weights does not even exist the design of previous zero-order methods for multi-objective bandits (Turgay et al.) 2018 [uu et al.) (019a)) Third, the regret analysis of MO-OCO is intrinsically different from that in the bandits setting.
A.4 OULTI-OBJECTIVE BAYESIAN OPTIMIZATION
The final area related to our work is multi-objective Bayesian optimization ÇZhagg & Golovin 2020 Konakovic Lukovic et al. 2020 Chowdhury & Gopalan 2021 Maddox et al.] Daulton al, 2022). which studies Bayesian optimization with vector-valued feedback. There are two branches of works in this area, using different notions of regret. The first branch based on scalarization, which adopts the expectation of the gap between scalarized losses over some given distribution Chowdhury & Gopalan 2021) as the regret. In this approach, the distribution of scalarization can be understood as a set of preference, which needs to be known beforehand. The second branch is based on Pareto optimality (Zhang & Golovin 2020), which uses hypervolume as the discrepancy metric and adopt the gap between the true Pareto front and the estimated Pareto front as the regret.
As the first work on multi-objective optimization the OCO setting, our work is largely different from these works the following aspects. First, the regret definitions are different. Specifically, compared to the first branch based on scalarization, our regret definition is purely motivated by Pareto optimality, which does not need any preference in advance; compared to the second branch using hypervolume, we note that hypervolume is mainly used for Pareto front approximation, which unsuitable to our adversarial setting where the goal is to impose the cumulative loss to reach the Pareto front. Second, multi-objective Bayesian optimization is conducted in stochastic setting, which typically assumes that the losses follow some Gaussian distribution, whereas our work is conducted in the adversarial setting where the losses can be generated arbitrarily.
B AN EQUIVALENT DEFINITION OF PSG
Recall that in Definition 3 we formulate the PSG metric as constrained optimization problem. We note that, since the PSG metric is based on the notion of "non-dominance" (Turgay al. 2018). its most direct form is actually
A' F) = infe,
e20
- s.t. VX" E [
or ViE fl....... m), f') f((x)-(x)))))) c (x(")
At the first glance, the above definition seems to be quite different from Definition 3 since it has an extra condition "Vi E (1,...,m, m). fa(
= f'("") In the following, we prove that both definitions actually yield the same value due to the infimum operation c.
Specifically, for any possible pair (x, 1,, F), we denote A' K F) ép and A (x; K,, F) En- By comparing the constraints of both definitions, it is obvious that 6g must satisfy the constraint
14

---

Published as a conference paper at ICLR 2023
of A' A'xx; KC",,,, F), hence the infimum operation guarantees that d I co. It remains to prove that 6 2 cp. To this end, we only need to show that en + E satisfies the constraint of A A(x; K), for any & > 0. Consider that either 7i E (1,..., m), (ax) - 6 < f'(x") or Vi E (1......) _,, (((())))
arbitrary x" K.* From the definition of Ax , we know
c (a)). 6 -- f((") for any a 0. Since it holds for any x" E K", 6 + lies in the feasible region of ((x; K"; F), hence we have co S 6 + E, > 0 and thus 6o S Ev. In summary, we have A' K", FF) Ax;;K" F)) for any pair (z, KC",
Whichever condition holds, must have 7i (1,...,m)) m....,m),.
(x) f
C DISCUSSION ON THE DOMAIN OF THE COMPARATOR IN S-PSG
Recall that in Definition the comparator æ' in S-PSG is selected from the Pareto optimal set X of the cumulative loss Σi= Fi. This actually stems from the original definition of PSG (Turgay et al.) (2118), which uses the Pareto optimal set the comparator set. In fact, comparing with Pareto optimal decisions X² already enough to measure the suboptimality of any decision sequence {z, 1-=1 The reason is that, for any non-optimal decision x' X' -'" there must exist some Pareto optimal decision x" E X that dominates x', hence the suboptimality metric does not need to compare with this non-optimal decision x'. In other words, even if we extend the comparator set in S-PSG to the whole domain X, the modified form will be equivalent to the original form based on the Pareto optimal set X In the following, we strictly prove this equivalence A {( X, (Fi)=E) = {({=)))= X" (FF))=))
Specifically, we modify the definition of S-PSG and let the comparator domain X' be any subset of the decision domain X, i.e.,
T
I (mx) - Σ (a))
A(Ex)) X" (R) = inf s.t. Vo" E xX E (1....,m)
Σ
<20
1=1
1=1
Then the modified regret based on the whole domain X' takes (T) = A [( X. (F
Now we begin to prove the equivalence A({x;)] [[1=t)_== i (Fi)T= ) = A [z: 1T
)==i;="' X', (Fi (F)) For
any X' C C. let E(²') denote the constraint of ((xx,) Mix (Fi)T i.e.
T
T
E(X²) = 20 Vx" EX, (1...., m). S(a.) - << Σ f(aa"),
then A(Ix,)T-i X', (FIIT=))
= inf E(Y).. Henee, we just need to prove inf ((X) = inf ((X*).
On the one hand, since X' c. X, from the above definition of S-PSG, it is casy to check that for any E (x)), it must satisfy E {x²)). Hence, we have E(X) C E(X").
On the other hand, given any E E(x'), we now check that e E ((Y). To this end, we con- sider arbitrary point x" X in two cases. (i) If x" E X², since have Σr- ET=1to f (a:) - Σr f'o (æ") for some ig. (ii) If x & X", since X is the Pareto optimal set of Ei= Fú, there must exist some Pareto optimal decision & E X that dominates x" w.r.t. Ei=1 Fr, which means that -T' fi( < Et f((")) for all i {l,..., m... Notice that 6 EE EEE((" gives Eis (x)) - < Σt= ( for some io, hence in this case we also have Σt f. (x,) -<< (x,))E<<
E(X"), we naturally
El Ei=ft fx"".. Combining the above two cases, prove that E E(Y), and consequently E(X²) C C(X)..
In summary, we have E(x) = E(X*), hence A((x)) (F.) inf E(X) inf E(X*) A A(<x,)T] X", (F) Therefore, it makes no difference whether the comparator in Rn is generated from the Pareto optimal set X or from the whole domain X.
D DERIVATION OF THE EQUIVALENT MULTI-OBJECTIVE REGRET FORM
In this section, We strictly derive the equivalent form of (T) in Proposition which is highly non-trivial and forms the basis of the subsequent algorithm design and theoretical analysis.
15

---

Published as a conference paper at ICLR 2023
Proof of Proposition Recall that the PSG metric used in Ru(T) is extension of vanilla PSG to leverage any decision sequence. To motivate the analysis, we first investigate vanilla PSG A(x; X², FF) that deals with single decision æ, and derive useful lemma as follows.
Lemma 1. Vanilla PSG has an equivalent form, i.e.,
A(x; X F) sup inf ((F(x))F(()))
E. XESm
where for any vector (1) ,... (T)) IRm the truncation (I)+ produces a vector whose i-th entry equals to max(1' 0} for all m.
Proof. In the definition of PSG, the evaluated decision æ is compared to all Pareto optimal points x' X². For any fixed comparator x' E X', we define the pair-wise suboptimality gap w.r.t F between decisions a and x' as follows
8(;; x', F) inf fe F(x) c1 y F(x')}
20
Hence, PSG can be expressed as
A X" F)
sup 5(x; F). x E'Ex'
To proceed, we analyze the pair-wise gap 8(n; F). From its definition, we know that d(x; ar, F) measures the minimal non-negative value that needs to be subtracted from each entry of F(x) until it is not dominated by x'. Now we consider two cases.
(i) If F(x) x F(x'), i.e., (x)) S sho for some ko E {l,..,, m], nothing needs to be subtracted from F(x) and we directly have F)
(ii) If F(x) > F(x'), we have (*) 2 (*(x') for all lo E {1...., m]. which obviously violates the condition F(x)- e1 * F(x') when
O. Now let gradually increase from zero. Notice that such condition holds only when there there exists some kn satisfying (x) S fho (x'), equivalently 8(0; x', F) = minke (x) (*)')
(xx pha Hence, in this case, have
Combining the above cases, derive an equivalent form of the pair-wise suboptimality gap. Specifically, we can easily check that the following form holds for both cases, i.e.,
8(x; x', F))
min max f (x) (x)),
kE().....m
To relate the above form with F, denote Um {ex 11 < k S m] as the of all unit vector in R.m then we equivalently have
8(0; Fe,,",F)
min A (T F(x'))+ XE
Now the calculation of 5(x;; , F) is transformed into minimization problem over X E Um- Since Um is discrete set, we can apply a linear relaxation trick. Specifically, we now turn to minimize the scalar p()) = X Fax(F((x)
F(x',, 0} over the convex curvature of, which is exactly the probability simplex S, = {X E R X > 0, || = 1}. Note that Um contains all the vertexes of Sm. Since imf p(A) is linear optimization problem, the minimal point X must be a vertex of the simplex, i.e,, X E Um Hence, the relaxed problem is equivalent to the original problem, namely,
8 F) min F(x')) inf ((F(z)-F(z')) XESm.
XEll
Taking the supremum of both sides over x' E X", we prove the lemma.
The above lemma can be naturally extended the sequence-wise variant S-PSG. Specifically, we can extend the wiir-wise suboptimality gap 5(æ; x', F') to measure any decision sequence, which now becomes
T Σ F((xx) el + Σ F((e))}
T
6( (F.Tm)) = inf
e20
16

---

Published as a conference paper at ICLR 2023
Then S-PSG can be expressed
A(fmi)-n: (FI)T
8(fx1)1=1: ;i"",,""" (FP) E'E
sup
Similar to the derivation of the above lemma, by investigating the relation between Ei= F((2))
and Ei=1 Fa()), we can derive an equivalent form of 0((x,) ) (Fittm)) as
T
T
8((z))_=lia (FFHT=)) = min
max
(x)
Σ
s
(z').
t=1
and further
T
8( 0((01)==1i0 (
inf
A (xx)))
- Σ P((x
XESm.
t=1
t=1
Hence, the S-PSG-based regret form be expressed as
T
T
(T( sup inf x EX XESm.
A Fe(a)))
- Σ F((')))+
The max-min form of (T) has a truncation operation (-)4. which brings irregularity to the regret form. To handle the truncation operation, utilize the following lemma:
Lemma 2. (a) For any I E R", have infxes.,, AT)+))+ max(infxes,, A A, (b) For any h X + R, we have supmex (xx), 0} = max(sup h).
Proof. To prove the first statement, we consider the following two cases.
(i) If I 0, then (1)+ 1. For any À E Sm. we have X T (1)+ A > Taking the infimum over infxes... X 2 0. Moreover, from the last equation we have max max(inf (infxes.,, Xes... A 1,00 infxes... ATA, which proves the statement in this case. (ii) If l + 0, then 1 < for some E (l....m): Set e, as the i-th unit vector in R", then we have e. 1 < 0. One the one hand, since e; Sm. we have infxes... A S e, < 0, and further minfinfxes... X 00
Sm. A E Sm on both sides, we have inf x T.. X (1)+
0. On the other hand, notice that e, (L)+ 0 and A (1)+ 2 0 for any A E Sm. then in.x A ( = e, (I)+ = O. Hence, the statement also holds in this case.
To prove the second statement, we also consider two cases. (i) If h(xa)) > 0 for some Tg E X' then sup=ex h(x)) 2 h(wo)) > O, and max h(x), 0} supaex h(x). Since we also have supaex max (oxxh((a) xx) 0} sup=exx h(x), the statement holds in this case.
(ii) h(x) < for all x X, then sup l(xx) < 0, and thus max(sup h(x)),) 0} 0. Meanwhile, for any æ E X, we have max (h(r)) = 0. which validates the statement in this case.
From the above lemma, we directly have
RT(T) sup maxf inf X F..
x E
XESm 1=1
t=1
max sup inf X ex XES...
F.(
F((a))),),
which derives the desired equivalent form.
E CALCULATION OF MIN-REGULLAIZED-NNRM
In this section, we discuss how to efficiently calculate the solutions to min-regularized- with Ll-norm and 1.2-norm.
17

---

Published as a conference paper at ICLR 2023
Algorithm 2 Frank-Wolis Solver for Min Minn-Regularized-Norr with LI-Norm
1: Initialize: A = (oi..... 72
)
2: Compute the matrix U (F(( (F(())) i... U Vfl(a.) Vi,j
[l....,m}.
3: repeat
4: Select an index E arg max (1.....
D=== Y U + a - 16)3.
5: Compute E arg minogggi | (x, xx o)VF((m))):11 -albb= -d,
6: Update A = (1 A) + dex.
7: until 8 ~ 0 or Number of Iteration Limits
8: return X
E.1 L1-NORM
Similar to (Sener & Koltun 2018), first consider the setting of two objectives, namely 2. In this case, for any x= (7, 7). Xo = (%, 1 1-) E S2, the LI-regularization || dollı equals 2 7o/ Hence nin-regularized-norm with Ll-norm round / reduces ). (7x, 7c) where
Ve E arg min 11 + (1 - >2 2 + 20ly 70l- 057$1
Interestingly, the above problem has closed-form solution.
91) +a)// - Proposition 3. Set (92 (g2 (a)-aa)/lgg /l91 91 91l12. and = (g] (g2 192-111 Then min min-regullrrieed--Trm with L/-norm produces weights A = (7e, 1 - -7)) where
7tt = max (>/' 1],00; where 7 = max 7n)
Proof. We solve the following two quadratic sub-problems, i.e.,
min (7)) 1h (1 7)92 12 20(70 -7),
as well as
min h2(r) = lhg1 + +1 - 722211 +2077 7o).
It can be checked that in the former sub-problem, h, monotonously decreases on (-xc, 7R and increases on [TR. +oo); in the latter sub-problem, h2 monotonously decreases on [/) and increases [Tz, -o)). Since each sub-problem has its constraint (0,, ro] or [no, 1)). the solution to the original optimization problem can then be derived by comparing the optimal values the two sub-probh tob-problems with their constraints. Specifically, notice that " s "A and 0 I %o 1, and we consider the following three cases.
(i When 0 < To 7t Yn. then hn monotonously decreases [0, 70 and its minimum [0, 70] is hy (10). Notice that (70) = h2(70). For the sub-problem of h2, we further consider two situations:
(i-a) If 7z < 1, then 7L E [70, 1]. hence the minimum of h2 on [70, 1] is h2(11). Since h2(T1) < hu((u) (1i), the minimal point of the original problem 72. and hence "t = -TL-
(i-b) 1f > 1, then he monotonously decreases on [Yo. 1], and we surely have h1) < h2(10) =
h1(1)). Hence y 1 in this situation.
Combining the above two situations, we have " min(7r., 1) in this case.
(ii) When 72 S 7n S "o S 1, then hy monotonously increases on [xo; 1] and its minimum on (xo. 1] is hz h2(7)). Notice that ha (70) = h2((0). For the sub-problem of h1, similar to the first case, we also consider two situations:
(ii-a) If > O, then 7/ [0, 70]. hence the minimum of h on [0, 70] is h (TR). Since hi (T(T)) S hy (1u) h2(")), the minimal point of the original problem is "R. and hence 7/ = 7/R-
(ii-b) If 7R < then h monotonously increases on [0. yo]- Hence we have hz(0) < h1(70)
h2(10). Hence the solution to the original problem 7/ 0.
Combining the above situations, have % max (7R, 0} in this case.
18

---

Published as a conference paper at ICLR 2023
Algorithm 3 Frank-Wolis Solver for Min Min-Regullarized-Nonr with L2-Norm
1: Initialize: A = (oi..... 72 ........................... )
2: Compute the matrix U (F(( (FF())))F(()))) i.., U vfi(a,)) VV(L), [I....,m}.
3: repeat
4: Select an index E arg ma (1...... 1 U +a mh)
5: Compute E arg 5511
which has an analytical form
(VF(( V/(a) +ale: A1
ò = maxx(min)
V A V/ a(ex - (A: Ao) 13.03.
6: Update A, = =1 (1- A) de;.
7: until 8 ~ or Number of Iteration Limits
8: return A₃-
(iii) When 7t. To < 7n, then hn monotonously decreases [0, 70] and h2 monotonously in- creases on [70: 1). Hence each sub-problem attains its minimum at 7o. and thus " = 70-
Summarizing the above three cases gives
min 1}, max 0}, 70>
7o S 71:
7
To 2 TR: otherwise.
We can further rewrite the above formula into a compact form as follows, which can be checked case-by-case.
7/- = min , 11, 0}, where x²- min 7R] n.h.
This gives the closed-form solution of hinn-rggularize--noee when = 2.
Now that we have derived the closed-form solution to the min-regularized-non solver with any two gradients, in principle, we can apply (Sener & Koltun 2018)'s technique efficiently compute the solution to the solver with more than two gradients. We provide the full procedure in Algorithm which an extension of (Sener & Koltun 2018). By following the exact line search technique (aggii 2013) in MGDA, we get our line search oracle as line 5 in Algorithm 2 The first term is the same as that in MGDA, and the second term is an extra LI L.-rreglarization term related to the design in Algorithm 1. Unlike the oracle of MGDA that has closed fore solution by reduction to the case of two gradients, the extra L1-norm term makes our oracle difficult to get closed-fore form solution. The reason is that, such extra term is the L1-norm of m-dimension vector, hence it can not simply reduce to the case of two gradients. To proceed, we can directly apply numerical methods get the solution (e.g. similar to the implementation in (Liu al. 2021)).
E.2 L2-NORM
Recall that in min- niin-regularize-nnon norm, the regularization on À can take various forms. In the following, we discuss an alternative regularization, i.e., L2-reeullarization r(>, Au) = - Ao112. In the discussion, will show that similar to (Sener & Koltun, 2018), min-regularized-nomm with L2- norm can be computed very efficiently via the Frank- Wolfe method.
Similar to the previous discussion on Ll-rreglarizzatin, we first consider the setting of 2. In this case, for any À = (7, - 7), Ag = (70 1 70) E S2. the 1.2-regularization _ - A 1 equals to (7 - 70 Hence min-regullarizdd-nomm with L2-norm at round É reduces to A; = (y., m) where
"y E arg min 11/ + (1 7) + a(7 - 22 05
Since the above problem is in the quadratic form, it also has a closed-form solution. The proof is elementary and hence omitted.
19

---

Published as a conference paper at ICLR 2023
Proposition 4. Min-regularizee-nnom with L2-norm produces weights X, (Yt, -1) where 91) 92 + ano
(g2
maaxmmin
92 91 + 1..0..
When 2, since X is constrained to the probability simplex Am. similar to the case of LI- regularization, we can use a Frank-Wolfe method to efficiently calculate the composition weights, which is presented in Algorithm Note that since the line search (step 2) has closed-form solution, its calculation cost is not high, I.C., just the same as the calculation cost of the original min-norm solver (Sener& Koltun 2018).
F MORE DETAILS OF THE THEORETICAL RESULTS
In this section, we first prove the remark helow Theorem D. i.e., with proper choices of 1)t and og DR-OMMD is guaranteed to have a sublinear regret bound in O(vT). Then we show the tightness of the above derived regret bound of DR-OMMD. Finally, we give a more detailed comparison with linearization from the theoretical aspect.
F.1 MORE DETAILS OF THE REMARK BELOW THEOREM
Recall that in the remark below Theorem our main paper, we claim that with proper choice of and a₁ DR-OMMD is guaranteed to attain a sublinear regret bound. We summarize this remark into the following corollary and provide strict proof.
Corollary 1. (i) (Fixed learning rate) When setting тet
V2yD and az GVT
4F
for any Xo E Sm. me
DR-OMMD achieves the following multi-objective regret
R(T) S DD.
(ii) (Diminishing learning rate) When setting = 227D
GvT at = 4F
for any Ag E Smn DR-OMMD
mi
attains the following multi-objectiive regret
3 R(T) 2T.
Proof. We start from the regret bound regarding X Theorem When aa from the definition of min-regularized-nomm the composite weights d generated by DR-OMMD at each round satisfy
+ 4F _ Aollı-
D arg min [F((x))11 XESm.
?h
Recall that An E Sm. Hence, for any i E {1,..,,") the last term of the regret bound in Theorem can be bounded as
4F |A doll2 min VF((;))11 AES...
4F
Av Ae
a dolli N (1; l
From Assumption 2 7)
each gradient gi is bounded as lg l| < G, hence [[V 1 [gg 2 = _im A 1lg2ll2 & G. Therefore, when a₁ 1F we have
[VE((:)) 4F || - dolli = (V; S G2.
Plugging it into the regret bound Theorem
we have
7D Tht G GPT=GV22DDT R(T) <
2
which proves the bound with the fixed optimal learning rate.
Alternatively, 17; and utilize Σr v 2VT, also have
V2yD GVt
T
R(T) S GV2
Σ
1
3 G
DT,
2
[=1
which proves the bound with the adaptive learning rate.
20

---

Published as a conference paper at ICLR 2023
F.2 THE TIGHTNESS OF DR-OMMD'S BOUND
In this subsection, we show that the derived bound in Corollary 1 is tight w.r.t. m regarding any gradient-based algorithm. Specifically, we follow the standard worst-case analysis of deriving lower bounds and construct a special case in which any gradient- algorithm will incur a regret in the order of (((T)).
f(m at each round t. In this case, the instantaneous gradients of all the ob- Assume f2 = fe-
jectives are identical, i.e., g Vsi (xx)) = (.((())) gi Vi E [I,...,.. For any gradient-based algorithm, since it can only utilize the gradient information of the objectives, it cannot distinguish the objective to which a certain gradient belongs. Alternatively speaking, in this case, any multiple gradient algorithm will treat all gradients the same way and thus behave like a single-objective algorithm using the single gradient g/- Hence, in intuition, for any gradient-based algorithm, the worst-case bounds are at least independent of m. In particular, the worst-case bounds of gradient- based algorithms cannot decrease as increases; otherwise, the above case will be violated.
In the following, we provide a detailed proof of the tightness of the ((VT) bound. In the above case, f for any I, the cumulative losses of all the objectives are also identical, ie.. 21=1 = 1 = Et= St" Therefore, the Pareto set X of the cumulative vector loss E1=1 F, coincides with the optimal decision set of the cumulative loss Σ ft of the first objective, i.e., X = argmin Σt= (xx). Recall our definition of the multi-objectivee regret. Since A FF(())= = f! (a:) for any E Sm, we have
since f
T Σ (a.))
R(T) sup x'EX' 1=1
(am)))
min Σ (xx)) EX
1=1
t=1
which exactly reduces to the single-objective regret Rs'(") defined by the losses { of the first objective. Hence we have R(TT) = (T') in this case. Since the losses [ 12= of the first objective can be chosen adversarially, we can follow Section 3.2 in (Hazan et al. 2016) construct a certain sequence {ft ] that admits a lower singlc-objective regret bound of S2 (vT). Hence in this certain case, any multiple gradient algorithm will admit a multi-objectivve regret R(T) = (2(T)) w.r.t. T and m, matching our derived regret bound for DR-OMMD in terms of both T and m.
Some readers may suspect it unreasonable that in the multi-ohjective setting, the derived regret bounds do not increase as m increases. Now we explicate the rationality of such independence in the following.
In fact, the independence of m lies in the adoption of PSG in the formulation of the regret. Recall that, in the definition PSG, "3i E (1....,my) means that it just needs to pick one coordinate fi("", which omits the dependency of m. We see this point from i to satisfy fi(x;) Recall that in the derivation of Proposition [ we know that the regret R(T) another perspective.
or equivalently - fz()). In particular, PSG takes a minimum operation over all objectives, and thus it does not necessarily increase as m increases.
has an equivalent form, namely x inf (A*) E (F)(
s x (I..,c.
There is another intuitive way that can help understand the rationality of the independence of m. As is well recognized in existing research in multi-objective optimization (Emmerich & Deutz, 2018), the proportion of the Pareto optimal solutions (or more precisely, non-dominated solutions) in the decision domain tends to increase rapidly as the number of objectives increases. As consequence, might not be harder to reach the Pareto optimal set when m turns larger, hence intuitively, the regret bound does not necessarily increase as increases.
F.3 MORE DETAILS IN THE COMPARISON WITH LINEARIZATION
we show that our derived bound for DR-OMMD is smaller than that of linearization, and discuss the margin between the two regret bounds in the two- objective setting with linear losses. We now summarize the result in Theorem iin the following.
Recall that in the remark below Theorem 1
Theorem 2. Consider a two-objective optimization setting with linear losses. Suppose the loss
functions are St (z) x. g) and f2(x)) (a:) x: 9t at each round t. For any Xo (20, 1 10%) E S..
21

---

Published as a conference paper at ICLR 2023
let X - norm. When the regularization strength set as a = 4T/n,, the margin between the regret bound of linearization with fixed weights X and that of DR-OMMD with composite weights x is least
76) denote the composite weights produced by nnnn-reullartzd-norn with LI-
th m 70) -92112 2
M
Before proving the theorem, we remark that the two bounds are basically in the same order. Note that this theoretical result is also very commonly seen in the offline setting, where multiple gradi- ent algorithms often have the same (convergence) rate as linearization Yu et al. 2020 Liu et al. 2021]. The benefit of multiple gradient algorithms mainly due the implementation composition. For example, the concept of common descent (Sener & Koltun 2018 Yu et al. 2020) eliminates the gradient conflicting issue; the resulting algorithm achieves substantial performance improvements compared linearization in their experiments. In this paper, move step for- ward and discuss the margin between DR-OMMD and linearization. We show that such margin is due the gradient difference g! 9 and the gap between the pre-defined weights Åu and the adaptive weights X This the best we can do for now. The regret bound comparison for m 2 is left for future research.
gradient
Proof of Theorem 2 We first write out the regret bounds of both methods. For DR-OMMD with ai 4F/n. Theorem provides the following regret bound
RDR-OMMD(TT) I 7D
m 2 XES...
min (IVEE(=))11 + ||
4F
Aoll1].
For linearization with fixed weights Ao E Sm, it can be viewed single-objective optimization with linearized loss A F,. Hence, we can directly borrow the tight bound of OMD (c.g.. Theorem 6.8 in (Orabona 2019) and derive bound
7D
T Σ (a
Riinear (T)
TJT
The margin between the above two bounds takes
4F - \olli)), M Σ 2 (1VF())))01 min (
1/t
which stems from different choices of composite weights. We investigate the margin at each round.
Lemma 3. In two-objective setting. suppose the gradients 91 and 92 some specific round i, and the corresponding gradient matrix = [g1, For any An = (70, 1 70) E Smm let D (n, 1 -1)) denote the composite weights produced by min-regularized-nnom with L.Inorm, then the following inequality holds, i.e.,
|G (I (| +alld dall 2 (70 - 72) 1
Proof. Denote the left side of the target inequality M M(,, >o). then it can be simplified
M(). 2o) (GA, GA, GA,) -al dolla - G(A, + A,) -ala: Aollı
To leverage this term, need to plug the derived composite weights A, into M M(),, Recall that in the two-objective setting, the weight y/ is given as
7t max 1), 03. where '" max 7o. rL}
where 7/- = (g] (g: 91) - a)/ gı 112 and "R = (g) (g2 gi + a)/ 92 gı 112. Since the calculate
maximum and minimum operations will truncate the value of the produced weight, M (A,,.o by case. Specifically, notice that 7t. < YR and 0 < 7o < 1, we consider the following cases.
22

---

Published as a conference paper at ICLR 2023
Case 1: When YR O, must have YL <R < 0 S Na. which leads to "/t 0. In this case,
have Ao- - x = (70: -70) and Au + X = (70. 2 -o). Therefore, (x,, Au) can be computed as
( 2o) = (Yug1 - 1092) T (yog1 + (2 - -2)g2) - 2a
Also, from the condition 7n < O, we have a < 92 (g) g2). Since X 2 0, plugging it into the above inequality, we have
M(). An) 2 (7091 7092) T (1og) 7092) r6ll91 -9212
In this case, since Tt- - O, we derive the desired inequality.
Case 2: When 7/,. > 1, must have To S 1 < 7T. < 7R. which results in 7 1. In this case,
have 20 - X, = (7o- - 1, - 70) and Ao + A = (70 + 1, 1-7) Now M ( Xo) can be calculated
as
M Ao) (17 1)91 + (1 - 70)g2) T ((10 1)91 + (1 70)92) - 2a(1 70).
Notice that the condition Yz gives a < g (g2 91). Since - %o 2 0, plugging into the above inequality, we have
M(,, Au) 2 ((ro 1)9, + (1 70)g2) T ((%) - 1 g1 + -1-11000 (1-1n)) = (1 - (1-7%)²l1 7 2ell2.
In this case, since 7/2 = 1, we derive the desired inequality.
Case 3: When 0 $ 7L < 7R I 1, the margin is a bit more complex since the value of A further depends on the relation between Au AL, and AR. Specifically, we consider the following cases.
(i) IfO < 72 S 70 S 7R S 1, then = %o. In this case, the inequality trivially holds.
(i) O I To S 7z S 1, then Y+- = 7L. In this case, since || Aollı 2(72 - -o), we can
calculate M(),, An) as
M(A,, Au) = ((%0 - )1 + (y2 - >))g2) ((70 + 72)1 + (2 - - 71)92) -20(12 7o)
-10 - - ) 92) [ ((10 + 72)91 + (2 - 71 g2) + 2a.)
Since "/ 7r. = (9] (g2 - gi) a)/ ||92 - g 11 we have a (g) _2) (-7199 + (T 1)g2). Therefore, we further have
(g: (0)) ((10 + 7g)1 + (2 % - -1))2) + 2a = (g)
92) T ((10 - -i1):: + (7 70)92)
= (g) g2) T (7/ (1) - 92))
Plugging it into the above equation on M(A,, we derive
M ( Ao) (7z -00 2 92l12
(iii) I S 7R S 7o0 S 1, then 7/- = YR- In this case, || AA - dollı = 2(700 - YR), and M (Ac, 2o) can be calculated as
(M,, Ao) = ((70 (R)g1 + (TR - r0)g2) T ((70 + 7R)91 + (2 - % - 7R)22) 22( - 7R)
= (70 -R) 92) ( + yR)9: + (2 - - 7R 7R)g2) -2a).
Since "/- (g) (g2 01) / 92 11. we have (g) 92) (rgg + (1 7n)g2). then
(g) (2) ((70 + +R)91 + (2 - To (R)92) 2a: (0) 92) (70 - - 92)-
Plugging it into the above equation on M (A,, >o). we derive
M(A,, An) = (7R - 700)2ll g2
Combining all of the above cases, we prove the lemma.
For any t E {I,..., T}, set g1 = g.. = gi (i.c., G G.), and a = 1F in Lemma we have
|GG G1 + 4F ||: - Au (11) 2 (7e - ?l9? - g6
Since | - >0113 = 2(7 - ) summing the above inequality over t E {1,..., T), we can directly calculate the margin
-
M Σ
1/ A
Aa112
!1 -9: -9.1.2. 11:.
4
-=1
which proves the theorem.
23

---

Published as a conference paper at ICLR 2023
0.7
linearization DR-ONMO
0.22
lin-opt DR-ONMD
Auwenge Los
Average Loss
0.20
02
0.0
0.4
0.6
0.8
200000
400003
500000
Value of
e Rounds
Bffect of Preference
(b) Learning Curve
Figure 3: Results to verify the effectiveness of adaptive regularization on covtype. (a) Performance DR-OMMD and linearization under varying A (A 1 --))-- (b) Performance using the optimal weights Ag = 0.9).
DMNS
Tex: Loce
1.0
6.8
0.0
0.6
40000
20200
60020
20203
60000
Roundh
Rounds
Rounds
(a) Task Average Cumulative Loss
(b) Task L, Training Loss
(c) Task L, Test Loss
3.4
DS OMND
D1 CEND
tose
3.2
25-151
Traniig low
25 751
Text Lokk
13
2.0
2.0-
1.0
0.8-
0.6
20000
40200
60000
20300
40000
62020
20203
40000
60020
Rounds
Rounds
Rounds
(c) Average Cumulative
(e) Truining
(1)
Figure 4: More empirical results of the multi-task deep online experiments MultiMNIST. The plots show the average cumulative loss, training loss and test loss of DR-OMMD and various base- lines on both tasks (lask L and task R).
G MORE EXPERIMENTAL RESULTS
G.1 MORE DETAILS OF THE EXPERIMENTAL SETUP
The protein and covtype datasets used in our experiments are publicly available in (Dua & Graff The MultiMNIST dataset is acquired by the code provided by (Sener & Koltun 2018).
2017).
All runs deployed Xeon(R) ES-2699 @ 2.2GHz.
G.2 MORE RESULTS FOR ADAPTIVE REGULARIZATION
We supplement the empirical results covtype in Figure which have been omitted from our main paper due to the lack of space. These results are consistent with the results on protein as presented our main paper.
G.3 MORE RESULTS FOR ONLINE DEEP MULTI-TASK LEARNING
In our main paper, due the page limit, Figure 2 only reports the average cumulative loss of DR- OMMD and various baselines on MultiMNIST. Here we supplement the results on the training loss and the test loss Figure 4 The results are consistent with the average cumulative loss, showing superiority of DR-OMMD over linearization and MGDA in the non-convex setting.
H OMITTED PROOFS OF PROPOSITION 2 (MIN-NORM MAY INCUR LINEAR REGRETS)
Proof. As we have described in our main paper, we consider the following two-objective optimiza-
tion problem. Decision domain is set X' {(u,v) u + S 2. 2, 2 0}. At each
24

---

Published as a conference paper at ICLR 2023
round t, the loss function Ft X - IR takes
(I/ a 2 | bll2), t 2k 1, k 1, ...i
Fi(z)
(1|= blž || cll²),
t 2k: 1...
where a (-2, = (0. 1) c= (2, -1). For simplicity of analysis, we first consider the case when the total time horizon an even number. Then it can be checked that the cumulative loss function takes
T
Σ
F((x)= 2 (||x - al12 + || -11.: || b12 + 1|0 - c112)
=T ((u + 1)² + 0² + 2, (u - 1) + + 2),
for any x (u, v) E X. Obviously the Parcto optimal set X of the cumulative loss coincides with the line segment between (-1, 0) and (1, 0), i..., X {(u, v) I S 2, 0} (note that X is the intersection of the line segment and X).
Now consider equipping OMD with vanilla min-norm, where the composite gradients are produced by the min-norm method. Suppose the learning process starts at any I1 = (u1, v1) E X such that en > O. Note that this is true if and only if æ1 & X Then for the iterate at, (u, vx) each round I, we can directly calculate the gradients as
2(x== a) = (2ue + 4,
20, + 2),
t 2k- 1;
9 =
2(x; b) =(2ue
20, 2),
t= 2k.
(2(x; - b) = =(2u4
20, - 2),
t= = 2k 1;
g
2(xx c) (2et
4,
20, + 2), 2k.
The min-norm weights can be computed as dr= = (7t, - 7e)) where
(x, b) T (a- b) 1 1 1-4 u1 - Ut
t= 2k - 1;
|la b 1
4
7t-
(xt
c)
(b
3 + Ut
1 = 2k.
|
c//
The composite gradient
7t- 2(x a) + (1 - 7t)) 2(x: b) = =(1 122 1,
-Ug + 1t 1), t= 2h 1;
gt comp
7t 2(x - b) + (1 - 7+) 2(x - c) = (-u, ut - Ut 1,
U2 Ut
- 1), L t= 2k.
Recall that the update form of OMD takes
Ft+ xx n1 (mmP)
where n/ > 0 is the learning rate and xx is the projection operation onto X. Denote the iterate æ; (u,, 1.) at each round. Now we can investigate the relation between I; and x++1 by considering the following two cases:
(i) at Th:: comp E X, then we do not need projection, and directly have # = D2 - 71:9
comp
(ii) If æ; nigi comp & X, then need to project æ; n:g: comp back to X. Denote x/41 Ct T/. comp, For simplicity we consider the projection based on the Euclidean distance, namely [xxx) = arg min x| - x' r'1 Since the composite gradient is orthogonal to the boundary on which the iterate after projection 2++1 IIx(2' is located, it can be checked that x++1 lies on the line segment linking æ, and 4'411- Alternatively speaking, I1+1 can be expressed as H, 2/9 comp for some 0 < 1/L < T/..
Combining the above two cases, we know that at each round f, there exists some T/g E [0, mh such that xt+1 = Z₁ n/9: comp Now we can analyze the relation between each entry of x; and D1+1- Specifically. since the second entry of the composite gradient is always non-iisitvve, namely -t + 2i 1 < 0 and - u4 - U,- < 0, we have 1/+1 2 V2 for any t. Moreover, since the first entry of
g, comp is non-negative when f = 2k 1, namely u2k-1
U2k- 1 1 2 0, have U2g S u22-1 for
25

---

Published as a conference paper at ICLR 2023
any k; since the first entry of 9: somp is non-positive when 2k, namely U2k have Ugk+1 2 U2k for any k.
U2k
1 S
Now can go back to analyze the gap between the composite weights at any two consecutive rounds. It is easy to verify that 7 < 12k and 1/2k > 1, hence we have
2 - (u2x - U2h 1) + (U26 + 028-1) 2 1 + U1
122 22k-111 ||| 2(72x -2k-11
2
2 - (122 U2k++1 - (122 + U2k+1) > 1 1 U1
1226+1 A28l11 = 2(72x 72k+1)
2
Therefore, the composite weights A, indeed change radically at any two consecutive rounds.
The above analysis on also implies the failure of min-norm in this problem. Recall that any Pareto optimal solution x² = (u", v=)
(F) E X must satisfy v* = Suppose the initial iterate æ = (W1, v1) for random initialization æ1 X. Then iteratively have 0 < 01 I 02 S ... S vr, which means that Φ, moves away from the Pareto set X
does not lie in X", ie., 01 0, which is almost
In the following, we strictly prove that min nin-norm indeed incurs linear multi-objective regret. To calculate R(T)), we first investigate the quantity R(w", A) A Σ
(F. (3x) F+(x=)) for any fixed weights À = (7, - 7) E Sy and best fixed decision x" u 0) E X Specifically, recall the form of Σ F2 derived above, then we have
Σ F1(x)) = (r(u" + +1)² + (1 (1- - 1)² 2)T.
Denote the cumulative loss Σ 1=1 (x:)) (In1 Iz2), we now consider the loss of each objective L and L2 separately. Specifically, for the first objective, we have
T/2
L
Σ k=1
(w2x + 2)² + 222 + (U2k-1 + 1)² + (02a- 1)3).
Since 0 < U1 12 S ... vr 1, for the term regarding Us have
T/2
T/2-1
(12x-1 1 1)² + (02* 1)2) (0) 11² + (UT -1)² + Σ
(122x 1)2 +122441 1)
k=1
k=1
T/2-1 1
7/2-1
(122k - 1)3 + (12x + +1)3)=
Σ
(2r +
k=1
k=1
T/2-1
2
Σ
(2r + 2) = (20g + +2)( / 1) 2 o7 + T -
k=1
For the je-th term regarding u4, have
(u2k-1 + 2)2 uz (u2k-1 1)2 + (uzx + + +1)))2(u222)) - -(2k) +
Recall that we have derived U2k S U2k-11 thus we have
T/2
T/2
T
Σ
U2kk + +) u2x 2
Σ (1 (wzx + +1)++) 2 k=1
Σ (w (n=+1)++22 +
where u + Σt= Ue and the last inequality is derived from Jensen's inequality. In summary, for the cumulative loss L1 of the first objective, we have
L 2 (ū + 1) + +T 2T - 2.
Similarly, we can analyze the cumulative loss I.2 of the second objective
T/2
L2
1 + (wzx 2)² + (12 1)² + (c2a 1)?).
2
26

---

Published as a conference paper at ICLR 2023
Since 0 < 02 I ... - I 1, for the term regarding i have
7/2
7/2
(122-1 - 1)2 + (122 + 1)3)
(122-1 1)2 1022-++113 2 of + +
k=1
k=1
For the term regarding ue, we also have
T/2
T/2
Σ
(2z-) + (u2x 2)²)
Σ ((12-1- + (u2s - 1)2 2(12x-1 U2x) + 2)
T
2
Σ
[4 - 1)2 + T 2 ū 1)2T + +
t=1
where the last inequality is derived from Jensen's 's inequality. Therefore, we have
La (ā 1-2-1)2--- + ofT + 27.
Combining the above inequalities, we have
T
R(x" A) = 711 + (1 -1--) A Σ F((x))
1=1
2 7(ū + - + 1)2) + (1 - > - 1)2 - (u" 1))) + ofT 27.
For any X E S2 (i.e., E [0, 1)), set x'' = (7,0) 0) E X then it holds that
R(w', 2) 2 os 2.
Equivalently, the multi-objective regret satisfies
R(T)- = sup inf R(x" (() 2 inf R(æ', A) 2 u - 2, x' XES2
XES2
which is linear w.r.t. T for any 0 (11, v1) X' such that V1 0.
We now investigate the case when T is an odd number. Since the calculation of the composite weights A and the composite gradient g: comp at each round is independent of the total time horizon T, we still have ||A+11 Aulla 2 + for any t. Hence the first desired property also holds for any odd T.
It remains to prove that OMD with min-norm still incurs linear regret when T is odd. In this case, the Pareto optimal set x does not lie in the z-axis anymore, hence it is difficult to directly compute R(T"). However, we can still use our derived R(x', X) for any even T to estimate the regret. Specifically, set xx' ( IT-1 ue, 0): from the above derivation with even T. for any À S2, still have (note that now T 1 is an even number)
T-1
T-1
AT
F((.))
A
Σ
Fe(x')
2
ufT
Since for any X, we have 0 < |
al1 ||
a
b
blg || c 10. have
T
T
R(z' =
Fi(z))
A Fi(x')
Σ
2 of - 12.
Furthermore, from the definition of Pareto optimality, there exists some xx E X that Pareto domi- nates x' regarding the cumulative loss I Ft, namely D. F((x")) - Σ F((x". Hence
T
R(w", A) A Σ P.( A Fi(x") R(Ø' A),
for any Sz. Therefore, the multi-objective regret
R(T) = sup inf R(x", A) N inf R(*", X) 2 inf R(2', A) 2 uē - 12, XES2
x- XESa
XES²
which is also linear w.r.t. T for any æ (wi, X' such that 11
0.
27

---

Published as a conference paper at ICLR 2023
1 OMITTED PROOFS OF THEOREM I
Proof. We start from the definition of the multi-objective regret Rn(T) (which abbreviated as R(T)). Specifically, for any À E Sm and . E Sm. it holds that
R(T)
sup inf Σ x (Fi( - F((x")) I
sup
X (F((Z)) Fi(x²))
x E- X EES
x Ex
1=1
[=1
Σ
(A Xc) (.(o))) + A. (FF((x)) ((((a)))((xx))) + (Ac-2)
sup
EX'
T
T
FIA- Aelli + sup
Σ
A (FF(())) F,(x')) ((((t)))P((x))) + Σ FI - A.
xx EX-
t=1
T || Acl11 + sup x'E 1=1
T
2F
Σ
X
T (Fi(at) Fi(x)).
To proceed, notice that the composite weights A, are given beforehand instead being calculated via min-regularized-nomm DR-OMMD acts just like standard OMD using linearized loss X Ft- Hence, the second term the above regret bound can be further analyzed in a similar way as single- objective OMD (Srebro et al., 2011; Cesa- Cesa-bianchi et al. 20122). Specifically, at each round t, since Fe is coordinate-wise convex, the linearized loss X, F. is also convex. Also notice that the composite gradient g: Ff;, )a, is exactly the gradient of X, F, at T4. Hence for any x² X", we have A Fz,)) X Fi(x") S 9: (æ, x²) g. (II+1 x²) g (æ: x2+1).
From the first-order optimal condition of t1+1, for any x' E X, we have
(n (()(a)) + VR(x++1) vR(=;)) (a' - xe+1) 2 0. Recall that gr A.; We set x' x= and combine the above two incqualities, which derives
(.,) XT F(()))
L (VR(E
gt (a, Tz41)-
Nt
Recall the definition of Bregman divergence BR. We can check that (also see (Beck & Teboulle 2003))
"_(x"xx,)) - Bn(x" (.+1)) Bn(x.41, x,) (VR(x)+1) VR(x,) Tx -x++1). Since R is 1-strongly convex, we have B xx, 2 ||,,4|1
x, 12/2 Hence
1 (BR(Ø", a:) BR(x", xz-1) -11
1 || - xx 113) + g. (x, - xz+1))
x, F((x:)) - XT F.(x") S T
Moreover, from the Cauchy-Schward inequality we have
g. (x, 1 - 1)|
19. 12 + 2m
|| 111.
2 Combining the above two inequalities, we derive
X, T F.(x))) - X, F((x') S (BR(x";; x.)) BR(x": ; ()) + St
V [F,
1)t
2
for any x= E X Summing it over & (1,.., T} and utilizing BR(x"; ; xT
0, we have
X (F(()))
- BR(x"; Σ
B
1
BR(#": oT)
71t
V VVF( Ae
111
7/1
M|-
t=2
Since Bn(x"; :.:) S DD and nt S At-1 for any t, we have (1 ni :n(x==;=r7) S (
Mt-1 DD. Hence we further have
Σ X (F((x)) - Fi(x)))
D
Σ Th
1/T
Taking the supremum over x" E X and plugging it back to the above regret bound, we prove the theorem.
28

---

Published as a conference paper at ICLR 2023
J REGRET ANALYSIS IN THE STRONGLY CONVEX SETTING
In this section, we discuss the regret bound of DR-OMMD in the strongly convex setting, where each loss function fü is H- -tstonggly convex. Recall that most literature in this setting only considers OGD (Zhao Zhang 2021] Wan et al. 2022), which is a special case of OMD that instantiates 1.2regularizerr i.e., R(z)
the regularization function the iterate following, we mainly analyze the bound of the OGD-type variant in the strongly convex setting. Theorem 3. Assume that for any t E (1,...;)) T) i
|| 12. Hence, in the
(1,...: m., the loss function ft is H-strongly and R(x) -||اا12 in DR- DR-OMMD, then it attains the following regret
convex. Set ?h- H:
H 21 R(T)
T
1
S
(IVF((=)))
4FHt|| -ull1)).
2
2Ht
Remark. By setting at HH, the above bound reduces
H R(T) S
x11
+
min (IVE
2olli3
2
2HL
XESm
S 2 x:
+
VF (z
H
- 11
+
G T
Σ = Ollo T),
2Ht
2
2H
which aligns with the optimal regret bound Ollog T') in the obnelc-o strongly convex setting Hazan et al. 2016).
Proof. From the derivation of Theorem I
we have
R(T) 2F Σ a Acll
Σ X (F. -F(())))((()))
sup x-
Denote the composite gradient as gr V. which equals to the gradient of X.F, at æt- Since A E Sm. A, F3 is convex combination of fe...., hence XeF, is also H-strongly convex. For any x" E X²x we now have
H
T (x. x²) 3 12, x w' F.(.))))) Lo Fa( S 9t
We now bound the term g.T (x: - ||a: =11 and the OMD update reduces to OGD, i.e., a++1 = xxx 7i9h) (IIx denotes the standard projection onto X). Plugging the above update rule into ||a,+1 =x"113 we derive
-x*). x²). When R(x) = 2/2 |2112 the Bregman divergence BR(œ, z)
| - x 12 = |[xx (a: neg:) x 112 < ||z, - 7.. - x ==
where the last inequality is derived from the Pythagorean theorem. Hence we have
x012 + n² | 2n.g. (æ, x'), | - x 11 < || -=0-l=='
or equivalently
9. (x) x²) ||,,; x=11 -112241 20 10
T1e 11
277
2
Plugging it into the inequality of A F((xx)) - -1 T Fe(x"), we derive
A, F((x))) - > F((=)()) S ||= -12-111111 xx
112
+
17c
9.
12
H
- x
x=13
2m
2
2
for any x= E x Summing it over L (1.... we have
T
X T (F((z)) -F((x))
T
T Σ
|x
x21 112+
+
1
H
x11
T
/F((z))>
2m11
2m,
27,-1
2
2=2
t=1
29

---

Published as a conference paper at ICLR 2023
When setting 1/: 1/Ht, Ht, we have
1
1
H
Ht
1)
H
0.
2tje
21k-1
2
2
Consequently, we have
T
T 1
Σ
(F((z))) F((x)) -
A
x1 2 -
11
+ Σ
IVF
2
2Ht
[=1
t=1
Plugging it into the above regret form, we derive the desired regret bound.
30


Reviews:
[{"review_id": "W9zVz4KoE9V", "reviewer": "Reviewer_WSb3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper studies multi-objective online learning, a framework in which the learner has to optimize jointly several conflicting objectives. In particular the notion of optimality and discrepancy need to be redefined. The authors propose a definition of the regret based on the sequence-wise Pareto Suboptimality Gap. Then, they propose an algorithm based on the regularized min-norm and prove it achieves a $\\sqrt{T}$ regret. Experiments complement the contributions.", "summary_of_the_review": "Overall, I am not fully convinced by the definition of the regret proposed by the authors. I also proposed some directions to explore to complement the contribution.", "strength_and_weaknesses": "**Strengths**\n- the paper is globally clear and well written\n- the topic is of interest to the ICLR community\n\n**Weaknesses**\n- I am not fully convinced by the definition of the regret (which is one important contribution of the paper). Typically, in Proposition 1, isn't $\\lambda^*$ just selecting the objective with respect to which the regret is the smallest? If the previous regret proposed was indeed too hard, this one seems on the contrary a bit easy. I point out this paper [1], where the authors study multitask Bayesian optimization. In particular in Section 2 they define a notion of regret which is the expectation (over a distribution of directions) of the scalarized regret. This seems to me a sensible definition, as opposed to the best (or the worst) possible direction. Could the authors comment on this point?\n\n**Questions**\n- one could imagine a setting where feedback (i.e., the gradient) is received only for a subset of the objectives. How would the regret bound look like in that case?\n- does the DR-OMMD achieve improved regret bounds if the objectives satisfy additional regularity assumption (e.g., strong convexity, exp-concavity)? If not, what is the reason?\n- it seems to me that the $\\lambda$ can be interpreted as learning rates. They are many ways to optimally tune the learning rate and adapt to the comparator, see e.g. [2, Chapter 9]. Could it make sense to use them rather than the regularized min-max norm to derive a sequence of optimal $\\lambda_t$?\n\n[1] No-regret Algorithms for Multi-task Bayesian Optimization, Chowdhury and Gopalan 2020\n[2] A Modern Introduction to Online Learning, Orabona 2020", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "V-Nkh5ZrgB", "reviewer": "Reviewer_GxU6", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper considers a multi-dimensional version of the online convex optimization. Concretely, the problem studies a sequential interaction between a predictor and an adversarial environment -- at each time, the predictor picks a point in a convex set and the environment subsequently picks M convex functions from the domain to the reals. The goal of the predictor is to make sequential predictions so as to minimize regret with respect to the Pareto frontier of the sum of the M dimensional functions over the time horizon. \n\nThe paper contributes to a rigorous definition of regret, provides a variational formula for the same which then aids in analysis. The first observation the paper makes is that directly plugging in the one dimensional OMD to the standard iterative multi-objective MO descent algorithm leads to linear regret. The key observation made here was that the offline algorithm optimizes the mixing weights for the gradients of the M function to the current iterate. However, in the online case, since the environment is adversarial and the regret is with respect to hindsight, converting naively the offline iterative algorithm to an online one yields linear regret. The paper then shows that the simple idea of solving two regularized optimizations -- one to choose the mixing weights and a separate one to choose the next iterate -- yields low regret.", "summary_of_the_review": "Overall this paper is very well written -- provides a simple algorithm and a new insight (double, separate regularization) for an important practical problem. The style of writing is also very pedagogical and aids the reader in quickly grasping the key concepts.", "strength_and_weaknesses": "Strengths -- Very well written paper. The style was nice -- presenting the problem, showing through detailed examples why simple approaches fail and then using those examples to build up to the final algorithm. \n\nWeakness -- The intuition and the effect of \\lambda_0 in the algorithm is not clear.  This is however a nit-pick and I believe can easily be fixed in the write-up. ", "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": "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": "N0CZAUk5FZ", "reviewer": "Reviewer_GCcZ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "This paper studies the problem of multi-objective online learning. In the classic online convex optimization problem, there is a single objective function, and the goal is to find the best action that leads to the best value of the objective function in a sequential decision-making setting. This paper extends the problem to a case where there are multiple objective functions. In this setting, then, the notion of best action needs further elaboration to define formally. The reason is that it is possible to have different best actions for different terms of the objective function. In this paper, the notion of Pareto optimality is used to define the Pareto optimal action. In addition, regret in multi-objective settings needs to be carefully redefined. \n\nThen,  after problem formulation, the paper develops an algorithm based on Doubly Regularized Online Mirror Multiple Descent, and the regret of the algorithm is analyzed, and it is shown that it matches the regret in a single objective case.", "summary_of_the_review": "Overall, I enjoyed reading this paper, and I think it studies a timely and practically relevant problem. The theoretical contribution is nontrivial and nicely executed. ", "strength_and_weaknesses": "**Strengths**\n- The paper is very well written and well organized. \n- The results are solid, and the authors provide sufficient insights on the issues with alternative solutions.\n- There are numerical results that support theoretical results. \n\n\n\n**Weaknesses**\n- The paper sounds like a nice re-execution of the multi-objective bandits in the full information feedback and online convex optimization. That said, I believe the authors did a great job clarifying the differences and unique challenges in this paper. Hence, I still believe that the contribution of this paper is valuable. \n- Is it possible to derive a problem-specific regret lower bound that captures the unique structure of the multi-objective property of the problem? It seems that in the paper, the only remark on the optimality of regret shows that with a proper parameter setting, the result matches the single-objective case. However, it is unclear what is the definition of optimality of regret in the multi-objective setting. ", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0ypnaTl922", "reviewer": "Reviewer_rnNt", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper is about Multi-objective online learning. Compared with the original online learning setting, this paper considers the case that the online algorithm is required to solve multi-sequence input loss functions simultaneously rather than the single input loss function. To measure the performance of the algorithm, this paper involves the sequence-wise PSG (Pareto sub-optimality gap), which extends the regret for the single objective online learning. Meanwhile, this paper involves the min-regularized norm with Multiple Gradient Descent to make a trade-off to the multi-gradient of the loss sequences in the proposed algorithm. Finally, this paper gives a sub-linear “regret” bound to the problem. ", "summary_of_the_review": "It is an interesting work for multi-objective online learning. In this paper, an effective measurement has been involved in online learning for multi-objective functions. Meanwhile, this paper offers an available multi-gradient descent technology in the online version. I would like to re-rate this paper if the presentation and analysis have been improved.\n\n", "strength_and_weaknesses": "This paper provides a new and efficient measurement of Multi-objective online learning. This measurement sequence-wise PSG is an extension of the original regret for the single loss function. Then, by proposing the algorithm, this paper involves the min-regularized norm to overcome the potential instability caused by the gradients for loss functions shown in a counterexample. This is a contribution.   \nHowever, there are some concerns about this paper.  \n1.\tIn the definition of sequence-wise PSG, the domain of the comparator of the algorithm is constrained to the Pareto optimality, not the total domain of the algorithm. Although the paper states the reason, it seems to be a very strong assumption of the problem. In one of the related works like “Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications ” (D. Lee et al.), the comparator term is also constrained but the domain to the comparator term remains. This paper might be supposed to emphasize more in detail to support the advantages of this measurement.   \n2.\tIn this paper, the regret bound for the multiobjective loss is T^{1/2}. In the main part and the appendix, the reviewer can only follow the result of the case when m=2, according to Lemma 3. This is a significant issue for this paper since theorem 1 only implies the sub-linear bound when the min-regularized norm method can bound the last term with arbitrary m. Otherwise, the result is a little bit incremental. Another suggestion is that the authors may rewrite the proof to make them easier and more obvious to follow, especially for Corollary 1.   \n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%