Conformal Inverse Optimization
Authors: Bo Lin
Erick Delage
Timothy Chan
Venue: NeurIPS 2024 poster (2024)
Keywords: inverse optimization
robust optimization
algorithm aversion
data-driven decision making
Primary area: optimization
TL;DR: We propose a principled approach to learn an uncertainty set from decision data and then solve a robust optimization model to prescribe high-quality and intuitive decisions.

Abstract: Inverse optimization has been increasingly used to estimate unknown parameters in an optimization model based on decision data. We show that such a point estimation is insufficient in a prescriptive setting where the estimated parameters are used to prescribe new decisions. The prescribed decisions may be low-quality and misaligned with human intuition and thus are unlikely to be adopted. To tackle this challenge, we propose conformal inverse optimization, which seeks to learn an uncertainty set for the unknown parameters and then solve a robust optimization model to prescribe new decisions. Under mild assumptions, we show that our method enjoys provable guarantees on solution quality, as evaluated using both the ground-truth parameters and the decision maker's perception of the unknown parameters. Our method demonstrates strong empirical performance compared to classic inverse optimization.

Conformal Inverse Optimization
Bo Lin
Erick Delage HEC Montréal Mila Québec AI Institute erick delage@hec.cccc
Timothy C. Y. Chan
University of Toronto
University Toronto
bl blin@mie. utoronto.com w ca
Vector Institute
tcychan@mie, utoronto.co
Abstract
Inverse optimization has been increasingly used to estimate unknown parameters in an optimization model based on decision data. We show that such a point estimation used
is insufficient in prescriptive setting where the estimated parameters to prescribe new decisions. The prescribed decisions may be of low-quality and misaligned with human intuition and thus are unlikely to be adopted. To tackle this challenge, we propose conformal inverse optimization, which seeks to learn an uncertainty for the unknown parameters and then solve robust optimization model to prescribe new decisions. Under mild assumptions, we show that our method enjoys provable guarantees on solution quality, as evaluated using both the ground-truth parameters and the decision maker's 's perception of the unknown parameters. Our method demonstrates strong empirical performance compared classic inverse optimization.
Introduction
Inverse optimization (IO) a supervised learning approach that fits parameters in an optimization model decision data. The fitted optimization model can then be used to prescribe future decisions. Such problems naturally arise in Al applications where human preferences are not explicitly given, and instead need to be inferred from historical decisions. For this pipeline to succeed in practice, the prescribed decision should not only be of high quality but also align with human intuition (i.e., perceived be of high-quality). The latter encourages algorithm adoption (Chen al., 2023; Donahue et al., 2023), which is critical in many real- world settings (Liu et al., 2023; Sun et al., 2022).
As an example, rideshare platforms, e.g., Uber and Lyft, provide shortest-path to the driver at the start of a trip based on real-time traffic data (Nguyen, 2015). The driver then relics on her perception of the road network formed through past experience to evaluate the path. The driver may deviate from the suggested path it is perceived to low-quality. Although seasoned drivers are often capable of identifying better path due to their tacit knowledge of the road network (Merchán et al., 2022), such deviations impose operational challenges as it may cause rider safety concerns and affect downstream decisions, such arrival time estimation, trip pricing, and rider-driver matching (Hu et al., 2022). Therefore, the platform may be interested leveraging historical paths taken by drivers to suggest high-quality paths for future trips, as evaluated using both the travel time and the driver's perception.
In this paper, we first show that the classic pipeline may generate decisions that are low-quality and misaligned with human intuition. We next propose conformal IO, which first learns uncertainty set from decision data and then solves a robust optimization model with the learned uncertainty set to prescribe decisions. Finally, we show that the proposed approach has provable guarantees on the actual and perceived solution quality. Our contributions are as follows.
New framework. We propose new 10 pipeline that integrates i) novel method to lear uncertainty sets from decision data and ii) robust optimization model for decision recommendation.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Theoretical guarantees. We prove that, with high probability, the learned uncertainty set contains parameters that make future observed decisions optimal. This coverage guarantee leads to bounds on the optimality gap of the decisions from conformal IO, as evaluated using the ground-truth parameters and the decision maker's (DM's) perceived parameters.
Performance. Through experiments, we demonstrate strong empirical performance of conformal 10 compared to classic IO and provide insights into modeling choices.
Literature Review
Inverse optimization. IO is method to estimate unknown parameters in an optimization problem based on decision data (Ahuja and Orlin, 2001; Chan et al., 2014; Chan and Kaw, 2020). Early IO papers focus on deterministic settings where the observed decisions are assumed to be optimal to the specified optimization model. Recently, IO has been extended to stochastic settings where the observed decisions are subject to errors and bounded rationality. Progress has been made to provide estimators that are consistent (Aswani et al., 2018; Dong et al., 2018), tractable (Chan et al., 2019; Tan et al., 2020; Zattoni Scroccaro et al., 2024), and robust to data corruption (Mohajerin Esfahani et al., 2018). Our paper is in the stochastic stream. Unlike existing methods that provide point estimation of the unknown parameters, we learn an uncertainty set that can be used in a robust optimization model.
Data-driven uncertainty set construction. Recently, data have become critical ingredient to design the structure (Delage and Ye, 2010; Mohajerin Esfahani et al., 2018; Gao and Kleywegt, 2023) and calibrate the size (Chenreddy et al., 2022; Sun al., 2023) of an uncertainty set. Our paper is related to the work of Sun et al. (2023) who first use an MI. model to predict the unknown parameters and then calibrate an uncertainty set around the prediction. However, this approach does not apply in our setting it requires observations of the unknown parameters, which we do not have access to. Our paper presents a new approach to calibrating uncertainty sets using decision data.
Estimate, then optimize. Conformal IO belongs to a family of data-driven optimization methods called "estimate, then optimize" (Elmachtoub al., 2023). Recent research suggests that even small estimation errors may be amplified in the optimization step, resulting in significant decision errors. This issue can be mitigated by training the estimation model with decision- aware losses (Wilder et al., 2019; Mandi et al., 2022) and robustifying the optimization model (Chan et al., 2023a). We take similar approach as the second stream, yet deviate from them by i) utilizing decision data instead of observations of the unknown parameters, and ii) focusing on both the ground-truth and perceived solution quality, the latter which has not been studied this stream of literature.
Preference learning. Preference learning has been studied in the context of reinforcement learning and has recently attracted significant attention due to its application in Al alignment (Ji et al., 2023). Existing methods focus on learning a reward function/decision policy that is maximally consistent with expert decision trajectories (Ng and Russell, 2000; Wu et al.. 2024) or labeled preferences in the form of pair-wise comparison/ranking (Wirth et al., 2017; Christiano et al., 2017; Rafailov et al., 2024). We enrich this stream of literature in two ways. First, we leverage unlabeled decision data that are not state-action trajectories, but solutions to an optimization model. Second, instead of learning a policy that imitates expert behaviors, we aim to extract common wisdom from decision data crowd-sourced from DMs who are not necessarily experts to encourage algorithm adoption.
3 Preliminaries
In this section, we first present the problem setup (Section 3.1) and then describe the challenges with the classic 10 pipeline (Section 3.2). Finally, we provide intuition on why robustifying the I0 pipeline would help (Section 3.3).
3.1 Problem Setup
Data generation. Consider a forward optimization problem
FO(O, u): minimize f(0,x) xEX(u))
(I)

---

where x E R" is the decision vector whose feasible region (() is non-empty and is parameterized by exogenous parameters u E TIm" 0 ε Rd is a parameter vector, and f TRadd + the objective function. Suppose u is distributed according to Pu supported on U. There exists a ground parameter vector 0" that is unknown to the DM. Instead, the DM obtains a decision x by solving FO u) where 0 is a noisy perception of 0" We assume that, while the distribution Pe of 0 is unknown, it is supported on a known bounded set Q C TRd and that 0 E e. Let ((eeu)) denote the x U + R be an oracle that returns an optimal solution FO drawn uniformly at random from X (0, u) == argmin {f(0,x) x E {())..
joint distribution of and u,
Objective function. We focus cases where f is linear in 0 and convex in x, i... f(0,x)
Eiela (xf((x)) where fe: R -> IR are convex basis functions. This generalizes the linear objective f(0,x) = xx. Moreover, FO with this objective function can be treated as multi multi-objeccive optimization model, which has been used to model routing preferences (Rönnqvist et al., 2017), radiation therapy planning (Chan et al., 2014), and portfolio optimization (Dong and Zeng, 2021). In this setting, the optimal solution to FO is invariant to the scale of 0, i.e., if E 2 (0, u), then ||0||2 }} without loss of generality.
x E XOPT(33 u) for any 3 E R.. So, we set O = {0 E æd
Learning task. Given a dataset of N decision-exogenous parameter pairs D = {*x, Ug ) we are interested in finding decision policy x 2 + K" to suggest decisions for future u. We require ((u) E (u) for any E U. As discussed later, x (u) is usually generated by solving an optimization model that may have multiple optimal solutions. So consider randomized policies (e.g., uniformly sample from a set of optimal solutions). This is nonrestrictive because a deterministic policy can be recovered from a randomized policy that samples the deterministic solution with probability one.
As a running example, FOP may represent a shortest path problem, where un specifies the origin and destination of a trip, 0" indicates the ground-truth travel times on each road segment, while Og is driver's perception of 0* (i.e., perceived travel times). Decision X corresponds
path taken by driver based on her perceived travel times. Given set of historical trips {us, &s )E[N]. our goal is to derive a routing policy x that can provide path recommendations for future origin-destinate destination pairs.
3.1.1 Assumptions
Assumption (L.LD. Samples). The dataset D is generated using x == x(0ks y uz) where (0), us) are i..dd samples from ((),.)) for all k E [N] Assumption 2 (Bounded Inverse Feasible Set). There exists a constant E E. such that, for any 0, 0' OPT (x, for some & E X(u) and u E U. we have 10 0'112 S 17, where
OPT xx u) = {0 E Rd x X (0, u), |0|| = =1]
(2)
Assumption 3 (Bounded Divergence). There exists a constant a E TR, such that [[((0) 0" S
Assumption is standard in the ML and IO literature. Assumption is mild because θ OPT (x, u) is by definition bounded and is usually much smaller than @. Assumption 3 states that the l2 distance between the expected perceived parameters and the ground-truth parameters upper bounded. is reasonable in many real-world settings. For example, a driver's perceived travel cost (0) should not be too different from the travel time (0") as the latter is an important factor that drivers consider.
3.1.2 Evaluation Metrics
Definition 1.
The actual optimality gap (AOG) of decision policy & is defined as (0", x(()) - f (0", x(0 u))]
AOG(X) E Ef
where the expectation taken over the joint distribution of the random variable u and the decision sampled using the possibly randomized policy x.
Definition 2. The perceived optimality gap (POG) of decision policy & is defined as
POG(x) : EE (())( - - (0.u) uo.u))
where the expectation is taken with respect the randomness in Q, u, and possibly x.
3

---

AOG is an objective performance measure. Achieving low AOG means that x can generate high- quality decisions. In contrast, POG is subjective measure that depends on the DM's perception of the problem. Achieving low POG is critical to mitigate algorithm aversion (Burton et al., 2020).
3.2 An Inverse Optimization Pipeline
Finding x is challenging for three reasons. First, unlike many ML tasks where the prediction target is unconstrained, we require x(u) to be feasible to FO which may involve large number of constraints. Supervised learning approaches that predict & based provide feasibility guarantees. An optimization module is often needed to recover feasibility or produce feasible solutions based
often fail they typically do not
and some estimated 0. Second, we do not directly observe 0* or 0, which precludes using classic ML techniques estimate them. Finally, AOG and POG may not necessarily align with each other, so we are essentially dealing with a bi-objective problem.
Standard lo Pipeline
Conformal 1o Pipeline
1. inverse problem
forward problem
1. data split
do validation
3. calibration problem
uncertainty
>>
4. robust forward
2. Inverse problem
decision data
decision data
point estimate
decision prescription
problem
training
point estimate
decision
prescription
Figure
Classic and conformal 10 pipelines.
In light of the first two challenges, a classic I0 pipeline (visualized in Figure 1) has been proposed to first obtain point estimation 0 of the unknown parameters and then employ policy X1o (u) := (Rönnqvist et al., 2017; Babier et al., 2020). Specifically,
(0, u) to prescribe decisions for any we can estimate the parameters by solving the following inverse optimization problem
IO (D) minimize OE
Σ KE[M]
l (Xt.
(OPT(A, u&)),
(5)
N
where é is non-negative loss function that returns 0 when & E XO uz). For instance, the following loss function is commonly used the literature.
Definition 3. The sub-optimality loss of O is given by
Es X (0, u)) = max f(0,x) f(0,xx. xEX(u)
The sub-optimality loss penalizes the optimality gap achieved by the observed decision under the estimated parameters. As remarked by Mohajerin Esfahani al. (2018), this loss function has better computational properties than its alternatives as it is convex in the unknown parameters. In fact, when the dataset D is large in size and the unknown parameters 0 are high-dimensional, the sub-optimality loss is usually the only loss function that leads to a tractable inverse problem, although it does not enjoy properties such as statistical consistency (see Chan al. (2023b) for detailed discussions). While such a trade-off is acceptable in some applications, we suggest that it is undesirable in our setting because the resulting policy can achieve arbitrarily large AOG and POG. To see this, consider the following example that satisfies Assumptions 1-3. This example is visualized in Figure 2.
Example 1. Ler FO (0, u) be the following problem
minimize
0101 0222
(7a)
subject to
+ uz2
(7b)
0 < r S
(7c)
0 E < 2.
(7d)
Let the ground-truth 0" (cos(T/ /4), sin (44) and l {u} where > 1 is real constant. We are given dataset D u) 8=1 where X; = x0 u) with O2 uniformly and independently drawn from O {(cos 6, di o (0, m/2) for all k [N].
N

---

Classic 10
Conformal 1O
2
x 1
X1
X1
Figure 2: Illustration of Example 1. The gray areas are the feasible region (u). The black arrows are the ground-truth parameter 0* The gray arrows are the extreme rays of O The blue and green arrows are the point estimation 0. The green area is the uncertainty set C(O, a). The black circles are the optimal solution to FO u). The blue and green circles are the suggested decisions. Note that X10 may suggest any decisions on the facet of xı + uz2 u, which are omitted for clarity.
Lemma In Example 1, let ON denote an optimal solution to IO(D) with the sub-optimality loss (6), we have P x0 = 0.) + as N + oc, where 0, == (I/VI+ u² u/ u/v.+++//
Lemma shows that, when using ID(D) with the sub-optimality loss to estimate the unknown parameter in Example the probability of the estimated parameter being 0n converges to one asymptotically, This implies that asymptotically we are almost certain that Xıo (r) = x(0., u), i.c. the policy that samples uniformly from the facet corresponding the constraint #1 + ur2 2 u. As result, &10 can achieve arbitrarily large AOG and POG when u is set to a large enough value.
Proposition 1. In Example 1, let (1) = 8(Ow. u). For any E R4 there exists some ū > 1 such that AOG((10) >> and POG(x1o) f.for any u
3.3 Robustifying the Inverse Optimization Pipeline
A natural idea to improve the AOG and POG of & is to robustify the decision pipeline. Specifically, instead of solving FO with some estimated parameters 0, we solve the following robust forward optimization problem with uncertainty set around to preseribe decisions (final steps in Figure 1).
RFO (C(0,.), u)
minimize maximize f(0,x) x)
(8)
xEX((u) (cC(0,a))
where C is an uncertainty set with 0 being its center and representing parameters that control its shape/size. Given the support set defined in Section 3.1, we focus on the following uncertainty set.
C(Ø a) == (0 Rd 110122 = 1, e 2 cos }
(9)
where a E (0, x] represents the max angle between 0 and any vector in the uncertainty set.
Remark An alternative approach to robustify the 10 pipeline is to replace IO with distribution- ally robust 10 for parameter estimation (Mohajerin Esfahani et al., 2018). However, this approach would not help as 9u is still optimal to the distributionally robust 10 in Example 1. So, the AOG and POG can still be arbitrarily large. See Appendix A.3 for complete statement and discussions.
Now, in Example 1, we analyze the performance of policy that utilizes RFO to prescribe decisions. Lemma 2. In Example 1, let Scro(u) be an optimal solution to RFO (C(O N, a),,u) where ON an optimal solution to (O(D) with the sub-optimality loss (6). When a e (0, 7/2), we have P [AOOG(xio) = and [POG(XcIO) < T/2V2 + 1 as oc.
Lemmas shows that, when using RFO to prescribe new decisions, the probability of achieving upper-bounded AOG and POG converges to one as N goes to infinity, long as E (0, r/2). These bounds are independent of u, in contrast to the AOG and POG of classic 10 that can be arbitrarily large as u changes (Proposition 1). However, the performance of this approach still depends on the choice of a, which non-trivial when FO more complex than tvo-dimensional linear program. We address this problem next.
5

---

4 Conformal Inverse Optimization
In this section, we present a principled approach to learn uncertainty sets that lead provable performance guarantees. As presented later, the learned uncertainty set contains parameters that make the next DM's decision optimal with a specified probability. We call this approach conformal I0 due to its connection to conformal prediction (Vovk et al., 2005), which aims to predict a set that contains the next prediction target with a specified probability. Our approach first converts each context-decision observation (ug, Xx)) to a parameter set @ (u,T, Xx) that contains all the parameters that explain &2 under ug. We then adapt conformal prediction to produce a set that has probability of containing at least one member of the next sampled @ (u, x). Note that if e gPPT (u, O X) is a singlcton almost surely, the approach is equivalent to applying conformal prediction to 0g directly. As illustrated in Figure there are three training steps in conformal IO: i) data split, ii) point estimation, and iii) uncertainty set calibration. We present these steps in Section 4.1 and analyze the properties of conformal I0 Section 4.2.
4.1 Learning an Uncertainty Set
Data split. We first split the dataset 'D into training and validation sets, namely Dimin and Dval. Let Krrain and Kvvi index Drain and Dval, respectively, while Nuain |Pinin| and Nval = PDaal
Point estimation. Given a training set Dusin. we apply data-driven I0 techniques to obtain a point estimation 0 of the unknown parameters. The most straightforward way is to solve I0 (Paan)) with any loss function. Alternatively, one may consider using end-to-end learning and optimization methods that do not require observations of the parameter vectors, e.g., the one proposed by Berthet et al. (2020). The point estimation can also come from other sources, e.g., from an ML model that predicts the parameters. Our calibration method is independent of the point estimation method.
Uncertainty set calibration. Given a point estimation 0, we calibrate an uncertainty set that, with a specified probability, contains parameters that make the next observed decision optimal. This property is critical for the results in Section 4.2 to hold. While we can naively achieve this by setting a = n, the resulting RFO may generate overly conservative decisions. Hence, are interested in learning the smallest uncertainty set that satisfies this condition. We solve the following calibration problem
CP (0, Deal, 7):
minimize a. a.(0))kEKu
(10a)
subject to
Xx E XOPT (0x, uz), Ak E Kvval
(10b)
Σ 0 E C(O, 2 (Nval + 1)
(10c)
Ke
|00|12 = 1, Vk E Krval 5
(10d)
(10c)
where decision a controls the size of the uncertainty set, 0g represent a possible parameter vector
associated with data point & E /Cvat 7 E [0, 1] is DM-specified confidence level. Constraints (10b)
ensure that O₂ can make the decision & optimal for E Kvaa- Constraint (10c) ensures that at least ((Naal + 1) of the decisions in Deal can find vector in C that makes it optimal. Constraints (10d) ensure that the parameter vectors are on the unit sphere as defined in Equation (9).
Remark 2 (Optimality Conditions). The specific form of Constraints (10b) depends on the structure FO. For example, when FO is a linear program, Constraints (10b) can be replaced with the dual feasibility and strong duality constraints. When the FO a general convex optimization problem, we can use the KKT conditions. For non-convex forward forward problems, we can replace Constraints (10b) with f(O,. xx) S f(0x, for all x E X(),, which can be generated in a cutting- plannngg-panegeae fashion.
Remark 3 (Feasibility). For CP to be feasible, we require, for each observed decision, there exists a O E θ that make it optimal. This condition holds for a range of problems, e.g., routing problems and the knapsack problem, even if the DM is subject to bounded rationality, i.e., the DM settles for suboptimal solutions due to cognitive/computan violated, we may pre-process Dont to project & point in X X(u) such that the condition is satisfied.
limitations. For problems where this condition is
Solving CP hard. First, CP is non-convex due to Constraints (10d). Second, Constraints (10b) involve the optimality conditions of Nyat problems, the size of CP grows quickly as Noal in-

---

creases. Nevertheless, considering large Daa is critical to ensure desirable properties of the learned uncertainty set (Section 4.2). Below we introduce a decomposition method to solve CP efficiently. Theorem 1.
Let Dunt be dataset, Y [0,1], 0 E R operator that returns the 7th largest value in set. The optimal solution CP Dval, 7) is 04 == arccos (T~ (EK,)) with C* == maxe, {0TO X E XOPT ub), 0 10 = 1
[> + 1)] and I be an
Theorem 1 states that we can solve CP by first solving Nuai optimization problems whose size is independent of Nval and then find a quantile in set of Naai elements. The first step is parallelizable and the second step can be done in O (N log(r)) time. Since the problem required for evaluating Ck is a maximization problem, we can replace the constraint |00x122 = 1 with ||0x122 S if IR4.
so this problem is convex when the forward problem is linear program.
4.2 Properties of Conformal 10
Theorem 2 (Uncertainty Set Validity). Let Daa be a datasel that satisfies Assumption 1, (0, u) be new i.i.d. sample from (( u), X = x= u), θ == OPT (Xt, u), and aty be an optimal solution to CP (0, ?)) where 0 E Rd. We have, for any y (v,N/a/(N + 1)}, that
P (( # Φ0 27
(11)
For any E [0, 1), with probability at least 1 - 1/Nval.
P ( - s <((Nua)
8 llog(Nnl + 1) log Nvoi
2 Nuai
(12)
Nvat
Theorem 2 states that our learned uncertainty set conservatively valid and asymptotically exact (Vovk et al., 2005). More specifically, first, our method will produce set that contains a 0 that makes the next DM's decision optimal no less than 7 of the time that it is used (conservatively valid). The probability in Inequality (11) is with respect to the joint distribution over DDai and the new sample. Second, once the set is given, we have high confidence that, the probability of the next DM's decision being covered is within e(Nvaa) from y. The probability in Inequality (12) is with respect to the new sample, while the high confidence is with respect to the draw of the validation data set. Overall, we have the almost sure convergence of ( n C(O, ar)) * Ø) to y as N goes to infinity. Finally, we note that in many practical applications, the number of decision observations N can be quite large. For example, in our motivating example, rideshare platforms observe millions of trips on a daily basis, providing ample data for both point estimation and uncertainty set calibration in pipeline.
Now, we relate the validity results to the performance conformal IO. The following Lemma an immediate result of the objective function f being linear in 0.
Lemma 3. For any & E x (0, u) and (0.u) E e x U, there exists constant v (x) E R2,, such that, for any 0, 0' E O we have f (0, f (0', s v (x) 0 0'112.
Theorem 3 (POG Bound). Let (u) be an optimal solution to RFO (C(O, a1), u) for any u E El, where 0 E Rd and on are chosen such that,, a new sample (0', u') from P(e.ur () and x' = x(0', u1),
P (c) an) n (u'xx') + 2) = 1. If Assumptions 2-3 hold, then
POG(XcIo) < (1 - 2 cos 2a; + 2)μ + npcIo,
(13)
and
AOG(Xcro) S (2 2--220 cos 2011 + 17 0) + (1 + d) where μ Elp((((0, u))]. PC10: == E(v|xcio and μr == (v (v|x(0", u)]).
(14)
Theorem states that, when C(0, contains a 0 that makes the next DM's decision optimal almost surely, conformal 10 achieves upper-bounded POG and AOG. While we can meet this condition by
using a large the bounds would be large as they increase as a increases, reflecting that the decisions may be overly conservative. Instead, we can use CP to obtain a that achieves close-to- 100% coverage and possibly add small A R4 as extra protection. Moreover, we show in Section 5
7

---

that, when using 7 < 100%. conformal 10 still demonstrates favorable performance compared to classic IO. Our bounds have cooblem-speciffee constants. To demonstrate tightness, we present their numerical values in Example with a π/ /4 (Table 1). They closely follow the performance of conformal IO, which outperforms classic IO by a large margin.
Table Performance profile of classic and conformal IO in Example
AOG
POG
2
10
50
100
2
10
50
100
Classic 10
0.35
3.18
17.32
35
0.74
4,55
24.51
49.50
Conformal 10
0.00
0.00
0.00
0.00
0.70
0.16
0.03
0.02
Conformal IO bound
0.70
0.05
0.002
0.001
1.58
0.67
0.15
0.08
5 Numerical Studies
Data generation. We consider two forward problems: The shortest path problem (linear program, d = 120) and knapsack problem (integer program, d = 10). See Appendix C.2 for their formulations. We use synthetic instances, which is a common practice as there no well established IO benchmark (Tan al., 2020; Dong et al., 2018). For both problems, parameters 0" and a dataset of N = 1000 DMs. For each DM k E [N]. we generate her perceived parameters 0j = (0 * p + c + 6n for i E [d] where pi. is uniformly drawn from [1/2, 2]. cj drawn from normal distribution with mean 0 and standard deviation 1, and 6g 0.1. For the shortest path problem, parameters uN represent a random rigin-destination pair on the network. For the knapsack problem, ug correspond to the weights different items and the DM's budget. The item weight w' for E [d] are uniformly drawn from [1, 10] and are shared among DMs. For each DM E [N], we generate budget uy = ql Σ, w where q uniformly drawn from [1/5,5].
randomly generate a ground-trute
Experiment design. Conformal I0 is compatible with any approach that can provide point estimation unknown parameters using decision data (Step 2 in Section 4. 4)... To the best of our knowledge, i) IO with the sub-optimality loss and ii) the PFYL approach from Berthet et al. (2020) are the only two methods that can perform this task at scale. We thus implement conformal IO with these two methods. They also serve as our baselines. We call both i) and ii) classic 10 to emphasize that they rely on a point estimation for decision prescription, although PFYL not an IO approach. See Appendix C for implementation details. In all experiments, conformal IO uses the training set for point estimation and the validation set for calibration, while classic IO uses the union of the training and validation sets for point estimation. So, they have access to the same amount of data and are evaluated on the same test set. Unless otherwise noted, experiments are based on 60/20/20 train-valice wwwidation-tesseeeeeeee -est split and are repeated 10 times with different random seeds.
Uncertainty validity. To verify Theorem 2, we empirically evaluate the out-of-sample coverage achieved by our uncertainty set under different target levels 7 and sample sizes N The point estimation generated by IO with the sub-optimality loss. As shown in Figure 3, when the validation set is small (N.a 10), we always achieve the specified target but C(θ, a.,) tends to over-cover (conservatively valid). When using larger validation sets (Nvat E {100, 200})), our coverage level gets closer to the specified y (asymptotic exact). These empirical findings echo our theoretical analysis.
Empirical Coverage (%))
Shortest Path
Empirical Coverage (%6)
Knapsack
90
70
70
Target
Nyw 10
50
Nv 100
30
30
N 200
10
10
30
50
70
90
10
30
50
70
90
Target Coverage y (%)
Target Coverage y (%6
Figure 3: Empirical coverage achieved by the learned uncertainty set (error bar range).

---

The value of robustness. As shown in Figure 4, solving RFO with an uncertainty set learned by conformal IO leads decisions of lower AOG and POG, compared solving FO with a point estimation from classic IO, On average, when varying 7 our approach improves AOG by 20.1-30 1-30.4% and POG by 15.0-23.2% for the shortest path problem, and improves AOG by 40.3-57.0% and POG by 13.5-20. % for the knapsack problem. The improvement is orthogonal to the point estimation method. Our decisions are higher quality and better align with human intuition than classic IO. Finally, the performance of conformal IO generally improves as the quality of the point estimate increases (see Appendix D for details). Therefore, even though the conformal IO pipeline is robust to estimation errors, using the best available point estimation method is still recommended.
Shortest Path 10
Shortest Path -
Knapsack 10
Knapsack
13
AOG
POG
*OG
11
FO RFORFORFORFORFO (10130)550170199))
FO RFORFORFORFORFO (10130)(50171199)
FO RFORFORFORFORFO (10(30)550000199)
FO RFORFORFORFORFO
(101300(50X701199
Shortest Path PFYL
Shortest Path PFYL
Knapsack PFYL
Knapsack PFYL
AOG
2-
2
RFORFORFORFORFO (10))30)15)(100099
RFORFORFORFORFO (101(301501170199)
RFORFORFORFORFO (101(30)55))00119)
RFORFORFORTORFO (101(30(50)
Figure 4: Performance profile of classic (blue) and conformal 10 (green).
Computational efficiency. As shown in Table 2, conformal IO and classic 10 require similar training times. When FO is an integer program (knapsack), the training of conformal IO is even faster because it replaces a relatively large inverse integer program (associated with Dirain U D.aa), which is notoriously difficult to solve (Bodur al., 2022), with smaller inverse integer program (associated with rrain) and a set of small calibration problems that are parallelizable (Theorem 1). At the prediction time, our method achieves lower AOG and POG at the cost of solving a more challenging RFO. Nevertheless, the solution time of RFO is within one second in our instances.
Table 2: Average (std) computational time of classic and conformal 10 in seconds.
Training
Prediction (per decision)
Problem
Classic 10
Conformal IO
FO
R.FO
Shortest Path
0.18 (0.02)
0.27 (0.03)
0.01 (0.00)
(0.12)
Knapsack
2.47 (0.37)
1.95 (0.32)
0.01 (0.00)
0.44 (0.15)
Important hyper-parameters. Finally, we provide empirical evidence that sheds light on the choice of two important hyper-parameters in conformal IO: i) confidence level 7, and ii) train-validation split ratio. Regarding 7, as shown Figure 4, the performance of conformal IO improves quickly as increases from 50% and remains stable and even worsens slightly after that. Hence, is possible to improve the performance of conformal I0 by carefully tuning 7 using cross-validation However, this requires an additional validation dataset. If such a dataset is unavailable, setting 7 a relatively large value (e.g., 0.99) usually yields decent performance, which aligns with our theoretical analysis. Regarding train- vaiinvvaiiattinn split ratio, intuitively, both the estimation and calibration can benefit from more data. However, when the dataset is small, we need to strike balance between these two steps aiming to achieve lower AOG and POG. We implement conformal IO for the shortest path problem under different dataset sizes (Nirin + N.a)) and train-validation split ratios (Nvat/ (Nirain + Nva)).. As shown Figure 5, when the dataset small, there is no benefit of using conformal because we do not have enough data to obtain good point estimation and uncertainty set simultancously. However,

---

the performance of classic 10 quickly plateaus as the dataset grows. When given a mid- or large-sized dataset, we can generally benefit from putting more data in Paal, echoing our theoretical analysis.
AOG
Used for Validation
POG
% Used for Validation
20%
-55
-11
2
3
5
20%
-34
-8
1
8
40%
22
19
40%
-12
14
16
60%
-7
13
11
24
25
60%
-4
14
19
80%
-13
20
9
23
14
80%
-10
8
2
15
11
%
160
480
640
800
160
320
480 640 800
# of Observed Routes
# of Observed Routes
Figure 5: Percentage reduction in AOG and POG when using the conformal I0 classic IO.
Conclusion and Future Work
In this paper, propose conformal IO, a novel IO pipeline recommend high-quality decisions that align with human intuition. We present new approach to learning uncertainty sets from decision data, which is then utilized in robust optimization model to prescribe new decisions. We prove that conformal IO achieves bounded optimality gaps, as measured by the ground-trute parameters and the DM's ss perceived parameters. We demonstrate the strong empirical performance of conformal IO via extensive numerical studies. Finally, we highlight several challenges that underscore future research directions. First, we focus on objectives that are linear the unknown parameters. While such objectives are ubiquitous in practice, it is of interest to extend our results for general convex objectives. Second, the robust forward problem, while leading to better decisions, is computationally more costly than the forward problem. Future research can be done to accelerate its solution process. Finally, while Conformal IO consistently outperforms classic 1O when the point estimation methods fixed, computational experiments suggest that its performance hinges the quality of the point estimate. Future research could explore point estimation methods that directly optimize the performance of the downstream robust optimization model.
Acknowledgments
The authors grateful to the anonymous reviewers for their valuable feedback and insightful comments. Erick Delage was partially supported by the Canadian Natural Sciences and Engineering Research Council [Grant (GPIN-2022-0522 and by the Canada Research Chair program [950- 230057].
References
Ahuja, R. K. and Orlin, J. B. (2001). Inverse optimization. Operations Research, 49(5):771-783.
Aswani, A., Shen, Z.-J., and Siddiq, (2018). Inverse optimization with noisy data. Operations Research, (6(3):870-892.
Babier, A., Mahmood, R., McNiven, L., Diamant, A., and Chan, T. (2020). Knowledge-baid automated planning with three-dimensional generative adversarial networks. Medical Physics, 2772)3297-306
Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.-P., and Bach, F. (2020). Learning with differ- entiable pertubed optimizers. In Advances in Neural Information Processing Systems, volume 33, pages 9508-9519.
Bodur, M., Chan, T. C., and Zhu, (2022). Inverse mixed integer optimization: Polyhedral insights and trust region methods. INFORMS Journal Computing, 34(3):1471-1488
10

---

Burton, J. W., Stein, M.-K., and Jensen, T. B. (2020). A systematic review of algorithm aversion in augmented decision making. Journal Behavioral Decision Making, 33(2))220-2339
Chan, T. C. Y., Craig, T., Lee, T., and Sharpe, M. B. (2014). Generalized inverse multiobjective optimization with application cancer therapy. Operations Research, 62(3):680-695.
Chan, T. C. and Kaw, N. (2020). Inverse optimization for the recovery of constraint parameters.
European Journal of Operational Research, 282(2):415-422
Chan, C. Y., Lee, T., and Terekhov, D. (2019). Inverse optimization: Closed-form solutions, geometry, and goodness of fit. Management Science, 65(3):1115-1133
Chan, T. C. Y., Mahmood, R., O'Connor, D. L., Stone, D., Unger, S., Wong, K., and Zhu, I. (2023a). Got (optimal) milk? pooling donations in human milk banks with machine learning and optimization. Manufacturing & Service Operations Management, O(0).
Chan, T. C. Y., Mahmood, R., and Zhu, I. Y. (2023b). Inverse optimization: Theory and applications. Operations Research, 0(0).
Chen, V., Liao, Q. V., Wortman Vaughan, J., and Bansal, G. (2023). Understanding the role of human intuition on reliance in human-Al decision-making with explanations. In Proceedings of the ACM on HumannCCmmptte Interaction, volume 7, pages 1-32.
Chenreddy, A. R., Bandi, N., and Delage, E. (2022). Data-driven conditional robust optimization. In Advances in Neural Information Processing Systems, volume 35, pages 9525-9533
Christiano, P. F. Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. (2017). Deep reinforce- ment learning from human preferences. In Advances in neural information processing systems, volume 30.
Delage, E. and Ye, Y. (2010). Distributionally robust optimization under moment uncertainty with application to data-driven problems. Operations Research, 58(3):595-61
Donahue, K., Kollias, K., and Gollapudi, S. (2023). When are two lists better than one?: Benefits and harms in joint decision-making, arXiv preprint arXiv:2308. 11721.
Dong, C., Chen, Y., and Zeng. B. (2018). Generalized inverse optimization through online learning. In Advances in Neural Information Processing Systems, volume 31.
Dong. C. and Zeng, B. (2021). Wasserstein distributionally robust inverse multiobjective optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, number 7 in 35, pages 5914- 5921.
Elmachtoub, A. N., Lam, H., Zhang, H., and Zhao Y. (2023). tssimate-heen-optiiize ver- sus wttp:/ddddsssiimaiiioottiiiiioii A stochastic dominance perspective. arXiv preprint arXiv:2304.06833.
Gao, R. and Kleywegt, A. (2023). Distributionally robust stochastic optimization with wasserstein distance. Mathematics of Operations Research, 48(2):603-655.
Hu, X., Cirit, O., Binaykiya, T., and Hora, R. (2022). DeepETA: How uber predicts arrival times using
deep learning. Uber Engineering Blog. Available at http:://www...abboooo//o//////// how-uber- ----ubberrrrddct---- -er---avvvav-iiieeeee Accessed: 2024-01-19.
Ji, J., Qiu, T., Chen, B., Zhang, B., Lou, H., Wang, K., Duan, Y., He, 7.,, Zhou, J., Zhang, 7.,, et al. (2023). AT alignment: A comprehensive survey. arXiv preprint arXiv:2310.19855
Liu, M.. Tang, X., Xia, S., Zhang, S., Zhu, Y., and Meng, Q. (2023). Algorithm aversion: Evidence from ridesharing drivers. Management Science, 0(0).
Mandi, J., Bucarey, V., Tchomba, M. M. K., and Guns, T. (2022). Decision-focused learning: through the lens of learning to rank. In International Conference on Machine Learning, pages 14935-14947. PMLR.
11

---

Merchán, D., Arora, J., Pachon, J., Konduri, K. Winkenbach, M.. Parks, S., and Noszek, J. (2022). 2021 Amazon last mile routing research challenge: Data set. Transportation Science, 0(0).
Mohajerin Esfahani, P., Shafieezadeh-Abadee S., Hanasusanto, G. A., and Kuhn, D. (2018), Data- driven inverse optimization with imperfect information. Mathematical Programming, 167:191- 234.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2018). Foundations of Machine Learning. MIT press.
Ng. A. Y. and Russell, S. (2000). Algorithms for inverse reinforcement learning. In Proceedings of the Seventeenth International Conference on Machine Learning, page 663-670.
Nguyen, T. (2015). ETA phone home: How uber engineers an efficient route. Uber Engineering Blog. Available at 2024-01-19.
Accessed:
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. (2024). Direct preference optimization: Your language model is secretly a reward model. Advances Neural Information Processing Systems, 36.
Rönnqvist, M., Svenson, G., Flisberg, P., and Jönsson, L.-E. (2017). Calibrated route finder: Improving the safety, environmental consciousness, and cost effectiveness of truck routing in sweden. Interfaces, 47(5)3372-395.
Shafer, G. and Vovk, V. (2008). tutorial on conformal prediction. Journal of Machine Learning Research, 9(3).
Sun, C., Liu, L.,, and Li, X. (2023). Predict-then-calibaae:: A new perspective of robust contextual LP. Advances Neural Information Processing Systems.
Sun, J., Zhang, D. J., Hu, H., and Van Mieghem, J. A. (2022). Predicting human discretion to adjust
algorithmic prescription: A large-scale field experiment in warchouse operations. Management Science, 68(2):846-865.
Tan, Y., Terekhov, D., and Delong, A. (2020). Learning linear programs from optimal decisions. In Advances in Neural Information Processing Systems, volume 33, pages 19738-19749.
Tang, and Khalil, E. B. (2024). PyEPO: pytorch-based end-to-ent preiect-hennoptinmee library for linear and integer programming. Mathematical Programming Computation, 16(3):297-335.
Vovk, V., Gammerman, A., and Shafer, G. (2005). Algorithmic learning in random world, vol- ume 29, Springer.
Wainwright, M. J. (2019). High-dimensional Statistics: A non-Asymptotic Viewpoint, volume 48. Cambridge University Press.
Wilder, B., Dilkina, B., and Tambe, M. (2019). Melding the data-decisions pipeline: Decision-focused learning for combinatorial optimization. In Proceedings the AAAI Conference on Artificial Intelligence, volume 33, pages 1658-1665.
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, (2017). A survey preference- reinforcement learning methods. Jouraa of Machine Learning Research, 18(136):1-46
Wu, F., Ke, J., and Wu, A. (2024). Inverse reinforcement learning with the average reward criterion. In Advances Neural Information Processing Systems, volume 36.
Zattoni Scroccaro, P., Atasoy, B., and Mohajerin Esfahani, P. (2024). Learning in inverse optimization: Incenter cost, augmented suboptimality loss, and algorithms. Operations Research, 0(0).
12

---

A Omitted Statements and Proofs in Section 3
A.1 Poof of Lemma 1
Proof. We first show that & E {(0, 1), (u, 0}} almost surely. Let 8, == arccos (1/ (1/vI+ + so
cos d. 1/v1++ u² and sin 5w u/vi+ u²a It is easy to verify that, when 0% E O
{(cos 6, sin si 8 E (0,6ul}, we have & x(();, u) (0, 1) almost surely; When 0z E O2
{(cos 6, sin 6) 5 E (6u, m/2)] we have x - x(Ok.. u) = (u, 0) almost surely. Since 9, is uniformly
distributed in 0 E O ④ 2g the distribution of &2 is
(0, (), w.p. 20w/T (u, 0), w.p. (TT 28.)/TT.
& =
(15)
Given sample set D {u,, X KE(N) let N1 and N2. respectively, denote the numbers of (0, 1) and (u, 0) in D. We next show that when N₂ and N₂ > O, 02 is the unique optimal solution to (D) Specifically, in Example 1, (D) is presented as follows.
N1
N2
0 == argmin o
1 ( +
N (2(
(16)
N
where
(0) = f0,
if 0 E 01, if 0 E 02, ul1
(17)
02
and
Uu0
02,
if 0 E O if 0 E 62-
(0)
(18)
0,
simple calculation gives that when N1 and N₂ > O, the minimum is 0 which occurs uniquely
at 0 (cos ou, sin 6w); When N2 = 0. the minimum is 0 which occurs when O E 11; When N1 = 0. the minimum which occurs when 2 Therefore, we have
P(NNN2 0) P (ON (cos 6u, sin 6..)) 1.
(19)
Given the probability distribution given in Equation (15) and that is generated using i.i.d. samples from 18, have
20 -20m
N
25
N
N2 0) =
(20)
π
which converges N goes infinity. Therefore, conclude that P(Ox (cos 8u, sin kw)) converges to as N goes to infinity.
A.2 Proof of Proposition
Proof. We first consider the AOG and POG of the decision policy Xio(u) = x(0., u) separately in the following two lemmas.
Lemma 4. In Example I, let (1) x(O.. u). For any E Ry there exists some ū > 1 such that AOG(X1o) > for any u > DAOG-
Proof. According to the definition of x, we know that (i)(u) is uniformly drawn from
(0., OPP XOPT(O.., u) - { ut
te [o, vo. u2 +1
(21)
Since the ground-truth 0* = (cos( T. /4), (in()//4).. the true optimal solution is x*x = (0, 1) with f(0","u u) = 2/2. Hence, we have
AOG +
22
11
t
ut
dt V2 V2(u 1)
+ Vu² +1
(22)
2
Vu +1
4
Therefore, for any v R2,, there exists ūAOG GAOG-
2/2v + such that AOG(X1o) > v for any
13

---

Lemma 5. In Example 1, let xio(u) = x(0 u). for any E E. there exists some ūPoG > 1 such that POG( > y for any u DPoG-
Proof. According to the definition of &, xio(u) is uniformly drawn from
( =
ut
t
tE (0, No
(23)
22
It is easy to verify that, when 0 E ④ == {(cos 6, sin 6) 1 (0,8wl), we have &2 x(0, u) (0,
with f(0, u) 82 almost surely; When 0 O == {(cos ö, sin 5) 8 (6u, a/2). we have
&s x00 u) = (u, 0) with f(O, u) = ud1 almost surely. Since the optimal solution drawn from X'OPT (On, u) is independent of the DM's perception 0, we have
V1241
ut
sin 8 sin d dõ (1- Vu² +1
POG =
COs ò +
Vu
u
+
+
2
vuz+1
1
c (1
1
sin d - u cos 8
dt d8
bb
Vu²
V uu= +1
V u2² +
1 6b
x=/2
(ucos
sin 8) d8
(-ucos 8 + sin 8) d8
2
" u+1
V 1
u
2
0 1
2
The inequality holds because vI u² u. Therefore, we have, for any v R4, there exists ÜPOG = 2t 1 such that (OG( for any u > ŪPOG.
Based on Lemmas and 5, we conclude that for any e E R4, there exists ū = max BAOG. (poo] 2/2v + such that AOG(()o) > v and POG(X1o) for any u > u.
A.3 Robustifying the Inverse Problem
An alternative approach to robustify the classic 10 pipeline is to solve distributionally robust inverse optimization problem. Specifically, consider the following loss function proposed by Mohajerin Esfa- hani et al. (2018).
Definition 4. The distributionally robust sub-optimality loss of is given by
EDR-S (0) := sup
pa [Ls (x, X u.)]
(24)
(F..)
where Pu,s is the sample distribution D. D. (F u.)) is p- Wasserstain ball of radius centered at P Pu,e and pd is a risk measure, e.g., the value risk.
The distributionally robust inverse optimization problem is
DRIO(D) minimize o0e
(0).
(25)
As shown by Mohajerin Esfahani et al. (2018), the estimated parameters from DRIO achieve bounded out-of-sample sub-optimality loss with a high probability. However, this does not imply bounded AOG and POG for the decision policy.
Lemma 6. In Example I, O,, is an optimal solution to DRIO(D).
Proof. As shown in the proof of Lemma 7, when (0, 7/2). the RFO (C(O,, a), u) has unique
optimal solution (0, 1). So {ci((u) = (0, 1) almost surely, when ON O,, and a E (0, - 7/2). is easy verify that, when 0 e e {(cos 6, sin 6) 8 (0, 6w]]. we have x x(0.u) u) (0,1)
14

---

almost surely; When O E @₂ = f(cos d, sin 6) 18 E (ōu, TT2) we have X2 = x((,2) = =u,,0)
almost surely. Hence, we have
POG((cio) = -
8u L/a 2
d0
x
a/2
x sin dõ
cos
7/2
TT
< (26)
b. 2
2
2 + u
2/2
The inequality holds because
>> 1.
0o. So we conclude that, when According Lemma we know that 1p(0N 0.)) + 1 N (0, π 1/2,, have IP [POG(xcIo) < < - ass N
Lemma shows that, in Example I, the estimated parameter from DRIO(D) may still be O.. Hence, the decision policy is identical X whose AOG and POG be unbounded. The fundamental reason behind these negative results is the misalignment between the sub-optimality loss and the evaluation metrics. Achieving low sub-optimality loss means that the suggested and observed decisions are of similar quality as evaluated using the estimated parameters. However, this does not speak to the similarity between these two decisions with respect to the DM's perceived parameters (POG) or the ground-truth parameters (AOG). Therefore, the out-of-sample guarantees on the sub- optimality loss do not translate into bounded AOG POG.
A.4 Proof of Lemma
We consider the AOG and POG conformal I0 separately in the following two lemmas.
Lemma In Example 1, let ScIo(u) be an optimal solution to RFO (C(0,, u).u) where ON is optimal solution to IO(D) with the sub sub-optimality loss (6). When (0, 1/2), have P [AOGG(xcT) = 0] + 1 as N + oo.
Proof. We first show that when 0 = 0,, and E (0, RFO ()) u) has unique optimal solution (0, 1). Let (0, 1), X2 2), X3 (u, 0) and x1 (u, 2) denote the four extreme points the feasible region (()).. respectively, and
R(x) = max 0101 0222. OcC(O...)
(27)
Since FO a linear program, suffices to show that, when a (0, R(xi) < min(R(xx)) R(xa), [(x4)} because, if there exists an optimal solution that is not an extreme point, then there must exist another extreme point x; such that R(x1) R(x;) where * 1. Next, we compare R(x1) with R(x2), R(x3), and R(x:). It is easy to verify that
(in + a), 1,
if (0, - 5ul. if E (x/2 8,,, π 2/2).
R(xi)
(28)
For X2, we have
2 sin((,, a),
if 10, 8u), if (n/2 5,,, π 1/2).
R(x²)=
(29)
2
Hence, we have R(xi)= < R(x2) when a E x0,x
For X3, we have
if (0, 5ul, cosos a),
R(x3)=
(30)
U,
if (8,,, क 7/2).
15

---

Since > 1, we have 2/2- - 6u < TT/<< 6n < x/2.. We will show that R(x1) < R(xs)
when a is
(0, x/2 8,). [m/2 8n, R.). and [6.. x/2). When a (0, x/2 8,). have
R(x1) sin(6, a)
sin 8g cos a + cos 0n sin a
cos a + V + u
sin
V1+ u²
u²
V1 008 ar +
sin
u²
v1 + u²
u
COS a +
sin
vI + u²
v1 + u²
(cos 6 cos sin 8 sin
co - (x) R(xs).
The second line holds due to the sum of angles identity. The third line holds due to the definition of
8u. The fourth line holds because 1. The fifth line obtained by simple manipulation. The sixth line holds due to the definition of 6,. The seventh line holds due to the sum of angles identity.
When a E [2/2- Ow 8w), we have
R(x1)= =1
u
< 1
12 +1
2²
1
Vu
2
Vuz +
Vu²
= u 8n
ssi Sa
Vu² +1
Vu²
< Cucos 8n cos + usi 6, sin
=ccos a)
R(x3).
The second line holds because u 1. The third line is obtained through simple manipulation. The forth line holds due to the definition of 6.. For the fifth line, we know that E [T/2 Sn, 5.) S [T/4- - 7/2] where cos a strictly decreasing Therefore, cos a < cos 8, 1/vu² and sin S sin(11/2 5x) = cos 8, 1/v Hence, the fifth line holds. The sixth line holds due to the sum of angles identity.
a and where sin a is strictly increasing a.
When a E [ōu, R/2), we have R(xi) 1 < u R(xa).
Hence, R(x1)= < R(xs) when a E (0, 722).
For X4, we have
R(x4) max u cos 8 sin 8EC(62.0)
(31)
Let of denote the optimal solution to the maximization problem for calculating R(x;). ). It is easy to verify that o (0, TT 1/2) when E (0, 7 12). So cos of and sin o > Hence, have
u.sos 8 2sin 5 u 07 + 2 8 sin 5 R(x,). R(x,) SEC(6..ar)
(32)
The first inequality holds because dj may be the maximizer of the problem associated with X4- The second inequality holds because > 1, cos 57 > 0, and sin 87 > 0.
Hence, when (0, 2/2), RFO (C(8., a), u) has unique optimal solution x1, so (cjo(u) (0, 1) almost surely. Given that (0, 1) is also the optimal solution to FO u4), we have AOG(X<1o) =
when 0N 0, and (0, r/2). According to Lemma 1, we know that P(Ox 0.,) + 1 as
N + oo. So we conclude that, when a E (0, T 7/2), we have [AOG(xaio) = 0] - as N - oo.
16

---

Lemma 8. In Example 1, let (u) be an optimal solution to RFO (C(ON.a)) where N an optimal solution to IO(D) with the sub-optimality loss (6). When a E (0, 7 we have P [POG() < ग| 2/2v2] + 1 as N + cc.
Proof. As shown in the proof of Lemma 7, when a E 70,) the RFO (C(O., a), u) has a unique
optimal solution (0, 1). So Xcιo(u) (u) = (0, 1) almost surely, when 0N On and E (0, π / It is
easy verify that, when 0 E 0 == {(cos 6, sin 6) |8 (0, 6ul3. we have X x(0. u) (0. 1) almost surely; When 0 E (2 == {(cos 6, sind) 18 E (6u, 2 we have &R = x(0, u) = -u,,)
almost surely. Hence, we have
(OG =
6b.. π
x
d5 +
7/2
x sin 5 dō =
CO8
8/2
T
<
π
(33)
2
bn 2
2
b..
2 u²
2/2
The inequality holds because u 1.
According to Lemma 1, we know that 10 = 0n) - las N + co. So we conclude that, when E (0, 7/2), we have I (POO((cco) < 2/2v2 - as N +
B Proof of Statements in Section
B.1 Definitions
Definition 5 (Empirical Rademacher Complexity). Let F be a class of functions mapping from 2 (2,, Zz,...., Zm } to [a. b) and DD be a fixed sample of size N with elements in Z, then the empirical Rademacher Complexity of F with respect to the sample D defined as
RD((F == E.
sup SEF N
Σ o.f(2.) KE[N]
(34)
where o = (01, (0.,,,,,.. with o; 's being independent uniform random variables taking values in 1-1
Definition (Rademacher Complexity). Let P denote the distribution according to which samples are drawn. For any integer N 2 1, the Rademacher complexity of function class F is the expectation of the empirical Rademacher complexity over the samples of size N drawn from P:
RN (F) = EDapx
(RD(F)
(35)
Definition 7 (Growth Function). Let H be a class of functions that take values in {-1, growth function 11 N + for H is defined as
1}. The
(N) (2, Z2....... ((((())) (Z2)),,(Z2)....).))).)))))) M(ZN)) h HYI
max
(36)
which measures the maximum number of distinct ways in which N data points in Z can be classified using the function class H.
B.2 Useful Lemmas
Lemma 9 (Corollary 3.1 in Mohri et al. (2018)). Let H be class of functions taking values in (1, then, for any integer N 1, the following holds
2 2og (N)
Ry (H) S
(37)
N
Lemma 10 (Theorem 4. 4.10 in Wainwright (2019)). For any b-uniformly bounded class of functions F.
any positive integer N 1. and any scalar 5 O. with probability at least 1 exp (-N8² ((bb)) we have
sup JEF
f(.)) - E[f(x.) & (F)
(38)
N
[E[M]
where R(F) denotes the Rademacher complexity of the function class F.
17

---

B.3
Proof of Theorem 1
Proof. We first present the extensive formulation of Problem (10). For convenience, we define θ₂ = O (ug, &x) for any k E [M] When a E [0, x]. 008 a is a strictly decreasing a. Therefore, minimizing a is equivalent to maximizing the value of cos a. We can replace the decision variable a in Problem (10) with new decision variable e = cos a with an additional constraint with -1 S c S 1. In addition, we introduce a new set of decision variables yı E {0, 1] that indicate if ① intersects with the learned uncertainty set (= 1) or not (= 0) for any l K Problem (10) can be presented as follows.
maximize
(39a)
e. (.(00) (th JecK,,
subject to
* E 2.OPT( uk);
Ak E Kiva
(39b)
0.0 2 c 2(y - -1),
Vk E KGval
(39c)
Σ yk 2 [N + +1]
(39d)
[Qull2 = 1,
Ak E Kval
(39e)
(39f)
yk E (0,1), vk E Kyaa-
(39g)
Constraints (39b) ensure that 02: is member of θ; for any k E K Constraints (39c) decide if 02 should be taken into account when calculating the maximal cosine value based on if θ intersects with C. Constraint (39d) ensures that C intersects with at least [<Na + 1)] inverse feasible sets. Constraint (39e) enforces O2 to be on the unit sphere as defined in Equation (9). Constraints (399)-33g) specify the ranges of the decision variables.
Observing that the objective of Problem (39) is to maximize e and that decision variables 0₂ of different data points only interact in Constraints (39c). We can re-write Problem (39) as
maximize
C
(40a)
subject
c cs Ck 2(( -1),
Vk K
(40b)
Σ yk 2
(N 1)]
(40c)
kEK.
1sc51
(40d)
Ak E Kuals yk E 10,
(40e)
where
C maximize 0%
0
(41a)
subject to &N X (OR, up)
(41b)
|10x112 1.
(41c)
Note that we replace Constraints (39c) with Constraints (41c) because the objective of Problem (41)
to maximize the inner product of 02 and so the maximum only occurs when ||0xll2 1.
We further observe that the optimal solution to Problem (40a) is to set yı = 1 for all k such that
Ck 2 T- ((K.)) and yı = otherwise. Therefore, the optimal objective value of Problem (40a)
is c = Pr ((c*) corresponding to a, = arcoos r (f(se ((cx))en) )
B.4 Proof of Lemma
Proof. Proof. For any fixed x, we have
f f (0',))
Σ (0, 00) f (x)
iE[d
<
S?(x),
Σ (0, 03)2
EE|d]
sE[d]
= (x) 0 0'112
18

---

where v(xt) = VEieta (.) The inequality follows the Cauchy-Schwann inequality.
B.5
Proof of Theorem 2
Proof. We first prove the learned uncertainty set is conservatively valid. Following the conformal prediction language used by Vovk al. (2005), we define a conformality measure each data
point,i.e. an observed decision and exogenous parameter pair, Ag R x U - R as follows
Ax u)
maximize
θT0
(42a)
subject to
+ O u)
(42b)
| 1 1.
(42c)
We note that cı Ag us) for any k E Keaa where Cs is defined in Theorem 1. Let [r( + 1)], and A := (Ap( ue) or equivalently, A ;= {cH)nek,.. Due to the definition of C a0) and that is chosen such that cosa (T(A), the event "O (x, u) n a(0,a) + Ø" is equivalent "Ag(X; u) D (AA",
P ( & u) n C a) # Ø) = (Ap((, (A))
(43)
Assumption 1 implies that the dataset D = Dval U {xx, u)} is exchangeable, i.. the ordering of the data points in D' does not affect joint probability distribution (Shafer and Vovk, 2008).
Therefore, the rank (from high to low) of Ag u) in A' == AU (Ag(R, u}} is uniformly distributed in {1, ........ Nyal + 1). So, we have
? S P (Ag u) (A))
P (A)g(
= 1 P <T)(())))
F (Ag(&, u) 2 (A))
= P ( OPT (x, u) nc(@ a)) + Ø
The first line holds due the definition of r. We obtain the second line by taking the complement of the event in the first line (inside the probability). The third line holds because Ag (X, u) can never be strictly smaller than itself, so any elements A' that are strictly smaller than Ag (X. u) are in A. Note that this line holds only when < N which occurs when y S / (Naal + 1), because A only has Naai elements. We obtain the third line by taking the complement of the event in the second line (inside the probability). The last line holds due to Equation (43), We note that all the probabilities are over the joint distribution of Deal and the new sample, i.e. D'.
We next prove that the learned uncertainty set is asymptotically exact. Let z4 := (UR, 81), 2 = (==) We define function class
H. = [(22, a) 1 O OPT O u) nc(O, a)] a (0,
(44)
Let I1 denote the growth function of as defined in Definition 7. It is casy to verify that (Nval = Nval +
(45)
because the value h(z, a)) is monotonically increasing in a for any fixed z E Z, so changing the value of can only leads to Noal + 1 different outcomes for a fixed dataset Z.
Therefore, according to Lemma 9, we have
2 log( Noai +
Nyw (H)
(46)
Nval
where Rv,,, (H) denotes the Rademacher complexity of H. when sample size is Noal as defined in Definition
We know that the value of a is chosen such that is the smallest value that satisfies
OPT (&t, ue) ue) a)] [NNNa +1]
Σ ())
Σ
1 OP
(47)
N
Nval
Nval
kEKw.
REKi.
19

---

so we have
7
E KEki
hlzz a)) 5
2
(48)
Nval
Nval
The second inequality holds because (N + 1)]
LeaN + Ty LaN + +7] YN 1yNval
La + +71
2
S 7
Nval
va
Nval
N
(49)
Since Deal is iid. sampled, for any fixed a, ExEK, (= a)/Naal provides a sample average approximation to E [2(2, a)), which can be interpreted as (OOPT (xx u) nc(O, ai) for any new sample (6, u) from Pa., and x x(0, u).
By applying Lemma 10, we have, with probability at least ô = 1 - 1/Nual
2 log Naal
h(=2, a:) E [1(2,, a))] S 29 (H) + +1
(50)
Nval K
Nval
By combing (46)-(50), we have, with probability at least 1 - 1/Nval-
8 llog( (Naa + 1) + log Nval
2
PP ((OFT((x -
(51)
Nval
Noal
B.6 Proof of Theorem 3
We bound the AOG and POG of conformal IO separately in the following two propositions.
Proposition (Conformal IO Achieves Bounded POG). Let &CIo(U) be an optimal solution to RFO a1), u) for any u E U. where R and an are chosen such that, for a new sample
(0', u') from (()o.)) and x' = =x00' IP (100,a))ne OPT (u',x) # #2) 1. If Assumptions
2-3 hold, then
(xG I (11- 2 cos 2a, + 2) + 7PCIO where μ == ([ u))] and Pc1o == E(v|xcIo
(52)
Proof. We first bound the perceived optimality gap of a sampled DM. Let (ê, u) be sample from [(o,u). x = x(0, u), (u) denote the optimal solution to the inner maximization problem in RFO (C(0,a1), u) when the outer decision variable is set to Ocio denote the optimal solution the inner maximization problem in RFO (C(0, a1), u) when the outer decision variable set to (u), If OPT (x, u) (( # Ø, let be an element of OPT (x, u) (C(( on), we have
f (0, xcio(u) - (0.x)
< (0, xcio(u) - (0.x) [v(x) + (X)ro
-0
< f (o, (c) f (0.x) + +n(x(x) + (Ecro
< ʃ (OcIo(u), Xcio(u)) / (0,x) + + (x()) (xcio(()))
< (u) f (0.x) + [x( + (xcIo
S <v(x) (c)o - 0/ + [ (1))
5 22 cos 2a1) + (v(x) (u))
= ((X)(1 - cos 20, + 2) + Ty (u))
20

---

The first line holds due to Lemma 3. The second line holds due to assumption 2. The third line holds due to the definition of (u). The fourth line holds because (Xc1o (u). Ocoo (c))(u) is an optimal solution to RFO (C(O, an), u). The fifth line holds due to Lemma 3. The sixth line holds because both (u) and O are in a10,a)) the angle between them is no larger than 2aq. Since both (u) and f are on the unit sphere, the Lg distance between them are bounded by 2(1 cos 201).
Since a is chosen such that IP 4 OPT (x, (c((, .1) = 1, we have
POG(Xc1o) = E f (0, (cio(1)) -f (0.x)
< E (x)x((1 cos 201 + 2) + nu [xcro[u]]}
= μ(11 - 2 cos 201 + 2) + nPCTO
where μ E [x]]]] and PaIO E (v [u)l
Proposition 3 (Conformal 10 Achieves Bounded AOG). Let (uio be an optimal solution to RFO (C(O, (C(0,,n), u) for any u E U, where E Bd and on are chosen such that, for a new sample (6', u') from (()..) and x' = x(0', u'). IP
# Ø) = If Assumptions
2-3 hold, then
AOG(X) S (2 2 cos 2011 + + oOØ" + (1 + o
(53)
where μ²" == [v/x(0," u))).
Proof. We first derive upper bound on the optimality gap of the suggested decision (c)o as evaluated using 0* for any u E U. Let (θ, u) be a sample from P(o.n). x(0 u), and @ be an element of O OPT (&, u) (C(( a1), which is non-empty almost surely because 0₁ is chosen such that P OPT (x. u) ((0,a))) = 1. Let (c denote the optimal solution to the inner maximization problem in RFO (C(O, a1), u) when the outer decision variable is set to &cIo (u). For any u E U, let x" (u) == x(0", u) and Oc1o (u) denote the optimal solution to the inner maximization problem in RFO (C(0, a1), u) when the outer decision variable is set to x" (u), we have
f f0", Xcro(u)) - f x0"xx"(x) (u))
sf ((00) (u) - (E(0). x (u)) + (v [xcoo (u)] + v [x (x)) | B(0)1l2
$ ((O), XcIo (u)
- - (E(0), x (u))
+ to (v ( (u)) + / [x (n)))
E f (0, Xcr((u)
- -1 (0,xx
+ o (M [xcro + (x' (u))
S E f 00, (c)
- f (0.x'(u)) + (v + θ 01|2]
+ a (v [Rcio [u)] + + (xx(xx)))
< E [ (0, Xcoo - (0, (u)) +
+ ((())
+ a (v +
S f (u) ff 00 x (u))
+ +17 (M (x)o((( + (x" (u)))
$ f
f (0, x (u)
+ (1) + (1 (u)) + + (xx (u)))
5 E ((x)())) - 0012 + (1 + +
cos 2a1) + (1 - o) (v (x)coo( + v (x (u))) s 2v (x" (u)) (1 cos
< (2 cos 201 7 σ)v (x" (u)) + (n + (x)((u)
The first line holds because of Lemma The second line holds due to Assumption 3. The third line holds because f is linear in 0. The expectation is taken over IP.. The fourth line holds due to Lemma
21

---

3. The fifth line holds due to Assumption 2. The sixth line holds because of the definition of ccoo The seventh line holds because (xcro ccoo is an optimal solution to RFO (C(O, 01), u). The eigth line holds due Lemma The ninth line holds since both (ci and 0 are the unit sphere and the angle between them is no greater than 201, then the L2 distance between them is upper bounded by 2(1 cos 201)
Next, we bound the AOG of XCIO. We have
AOG(X)
[f (0" Xcio(u)) - (0" x' (u))]
I E [2 2 cos 201 + + d)v (x' (u)) + (1 o) [xco((]
(2 cos 201 + + + (g) + dCTo
where = E (v|x (u)]).
C Numerical Experiment Details
C.1
Computational Setup
All the algorithms are implemented and test using Python 3.9.1 on a MacBook Pro with an Apple M1 Pro processor and 16 GB of RAM. Optimization models are implemented with Gurobi 9.5.2.
C.2 Forward Problems
C.2.1 Shortest-path
We consider the shortest path problem on a 5x5 grid network G(N, E) where N and & indicate the node and edge sets, respectively. Let E and & -- (i) denote the sets of edges that enter and leave node E N, respectively. Let u" and ud denote the origin and destination of the trip, respectively. We define Tij E as binary decision variables that take if road (i,j) is traversed for any (i, E E. The shortest path problem is presented follows.
minimize
Σ (KS)EE
Osgati
(54a)
if ud
subject to
Σ (1)
Izj
Σ
Tij
1,
if 0d
WiE
(54b)
(6)))8-(1)
0,
otherwise
Z4 {0,1), (.
(54c)
The objective function minimizes the total travel cost. The first set of constraints are the flow- balancing constraints that make sure we can find a path from to ug. The second set of constraints specify the range of our decision variables. Note that the constriant matrix is totally unimodular, so
can replace the binary constraints with 0 < Zzz for any (i.j) E E when implementing this model.
C.2.2 Knapsack
We consider knapsack problem of 10 items. We define binary decision variables æ, that indicate item E [d] is selected (= 1) or not (= 0). The knapsack problem is presented as follows.
maximize x
8
(55a)
HEId]
subject
Σ
(55b)
I; E [0, Vi e [d].
(55c)
The objective maximizes the total value of the selected items. The first constraint enforces a total budget for item selection. The second set of constraints specify the range of our decision variables.
22

---

C.3 Obtaining a Point Estimation
We consider two methods to obtain point estimations of the unknown parameters. They are data- driven inverse optimization with the sub-optimality loss and ii) the gradient-based method proposed by Berthet al. (2020). We implement the method from Berthet al. (2020) with the package provided by Tang and Khalil (2024). Hyper-parameter are tuned using separate validation set of 200 decision data points. Batch size set to 64. We use the Adam optimizer with an initial learning rate of 0.1. We train the model for 20 epochs.
We present the implementation details of the data-driven inverse optimization method next. We consider solving
minimize OERiEI,eE Rm
Σ L
(56a)
Nwain
subject to
Vx E Nx. E Kunin 4. 2 0x xxx,
(56b)
0
1 S 4
(56c)
This problem is initialized without Constraints (56b), which were added iteratively using a cutting- plane method. Specifically, in each iteration, after solving Problem (56), let O' and {% keKm. be the optimal solution. For each data point E Kunin. we solve the following sub-problem
minimize xxEX(uL)
x'xx
(57)
Let x be the optimal solution to the sub- sub-problem. 1f < 0 x' we add the following cut Problem (56)
l 0 x
(58)
We keep running this procedure until no cut is added to the master Problem (56).
C.4
Solving the Calibration Problem
C.4.1 Shortest Path
For each data point in the validation set, we calculate the value of c by solving the following problem
maximize
0T 0
(59a)
σ 0E VER!!!
subject to
Wdd Wor Σ
Vty
0
(59b)
(1,)EE
Wi wi Uij Cij. V(i.)) EE
(59c)
00 2| S 1.
(59d)
where w E R and v R! respectively, denote the dual variables associated with the flow- balancing constraints and the capacity constraints in the primal problem. The first constraint enforces strong duality. The second set constraints are the dual feasibility constraints. The last constraint ensures the optimal solution is on the unit sphere. Note that do not need to enforee ||0||2 1 because this is a maximization problem.
C.4.2 Knapsack
For each data point in the validation set, calculate the value of ct by solving the following calibration problem
maximize dERd
(60a)
subject to
0T & 0xx,
Vx E X(u)
(60b)
||0|| < 1.
(60c)
23

---

We initialize this problem without Constraints (60b). In each iteration, after solving the calibration problem, let 0' denote the optimal solution. We solve FO uz) and let x' denote the optimal solution. If x > &' we then add the corresponding cut to the model. We keep running this process until no cut added.
C.5 Solving the Robust Forward Problem
Let a = cos -1 (T&(fc) (ek..)) We next solve the following robust model to recommend new decision to prescribe decision given U.
minimize maximize xEX((u) BERIE
0
(61a)
subject to
0 2 cos(a)
(61b)
||0||2 S 1.
(61c)
We initialize this problem as follows.
minimize Ω
(62a)
XEX(u),
subject to 0 < Ω A0 E Ô.
(62b)
We initialize θ = Ø. We first solve Problem (62), let x' and O' denote the optimal solution. Then
we solve the following sub-problem
maximize PERIET
0Tx
(63a)
subject
0 2 cos(a)
(63b)
||0|| S 1.
(63c)
Let 0' denote the optimal solution the sub-problem. If 0Tx > Ω then add 0' θ and re-solve Problem (62). We keep running this procedure until new solution is added to O.
D Additional Computational Results
In this section, we conduct additional computational experiments to assess how point estimate quality affects the performance of the Conformal IO pipeline. Specifically, we focus on the knapsack problem, where we randomly generate point estimates with an angular deviation from the ground- truth parameter 0", with serving as a proxy for point estimate quality. We then apply our calibration method to the point estimate and subsequently use the robust forward problem to generate decision recommendations. We vary the value of 8 and report the average (std) out-of-sample AOG and POG achieved by our pipeline in Table 3.
Table 3: Mean (std) AOG and POG by conformal 10 when varying point estimate quality.
6
π r/20
T/10
3T 3
r/5
POG
8.45 (0.67)
8.29 (0.66)
8.94 (0.79)
9.91 (0.95)
11.58 (1 (1.40)
AOG 0.00 (0.00)
0.16 (0.07)
0.30 (0.19)
0.74 (0.31)
1.38 (0.53)
In general, conformal I0 benefits from more accurate point estimates (i.e., when 8 is small). However, the trend is not always strictly monotonic, For instance, as 8 increases from 0 to z/10, the POG initially decreases before rising again. While beyond the scope of this work, exploring point estimation methods that optimize for the performance of the downstream robust optimization could be a valuable direction for future research.
24

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: Theoretical results are proved Sections 3 and Section (complete proofs are in the appendix). These results are verified numerically in Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Limitations and future research directions are discussed in Section 6.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model sell-specificatinn. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
25

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
Assumptions are stated and justified in Section 3.1.1. Proofs are in the
appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experiment details are well documented in the paper. We also open source our implementation https: btttps://anongee //w.n///nnnnmun../m/ 4open. occienn///Coofffoaa11-----
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
26

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Data and source code available at hattps:/anooyyouus 4open sci science/ r Conformaa10-BB766
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c cc/ public/guice /uwdee//ooeeuuummaaee wwo.sosisssiiooiiccorooroo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https: /nips.cca wwtpccccpppccccoece cooollicguuiesss /ed.ed/edoodbubmmiii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question:
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, this information is documented in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
27

---

Justification:
We report error bars/standard errors for all experimental results in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
This information is disclosed in Appendix C.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http///eerrpp..eeee wttppb/ccc/hiicciuiieeeieee//eee
Answer: [Yes]
Justification: We have reviewed the NeurIPS Code and Ethics and confirm that our paper conform with it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
28

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [NA]
Justification: This is theoretica/mmethooolggaaal paper that presents foundational research
in optimization. We do not see a direct path to any negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This is theoretica/mmethoooloiiaall paper that presents foundational research in optimization. It does not involve any high-risk data/model.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
29

---

12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
We properly cite code/papers on which our research is built on.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
Our code and data along with documentations are available at https: anonymous.4opg science/r/Conf ormal10-B776
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details the dataset/code/modell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots. if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
30

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as institution conducting the review.
31


Reviews:
[{"review_id": "xXFRsBMr4u", "reviewer": "Reviewer_5FdS", "summary": "In some supervised decision making, one usually leverage solution of optimization problem sequentially for future decisions. The authors argue that a single point estimation might not be enough and rather suggest estimating a whole uncertainty set on the model parameter and instead suggest a minimax robust optimization problem for future decisions. A nice contribution is to provide theoretical guarantees on the optimality gap of the proposed solution, with high probability.", "questions": "1-) **Presentation** : After introducing the framework, the introduced example 1 seems quite toyish and the presentation here is quite confusing:\n\n- example 1 is followed by lemma 1 that only applies to example 1, which is followed by proposition 1 that only applies to example 1 ... So I am quite curious to see how this generalize to other problems. Otherwise remove the \"lemma\" and \"proposition\" denomination and set it all under the Example 1 umbrella.\n\n- Same for lemma 2.\n\n- I am curious how the main contributions Theorem 2 and 3 applies to the given example 1. Also how does it applies to classical linear model with Gaussian noise? \n\n- In line 86, it seems that the authors assume the knowledge of the distribution $\\mathbb{P}_u$. But it is not clear how is this used in the given examples, and how does it appears in the main results.\n\n\n2) **Related works** : The authors might want to *remove* some overclaim in the paper e.g. in the conclusion *\"We present the first approach to learning uncertainty sets from decision data, which is then utilized in a robust optimization ...\"*, here are some refs of similar previous work, just to name a few.\n\n- (Siddiqui et al 2015) https://link.springer.com/article/10.1057/jors.2014.41\n- (Csaji etal 2015)  https://arxiv.org/abs/1807.08216\n- (Dekker etal 2008) https://hal.science/hal-03046711\n- (Guille-Escuret etal 2024) https://arxiv.org/abs/2401.15254\n\nBeyond the downstream applications that might differ, how the contributions of this paper compare to such previous work?\n\n3-) In the main text, it is unclear how conformal prediction framework is used. As far as I know, uncertainty sets derived from conformal prediction applies to *observations* and not model parameters directly [besides some very recent works that provide early results for such extension]. \n\n4-) How does one obtain a reasonable $\\eta$ in assumption 2. How such a choice affects the presented bound? Typically I am surprised it does not even appears in Equation 12. For example if one consider overparametrized linear model, the sets of solutions are usually unbounded. I also do not understand why we can use scale invariance here without loss of generality. The authors might want to write this part more explicitly\n\n_______ Edit after rebuttal _________\n\nAfter considering authors rebuttal and discussions, I raised my score to support paper acceptance.", "limitations": "OK", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- The problem considered is quite interesting for safer AI based decision making.\n\n- The derivation of uncertainty sets seems novel and quite intriguing.", "weaknesses": "The presentation is quite convoluted and hard to follow at several points. See questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. Presentation. \n    - **The goal of Example 1 is to get through the intuition**. Since both reviewers UvTc and ggLM recognize its usefulness, we view the simplicity of example 1 as a strength. We suggest keeping the Lemmas and Proposition as they help to organize our results. Putting them under example 1 would necessitate moving the proofs to the main body, which is long. Moreover, we are clear in these statements that they only apply to Example 1 so they won’t cause confusion. \n    - **Generality**. We provide general results for conformal IO in Theorem 3. For its application to example 1, we point the reviewer to Table 1 where we present the values of our bounds in Example 1. Our bounds closely follow the real AOG and POG achieved by conformal IO. Our result for classical IO is specific to Example 1. Our point is it can fail in some settings (not in general).  Moreover, we demonstrate empirically in Section 5 that we consistently outperform classical IO, which aligns with our finding in Example 1. \n\n    - **Application of Theorems 2 and 3.** The application of Theorem 3 has been discussed above. Theorem 2 is about the coverage that our uncertainty set can achieve, which wasn't discussed in Example 1. Instead, we verify Theorem 2 in Figure 3 using more complicated problems. \n    - **Linear model.** We see the connection between linear regression and our setting, but since they are very different, it is unclear how to interpret the theorems in this new setting. In IO, we are given (context $u$, decision $x$) data and the mapping from $u$ to $x$ is described by an optimization layer parameterized by $\\theta$. However, in linear regression, we are given (“feature” $u$, “target” $x$) data and the mapping is described by a linear function $x = \\theta^\\intercal u$. \n         - **Theorem 2.** In our setting, different data points $(u_k, x_k)$ are generated by different $\\theta_k$, reflecting that decision makers have different perceptions. We want an uncertainty set that contains a $\\theta$ that can explain the next  $(u_k, x_k)$ (Theorem 2). However, in regression, all the data points are generated by the same $\\theta$. People are interested in a set that contains the true $\\theta$. These two properties are different. The meaning of Theorem 2 is unclear in regression due to the discrepancy in the data generation process.\n         - **Theorem 3.** In our setting, we use the uncertainty to prescribe decisions. We want these decisions to be of high quality with respect to random human perception (Theorem 3). In regression, the confidence set is usually not used for this purpose. So Theorem 3 may carry limited meaning. \n    - **Line 86**. We didn't make any assumption regarding the distribution. We only introduce notations in line 86. \n2. **Related Work.** Thank you for sharing your concern. We plan to make the claim more precise by changing the sentence to “... the first **IO approach** that learns …”. Incase there is a misunderstanding regarding our contribution, we discuss the suggested papers below.\n    - The first paper is about solving a robust model when the uncertainty set is given. The uncertainty isn't constructed in a data-driven way. \n    - The other papers are about constructing a confidence region for parameters in a linear regression model. As we discussed above, this is very different from our setting, so these methods are not applicable in our setting. We emphasize that we work with **decision data**. That is, our observations are solutions to optimization problems, so there are optimization structures that we need to consider which are not captured in these existing works. \n\n    In summary, we believe our claimed contribution is valid. We recognize the importance of differentiating our setting from regression and will add discussions at the start of Section 3.2.\n3. **CP for parameters.** We emphasize that our problem is different from regression. We adapt the CP concept to suit our IO setting. However, we understand the reviewer’s point. If one considers predicting the decision $x$ based on context $u$ using an optimization layer parameterized by $\\theta$, then one can see our application of CP as producing uncertainty sets for parameters. Conceptually, we first converts the dataset of $(u_k,x_k$) observations to a set of (“parameter set” $\\Theta(u_k,x_k)$), each set $\\Theta(u_k,x_k)$ containing all the parameters that explain $x_k$ under $u_k$. We adapt CP methods to produce a set that has $\\gamma$ probability of containing at least one member of the next sampled $\\Theta(u,x)$. We will add this discussion in Section 4 to clarify. In theory, one can apply our method to regression, but as discussed above, the interpretation of our theorems is unclear, so we leave it for future work.\n\n4. **Assumption 2**.\n    - **Scale invariance**. We point the reviewer to lines 92-98. Since we focus on objective functions that are linear in $\\theta$, the scale of $\\theta$ neither affects the decision we observe nor the prescription we make. That is, if we multiply $\\theta$ by a positive constant, the optimal solution to FP would not change. We thus can without loss of generality enforce $||\\theta||_2 = 1$ in Equation (2). \n   - **We don’t need to choose $\\eta$ to apply our method**. We assume the existence of $\\eta$ to prove Theorem 3, which is always true due to the l2 norm constraint in Equation (2) (discussed above). For a specific instance, we can enumerate possible $(u, x)$ pairs and calculate the diameter of the corresponding set defined in equation (2). This is how we calculate the bounds in Table 1. Regarding its impact, based on equations (13) and (14), the bound increases as $\\eta$ increases. \n    - **Equation (12) should not depend on $\\eta$**. Equation (12) is a standard concentration result. It means the coverage probability observed in the validation set shouldn't be too different from the real coverage probability. The variation only depends on the size of the validation set.", "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": "", "extra_scores": {}}, {"review_id": "RBHBsKKc6G", "reviewer": "Reviewer_UvTc", "summary": "This paper considers a robust inverse optimization problem. The author provides an uncertainty set with probabilistic guarantees for the estimated parameters, illustrates the advantages of robust inverse optimization over deterministic inverse optimization through an example, and demonstrates its superiority in experiments on other problems.", "questions": "- The failure of the point estimation method in Example 1 is partially because of the sub-optimality loss. Will the conclusion be changed if using another loss?", "limitations": "The authors have discussed the limitations in Section 5 & 6.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-  This paper considers robust inverse optimization problems, which is a good complement to existing inverse optimization literature.\n-  The procedure of efficiently solving CP is described in good detail, which is helpful for implementation.\n-  The paper is overall clearly written and well-structured. The authors use a simple intuitive example to illustrate the motivation of robustifying the inverse optimization, which I find really helpful.", "weaknesses": "- The present of the uncertainty set in (9) may need justifications.\n-  Although the RFO method can work based on any point estimation method, the performance of the solution usually depends on the quality of the point estimation method. I wonder if the authors could discuss this in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for recognizing the novelty and clarity of our paper.\n\n- **Uncertainty Set justification.** We explain the two constraints in Equation (9) below. \n    - **l2 norm = 1**. We point the reviewer to the discussion under “objective function” in Section 3.1. We focus on objective functions that are linear in the unknown parameters. So, the scale of the parameters $\\theta$ neither affects our decision observations nor our decision recommendations. For example, consider a shortest path problem where $\\theta$ is a vector of travel cost on each road segment. Multiplying this vector by any positive constant (e.g., 2) would not change the optimal route. This is why we force (without loss of generality) all the cost vectors to have a fixed l2 norm. \n    - **The angle constraint**. The second constraint imposes that the maximum angle between any cost vector $\\theta$ in the uncertainty set and the point estimate $\\bar{\\theta}$ is $\\alpha$. Alternatively, we can interpret it as bounding the distance between the two vectors:\n        - $||\\theta - \\bar{\\theta}||^2 \\leq 2 - 2\\cos(\\alpha)$ \n        - ⇔ $||\\theta||^2 -2 \\theta^\\intercal  \\bar{\\theta} + ||\\bar{\\theta}||^2 \\leq 2-2\\cos(\\alpha)$ \n        - ⇔ $\\theta^\\intercal \\bar{\\theta} \\geq \\cos(\\alpha)$.\n\n- **Point estimation quality.** The reviewer correctly points out that the performance of our approach may depend on the quality of the point estimation. To verify this conjecture, we perform additional computational experiments using the knapsack problem where we randomly generate point estimations whose angle from the ground-truth $\\theta^*$ is $\\delta$ (a proxy for “point estimation quality”) and apply our calibration method to that. We vary the value of $\\delta$ and report the average (std) out-of-sample AOG and POG achieved by our pipeline below. \n\n    | $\\delta$ | $0$              | $\\pi/20$       | $\\pi/10$        | $3\\pi/20$       | $\\pi/5$          |\n    |-----------|---------------|----------------|----------------|----------------|----------------|\n    | POG       | 8.45 (0.67)   | 8.29 (0.66)    | 8.94 (0.79)     | 9.91 (0.95)     | 11.58 (1.40) |\n    | AOG     | 0.00 (0.00)     | 0.16 (0.07)    | 0.30 (0.19)     | 0.74 (0.31)     | 1.38 (0.53)    |\n\n  Overall, our method can generally benefit from using a better point estimation (i.e., when $\\delta$ is small). However, the trend may not be strictly monotonic (see the change in POG from $\\delta = 0$ to $\\delta = \\pi/20$). In fact, what we mean by “high-quality point estimation” is not entirely clear, especially when we consider POG as a performance measure. This observation inspires us to draw connections between our work and recent literature regarding obtaining a point estimation that directly optimizes the performance of the downstream robust model; See, for example [1]. We believe this is an interesting observation that will inspire follow-up works. Due to the page limit, we may need to include these results in the appendix, but we will make sure to include these discussions when talking about future research directions in Section 6. \n[1] End-to-end conditional robust optimization. UAI, 2024. \n\n- **loss function**. Yes, the result in Example 1 depends on the usage of the sub-optimality loss. Using other loss functions, for example, the predictability loss proposed in [2] will give us better performance in theory. However, as we discuss in lines 140-148, these loss functions usually lead to intractable inverse optimization problems so they are very difficult to use in practice. The sub-optimality loss is usually the only loss that leads to a tractable IO problem. This is why we focus our discussion on the sub-optimality loss. \n\n\n[2] Inverse optimization with noisy data. Operations Research, 2018.", "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": "", "extra_scores": {}}, {"review_id": "h4Q9o9YRKG", "reviewer": "Reviewer_ggLM", "summary": "This paper proposes conformal inverse optimization (CIO) which uses conformal prediction to learn uncertainty sets for parameter estimates in IO. These uncertainty sets are then used to formulate a robust version of the forward optimization problem. The authors provide intuition for their method and also provide theory to show that CIO is a principled approach. Experiments on synthetic shortest path and knapsack problems demonstrate the promise of CIO.", "questions": "* Line 124: What is meant by “algorithm aversion”?\n\n* How is the uncertainty set calibration related to the classic conformal prediction framework?", "limitations": "Please see “Weaknesses”", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The authors motivate their approach of conformal inverse optimization using examples (e.g., Example 1).\n\n* The figures in section 3 provide helpful intuition for the proposed approach. Nicely done!\n\n* The authors show that their method is theoretically justified — it obtains uncertainty set validity and also allows for a bound on the POG.\n\n* The authors provide a code implementation of their method, which makes their experiments easier to reproduce. Furthermore, the experiments are described in sufficient detail in the main paper.", "weaknesses": "* The setup in section 3.1 could benefit from more intuition. I think having a running example (e.g., rider-driver matching) where $x$, $u$, $\\theta$, and $\\mathcal X(u)$ have a practical meaning would be very helpful.\n\n* Line 85: I think the domain of $f$ should be $\\mathbb{R}^{n} \\times \\mathbb{R}^{d}$, not $\\mathbb{R}^{n \\times d}$.\n\n* The idea of $\\alpha$ (line 202) could be explained better. How exactly does $\\alpha$ control the size of the uncertainty set?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- **Running example.** We thank the reviewer for this suggestion. Throughout the paper, we can think of the forward problem as a shortest path problem where the decision $x$ corresponds to a path from an origin to a destination specified by $u$ and the parameters $\\theta$ can be treated as the travel cost on each road segment. More specifically, $\\theta^*$ is the real travel time on each road segment and $\\hat{\\theta}$ is a driver’s noisy perception of $\\theta^*$. We will add this example to Section 3.1 to add clarity.\n\n- **line 85**. We will fix this in the revised version. \n\n- **How $\\alpha$ control the uncertainty set size.** We point the reviewer to equation (9) where we define the uncertainty set. The parameter $\\alpha$ controls the max angle between the point estimation and any cost vectors in the uncertainty set. So, using a larger $\\alpha$ means we include more cost vectors in our uncertainty set. We will add a pointer to equation (9) in line 202 to remind the readers about this. \n\n- **Algorithm aversion.** Algorithm aversion means humans are often reluctant to adopt algorithm recommendations even if algorithms may have very strong performance. There are many reasons behind this, for example, the suggested solution may be misaligned with human intuition (our focus in this paper), and the algorithm may be uninterpretable. We will add a short sentence after line 124 to make the definition clear. \n\n- **Connection to classic CP**. From a conceptual point of view, our approach first converts the dataset of (“context” $u_k$, “decision” $x_k$) observations to a set of (“parameter set” $\\Theta(u_k,x_k)$), each set $\\Theta(u_k,x_k)$ containing all the parameters that explain $x_k$ under $u_k$. Our work adapts conformal prediction methods to produce a set that has $\\gamma$ probability of containing at least one member of the next sampled $\\Theta(u,x)$. Note that if $\\Theta(u,x)$ is a singleton almost surely, the approach reduces to applying CP on the set ($\\theta_k$). We will add this discussion at the start of Section 4 to clarify the connection.", "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": "", "extra_scores": {}}, {"review_id": "lZSQvwwpsG", "reviewer": "Reviewer_Bo7T", "summary": "The paper proposes a robust optimisation method for decision problems that provides not only a point estimate but also an uncertainty set. The methodology is tested on decision making tasks such as shortest path and the knapsack problem and shows favourable results when compared to classical inverse optimisation methods. The theoretical results focus on the validity of the uncertainty set as well as bounds on actual and perceived optimality of the decision policy.", "questions": "Can you explain the significance of the $\\Delta_\\alpha$ term in more detail (line 258)?\n\nWhile you mention some inverse reinforcement learning literature (e.g. line 72), I wonder if you are aware of any similar probabilistic approaches in that literature?\n\nI appreciate that providing a real-world example may be difficult, but can you comment on the possible issues of using your approach on real-datasets. Are any of the assumptions in your analysis likely to be violated (e.g. due to distribution shift or quality/size of data)?", "limitations": "The limitations are discussed in Sec. 6 as well as throughout the analysis and experiment sections.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper addresses an important problem of inverse optimisation taking advantage of the CP framework. The proposed pipeline is clear and easy to follow. To the best of my knowledge, the work is original. The writing quality and clarity is good.", "weaknesses": "My only concern is the practical applicability of the methodology. While I appreciate the motivation for the approach and the extensive discussion of the evaluation metrics, I feel the gains offered by the methodology are minor, particularly given the fact that large datasets will be needed to calibrate the model and choose the hyperparameters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "- **Data availability.** We thank the reviewer for recognizing the importance of the topic and the clarity and novelty of our paper. However, we would like to point out that data availability should not be a bottleneck in practice. For example, consider the ridesharing example we describe in Section 1 where the forward problem is a shortest path problem from an origin to a destination. To apply our method, the data we need are historical paths taken by Uber drivers. Uber can observe millions of such trips on a daily basis. This type of data is more and more accessible to academic researchers as well. For example, Amazon recently released a dataset of thousands of delivery trips in major US cities [1]. Therefore, we believe our paper can potentially make a big impact as decision data become increasingly accessible.  \n\n  [1] 2021 Amazon last-mile routing challenge: Data set. Transportation Science, 2024.\n\n- **Significance of $\\Delta_\\alpha$.** This parameter is useful only when we want to achieve 100% coverage. We need some extra protection in this case because conformal prediction in general cannot provide a 100% coverage guarantee. But in practice, since choosing a $\\gamma$ < 100% usually gives us better performance as we show in Figure 4, the choice/usage of this parameter is not very important. We’ll rephrase the discussions in line 258 to make this more clear. \n\n- **Probabilistic approaches.** We are not aware of any other papers that use probabilistic approaches in our setting. If the reviewer can provide pointers to such literature, we would be happy to review and add them to Section 2 as appropriate.  \n\n- **Challenges.** Thank you for this question. We are actively looking for real-world applications to demonstrate the value of our approach. We see the following potential challenges. First, as you mentioned, when dealing with real-world data, we always need to worry about things like distributional shifts, data quality (again, we don’t think quantity is an issue) and independence (assumption 1). Second, to apply any inverse optimization approach, we always need to specify a forward optimization problem. We need to engage with practitioners to really understand the problem that they are trying to solve to formulate a reasonable forward problem to work with. The model may always be wrong (in the sense that there is always a trade-off between model tractability and granularity), so demonstrating the performance under model misspecification is also critical. We will add these discussions in the conclusion section.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes conformal inverse optimization where we seek to learn an uncertainty set for the unknown parameters in an optimization model. Given such a set, the proposed method solves a robust optimization problem to prescribe new decisions in a theoretically principled manner. 

The reviewers unanimously agree that the paper is well-written, and its contributions merit acceptance. After carefully reading the paper and the corresponding discussion, I tend to agree. Please incorporate the reviewers' feedback. In particular, addressing the following concerns will help strengthen the paper:
- Clearly contrast to the previous literature in the conformal prediction (response to Rev. 5FdS, Rev. ggLM)
- Add the shortest path problem as a running example in Section 3 (response to Rev. 5FdS, Rev. ggLM)
- Include the additional experiment studying the impact of point estimating quality (response to Rev. UvTc)
- Include the comment about data availability to justify the practical applicability and the corresponding challenges of the proposed approach (response to Rev. Bo7T)
Decision: Accept (poster)