Learning Multiobjective Program Through Online Learning
Authors: Chaosheng Dong
Yijia Wang
Bo Zeng
Venue: Submitted to ICLR 2023 (2023)
Keywords: Learning Multiobjective Program
Multiobjective Optimization

Abstract: We investigate the problem of learning the parameters (i.e., objective functions or constraints) of a multiobjective decision making model, based on a set of sequentially arrived decisions. In particular, these decisions might not be exact and possibly carry measurement noise or are generated with the bounded rationality of decision makers. In this paper, we propose a general online learning framework to deal with this learning problem using inverse multiobjective optimization, and prove that this framework converges at a rate of $\mathcal{O}(1/\sqrt{T})$ under certain regularity conditions. More precisely, we develop two online learning algorithms with implicit update rules which can handle noisy data. Numerical results with both synthetic and real world datasets show that both algorithms can learn the parameters of a multiobjective program with great accuracy and are robust to noise.

Under review as a conference paper at ICLR 2023
LEARNING MULTIOBJECTIVE PROGRAM THROUGH ONLINE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We investigate the problem of learning the parameters (i.e., objective functions or constraints) of a multiobjective decision making model, based on a set of se- quentially arrived decisions. In particular, these decisions might not be exact and possibly carry measurement noise or are generated with the bounded rationality of decision makers. In this paper, propose a general online learning framework to deal with this learning problem using inverse multiobjective optimization, and prove that this framework converges at a rate of (1/ /V) under certain regular- ity conditions. More precisely, we develop two online learning algorithms with implicit update rules which can handle noisy data. Numerical results with both synthetic and real world datasets show that both algorithms can learn the parame- ters of multiobjective program with great accuracy and are robust to noise.
INTRODUCTION
In this paper, we aim to learn the parameters (i.e., constraints and a set of objective functions) of decision making problem with multiple objectives, instead of solving for its efficient (or Pareto) optimal solutions, which is the typical scenario. More precisely, we seek to learn 0 given [ys]se[N] that are observations of the efficient solutions of the multiobjective optimization problem (MOP):
min (fi(x,0), 0), fz(, fxx,
s.t. X0).
where 0 is the true but unknown parameter of the MOP. In particular, we consider such learning prob- lems in online fashion, noting observations are unveiled sequentially in practical scenarios. Specif- ically, we study such learning problem as an inverse multiobjective optimization problem (IMOP) dealing with noisy data, develop online learning algorithms derive parameters for each objec- tive function and constraint, and finally output an estimation of the distribution of weights (which, together with objective functions, define individuals' utility functions) among human subjects.
Learning human participants' decision making scheme is critical for an organization in designing and providing services or products. Nevertheless, as in most scenarios, we can only observe their decisions or behaviors and cannot directly access decision making schemes. Indeed, participants probably not have exact information regarding their own decision making process (Keshavarz) et al.) 201Th. To bridge the discrepancy, we leverage the inverse optimization idea that has been proposed and received significant attention in the optimization community, which is to infer the missing information of the underlying decision models from observed data, assuming that human decision makers are making optimal decisions (Ahuja & Orlin 2001| [yengar & Kang 2005 Schae-
fer 2009: Wang 2009 Keshavarz al.) 2011 Chan Chan al., [004]] Bertsimas et al. 2015 Aswani
et al. 2018 Esfahani et al. 2018 Tan et al. (020). This subject actually carries the data-driven
concept and becomes more applicable large amounts of data generated and become readily
available, especially those from digital devices and online transactions.
1.1 RELATED WORK
Our work draws inspiration from the inverse optimization problem with single objective. seeks particular values for those parameters such that the difference between the actual observation and the expected solution to the optimization model (populated with those inferred values) is minimized. Al- though complicated, an inverse optimization model can often be simplified for computation through

---

Under review as a conference paper at ICLR 2023
using KKT conditions or strong duality of the decision making model, provided that it is convex. Nowadays, extending from its initial form that only considers a single observation Abuja & Orlin 2000T) [yyngar & Kangl (2005); [Schaefer (2009): Wang (2009) inverse optimization has been fur- ther developed and applied to handle many observations Keshavarz et al. (011); Bertsimas et al. (2013); Aswani et al. (2018); Esffhhai al.] (2018). Nevertheless, particular challenge, which is almost unavoidable for any large data set, is that the data could be inconsistent due to measurement errors or decision makers' sub-optimality. To address this challenge, the assumption on the obser- vations' optimality is weakened to integrate those noisy data, and KKT conditions or strong duality relaxed to incorporate inexactness.
Our work is most related to the subject of inverse multiobjective optimization. The goal is to find multiple objective functions or constraints that explain the observed efficient solutions well. There are several recent studies related to the presented research. One is in Chan et al. (2014), which considers a single observation that is assumed to be an exact optimal solution. Then, given a set of well-defined linear functions, an inverse optimization is formulated to learn their weights. Another one is Dong & Zeng (020), which proposes the batch learning framework to infer utility functions or constraints from multiple noisy decisions through inverse multiobjective optimization. This work can be categorized as doing inverse multiobjective optimization in batch setting. Recently, Dong & Zeng (2021) extends Dong & Zeng (2020) with distributionally robust optimization by leveraging the prominent Wasserstein metric. In contrast, we do inverse multiobjective optimization in online settings, and the proposed online learning algorithms significantly accelerate the learning process with performance guarantees, allowing us to deal with more realistic and complex preference infer- ence problems.
Also related to our work is the line of research conducted by Bärmann et al. 2017) and Dong ltt al. (2018), which develops online learning methods to infer the utility function or constraints from sequentially arrived observations. However, their approach is only possible to handle inverse optimization with a single objective. More specifically, their methods apply to situations where ob- servations are generated by decision making problems with only one objective function. Differently, our approach does not make the singlc-objective assumption and only requires the convexity of the underlying decision making problem with multiple objectives. Hence, we believe that our work gen- eralizes their methods and extends the applicability of online learning from learning single objective program to multiobjective program.
1.2 OUR CONTRIBUTIONS
To the best of authors' knowledge, we propose the first general framework of online learning for inferring decision makers' objective functions or constraints using inverse multiobjective optimiza- tion. This framework can learn the parameters of any convex decision making problem, and can explicitly handle noisy decisions. Moreover, we show that the online learning approach, which adopts an implicit update rule, has an O(VT) regret under suitable regularity conditions when using the ideal loss function. We finally illustrate the performance of two algorithms on both multiob- jective quadratic programming problem and a portfolio optimization problem. Results show that both algorithms can learn parameters with great accuracy and are robust noise while the second algorithm significantly accelerate the learning process over the first one.
2
PROBLEM SETTING
2.1 DECISION MAKING PROBLEM WITH MULTIPLE OBJECTIVES
We consider a family of parametrized multiobjective decision making problems of the form .....
min XER
(fi 0), fz(x. .)..... f)(
(DMP)
8.L.
x
where p 2 2 and fi 0) R. x R + R for each E [p]. Assume parameter 0 E θ C R We denote the vector of objective functions by f(x, 8) = (fi 0), f2(, 6)................ ff, fx 8))² Assume x(0) = {x E R" g(x. 8) - 0,x E RT }. where g(x, 0) = (g) vector-valued function with ga (x, 0) RRD x Ro - IR for each l: E (4).
(x, 8)) is another
2

---

Under review as a conference paper at ICLR 2023
Definition 2.1 (Efficiency). For fixed 6, decision vector x' X(0) is said to be efficient if there exists no other decision vector x E (() such that fx 0) I ft(x", 0) for all E [p]. and (x, < fx( 8) for at least one & E [p].
In the study of multiobjective optimization, the set of all efficient solutions is denoted by ( and called the efficient set. The weighting method is commonly used to obtain an efficient solution through computing the problem of weighted sum (PWS) Gass & Saaty 1955 as follows.
min
w T f(xxx 8) s.t. x X (0),
(PWS)
where w = (w*, ..... w Without loss of generality, all possible weights are restricted to simplex, which denoted by , {w E R2 1"w 1}. Next, we denote the set of optimal solutions for the (PWS) by
S(w, 0) = arg min { (wTT(sx f( 0) x x x())
Let ",, = (w R 12 = }.. Following from Theorem 3.1.2 of Miettinen (2012). we have: Proposition 2.1. If E S(w, 0) and w E W, then (0).
The next result from Theorem 3.1 of Miettinen (012)) states that all the efficient solutions can be found by the weighting method for convex MOP
Proposition 2.2. Assume that MOP is convex. x E X is an efficient solution, then there exists a weighting vector W such that is optimal solution of (PWS)
By Propositions Corollary 2.2.1. For convex MOP
2.1 2.2 we can summarize the relationship between S(w, 0) and Xg(O) as follows.
U We wEW!
S(w, S (x( S
U 5)w,0) W
In the following, we make few assumptions to simplify our understanding, which are actually mild and appear often in the literature.
Assumption 2.1. Set is a convex compact set. There exists D > 0 such that |00|2 S D for all 0 E θ. In addition, for each 0 O, both f(x, 0) and g(x. 0) are convex in x.
2.2 INVERSE MULTIOBJECTIVE OPTIMIZATION
Consider learner who has access to decision makers' decisions, but does not know their objective functions or constraints. In our model, the learner aims to learn decision makers' multiple objective functions or constraints from observed noisy decisions only. We denote y the observed noisy deci- sion that might carry measurement error or is generated with bounded rationality of the decision maker. We emphasize that this noisy setting of y reflects the real world situation rather than for analysis of regret. Throughout the paper assume that y is random variable distributed accord- ing to an unknown distribution Py supported on V. As y is noisy observation, we note that y does not necessarily belong to X x(),, i.c., might be either feasible infeasible with respect to X (8).
We next discuss the construction of an appropriate loss function for the inverse multiobjective opti- mization problem Dong & Zeng (2020 2021). Ideally, given noisy decision y and hypothesis 0, the loss function can be defined as the minimum distance between y and the efficient set X (f):
l(y, 0) min ||y 1 xe
(loss function)
For a general MOP however, there might exist no explicit way to characterize the efficient set X (0). Hence, an approximation approach to practically describe this is adopted. Following from Corollary 1 a sampling approach is adopted to generate w) E W. for each & E [K] and approx- imate Xg(0) as Uke[k] S(w,,) 0). Then, the surrogate loss function defined as
1x (y,
min
||y
x
(surrogate loss)
0)
kE|K]
3

---

Under review as a conference paper at ICLR 2023
By using binary variables, this surrogate loss can be converted into the Surrogate Loss Problem.
lx = min 2
ly - Σ 2
KE[K]
Σ 2k 1, Xx E S(wk; 0). [E(K]
Constraint ΣKE[K] F = ensures that exactly one of the efficient solutions will be chosen to measure the distance to y. Hence, solving this optimization problem identifies some wh with & [K] such that the corresponding efficient solution S(wx, 8) is closest to y.
Remark 2.1. It is guaranteed that no efficient solution will be excluded if all weight vectors in * are enumerated. As is practically infeasible due computational intractability, we can control K to balance the tradeoff between the approximation accuracy and computational efficacy. Certainly, the computational power is strong, we would suggest to draw a large number of weights evenly in WP avoid any bias. In practice, for general convex MOP we evenly sample {wa ke( from W to ensure that (w,,, 0) E (0). If [(x 0) is known to be strictly convex, we can evenly sample {wk hE(RR] from W as S(wk. 8) E (g( by Proposition 2.1
3 ONLINE LEARNING FOR IMOP
In our online learning setting, noisy decisions become available to the learner one by one. Hence, the learning algorithm produces sequence of hypotheses (01, 0T+1). Here, 7 is the total number of rounds, and 0, is an arbitrary initial hypothesis and 0, for 1 is the hypothesis chosen after seeing the (t 1 t) decision. Let I(y,, 61) denote the loss the learning algorithm suffers when it tries to predict y, based on the previous observed decisions fy1...., y The goal of the learner is to minimize the regret, which is the cumulative loss Σ 7(ye, 0e) against the best possible loss when the whole batch of decisions are available. Formally, the regret is defined as
RT 0,), - min OEO
(y:,,)). 0).
Unlike most online learning problems that assume the loss function be smooth Shalev-Shwartz [201]: Hazan (2016), ((y, 0) and 1x (y, I) are not necessarily smooth in our paper, due to the struc- of X g (0) and UkejK] Swwk, 0). Thus, the popular gradient based online learning algorithms Bottou 1999;; Kulis & Bartleti (2010) fail and our problem is significantly more difficult than most of them. To address this challenge, two online learning algorithms are developed in the next section.
3.1
ONLINE IMPLICIT UPDATES
Once receiving the ith noisy decision yı, the ideal way to update 0 is by solving the following optimization problem using the ideal loss function
_110 1 110 - 01112 + myl(y,, 0),
o+41 = aag min
where 7/, is the learning rate in each round, and ((y,, 0) is defined in loss function
As explained the previous section, I(ye, 0) might not be computable due to the non-existence of the closed form of the efficient set (0)) Thus, we seek to approximate the update by:
0+11 arg min
マ 110 0,112 melk (ye,
(3)
#Ee
where 7), is the learning rate in each round, and 1x (y:, 0) is defined in surrogate loss
The update 3 approximates and seeks to balance the tradeoff between "conservativeness" and maintain the current
"correctiveness" where the first term characterizes how conservative estimation, and the second term indicates how corrective we would like to modify with the new estimation. As closed form exists for 0.41 in general, this update method is implicit approach.
4

---

Under review as a conference paper at ICLR 2023
Algorithm Online Learning for IMOP
Algorithm 2 Accelerated Online Learning
1: Input: noisy
decisions {Ys)Ee,
weights
1: Input: (yther and (wx [Wk]kE
(wx) kek
2: Initialize 01
2: Initialize 0 =
3: for = 1 to T' do
3: for tt= to do
4: receive Yt
4: receive Yt
5: suffer loss Ix (y:: 0&)
5: suffer loss Lx (ye, 8:)
6: let ka = arg | klyl xxl
6: if 1 (y,, 8.) 0 then
where X2 E Sww,, 0e) for & E [K]
7:
0.+1 < 02
7:
if UR (v., 02) 0 then
8:
else
8:
Btt1 c 0
9:
set learning rate The 1/vt
9: else
10:
update 0z+1 by solving 3 directly (or equiva- lently solving K subproblems
10: set learning rate nt x 1/ update 0++1 by with k k*
11:
end if
12: end if
end for
end for
To solve
we can replace X3 E S(wk, 0) by KKT conditions for each & E [K]:
min 8
1 - 0.112 + 1/ Σ
lyy: kE[K]
0x11
s.t.
θ E θ
g(xx) S 0, u 2 0, u g((() xx) = 0,
Ak E [K],
Vx, w f(x:: 0) + ug Vx,8(x))== = =0,
S 02 S Mb
Vk E [K],
X5 My (1 - 2x)) S 02 < 8k.
Vk E [K],
Σ 2k 1,
KE[K]
X5 E", Ws E RT.
2 E {0, 1]:
Ak E [K],
where ug is the dual variable for eu (x, 0) < O, and Mg is a big number to linearize z3:K-
Alternatively, solving 3 is equivalent to solving K independent programs defined in the following and taking the one with the least optimal value (breaking ties arbitrarily).
min BEe
1 110 0el12 + nelly x||
(4)
s.t. E Swc,, 0)-
Our application of the implicit update rule to learn an MOP proceeds outlined in Algorithm
Remark 3.1. (i) When choosing 4 to update 0.+1, we can parallelly compute K independent prob- lems of[4] which would dramatically improve the computational efficiency. (ii) After the completion of Algorithm]] | we can allocate every y: to the that minimizes (x (y,, 0T+1), which provides an inference on the distribution of weights of component functions fi 0) over human subjects.
Acceleration of Algorithm I Note that we update and the weight sample assigned to in simultaneously, meaning both and the weight sample index i are variables when solving 3 In other words, one needs to solve K subproblems[] to get optimal solution for 3] However, note that the increment of by 3 typically small for each update. Consequently, the weight sample assigned to y. using 0.+1 roughly the same using the previous guess of this parameter, i.e., 8. Hence, it is reasonable to approximate 3 by first assigning a weight sample to y; based on the previous updating result. Then, instead of computing K problems of simply compute single one associated with the selected weight samples, which significantly cases the burden solving Our application of the accelerated implicit update rule proceeds outlined in Algorithm 2
5

---

Under review as a conference paper at ICLR 2023
Mini-batches We enhance online learning by considering multiple observations per update Bottou & Cun (2004). online IMOP, this means that computing 81+1 using [Nae] > decisions:
0++1 arg min lEB
& 110 0.11
Σ ()(y,,0),
(5)
[N BE
However, we should point out that applying Mini-batches might not be suitable here the update 5 drastically more difficult to compute even for |Nu] = 2 than the update with a single observation.
3.2
ANALYSIS OF CONVERGENCE
Note that the proposed online learning algorithms are generally applicable to learn the parameter of any convex MOP In this section, we show that the average regret converges a rate of (L/vTT) under certain regularity conditions based on the ideal loss function [y 0). Namely, we consider the regret bound when using the ideally implicit update rule Next, we introduce a few assumptions that are regular in literature Keshavarz et al. (201T); Bertsimas et al. (2015); Esfahani et al. (2018); Dong et al. (2018).
Aswani et al. ; Dong &
Assumption 3.1. (a) X (0) is closed, and has a nonempty relative interior. X(0) is also bounded.
Namely, there exists B >> such that |x||| < B for all x E (0). The support y of the noisy decisions y is contained within a ball of radius R almost surely, where < co. In other words, P(1y||2 I R)
(b) Each function in f is strongly convex on IR.", that is for each I E [p]. 3i2 > 0, Vx, E R
Vfi(x, -v (y - X1 x y
Regarding Assumption 3.1 (a), assuming that the feasible region is closed and bounded is very common in inverse optimization. The finite support of the observations needed since we do not hope outliers have too many impacts in our learning. Let À minke(r) ()r). It follows that w f(x, 0) is strongly convex with parameter À for Wp, Therefore, Assumption 3.1 (b) ensures that S(w, f) is single-valued valued set for each w.
The performance of the algorithm also depends on how the change f affects the objective values. For Ve E Wp 01 E 0,02 E O, we consider the following function
l((x, w. 01, 02) w² f(x, 01) w f(x, 02).
Assumption 3.2. 3x > 0, Vu Wp h(, w. 0,, 02) is n-Lipschitz continuous on V. That is,
[x(x, w. 01, 02) h(y, w. 1, 02) I x||01 02 |2||2|| y/12, Vx, )..
Basically, this assumption says that the objective functions will not change much when either the parameter 9 or the variable is perturbed. It actually holds in many common situations, including the multiobjective linear program and multiobjective quadratic program.
From now on, given any y E V, 0 O, we denote x(0) the efficient point in (e) that is closest to y. Namely, I(y, 8) = ly II.
Lemma 3.1. Under Assumptions 3.1
3.2
the loss function I(y, is uniformly 4(B-1)s Lipschitz
continuous 0. That is, Vy E )/ , U2 E O, we have
4(B
R)s 10:
[( 0,) -(y, 02)
02112-
The key point in proving Lemma 3.1 is the observation that the perturbation of S(w, 0 due is
bounded by the perturbation of 0 by applying Proposition 6.1 in Bonnans & Shapiro (1998). Details of the proof are given in Appendix.
Assumption 3.3. For MOP Vy E V, O2 E O. Va, 3 2 O.t. a + B = 1, we have either of the following:
(a) if E (x)( and X2 (x((2), then ax1 fx2 Xx(a0, 302)-

---

Under review as a conference paper at ICLR 2023
(b) [|ox(01) + Bx((2) x(a01 382)1l2 S a;31x((01) - x(02))l2/(( + R)).
The definition of x((1), x(01),x(()) x(62) and x(a81 + 382) is given before Lemma 3.1 This assumption
requires the convex combination of x1 E ( and X2 ((2) belongs to X X + -82). Or there exists an efficient point in Xx(a0) + 302) close to the convex combination of x(0)) and (02). Examples are given in Appendix.
Let l* be an optimal inference to minøee Eierry '(y,, 0). i.e., an inference derived with the whole batch of observations available. Then, the following theorem asserts that under the above assump- tions, the regret Ry- = E (f(y,,0) 0,) [(y,, 0") of the online learning algorithm is of (VTT).
Theorem 3.2. Suppose Assumptions 3.1
3.3 hold. Then, choosing 7/-
DA 1 2v2(B++R) V
we have
R S 4v2(B DD VT.
A
We establish the above regret bound by extending Theorem 3.2 in Kulis & Bartlett (2010). Our ex- tension involves several critical and complicated analyses for the structure of the optimal solution set S(w, 0) as well as the loss function, which is essential to our theoretical understanding. Moreover, we relax the requirement of smoothness of loss function Lipschitz continuity through similar argument in Lemma 1 of Wang et al. (2017) and Duchi et al. (2011).
EXPERIMENTS
In this section, we will provide multiobjective quadratic program (MQP) and a portfolio optimiza- tion problem to illustrate the performance of the proposed online learning Algorithms [ and 2 The mixed integer second order conic problems (MISOCPs), which are derived from using KKT condi- tions in 3 are solved by Gurobi Optimization (201)). All the algorithms are programmed with Julia Bezanson et al. (2017). The experiments have been run on an Intel(R) Xeon(R) E5- 1620 processor that has a 3.60GHz CPU with 32 GB RAM.
4.1 SYNTHETIC DATA: LEARNING THE PREFERENCES AND RESTRICTIONS FOR AN MQP Consider the following multiobjective quadratic optimization problem.
(fi(x) xx"QQxx c xxxxxxxxx Q2x c5x
min XER
[2(x) 1x"
s.t.
Ax S,
where parameters of the objective functions and constraints are provided in Appendix.
Suppose there are decision makers. In each round, the learner would receive one noisy decision. Her goal is to learn the objective functions restrictions of these decision makers. In round suppose that the decision maker derives an efficient solution X₃ by solving (PWS] with weight wi, which is uniformly chosen from W2 Next, the learner receives the noisy decision y: corrupted by noise that has jointly uniform distribution with support [-0.5, 0.5]². Namely, y: Xx + er, where each element of & U--0.5,00 0.5).
Learning the objective functions In the first set of experiments, the learner seeks to learn e₁ and C2 given the noisy decisions that arrive sequentially in T rounds. We assume that e₁ is within range 6], C2 is within range [-6, - 11 T = 1000 rounds of noisy decisions are generated, and K = 41 weights from V2 are evenly sampled. The learning rate is set to π) = 5/ VF. Then, we implement At each round t, we solve Jusing parallel computing with 6 workers.
Algorithms
D and 2
To illustrate the performance of the algorithms in statistical way, we run 100 repetitions of the experiments. Figure Ta shows the total estimation errors of e₁ and C2 in each round over the 100 repetitions for the two algorithms. We also plot the average estimation error of the 100 repetitions. As can be seen in this figure, convergence for both algorithms is pretty fast. Also, estimation errors over rounds for different repetitions concentrate around the average, indicating that our algorithm is pretty robust to noise. The estimation error in the last round is not zero because we use a finite K to approximate the efficient set. We see in Figure Ib that Algorithm is much faster than Algorithm I especially when K is large. To further illustrate the performance of algorithms,, we randomly pick one repetition using Algorithm and plot the estimated efficient set in Figure [c We can
7

---

Under review as a conference paper at ICLR 2023
12
Gersel lia
Bushing setting Oráro setting
127
Timo
[|0
10
1000 K-6
Round
K-11
K--11
K-41
21
Tw5
T
Tw
(a)
(b)
(c)
(d)
Figure 1: Learning objective functions of an MQP over T 1000 rounds. We run 100 repetitions of
experiments. Let [c,, C2]. (a) We plot estimation errors each round for all 100 experiments
and their average estimation errors with K = 41. (b) Blue and yellow bars indicate average running time and standard deviations for each K using Algorithm and 2 respectively.
(c) We randomly pick one repetition. The estimated efficient set after T 1000 rounds is indicated by the red line. The real efficient set is shown by the yellow line. (d) The dotted brown line is the error bar plot of the running time over 10 repetitions in batch setting. The blue line is the error bar plot of the running time over 100 repetitions in an online setting using Algorithm
clearly that the estimated efficient set almost coincides with the real efficient Moreover, Figure Id shows that IMOP in online settings is drastically faster than in batch setting. is practically impossible apply the batch setting algorithms in real-world applications.
Learning the Right-hand Side In the second set of experiments, the learner seeks to learn b given the noisy decisions that arrive sequentially in rounds. We assume that b within [-10, 10]². T' = 1000 rounds of noisy decisions are generated. K = 81 weights from Wr are evenly sampled. The learning rate is set to 1) 5/vl. Then, we apply Algorithms and To illustrate the performance of them, we run 100 repetitions of the experiments. Figure 2a shows the estimation error of b in each round over the 100 repetitions for the two algorithms. We also plot the average estimation error of the 100 repetitions. As can be seen in the figure, convergence for both algorithms is pretty fast. In addition, we see in Figure 2b that Algorithm is much faster than Algorithm
Ag 1: Extimation ener
Diruel l
Agg 1: Ave Average entr
Agg 2: Estimation ene
Alg 21 Average enr
Time(s)
bb
10'
600
Round
K=6
(a)
(b)
Figure 2: Learning the right-hand side of MQP over 7 1000 rounds. We run 100 repetitions
of the experiments. (a) We plot estimation errors at each round & for all 100 experiments and their average estimation errors of all repetitions with K 41. (b) Blue and yellow bars indicate the average running times and standard deviations for each K using Algorithm and respectively,
4.2 REAL-WORLD CASE: LEARNING EXPECTED RETURNS IN PORTFOLIO OPTIMIZATION
We next consider noisy decisions arising from different investors in stock market. More precisely, consider portfolio selection problem, where investors need to determine the fraction of their wealth to invest in each security to maximize the total return and minimize the total risk. The process typically involves the cooperation between investor and a portfolio analyst, where the analyst provides an efficient frontier on a certain set of securities to the investor and then the investor selects portfolio according to her preference the returns and risks. The classical Markovitz mean- variance portfolio selection Markowitz
(952) in the following is used by analysts.
(x( =-T
min
fx(x)
=xTQx
s.t.
< 24 < by,
Vi E [n].
Σ x 1,
1=1
8

---

Under review as a conference paper at ICLR 2023
Efficent Fronter and Extimsted Efficent
0.12
smorrd Frusder siiceet
Nurstet decisltcse
0.1
0.02
006
3.00
8.30
3.30
0.28
020
0.34
The weight of fi(x)
Sunderd Deviztion of Portlatio Riturrt (Anmsallodd)
(a)
(b)
Figure 3: Learning the expected return of a Portfolio optimization problem over T = 1000 rounds with K 41. (a) The red line indicates the real efficient frontier. The blue dots indicate the estimated efficient frontier using the estimated expected return for K 41. (b) Each bar represents the proportion of the 1000 decision makers that has the corresponding weight for fx().
where r E R is vector of individual security expected returns, Q E R is the covariance matrix of securities returns, x is a portfolio specifying the proportions of capital to be invested in the different securities, and b; is an upper bound on the proportion of security i, Vi E [n|]
The dataset is derived from monthly total returns of 30 stocks from blue-chip index which tracks the performance of top 30 stocks in the market when the total investment universe consists of thousands assets. The true expected returns and true return covariance matrix for the first securities are given in the Appendix.
Dataset:
Details for generating the portfolios are provided in Appendix. The portfolios on the efficient fron- tier are plot Figure 3a The learning rate set to 1/t = 5/vt. At each round 1, we solve using parallel computing. In Table we list the estimation error and estimated expected returns for different K. The estimation error becomes smaller when K increases, indicating that we have a better approximation accuracy of the efficient efficient frontier using the estimated i for K = 41 in Figure 3al We can see that the estimated effi- cient frontier is very close the real one, showing that algorithm works quite well in learning expected returns in portfolio optimization. We also plot our estimation on the distribution of the weight of fi (x) among the 1000 decision makers. As shown in Figure 3b) the distribution follows roughly normal distribution. We apply Chi-square goodness-of-fit tests to support our hypotheses.
when using larger K. We also plot the estimated
Table I: Estimation Error for Different K
K
6
11
21
41
Ttruell |12
0.1270
0.1270
0.0420
0.0091
CONCLUSION AND FUTURE WORK
In this paper, an online learning method to learn the parameters of the multiobjective optimization problems from noisy observations is developed and implemented. We prove that this framework converges at a rate of O(1/VT) under suitable conditions. Nonetheless, as shown in multiple ex- periments using both synthetic and real world datasets, even these conditions are not satisfied, we still observe fast convergence rate and strong robustness to noisy observations. Thus, it would be interesting to analyze to what extent these conditions can be relaxed.
Also, we note that our model naturally follows the contextual bandit setting. We can view the decision yt observed at time as the context. The learner then takes the action 0, and the loss is jointly determined by the context and the action. Compared to the vast majority of literature surveyed in Zhou (0055), the main technical difficulty our model how to set an appropriate
reward (loss) given the context (yx) and the action (0z). Intuitively, we set the loss the difference between the context (y/) and another context generated by the action. Motivated by this observation, one future work is to integrate classical contextual bandits algorithms into model. Particularly, we think that algorithms without the Linear Realizability Assumption (the reward is linear with respect the context), such KerneUUBB, might fit well in our problem.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ravindra K Ahuja and James B Orlin. Inverse optimization. Operations Research, 4955)7771-783 2001.
Anil Aswani, Zuo-Jun Shen, and Auyon Siddiq. Inverse optimization with noisy data. Operations Research, 2018.
Andreas Bärmann, Sebastian Pokutta, and Oskar Schneider. Emulating the expert: Inverse optimiza- tion through online learning. In JCML, 2017.
Dimitris Bertsimas, Vishal Gupta, and Ioannis Ch Paschalidis. Data-driven estimation in equilibrium using inverse optimization. Mathematical Programming, 153(2):595 633, 2015.
Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral B Shah. Julia: A fresh approach to numerical computing. STAM Review, 59(1):65-98, 2017.
J Frédéric Bonnans and Alexander Shapiro. Optimization problems with perturbations: A guided tour. SIAM Review, 40(2):22--26) 1998.
Léon Bottou, On-line learning and stochastic approximations. In On-line Learning in Neural Nei- works, pp. 9-42. Cambridge University Press, 1999.
Léon Bottou and Yann Cun. Large scale online learning. NIPS, 2004.
Timothy CY Chan, Tim Craig, Taewoo Lee, and Michael B Sharpe. Generalized inverse multi-
objective optimization with application cancer therapy. Operations Research, 62(3):680-695, 2014.
Chaosheng Dong and Bo Zeng. Inferring parameters through inverse multiobjective optimization. arXiv preprint IrXiv:1808. 00935, 2018.
Chaosheng Dong and Bo Zeng. Expert learning through generalized inverse multiobjective opti- mization: Models, insights, and algorithms. In ICMI., 2020.
Chaosheng Dong and Bo Zeng. Wasserstein distributionally robust inverse multiobjective optimiza- tion. In AAAI, 2021.
Chaosheng Dong, Yiran Chen, and Bo Zeng, Generalized inverse optimization through online learn- ing. In NeurIPS, 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 120uu)):121-2155 2011.
Peyman Mohajerin Esfahani, Soroosh Shafiezzadeh-Abaddhh Grani A Hanasusanto, and Daniel Kuhn. Data-driven inverse optimization with imperfect information. Mathematical Program- ming, 167(1):191-334 2018.
Saul Gass and Thomas Saaty. The computational algorithm for the parametric objective function. Naval Research Logistics, 2(1-2):39 45, 1955.
Inc. Gurobi Optimization. Gurobi optimizer reference manual, 2016. URL http: / www. gurobi..cmmm com
Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer, 2001.
Elad Hazan. Introduction online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325, 2016.
Garud Iyengar and Wanmo Kang. Inverse conic programming with applications. Operations Re- search Letters, 33030,3,--330, 2005.
Arezou Keshavarz, Yang Wang, and Stephen Boyd. Imputing a convex objective function. In Intelligent Control (ISIC), / IEEE International Symposium on, pp. 613-619, IEFE, 2011.
10

---

Under review as a conference paper at ICLR 2023
Brian Kulis and Peter L Bartlett. Implicit online learning. In ICML, 2010.
Harry Markowitz. Portfolio selection. The Journal of Finance, 7(1):77-91, 1952.
Kaisa Miettinen. Nonlinear Multiobjective Optimization, volume 12. Springer Science & Business Media, 2012.
Andrew J. Schaefer. Inverse integer programming. Oplimization Letters, 3(4):483-489) 2009.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends@ in Machine Learning, 1(2):107-194, 2011.
Yingcong Tan, Daria Terekhov, and Andrew Delong. Learning linear programs from optimal deci- sions. arXiv preprint arXiv:2006..00 089233 2020.
Jialci Wang, Weiran Wang. and Nathan Srebro. Memory and communication efficient distributed
stochastic optimization with minibatch prox. In Proceedings of the 2017 Conference Learning Theory, volume 65, pp. 1882-1919, 2017.
Lizhi Wang. Cutting plane algorithms for the inverse mixed integer linear programming problem. Operations Research Letters, 37(2):114-116, 2009.
Li Zhou. A survey on contextual multi-armed bandits. arXiv preprint arXiv: 1508.03366, 2015.
A
APPENDIX
A.1 OMITTED MATHEMATICAL REFORMCLATIONS
Before giving the reformulations, we first make some discussions about the surrogate loss functions.
L (y min lly (0,(),1)
kE[K]
min
lly
24 11 (K - 1)
#.6(0.1)
kE[K]
where X2 E S(wk: 0) and Σ 2k 1.
Since (K y) _ is a constant, we can safely drop it and use the following as the surrogate loss function when solving the optimization program in the implicit update.
1x(y,0)
min Σ E1y-- ze (0.10
RE(K]
where X E S(Wk. 0) and ΣkERK 2k = 1.
A.1.1 SINGLE LEVEL REFORMULATION FOR THE INVERSE MULTTIBIECTIVE OPTIMIZATION PROBLEM
The parametrized mulobjective optimization problem is
min xER
f(x, 0)
MOP
s.t.
g(x) <
where
f(x; 0) (x, 0), f2(x, 0). ... f f,(x,
g(x) (g) (x). (x)....) (x)
Then, the single level reformulation for the Implicit update in the paper is given in the following
11

---

Under review as a conference paper at ICLR 2023
min
1110 0:112 + ' Σ lly+ 0x11
kE[K]
s.t.
0 +
8(x²) < 0, us 2 0
u g [Kk) = 0
vk [K]
Vx, Wi: f(x:; 8) - Vx. -xx)(x)=
0 S 0R < M&ZK
vk E [K]
X M1 2k) 5k X
Ak [K]
Σ 2 =
[E[K]
X E R" Ur E R to E (0.1)", E (0,1) Aa E [K]
A.1.2 SINGLE LEVEL REFORMULATION FOR THE INVERSE MULTIOBIECTIVE QUADRATIC PROBLEM
When the objective functions are quadratic and the feasible region is a polyhedron, the multiobjec- tive optimization has the following form
1 12" x
min xER*
MQP
1x + +c cxxx
s.t.
Ax b
where Qi S (the set of symmetric positive semidefinite matrices) for all ( E [p]..
When trying to learn { het)) the single level reformulation for the Implicit update in the paper is given in the following
min
Σ
c -ci12 + Th
Σ lly: 0x112 RE[R]
s.t.
C E Ci
4 [p]
Ax 2 b, U₁ 2
up S Mt
4A [y]
Ax b 5 M(1 t²)
(wtQu +... w((p))x wfe + ... + w.c,p AFu =0
S 03 S Ma²k
Wk E [y]
X M₁ (1 =x)= < 0g Xx X
Vk E [K]
Σ 2k =1
KE[K]
Xk E R", us E RT, t, E (0,1),, 2 E (0,1)
EE [
where of is the estimation of c, at the tth round, and Č₁ is convex set for each I E [p]. We have a similar single level reformulation when learning the Right-hand side b. Clearly, this is a Mixed Integer Second Order Cone Program(MISOCP) when learning either c; b.
12

---

Under review as a conference paper at ICLR 2023
A.2
OMITTED PROOFS
A.2.1
STRONGLY CONVEX OF w wF 0) AS STATED UNDER ASSUMPTION 3.1
Proof. By the definition of X,
Vw Vw" Vu''((x00) T (x-x)
& wifily, 0) v V wifi(xx 01)
V
(x-x)
1=1
T
Σ wi Vfly,, 01) - Vf((x, 61)
(y (y-x) x)
wr>1 y113 7||x y Σ
u1
1=1
A|Ix y12
Thus, w f(x, 0) is strongly convex for E R"
A.2.2 PROOF LEMMA 3.1
Proof. By Assumption 3.1(b). we know that Sww, 0) is a single-valued set for each w E W, Thus, vy E V, v0,,0, 0g E ( Ewo, w² E w, s.t.
x(01) = S(w (/w",,1) 01), x(02) = ((w2,,0)
Without of loss of generality, let (y, 2 1x (y, 02). Then,
Lx (y, 01) - (y, 02) = 1x (y. 01) - (y, 02)
lly x(61)113 |yy x(82)113
Ily -S(w",0))
yy -S(w², S(w2,0%) 02)
(6)
S Ily - -S(w2,01)13 - yly -Sw22, n0u2,0, 02)
(S(w?, (2)) S(w2 01),2 5(w2 01) S(w?,02)
S 2(B + 12) (w 02) - 3()210))11
The last inequality is due to Sauchy-Schwand inequality and the Assumptions 3.), that is
|2y - Sww2, .1) - Sww2, 02)122 - 2(B
Next, we will apply Proposition 6.1 in Bonnans & Shapiro (198 to bound [SS(w2,0>) S(w², 01)112-
Under Assumptions 3.1 - 3.2, the conditions of Proposition 6.1 in Bonnans & Shapiro (9988) are satisfied. Therefore.
2x 00 B2ll2
||S(W2 02) S(w2,,:)122 S
Plugging equation 7 and equation g in equation yields the claim.
A.2.3 PROOF OF THEOREM 3.2
Proof. We will extend Theorem 3.2 in Kulis & Bartlett (201)) to prove our theorem.
Let (0) 1 0.113 myl(y,, 8).
We will now show the loss function is convex. The first step is to show that if Assumption 3.3 holds, then the loss function ((y 0) is convex in 0.
13

---

Under review as a conference paper at ICLR 2023
First, suppose Assumption 3.3(a) hold. Then,
ab1 + 582) ally, 81) Bl(y, 02) 1(y.a81
ally x(O)) )l22 + Blyy x(02)ll |yy x(a0i + 302)
z ally x(01)llž + Blyy x(02)l1 - 1ly- (ax((1)) - 3x(02)113 (By Assumption 3.3(a))
(f)l(x(1)) x((2)]l1
Second, suppose Assumption 3.3(b) holds. Then,
ally, 01) + 3l(y, 02) ((y, a01 + 302)
= ally x(61)113 + Bly x(f2) 1 ly x(a0) + 382)11
ally x x01))] Blyy x(02) 12 lyy axx(0)) (x(
+ ll ax(01) 3x ly - x(a01 + :82)
(01l - x(02)ll + - -ax((0)))) - (x(02) - lly x(x00 + 3002)111
ag11x((1) x(02)11 (ax(01) + 8x(02) x(a0) + (02), 2y -x(a01 + -000000 ax((0)) 3x(02))
x(01) - x(02) |lax(0:) + (x((2) x(a0) - 302)]12|12y - x(a01 + .300) ox((1) - -x(22))22
(10)
The last inequality is by Sauchy-Schwarte inequality. Note that
[|ax(01) + (x(00) x(a0) (02))12||2 ||2 - x(a0) + 302)) ax(())) - 3x(0))l
2BB Rx (01) + (0x(22) x(a0: + /822]ll
(11)
x;31|x(0) (0) - x(22)l12
(By Assumption 3.3(b))
Plugging equation in equation T0
yields the result.
G2 (0.+))
Using Theorem 3.2. Kulis Bartlett 2010), for ar S Ge(l))
we have
Rr E Σr 1 (1 at ax)m, 0z)
mi
(12)
(l0, - 0r 12 10+11 (²)
2n.
Notice that
G.(O,) Go(((+1)
ni (1(ye, 02) 1(y 0 0c+1)) ) - 1110 - 0c+1
4(B+ R)Nn 100 0 ||2 -1100 0c+1 11
(13)
8 22 X²
The first inequality follows by applying Lemma 3.1.
Let ar Re(0.+1),
Using equation 13
we have
(.)))))
(1 az mml()
(1 ar (o.)) (f:) ((
(14)
8 (2)++))2220 ?
X²
Plug equation 14 in equation 12 and note the telescoping sum,
T 8(B +
R)2
Rr
X2
t=1
(1)0,
8" 112
10 11)
2m
1=1
14

---

Under review as a conference paper at ICLR 2023
Setting 7t- 2(B4R)ev/: we can simplify the second summation to D) since the sum
telescopes and 01 0, 110 2 S D. The first sum simplifies using Ei=1 2VV -1 to obtain the result
4 VT.
RT S
X
A.3 OMITTED EXAMPLES
A.3.1 EXAMPLES FOR WHICH ASSUMPTION
3.3 HOOLDS
Consider for example the following quadratic program
x 20 x 20 x
min
s.t.
0 x - 10
One can check that Assumption 3.3 (a) is indeed satisfied. For example, let n = 1. Then, W.L.O.G. let 0 8g. Then, (t) [01, 02]. Consider two parameters that A¹ (8), 82 (69,
[0, 10 For all a E [0,
Xg(at' + (1 - a))²) = [a0] + +1 - a)ff, a02 + (1 - a)0
Although tedious, one can check that one can check that Assumption 3.3 (a) is indeed satisfied.
A.4 DATA FOR THE PORTFOLIO OPTIMIZATION PROBLEM
Table 2: True Expected Return
Security
2
3
6
7
Expected Return
0.1791
0.1143
0.1357
0.0837
0.1653
0.1808
0.0352
0.0368
Table 3: True Return Covariances Matrix
Security
2
5
8
0.1641
0.0299
0.0478
0.0491
0.058
0.0871
0.0603
0.0492
0.0299
0.0720
0.0511
0.0287
0.0527
0.0297
0.0291
0.0326
0.0478
0.0511
0.0794
0.0498
0.0664
0.0479
0.0395
0.0523
0.0491
0.0287
0.0498
0.1148
0.0336
0.0503
0.0326
0.0447
0.0580
0.0527
0.0664
0.0336
0.1073
0.0483
0.0402
0.0533
6
0.0871
0.0297
0.0479
0.0503
0.0483
0.1134
0.0591
0.0387
0.0603
0.0291
0.0395
0.0326
0.0402
0.0591
0.0704
0.0244
0.0492
0.0326
0.0523
0.0447
0.0533
0.0387
0.0244
0.1028
A.5 APPROXIMATION ERROR
Theorem A.1. Under Assumption 3.1 we have that Vy y, V0 
4(B + R)
/2p
0 05lx(y,0 - 1(y,0) -11y)))))(y
A A A-1 1'
where
(A + 2)!
K
(A - 1)1(p 111 [elp]xxeXX (0) Bee
max
[f(( 0))
Furthermore,
16e( (BeBBo + R)
0 S (k 0) - 1l.. 0)
X
K p-1
15

---

Under review as a conference paper at ICLR 2023
Thus, the surrogate loss function uniformly converges to the loss function at the rate of O(1/K=T)) Note that this rate exhibits a dependence on the number of objective functions As p increases, might require (approximately) exponentially more weight samples {wx ]eE[]] to achieve an approximation accuracy. In fact, this phenomenon is reflection of curse of dimensionality Hastic al. 200T), principle that estimation becomes exponentially harder the number of dimension increases. In particular, the dimension here is the number of objective functions p. Naturally, one way deal with the curse of dimensionality is to employ dimension reduction techniques in statistics to find low-dimensional representation of the objective functions.
Example A.1. When p = 2. MOP is a bi-objective decision making problem. Then, Theorem A. shows that 1 0) 1yy, 0) is of (1/K)). That is, (x(y,0) asymptotically converges (yy 0) sublinearly.
Proof. By definition.
((yy,)
min
lly - -
min bly - x 0. xEXx(0)
xe U S(w,. kc|A]
Let I|y Sww 0)122
min
x 1. and lly S(w ,0)12
min lly
x
x1 Let
x U kE[K]
0)
x xxXx(0)
w the closest weight sample among (wx ] to wv. Then,
(x - 0y
= y S(w 0)| lyy - S(w", 0)12
S yy S(wg., 0)1 Ily S(w 0)11
(2y S(u 0) S(w7,0) 00)" (S(w), 0) Sww ((ww,0)) 0))
(15)
< | 12 S(w) 0) 5(w",0)la (w (W),, - S(w 0)1l
S 2(B R) B) 5(w 0)1
A(BRRICVE | w 112.
where Ç
xx x .0ee (xx(x, 0)) The third inequality is due Cauchy Schwarz inequality.
Under Assumption 3.1 we can apply Lemma 4 in Dong & Zeng 2018 to yield the last inequality.
Next, we will show that Yw E Wp the distance between w and its closest weight sample among {wi he[RK is upper bounded by the function of K and p and nothing else. More precisely, we will
show that
V2 A A-1
sup min ||w wxll2 we NEW, kE(K]
S
(16)
Here, A is the number of evenly spaced weight samples between any two extreme points of Wp-
[K] are evenly sampled from Wp, and that the distance between any two extreme points of Wr equals to v2. Hence, the distances between any two neighboring weight samples are equal and can be calculated as the distance between any two extreme points of W, divided by 1. Proof of equation 16 can be done by further noticing that the distance between any w and {wx } is upper bounded by the distances between any two neighboring weight samples.
Note that { {wx) kek kejk]
Combining equation
1 and equation 16 yields that
0 < (x(y, -1y,, < 4(B+ R)C
2pp
(17)
A A-1'
Then, we can prove that the total number of weight samples K and has the following relationship:
K A - 2 2)
(18)
Proof of equation can be done by induction with respect to p. Obviously, equation 18 holds when p = 2 as K A. Assume equation [8 holds for the < p cases. For ease of notation, denote
KA
A + 2 p
16

---

Under review as a conference paper at ICLR 2023
Then, for the p case, note that the weight samples be classified into two categories: Wp O; up O. For up 0, the number of weight samples is simply K For up >> O, the number of weight samples is KA-1 Thus,
K K K + Kp-
(19)
Iteratively expanding Kp KA-1 through the same argument as equation 18 and using the fact that
1
- + t)
we have
K
KA. p-1
KA-1
K.t. k K
Kp-1 - kp-1 .... - K
(20)
AA + P 3)
A (A+
p - 4) + +... +
(D) (D-2) 2) + (b=1)
p +
y
p-+p-2))
(A-1)1(p-1]
To this end, we complete the proof of equation 18 Furthermore, we notice that
(A 2)
(A + 2
A + p-p - - p-1
K (A 1)1(p 1)!
(w-1))
p-1
Then, when 2 p 2 20-1), through simple algebraic calculation we have
p-1
(21)
K
A A+p-2
A
We complete the proof by combining equation 17 and equation 21 and noticing that /2p S p.
17


Reviews:
[{"review_id": "SsZMe9VQ0Ii", "reviewer": "Reviewer_QnFE", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "This paper is very technical and I'll first say I am not familiar with the literature. However, as somewhat an \"outsider\" to this problem, hopefully I can contribute by asking the right questions, which can help the author make this work more accessible.\n\nMy naive understanding of this paper is that it's basically doing reward learning (or inverse reinforcement learning). Given a black box agent with some latent reward function (of a particular form, that of min of bunch of other functions), we can observe the agent's actions to infer what the reward function is. The observations come sequentially, but we do not get to control what observation to make.", "summary_of_the_review": "from a non-expert point of view, this paper can result in an artifact that can exist in scipy as a black-box, which is definitely a contribution. I would defer technical correctness to an expert.\n\nafter discussion with other reviewers, who knows the work better, I'm lowering my score to a 6.\nI still think this work is interesting though.", "strength_and_weaknesses": "strength : It tackles a new problem of multi-objective reward learning, of a particular form: min(f1(x,\\theta) ... fn(x,\\theta)). The paper was able to take this special form, along with some assumptions, to develop a set of update-rules to guess what \\theta can be as online observations come in. Even if the user (like me) does not grasp the full derivation, this algorithm can easily exist in a package to be used as black box.\n\nweakness : for me the paper is easy to follow wherever it is self-contained, but then some thm or corr. was invoked, and this \"jump\" makes the paper hard to follow. however this is unlikely to be an issue with people familiar with the field.\n\nI do have some questions, which would be great to have answered:\n\n1. when we say the agent is minimizing regret, does it mean it is sufficient agent comes up with a hypothesis that explains the data as well as the original \\theta, rather than trying to infer the original \\theta itself?\n\n2. I always find the connection between bandit-like literatures and bayesian inference related, yet the two use very different language. For me, I'd think we just put some prior over the hypothesis P(\\theta), and we do posterior inference of P(\\theta | Data) while assuming some forward data generating process P(Data | \\theta). Or more simply, we can find the maximum-likelihood estimator without the full posterior. There must be a good reason why this kind of language isn't the way to explain your work, but what is it? \n\n3. How would the problem change if you are allowed to take active samples? i.e. present the agent with a scenario as a query, and see how it respond to it in the style of active learning. Can your approach be made to work in this setting? How would you select a query? How would you select a query without making some distributional assumptions of the objective function, other than it is a min of a bunch of functions ? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "QP6bdYST8I", "reviewer": "Reviewer_4Sxk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors study an inverse online multiobjective problem. In particular, the learner noisily observes a sequence of decisions made by a decision-maker. The learner's goal is to infer the parameters of the multiple objectives used by the decision-maker.\n\nThe authors give an online learning algorithm for this setting that achieves $1/\\sqrt{T}$ regret under some regularity conditions—namely strong convexity of the individual objectives and Lipschitzness in how the decision changes as a function of the parameters. A key issue is efficient computation of the efficient frontier and how approximation affects algorithm performance. Motivated by the theory, the authors introduce an accelerated variant.\n\nIn the experiments, the authors illustrate the estimation error of each algorithm, its computational cost and how well its estimated efficient set matches the true one.", "summary_of_the_review": "The work takes a new incremental step that \\emph{may} be in the direction of solving an interesting problem.\n\nPost-response:\nI am somewhat convinced by the authors' response but not fully. (The updated version also fails to fix many of the small presentational issues that the paper has).", "strength_and_weaknesses": "Strengths:\n- The setting and algorithm appear novel.\n- The experiments provide a nice evaluation of the two variants of the algorithm.\n\nWeaknesses:\n- The alignment between the work and motivation seems a bit off. The most natural motivation from my perspective is being able to predict the decision better under unseen settings where we have some salient information, such as new estimated returns and risks in the portfolio optimization setting. As it stands, nothing appears to change between observed decisions except the realized noise—so there doesn't seem to be a strong reason to infer the parameter vector $\\theta$.\n- The authors also gesture towards suboptimality of the observed decisions, which seems like a relevant problem, but their model doesn't really accommodate this because the noise is simply added to the decisions themselves. I was expecting to see noise added farther upstream—either to the objective functions themselves or to the parameters $\\theta$.\n- The sequence of intro to related work is poorly written, in my opinion, starting from about the second paragraph. The end of the intro serves as a mini related work section on its own, but it doesn't make clear what the authors' contributions are in detail or directly clarify what is different from past work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Bb8kJIo901", "reviewer": "Reviewer_SLew", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of inverse multiobjective optimization via online learning. Under some assumptions, the authors prove that an ideal online implicit update method has the regret bound of $O(\\sqrt{T})$. However, this ideal method cannot be implemented in practice. To address this problem, the authors proposed two approximate variants of this ideal method, which are heuristic.", "summary_of_the_review": "From the above comments, I think this paper is marginally below the acceptance threshold.", "strength_and_weaknesses": "#Strength\n1) The problem of inverse multiobjective optimization is interesting.\n2) The authors propose an ideal online implicit update method with the $O(\\sqrt{T})$ regret bound, and provide two efficient variants of this ideal method.\n\n#Weaknesses\n1) Dong et al. (2018) have studied inverse optimization via online learning and proposed an online method with $O(\\sqrt{T})$ regret bound. Although this paper further considers the inverse multiobjective optimization, which is more general than Dong et al. (2018), both the ideal online implicit update method and the regret bound are very similar to those in Dong et al. (2018), which limits the novelty of this paper.\n2) Compared with Dong et al. (2018), the additional challenge faced by this paper is caused by the non-existence of the closed form of the efficient set. The authors address this challenge by approximating the efficient set with a sampling approach. However, the authors do not provide theoretical guarantees about the approximation error.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject