Pareto Navigation Gradient Descent: a First Order Algorithm for Optimization in Pareto Set
Authors: Mao Ye
qiang liu
Venue: ICLR 2022 Submitted (2022)
Keywords: Pareto set
Multitask learning

Abstract: Many modern machine learning applications, such as multi-task learning, require finding optimal model parameters to trade-off multiple objective functions that may conflict with each other.
The notion of the Pareto set allows us to focus on the set of (often infinite number of)
models that cannot be strictly improved. But it does not provide an actionable procedure for picking one or a few special models to return to practical users. In this paper, we consider \emph{optimization in Pareto set (OPT-in-Pareto)}, the problem of finding Pareto models that optimize an extra reference criterion function within the Pareto set. This function can either encode a specific preference from the users, or represent a generic diversity measure for obtaining a set of diversified Pareto models that are representative of the whole Pareto set.
Unfortunately, despite being a highly useful framework, efficient algorithms for OPT-in-Pareto have been largely missing, especially for large-scale, non-convex, and non-linear objectives in deep learning. A naive approach is to apply Riemannian manifold gradient descent on the Pareto set, which yields a high computational cost due to the need for eigen-calculation of Hessian matrices. We propose a first-order algorithm that approximately solves OPT-in-Pareto using only gradient information, with both high practical efficiency and theoretically guaranteed convergence property. Empirically, we demonstrate that our method works efficiently for a variety of challenging multi-task-related problems.

Under review conference paper at ICLR 2022
PARETO NAVIGATION GRADIENT DESCENT: ORDER ALGORITHM FOR OPTIMIZATION IN PARETO SET
FIRST-
Anonymous authors Paper under double-blind review
ABSTRACT
Many modern machine learning applications, such as multi-task learning, require finding optimal model parameters trade-off multiple objective functions that may conflict with each other. The notion of the Pareto set allows us to focus on the set of (often infinite number of) models that cannot be strictly improved. But it does not provide an actionable procedure for picking one or a few special models to return to practical users. In this paper, we consider optimization Pareto set COPT-in-Paretol the problem of finding Pareto models that optimize an extra reference criterion function within the Pareto set. This function can either encode a specific preference from the users, or represent a generic diversity measure of diversified Pareto models that representative of the whole Pareto
for obtaining set. Unfortunately, despite being a highly useful framework, efficient algorithms for OPT- in-Pareto have been largely missing, especially for large-scale, non-convex, and non-linear objectives in deep learning. A naive approach to apply Riemannian manifold gradient descent on the Pareto set, which yields high computational cost due the need for eigen- calculation of Hessian matrices. We propose a first-order algorithm that approximately solves OPT-in-Pareto using only gradient information, with both high practical efficiency and theoretically guaranteed convergence property. Empirically, we demonstrate that our method works efficiently for a variety challenging multi-task-relater problems.
10
12
13
14
15
16
17
18
INTRODUCTION
19 Although machine learning tasks are traditionally framed as optimizing a single objective. Many modern applications, especially areas like multitask learning, require finding optimal model parameters minimize multiple objectives (or tasks) simultaneously. As the different objective functions may inevitably conflict
20
21
22 with each other, the notion of optimality multi-objective optimization (MOO) needs to characterized by the Pareto set: the set of model parameters whose performance of all tasks cannot be jointly improved.
24 Focusing on the Pareto set allows us to filter out models that can be strictly improved. However, the Pareto set typically contains infinite number of parameters that represent different trade-offs of the objectives. 26 For m objectives f,,...,by, the Pareto set often an (m - 1) dimensional manifold. both intractable and unnecessary give practical users the whole exact Pareto set. A more practical demand is to find some user-specified special parameters the Pareto set, which can be framed into the following optimization in Pareto set (OPT-in-Paree)
28
29
problem:
30 Finding one or a set of parameters inside the Pareto set of fm that minimize a reference criterion F.
Here the criterion function F be used to encode informative user-specifie preference the objectives fi...., lu. which allows us to provide the best models customized for different users. can also be an non-informative measure that encourages, for example, the diversity of set of model parameters. In this
32
38

---

Under review as conference paper at ICLR 2022
34
case, optimizing in Pareto set gives set of diversified Pareto models that are representative of the whole Pareto set, from which different users can pick their favorite models during the testing time.
35
36
OPr-in-Pareto provides a highly generic and actionable framework for multi culti-objecctvv learning and opti- mization. However, efficient algorithms for solving OPT-in-Pareto have been largely lagging behind in deep learning where the objective functions are non-convex and non-linear. Although has not been formally studied, a straightforward approach is to apply manifold gradient descent on F in the Riemannian manifold formed by
37
36
40 the Pareto set (Hillermeier, 2001; Bonnabel, 2013). However, this casts prohibitive computational cost due to the need for eigen-computation of Hessian matrices of {f.). In the optimization and operation research
42 literature, there has been a body of work on OPT-in-Pareto viewing it as a special bi-level optimization
43 problem (Dempe, 2018). However, these works often heavily rely on the linearity and convexity assumptions
44 and are not applicable to the non-lineat and non-convex problems in deep learning; see for examples in Ecker
45 & Song (1994); Jorge (2005); Thach & Thang (2014); Liu & Ehrgott (2018); Sadeghi & Mohebi (2021) (just
46 to name a few). In comparison, the OPT-in-Pareto problem seems to be much less known and under-explored
47
in the deep learning literature.
48 In this work, we provide a practically efficient first-order algorithm for OPT-in-Pareto, using only gradient information of the criterion F' and objectives {4). Our method, named Pareto navigation gradient descent (PNG), iteratively updates the parameters following a direction that carefully balances the descent on F and {e.) such that it guarantees to move towards the Pareto set of { when it far away, and optimize F in a neighborhood of the Pareto set. Our method is simple, practically efficient and has theoretical guarantees.
49
50
51
52
53 In empirical studies, we demonstrate that our method works efficiently for both optimizing user-specific
54 criteria and diversity measures. In particular, for finding representative Pareto solutions, we propose an energy distance criterion whose minimizers distribute uniformly on the Pareto set asymptotically (Hardin & Saff. 2004), yielding principled and efficient Pareto set approximation method that compares favorably with recent works such as Lin et al. (2019); Mahapatra & Rajan (2020). We also apply PNG to improve the performance of JiGen (Carlucei et al., 2019b), multi-task learning approach for domain generalization, by using the adversarial feature discrepancy as the criterion objective.
55
56
57
58
59
60
Related Work There has been rising interest in MOO in deep learning, mostly in the context of multi-task learning. But most existing methods can not be applied to the general OPT-ii-Pareto problem. A large body of recent works focus on improving non-convex optimization for finding some model in the Pareto set, but cannot search for a special model satisfying a specific criterion (Chen et al., 2018; Kendall et al., 2018; Sener & Koltun, 2018; Yu et al., 2020; Chen et al., 2020; Wu et al., 2020; Fifty al., 2020; Javaloy & Valera, 2021). One exception is Mahapatra & Rajan (2020); Kamani et al. (2021), which searches for models in the Pareto 66 set that satisfy a constraint on the ratio between the different objectives. The problem they study can be viewed as special instance of OPT-in-Pareet However, their approaches are tied with special properties of the ratio constraint and do not apply to the general OPT-in-Pareto problem.
61
62
63
64
65
67
68
69 There has also been increasing interest in finding compact approximation of the Pareto set. Navon et al. (2020): Lin et al. (2020) use hypernetworks to approximate the map from linear scalarization weights to the corresponding Pareto solutions; these methods could not fully profile non-convex Pareto fronts due
70
72 to the limitation of linear scalarization (Boyd et al., 2004), and the use of hypernetwork introduces extra
73 optimization difficulty. Another line of works (Lin et al., 2019; Mahapatra & Rajan, 2020) approximate
74 the Pareto set by training models with different user preference vectors that rank the relative importance
75 of different tasks; these methods need good heuristic design of preference vectors, which requires prior
76 knowledge of the Pareto front. Ma et al. (2020) leverages manifold gradient to conduct a local random walk
77 on the Pareto but suffers from the high computational cost. Deist et al. (2021) approximates the Pareto set
78 by maximizing hypervolume, which requires prior knowledge for choosing good reference vector.
79 Multi-task learning can also be applied to improve the learning in many other domains including domain
80 generalization (Dou et al., 2019; Carlucci et al., 2019a; Albuquerque et al., 2020), domain adaption (Sun
2

---

Under review conference paper at ICLR 2022
81 al., 2019; Luo et al., 2021), model uncertainty (Hendrycks et al., 2019; Zhang et al., 2020; Xie al., 2021),
82 adversarial robustness (Yang & Vondrick, 2020) and semi semi-supervised learning (Sohn et al., 2020). All of
83 those applications utilize linear scalarization to combine the multiple objectives and it is thus interesting to apply the proposed OPT-in-Pareed framework, which we leave for future work.
84
2 BACKGROUND ON MULTI-OBJECTIVE OPTIMIZATION
85
86
We introduce the background on multi-objectivve optimization (MOO) and Pareto optimality. For notation, we denote by [m]] the integer set {1, 11.2.... m), and R, the set of non-negative real numbers. Let C {w E 14, 2in1 wi = 1] be the probability simplex. We denote by ||-Il the Euclidean norm.
87
88
89
Let A E R" be a parameter of interest (c.g., the weights in a deep neural network). Let ((0) .m (0)) be set of objective functions that want to minimize. For two parameters 8, 0' E R". we write e()) = 2(0") if (0) 2 ((0)) for all i E [m]] and write {(O) > e((') if E(O) > e(O' and
90
91
l(0)= # {. We say that 0 is Pareto dominated (or Pareto improved) by 0' if {()) > ((6"). We say that 0 is
92
Pareto optimal on a set θ C R,, denoted as E Par if there exists no 8' E θ such that (()) - e((').
98
94
The Pareto global optimal set p Parcto(R"" is the set of points (i.e., 0) which Pareto optimal on the whole domain R The Pareto local optimal set of e, denoted by Pt, is the set of points which are Pareto optimal neighborhood of itself:
95
96
p' {0 E R": there exists neighborhood No of 0, such that E Pareto(No))-
97
The (local or global) Pareto front is the set of objective vectors achieved by the Pareto optimal points, e.g.. the local Pareto front is F {L(0) A E } Because finding global Pareto optimum is intractable for non-convex objectives in deep learning, we focus on Pareto local optimal sets in this work; in the rest of the paper, terms like "Pareto set" and "Pareto optimum" refer to Pareto local optimum by default.
98
99
Pareto Stationary Points Similar to the case of single-objective optimization, Pareto local optimum implies a notion of Pareto stationarity defined as follows. Assume l is differentiable on IK", A point 0 is called Pareto stationary if there must exists a set of non-negative weights . Wm with Σm= wi = 1, such that a stationary point of the w-weighted linear combination of the objectives: Ea (0) = Σ i=1 (0). Therefore, the set of Pareto stationary points, denoted by P. can be characterized by
: =
g(0)
= min WECm
wi (0)1
where g(0) is the minimum squared gradient norm of la among all in the probability simplex C' on [m]. Because g(8) can be calculated in practice, it provides an essential way to access Pareto local optimality.
102
Finding Pareto Optimal Points A main focus of the MOO literature is to find (set of) Pareto optimal points. The simplest approach is linear scalarization, which minimizes lu for some weight w (decided, e.g., by the users) in Cm. However, linear scalarization can only find Pareto points that lie on the conver envelop of the Pareto front (see e.g.. Boyd et al., 2004), and hence does not give complete profiling of the Pareto front when the objective functions (and hence their Pareto front) are non-convex.
104
105
106
107
Multiple gradient descent (MGD) (Désidéri, 2012) is an gradient-based algorithm that can converge to a Pareto local optimum that lies on either the convex or non-convex parts of the Pareto front, depending on the initialization. MGD starts from some initialization 6g and updates A at the t-th iteration by
1 ||01
O1+1 f- O2 Et.,
arg mnax HERR
min (E.(0,)T [i[mm]
(2)
2
3

---

Under review conference paper at ICLR 2022
108 where & is the step size and U2 is an update direction that maximizes the worst descent rate among all objectives, since (B,) T = (f. (0, {v))/{ approximates the descent rate of objective & when 110 following direction v. When using a sufficiently small step size Ç. MGD ensures yield a Pareto improvement (i.e, decreasing all the objectives) on O, unless 0, is Pareto (local) optimal: this is because the optimization in
112
Equation (2) always yields minke[m] (0,) 24 S 0 (otherwise we can simply flip the sign of ez).
Using Lagrange strong duality, the solution of Equation (2) can be framed into
Ut = Σ Wiet Vl)(o))
where
1 = arg min (B) {was)
(3)
WEC
113 It is easy to see from Equation (3) that the set of fixed points of MDG (which satisfy is = 0) coincides with
114 the Pareto stationary set P
115 A key disadvantage of MGD, however, is that the Pareto point that it converges to depends on the initialization
and other algorithm configurations in a rather implicated and complicated way. It is difficult explicitly control MGD to make it converge to points with specific properties.
117
3 OPTIMIZATION IN PARETO SET
119 The Pareto set typically contains an infinite number of points. In the optimization in Pareto set (OPT-in- Pareto) problem, we are given an extra criterion function F(0) in addition to the objectives f, and we want to minimize in the Pareto set of l, that is,
121
min F(0). PEP'
For example, one can find the Pareto point whose loss vector ((0) is the closest given reference point 123 r E RT by choosing F(0) |E(0) - r|| We can also design F to encourages (()) to be proportional r,
124 i... L(O) x r; constraint variant of this problem was considered in Mahapaira & Rajan (2020).
125 We can further generalize OPT-in-Pareto allow the criterion F depend on an ensemble of Pareto points [ ..., 0x) jointly, that is,
min ENE
F(O 0n).
(5)
For example, if F(61.... ... fy) measures the diversity among {0:) then optimizing it provides set of diversified points inside the Pareto set Pt, An example of diversity measure is
F(O1....,0NN = F((E(O))..... e(ON)),
with
F((e,...., Σ ||e: - 2 e,11 (
(6)
where E is known as energy distance in computational geometry, whose minimizer can be shown to give an uniform distribution asymptotically when N - do (Hardin & Saff, 2004). This formulation is particularly useful when the users' preference is unknown during the training time, and we want to return an ensemble of models that well cover the different areas of the Pareto set to allow the users to pick up a model that fits their needs regardless of their preference. The problem of profiling Pareto set has attracted line of recent works (e.g., Lin et al., 2019; Mahapatra & Rajan, 2020; Ma et al., 2020; Deist et al., 2021), but they rely on specific criterion heuristics and do not address the general optimization of form Equation (5).
128
130
132
133
134
Manifold Gradient Descent One straightforward approach to OPT-in-Pareto is to deploy manifold gradient descent (Hillermeier, 2001; Bonnabel, 2013), which conducts steepest descent of F(0) in the Riemannian manifold formed by the Pareto set P Initialized at 0g E P*, manifold gradient descent updates O, at the t-th iteration along the direction of the projection of V FO.)) on the tangent space T(0.) at O, in P
136
137
0.4 02 <Proj (VF(()))
4

---

Under review conference paper at ICLR 2022
138 By using the stationarity characterization in Equation (I), under proper regularity conditions, one can
show that the tangent space 'I ((;;) equals the null space of the Hessian matrix V2k., (0+), where wy
140
arg wec & (0=)ll- However, the key issue of manifold gradient descent the high cost for calculating this null space of Hessian matrix. Although numerical techniques such as Krylov subspace iteration (Ma
142
et al., 2020) or conjugate gradient descent (Koh Liang, 2017) can be applied, the high computational cost
(and the complicated implementation) still impedes its application in large scale deep learning problems. See
144
Section for discussions on other related works.
4 PARETO NAVIGATION GRADIENT DESCENT FOR OPT-IN-PARETO
145
We introduce our main algorithm, Pareto Navigating Gradient Descent (PNG), which provides practical approach to OPT-iin-Pareto, For convenience. we focus on the single point problem in Equation (4) in the presentation. The generalization to the multi-point problem in Equation (5) is straightforward. We first introduce the main idea and then present theoretical analysis in Section 4.1.
148
Main Idea We consider the general incremental updating rule of form
0c+1 0g Eur,
where is the step size and v2 is update direction that we shall choose achieve the following desiderata balancing the decent of {& and F:
151
i) When 6, is far away from the Pareto set, we want to choose 2 to give Pareto improvement to 8,, moving it towards the Pareto set. The amount of Pareto improvement might depend on how far 0g is to the Pareto set.
158
ii) If the directions that yield Pareto improvement are not unique, direction that decreases F(0) most.
choose the Pareto improvement
155
iii When 0, is very close to the Pareto set, e.g., having small g(6), want to fully optimize F(A).
We achieve the desiderata above by using the v, that solves the following optimization:
[VF(0.) - -|l2 s.t. Vol,(0.) 2 st, Vi [ml]
1/- = arg min eElt
(7)
where we want to be as close TO VF(O.) as possible (hence decrease F most), conditional on that the decreasing rate Vol, (0.) o, of all losses E, are lower bounded by a control parameter d.. A positive de enforces that Vo, (0) it is positive for all é, hence ensuring Pareto improvement when the step size is sufficiently small. The magnitude of o, controls how much Pareto improvement we want to enforce, so we may want to gradually decrease de when move closer to the Pareto In fact, varying de provides an intermediate updating direction between the vanilla gradient descent on and MGD on (L:):
158
160
162
i) If 0: -o, have 1/2 ((t)) and it conducts pure gradient descent F without considering {4:)-
184
ii) or + +oo, then 1/ approaches to the MGD direction of {4,} in Equation (2) without considering F.
In this work, propose to choose o, based on the minimum gradient norm g(ft) in Equation (1) surrogate indication of Pareto local optimality. In particular, we consider the following simple design:
if g(t)) S e, di (O. if g > e,
(8)
165 where e is a small tolerance parameter and 0₁ is positive hyper-parameter When g(O,) > e, we set di to be proportional g0,), ensure Pareto improvement based on how far 0, is Pareto set. When g(0)) e, 167 we set de -oo which "turns off" the control and hence fully optimizes F(0).
In practice, the optimization in Equation (7) can be solved efficiently by its dual form follows.
5

---

Under review conference paper at ICLR 2022
Theorem
The solution ot of Equation (7), if exists, has a form of
m 1/ = VF(0.) Σ
(9)
with
(1, the solution of the following dual problem
m ] IVF((0)) + Σ ( Σ Azoe.
m
max AER
(10)
169
The optimization in Equation (10) can be solved efficiently for a small m (e.g, m S 10), which is the case for typical applications. We include the details of the practical implementation in Appendix B.
170
171
4.1
THEORETICAL PROPERTIES
We provide theoretical quantification on how PNG guarantees to i) move the solution towards the Pareto set (Theorem 2); and ii) optimize F' in a neighborhood focus the continuous time limit of PNG, which yields differentiation equation dd,- = dtdt with et defined in Equation (7), where E R+ is a continuous integration time.
173
Pareto set (Theorem 3). simplify the result and
highlight the intuition,
175
Assumption
Let {0,: E R be solution of d0, = -u,t with v, in Equation (7); dx in Equation (8); e > 0: and 0; 2 Vt E R4+ Assume F and are continuously differentiable on R", and lower bounded with F infaer (()) oo and E == infeeR (6) oc. Assume suPpeR" | S.
178
Technically, d0, - v. is piecewise smooth dynamical system whose solution should be taken in the Filippov sense using the notion of differential inclusion (Bernardo et al., 2008). The solution always exists under mild regularity conditions although it may not be unique. Our results below apply to all solutions.
180
Pareto Optimization on l We now show that the algorithm converges to the vicinity of Pareto set quantified by notion of Pareto closure. For 2 0, let P. be the set of Pareto e-stationary points: P. {0 IR" g(0) < e). The Pareto closure of set Pe, denoted by Pa is the set of points that perform worse than at least one point in Pe, that is,
Pe Uoep, (0),
0 (6' E R =0)=)(())
182 Therefore, P. is better than or at least as good as P. terms of Pareto efficiency.
Theorem 2 (Pareto Improvement l). Under Assumption 1, assume 0g & Per and te is the first time when Or E Pa. then for any time < ler
d
min g(0.) (minse[m)[L ft) 00
(,())) -ag(())) dt
So a,,s
Therefore, the update yields Pareto improvement on l when 0, & Pe and o.g(0.) 0.
Further, if J a,ds +0, then for any there exists finite time RR_ which the solution enters Pe and stays within P. afterwards, that is, we have Ot, E P. and 02 Peror any 2 le-
185
Here guarantee that 0g must enter P. for some time (in fact infinitely often), but it is not confined in P.- On the other hand, 0r does not leave Pe after it first enters P. thanks to the Pareto improvement property.
187
show that PNG finds local optimum of F inside the Pareto closure P. in approximate sense. We first show that a fixed point of the algorithm that is locally convex on and & must be local optimum of F in the Pareto closure of (Ø). and then quantify the convergence of the algorithm.
Optimization F We
189
6

---

Under review conference paper at ICLR 2022
191
Lemma 1.
Under Assumption 1, assume 0₂ & Pe is a fixed point of the algorithm, that is, d6. at - 4 0,
192 and F, l are convex in neighborhood 6,, then 8₁ is a local minimum of F in the Pareto closure { that is,
183
there exists a neighborhood of 9, in which there exists no point I' such that F(0)) < F(0e) and {((') = E E
194
On the other hand, if 0g E Pe. we have U, = (0t), and hence a fixed point with d0, unconstrained local minimum of F when F is locally convex on Oz.
or
Utt = is an
Theorem 3. Let > and assume == sup)) E P.} < -00 and supizo at < cc. Under Assumption I, when we initialize from 0n E Pe. we have
d0 2
F(Oa) F
I as (asIe + @v ds. + t
min =
ds
t
In particular, we have a₁ const, then m |d00//s/] = (
If Jo at < +00 some 2 1, we have min,e(o.1) ||d0./ds|] 011/t /gc/t//1).
197
198
Combining the results in Theorem 2 and 3, we can see that the choice of sequence fas: E R. controls how fast want to decrease l vs. F. Large a, yields faster descent f, but slower descent on F. Theoretically, using a sequence that satisfies f o,dl = +o and f a7 dl < +oo for some > 1 allows us to ensure that both [l g(O,) and min.e]o.4 ||d0/ ddsl converge to zero. If we use constant sequence at a, it introduces an ((ex//e)) term that does not vanish as ! + +oc. However, we can expect that g, is small when 6 small for well-behaved functions. In practice, we find that constant ar works sufficiently well.
200
203
204
5
EMPIRICAL RESULTS
205
We introduce three applications of OPT-in- PPr-eto with PNG: Singleton Preference, Pareto approximation and improving multi-task based domain generalization method. We also conduct additional study on how the learning dynamies of PNG changes with different initialization and apper-parameters (a; and e), which are included in Appendix C.3. Other additional results that are related to the experiments in Section 5.1 and 5.2 and are included the Appendix will be introduced later in their corresponding sections.
207
209
210
5.1
FINDING PREFERRED PARETO MODELS
We consider the synthetic example used in Lin et al. (2019); Mahapatra & Rajan (2020), which consists of two losses: { 1 exp(- ||0 m|l²) and (2) 1 exp(e ||0 + nll²), where r) = n 11/ and n 10
212
213
is dimension of the parameter 0.
214
Ratio-based Criterion We first show that PNG can solve the search problem under the ratio constraint of objectives in Mahapatra & Rajan (2020), i... finding a point 0 E p ni with s = (0. .T (0) = r2(2(0)
215
mm (0)). given some preference vector r = /r...., ]m We apply PNG with the non-unifornity score defined in Mahapatra & Rajan (2020) as the criterion, and compare with their algorithm called exact Pareto optimization (EPO). We show in Figure ((a)-(b) the trajectory of PNG and EPO for searching models with different preference vector r, starting from the same randomly initialized point. Both PNG and EPO converge to the correct solutions but with different trajectories. This suggests that PNG is able to achieve the same functionality of finding ratio-constraint Pareto models Mahapatra & Rajan (2020); Kamani et al. (2021) do but being versatile to handle general criteria. We refer readers to Appendix C. for more results with different choices of hyper- parammtrrseserrs and the experiment details.
216
217
216
220
222
224
Other Criteria We demonstrate that PNG is able to find solutions for general choices of F. We consider the following designs of F: 1) weighted & distance w.r.t. reference vector E B.,, that is, (()
7

---

Under review conference paper at ICLR 2022
Lask pICAE
proieencc
widiited datanes
outrolax oninee
Fareto FooG
Practo Food
PNG
Pireto Frort
Parnto Poont
PSG
PVG
Tirget
Trrge
Figure I: (a)-(b): the trajectory of finding Pareto models that satisfy different ratio constraints (shown in different colors) on the two objectives &,, l2 using EPO and PNG; we can see that PNG can achieve the same goal as EPO (with different trajectories) while being a more general approach. (c)-(d): the trajectory of finding Pareto models that minimize the weighted distance and complex cosine criterion using PNG. The green dots indicate the converged models. We can see that PNG can successfully locate the correct Pareto models that minimize different criteria.
226
E (4,(0) r.) (r)²//ry: and 2) complex cosine: in which F is a complicated function related to the cosine of task objectives, i.e., Fess cos (= (0) r1)/2) + (cos(T (((02) r2)) + 1)2. Here the weighted &z distance can be viewed as finding Pareto model that has the losses close to some target value r, which can be viewed as alternative approach to partition the Pareto set. The design of complex cosine aims test whether
227
228
229
230
PNG is able to handle very non-linear criterion function. In both cases, we take 71 [0.2, 0.4, 0.6, 0.8) and
231
22 1 r1- We show in Fig ((c)-(d) the trajectory of PNG. As we can see, PNG is able to correctly find the
optimal solutions of OPT-in-Pareto. We also test PNG on a more challenging ZDT2-variant used in Ma et al. (2020) and larger scale MTL. problem (Liu et al., 2019). We refer readers Appendix C.1.2 and C.1.3 for
233
the setting and results.
235
5.2
FINDING DIVERSE PARETO MODELS
Setup We consider the problem of finding diversified points from the Pareto by minimizing the energy distance criterion in Equation (6). We use the same setting as Lin et al. (2019); Mahapatra & Rajan (2020). We consider three benchmark datasets: (1) MultiMNIST, (2) MultiFashion, and (3) MultFFshhonnMNNIST. For each dataset, there are two tasks (classifying the top-left and bottom-right images). We consider LeNet with multihead and train N 5 models to approximate the Pareto set. For baselines, we compare with linear scalarization, MGD (Sener& & Koltun, 2018), and EPO (Mahapatra & Rajan, 2020). For the MGD baseline,
237
238
239
240
241
242
we find that naively running it leads to poor performance as the learned models are not diversified and thus we initialize the MGD with 60-epoch runs of linear scalarization with equally distributed preference weights and
243
244
runs MGD for the later 40 epoch. We refer the reader to Appendix C.2.1 1 for more details of the experiments.
Metric and Result We measure the quality of how well the found models {0I.... 0N) approximate the Pareto set using two standard metrics: Inverted Generational Distance Plus (IGD+) (Ishibuchi et al., 2015) and hypervolume (HV) (Zitzler & Thiele, 1999); see Appendix C.2.2 for their definitions. We run all the methods with independent trials and report the averaged value and its standard deviation in Table 1. We report the scores calculated based on loss (cross-entropy) and accuracy on the test set. The bolded values indicate the best result with p-value less than 0.05 (using matched pair t-test). In most cases, PNG improves the baselines by large margin. We include ablation studies in Appendix C.2.3 and additional comparisons with the second-order approach proposed by Ma et al. (2020) in Appendix C.2.4.
246
248
250
252
5.3
APPLICATION TO MULTI-TASK BASED DOMAIN GENERALIZATION ALGORITHM
254
JiGen (Carlucci et al., 2019b) learns a domain generalizable model by learning two tasks based on linear scalarization, which essentially searches for model in the Pareto set and requires choosing the weight of
8

---

Under review conference paper at ICLR 2022
Loss
Acc
Data
Method
HVT (10-2)
IGD+J (10-2)
HVT (10-2)
IGD+| (10
Linear
7.481
0.04
0.002
0.036 0.0084
MGD
7.69 1 0.10
0.001
9.27 1: 0.023
0.0078 + 0.0010
MultiMMNIST
EPO
7.87+0.16
0.029
9.17 + 0.032
0.065 + 0.018
PNG
7.86+0.11
0,042+0.012
9.39++0.036
0.0056+0.0022
Linear
0.38
0.059
0.03
0.019
0.064 + 0.012
MGD
0.42 0.064
0.046
0.016
4.77 + 0.019
0.023
Multi-Fashion
EPO
0.36 0.058
0.31 0.11
4.78 0.030
0.21 +: 0.020
PNG
0.47
0.016=0,0022
4.81+00021
0.023=000031
Linear
5.01 0.057
0.167 0.054
8.46 + 0.046
0.110 + 0.035
MGD
5.09 0.069
0.060 0.029
8.40 0.045
0.04
Fashion-MNIST
EPO
4.60 + 0.166
0.233 0.054
8.12 0.041
0.385 + 0.077
PNG
5.27+-0055
0.048+0.027
8.53+
0.046+0.022
Table 1: Results of approximating the Pareto set by different methods three MNIST benchmark datasets. The numbers in the table are the averaged value and the standard deviation. Bolded values indicate the statistically significant best result with p-value less than 0.5 based matched pair t-test.
PACS
art paint
cartoon
sketches
photo
Avg
D-SAM
0.7733
0.7243
0.7783
0,9530
0.8072 O. 0.7905
DeepAll
0.7785
0.7486
0.6774
0,9573
JiGien
0.8009
0.004
0.7363
0.007
0.7046 E 0.013
0.9029:000002
0.8012 0.002
JiGen+adv
0.7923 0.006
0.7402
0.004
0.7188 + 0.005
0.9617 + 0.001
0.8033 0.001
JiGen+PNG
0.8014+0.005
0.7538+00.00
0.7222+0.006
0.9627++0.002
0.8100=0.005
Table 2: Comparing different methods for domain generalization PACS using ResNet-18 18. The values in table are the testing accuracy with its standard deviation. The bolded values are the best models with p-value less than 0.1 based on match-pair t-test.
256
linear scalarization carefully. It is thus natural to study whether there is better mechanism that dynamically adjusts the weights of the two losses so that we eventually leam a better model. Motivated by the adversarial feature learning (Ganin et al., 2016). we propose to improve JiGen such that the latent feature representations of the two tasks are well aligned. This can be framed into an OPT-in-Pareth problem where the criterion the discrepancy of the latent representations (implemented using an adversarial discrepancy module in the network) of the two tasks. PNG is applied to solve the optimization. We evaluate the methods on PACS (Li et al., 2017), which covers 7 object categories and 4 domains (Photo, Art Paintings, Cartoon, and Sketches), The model trained on three domains and tested on the rest of them. Our approach is denoted as JiGen+PNG and we also include JiGen + adv, which simply adds the adversarial loss as regularization and two other baseline methods (D-SAM (D' Innocente & Caputo, 2018) () and DeepAll (Carlucei et al., 2019b)). For the three run 3 independent trials and for the other two baselines, we report the results in
257
258
259
260
261
263
265
266
JiGen based approaches, their original papers. Table 2 shows the result using ResNet-18, which demonstrates the improvement by the application of the OPT-in-Pareto framework. We also include the results using AlexNet in the Appendix. We refer readers to Appendix C.4 for the additional results and more experiment details.
267
268
269
6
CONCLUSION
270
271
This paper studies the OPT-in- Parino, a problem that has been studied operation research with restrictive linear convexity assumption but largely under-explored in deep learning literature, in which the objectives are non-linear and non-convex. Applying algorithms such as manifold gradient descent requires eigen- 273
computation of the Hessian matrix at each iteration and thus can be expensive. We propose a first-order approximation algorithm called Pareto Navigation Gradient Descent (PNG) with theoretically guaranteed descent and convergence property to solve iPT-iin-Preeo..
275
9

---

Under review conference paper at ICLR 2022
277
REFERENCES
Isabela Albuquerque, Nikhil Naik, Junnan Li, Nitish Keskar, and Richard Socher. Improving out-of- distribution generalization via multi-task self-supervised pretraining, arXiv preprint 2003s 2020.
279
280
281
Mario Bernardo, Chris Budd, Alan Richard Champneys, and Piotr Kowalczyk. Piecewise-smoolh dynamical systems: theory and applications, volume 163. Springer Science & Business Media, 2008
283
Silvere Bonnabel. Stochastic gradient descent on riemannian manifolds. IEEE Transactions on Automatic Control, 580):2217-2229, 2013.
285
Stephen Boyd, Stephen Boyd, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
296
Fabio M. Carlucci, Antonio D' D'Innocente, Silvia Bucci, Barbara Caputo, and Tatiana Tommasi. Domain generalization by solving jigsaw puzzles. In Proceedings of the IEEÉ/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2019a.
288
289
290
Fabio M Carlucci, Antonio D' D'Innccente, Silvia Bucci, Barbara Caputo, and Tatiana Tommasi. Domain generalization by solving jigsaw puzzles. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 2229222222222222 2238, 2019b.
292
Zhao Chen, Vijay Badrinarayanan, Chen-Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing deep multitask networks. In International Conference on Machine Learning, pp. 794 803. PMLR, 2018.
284
296
Zhao Chen, Jiquan Ngiam, Yanping Huang, Thang Luong, Henrik Kretzsehmar, Yuning Chai, and Dragomir Anguelov. Just pick a sign: Optimizing deep multitask models with gradient sign dropout. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2050-2050. Curran Associates, Inc., 2020. URL https: https:://roooeeeeee ppwooeedodddneeeeoooooooooe ings. neurips.co/ wttpse/ccpppppeeeeeeeeeeeeeeeeee /2000 110022//LLL111000777744448088000
297
286
300
Paper Pap.r.pdf..
301
Timo M Deist, Monika Grewal, Frank JWM Dankers, Tanja Alderliesten, and Peter AN Bosman. Multi-objective learning to predict pareto fronts using hypervolume maximization. arXiv preprint
302
arXiv:2 2021.
304
Stephan Dempe. Bilevel optimization: theory, algorithms and applications. TU Bergakademie Freiberg, Fakultät für Mathematik und Informatik, 2018.
305
Sean-Antoine Désidéri. Multiple-gradient descent algorithm (mgda) for multiobjective optimization. Comptes
307
Rendus Mathematique, 350(5-6):313-318, 2012.
Qi Dou, Daniel C Castro, Konstantinos Kamnitsas, and Ben Glocker. Domain generalization via model- agnostic learning of semantic features. arXiv preprint 11X1v:1910.13580, 2019.
309
310
Antonio D' IInnccente and Barbara Caputo. Domain generalization with Nomain-specifee aggregation modules. In German Conference on Puttern Recognition, pp. 187-198. Springer, 2018
311
312
Joseph G Ecker and Jung Hwan Song. Optimizing a linear function over an efficient set. Journal of 313
Optimization Theory and Applications, 83(3):541-566 1994.
314
Christopher Fifty, Ehsan Amid, Zhe Zhao, Tianhe Yu, Rohan Anil, and Chelsea Finn. Measuring and harnessing transference in multi-task learning. arXiv preprint 200:2000..541... 2020.
10

---

Under review conference paper at ICLR 2022
316
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In International conference on machine learning, pp. 1180-1189. PMLR, 2015.
317
318
Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, François Laviolette, Mario March, and Victor Lempitsky. Domain-adversaria training of neural networks. Journal of Machine Learning Research, 17(59):1 33, 2016. URL http::/ /jmlr. wtt/oooggeaeeee..oo.ee pwtppps/v1//1--22222
319
320
html.
321
DP Hardin and EB Saff. Discretizing manifolds via minimum energy points. Notices of the AMS, 51(10): 1186-1194 2004.
322
323
Dan Hendryeks, Mantas Mazeika, Saurav Kadavath, and Dawn Song. Using self self-supervised learning can improve model robustness and uncertainty. H. Wallach, H. Larochelle, A. Beygelzimer, F, d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL httpa: http:::pp/prooceeiiini wwwrips...... cc/ httpp///ccccppppee/eeee// 20t/////0119//11e/ www.rrieeeennneenneeo.oo..mm...e pdf..
324
326
328
Claus Hillermeier. Generalized homotopy approach to multiobjective optimization. Journal of Optimization Theory and Applications, 110(3)5557-583 2001.
329
320
Hisao Ishibuchi, Hiroyuki Masuda, Yuki Tanigaki, and Yusuke Nojima. Modified distance calculation in generational distance and inverted generational distance. In International conference on evolutionary multi-criterion optimization, pp. 110-125. Springer, 2015.
331
332
333
Adrián Javaloy and Isabel Valera. Rotograd: Dynamic gradient homogenization for multi-task learning. arXiv preprint N.iv:2203.02633. 2021.
334
335
Jesús M Jorge. A bilinear algorithm for optimizing a linear function over the efficient set of a multiple objective linear programming problem. Journal of Global Optimization, 31(1):1-16, 2005.
336
397
Mohammad Mahdi Kamani, Rana Forsati, James Z Wang, and Mehrdad Mahdavi. Pareto efficient fairness in supervised learning: From extraction to tracing. arXiv preprint 100v:2210.01134, 2021.
338
339
Alex Kendall, Yarin Gal, and Roberto Cipolla. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7482-7491, 2018.
340
341
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning, pp. 1885-1894. PMIR, 2017.
348
344
Da Li, Yongxin Yang. Yi-Zhe Song, and Timothy M. Hospedales. Deeper, broader and artier domain generalization. Proceedings of the IEFE International Conference on Computer Vision (ICCV), Oct 2017.
345
347
Da Li, Yongxin Yang, Yi-Zhe Song, and Timothy Hospedales. Learning to generalize: Meta-learning for domain generalization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 32, 2018a.
319
Ya Li, Xinmei Tian, Mingming Gong, Yajing Liu, Tongliang Liu, Kun Zhang, and Dacheng Tao. Deep domain generalization via conditional invariant adversarial networks. In Proceedings of the European Conference Computer Vision (ECCV), pp. 624-639, 2018b.
351
353
Xi Lin, Hui-Ling Zhen, Zhenhua Li, Qingfu Zhang, and Sam Kwong. Pareto multi-task learning. arXiv preprint arXiv: 1912, 12854, 2019.
11

---

Under review conference paper at ICLR 2022
355
Xi Lin, Zhiyuan Yang, Qingfu Zhang, and Sam Kwong. Controllable pareto multi-task learning. arXiv preprint arXiv:2010.06313, 2020.
356
357
Shikun Liu, Edward Johns, and Andrew J Davison. End-to-end multi-task learning with attention. In
358
Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1871-1880,
359
2019.
380
Zhengliang Liu and Matthias Ehrgott. Primal and dual algorithms for optimization over the efficient set.
361
Optimization, 67(10);1661-166) 2018.
362
Xiaoyuan Luo, Shaolei Liu, Kexue Fu, Manning Wang, and Zhijian Song. learnable self super--eee task
for unsupervised domain adaptation on point clouds. arXiv preprint arXiv:2104.05164 2021.
384
Pingchuan Ma, Tao Du, and Wojeiech Matusik. Efficient continuous pareto exploration in multi-task learning.
365
In International Conference on Machine Learning, pp. 6522-6531. PMLR, 2020.
366
Debabrata Mahapatra and Vaibhav Rajan. Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization. In International Conference Machine Learning, pp. 6597-6607. PMLR, 2020.
388
389
Aviv Navon, Aviv Shamsian, Gal Chechik, and Ethan Fetaya. Learning the pareto front with hypernetworks. arXiv preprint arX1v:2010.04104, 2020.
Javad Sadeghi and Hossein Mohebi. Solving optimization problems over the weakly efficient set. Numerical Functional Analysis and Optimization, pp. 1-33, 2021.
372
373
Ozan Sener and Vladlen Koltun. Multi-task learning as multi-objective optimizationn... S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Pro- cessing Systems, volume 31. Curran Associates, Inc., 2018. URL https: http:::://////pepppeeeeeee www.innnn..nnnnnneeeeeeeeeeeeure neurips. Paper... pdf.
375
376
cc cc/paper/2018/ http:///////..ee//2aaaaaaaaeeeee aeeaaaaaaeee15533333333300000
Nathan Silberman, Derek Hoiem, Pushmeet Kohli, and Rob Fergus. Indoor segmentation and support inference from rgbd images. In European conference on computer vision, pp. 746-760. Springer, 2012.
378
379
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi- supervuper learning with consistency and confidence. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 596-608. Cur- ran Associates, Inc., 2020. URL https: ptwce//ooccedcceeoooooooo ngs. www.nnnrissssnnoommmmmmmmmmmm pwtpppppp////////////c/ /fiee/ Pat3333--PPeppee .dd..
380
381
382
384
385
Yu Sun, Eric Tzeng, Trevor Darrell, and Alexei A Efros. Unsupervised domain adaptation through self- supervision. arXiv preprint arXiv: /1855, 2019.
Phan Thien Thach and TV Thang. Problems with resource allocation constraints and optimization over the efficient set. Journal of Global Optimization, 58(3):481-495, 2014.
386
389
Sen Wu, Hongyang R. Zhang, and Christopher Ré. Understanding and improving information transfer in multi-task learning. In International Conference Learning Representations, 2020. URL https: / / /pppneevieww...e net/ / forum? seiidddylkksxa..n
391
392
Sang Michael Xic, Ananya Kumar, Robbie Jones, Fereshte Khani, Tengyu Ma, and Percy Liang. In-n-out: Pre- training and self-training using auxiliary information for -uitt--distiibution robustness. In International Conference on Learning Representations, 2021. URL https: / oppnreveeeeeeeeeeeeeeeeeeeeeeeee ew. net. forum?id= jznizqvr15J.
394
12

---

Under review conference paper at ICLR 2022
396
Junfeng Yang and Carl Vondrick. Multitask learning strengthens adversarial robustness. 2020.
387
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gra- dient surgery for multi-task learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp- 5824-5836 Cur- Associates, Inc., 2020. URL https: pproceeii/so neurips ccc http/ppppee220000 /tteer//22//////// file/ Ee78a8acf5fda www.9ee0000022200-0------
399
401
402
Linfeng Zhang, Muzhou Yu, Tong Chen, Zuoqiang Shi, Chenglong Bao, and Kaisheng Ma. Auxiliary training: Towards accurate and robust models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 372-381, 2020.
403
404
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.
406
13

---

Under review conference paper at ICLR 2022
407 A
THEORETICAL ANALYSIS
Theorem [Dual of Equation (7)) The solution of Equation (7), if it exists, has form of
m
24 = VF(0.) N VL((O))
with 1 the solution of the following dual problem
VF(00) + Σ A ve.)).
X
AER
2
where Be is the set of nonnegative m-dimensional vectors, that is, R () Rm A 2 0, vi [m]]-
409
Proof. By introducing Lagrange multipliers, the optimization in Equation (7) is equivalent to the following minimax problem:
410
min max VER" XER" 2
[VF(0)) - 0112
-112 + Σ
A ( (Z.())
t=1
With strong duality of convex quadratic programming (assuming the primal problem is feasible), we can exchange the order of min and max, yielding
max
+(A) = min vER"
1 IVF((.) v/2
Aa (o: V((0))
XERT
is easy that the minimization w.r.t. v is achieved when 412 ingly, the (A) has the following dual form:
VF((.)) E A (o.)). Correspond-
m
VF(O.) + Σ (.
AER 2
i=1
This concludes the proof.
Theorem [Pareto Improvement on E]
Under Assumption 1, assume Og & Pe. and to is the first time
when O2, Pe, then for any time & < ter
d de (((0,) S (0.())).
min g(O.) < mingg[m:(es(0))) (e:(0)) fT) (E(0,
So aa,
414 Therefore, the update yields Pareto improvement on l when Og & Pe and ong(O.) > O.
415 Further, if Jo a,ds +o, then for any > e, there exists a finite time t, E R_ on which the solution enters
416 Pe and stays within P. afterwards, that is, we have tr, E Pe and 0, E Per any 2 te.
Proof. i) Whent ter we have g(O.) > e and hence
d
(0.)) Ve,(0)) 5 - -baa=))))))))) -0ng(0)).
(11)
dt
417 where we used the constraint of (8,) 0 2 Φi in Equation (7). Therefore, we yield strict decent on all the losses (4,) when (0,) > 0.
14

---

Under review conference paper at ICLR 2022
ii) Integrating both sides of Equation (11):
min g(O)) < Lo (ag(0.))ds sE[0,4]
I (((0)) (:(O.)
((00) 8" So a,ds
So a,ds
So adds
419 This yields the result since it holds for every E [m]]
420 So a,dt +oc, then we have min ((a)) + when t +00. Assume there exists an c > c, such that Og never enters Pa finite I. Then we have g(0,) for R4, which contradicts with mi g(0.) - 0.
422
ii Assume there exists finite time t' (te. +oo) such that 0y Pe. Because e and g is continuous, Pa is in the interior of P. S P.. Therefore, the trajectory leading to Oy of P. must pass through P. Pe at some
425 point, that is, there exists a point t" [te, t'), such that {0.: t E [t", [t]] & Pe. But because the algorithm can
426 not increase any objective l, outside of Pe. we must have 2(0x) 3 E(Oe)), yielding that O2 E [0pr} S Pe
427
where [0.r) is the Pareto closure of {0."} }; this contradicts with the assumption.
Lemma 1
Under Assumption 1. assume 0, & Pe is fixed point of the algorithm, that is, d8g U 0, and F. are corvex in a neighborhood 8,, then 9, is local minimum of F in the Pareto closure {0:}, that is. there exists neighborhood of 0, in which there exists point 6' such that F(0") F(0,) and
429
431 E(0') 3 E(0,).
Proef. Note that minimizing F in {0.} can be framed into a constrained optimization problem:
min F(0) 8.1. (0) S (0.),, Vi E [m]]
In addition, by assumption, 0 = 0, satisfies vy- = VF(0,) + (e,(0) = 0, which is the KKT stationarity condition of the constrained optimization. also obvious to check that Og satisfies the feasibility and slack condition trivially. Combining this with the local convexity assumption yields the 435 result
432
433
434
Theorem 3 [Optimization of F] Let > and assume ge == supo(o(0) 0 P... < to0 and sup:20 ag < oc. Under Assumption when we initialize from Og E Pe. we have
d0
F(On) - F + I (a + cv)c)) ds.
min sE
ds
t
(1/t+ | av 437 If Jo a7 +00 for some y 2 1, we have min.e(o.1) [|d0,/dst O(1/t ////t
436 In particular, we have = const, then eo... |dll/ds||² 0
Proof. i) The slack condition of the constrained optimization in Equation (7) says that d (V::(O.)T et - Φi) 0, Vi [m].
(12)
This gives that
T
m
A (e(())) 12 VF((.)) Σ
VF(()) or
//pluggin Equation (12).
(13)
15

---

Under review conference paper at ICLR 2022
If 0g & Pe, we have o, (rg(Or) and this gives
d
d0
2
dt F(0.) -FF((.)) 11 A
a.g(()))
dt
0g is in the interior of Pe. then we run typical gradient descent of F and hence has
F(O.) - 11xel d0. dt
dt
If 0, is on the boundary of Pe, then by the definition of differential inclusion, d0/dt belongs to the convex hull of the velocities that it receives from either side of the boundary, yielding that
d F(O.)
d0, de
d0
where 3 E [0, 1]. Combining all the cases gives
d0.
2
m
F(O.)
+ Σ (g
dt
ct
Integrating this yields
d0, ds
d0
F(0o) F
+ J. Σ
min =
-
ds S
0
ds
t
F(Oo) - F
+ { Os (aage + cv ds,
b
where the last step used Lemma 2 with agg(0e):
(0,0ng(0)) (0.) + can conV g0,) ozg. + cot D
and here used g(0,) S ge because the trajectory is contained in P. following Theorem 2.
439 The remaining results follow Lemma 4.
A.0.1
TECHNICAL LEMMAS
Lemma 2. Assume Assumption holds. Define g(0) = min EE wi (e;(() where Cm the probability simplex [m]. Then the Vi and Xi defined in Equation (7) and Equation (10), we have
Ar.g(0.) S max (or covo((0))) 0).
441 Proof. The slack condition of the constrained optimization in Equation (7) says that
A1.1 (VL,(0) et - Φt) 0, Vi E [m]. Sum the equation over E [m] and note that 04 = VF(H:) + Em Ar, (o,)). We get
N vE,(0))
Σ N (E(1)))
VF(0) Σ
X 0.
(14)
16

---

Under review conference paper at ICLR 2022
Define
Σ A (O,)
A
A
9t - g(0.) = min
Σ wi Ve;(0s)
Then it is easy to see that xa X3ge. Using Cauchy-Schwar inequality,
m
m Σ
Σ
Xr. V(((1)
VF(0.) $ |VF(O))
X Ve,(0)
S Sc/or,
where used [VF())))l s b Assumption 1. Combining this with Equation (14), we have
xt destel S SevIr.
Applying Lemma yields the result.
Lemma 3. Assume Φ E IR, and x, X, 9 E RR are non-negative real numbers and they satisfy
1 Aol S e/Ex
x x2 X2.
443
Then we have Ag < max(0. Φ + c/g).
Proof. Square the first equation, we get
f(x) = (x 10) - -c²r S
where f is quadratic function. To ensure that f(x) < 0 has solution that satisfies Xag, need
have f()29) I O, that is,
((A3))((2²g = - Aσ)² 223g So.
444 This can hold under two cases:
445 Case 1: À = 0;
446 Case Ayg Φ1 S CvD, and hence - S Ag S o
Under both case, we have
Ag S max -/0)-
447
Lemma 4. Let {ax: t E [R4) C R4 be non-negative sequence with A == ajdt)) where 7 2 1, and = sup, ai < cc. Then we have
1 (( (a + +a.) ds < (B+ 1)
i.
Proof. Let --. that 1/m 1/7 1. We have by Holder's inequality,
[ adds s (f a3ds))
1/4 ( 1'dss) (f(raa))
1/n
S A/ AL
and hence
/ ag) ds < B+1 1
a.ds < (B + 11
17

---

Under review conference paper at ICLR 2022
Algorithm 1 Pareto Navigating Gradient Descent
I: Initialize fy; decide the step size &, and the control function & in Equation (8) (including the threshold
>> 0 and the descending rate {at)).
2: for iteration do
B.t1 t 01 Evr,
Vy = VF(O.) + Σ AL (2,(
(15)
where A = 0, vi E [m] if g(O,) S e, and (Aa)) is the solution of Equation (10) with ((0+) (Og( when g(0,) >
3: end for
449
PRACTICAL IMPLEMENTATION
Hy pere-apaaaeterss Our algorithm introduces two hyperparameters {at} and over vanilla gradient descent. We use constant sequence a, a and we take a = 0.5 unless otherwise specified. We choose by 451
452 e Yeg. where is an exponentially discounted average of 1 E [4)(0)) over the trajectory so that it automatically scales with the magnitude of the gradients of the problem at hand. In the experiments of this paper, we simply fix y = 0.1 unless specified.
453
454
455
Solving the Dual Problem Our method requires to calculate { with the dual optimization problem in Equation (10), which can be solved with any off-the-shelf convex quadratic programming tool. In this work, we use a very simple projected gradient descent to approximately solve Equation (10). We initialize (u,) with
457
vector and terminate when the difference between the last two iterations is smaller than a threshold or the algorithm reaches the maximum number of iterations (we use 100 all experiments).
459
The whole algorithm procedure is summarized in Algorithm 1.
481
C
EXPERIMENTS
C.I FINDING PREFERRED PARETO MODELS
463
C.1.1
RATIO-BASED CRITERION
The non-uniformity score from (Mahapatra & Rajan, 2020) that we use in Figure 1 is defined as
m
{,(00)
(0) Σ (0) log
(.(0)
(16)
1/m
(0)
464
We fix the other experiment settings the same as Mahapatra & Rajan (2020) and use 7 0.01 and a = 0.25 for this experiment reported in the main text. We defer the ablation studies the hyper-parameter and y
486
Section C.3.
467
C.1.2
ZDT2- VARIANT
488
We consider the ZDT2-Variant example used Ma et al. (2020) with the same experiment setting, in which the Pareto set is cylindrical surface, making the problem more challenging. We consider the same criteria, e.g. weighted distance and complex cosine used in the main context with different choices
470
of ri [0.2. 0.4, 0.6, 0.8). We use the default hyper- parameer set up, choosing 0.5 and 0.1.
18

---

Under review conference paper at ICLR 2022
weigated distance
complex oreine
Pareto Front
PNG
Target
Pareso Front
PNG
Turgel
Figure Trajectories of solving OPT-in-Pareto with weighted distance and complex cosine as criterion using PNG. The green dots are the final converged models. PNG is able to successfully locate the correct models in the Pareto set.
472 For complex cosine, we use MGD updating for the first 150 iterations. Figure shows the trajectories, demonstrating that PNG works pretty well for the more challenging ZDT2- ST2--ariant tasks.
473
474
1.1.3
GENERAL CRITERIA: THREE-TASK LEARNING ON THE NYUv2 DATASET
475
We show that PNG is able to handle large-scale multitask learning problems by deploying it on a three- task learning problem (segmentation, depth estimation, and surface normal prediction) on NYUv2 dataset (Silberman et al., 2012). The main goal of this experiment to show that: 1. PNG is able to handle OPT-in-Parete in large-scale neural network; 2. With proper design of criteria, PNG enables to do targeted fine-tuning that pushes the model to move towards certain direction. We consider the same training protocol Liu al. (2019) and use the MTAN network architecture. Start with model trained with equally weighted linear scalarization and our goal is to further improve the model's performance on segmentation and surface normal estimation while allowing some sacrifice on depth estimation. This can be achieved by many different choices of criterion and in this experiment, we consider the following design: F(0)= (Exg(()
477
479
481
482
483
(aun)ace))))(CC (0))/(0.001 + deepth (0)). Here Exeg. Lsutiaee and Eaepth are the loss functions for segmentation, surface normal prediction and depth estimation, respectively. The constant 0.001 in the denominator is for numeric stability. We point out that our design of criterion a simple heuristic and might not be an optimal choice and the key question we study here is to verify the functionality of the proposed PNG. As suggested by the open-source repository of Liu et al. (2019), we reproduce the result based on the provided configuration. To show that PNG is able to move the model along the Pareto front, show the evolution of the criterion function and the norm the MGD gradient during the training in Figure 3. As we see, PNG effectively decreases the value of criterion function while the norm of MGD gradient remains the same. This demonstrates that PNG is able to minimize the criterion by searching the model in the Pareto set. Table compares the performances on the three tasks using standard training and PNG, showing that
484
486
488
490
482
483
494
PNG is able to improve the model's 's performance on segmentation and surface normal prediction tasks while satisfying bit of the performance depth estimation based the criterion.
495
496
C.2
FINDING DIVERSE PARETO MODELS
497
C.2.1
EXPERIMENT DETAILS
19

---

Under review conference paper at ICLR 2022
Segmentation
Depth
Surface Normal
Algorithm
Angle Distance
(Higher Better)
(Lower Better)
Within t
(Lower Better)
mloU
Pix Ace
Abs Err
Rel Err
Mean
Median
11.25
22.5
30
Standard
27.09
56.36
0.6143
0.2618
31.46
27.37
19.51
41.71
54.61
PNG
28.23
56.66
0.6161
0.2632
31.06
26.50
21.06
43.41
55.93
Table 3: Comparing the multitask performance of standard training using linear scalarization with equally weighted losses and the targeted fine-tuning based on PNG.
We train the model for 100 epochs using Adam op- timizer with batch size 256 and 0.001 learning rate. To encourage diversity of the models, following the setting in Mahapatra & Rajan (2020), we use equally distributed preference vectors for linear scalarization and EPO. Note that the stochasticity of using mini- batches is able improve the performance of Pareto approximation for free by also using the intermedi- ate checkpoints approximate P. To fully exploit this advantage, for all the methods, we collect check- points every epoch approximate P, starting from epoch 60.
Criterion
Norm of MGD Grad
489
501
Values
503
505
506
507
Itertions
508
509
Figure 3: The evolution of Criterion F and the norm of MGD gradient when trained using PNG on NYUv2 dataset with MTAN network. PNG effectively de- creases the criterion while ensuring the model is within the Pareto set, since the norm of MGD gradient remains unchanged.
C.2.2
EVALUATION METRIC DETAILS
511
We introduce the definition of the used metric for evaluation. Given set P {01,... ON) } that we
513 use to approximate P, its IGD+ score defined as:
IGD+ J q(0, P)du((), q(0,
min (e(0) - e(0)) -11: PEP
514
where j is some base measure that measures the importance of 0 E P and (1)+ == max 0), applied on each element of a vector. Intuitively, for each 8, we find nearest 0 E P that approximates e best. Here the (-)+ is applied as only care the tasks that 0 is worse than 0. In practice, common choice of μ 517 be a uniform counting measure with uniformly sampled (or selected) models from P. In our experiments,
515
since we can not sample models from P. we approximate P by combining P> from all the methods, i.e., Pm. where P... is the approximation set produced by algorithm m. This approximation might not be accurate but is sufficient compare the different methods,
518
519 P Rd (Leea
The Hypervolume score of P. w.r.t. reference point l" Rmm is defined as
HV(P) 1 (fe [f,, lm] R 30 E P, s.t. (,) S S4 s4sevve S [ml))
522 where i is again some measure. We use = [0.6, 0.6] for calculating the Hypervolume based on loss and set y be the common Lebesgue measure. Here we choose 0.6 as we observe that the losses of the two tasks 524 are higher than 0.6 and 0.6 is roughly the worst case. When calculating Hypervolume based on accuracy, we simply flip the sign.
20

---

Under review conference paper at ICLR 2022
Loss
Acc
Hvt (10-2)
IGDL (10-2)
Hvt (10-2)
IGD4 (10-
0.25
1
0.041
9.39 0.038
0.0056 = 0.002
7 Y= 0.1
a = 0.5
7.86 = 0.12
0.043+0.001
9.39 + 0.038
0.0056 + 0.002
0.75
7.84 = 0.11
9.38 + 0.037
0.0057 + 0.002
7 0.01
7.86 = 0.12
0.012
9.39 + 0.038
0.0056 + 0.002
a 0.5
7 0.1
7.86 = 0.12
0.043
9.39 = 0.038
0.0056 + 0.002
7 0.25
7.85 0.11
0
9.39 + 0.036
0.0056 + 0.002
Table 4: Ablation study based on Multi-Mnist dataset with different choice of a and 7.
C.2.3
ABLATION STUDY
527
We conduct ablation study to understand the effect of a and y using the Pareto approximation task on Multi-Mnist. We compare PNG with 0.25, 0.5, 0.75 and y 0.01, 0.1, 0.25. Figure 4 summarizes the result. Overall, we observe that PNG is not sensitive to the choice of hyper-parameter.
529
C.2.4 COMPARING WITH THE SECOND ORDER APPROACH
531
We give a discussion on comparing our approach with the second order approaches proposed by Ma et al. (2020). In terms of algorithm, Ma al. (2020) is local expansion approach. To apply Ma et al. (2020), the first stage, we need to start with several well distributed models (i.e., the ones obtained by linear scalarization with different preference weights) and Ma et al. (2020) only applied in the second stage find the neighborhood of each model. The performance gain comes from the local neighbor search of each model (i.e. the second stage).
538
534
535
536
537
In comparison, PNG with energy distance is a global search approach. It improves the well-distributedness of models in the first stage (i.e. it's a better approach than simply using linear scalarization with different weights). And thus the performance gain comes from the first stage. Notice that we can also apply Ma et al. (2020) to PNG with energy distance add extra local search to further improve the approximation.
538
539
540
541
In terms of run time comparison. We compare the wall clock run time of each step of updating the 5 models using PNG and the second order approach Ma al. (2020). multi-MNIST dataset using the average of 100 steps. PNG uses 0.3s for each step while Ma et al. 2020 uses 16.8s. PNG 56x faster than the second order approach. And we further argue that, based on time complexity theory, the gap will be even larger when the size of the network increases.
542
calculate the run time based on the
544
C.3
UNDERSTANDING PNG DYNAMICS
547
We draw more analysis to understand the training dynamics of PNG.
548
Different Staring Points We give analysis on PNG with different initializations showing that PNG is more robust to the initialization than other approaches such as Lin et al. (2019). We consider the Pareto set approximation tasks and reuse synthetic example introduced Section 5. We consider learning models to approximate the Pareto front staring from two different bad starting points. Specifically, in the upper Figure 4, we consider initializing the models using linear scalarization. Due to the concavity of the Pareto front, linear scalarization
550
of
552
only learns models the extreme end of the Pareto front. The second row uses MGD for initialization and the models is scattered at an small region of the Pareto front. Different from the algorithm proposed by Lin al. (2019) which relies good initialization, using the proposed energy
554
21

---

Under review conference paper at ICLR 2022
Paceto Front
Models
Figure 4: Evolution of models from different initialization. Upper row uses initialization with linear scalarization and lower row uses initialization from MDG. From left right: evolution of models during training. PNG is robust to initializations. In both two cases of very poor initialization, PNG is still able to move the models so that they are eventually well distributed on the Pareto set.
distance function, PNG pushes the models to be equally distributed on the Pareto Front without the need of any prior information of the Pareto front even with extremely bad starting point.
557
Trajectory Visualization with Different Hyper-parameter We also give more visualization the PNG trajectory when using different hyper-parameters. for studying the hyper- syper-parameters parameters.. We reuse synthetic example introduced in Section 5.1 and 7. We fix 0.25 and vary ? 0.1, 0.05, 0.01, 0.1; and fix 7 = 0.01 and vary a = 0.1, 0.25, 0.5, 0.75. Figure plots the trajectories. As we can see, when y is properly 561
559
562
chosen, with different a, PNG finds the correct models with different trajectories. Different a determines the
563
algorithm's 's behavior of balancing the descent of task losses or criterion objectives. On the other hand, with too large y, the algorithm fails find a model that is close P", which is expected.
564
565
C.4
IMPROVING MULTITASK BASED DOMAIN GENERALIZATION
566
We argue that many other deep learning problems also have the structure of multitask learning when multiple losses presents and thus optimization techniques in multitask learning can also be applied to those domains. this paper we consider the JiGen (Carlucci al., 2019b). JiGen learns model that can be generalized unseen domain by minimizing standard cross-entropy loss fetms for classification and an unsupervised loss
567
568
589
570
Lig based on Jigsaw Puzzles:
{()) (1 felns (0) + (f).
The ratio between two losses, i.e. w, is important the final performance of the model and requires careful grid search. Notice that JiGen is essentially searching for a model on the Pareto front using the linear scalarization. Instead of using fixed linear scalarization to learn model, natural questions is that
572
22

---

Under review conference paper at ICLR 2022
pudeeace
pirkenmn
lioes profennure
prefimmos
Panto Freat
PVG
cool predeneee
trols prrfermnen
baok prefenmnco
tadk preferwerr
Figure 5: Ablation study on OPT-in-Pareto with different ratio constraint of objectives. Upper row, from left right: fixing a 0.25, 7 0.1, 0.05, 0.01, 0.001; Lower row, from left right: fixing y 0.01, a= 0.1, 0.25, 0.5, 0.75. By comparing the figures in the first row, we find that choosing too large y make the final converged model be far away from the Pareto set, which as expected. By comparing the figures in the second row, we find that changing make PNG give different priority in making Pareto improvement or descent on When a larger (the right figures), PNG will first move the model Pareto set and start decrease F after that.
23

---

Under review conference paper at ICLR 2022
574
whether it is possible to design a mechanism that dynamically adjusts the ratio of the losses so that we can achieve to learn a better model.
575
576
We give case study here. Motivated by the adversarial feature learning (Ganin et al., 2016), we propose to improve JiGen such that the latent feature representations of the two tasks are well aligned. Specifically, suppose that ceinss (0) = (J) 0)}==1 and Djgg = { (2ta, 0) 0)}== is the distribution of latent feature
577
578
representation of the two tasks, where Iy is the i-th training data. We consider FPD as some probability metric
580
that measures the distance between two distributions, we consider the following problem:
min FPD L class (0), Djie (0)]
PEP-
581
With PD as the criterion function, our algorithm automatically reweights the ratio of the two tasks such that their latent space is well aligned.
582
583
Setup We fix all the experiment setting the same as Carlucci et al. (2019b). We use the Alexnet and Resnet-18 18 with multihead pretrained on ImageNet as the multitask network. We evaluate the methods on PACS (Li et al., 2017), which covers 7 object categories and 4 domains (Photo, Art Paintings, Cartoon and Sketches). Same to
585
586
Carlucci et al. (2019b), we trained our model considering three domains as source datasets and the remaining
587
one as target. We implement FPD that measures the discrepancy of the feature space of the two tasks using the idea of Domain Adversarial Neural Networks (Ganin & Lempitsky, 2015) by adding an extra prediction head on the shared feature space to predict the whether the input is for the classification task or Jigsaw task. Specifically, we add an extra linear layer on the shared latent feature representations that is trained to predict the task that the latent space belongs to, i.e.,
588
589
590
591
FpD(2 Pelass (0), (iig(())
= min we, 12
Σ log(o(w") Velass ()), + log(1 - o(w Dotass (2i, 0))).
582
Notice that the optimal weight and bias for the linear layer depends on the model parameter 0, during the training, both w, b and & are jointly updated using stochastic gradient descent. We follow the default training protocol provided by the source code of Carlucci et al. (2019b).
594
Baselines Our main baselines are JiGen (Carlucci et al., 2019b); JiGen + adv, which adds an extra domain adversarial loss on JiGen; and our PNG with domain adversarial loss as criterion function. In order to run statistical test for comparing the methods, we run all the main baselines using random trials. We use the released source code by Carlucci et al. (2019b) to obtained the performance of JiGen. For JiGen+ady, we use
596
598
589
an extra run tune the weight for the domain adversarial loss. Besides the main baselines, also includes TF (Li et al., 2017), CIDDG (Li et al., 201 (Q).,, MLDG (Li et al., 201 2018a). D-SAM (D' Innnneneete & Caputo, 2018) and DeepAll (Carlucci al., 2019b) as baselines with the author reported performance for reference.
600
601
802
Result The result is summarized in Table with bolded value indicating the statistical significant best methods with p-vuuue based on matched-pair t-test less than 0.1. Combining Jigen and PNG to dynamically reweight the task weights is able to implicitly regularizes the latent space without adding an actual regularizer which might hurt the performance on the tasks and thus improves the overall result.
603
604
605
24

---

Under review conference paper at ICLR 2022
Method
Art paint
Cartoon
Sketches
Photo
Avg
AlexNet
TF
0.6268
0.6697
0.5751
0,8950
0.6921
CIDDG
0.6270
0.6973
0.6445
0.7865
0,6888
MLDG
0,6623
0.6688
0.5896
0,8800
0.7001
D-SAM
0.6387
0.7070
0.6466
0,8555
0.7120
DeepAll
0.6668
0.6941
0.6002
0,8998
0.7152
JiGen
0.6855 + 0.004
166889110000
0.6831110.00
0.89-16 + 0.008
0.7380 + 0.002
JiGen adv
0.6857 + 0.004
0.6837 + 0.003
0.6753 + 0.008
0.8980 + 0.001
0.7357 + 0.003
Jigen PNG
0.69144-0.005
0.6903
0.6055+00.00
0.004
0.7429+00.002
ResNet-18
D-SAM
0.7733
0.7243
0.7783
0.9530
0.8072
DeepAll
0.7785
0.7486
0.6774
0.9573
0.7905
JiGin
0.8009 E 0.004
0,7363
= 0.007
0.7046
+ 0.013
0,962910.002
0.8012 = 0.002
JiGen + adv
0. 0.7923 + 0.006
0.7402 + 0.004
0.7188 + 0.005
0.9617 = 0.001
0.8033 + 0.001
JiGen PNG
0.8014:10.005
0.7038=1.0001
0.7222:1.0066
0.962710.002
0.8100=0.005
Comparing different algorithms for domain generalization using dataset PACS and two network architectures.
Table
25


Reviews:
[{"review_id": "xmZ30U1ZXzK", "reviewer": "Reviewer_6MZF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Finding points on the Pareto front is the main motivation of many proposals in recent years. The two main motivations of the current proposal are based on resolving issues of the existing methods for large-scale models and non-convex and non-linear models in deep learning. Clearly, these claims that existing methods are not suitable for these situations are not accurate. First, in most recent works based on MGDA methods such as [A] and [B], there is either convergence analysis for both convex and non-convex objectives or no convexity assumption. Hence, this statement seems to be inaccurate, and there is no experimental comparison with other existing methods other than EPO. \n\nMoreover, the claim that they are proposing an algorithm for large-scale models seems to be inaccurate again. Since all the analysis is based on having access to the deterministic oracle of gradients and not stochastic ones, it is not clear how they can be scalable to large-scale models. The non-stochastic analysis of convergence is provided by other algorithms as well, hence, the superiority of the current approach over them is not clear.\n\nAbove all that, my main concern is the similarity of the current proposal with Algorithm 2 in [B] without a clear reference in the current work, which is clearly not acceptable. Especially since they have cited this paper in the related work and are aware of this work. In [B], similar to the current proposal the goal of finding preference-based solutions on the Pareto set has been added as a KL-divergence to the main objective. Again, similar to the current proposal, before reaching the Pareto set, they are enforcing the main and side objectives at the same time, and when they reach the Pareto set, they only pursue the side objective since the main objective common descent direction becomes zero. Compare condition (8) in the paper with Case I and II in Algorithm 2 in [B]. It is even more clear how close these proposals are when you compare their empirical results. Comparing Figure 1a and 1b in this paper and Figure 5b and 5c in [B] show the similarities. The difference of the current work with the one in [B] is generalizing the side objectives to other objectives such as diversity in addition to the preference-based. Despite this, the lack of acknowledging the existing similar work and comparing with them is clearly unacceptable.\n\n[A] Mahapatra, Debabrata, and Vaibhav Rajan. \"Multi-task learning with user preferences: Gradient descent with controlled ascent in pareto optimization.\" International Conference on Machine Learning. PMLR, 2020.\n\n[B] Kamani, Mohammad Mahdi, et al. \"Pareto Efficient Fairness in Supervised Learning: From Extraction to Tracing.\" arXiv preprint arXiv:2104.01634 (2021).\n\n", "summary_of_the_paper": "This paper intends to introduce an algorithm for finding points on the Pareto frontier with some conditions defined by the user. In this proposal, the condition defined by the user is added to the main objectives and solves a new multiobjective optimization problem. They provide empirical comparisons to show the effectiveness of their approach.", "summary_of_the_review": "There are some concerns regarding the motivations of this work. Also, similarities with the current work and existing methods not referenced appropriately, which seems to reduce the novelty of this work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "5DVRtNQxkyG", "reviewer": "Reviewer_p4mF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The objective studied is quite general and it is conceptually nice that you can plug in any loss $F$ to optimize over the pareto set (it seems that this framework is quite versatile). The paper is carefully written and nice to read. The theoretical results aren't too surprising, and somewhat limited because they work in the continuous setting and don't give specific step sizes. In the experimental results we see that the performance is marginally better than previous work (but it's more general). It would be good to mention how long the algorithm takes and compare it to the other methods.\n\nThe authors mention that the problem with the scalarization approaches (where the losses are combined into a single objective by taking their convex combination) is that they only find solutions on the convex envelope of the Pareto frontier, and thus can miss some solutions. But is there any evidence that the authors' approach does any more than that (i.e. find solutions that are not on the convex envelope)? In the figures that I saw in the paper the Pareto frontier is convex.\n\nRegarding the diversity experiments, the authors should explain a bit better how they computed the metrics. It is mentioned in the appendix that instead of sampling from the Pareto set they sample from the solutions of the various algorithms that are being compared but they could expand on that.\n\nThe authors mention that one drawback of JiGen is that it requires a careful grid search for the weighting of the two objectives. I am not sure I agree with this, since in the JiGen paper this parameter doesn't seem to be extremely critical for performance. What weighting did the authors use in their JiGen experiments and how would it compare to e.g. always setting the weights to (1,0.5)?\n\nI have a slight doubt about the approach of trying to make the distributions of the feature embeddings of image classification and jigsaw the same. By adding this distribution discrepancy module in the objective it seems to me that this approach is inadvertently trying to achieve patch permutation-invariance, which is not necessarily something desirable in general (and could also make the classification problem harder). \n\nCan the authors' algorithm be framed of as some kind of approximate projected gradient descent? I.e. if $g \\leq \\epsilon$, then take a gradient step in $F$, otherwise make Pareto-improving steps to decrease $g$. I wonder how this would compare to the authors approach, since this is a more principled way to go about it.\n\nThere is a typo in Theorem 2: $g(\\theta_t)$ should be $g(\\theta_s)$.", "summary_of_the_paper": "This paper deals with multi-objective optimization. In particular, given loss functions $\\ell_1,\\dots,\\ell_m$ and $F$, the goal is to minimize $F$ in the Pareto set of $\\ell_1,\\dots,\\ell_m$, i.e. $\\min_{\\theta} F(\\theta)$ under the constraint that for all $\\theta'$ there exists $j$ with $\\ell_j(\\theta') \\geq \\ell_j(\\theta)$. This is useful for multi-task learning, where we are interested in training a model with robust performance under a variety of tasks.\n\nThe main contribution is an algorithm that attempts to approximate this optimization problem. The main idea is to take steps in some direction $v$ that correlates as much as possible with $-\\nabla F(\\theta)$, while making sure that $\\langle v, -\\nabla \\ell_j(\\theta)\\rangle \\geq \\alpha$ for all $j$, and some scalar $\\alpha$.\n\nThe theoretical results show that the above continuous process will converge to a solution $\\theta$ that, if $F$ and $\\ell_j$'s are locally convex at $\\theta$, cannot be locally improved in the sense that any direction that decreases $F$ gives a solution that is Pareto-dominated by $\\theta$.\n\nThe experimental results show how the algorithm performs when $F$ is designed to 1) balance the ratios between the losses $\\ell_j$ based on some pre-specified numbers and 2) maximize diversity of a bunch of solutions $\\theta_1,\\dots,\\theta_k$ and 3) domain generalization.", "summary_of_the_review": "The paper is well written and presents a nice general framework, although it is not clear to me that there is a significant performance improvement compared to previous work. Therefore I lean towards acceptance.\n\n---------------------------\n\nAfter reading Reviewer's 6MZF comments, I agree that there are major similarities to Algorithm 2 in Kamani et al that need to be acknowledged. I disagree with the authors' claim that Kamani et al only makes sense for a specific choice of $F$, since their algorithm can be stated for general $F$. Therefore, I decrease my score by 1 point.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4Ove3maKjuA", "reviewer": "Reviewer_ZUH7", "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": "The paper provides a good overview of Pareto optimality and of previous works, although a thorough discussion of scalarizations (including the recent hypervolume scalarizations used for non-convex Pareto frontiers) would make sense, since there is extensive use of the linear scalarization throughout. The main interesting setting of the paper seems to be the addition of a \"non-informative\" function that would like to be maximized along the Pareto front. Examples of these functions are given; however, it seems like such a problem has already been considered.\n\nFurthermore, it is unclear if the proposed gradient descent approach to solve the main problem is novel or if it has good convergence guarantees in finite time (not in the limit). Under certain assumptions, the algorithm have descent guarantees, but it is unclear if these assumptions are discussed or are realistic. Ultimately, the algorithm also fails to find points on the Pareto frontier, just points that are Pareto \"optimal\" according to a given definition (when the Pareto frontier is non-convex, there are no clear guarantees).\n\n\n\n ", "summary_of_the_paper": "The paper summarizes a new gradient descent procedure for finding Pareto optimal points, while simultaneously optimizing with a \"non-informative\" function F that depends on the whole set of points.", "summary_of_the_review": "The paper presents an interesting setting for multi-objective optimization, but suffers from a lack of discussion of scalarizations, assumptions, why non-convex Pareto frontiers can be discarded, and the novelty/convergence of the optimization.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "-lPhg6oaXM", "reviewer": "Reviewer_vNLC", "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": "Strengths\n1) Intro and background sections refer to many prior works.\n2) The proposed algorithm is quite intuitive, and the theoretical analysis is rigorous.\n\nWeaknesses\n1) Many important details are left out, esp. in the experiment section. Granted, some of these important details can be found in the appendices, but I personally find them more important than some existing contents of the paper. For example, the practical implementation of the proposed algorithm and how its hyperparameters are chosen. Among the 3 experiment subsections, the 1st one shows a toy example. The 2nd and 3rd have slightly more practical or realistic settings. The extra criterion $F(\\theta)$ is critical for the readers to properly interpret the experiment results. The discussion about why and how to select such kind of $F(\\theta)$ is lacking. For the 3rd experiment, it was mentioned in the appendix, but even there, it's not very clear. Moreover, no comparison of computational cost between different methods can be found.\n\nA detail: At the end of line 93, the inequality should be $\\ell(\\theta') \\succ \\ell(\\theta)$.", "summary_of_the_paper": "This paper proposes an algorithm to optimize in a Pareto set in order to reach a solution or solutions that can minimize an extra criterion. The proposed algorithm is highly relevant in the context of multitask learning. The proposed algorithm takes both 1) optimizing the extra criterion w/o considering the original objectives and 2) multiple gradient descent (MGD) as its special cases. It has the flexibility to switch between two cases depending on the magnitude of the gradients w.r.t. the original tasks. The authors provide strong theoretical analysis for the proposed algorithm along with some empirical results to show its effectiveness.", "summary_of_the_review": "The algorithm proposed in this paper is intuitive and highly relevant in the context of multitask learning, but I find the experiment section didn't show the effectiveness of the proposed method clearly. Many missing important details result in many question marks while I read the paper. I think a clear and convincing experiment section is, to some extent, more important than the theoretical analysis given the gap between those regularity conditions required and the practical use cases. The experiment section of this paper definitely has room for improvement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose the OPT-in-Pareto algorithm that considers multi-objective optimization, and includes an extra "non-informative" reference metric for choosing between different Pareto-optimal solutions.

The reviewers generally agreed that the work was compelling. However, one reviewer (6MZF) brought up the fact that the proposal is extremely similar to one proposed by a different arXiv paper, and convincingly argued that the authors of this paper were aware of the other before submission.

This is a difficult situation. On the one hand, for the purposes of establishing priority, an arXiv paper "doesn't count". On the other hand, I believe that authors are obligated to appropriately credit all relevant work of which they are aware, in *any* form: this includes journals, conference proceedings, preprints, emails, personal conversations, stackoverflow posts, tweets, etc. In this case, it seems that the authors did not adhere to this second condition, and while they have updated their manuscript, two reviewers said that they were unsatisfied by the changes on this point.

I want to emphasize that this isn't a question of priority: the first to publish "wins", and nobody has published this work, yet. However, other researchers working on the same problem, and proposing similar solutions, *must* be appropriately credited, even by the eventual winners (if they are aware of them).
Decision: Reject