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

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 two novel multi-objective regret definitions. The regret definitions build upon an equivalent transformation of the multi-objective dynamic regret based on the commonly used Pareto suboptimality gap metric in zero-order multi-objective bandits, 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 only 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 both the static and dynamic regret bounds for the proposed algorithm, each of which matches the corresponding optimal bound in the single-objective setting. Extensive experiments on both simulation and real-world datasets verify the effectiveness of the proposed algorithm.

Multi-Objective Online Learning
Anonymous Author(s)
Affiliation Address email
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 definitions. The regret definitions build upon an equivalent transformation of the multi-objective dynamic regret based on the commonly used Pareto suboptimality gap metric in zero-order multi- objective bandits, 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 linear regret, which shows that only 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 miin-regularize-nnon solver that regularizes the composite weights. Combining min-regularized-non with OMD results the Doubly Regularized Online Mirror Multiple Descent algorithm. We further derive both the static and dynamic regret bounds for the proposed algorithm, each of which matches the corresponding optimal bound in the single-objective setting, Extensive experiments on both simulation and real-world datasets verify the effectiveness of the proposed algorithm.
2
10
11
13
14
15
17
Introduction
Traditional optimization methods for machine learning are usually designed optimize single 20 objective. However, in many real-world applications, we are often required to optimize multiple correlated objectives concurrently. For example, in autonomous driving 2 20) the self-driving
21
22 vehicles need to solve multiple tasks such as self-localization and object identification at the same
23 time. In online advertising [21] [22), advertisers need to determine the exposure of items different
24 users to maximize both the Click-Through Rate (CTR) and the Post-Click Conversion Rate (CVR).
25 In many multi-objective scenarios, the objectives may conflict with each other [15]. Hence, there may
26 not exist any single solution that optimizes all the objectives simultaneously. For example, in online advertising, merely optimizing CTR or CVR will degrade the performance of the other 22).
27
28
Multi-objective optimization (MOO) 23 6 is concerned with optimizing multiple conflicting objectives simultaneously. It seeks Pareto optimality, where single objective
be improved without hurting the performance of the others. Many different methods for MOO have been proposed, including evolutionary methods [26] [3), scalarization methods [9, and gradient-based iterative methods 77]. Recently, the Multiple Gradient Descent Algorithm (MGDA) and its variants have been introduced the training of multi-task deep neural networks and achieved great empirical success
30
31
32
33
34
29), making them regain a significant amount of research interest [17] 33 [8]. These methods
35
compute composite gradient based on the gradient information of all the individual objectives
36
and then apply the composite gradient to update the model parameters. The composite weights are determined by min-norm solver [7] which yields a common descent direction of all the objectives.
37
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

38
However, compared to the increasingly wide application prospect, the muudient-based iterative algorithms are relatively understudied, especially for the online learning setting. -bjjtt-o online learning is of essential importance due to 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 online 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 neural networks. 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 [8, Adam [6]. and AMSGrad 228
39
40
41
42
43
44
45
48
In this paper, we give systematic study of multi-objective online learning. To begin with, we formulate the framework of Aulti-OOjecttve Online Convex Optimization (MO-OCO). The first major challenge is the lack of regret definitions in the multi-objective setting. To tackle this challenge, we need appropriate discrepancy metries that can be used in the regret definitions, which evaluate the gap between any two vector losses by producing scalar values. Intuitively, the Pareto suboptimality gap (PSG) metric, which frequently used in zero-order multi-objective bandits 30 [9]. a very promising candidate. It can yield scalarized distances from any vector loss to given comparator set. We can thus define the multi-objective regret by simply plugging in PSG as the discrepancy metric. However, as a metric designed purely from the geometric view, PSG is intrinsically difficult to be optimized directly via gradient-base based iterative methods. To resolve this problem, for the -Sseb multi-objective dynamic regret, we derive its equivalent unconstrained max-min min form via highly non non-trivial transformation. This form is intuitive to the design of first-order multi-objective online algorithms, indicating that we should select convex combination of the gradients at each round. Unfortunately, for the PSG-hased static variant, such an equivalence does not exist. To remedy this issue, we make extensions of the dynamic variant by fixing the comparator set and the composite weights, which yields an appropriate definition of the multi-objective static regret.
47
48
49
50
51
53
54
55
57
59
60
61
Based on the MO-OCO framework, we develop a novel multi-objective online algorithm termed Doubly Regularized Online Mirror Multiple Descent. The key module of the algorithm is the gradient composition scheme, which calculates composite gradient in the form of convex combination of the gradients of all objectives. Intuitively, the most direct way to determine the composite weights is to apply the min-norm solver 77) commonly used in offline multi-objectinn optimization. However, directly applying min-norm is not workable in the online setting. Specifically, the composite weights in min-norm are only determined by the gradients the current round. In the online setting, since the gradients can be adversarial, they may result in undesired composite weights, further producing composite gradient that reversely optimizes the loss. To rigorously verify this point, we give showcase in which equipping OMD with vanilla min-norm even incurs a linear regret, showing that only regularizing the iterate, as in OMD, is not enough guarantee sublinear regrets in the multi- objective setting. To fix this issue, we devise a novel min-regularized-non solver with an explicit regularization on composite weights. Equipping it with OMD results in our proposed algorithm.
63
64
65
66
67
68
69
71
72
73
74
75 We then conduct the theoretical analysis for our proposed algorithm. We derive a multi-objectivy static
76 regret bound O( D(VT) and multi-objective dynamic regret bound 0221/372/3) for DR-OMMD. Both bounds match the optimal bounds in the single-objective setting II Our analysis also
77
78
shows that DR-OMMD attains lower regret than linearization with fixed composite weights.
79 To evaluate the effectiveness of DR-OMMD, we conduct extensive experiments on both simulation datasets and real-world datasets. We first elaborate simulation experiments, in which we find that DR-OMMD attains lower regret than vanilla min-norm and linearization, which verifies the solver. We then realize adaptive regularization via multi- 83 objective optimization on real-world datasets, and find that adaptive regularization with DR-OMMD significantly outperforms fixed regularization with linearization.
80
81
82 superiority of the min-regularized-noon
84
85 In summary, in this paper, we give the first systematic study of multi-objective online learning, which encompasses a novel framework, a new algorithm, and corresponding non-trivial theoretical analysis. We believe that this work paves the way for future research on more advanced multiple-objective optimization algorithms, which may inspire the design of new optimizers for multi-task deep learning.
86
87
88
2 Preliminaries
90 In this section, we briefly review the necessary background knowledge of online convex optimization
91 and multi-objective optimization.
2

---

92
2.1
Online Convex Optimization
93
Online Convex Optimization (OCO) 38 is the most commonly adopted framework for designing online learning algorithms. It can be viewed as a structured repeated game between a learner and an adversary. each round t E [l..... J. the learner is required to generate decision
94
95
96 Iy from a convex compact set X C RR, Then the adversary replies the learner with a convex function
97 Jt= X' + TR and the learner suffers the loss (xz). The goal of the learner is to minimize the regret
98
with respect to the best fixed decision in hindsight, i.e.,
- Rs(T) = 1= fe(r)) - min Σ -== ft(x").
x² EX
99 Note that the above regret is the static regret [10], which compares the learner's cumulative loss with that of fixed decision. There is another version of regret, namely the dynamic regret [TO] B4) which compares the learner's cumulative loss with that of sequence of local optimal decisions, i.e.,
100
RT( (a(T)==E) Se(ar)) - E 211
min f((x)).
102
Any meaningful regret is required to be sublinear in T, i.e., limm (T)D(T)// = O, which implies that when 7' is large enough, the learner can perform as well as the best fixed decision in hindsight (for static regret) or the local optimal decision at each round (for dynamic regret).
104
105
Online Mirror Descent (OMD) [|| is classic first-order online learning algorithm. At each round E (1,...,7) T). OMD yields its decision using the following formula
106
x++1 = arg min 17 (VV fe(x)), x) + BR(I,
=EX
107
where 17 is the step size, X + R is the regularization function, and BR =') -(2) <VR(z'). ), x²) is the Bregman divergence induced from R. As meta-algorithm, by instantiating different regularization functions, OMD can induce two important algorithms, i.c., Online Gradient
109
Descent 38 and Online Exponentiated Gradient [
2.2
Multi-Objective Optimization
112
Multiple-objective optimization (MOO) is concerned with solving the problems of optimizing multiple objectives simultaneously 39 29]. In general, since different objectives may conflict with each other, there is no single solution that can optimize the objectives at the same time. Instead, MOO seeks to find solutions that achieve Pareto optimality. Next, we exposit Pareto optimality and related definitions more formally using a vector-valued loss H = (h ......,"! as objectives, where
115
114
115
116
m 2 and h' K. - RR, i {L...., m), KC C I. is the i-th loss function.
118
Definition 2.1 (Pareto optimality). (a) For any two solutions xr, x' E K. we say that x dominates if h² (a:) < h'(x') for all i, and there exists one i such that h (x) < (a');; otherwise, we say that x does not dominate x', denoted as x A x' or x' y x.
119
s' denoted as x' or x'
120
121
(b) A solution x" IC is called Pareto optimal if it not dominated by any other solution in K.
122
There may exist multiple Pareto optimal solutions. For example, it is easy to show that the optimizer of any single objective, i.e., a E arg min h((x), {1,..., m). is Pareto optimal. Different Pareto optimal solutions reflect different trade-offs among the objectives [7].
123
124
125
Definition 2.2 (Pareto front). (a) All Pareto optimal solutions form the Pareto set Px(H). (b) The image of PH(H) constitutes the Pareto front, denoted as P(H) (H(x) x E PPc(H))
126
127 Now that we have established the notion of optimality in MOO, we proceed to introduce the metries that measure the discrepancy of an arbitrary solution x E KC from being optimal. Recall that, in the single-objective setting with merely one loss function h + H. where Q C IR for any E Q. the loss gap h(z)- min."e@ o h(2") is directly the discrepancy measure. However, in MOO with more than one loss, for any IC, the loss gap H(x) (-"", where x" E (H) is vector. Intuitionally, the desired discrepancy metric shall scalarize the vector-valued loss gap and yield
128
129
130
131
132
133
the value 0 for any Pareto optimal solution. In general, there are two commonly used discrepancy metrics in MOO, i.e. Pareto suboptimality gap (PSG) 300 and Hypervolume (HV) 4 As HV is colume-based metric, it is more difficult to optimize or analyze via iterative algorithms [6. Hence
135
in this paper, we adopt PSG, which has been extensively used in multi-objective bandits (30 19
3

---

137
Definition 2.3 (Pareto suboptimality gap). For any E K. the Pareto suboptimality gap to a given 138 comparator set K K, denoted as ((x; K", H), , defined as the minimal scalar e 2 that needs
139 to be subtracted from all entries of (x), such that (x) el is not dominated by any point in K"", where 1 denotes the all-one vector in R i.e.
140
( KC, H) = inf e, s.t. Va" E E Di , (.l....,..... h())) ( (x").
e20
Clearly, PSG is a distance-based discrepancy metric that motivated from purely geometric viewpoint.
142
In practice, the comparator set IC" is often set to be the Pareto set Px (H) [30]. Then for any a E K.
its PSG is always non-negative and equals to zero if and only if Px (x)
144
Multiple Gradient Descent Algorithm (MGDA) is an offline first-order algorithm for MOO 9
At each iteration E (1...., I.) (I. is the number of iterations), it first computes the gradient Vh (21)
145
for each objective E (1,.... m) then derive the composite gradient 9) comp Di=1 2 V/ (mx) as
146
the convex combination of these multiple gradients: it applies Si to execute the gradient descent
147
step to update the decision, i.e., I1+1 = I n9: comp, where v is the step size. The core part of
148
MGDA is the module that determines the composite weights d (A,...., 27"), which is given as
149
\ = arg min
Σ (x))(1
1, (1..... m}} denotes the probabilistic simplex in 151 R... This is a min-norm solver which finds the weights in the simplex that yields the minimum Le norm of the composite gradient. Thus MGDA is also called the min-norm method. Existing works
where Sm. {" REE X'
152
159
7 (2) have shown that MGDA is guaranteed to decrease all the objectives simultaneously until it
154
reaches Pareto optimal decision (under the convex setting where all h' are convex functions).
Multi-Objective Online Convex Optimization
155
156
In this section, we formally formulate the framework of multi-objective optimization in the online setting, termed Multi-Objective Online Convex Optimization (MO-OCO).
157
F Framework overview. We tailor the famous online convex optimization (OCO) framework to the objtiioee setting, which can be viewed as a repeated game between an online learner and the adversarial environment. At each round t E {1..... T), the learner generates decision r; from given convex compact decision set X C R". Then the adversary replies the decision with a vector loss function Fx(x)) X - I where its i-th component (x) X - R belongs to the i-th objective, and the learner suffers the loss F((e)) E I The goal of the learner is to generate a
159
161
162
163
sequence of decisions {xx) so that the cunulative loss Dn ((())) can be optimized.
164
Recall that, in the single-objective setting, the performance metric R(T) --= i.e. the regret, compares the actual decisions x, with some comparator 2, E X at each round t. For the static regret, all 2, are identically set the fixed optimal decision x" w.r.t. all losses in hindsight, ie.. 21 = x² E arg mingex En= (x)).. For the dynamic regret, each 2, is selected as the optimal decision x, w.r.t. the instantaneous loss ft at that round, i.e., = x² arg min fz).
f((2)),
166
167
168
189
170 In analogy,
define the multi-objective regret R(T)= the actual decisions T3 with some comparator 2, E X. However, in general, no single decision can optimize all the objectives the same time. Hence, it is natural to compare 2; with group of Pareto optimal decisions, which constitute a comparator set C, C X. To measure the discrepancy between 2e and C., we further introduce the Pareto suboptimality gap (PSG) [30] A(r;; C,, F.). Then the multi- objective regret can be defined as R(T)) = Σー= A(z;; C,,FF. F.). Now we can formulate the static or the dynamic variant by specifying the comparator set C, at each round. Specifically, by setting all C2 to be the Pareto set X of the cumulative loss Σ Ft, we formulate the multi-objective static regret RMOS (T) = Σr= A(x;;" X", F.). By setting each C, to be the Pareto set X, of the instantaneous loss F,, we formulate the multi-objective dynamic regret RMOD (T) ΣT= A(zi Xf, Fi).
A,, where each A, compares
171
172
173
174
175
177
178
Our definition of PSG is bit different from that in (30 In Appendix B show that they are equivalent.

---

180
Recall that PSG is zero-order metric motivated in purely geometric sense, namely. its calculation needs to solve a constrained optimization problem with an unknown boundary fa(",, Yx" E C.. Hence, it is not straightforward to design first-order algorithm to optimize PSG, not to mention the regret analysis. To motivate algorithm design and analysis, we investigate the two variants in more detail, We begin with the dynamic variant, since we find that it has an equivalent form, which is intuitive and has a strong implication on the design of effective online multiple gradient algorithms.
181
182
185
184
185
186
An equivalent form of the dynamic regret. Surprisingly, the multi-objective dynamic regret RMOD can be transformed into an unconstrained max-min form. The derivation utilizes Pareto optimality of X2 and is highly non -onvtrivial, which is deferred to the appendix due to the space limit.
197
188
Proposition 3.1. The multi-objectiio dynamic regret has an equivalent form, i.e.,
189
T Σn sup inf =Tex E3
RMOD (T)
(F((x))) -x()))).
1S1ST 1S
190
Remark. (i) The above form can be understood as a variant of the standard dynamic regret regarding {i; F whereas \ं are unknown to the learner. This provides an intuition that we can gen- erate weights A E Sm, at each round and optimize (i,Fil via single-objective techniques. For first-order algorithms, is equivalent to selecting convex combination of individual gradients and then applying the composite gradient to model update. Undoubtedly, how to generate the weights A needs some careful designs, which will be explicated later in the algorithm section.
191
192
195
194
195
iii) When = 1, we have Sm. {1} and X arg m F()x). Hence RMOD(T) E (F.( - mingex F((r)), which is exactly the single-objective dynamic regret RT((T)
197
198
An alternative form of the static regret. Unfortunately, for RMOs: the above equivalence form does not exist. Here the reason. In RMOs, the comparator set X' is the Pareto set of the cumulative loss Σx F, rather than the instantaneous loss F,. Hence, at some specific round t, the decision It may Pareto dominate all points in X w.r.t. the instantaneous F,, and we would expect the metric A to be negative. However, PSG (or other commonly used metrics such as Hypervolume) always yields non-negative values, so the induced RMos is not aligned with Rg. For example, when
199
200
202
204 m- 1, we have RMOS (T) supx Dr (
(,)),,)), which can be much looser than the static regret (T) = sup=*ex* Et (P) - Fx))))) Hence the analysis of RMos is intrinsically complex if we use existing discrepancy metrics that always yield non-negative values.
205
206
207
Enlightened by Proposition 3.1 we can formulate the static regret in a different way, i.e., by modifying the equivalent form of dynamic regret. Recall that in Proposition 3.1 at each round f, the comparator o is selected from the Pareto set XT of the instantaneous loss Fr, and the weights A3 are generated from Sm. To formulate the static variant, we can use fixed comparator x= from the Pareto set X" of the cumulative loss E, F2 and fixed weights X E Sm at all rounds. Now the static variant takes
209
211
RMos (T) = sup inf x' EX ESS....
X
F((x)) - - F((x)).
Remark. (i) RMOs(T) has clear physical meaning that optimizing it will impose the cumulative
loss Eim (x,) to reach the Pareto front P See more details in Appendix C.
213
(ii) When = 1, Sm {1} and X reduces to arg minzex ΣT= (z)). Therein RMos(T) =
214
F((x)) min DT Fi(x"), which reduces to the single-objective static regret Rs (T')
215
4
Online Mirror Multiple Descent
216
217
In this section, we present the Online Mirror Multiple Descent (OMMD) algorithm, the protocol of which is given in Algorithm [ At each round f, 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 to the online mirror descent step.
218
219
220
4.1
Vanilla Min-Norm May Incur Linear Regrets
222
The core module of OMMD is the composition of multiple gradients. For simplicity, we represent the gradients at round in matrix form (zz) (z.).... V (xx)) E _=*m, Then the
5

---

Algorithm Doubly Regularized Online Mirror Multiple Descent (DR-OMMD)
1: Input: Convex set X, time horizon T, regularization parameter at, learning rate 7/S regulariza- tion function R, user preference Ao-
2: Initialize: T1 X.
3: for = ,,...,, do
4: Predict 2 and receive a loss function F. X' Rm
5: Compute the multiple gradients V (x+) = [V (..)..... V.[T" E Raxm.
6: Determine the weights for the gradient composition via min-regularized-norm
A arg min (2:)) all2 - 2o111
AES
7: Compute the composite gradient 9t = (..(
8: Perform online mirror descent using 9t
F++1 arg min at) Bn(x,
TEA
9: end for
224
composite gradient is given as 9t = (Fa where xe is the composite weights. As illustrated in Preliminary, the min-norm method in MGDA [9] is classic method to determine the composite weights the offline setting, which results in a common descent direction that can descend all the losses simultaneously. Thus, it is tempting to consider applying it to the online setting.
226
228
However, directly applying the min-norm method to the online setting not workable, which may even incur linear regrets of the resulting algorithms. The rationale is as follows. In the vanilla norm method, the composite weights A are determined solely by the gradients (x.) at the current round f, hence they are very sensitive to the instantancous loss F, 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 problem instance in which min-norm incurs linear regret. We extend OMD to the multi-objective setting, where the composite weights are directly yielded by min-norm [...
230
232
234
236
Problem instance.
We consider two-objective problem. The decision domain is X {(u, v) 0 u S 2, 2 0} and the loss function at each round
238
e
F1(1)= = (I|== all || - -b1)), t= = 1,
k = 1.
[(1 - b12 - cll2),
t 1=2k, 2k,
k= 1,2,
239
where a = (-2, 1),b = (0, c = (2, (1). For simplicity, we first analyze the case where the total time horizon T is an even number. Then we can compute the Pareto set of the cumulative
loss Ei= Fe, i.e., X" ((,,0) -- < u uu 11) which locates at the r-axiss For conciseness of analysis, we instantiate OMD with 1.2 re-rreuuaarzzaton, which results in the simple OGD algorithm
242
243
24 We start an arbitrary point .ı (1), E X satisfying ei > O. At each round t, suppose the decision Ie- = (ux, vx) E X, then the gradients of each objective w.r.t. 24 can be calculated as
244
g = [(2t + 4, 20 + 2), (22m:
1 t= 2h 1;
(2uR,
20 2), t= 2k 1;
gee
-
20,- -0-22 2), t 2k.
(24 - 4, 20 2),
t = 2k.
Since 0 S 0, < J. we observe that the second entry of either gradient alternates between positive and negative. By using min-norm, the composite weights X; can be computed as
246
((1 ur vx)/4, A = ((3 4 + v4)/4, (1 41+4-- - 1 o4)/4), t= 2k.
(3 + u4 + rz)/4), 1= 2k 1;
We observe that both entries of composite weights alternative between above and below }. and 248 | d |1 > 1. Recall that || | = 1, hence the composite weights at two consecutive rounds change radically. The resulting composite gradient takes
247
249
(u: - 1/ + 1,
- -t + 1/ - 1), 1= 2k 1;
comp
(- 2/4 1,
- -4 - 1), t= 2k.

---

250
The fluctuating composite weights mix with the positive and negative second entries of gradients, making the second entry of 9: mp always negative, i.e., - + 24 < 0 and -4 4 Hence 9t cmmp actually drives 24 away from the Pareto set X that coincides with the r-axis. This essentially reversely optimizes the loss, hence increases the regret. In fact, we can prove that it even incurs a linear regre(" Due to the lack of space, we leave the proof of linear regret when T is an odd number in the appendix. The above results the problem instance are summarized as follows.
251
253
254
255
256
Proposition 4.1. For OMD equipped with vanilla min-norm, there exists a multi-objective online convex optimization problem, in which the resulting algorithm incurs a linear regret.
257
258
Remark. Stability is a basic requirement to guarantee meaningful regrets in online learning [25] In the single-objective setting, directly regularizing the iterate 2, (e.g., OMD) is already enough. However, as shown in the above analysis, only regularizing 2 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 the composite gradient. Therefore, in multi-objective online learning, besides regularizing the iterates, also need to explicitly regularize the composite weights.
260
262
4.2
Doubly Regularized Online Mirror Multiple Descent
Enlightened by the design of regularization FTRL 225 we consider the regularizer r(x, Ao). where 265
An is the pre-defined composite weight that may reflect the user preference. This results in new solver called mii--egularized--oore i.e.,
287
A = arg min [ + ar(A, AES
288
where is the strength of regularization. Equipping OMD with the new solver, we derive the proposed online algorithm. Note that beyond the regularization on the iterate x; that is intrinsic in
289
270
online learning, there is another regularization on the composite weights A in min-regularized norm.
271
Both regularizations are fundamental and they together ensure the stability in the multi-objective online setting. Hence we call the algorithm Doubly Regularized OMMD (DR-OMMD).
272
In principle, can take various forms such L1-norm, Lo-norm and KL divergence etc. Here we adopt -nom since it aligns well with the simplex constraint of X. Min-regularized-nonn
274
275
be computed very efficiently, since it has closed-form solution when m 2. Specifically, suppose the gradients at round are gf and g². Set 7L (02 (92 - 91) aa) ll92 9ıll² and
276
277
7R = (g) (g2 91) + ai/ |1922 - 91ll². Given any Ao = (70, 7o) E Sz, we can compute the composite weights X, (y,, 1 7)) where
7 max (oiin(?" 1}. 0), where 7/" =
vn).
279
In addition, when m > 2, since the feasible region S,, is simplex, we can introduce a Frank-Wolfe solver 14 compute the composite weights. See the protocol and more details in Appendix D.
280
281
Compared to vanilla min-norm, the composite weights in min-regularized-nn norm are not fully deter- mined by the adversarial gradients. The resulting relative stability of composite weights make the composite gradients more robust to the adversarial environment. In the following, we give general analysis and prove that DR-OMMD indeed guarantees sublinear regrets.
282
283
284
285
4.3
Analysis
286
We now analyze the static regret and the dynamic regret of DR-OMMD. Our analysis is based on the following commonly used assumptions [13
287
Assumption 4.2 (Bregman divergence). The regularization function R is 1-strongly convex. In
289
addition, the Bregman divergence is L-piscchitz continuous, i.c., BR( 2) - BR(y.²) S 7||
290
vI1, Va, y, 2 E domR, where dom R is the domain of R and satisfies X' domn R
Assumption 4.3 (Lipschitz continuity). For each i E (1,..., m. there exists some positive and finite G such that, the i-th loss ft at each round t (I...., T}
} is G-Lipschitz continuous w.r.t. ||- ie., (z) fl (x') < GlIæ z'Il. Note that in the convex setting, this assumption leads to bounded gradients, i.c., (f)()) S for any E (I,...,T), (I....,m, m.., x x E X.
292
294
Mooe concisely, here the regret is the multi- objeivobe static regret.
7

---

295
We first provide the static regret bound. The proof is left to the appendix due to the lack of space. Theorem 4.4. Suppose the diameter of X is bounded by D. Assume Fe is bounded, i.e., lfi(x)) S
296
F V,Ve X (1, (I,..., TT, ,.,...,... For any do Sm. DR-OMMD atlains
287
1 RMos(T) - Bulx" (o)l",,z))+ " (IVF(OD) 17
T
4F 1 - doll1).
7
298
Remark. (i) Linearization with weights Ao E Sm can be viewed as single-objective optimization on scalar loss Ag F,, whose gradient is 9: (2) Hence we can directly borrow the tight bound of OMD (Theorem 6.8 in (27]) and derive a bound 1 [Bn(x", =1) Σ The [VF for linearization. In comparison, if we set = 4F/n in DR-OMMD, then from the formulation of b the bound becomes 1 (x( 211 + Ei=1 minxes.. (zx) + allA - >olla), which is smaller than that of linearization. Note that the lower regret of DR-OMMD compared to linearization is also empirically verified in our experiments (see Figure D.
300
2
301
304
iii When 7) v2-D
1F, the bound is in the order of O(VT). It matches the optimal static GVT a 77
306
objele-ob regret bound w.r.t. T (see more details in Appendix E).
307
Then we turn to the dynamic regret. Our analysis relies on an additional assumption 2 32
308
Assumption 4.5 (Temporal variability). For each E ml,. there exists some positive and finite VT such that Ei=1 supzex [f((z) (z) S Vr.
309
Theorem 4.6. Assume the step size satisfies GoT S S W/z Then under all the above assumptions.
310
for any preference do E Sm, OMMD with hiii-regulrrized-nome attains
BMOD (T) S GTT
DV
T + (IVT +
"
SFG2T VT
11 Aull2).
2
G2
2
Remark. When = ( GT
(>DVV /1/3 a
TFG the bound is in the order of 0 matching V/r
312
313
the best attainable single-objective dynamic regret bound 2 35 (see more details in Appendix E).
314
5
Experiments
315
In this section, we conduct extensive experiments to evaluate the effectiveness of DR-OMMD. We consider two baselines: (i) linearization performs single-objective online learning the linearized loss Ao F2 at each round t, where the weights λo E Sm are given beforehand; note that it is equivalent to computing composite gradients with fixed weights A Ao. (ii) min-norm equips OMD with vanilla min-norm 7 for gradient composition.
317
319
320
5.1
Simulation Experiments: Tracking the Pareto Front
As summarized in Figure 1 (a), the goal is to track two points Ef cycling along circle C = (5 R² ||E|]2 = 1}. For each E {1, 2}. E = (cos 0j, sin of) is determined by some angle 0z. We set positive integer pi the rotating period of E. which is unknown to the learner. The two points are initialized by 0 = 0 and 03 = TT/2 and move as follows: at each round I, for each E (1,2), the adversary independently samples an angle 5ÿ from Gaussian distribution (2T PPi 1 1/) then moves the i-th point to Ei+ = (cos 0f sin 0 where 0: = 0ī - 8f. Note that E0;- =
322
323
324
325
326
327
0 + 2nt/ Pi, hence in average E rotates clockwise with a period of pi_ At each round t, the learner
generates a decision I, from L2-norm ball X {I E 2 |2||| < 2}. Then it acquires E, e2 and suffer the losses fi = ||, - / E [1. In this problem, the Pareto set of F, = (ft f?) exactly the line segment between & and E i... X = {Ac] + (1 2)& A (0, 1].. At each round t, PSG measures the squared distance between I, and X
329
331
We run T = 10, 000 rounds. To simulate the pattern drift, we set p = 10. p2 = 20 at the first 333 Ti 3, 000 rounds, and pl 20, p2 10 at the last T2 = 7, 000 rounds. For linearization, the weights Ao = (Aj, 1 X are decided via a grid search \o E 00, 1); we consider three variants: lin-/ uses the optimal An for the first Tj rounds, lin-2 uses the optimal Ao for the
332
335
last T3 rounds, and lin-opt uses the optimal d for all T rounds. For DR-OMMD, for faimess of
8

---

8:37
In-e::
6.2
Avarage Lave
co.
2.2
2000
0000
10:00
32330
00
92
05 36
10
2500
5004 7508 3300 12540
(a) Simulation Secup
(b) Leaming Curve
(a) Effect Preference
A2
(b) Learning Curve
Figure 1: Simulation setup and results. (a) The
Figure 2: Results to verify the effectiveness of adaptive regularization on protein. (a) Perfor- mance of DR-OMMD and linearization under varying Ào = (A), 1 x (b) Performance us- ing the optimal weights Xg = 0..1,
targets E/ 4 cycle along the circle. The Pareto set at each round is the line segment [5/ <?1; PSG measures the distance from 2; to [s. - (b) Performance FR-OMMD and baselines.
337
comparison we use the same Å of lin-opt. The learning rates 17 in all algorithms and the parameter in DR-OMMD follow the corresponding theories (c.g., Theorem 4.6). In this experiment, since the loss functions are manually designed, the value of Vr can be directly calculated. Note that in
338
339
340
some scenarios where Vr is unknown, we can conduct grid search and utilize a meta-algorithm to handle the unknown Vr (37 [. similar the single-objective setting. From the results Figure [ we find that DR-OMMD achieves the lowest PSG, showing its ability to track the Pareto front; meanwhile, min-norm appears very unstable the online setting, even worse than linearization.
341
(b),
343
344
5.2
Convex Experiments: Adaptive Regularization via Multi-Objective Optimization
In many real-world online scenarios, regularization is often adopted avoid overfitting. A standard way is to add a term r(z) to the loss (x) at each round and optimize the regularized loss f(()) 346
or (I) 24 where is treated as hyperparameter that needs to be fixed beforehand. The formalism of multi-objective online learning provides a novel way to realize regularization. Since r(x) measures the complexity of ær it can be regarded as the second objective alongside the primary goal (xx). We
348
349
350
can construct a vector loss (x()) = ((())),(() at each round and thereby cast regularized online learning into bi-objective online optimization problem. Compared to fixed regularization, the new approach effectively chooses the regularization strength or = X//A| in an adaptive way.
351
352
We use two large-scale online benchmark datasets. (i) protein is a bioinformatics dataset for protein type classification [31]. which has 17 thousand instances with 357 features. (ii) covtype is a biological dataset collected from non-stationary environment for forest cover type prediction B]. which has
354
356
50 thousand instances with 54 features. For both tasks, we set the logistic loss of classification as the first objective, and the squared L2-norm of model parameters the second objective. Since the ultimate goal of regularization is to enhance predictive performance, we adopt the average loss as the performance metric, namely EisT Ie(x:))/T where (1())) is the classification loss at round l.
357
358
359
360
We adopt 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 10.1, 3.0). .. For DR-OMMD, the parameter a is simply set as 0.1. For fixed regularization, the strength = (1 A /1. is determined by the some preference A E [o, 1]. which is essentially linearization with weights Ào
361
(Ap: 1- -A)). We run both algorithms with varying initial weights X E 0., .... }). In Figure we plot (a) their final
363
365
performance w.r.t. the choice of Ao and (b) their learning curves with desirable An (c.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- RMMM consistently outperforms fixed regularization.
367
6 Conclusions
389
In this paper, we give a systematic study of multi-objective optimization in the online setting. We first formulate the framework of Multi-Objective Online Convex Optimization. Then we devise the Doubly Regularized Online Mirror Multiple Descent algorithm, which has a special design for gradient composition in online learning, namely hiin--egulariee--ooe bounds for OM-D and conduct extensive experiments to demonstrate its effectiveness.
371
372
We provide non-trivial regret
373
Limitations. As the first step of studying multiple gradient algorithm in online learning, we conduct our analysis in the convex setting. Although does not affect the usage the non-convex setting (see empirical validation in Appendix F), we can give a formal non-convex analysis in the future.
375

---

References
377
378
[1] Dheeraj Baby and Yu-Xiang Wang. Optimal dynamic regret in exp-coneave online learning, In Conference Learning Theory, pages 359-409. PMLR, 2021.
380
[2] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Opera- lions Research, 6365):122711244, 2015.
381
382
[3] Jock A Blackard and Denis Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and Electronics in Agriculure, 24(3):131-154) 1999.
383
384
[4] Lucas Bradstreet. The hypervolume indicator for multi-objective optimisation: calculation and use. University of Western Australia Perth, 2011.
386
387
[5] Nicolò Campolongo and Francesco Orabona. A closer look at temporal variability in dynamic online learning. arXiv preprint arXiv:2102.07666, 2021.
389
[6]
Kalyanmoy Deb. Multi-ohjective optimization. In Search methodologies, pages 403-449 2014.
390
[7] Jean-Antoine Désidéri. Multiple- descent algorithm for multiobjective optimization. Comptes Rendus Mathematique, 350(5-6):313-318 2012.
382
[8] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
393
394
99] Jörg Fliege and Benar Fux Svaiter. Steepest descent methods for multicriteria optimization. Mathematical Methods of Operations Research, 51(3):479-494, 2000.
110] Eric Hall and Rebecca Willett. Dynamical models and tracking regret in online convex pro- gramming. In International Conference on Machine Learning, pages 579-587, 2013.
387
398
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimization, 2(3-4):157-325, 2016.
399
400
[12]
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 Puttern Analysis and Machine Intelligence, 42(10))2002-2719, 2019.
402
403
[13] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online optimization: Competing with dynamic comparators. In Artificial Intelligence and Statistics, pages 398-406, 2015.
405
406
[14] Martin Jaggi. Revisiting Frank- Wolfe:
Projection-free sparse convex optimization. In Interna- tional Conference on Machine Learning, pages 427-435, 2013.
407
408
[15] Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty weigh losses for scene geometry and semantics. In IEEE Conference on Computer Vision and Pattern Recognition, pages 7482-7491, 2018
409
410
[16] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 411
arXiv: arXiv:1412.6988 1412.6980 2014.
[17] Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qing- Fu Zhang, and Sam Kwong. Pareto multi-task learning. In Advances in Neural Information Processing Systems, pages 12060-12070, 2019.
414
415
[18] Bo Liu, Xingchao Liu, Xiaojie Jin, Peter Stone, and Qiang Liu. Conflict-averse gradient descent for multi-task learning. arXiv preprint arXiv:2110. 144444 2021.
416
417
[19] Shiyin Lu, Guanghui Wang. Yao Hu, and Lijun Zhang. Multi-objective generalized linear bandits. In International Joint Conference on Artificial Intelligence, pages 3080-3086, 2019.
418
[20] Weixin Lu, Yao Zhou, Guowei Wan, Shenhua Hou, and Shiyu Song. L3--et: Towards learning based lidar localization for autonomous driving. IEEE Conference on Computer Vision and Pattern Recognition, pages 6389-6398, 2019.
420
10

---

422
[21] Jiaqi Ma, Zhe Zhao, Xinyang Yi, Jilin Chen, Lichan Hong, and Ed H Chi. Modeling task rela- tionships in multiitask learning with on Knowledge Discovery & Data Mining, pages 1930-1939, 2018.
423
exxpeess. In International Conference
[22] Xiao Ma, Liqin Zhao, Guan Huang, Zhi Wang, Zelin Hu, Xiaoqiang Zhu, and Kun Gai. Entire 425
426
space multi-tash model: An effective approach for estimating post-click conversion rate. In International ACM SIGIR Conference on Research & Development in Information Retrieval, pages 1137-1140, 2018.
427
428
429
[23] Timothy Marler and Jasbir S Arora. Survey of multi-objective optimization methods for engineering, Structural and Multidisciplinary Optimization, 26(6):369-395, 2004.
430
431
[24]
Brendan McMahan, and L1 regularization. In International Conference Artificial Intelligence and Statisties, pages 525-533, 2011.
Follow-the-rggulariiee--ee and mirror descent: Equivalence theorems
432
433
434
[25] H Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. The Journal of Machine Learning Research, 18(1)3111-3116, 2017.
435
[26]
Tadahiko Murata, Hisao Ishibuchi, et al. MOGA: multi-objective genetic algorithms. In IEEE International Conference on Evolutionary Computation, pages 289-294, 1995.
437
438
[27]
Francesco Orabona. modern introduction to online learning. arXiv preprint arXiv: 1912.
2019.
440
[28]
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In International Conference on Learning Representations, 2018.
441
442
[29] Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimization. In Advances in Neural Information Processing Systems, pages 525-536, 2018.
443
444
[30] Eralp Turgay, Doruk Oner, and Cem Tekin. Multi-objective contextual bandit problem with similarity information. In International Conference on Artificial Intelligence and Statisties, pages 1673-1681, 2018.
445
448
447
[3I] Jung-Ying Wang. Application of support vector machines in bioinformatics. PhD thesis, National Taiwan University, 2002.
448
[32] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In International Conference Machine Learning, pages 449-457, 2016.
450
[33] Tianhe Yu, Saurabh Kumar, Abhishck Gupta, Sergey Levine, Karol Hausman. and Chelsea Finn. Gradient surgery for multi-task learning. In Advances in Neural Information Processing Systems, pages 5824-5836, 2020.
453
[34] Lijun Zhang, Shiyin Lu, and Zhi-Hua Zhou. Adaptive online learning in dynamic environments. In Advances in Neural Information Processing Systems, pages 1330-1340, 2018
456
457
[35] Lijun Zhang, Tianbao Yang, Zhi-Hua Zhou, et al. Dynamic regret of strongly adaptive methods. In International Conference on Machine Learning, pages 5882-5891 2018.
458
459
[36] Richard Zhang and Daniel Golovin. Random hypervolume scalarizations for provable multi- objective black box optimization. In International Conference on Machine Learning, pages 1 11096-11100 1105, 2020.
460
462
[37] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. Advances in Neural Information Processing Systems, 33:12510-12520, 2020.
463
38
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning, pages 928-936, 2003.
485
486
[39] Eckart Zitzler and Lothar Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE transactions on Evolutionary Computation, 3(4):257-271, 1999.
468

---

Checklist
489
470
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
472
contributions and scope? [Yes]
473
(b) Did you descrihe the limitations of your work? [Yes] See Section 6.
474
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work
475
concerning a general problem in online learning.
476
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
478
2. If you are including theoretical results...
479
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section 4.3.
480
481
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix G, H.
482
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] They are included in the supplementary materials.
484
486
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 5.
487
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [N/A] We conduct online learning experiments, where the learning process is deterministic.
489
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix E.
492
493
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
494
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite the source of datasets.
485
(b) Did you mention the license of the assets? [Yes] In the supplemental material. URL? [Yes]
(c) Did you include any new assets either in the supplemental material Our codes are provided in the supplemental material.
498
499
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] We only use publicly available benchmark datasets. (e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] We only use publicly available benchmark datasets.
500
501
503
504
5. If you used crowdsoureing or conducted research with human subjects...
505
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
506
507
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
508
509
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "GgGDc9uyvim", "reviewer": "Reviewer_6wxE", "summary": "This work performs a systematic study of online multi-objective optimization.  The authors formulate the multi-objective online convex optimization, in which multi-objective dynamic regret and static regret are formulated.  \nThe authors further show that the vanilla min-norm method used in MGDA may incur linear regrets. The authors further proposed a regularized version of online mirror descent. The min-regularization-norm is inspired by the regularization in FTRL. Both static regret bound and static regret bound are derived for the proposed regularized multi-objective online mirror descent method. The regret bounds match the optimal regret bounds in the single-objective setting. \n\n", "questions": "Can the authors leverage more on what are the meaningful and high-impact applications of online convex optimization? ", "limitations": "- The empirical evaluation is not comprehensive enough. \n- The motivation and significance of the contribution need justification. \n- The proposed method is in fact quite straightforward. The novelty is kind of limited. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- The multi-objective online convex optimization framework is quite clean and helpful.\n- The proposed algorithm is reasonable and sound. The theory is solid to me.\n- Good empirical performance.\n\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GbVyZjh4do", "reviewer": "Reviewer_yhTW", "summary": "This paper focuses on the problem of multi-objective online convex optimization, where the losses are given in vectors and the scalarized objective is the Pareto suboptimality gap, which to some extent reflects the distance to the Pareto frontier. The authors proposed online mirror multiple descent, which is the generalized version of online multiple gradient descent by allowing different regularizers, and provably enjoy optimal dynamic regret. Experiments validate the effectiveness.", "questions": "Does the term the $\\sum_t \\lambda_t-\\lambda_0$ in Thm 4.6 have some specific meaning?", "limitations": "See weaknesses above.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Clear writing\n- Standard techniques with strong results\n\nMinor Weaknesses:\n- There exists mainly two lines of work on multi-objective online learning. One line focuses on the Pareto frontier while another line focuses on deriving no-regret algorithms according to Blackwell's approachability theorem. Though slightly different in the explicit scalarized objective, I think both lines of work contribute a lot to the community. And thus some additional related works and contenders should be noticed.\n- The implementation of projection with different types of regularizers in OMMD should be carefully discussed.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BrqrGRhsUSu", "reviewer": "Reviewer_aTnA", "summary": "This paper studies the online multi-objective learning problem in the online convex optimization (OCO) framework. The main contribution of the paper is to show that the regret minimization problem over the Pareto suboptimal gap can be converted to a single-objective optimization problem. Then, the online mirror descent method can be applied to achieve the static and dynamic regret bound for the multi-objective learning problem.\n", "questions": "- What is the gap between the alternative form of static regret (Line 210) and the static regret defined by PSG (Line 177)?  Can the gap between the two regrets be bounded?\n- it seems the code in the supplementary material only contains the implementation of the min-norm solver rather than the whole code. \n- the optimal step size in Theorem 4.6. relies on the temporal variability $V_T$, which is unknown in advance. In the single-objective setting, some previous works try to solve this issue by grid search with a meta-algorithm [4,5,6]. How does the algorithm in this paper handle the non-stationarity to obtain the dynamic regret? \n- in Line 42-43, the authors have claimed that “the theoretical investigation of multi-objective online learning will lay a solid foundation for the design of new optimizers for multi-task deep neural networks.” However, it seems to me that the theoretical results in this paper do not have a strong connection with multi-task DNN ( in OCO framework, the function should always be convex). It would be better if the author could elaborate more on this issue. \n\n\n[4] P. Zhao, Y.-J. Zhang, L. Zhang, Z.-H. Zhou. Dynamic regret of convex and smooth functions. In: Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.\n\n[5] D. Baby and Y.-X. Wang. Optimal dynamic regret in exp-concave online learning. In: Proceedings of the 34th Conference on Learning Theory (COLT), 2021.\n\n[6] D. Baby and Y.-X. Wang. Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond. In: Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.\n", "limitations": "This paper has discussed its potential limitations in Line 370-372. But I think there are also some other limitations as I have listed in the weakness and question part.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strength:\n- Novelty: although the definition of Pareto suboptimal gap (PSG) has appeared in the bandits setting, the paper proposes an interesting reduction in the full information setting that the regret defined by PSG can be converted to a single-object optimization problem.\n- Clarity: this paper is well-structured and clearly written in most parts, which makes it easy to follow.\n\n### Weakness:\n- the title of this paper is somewhat overclaimed to me. The focus of this paper is on the multi-objective optimization in OCO (full information), and a gradient-based algorithm is proposed, which is not that general enough to cover the entire multi-objective online learning. For example, as referred by the paper, there are many papers on multi-object optimization in the context of bandit. Besides, multi-objective learning does not only exactly mean multi-objective optimization. For instance, [1] considers the optimization of two objectives in MAB (best arm identification and regret minimization); other results can be found in the references therein. Even in the full information, there is work studying how to handle the Pareto-frontier in the absolute loss game [2]. So, I advise the author to place the paper in the right place of the contemporary literature to avoid misleading. \n\n- Although the reduction proposed in this paper is interesting, I still have some reservations about the main theorems and their proofs.\n\t- on Theorem 4.6: by the optimal step size, the method achieves an $O(T^{2/3}V_T^{1/3})$ dynamic regret bound. But in the full information online learning (i.e. there is no noise in the feedback), a simple algorithm by just playing $x_t^* = \\\\arg \\\\min_{x\\\\in\\\\mathcal{X}} f_{t-1}(x)$ can achieve $O(V_T)$ dynamic regret [3]. I am not sure whether the $O(T^{2/3}V_T^{1/3})$ bound is tight in the full information case. It would be nice if the author could provide a lower bound.\n\t- another concern is the technical contribution of this paper. It seems that the proofs of Theorem 4.4 and Theorem 4.6 follow the standard analysis of the OMD algorithm. I think it would be nice for the author to highlight their technique contributions.\n\n- about the experiments: as shown by the authors in line 337, the learning rate $\\eta$ and parameter $\\alpha$ are set according to the theories. However, it seems that the setting of the step size $\\eta$ requires the knowledge of $V_T$, which is unknown in advance in the practice. So, it is unclear to me how the authors choose the parameter in the experiments ( Maybe one can calculate the $V_T$ in advance of the online learning process, but this could make a somewhat artificial experiment setup.).\n\n- about the reproducibility: it seems that only the supplementary material only provides the code on the min-norm solver, which is not the method proposed by this paper.\n\n[1] R. Degenne, T. Nedelec, C. Calauzenes and V. Perchet. Bridging the gap between regret minimization and best arm identification. In: AISTATS 2019.\n\n[2] Koolen W M. The pareto regret frontier. In: NeurIPS 2013.\n\n[3] Yang, T., Zhang, L., Jin, R., and Yi, J. (2016, June). Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. In: ICML 2016.\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Atf8D3mPbD1", "reviewer": "Reviewer_5pLZ", "summary": "The paper studies multi-objective online learning. It proposes new notions of static regret and dynamic regret based on a Pareto suboptimality gap metric. They show that OMD with the min-norm solver has linear regret, motivating the design of new algorithms. They propose a novel algorithm, Doubly regularized Online Mirror Multiple Descent, that regularizes the composite weights. They show that it obtains static and dynamic regret bounds with the usual scalings in T and that match the optimal bounds when there is only one objective. They provide experiments comparing their algorithm to a linearization baseline and the OMD algorithm with the min-norm solver.", "questions": "What is the the definition of regret in figure 1: static or regret? This is important for interpreting the experimental results.\n\nIn several places, the authors mention the optimal weights (e.g., \"...lin-2 uses thwe optimal lambda_0 for the last...\" line 333 and the caption in Figure 2). What is meant by the optimal weight? \n\nI think explaining the improvements over the linearization baseline is very important. ", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is clearly written and provides a nice pedagogical overview of the field. \n\nMulti-objective online learning is an important problem with many real-world applications. The new algorithms could find widespread use. \n\nThe paper develops seemingly new regret notions with new algorithms and provides experiments showing that their method is competitive. \n\nIt is nice that they give a simple example showing that MGDA doesn't work in the multi-objective setting. This is useful motivation for the design of new algorithms. \n\nWeaknesses:\n\nThe theoretical comparison to the linearization baseline seems incomplete. It would be nice to understand what a standard analysis for linearization baseline yields for its regret bounds and how this may be suboptimal in comparison to the proposed algorithm. For example, it seems that in the static regret setting removing the inf in the display between lines 210 and 211 and applying the standard analysis also gives a $O(\\sqrt{T})$ regret. Is that correct? In lines 299-301, there is some discussion of the differences, but it is unclear how large of a difference there is between the methods. Are there concrete examples as for MGDA?\n\nIn the experiments, although the proposed method performs strongly, the improvement over the linearization baseline does not seem significant. This is especially important since the proposed method is more computationally burdensome than the linearization baseline, requiring to solve the optimization problem in in lines 266-267. This makes it more important to show an improvement over linearization.\n\nIt seems like an attractive property of MGDA is that it balances between the objectives (lines 151-153). Is there a similar property for this work?\n\nIn Section 5.2, it is not clear to me what is the advantage of choosing the regularization strength in an adaptive way. Won't this just yield one point on Pareto Front, so it is not significant? Can you describe the advantage in more detail?\n\nWhile the upper bounds have the attractive property of achieving the optimal rates in the single-objective setting, the authors give no lower bounds for the multi-objective setting, so optimality of the approach is unclear. Can the authors comment on optimality?\n\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject