Predict-then-Calibrate: A New Perspective of Robust Contextual LP
Authors: Chunlin Sun
Linyu Liu
Xiaocheng Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Uncertainty Quantification
Contextual LP
Robust Optimization
Distributionally Robust Optimization

Abstract: Contextual optimization, also known as predict-then-optimize or prescriptive analytics, considers an optimization problem with the presence of covariates (context or side information). The goal is to learn a prediction model (from the training data) that predicts the objective function from the covariates, and then in the test phase, solve the optimization problem with the covariates but without the observation of the objective function. In this paper, we consider a risk-sensitive version of the problem and propose a generic algorithm design paradigm called predict-then-calibrate. The idea is to first develop a prediction model without concern for the downstream risk profile or robustness guarantee, and then utilize calibration (or recalibration) methods to quantify the uncertainty of the prediction. While the existing methods suffer from either a restricted choice of the prediction model or strong assumptions on the underlying data, we show the disentangling of the prediction model and the calibration/uncertainty quantification has several advantages. First, it imposes no restriction on the prediction model and thus fully unleashes the potential of off-the-shelf machine learning methods. Second, the derivation of the risk and robustness guarantee can be made independent of the choice of the prediction model through a data-splitting idea. Third, our paradigm of predict-then-calibrate applies to both (risk-sensitive) robust and (risk-neutral) distributionally robust optimization (DRO) formulations. Theoretically, it gives new generalization bounds for the contextual LP problem and sheds light on the existing results of DRO for contextual LP. Numerical experiments further reinforce the advantage of the predict-then-calibrate paradigm in that an improvement on either the prediction model or the calibration model will lead to a better final performance.

Predict-then-Calibraeee A New Perspective of Robust Contextual LP
Chunlin Sun*. Linyu Liu Xiaocheng Li
Institute for Computational and Mathematical Engineering. Stanford University Department of Automation, Tsinghua University
3 Imperial College Business School, Imperial College London
Abstract
Contextual optimization, also known predict-then-optimizz or prescriptive ana- lytics, considers an optimization problem with the presence covariates (context side information). The goal is to learn prediction model (from the training data) that predicts the objective function from the covariates, and then in the test phase, solve the optimization problem with the covariates but without the observation the objective function. this paper, we consider a risk-sensitive version the problem and propose generic algorithm design paradigm called predict-then- calibrate. The idea to first develop prediction model without concern for the downstream risk profile robustness guarantee, and then utilize calibration (or recalibration) methods to quantify the uncertainty of the prediction. While the existing methods suffer from either restricted choice of the prediction model strong assumptions on the underlying data, we show the disentangling of the pre- diction model and the ralieration/uunceraintyy quantification has several advantages. First, it imposes no restriction on the prediction model and thus fully unleashes the potential of off-the-shelf machine learning methods. Second, the derivation of the risk and robustness guarantee can be made independent of the choice of the prediction model through data-splitting idea. Third, our paradigm of predict-then then- calibrate applies to both (risk-sensitive) robust and (risk-neutral distributionally robust optimization (DRO) formulations. Theoretically, it gives new generalization bounds for the contextual LP problem and sheds light on the existing results of DRO for contextual LP. Numerical experiments further reinforce the advantage of the predict-thent then-calibrate paradigm in that improvement on either the prediction model or the calibration model will lead to a better final performance.
Introduction
Contextual linear programming (LP) considers the linear programming problem with the presence of covariates, and it can be viewed as prediction problem under a constrained optimization context where the output of the prediction model serves as the objective of a downstream LP. The goal is to develop model (trained from past data) that prescribes decision/solutiin for the downstream LP problem using directly the covariates but without observation of the objective function. A similar problem formulation was also studied as prescriptive analytics [Bertsimas and Kallus 2020) and predictthenn-otimiie Elmachtoub and Grigas [2022]. The existing literature mainly develops two approaches for the problem: (i) end-to-end algorithms that map the covariates directly to a recommended decision for the LP or (ii) two-step algorithms that first predict the unobserved objective using the covariates and then solve the LP with the predicted objective. While the literature has been largely focused on the nisk-nlutral objective, our paper considers the risk sensstivv///obbuss
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

formulation of the problem. The robust formulation of the contextual LP can be viewed as both risk-sensitive version of the risk-neutral objective in contextual LP and an adaptive/contextual version of the standard (context-free) free) robust optimization problem. In comparison with the robust optimization literature, the contextualized robust optimization problem allows a contextual and data-driven way to design the uncertainty set and ideally can utilize the contextual information to make less conservative decisions. The contextual/data-
uncertainty set has been considered by several existing works on transportation (Guo et al. [0233 D. portfolio management (Wang et al. (2022), ) and healthcare (Gupta et al. (2020). ). While these works focus on applications with special structures or distributions, our paper considers generic setup and aims for general solution to the problem.
In our paper, we make the following contribution:
First, we formulate algorithm design paradigm of predictthen-calibraae and introduce the notion of uncertainty calibration/quantiicaatt to the problem of contextual optimization. The idea is to first develop a prediction model without worrying about the downstream robustness, and then tailor the uncertainty calibration methods to quantify the prediction uncertainty towards the robust objective.
Second, we develop two algorithms for robust contextual LP under the paradigm of predict-then- calibrate. The derivation of theoretical guarantees shows the advantage of the disentanglement of the prediction phase and the uncertainty calibration phase. Moreover, we quantify the advantage of better prediction and/or a better uncertainty calibration both theoretically and empirically.
Third, we also draw connection with the related problem of distributionally robust optimization. We utilize the same idea of predictthenn-caibeee and derive a new generalization bound for the distributional robust version of contextual LP utilizing tools from the nonparametric regression.
In the following, we review the several streams of literature that are related to our work.
Conditional robust optimization. The problem studied in our paper can be viewed as a condi- tional version of the classic robust optimization problem. The robust optimization stems from the replacement of the risk-neutral expectation objective with a sisk-ssnsittvve robust objective such as Value-at-Re Satt-Risk(Vaa /quantie The literature robust optimization develops methods approximate VaR by specifying the shape and size of an uncertainty set to guarantee that a VaR constraint would be satisfied Ghaoui et al. [2003). Chen et al. [2007) Natarajan et al. [2008). |Bertsimas et al.) (2018) designs the uncertainty set with a finite-sample probabilistic guarantee on optimal solutions. Goerrgk and Kurtz (2020) constructs the uncertainty set as the union of K convex sets by clustering historical data. While all these works concern the context-free setting, the contextual (or conditional) setting, or the problem of robust contextual LP, considers the presence of covariates in robust optimization.
Along this line. Ohmori [022]] proposes a colume-minimized ellipsoid covering k-nearest samples in
the contextual space, leading nonlinear programming problem. [Cenreddy al. [2022) extends the idea in Goerigk and Kurtz [0200] and novelly adopts deep learning approach to the problem which identities which clusters the uncertain parameters belong based on the covariates. Compared
to the end-to-end formulationn Ohmori] (2021). ) Chenreddy et al. [2022). J. we do not impose restrictions on the prediction model and have larger flexibility in choosing the uncertainty quantification method.
Contextual LPPPredict-ther thenoiiiiieeen-.iiiiie.e Our work complements the existing literature on contextual LP by considering risk-sensitive objective. The existing works Donti et al. [2017). Elmachtoub and Grigas 2022). Ho-Nguyen and Kılınç-Karzn (2022), |Hu et al. [2022] mainly study the risk-neutral objective for the problem and aim to develop prediction methods that account for the downstream optimization tasks. To model the remaining uncertainty after prediction in optimization. Sen and Deng (2018) considers training a parameterized point- wise estimation model first, and then approximating the conditional distribution by imposing randomness to the learned parameters empirically, [Ban et al. [2099] proposes to forecast the distribution of new product demand by adopting a línear regression model to fit the demands of similar products with covariates, and then using the empirical distribution of covariate-inde inndeede-nnde residuals to build sample average approximation (SAA) model. SAA
Some recent works Kannan et al. [2020] [2022] [ further generalize it to a residuals- framework to include more machine learning methods and adopt distributionally robust optimization to mitigate the overfitting under limited data. A key difference between our work and this line of works is that we consider a risk- sensitive objective, while these works consider a risk-neutral objective. In this light, our framework of predict- predict-then--aut chen-calibrate is compatible with any prediction model developed along this line, and it tailors the prediction model for a robustness task.
2

---

2 Problem Setup
Consider linear program (LP) that takes the following standard form
LP(c, A, = min c x;
s.t. Ax = b, x 2 0,
where e E IR", A E Rmxx, and IR" are the inputs of the L... addition, there is an available feature vector IRd that encodes the covariates (side information) associated with the I.P.
The tuple (c, A, b, =) is drawn from unknown probability distribution P. The problem of contextual LP (predict-thennoppimizz or prescriptive analytics) usually assumes the availability of a learning (training) dataset sampled from the distribution
Dj = { R
1-1
During the test phase, one needs recommend feasible solution Inew new LP problem using the observation of (Anow: bnew; Znew) but without the observation of the objective vector Cnew:
(Anow Unew, know) ) + Inew.
The focus of the existing literature has been mainly on the risk-neutral objective
min [[c|=]] xr,
(2)
s.l. Ar b,
where the recommended decision x can be viewed as a function of (A, z).
Alternatvell,, consider risk-sensitive objective
min VaR [c' x|>],
(3)
s.t. Ar = b, x 20
where E 1), Here VaR, (U) denotes the a--uaanile/valle-attee
(VaR) of random variable U;; specifically, (U) = (a: with (-) be the inverse cumulative distribution function of U.
can interpret the problem 3 two ways: First, can be viewed as a risk-sensitive version the contextual LP problem 2 From the prediction viewpoint, the standard problem ( concerns only
the prediction [[c]2]. while solving (3) may involve a distributional prediction of the conditional distribution e|z. Second, the classic robust LP problem considers setting where there is covariate, and the VaR is taken with respect to the (marginal) distribution of c. Comparatively, the problem (3) conditionally robust version where the VaR is taken with respect the conditional distribution c 2. The presence of the covariates 2 reduces our uncertainty on the objective e and thus will induce less conservative decisions with the same level of risk guarantee.
can be viewed
Throughout the paper, work with well rell-trained ML model f: Fd + R" that predicts the objective with the covariates and is learned from the training data Dj. We emphasize that we do not impose any
assumption on the model, but assume the availability of a validation set Deal == {Ce, Ac, b,, z ) that can be used to quantify the uncertainty of
3 Robust Contextual LP
The problem 3 has been extensively studied under the context-free setting in the literature robust optimization [Ben-Tal et al. 2009). and the key challenge the non-convexity of the objective function. Equivalently, the problem
3 can be written as the following optimization problem
min max x,
all CEll
s.t. A x2.0. Pap(CE U)
where the decision variables are x, e and a measurable set 4. The last constraint is with respect to the set U1 and the probability is taken with respect to the conditional distribution c/z. One issue to
3

---

solve this problem is the intractability in optimization over the uncertainty set. Particularly, even if the conditional distribution c| discrete, (4) is equivalent a mixed integer linear programming problem, which is generally NP-hard and computationally intensive. Similarly, when solving a sample average upproximation form of 4 (Bertsimas and Kallus (2020), the problem becomes similar to the discrete case, and the intractability issue is still inevitable. To resolve this issue, one can solve the following approximation problem with a fixed uncertainty set satisfying (c U) 2 a,
LP(U) == min max C I,
(5)
Ar b, x
A box- ellipsoid-shaped uncertainty set enables tractable optimization of the problem (5). The uncertainty set hopes to cover the high-density region so that the approximation to (3) is tighter.
Now we present two algorithms that implement this approximation idea in the contextual setting. The key quantify the uncertainty of the prediction model. Both algorithms construct contextual uncertainty sets for the prediction model; that is, the size of the uncertainty set changes with respect the covariates z. In addition, importantly, the construction of these uncertainty sets accounts for the tractability of the downstream robust optimization problem (5) by outputting the box and ellipsoid shapes, respectively. In both algorithms, we first split the available validation data into two sets D and D2, and use the first set Dj for preliminary calibration, and the second set D2 for additional adjustment. The output from both algorithms gives a contextual uncertainty set (z) that works as the input of (5) and thus solves the downstream robust optimization problem.
Algorithm Box Uncertainty Quantification (BUQ)
1: Input: Dataset Datt ML model f. parameter a
2: Randomly split the validation data into two index sets D2 U U22 (I,..., and D1 0 D2
3: Pelrreiinyyryy calibration of the uncertainty sets
4: for t E Dj do
5:
Calculate the residual vector on the t-th validation sample
f(zx)
(6)
and denote ri (re1, ..., Ptn)"
6: end for
7:
Train quantile regression model h(z) Rdd R"
that minimizes
ΣΣe Pa (Iral h(2)).)
TED:
where prl(:) (1 (.)+ denotes the pinball loss
8: % Additiinall adjustment of the size of the uncertainty sets
9: for E DD2 do
Let
Te(1) = f(z)) + m)((z)) e ER" (1)1) = f(z)) - m/((zz)) E E
11: end for
12: Choose minimal y > 0 such that
Σ (c) Sa <a <a())) min(|P2l, a( + +1}
(8)
LED₂
where 1(-} is the indicator function and the inequality is required to hold element-wise Output: h, n
In Algorithm [ first compute the residual/error vector r. R for samples in dataset D Then for each coordinate 1,.... n, we fit quantile regression model h that predicts the quantile of the absolute error by minimizing 7 Specifically, the model h aims to predict the quantiles of each coordinate of the residual vector Then, in the second step of Algorithm we pretend the quantile model h is "correct" and construct the uncertainty sets accordingly for samples in dataset

---

D2. Importantly, the uncertainty set is parameterized by a scalar We use the parameter to perform an additional adjustment of the uncertainty set so that the coverage probability met on D2 by The algorithm outputs the function & and 7,, and it will output a box-shaped uncertainty set ua (=) f()) nh(=), f(=) n)((z) for new sample with covariates
Algorithm 2 Ellipsoid Uncertainty Quantification (EUQ)
1: Input: Dataset Datt ML model f. parameter a
2: Randomly split the validation data into two index sets D1 UD2 (1,..,
and D1 n D2
3: %% Preliminary calibration of the uncertainty sets
4: for D do
5: Calculate the residual vector on the t-th validation sample
T == f(x))
6: end for
7: Use Dj to fit a model 9 : Rd - that predicts the a-quantile of ||re|2 using the covariates z5
8: Fit a zero-mean normal distribution for the scaled residual vector
(re/((z)) t D1}
and denote the covariance matrix E 9: %edAdiitinnal adjustment of the size of the uncertainty sets Choose a minimal r > 0 such that
Σ (a- IED2
f(z+)) s =(())))(()))))))))))) 2 min([P2),,a(1Pa)
1)}
(9)
where 1{-} is the indicator function and the inequality is required to hold element-wise.
11: Output: 9. Σ,
Algorithm follows similar spirit as Algorithm It first computes the residual vector Ty for samples in dataset Dj, but differently from Algorithm fits a regression model for the norm |rr||2. Then fits zero-mean normal distribution for the scaled residual vector. The motivation is that the residual vector (up to scale ((2)) follows multivariate normal distribution. We remark that although the algorithm design is motivated by such setting of normal distribution, its theoretical guarantee does not rely on this normal structure. The key the second step of additional calibration: it pretends the uncertainty set is "correct" and uses additional scalar v to make further adjustments such that the coverage probability a is met on D2 by D.. For a new sample with covariates 2, the algorithm outputs
an ellipssid-shaped uncertainty set (z) = c: (
f(=)) f())) (C)-)(())
n²(2))
In comparison, for the first step of preliminary calibration, Algorithm I quantifies the uncertainty of each coordinate of the residual vector individually, while Algorithm 2 presumes Gaussian structure. We remark that the two algorithms provide two examples for the design of the preliminary calibration step. but these are not the only two options. As we will see shortly. the second step of additional adjustment in charge of the coverage guarantee, so the first step can be further modified based on other prior knowledge of the underlying data/optimization problem.
3.1 Algorithm Analysis
The following proposition provides coverage guarantee for both [[gorithm[[aadd] that the output uncertainty set will cover new sample with probability of approximately a.
Proposition 1. For a new sample (c, A, from distribution P, denote the uncertainty sets output from Algorithm 1 and Algorithm by (2) (z) and and respectively. The following inequalities hold 1,2.
a S C (x)) < a 1D21+1
(10)
where the probability is with respect to the new sample (c, A, b, b) and dataset D2-
5

---

The proposition gives the following insights into the two algorithms and the general problem of robust contextual LP. First, the second step (in both algorithms) of the adjustment via the scalar 1j the key to the coverage guarantee (TO), with several advantages. First, as the concentration argument is made with respect to only this second step, the bound rather tight and free of unnecessary conservation in the uncertainty set construction. Second, it allows full flexibility in the choice of the prediction model f and the preliminary calibration model h (Algorithm I and 9 (Algorithm 2). This reinforces The design of the prediction model can be solely targeted on the accuracy, and the coverage guarantee can be deferred and taken care of by the calibration steps such these two algorithms.
the notion of wredict-heen-caibree
Furthermore, we note the probability in 10 is taken with respect to only the validation data and the new sample. It means Proposition holds even the training data Dr (for obtaining f) is not sampled from the distribution P. In other words, the result only requires the validation data Diat P and it is robust to a distribution shift of the training distribution when Dr + P. In broader context, when the training data, validation data, and test data come from different distributions, this situation is commonly referred to as the out-of-domain (OOD) problem. We refer to the survey papers Shen al. [2221] Yang et al. [202]] for more detailed discussion of this problem. Developing more coverage guarantees with OOD data will require future investigations, and we will list this problem
as future direction.
In addition, the coverage guarantee in Proposition contextual LP problem as in the following corollary.
! can be extended to robustness guarantee for the
Corollary 1. For new sample (c, A, b, 2) from distribution P, denote the uncertainty set output from Algorithm| I or Algorithm by Ua(2). Let x² and OPT(z) be the optimal solution and the optimal value of LP(Ua( 5). Then we have
P (c x (x) OPT(2)) 2
where the probability is taken with respect to the new sample (c, (c b, 2) and D2.
To end this section, we remark that although the coverage guarantee (T0) in a population sense where the probability is taken with respect both and 2, our framework of wredictthen-calibrae
also has the ficxibility to achieve an individual coverage by changing the calibration algorithm under some assumptions. Here, the individual coverage means that the conditional probability P (c E (z)]2) = a holds for any covariate 2 as the constraint in ( where Ua (=) denotes any given contextualized uncertainty set. However, the abbov--mentoons assumption achieve individual coverage cannot be verified from the data prior, and achieving this coverage is, in general, a hard problem, although there have been many attempts in the literature conformal prediction and model calibration. In addition, we want to emphasize that, compared to achieving individual coverage, the most significant focus of this paper is introduce the idea of uncertainty quantification solve robust optimization, which disentangles the prediction from the calibration. As a result, we delay the discussion of the individual coverage to Appendix B.1
3.2
Value of Better Prediction and Contextual Uncertainty Set
Two important components in the framework of predict-heen-calibrate are (i) the flexibility in choosing the prediction model ff and (ii) the contextual uncertainty set (z). In the following, we illustrate the importance of these two aspects via simple examples.
The value of better prediction. Consider a single-variable LP
min Cr s.t. - 1 < 1
(1I)
where the objective is determined by e Σi= 24 d Here 2 and sampled from an exponential distribution Exp(1) for all i = 1,.., d. We note that 2; can be interpreted as either the covariate itself some useful latent factor extracted by the prediction model. Consider a prediction model that can only utilize/extract the first covariates/latent factors 21:A = (21, 2x). The optimal
prediction model would be [4(21::) E 2i, and also we assume it has perfect uncertainty quantification denoted by (21.a) We denote the accordingly robust solution by x; (3))),, and thus all these solutions for k = 1,,.. d meet the coverage guarantee.

---

Proposition 2. For any E (0.5, 1) and k 2 1
P (11(k = =0)
1 r(k)
(7 (7(K, max {0. -
{o
log (a-a) (1+ (1+ d-A (1=))= -7 ( max {
{a, (o.-dlog (
(a(1+2) d-A
and it decreases monotonously with respect k. Here, 7),;)) denotes the lower incomplete gamma function.
Proposition givee an analytical expression for the probability the optimal robust solution equal to zero. A zero solution can be viewed as conservative solution when the prediction model is uncertain about the objective c. While we assume the prediction model equipped with perfect uncertainty quantification, the proposition says that more informative covariates and/or powerful prediction models will lead to less conservative solutions for the downstream robustness task. The reason is that a better prediction model can make the uncertainty quantification task easier by smoothing the conditional distribution of the residual r|2 with respect to z. For example, when k = d in Proposition 2 the distributions of residuals are identical and thus very smooth for different covariates, which is easier to quantify than the case with 0. This reason can also be extended to general cases.
The value of better calibration. Consider the LP again but with specified by
c (sign( (2) + [z)
where E R is sampled uniformly from [-1, 1]. and is sampled from the uniform distribution on [-0.5, 0.5]. this case, the sign of the objective e can be deterministically determined by the sign of With perfect knowledge of the underlying uncertainty, the following solution is the optimal robust solution for all a E (0,1)
(z) sign(2).
The following proposition gives another uncertainty set with the optimal prediction model and coverage guarantee but suboptimal robust solution.
Proposition 3. For 1/2, let the uncertainty set
V2
1- 122-22222202 20
i/ [0, 1],
ua(2)=
2
-00,
-- -00,-
2
20
if E (-1,0).
The uncertainty set has coverage guarantee in that P(c (=)) If we solve the optimization problem (5) with the uncertainty set Uo (z), the following robust solution is obtained
1,
if
3 20 2-2-20
2(2) =
0, if
3220 2a
<25 20 2.2
1, if 3+20+2V2-24
The robust solution induced by the uncertainty set U4, (2) is unnecessarily conservative compared to the optimal robust solution x (z). This highlights the importance of good uncertainty quantification. and in particular, contextualized uncertainty quantification. Specifically, the suboptimality of r(z) arises from that the uncertainty set (z) in the proposition is not much contextualized with respect
to z, and this justifies the contextualized uncertainty models and ğ for the preliminary calibration step in Algorithm] ] and Algorithm 2
In addition to the contextualized uncertainty quantification, remark the flexibility in choosing the calibration model or uncertainty set can bring us two benefits. First, it has the potential to further reduce decision conservatism by collaborating with new designs of small uncertainty sets. Specifically, we can design predict-heen-calibe on many previous works that focus on designing minimum size uncertainty sets to achieve given coverage guarantee in the context-free robust optimization distributional robust optimization literature (Bertsimas al. (2018). Gupta [2019). Second, this framework is also applicable to more general optimization problems such convex programs multi-stage stochastic programs. In
algorithms with even small uncertainty sets based
7

---

particular, for these general problems, if the robust VaR formulation has tractable construction of the uncertainty set in the context-free setting, we can then design predict-then thten-haiinaateeeeee algorithm by constructing the corresponding contextual uncertainty set accordingly. To close this section, we emphasize that our predict-then-calibar framework behaves more like a plug-in module that can fit into the existing robust optimization literature, and thus, it is potentially capable of handling more problems than the contextual LP loss discussed in this paper.
4 Extension to Distributionally Robust Contextual LP
In the previous sections, we study the problem of robust contextual LP and the framework of predict- then-calibrate. Now we turn to a related but different problem distributionally robust contextual LP - through the lens of predict- seddictthen-ccalbbatt. We relate the objectives of robustness and distributional robustness with the two types of uncertainty in the uncertainty quantification literature. We show the paradigm of predict-then then-chlibnatee can also be extended to the distributionally robust contextual LP and obtain new generalization bound for the problem.
The distributionally robust contextual LP concerns the following problem:
min max P'EE,
Epi [c x]
Ep [c]
s.t. Ar < b, 0
where E. denotes set of distributions that describes the uncertainty on Ideally, one hopes that the uncertainty set covers the true conditional distribution clz. Compared the robust version that concerns the VaR/Quantile of the objective the formulation here still concerns the risk-neutral The
objective but accounts for the uncertainty estimating E[c|=]. The distributionally robust optimization has two roles: first, it can be used to derive solutions with provable guarantees on generalization, and second, it induces a regularization effect for the underlying prediction model.
F(c)
epistemic
B[c]
Roos
RO sp aaleatoric
Figure 1: Illustration of robust optimization (RO) and distributionally robust optimization (DRO) (here we omit the covariates 2 for simplicity). DRO concerns epistemic uncertainty HHällermeier and Waegeman 22021) the part of the uncertainty that be reduced by obtaining With more samples, the uncertainty set will shrink. In contrast, aleatoric uncertainty Hüllermeier and Waegeman [222]] refers the inherent and irreducible randomness of c. To derive the uncertainty set for RO problem, one needs to account for the summation of epistemic and aleatoric uncertainty.
information.
As in the previous section, denote the prediction error the validation data D by
Ti = Ct - f(z).
The following proposition states that there exists a distributionally robust algorithm that achieves generalization bound that is oblivious with respect to the underlying prediction model f.
Proposition 4. Assume there exists a constant L such that the following condition holds for any 2, z'
E|r|z] - -[r[[=]] & T=|=-
Then under mild boundedness assumptions on the distribation, there exists a distributionally robust optimization algorithm that utilizes the validation data Duat and outputs solution ((2) such that the following inequality holds with high probability
E [c (6(z) - x (=))) S S0 OT 2Gंक log logT).
8

---

Specifically, the DRO algorithm performs nonparametric uncertainty quantification with respect to r, 's and thus it is oblivious the underlying prediction model f. We remark that such idea of calibrating r is not new and has been exploited in Wann al. 2021 Kannan et al. [020 2021]. But notably, our result requires weaker condition the underlying f. where the previous works rely realizability condition of the prediction model. Moreover, compared with the generalization bound the contextual I.P literature Liu and Grigas [2021), although Liu and Grigas [2021] develops an O(T-1/4) generalization bound, they still require the function class of the prediction model can have bounded Rademacher complexity. that condition holds here, our generalization bound can also be improved accordingly.
We defer the detailed proof and the DRO algorithm to Appendix C.5
Experiment
In this section, we illustrate the performance of our proposed algorithms via one simple example and also shortest path problem considered in Elmachtoub and Grigas [0022] and Hu et al. [2022). We defer more results including more visualizations, another experiment on the fractional knapsack prob- lem lem|Hos (Ho-Nuyyen and Kilınc-Karzan [022], and experiment setups to the Appendix. We implement our (
and Algorithm 2 (PTC-E) against several benchmark methods including the Ellipsoid method that ignores the covariates, k-nearest neighbor (kNN) approach in Ohmori [202I]. the Deep Cluster- Cluster-Classify (DCC), and Integrated Deep Cluster-Classify (IDCC) approaches
in Chenreddy et al. [2022]. More experiment details are deferred to Appendix A
Uireettintly set
Uncertainit set
1.0
Lassn
1.0
L Inear
GBR
0.5
0.5
0.0-
0.0
0.5
1.0
Rebust solutionx
Robestt solution
Optimal
Optimal
K0
GAN
-6.4
-0.2
0.0
0.2
0.4
-0.4
-0.2
0.0
0.2
0.4
x=1
(a) Prediction
(b) Uncertainty quantification
Figure 2: Performance under different prediction and quantile regression models in PTC-B. The results corresponding to PTC-E are the same since PTC-B and PTC-E coincide in this one-dimensional case. The scattered black points indicate the training samples and the curves indicate the band for the uncertainty set. For the left panel, we fix the uncertainty quantification model h to neural network and implement different prediction models. For the right panel, we fix the prediction model as neural network and implement different uncertainty quantification models. KR stands for kernel regression, GBR stands for gradient boosting regression, and NN stands for neural network.
Simple LP Visualization
In the first experiment, we study the LP problem 11I where the optimal solution and the uncertainty set can be visualized. Here the covariates 2 (21,.., za) where 2; sampled from Unif[- 0.5, 0.5] independently for = 1,... d, e ~ Unif[ 0.5, 0.5]. and c = (sign(z1) + E) /lzi I (c is independent of ..,..., zd). We consider risk level of PTC-B and PTC-E, 20% for final adjustment (D2). In Figure 2 the robust solutions obtained from different prediction methods and different calibration methods Section 3.2 that either a better prediction model or a better calibration model will improve the final performance of the robust optimization problem.
0.8 and dataset size T 1000. For our methods of 60% of the data for training f. 20% for preliminary calibration (D1). and
plotted. The results reinforce the discussions in
Shortest path problem
Now we present numerical experiments for shortest path problem on a 5 grid with 40 edges, and the cost of traveling through edge is a for i I,...,n. We follow the experiment setup in

---

Lasso
Random Forest
2.4
Avg. VaR (x1000)
Avg. VaR (x1000)
OLS
Ellissoid
1.85
Ke
2.2
KNN
KemelRRidge poly
DCC
IDCC
1.80
2.0
PTC.
PTC-E
1.75-
1.8
1.70
20
50
100
MSE (x100)
(xx100)
Figure Value better prediction
Figure Sample efficiency
Table Average VaR and coverage on shortest path problems under different risk level settings. The average is reported based on 500 simulation trials.
(a) Average VaR
(b) Average coverage
Ellips.
kNN
DCC
IDCC
PTC-B
PTC-E
Ellips.
KNN
DCC
IDCC
PTC-B
PTC-E
0.6
2447
1940
2218
2181
1650
1690
0.6
0.63
0.65
0.62
0.63
0.56
0.63
2488
2273
2168
1717
0.73
0.65
0.7
0.64
0.71
2535
2312
2205
1708
1774
0.82
0.65
0.8
0.84
0.76
0.8
0.85
2563
2032
2286
2286
1735
1796
0.85
0.87
0.65
0,85
0.89
0.79
0.85
0.9
2598
2059
2392
2291
1769
1843
0.9
0.92
0.65
0.89
0.93
0.88
0,91
0.95
2646
2098
2373
2249
1832
1905
0.95
0.96
0.65
0,94
0.97
0.93
0.97
Elmachtoub and Grigas 2022 and Hu et al. 2022 where the details are deferred to Appendix A.2 In this experiment, we demonstrate several aspects of our algorithms. First, Figure Sguuee]show. shows the averaged VaR of PTC-B solutions (under different prediction models f) versus the Mean Squared Error (MSE) on the test data, which reveals positive correlation between the predictive performance and the quality of the solution obtained in the downstream robust optimization task. We utilize the Kernel Ridge method with the RBF kernel-identified the rop-performing model in Figure 3 -as the predictive model and the Neural Network (NN) model as the preliminary calibration model for both PTC-B and PTC-E in the ensuing experiments (Figure Aag and Table to compare with other algorithms. Second, Figure demonsttates that our algorithms exhibit better sample efficiency than the benchmark algorithms we increase the number of training samples. Specifically, while the model DCC and IDCC take ad advantage of the expressiveness of a complicated deep learning architecture, they can be more costly in terms of the required training samples. Furthermore, we compare the performance under varying risk level settings in Table [ The Ellipsoid method does not utilize the covariates information, so although has coverage guarantee, it performs worst on the VaR. The kNN method [Ohmori 2021 has good VaR performance, but it lacks confidence adjustment, so it is hard to adapt to different confidence levels. The two deep learning- approaches and ours give good coverage guarantees, while we attribute the advantage of our algorithms to the flexibility in choosing the prediction model and the calibration model.
Conclusion. In this paper, we study the robust contextual LP problem which lies at the intersection of contextual LPPpredic-theen-opiiiiz and robust optimization. We develop two algorithms for the problem which output box- and ellipsoid shape uncertainty sets. The algorithms introduce new perspective for contextualized uncertainty calibration, and it highlights the convenience brought by the disentanglement of the prediction and the uncertainty calibration. Yet, as mentioned earlier, the coverage guarantee Proposition is with respect to a population/average sense. Developing algorithms with individual-level coverage guarantees deserves more future investigation. Also, we hope our work provides starting point for future research on risk-sensitive and robust decision- making for the problem of contextual optimization and optimization with machine- learned advice.
10

---

References
Naomi S Altman. An introduction to kernel and nearest- neightr nonparametric regression. The American Statistician, 46(3):175-188) 1992.
Anastasios N Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.0751, 2021
Gah-Yr Yi Ban and Cynthia Rudin. The big data newsvendor: Practical insights from machine learning.
Operations Research, 67(1)990-108, 2019.
Gah-Y Yi Ban, Jérémie Gallien, and Adam J Mersereau. Dynamic procurement of new products with covariate information: The residual tree method. Manufacturing & Service Operations Management, 21(4):798-813
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Conformal prediction beyond exchangeability. The Annals of Statistics, 5662):81-885,, 2023.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization, volume 28.
Princeton university press, 2009.
Dimitris Bertsimas and Nathan Kallus. From predictive to prescriptive analyties. Management Science, 66(3):1025 2020.
Dimitris Bertsimas and Nihal Koduri. Data-driven optimization: A reproducing kernel hilbert space approach. Operations Research, 70(1):454-4711 2022.
Dimitris Bertsimas and Bart Van Parys. Bootstrap robust prescriptive analytics. Matheratical Programming, 195(1-2):99-78, 2022.
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathematical Programming, 167:235-22 292, 2018.
Dimitris Bertsimas, Christopher McCord, and Bradley Sturt. Dynamic optimization with side information. European Journal of Operational Research, 304(2)6634-65,, 2023.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: nonasymptotic theory of independence. Oxford university press, 2013.
Leo Breiman. Classification and regression trees. Routledge, 2017.
Junyu Cao and Rui Gao. Contextual decision-making under parametric uncertainty and data-driven optimistic optimization. Available at Optimization Online, 2021.
Ningyuan Chen, Saman Lagzi, and Joseph Milner. Using neural networks to guide data-driven operational decisions. Available at SSRN 42/7092, 2022.
Xin Chen, Melvyn Sim, and Peng Sun. A robust optimization perspective on stochastic programming. Operations Research, 5556:1058 2007.
Abhilash Reddy Chenreddy, Nymisha Bandi, and Brick Delage. Data-driven conditional robust optimization. Advances in Neural Information Processing Systems, 35:9525-9537, 2022.
Youngseog Chung, Willie Neiswanger, Ian Char, and Jeff Schneider. Beyond pinball loss: Quantile methods for calibrated uncertainty quantification. Advances in Neural Information Processing Systems, 14:10911- 2021.
Peng Cui, Wenbo Hu, and Jun Zhu. Calibrated reliable regression using maximum mean discrepancy. Advances in Neural Information Processing Systems, 33:17164-17175, 2020.
Priya Donti, Brandon Amos, and J Zico Kolter. Task-based end-to-end model learning in stochastic optimization. Advances in Neural Information Processing Systems, 30, 2017.
Adam N Elmachtoub and Paul Grigas. Smart "predict, then optimize". Management Science, 68(1): 9-26, 2022.

---

Nicolas Fournier and Arnaud Guillin. On the rate of convergence in wasserstein distance of the empirical measure. Probability theory and related fields, 162(3-4):70--38, 2015.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan Tibshirani. The limits of distribution--ree conditional predictive inference. Information and Inference: A Journal of the IMA, 10(2):455-482 2021.
Laurent El Ghaoui, Maksim Oks, and Francois Oustry, Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Operations Research, 51(4):543-556, 2003,
Mare Goerigk and Jannis Kurtz. Data-driven robust optimization using unsupervised deep learning. arXiv preprint arX1v:2011.09769, 2020.
Zhen Guo, Bin Yu, Wenxuan Shan, and Baozhen Yao. Data-driven robust optimization for contextual vehicle rebalancing in on-demand ride services under demand uncertainty. Transportation Research Part C: Emerging Technologies, 154:104244, 2023.
Vishal Gupta. Near-optimal bayesian ambiguity sets for distributionally robust optimization. Man- agemen! Science, 65(9):4242-4220, 2019.
Vishal Gupta, Brian Rongqing Han, Song- Hee Kim, and Hyung Paek. Maximizing intervention effectiveness. Management Science, 66 66(12):557-55588 2020.
Peter Hall, Rodney CL Wolff, and Qiwei Yao. Methods for estimating a conditional distribution function. Journal of the American Statistical association, 94(445):154-163 1999.
Lauren Hannah, Warren Powell, and David Blei. Nonparametric density estimation for stochastic optimization with an observable state variable. Advances in Neural Information Processing Systems, 23, 2010.
Chin Pang Ho and Grani A Hanasusanto. On data-driven prescriptive analytics with side informa- tion: A regularized nadaraya-watse watson approach. URL: http://wwww. aptimizationn-nlliz org/DB F1LEE20190017043, pdf. 2019.
Nam Ho-Nguyen and Fatma Kilınę-Karznn Risk guarantees for end-to-end prediction and optimiza- tion processes. Management Science, 68(12):8680-866 8698, 2022.
Yichun Hu, Nathan Kallus, and Xiaojie Mao. Fast rates for contextual linear optimization. Manage- ment Science, 68(6):423--42555 2022.
Eyke Hüllermeier and Willem Waegeman. Aleatoric and epistemic uncertainty in machine learning:
An introduction to concepts and methods. Machine Learning, 110:457-506. 2021.
Nathan Kallus and Xiaojie Mao. Stochastic optimization forests. Management Science, 2022.
Rohit Kannan, Güzin Bayraksan, and James Luedtke. Residuals-based distributionally robust. optimization with covariate information. arXiv preprint arXiv:2012..10088, 2020.
Rohit Kannan, Güzin Bayraksan, and James Luedtke. Heterooseedasticityyaaarr residuals-based contextual stochastic optimization. arXiv preprint arXiv:2101.031139 2021.
Rohit Kannan, Güzin Bayraksan, and James R Luedtke, Data-driven sample average approximation with covariate information. arXiv preprint arXiv:2207. 13554,, 2022.
Volodymyr Kuleshov, Nathan Fenner, and Stefano Ermon. Accurate uncertainties for deep learning using calibrated regression. In International conference on machine learning, pages 2796-2804. PMLR, 2018.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523): 1094-1111, 2018.
12

---

Heyuan Liu and Paul Grigas, Risk bounds and calibration for smart predict-then-optmmize method. Advances in Neural Information Processing Systems. 34:22083-22094, 2021.
Shang Liu, Zhongze Cai, and Xiaocheng Li. Distributionn-ree model-agnostic regression calibration via nonparametric methods. arXiv preprini arXiv:2305. 2023.
Gar Goei Loke, Qinshen Tang, and Yangge Xiao. Decision-driven regularization: A blended model for predict-hen--opimmiz. Available at SSRN 3623006, 2022.
Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1): 141-142, 1964.
Karthik Natarajan, Dessislava Pachamanova, and Melvyn Sim. Incorporating asymmetric distri- butional information in robust value-at-risk optimization. Management Science, 54(3):573-585, 2008.
Viet Anh Nguyen, Fan Zhang, Jose Blanchet, Erick Delage, and Yinyu Ye. Distributionally robust local non-oonnnnnnn moon-parmmetric conditional estimation. Advances in Neural Information Processing Systems, 33:15232-15222 2020.
Viet Anh Nguyen, Fan Zhang. Jose Blanchet, Erick Delage, and Yinyu Ye, Robustifying conditional portfolio decisions via optimal transport. arXiv preprint 10t::2203..445/1 2021.
Shunichi Ohmori. predictive prescription using minimum volume k-nearest neighbor enclosing ellipsoid and robust optimization. Mathematics, 9(2):119, 2021.
R Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 2:21-42, 2000.
Suvrajeet Sen and Yunxiao Deng. Learning enabled optimization: Towards fusion of statistical learning and stochastic programming. INFORMS Journal Optimization (submitted), 2018.
Zheyan Shen, Jiashuo Liu, Yue He, Xingxuan Zhang, Renzhe Xu, Han Yu, and Peng Cui. Towards out-of-distribution generalization: A survey, arXiv preprint arXiv:2 13624, 2021.
Vladimir Vovk. Conditional validity of inductive conformal predictors. In Asian conference on machine learning, pages 475-490. PMLR, 2012.
Tianyu Wang, Ningyuan Chen, and Chun Wang. Distributionally robust prescriptive analytics with wasserstein distance. arXiv preprint arXiv:2106.0575 2021.
Yijie Wang, Grani A Hanasusanto, and Chin Pang Ho. Robust contextual portfolio optimization with gaussian mixture models. 2022.
Geoffrey Watson, Smooth regression analysis. Sankhyā: The Indian Journal of Statistics, Series A, pages 359-372, 1964.
Jingkang Yang. Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A survey. arXiv preprint arXiv:2 2021.
Shengjia Zhao, Tengyu Ma, and Stefano Ermon. Individual calibration with randomized forecasting. In International Conference on Machine Learning, pages 11387-11397. PMLR, 2020.
Taozeng Zhu, Jingui Xie, and Melvyn Sim. Joint estimation and robustness optimization. Management Science, 68(3):1659-1677 2022.
13

---

A Supplementary for Experiment
Details of benchmarks. For the DCC and IDCC algorithms proposed in Chenreddy et al. [002]] we set the number of clusters to be 10. This choice of the number of clusters is large enough because there are clusters containing no training samples. The Ellipsoid method, which is also benchmark used in Chenreddy et al. 2022]. fits Gaussian distribution without contextual information and calibrates the radius to cover a proportion of a training samples. For the ANN conditional RO method Ohmori 2021]. the hyperparameter, k, lacks the flexibility to adjust with respect to the number of training samples T, the dimensionality of the problem, and the risk level a so we empirically choose k = max VT, x n here. Different algorithms utilize the same dataset to ensure fairness in each round of comparison. We redefine T as its size in the experiment section. For proposed Algorithm (PTC-B) (PTC under the PTC framework, the dataset is randomly split into 60%, 20%, and 20% to do prediction, preliminary calibration, and final adjustment, respectively.
Performance measurements. In the test phase, we randomly generate 2 from its marginal distribu- tion. Then, for each 2, we generate set with 1000 objective vectors, {c² 1 from Palz. Given any robust solution x conditioned on z, we estimate the VaRalc x| by the a-quantile of {c' J] and take its empirical expectation over as the average VaR. Similarly, we estimate the average coverage by the average frequency of {e U2
A.1 Simple LP Visualization
We select NN the prediction and preliminary calibration models in both PTC-B and PTC-E algorithms and compare them to benchmarks. Here, because is only 1-dimensional, we replaced the DCC and IDCC algorithms, which are based on deep neural networks, with another clustering method, K-Means. Figure shows the performance different algorithms when d increases (d 4. and 16). and the plot is shown by fixing 22, ..... 2d to O in the test phase. The Ellipsoid method performs the worst and gives an unchanged uncertainty set for all different & due to its ignorance of the contextual information. All algorithms degrade with increase in irrelevant information, but localized methods such as kNN and K-Means exhibit more severe deterioration. Our proposed methods, however, maintain certain degree of stability.
Ellipsoi
KNN
K:Means
PTC-8
PTC-E
T=1000, d=1
T=1000,
T=1000, d=16
1.0
0.5
0.0
0.5
-1.
Optimal Elllp KNN KMeans PTC-E
0.0
21
21
x=
x=1
Figure 5: Comparison in performance deterioration with increasing dimensions
A.2 Shortest Path Problem
In this section, we consider a shortest path problem on 5 x grid with 40 edges, and the cost of traveling through edge is for i = 10. 40. After observing the covariates (e.g., weather conditions, day of the week), we aim select route from the left-top vertex to the right-bottom one to minimize the value-at-risk travel time, i.e., VaR., I). The data generation process is as follows. First, we generate 0-1 matrix O E 1010xd once with random seed 0 and fix it to encode the parameters of the true model, where each entry generated from a Bernoulli distribution with probability 0.5. Then, the covariate vector zt Id is generated from N N(0, Ia) for t = I,..,,

---

Ellipsoid
KNN
DCC
IDCC
PTC-B
PTC-E
2.5
Scaled VaR
2.0
1.5
1.0
0.5
0.6
0.7
0.8
0.85
0.9
0.95
Figure 6: Box plot of scaled VaR shortest path problems under different risk level settings
Given z', the cost on edge is ct - [[ 1( (z') +33 + +1 1-1].e; ee, where e; Unif 3] independently for 1, .... 40. We implement d 10 here. To simulate the uneliminated irrelevant information, we set the last two dimensions & are set to be zero. In the test phase, evaluate the performance marginal distribution of 2. We select the Kernel Ridge method with the RBF kernel as our prediction model and the NN model as preliminary calibration model in both PTC-B and PTC-E.
to be independent of c, so their corresponding column vectors in 500 2 generated from the
In Figure
we show the box plot version of Table with scaled VaR. Here, alleviate the impact of randomness on we scale the VaR by the optimal value of the corresponding conditional stochastic program with expectation objective, i.e., VaR,/Obj Obj where Obj = maxAz=5,220 [E(c] 2] x. Fig-
ure olcce again demonstrates the superior performance of our algorithms minimizing VaR that in Table
A.3 Fractional Knapsack Problem
In this section, consider fractional knapsack problem and follow the setup in Ho-Nguyen and Salinç-Karzan 2022). This problem can be interpreted as a maximization problem, wherein consumer aims maximize their utility by selecting items under budget constraint. Specifically, fit our formulation, the problem can be written as
min VaRa. (-cTar) x), where (s ZEX
[0, 1]"h TT. S B}.
Here, e the utility vector and we use a minimization version to represent maximization problem. E RR" is some fixed positive vector indicating the price of items, and B > 0 is the budget. The same as the shortest path problem, we randomly generate a 0-1 matrix θ E 200 once with the last 2 columns entirely filled zeros indicate the independence of the last dimensions of to Then, we generate multivariate independent from Unif(O, 4]d, and c = (9z)² e, where is multivariate independent and following Unif[ 4 $ We conduct experiments
data generated under 7 = 5000, 10, and n = 20, and we choose the Kernel Ridge method with RBF kernel as our prediction model, and the NN as preliminary calibration model in both the PTC-B and PTC-E.
Given new covariate 2, conditional RO algorithm will output an uncertainty set. Under different constraints, the worst-case scenario corresponding to the uncertainty set may vary, so we compare the performance under randomly generated constraints. We generate the price vector p with each entry as integer uniformly sampled from [1, 1000). Then, randomly generated Unif(0,, 1], and the
15

---

-2.5
5.0
Scaled VaR
-7.5
-10.0
Ellipsoid
-12.5
KNN
DCC
-15.0
IDCC
PTC-B
PTC-E
-17.5
0.6
0.7
0.8
0.85
0.9
0.95
Figure 7: Box plot of scaled VaR on knapsack problems under different risk level settings
budget B is sampled from Unif max, Pj, 1 of constraints {(p', |2 (with random seed 0) and fix them. In the test phase, the average VaR and coverage are taken over 100 z's and 10 constraints (1000 instances total).
max; Pj]. Here, randomly generated 10 sets
Table associated with Figure 7 displays the comparison results under varying risk levels and demonstrates the advantages of our proposed algorithms again via the lower VaR and proper cov- erage that closely matches the risk level, where the scaled VaR in Figure is the VaR divided by max E[c|=] x. The contextual-gnoorance method, Ellipsoid, performs the worst with the total utilities remaining O, which shows its excessive conservatism by specifying the worst-case utility of each item to be non-posinee non-positive and selecting nothing. The DCC and IDCC, as well as our PTC-B and PTC-E methods, exhibit better performance than the kNN method due to utilization of expressive NN models, which are not limited to utilizing only local information. By virtue the flexibility of algorithms in the model selection, the chosen Kernel Ridge regression model is more suitable than the Blustering-basee DCC and IDCC methods for this problem with continuous covariates, so algorithms achieve relatively better performance than theirs.
Table 2: Average VaR and coverage on fractional knapsack problems under different risk level settings. The result is reported based on 500 simulation trials.
(a) Average VaR
(b) Average coverage
a Ellips.
KNN
DCC
DDCC
PTC-B
PTC-E
0
Ellips.
KNN
DCC
IDCC
PTC-B
PTC-E
-1175
-1256
-1131
-1310
-1310
0.6
0.66
0.96
0.75
0.65
0.57
-1148
-1241
-1111
-1298
-1297
0.7
0.74
0.96
0.74
0.73
0.8
-1137
-1230
-1090
-1283
-1282
0.8
0.82
0.96
0.86
0.83
0.79
0.82
0.85
0
-1128
-1223
-086
-1273
-1273
0.85
0.86
0.96
0.89
0.89
0.88
0.86
0.9
0
-1114
-1213
-1087
-1261
-1261
0.9
0.91
0.96
0.92
0.93
0.91
0.91
0.95
-1102
-1180
-092
-1242
-1243
0.95
0.96
0.96
0.97
0.95
0.92
0.97
B Supplementary for Section 3
This section provides discussions about the individual coverage and proofs for theoretical statements in Section 3 Section B.T. we will provide a brief literature review about global coverage and individual coverage, and then, provide algorithm to achieve the individual coverage with
16

---

corresponding theoretical results. In Sections B.2 B. and B.4, we will show Propositions respectively. The proof will utilize some useful lemmas in Section
B.1 Individual Coverage
The uncertainty quantification literature arises from two communities. referred as "conformal prediction" in the field of statistics and "model calibration" in the field of machine learning. In the following, we briefly review the results of global and individual coverage in uncertainty quantification in those two communities, respectively.
Conformal prediction: Milestone works on the topic, Lei et al. 2018 Barber et al.
2023 focus
on global coverage, [Angllopoulos and Bates [202]] a survey paper on conformal prediction, also coverage, |Foygel Barber et al.) [202T].
focuses on the global guarantee. For conditional/indii
Vovk [012] state an "impossible triangle" in uncertainty quantification: (i) the coverage result is built for conditional coverage; (ii) it makes assumptions on the underlying distribution; (iii) it has finite-sample guarantee rather than asymptotic consistency. Essentially, in our paper, Algorithms I and basically fail to meet (i), but they barely rely on any assumptions
the underlying distribution and enjoy a finite-sample guarantee, that is, achieving (ii) and (iii). Later this section, we will introduce nonparametric algorithm that achieves conditional coverage, and the coverage can be nonpar samite-sample, i.c., achieving (i) and (ii), while this result requires additional assumptions on the underlying distribution, which is violation of (ii).
Model calbbrationrreeliibattto:: 2021], Kuleshov et al. (2018). Zhao et al. [2020] are a few state-of the-art papers on calibrating the uncertainty of a regression model. We note that none of these papers claim to achieve conditional coverage guarantee. Rather, they ensure global guarantee and strive for hetter empirical conditional coverage. In particular, Zhao al. (0200 gives pessimistic result conditional coverage that it is impossible to verify whether an algorithm achieves individual coverage. However, the proof is based on very special case, and is possible rule out with some mild conditions.
Laks Jaksmmiarayanna al. 2017] Cui al. 2020]. Chung et al.
In the following, we present Algorithm
S under our predict-then-calibrat framework, which can
achieve individual coverage.
Algorithm 3 Uncertainty Quantification with Individual Coverage
1: Input: Validation data Dvat, MI. model f. kernel choice k,(,)) bandwidth h. target covariate 20
2: For each E Doat, let
Ta == -==a-f(z)
3: Define the estimation of the conditional distribution r|z =z:
Kn Kn(ze, 20 20r
Prleo
Σ
EIED.O
K₁ Kn(2,,
BE DeDi
where 8, denotes the delta distribution
4: Choose a minimal 17 > 0 such that
Prizo (fr: ||r|12 S <n) 2 a
5: Output: Uncertainty set U1 (20) cc: [||e f(z0)l2 s 5m}
Here, this uncertainty guantification algorithm is mainly based on a nonparametric estimation in Hall al. [1999], [Lu al. [2023), which is also similar to the nonparametric estimation Algorithm 4 The estimator in Step 3 in Algorithm 3 covers wide range of non-parametric estimators with different kernels, including k-nearest neighbors, and it can approximate the conditional distributions of the residuals r|= =n with a sublinear convergence rate under some Lipschitz conditions. As result, by using this estimator, we can directly calculate the size of the uncertainty set so that the estimated conditional distribution attains individual coverage. That is Step 4 in Algorithm 3 In the
17

---

following, we will provide a statement without proof since the analysis is almost the same as the
proof of Proposition We also refer to Hall al. [1999]. Liu et al. [2023) for detailed analysis.
Proposition 5. Assume there exists a constant L' such that the following Lipschitz condition holds for any z,
TV(Pr Px S -
where :)) denotes the total variation distance between two distributions, and Pr|zs Pr/z denotes the conditional distribution of the residuals given covariates or z', respectively, Then under mild boundedness assumptions on the distribution, the uncertainty set (z(()) output from Algorithm satisfies
TV( S O OT MOrTS log T
Moreover, it is worth noting that, through this approximation of the conditional distributions, can extend our framework tractable optimizing conditional value-at-risk besides VaR in (3). Specifically, one generate number of independent samples {čx ]k from the approximation
of the conditional distribution c/2 = Zg- Then to optimize the following empirical CVaR objective (Rockafellar et al. 2000)
min 2,7
( x-
K(1
s.t. Az b, 2 0.
This is convex program that has equivalent linear program and is thus computationally tractable.
To close this section, want emphasize that the Lipschitz assumption in Proposition cannot be verified from the data prior. Also, we prefer not to claim we have solved the conditional coverage problem for two reasons: (i) We do not want give an impression to the robust optimization community that conditional coverage is an easy task to achieve. One should proceed with caution when applying the nonparametric algorithm; (ii) We don not want to give an impression to the statistics and ML communities working on uncertainty quantification problems that we underestimate the difficulty of the conditional coverage and lack of understanding of the related literature.
B.2 Proof for Proposition
1 [and Corollary
In this section, we first show Proposition I then show Corollary I based on the result of Proposition
Proposition 1 For new sample (c, A, b, 2) from distribution P, denote the uncertainty sets oulput from Algorithm 1 and Algorithm by u( (z) and u4 (2), respectively. The following inequalities hold for
1,2
a (CE a [D2] +1
where the probability is with respect to the new sample (c, A, b, 2) and dataset D2-
Proof. Denote n [Dz] as the number of samples in the D:2. the following, we show for ie 1, 2,
P (CEE = [a + +1]
(12)
n n+1
where [.1 denotes the ceiling function. it holds, we can prove this proposition by the following inequalities
[a(n + 1)] 11
a(n + 1) + a,
an + [a(n 1)]
1 n+1
1+11 n m+1
To show 122.. we will use the exchangeability of the dataset Dz and new sample (c, A, b, 2). Specifi- cally, denote {ce 1n the samples in D2, and denote Cx+1 as the new sample. Then, define ne
18

---

fort = 1,..., + with respect to Algorithms 1 Do 2
as follows
min {1 2 0: ( 4 & ((()),,
if k = 1,
min 7 OV (a: - f(=))) (c f(2e)) s no(z))
if k: 2.
In the proof below, we only show (12 for Algorithm I and the proof for Algorithm
2 can be obtained
similarly. Based on the choice of the uncertainty set and definition of 1j in Algorithm we have that
v is the [o(n-1]] 1)1 upper quantile in {ne 1= This choice of v also implies C+41 E Ma if 7++1 S %
which means
(co+1 E 4. = P (7m+1 is among the [a(n + + -mmalless of {m (mo)t=))
(13)
Then, is sufficient to show
[a(n + 1)]
IP (1x+1 is among the [a(n + 1)] -smallest of (mo)tt)
+
To this end, because fcr 12+1 are ii.d., we have
(Ma+1 is among the [a(n + 1)] -smallest of (m:)==)) )=+1)
(14)
=P (n is among the [a(n + -mmallets of (nchet) 1=+1)
for all t ...., n,, which is also referred to the exchangability. Then, we finish the proof by the following equalities:
(14+1 is among the [a(n + 1mm-seallest of (
n+1
(nt is among the [a(n + 1)7-smallest of (m))t)
+
E
{n is among the [a(n + 1)] -smallest of (mb=t)) }
Ja(n + 1)1
++
where the first equality is obtained by the exchangeability (4). the second equality is obtained by the definition of the expectation, and the last equality is obtained by the fact that
{n is among the [a(n 1)] -malless of (n ) [a(n + 1)7.
Next, we show Corollary 1
Corollary [. For a new sample from Algorithm Tor Algorithm by (z). Let x² (z) and OPT(z) be the optimal solution and the optimal value of LP((a(2)) (5)
(c. A, b, b) from distribution P, denote the uncertainty set output
Then we have
P (c < OPT(=)) 2 a
where the probability is with respect to the new sample (c, A, b, and D2.
Proof. By definition of the robust optimization problem (5) have
c cTx²(z) < (p)(z)
if e (2) for k 1,2. Then, Proposition implies
(e xx)))) OPT(=)) 2 a.
19

---

B.3 Proof for Proposition
2
Proposition
2 For any a E (0.5.1)
(a 0)
{ (0, -d 0,-dlog log (1 (1- (1+ d-h }}}
-2 1 max { 0, 00-dl a (((++)) d-
1 T(k)
7 ks
k, max
and it decreases monotonously with respect k.
Proof. Recall that
21 de,
(15)
and 2; and are drawn from an Exponential distribution Exp(1) for all i 1,... d. For any fixed
I,...,d, d, the corresponding prediction model is fu((1:))
Σ Z
We first characterize the distribution of the objective vector given 21:k for any k = L,..,, d. By the additivity Gamma distributions and the fact that the exponential distribution is a special case the Gamma distribution, we have given 21:k
d II i=k+1
P(c 2 0) So .. { (allau) +
Σ i=k+1
2, 226 de
e ";
e dedzxx
zd k+1 e -
J0 1(falzER) +E2d d.
dedž
(16)
T(d k)
zd-ktle 1
(1-e (1-e- (((=)))()))))))
dz
T(d - k)
= 1 -
(1+ 1
1
where the first line comes from the definition of the objective vector 15 the second line comes from changing variables that 3 = Σ and the additivity of Gamma distributions, and others come
1= k+
from the direct calculation. Then, by taking the complement, we have
P(c S 0) = = (1+ 1 k-d
(17)
Next, we compute the probability that x, (21.)) = 0. the one-dimensional setting with the feasible set {z -1 < 1]. the optimal solution of (5) can be determined by the sign of the objective vector. Thus, we are confident that e is non non-negative, the optimal solution should be x (21:k) -1; if we confident that is nos-iosiieee, the optimal solution isz (Z 1; if are not confident about the sign of the objective vector, we will be conservative and choose x (#1se) = 0. That is,
1.
if P 0/21;)) 2 a,
x (21:k)
0,
Pf 01 0|21,8) Sa
(18)
-1,
P(c 2 0/21,)) 2 a.
Then, plugging (6) and
17 into
18 we have P(c < 0| Plc 2 0| S a only when
max 0, log (1+ 1) d-A )
}
fa(=))) s max ( (0. -dlog (1 (1- 1 1) d-h
0,
d
(19)
20

---

Integrating the probability on the set 19 with respect to 21:k, we have
(1 (1 0)
(20)
1 r(k)
(7(K, [K,max
(7
k, max {o {0. 0, -0ldl (1 (1-0) (1+ d-A )²))))))) -2
ks max
{ 0, -0--dlo (a
(a(1+t)) d
(21)
To see it decrease, we can apply Jensen's inequality to see the result.
B.4
Proof for Proposition 3
Proposition
3 For 2 1/2, let the uncertainty set be
1--2-17 22
00
if [0, 1],
Ua(z)=
2
-00,-
22V22
if [-1,0).
The uncertainty set has a coverage guarantee in that Pic Un (=)) = a. If we solve the optimization problem (5) with the uncertainty set Ug (z), the following robust solution is obtained
1. if 3-20 20 2-22-22222 2-
x(2)= =
0, if
22 2m
<25
20 2v2 2a
if 3+20+222-2
1,
Proof. We first show that Plce E (, Given the prediction function f(=) sign(=) Vial
the residual is r = c- f(z) = c/\2). By calculation, we have that the marginal distribution of the objective vector satisfies
- 2ro + 21 if < r 1/2 P(r < ro) = [ + 2ro + 2: if - 1/2 50.
(22)
and this distribution the same as the marginal distribution of the objective vector given : 2 0 or S (I since the distribution of only depends on the absolute value of 2. Then, we have
/2
2a
/2
2a 2 << 0
P(c (x))))
P
2 2
0
rs
2
2
2
1 /2
20
2
2a
+ 2
P
r
2
2
where the first line comes from the property of the conditional expectation, the second line comes from the fact that the distribution of the residual is independent of the sign of the covariate z, and the last line comes from 22
Next, show that the solution x=2) is the optimal solution of problem (5) with the uncertainty set (4 (z). By (5) and the feasible set, we have that the optimal solution is 1 or - only when all elements in the uncertainty set is non-positive non-negative, respectively, and the optimal solution 0 when the uncertainty set contains both positive and negative numbers. Thus, we can find the result by computing the lower and upper bound of the uncertainty set (a(2) for [0, and 2 E [-1, 0). respectively.
C Supplementary for Section 4
This section provides our algorithm and the corresponding analysis for Section We first briefly summarize the problem and then, develop the DRO algorithm raised by our predict-then-calibne framework and the detailed proof of the algorithm analysis.
21

---

As stated in Section we here consider the risk-neutral problem as follows
min E[c[2]*
s.t. Ar b.
instead of risk-sensitive objective in Section As stated in Section we work on well-trained ML prediction model f that predicts the objective vector based on the covariate Then, will apply the idea of distributionally robust optimization to bound the prediction error and develop the generalization bound. We remark again that the prediction model can be any off off-the-shelf machine learning method since we have no assumption about it.
C.1 DRO Algorithm
In this part, derive the DRO algorithm from our predict-themm-calibbate framework. As for Algorithms [ aand 2 we work on the prediction error
C f(())
of all samples in the validation dataset Deal = fce Ar, be, 24 17 In the following, by a little abuse of notation, we use E Deal to denote sample tuple (ce, As, bt, 21) in the validation
Algorithm 4 Contextual Distributionally Robust LP
1: Input: Dataset Deat, ML model f, radius E, bandwidth h. target covariate
2: For each E 'D vat, let
Tt == ct f=x)
3: Define the estimation of the conditional mean of residuals of covariate zo by
To
Σ
we(2s, zo)re,
EED
where
wr(x) x K( zo)/h),
Σ
wx(2)
DEDeat
and (=) is a kernel function that satisfies Assumption 4: Construct the degenerate ambiguity set by
E fr' ||r roll2 S $}
5: Solve the degenerate distributional robust optimization problem
#(zo) arg min sup(f(z) + r) x;
rE
s.t.
Ar b, x 0,
6: Output: #(20)
The main idea of our algorithm is similar to distributionally robust optimization that consists of two steps: firstly, construct an ambiguity set E, and secondly, solve the following distributionally robust LP:
min max Ep. PEE s.t. Ax b x 2 0,
(f(2) + tr) Tx)
(23)
and use its optimal solution to solve Pr|zo. we can obtain good solution to by solving (23) with some generalization bound. Here, Priz denotes the distribution of the prediction error given the covariate z. our case, specifically, the ambiguity set can degenerate into set consisting of the mean of distributions in the ambiguity set since we only focus on the estimation the conditional mean E[[[z)) =o] for the target covariate ø0- Thus, in the following, will also use E to denote set of vectors corresponding to the means of
If the ambiguity contains the target distribution, say
22

---

the distributions in E. Then, as the ambiguity set degenerates, the problem (23 also degenerates to the robust optimization problem in Step of Algorithm 4
Now, we consider the construction of E. We apply a kernel estimation in Steps and 4 of Algorithm construct E. The following proposition says that if we choose proper in Algorithm = contains the conditional mean [[]]
Proposition 6. Assume there exists a constant I. such that the following condition holds for any 2,
[B[[]]] - E[r[=1]| _ L||z 2
Then under mild boundedness assumptions on the distribution, with probability no less than - 5, ro defined in Algorithm satisfies
[[|] roll2 s0
[Ld-12
32
T शांक log )
82/2
when choosing the bandwidth h = T 2x42d.
We defer the proof and assumptions to the next chapter. After developing this estimation error, if the feasible region of ① is in the unit ball with probability 1, directly build the generalization bound for the downstream problem by Proposition 4
Proposition Under the same assumptions as in Proposition 6 Algorithm outputs a solution ((20) such that
E [e (#(20) xx (=o))) 0
Ld
32
T acto log T)
81/2
holds with probability no less than 6.
Here, we emphasize that if the residuals are i..d., we can equivalently have = 0, 3c. Then, the convergence rate of our Algorithmmiis OTT21/2) which matches the rate in Wang al. [202]] Kannan et al. [2020, 2021]. Moreover, we remark that our results have the potential to be generalized to general cases for distributionally robust optimization there are more convergence theories developed for the non-i.i.d. samples. Specifically, if the distributions have some smooth properties with respect to the covariate 2, the kernel estimation
Pt:=
Σ tED.at
(24)
will also be good approximation to Prizy where is the weight constructed in Step in Algorithm with some kernel function for all E D The proof will be similar to the proof of Proposition Once being able utilize samples in Deal approximate P can develop similar DRO best knowledge, the current state-of-the-aar theory can only approximate a distribution by the empirical distribution constructed by i.i.d. samples [Fournier and Guillin 2015). and its proof cannot be extended to a more general non-i.i.d setting. Thus, one interesting future direction will be developing distributional convergence results for non-i.i.d. settings, and our framework can also have the potential be applied general distributionally robust problems.
algorithm for general cases. However,
In the following sections, will provide detailed proof for Proposition 6 and We first state and interpret our assumptions Section C.2 Then, in Section C.3 we show two essential lemmas that
helpful for later proof. In Sections C.4
C.4and C.5
will rigorously restate and show those two
propositions, respectively.
C.2 Assumptions for Algorithm
Now, we state those assumptions. Most of them are boundedness assumptions. We first state our assumptions about the residual. Recall the residual defined in Algorithm is
r f(x),
for any obejective vector e and covariate z, where f is the prediction model.
Assumption 1. We assume the residual vector satisfies the following conditions:
23

---

(a) Boundedness: the residual vector is bounded that E [-1,
(b) Distribution: the residual vector given the covariate z fooloos some unknown continuous distribution Pr|z with the density function Pr|z-
(c) Smoothness: for any two covariates 2, E [0, 1]s, the difference between the conditional means of Priz and Prys satisfies
|||r| E[rr2']12 S L||z - -2'112
for some positive constants L, > O.
Assumptions (a). are just boundedness conditions. Assumption (c) says that the distribution of the residual vector r given the covariate z enjoys some smoothness, and s measures the order of the smoothness. Specifically, if we perturb the covariate little bit, the perturbation will only slightly change the corresponding conditional distribution of the residual given 2. This condition is weaker than many recent papers with some true-model assumptions. For example, Wang et al. 22021, Kannan et al. 2020] assume e = fo(2) + e for some function fo(2) and random noise e, and Kannan al. [022 also assume that all objective vectors for different covariates share same type of randomness. When fu(2) can be learned by the prediction model, Assumption (c) holds for L == 0 and
Assumption 2. We assume the covariate z satisfies the following conditions:
(a) Boundedness: the covariate is bounded that E [0, 1]a.
(b) Distribution: the covariate follows some unknown continuous distribution Pa with the density function p(z) E C* ([0,
(c) Smoothness: the density function p(z) ((O, 1Jd) satisfies p(z) p and [p S for some positive constants p, and all [0, 1jd.
The first two parts of Assumption are also boundedness assumptions. Part (c) guarantees that the density function is smooth enough so that it has no steep peak and can not change drastically around any covariate z. We remark that by other weaker assumptions that can be satisfied by any density function. The last assumption is about the kernel function we used in Algorithm 4 It basically requires the kernel function to have bounded support and a positive lower bound on the support. This condition can also satisfied by many kernel functions, such as the uniform kernel and the truncated Gaussian kernel.
this assumption only for simplicity. and it can be replaced
Assumption 3. We assume the kernel function satisfies
K(2) b, 1(K(z) >(12)000 0} and K(2) S ba
max Ioordd
|2
S
R
for some positive constants bR, by > 0 and R> 1.
C.3 Essential Lemmas Proving Propositions Band
In this section, we let T [Dnat] and the bandwidth h = T-?, where y is parameter that will choose later. Without loss of generality, we let D {1, T). For any vector Rdd, (2)4 to denote its i-th entry for I,.... d. In addition, denote 20 as the target covariate, denote S0330 the value of the kernel function evaluated 2; with bandwidth h, and denote k)
K, K(
(x( = ΣT_ _ ) as the corresponding weight for any E D Moreover, for simplicity, by a little abuse of notation, we drop the input variables the kernel and weight functions and use K₁ and w, represent the value of the kernel function and the weight when the context is clear.
Before proving Propositions and 4 we first provide two essential lemmas. Lemma shows that, with high probability, there are least O (T1-dr) samples with positive weights. In the proof of the later lemma and Propositions and we will utilize those samples to give an approximation of the conditional mean of the target distribution Pr/z-
24

---

for any positive constant E (0, and 2 max 100 (2)) (+)
Lemma 1. Under Assumption with probability no less than
2'
T
1(
f1r > 0} (2R) log
(25)
Specifically, if dy and T is sufficiently large such that ((28)dT1-4) 2 2//TooTT.
T
Σ
1(r > 03 (2
(26)
Proof. In the following, we show the first inequality (2 The second inequlity (26) can be obtained by plugging the condition & (22R) 2 2/T T into 25
By Hoeffdiig's s inequality, we have for any target covariate with probability no less than 1 1
7
T E1ta > 0} 2 TE
{
max I(=); - (zo)d S R. VT log log T, :I......
where the probability is taken with respect to for = I,...? T. Thus, it is sufficient to show that with probability no less than
R. R H (2R)
8
max [()): (=);-(zo):
where the probability is taken with respect to zy. To see this, for any 2g such that p(2o) > 6/4, by Assumption (c), have that when T
1/7
1y/ee
p(2)
pl
cvdRR T
8 8 8
2
:=.....d for all satisfying max [(=); (=));-(z)) < R-T where the first line comes from Taylor's expansion
and Assumption (c), and the second line comes the condition that T 2 Avde 1/7
Thus, by
integrating the density function on the set 2: max [(2); (20)el I R T-y we have
max [(=); - (zo) R. 7-7 8 2 (22))
i= il......d
Moreover, since P([z: : p(z) < 8/2)) ((=)) < 5/2) < 6/2, we have P((z p(z) > 8/2)) 8/2, and finish the proof.
The next lemma develops the concentration property for ro defined in Step 3 in Algorithm
Lemma 2. Under Assumptions and for any T > O, with probability no less than 1 inequality below holds for all
2n the
72
T
2bR 7- . br
Σ
w (r(rr)s
S
where ī = Σ 1ww > 0}. Here, the probability taken with respect to the covariates 2i...., 2T
and their corresponding residuals.
25

---

Proof. This is also an application of Hoeffding's s inequality. We first show it for fixed 21,...., 2T and T
1w > 0} is fixed as well. Moreover, for any wy > O, by Assumption Bnd its definition Algorithm that it is a ratio between corresponding non-zero kernel functions, have w/ bbx b. entry of the residual is in [-1, 1J, we have wA (rr) bounded by [- bz ba) Thus, by Hoeffding's D. by
fixed target covariate 2g. In this case, we have T T Σ
1=1
b, bu In addition, by Assumption (a that each
inequality (Lemma we have with probability no less than 1 2/T
we . (re)s
Σ
T
w. (rrr
26R T log - by
for any i = 1,....d d. Then, we can find the result by taking the union bound for all entries = 1,.... and integrating the probability with respect to ,.,...; 2T.
Now, we are equipped with all essential lemmas, and in the following, we will show Propositions and 4
C.4 Proof of Proposition
In this section, we will adapt the same notation as in Section
C.3
Proposition 6 Under Assumptions
7
and
3
with probability no less than 5,
bR by
16L 8
32
[|E[]|a]] rolla S
/2
R
+ 81/2
T 2riza log T
holds when choosing the bandwidth h T
20122
Proof. To prove it, we first apply the triangle inequality that
||[r|a]] - roll2 - |||r zol - Esrol=o .... 2T|l12 + Ilro - E[rol lo. 2T|122
|||r zu]
wr + ||ru E/rol .... 2r|122
(27)
T S L,
Wel [[] E[rla + ||ro B|rol2o, B(rollo...., 2r
T
< L, we 2n - = + ||ro- -
2T]l
where the first and the third line come from the triangle inequality, the second line comes from the definition of ro Σ Wer', and the last line comes from Assumption I (c). In the following, we 1=1
T
analyze the first and the second terms in the last line, respectively.
We first analyze the first term in the last line of (7 Denote T
Σ 1[w, 0}. By Hoeffding's
inequality, for fixed 20, we have with probability no less than
722
T
T
Σ we|lzz - =:11ē
Ke|l zxllă
T
K₁
[=1
1
Ki|1z0 - zells
(28)
7
<
(TE[ Ki |||]
TIE
20l1E] + 2 R2 log log
1,7
26

---

where the first line comes from the definition of wt, the second line comes from Assumption 3 which gives the lower bound of the kernel function, and the third line comes from Hoeftding's inequality. Then, we compute the expectation
2 zollål < P(K1 > 0) bgdd R
p (2RT-7) bRd RTT 77
p l nater-er-dy
Here, the first step is obtained by Assumption 3 the upper bound of the kernel function and the boundedness of its support, the second line comes from Assumption 2 the upper bound of the density function, and the last line is obtained by calculation. Plugging this upper bound into 22 we have the first term in the right-hand side of (27 can be bounded by
LbR (2 (2 b,T
L Σ
w.
2el12
R/ log///2-0000g7 log log
(29)
we have for Then, for the second term in the right-hand side of (27 under the event of Lemma] fixed 2g
2bnyn 2r
[no E/rol Eos
- 1 log
(30)
br
Next, combine
29 and
30 to draw the result. Under the event of Lemma that
T2 0 8
8
(2R)
the inequality 29 becomes
SLbR 8b,
We
=0
21 112
(DR* + 12/22-d min( log
(31)
and the inequality (30) becomes
Iro E|rol Fo. ze]ll2 S b,2 p2/28//2
bavn
1-dr
log T.
(32)
The event of the intersection of events corresponding to Lemma and inequalities
29 and 30
happends with probability no less than 1 2/2 2r43 Thus, if T 2 4n
plugging
31
and
32
into we have with probability less than 1 5,
bR
(16L
32 81/2
E [ rolla s
22 R
T
log
Finally, let
2x we finish the proof.
C.5 Proof of Proposition
In this section, we also use the same notation in Sections C.2 and C.4 We show that the optimality gap between the solution given by Algorithm and the optimal solution converges to
co.
Proposition Suppose the feasible region {x Ar < b, 0} is included in the unit ball {x : ||~||| < J.. and the absolute values of each entry of the prediction function is bounded by f. Under Assumptions
7 and Algorithm outputs solution i(20) such that with probahility
less than -8
bR
32T
64
)
E (0(20) x" (zo))
5
/22 R
log T,
b,
81/2
where x² (20) the optimal solution to [P(] A, A,b), and the probability taken with respect to 21, my 2T, their corresponding objective vectors, the constraints (A, b) and the target covariate zo-
27

---

Proof. This is a direct application of Proposition 6 We first show the relation between two LPs with different objective vectors, For any two LPs with different objective vectors c C2 but with the same constraint (A, b), denote si and x2 as their optimal solutions. Then, if the optimal solutions are contained in the unit ball, we have
c] (xz z;) = (c) m - -2 - (c2 2 -
- + + (c oं - cj 2]
$ |c <2 22 ||| c2 c (c2 22 02 xt)
(33)
< |cc <2 12|1||11 |cc c2 2
S 2||c1 02112,
where the first step is obtained by rearranging terms, the second step is obtained by Cauchy inequality, the third step is obtained by the optimality of z with respect to the objective vector e2, and the last step is obtained by the condition that 2 and are in the unit ball.
Then, since in the event of Proposition that happens with probability no less than 8,
bR 166L. b,
32
[[r] - roll2 S
22 R +
T
log T,
81/2
and the difference between the objective vectors is the same as the difference between the correspond- ing residuals, the inequality (33) implies that
bR b,
32L pd
64
[o] T (zo) - =(zo)) -
R² +
T 2 log
(34)
81/2
and we finish the proof.
D Auxiliary Lemmas
In this section, we state some useful lemmas the information theory that are helpful in our proof. Lemma 3 (Hoeffding's inequality). Let X1, ..... Xr be independent random variables such that X takes its values in [ug, U2] almost surely for all t I T. Then the following inequality holds
n E
2T
PP
X1 EX, 2
< 22ex
5 E (2: - 0z
for any > 0.
Proof. We refer Chapter 2 of Boucheron et al. 2013
E Additional Related Work
Due to the space constraints in the main text, we provide additional discussion on related work here.
Contextual RO with parametrized prediction model. An alternative approach contextual robust optimization relies on the assumption that the relationship between the outcome variable c and the covariate is governed by parameter in the true underlying model. In this approach, the estimation/prediition process and the optimization problem are integrated by constructing an uncertainty set for the parameter 0 to mitigate the estimation uncertainty. Zhuu al. 2022 constructs the uncertainty set for 0 that contains all the parameters with training loss no worse than a threshold, but no coverage guarantee is provided. This can also be viewed a special case of the decision-driven regularization model introduced in Loke et al. (2022). Another study by Cao and Gao [222] extends the consideration of uncertainty to both the parameter and residual. However, the incorporation of estimation and optimization processes in one optimization model can raise tractability issues, restricting the choice of complex yet expressive prediction models.
For the contextual stochastic optimization problem with a risk-neutral objective, below is the other two streams of work in addition the wedict-then-optinie paradigm illustrated in the main text.
Local learning- conditional stochastic optimization. One stream of work tends to construct stochastic optimization problems with estimated conditional distributions learned by some local
28

---

learning methods. Hannah et al. 2010] approximates it by using Nadaraya- Watson kernel regression [Nadaraya 1964 Watson 1964] to reweight the historical data. [Bertsimas and Kallus 2020 further generalizes it to framework using broader range of non- con-parametric machine learning methods based on local learning, such as KNN [Altman] 1992]. classification and regression trees [Breiman] 2017].
To overcome the overfitting effect of these methods when the sample size is small, distributionally
robust optimization (DRO) methods are introduced. [Bertsimas and Van Parys [2022] enhances the robustness of bootstrap data by constructing the entropy -bosed DRO model. Nguyen et al. (2020)
202T], Wang et al. [2021]. Bertsimas et al. [003]] investigate the Wasserstein based DRO model. Ho
and Hanasusanto 2019 designs regularized approach and obtains tractable approximation by
leveraging ideas from DRO with a modified x² ambiguity set.
End-to-end prescriptive analytics without prediction. Instead of learning to predict uncertain
outcomes, |ann and Rudin [2019] directly learns the function mapping from covariates to decisions by employing the linear decision rule for the newsvendor problem. There are also further studies investigating such integrated approaches without prediction using more complicated models [Bertsi- mas and Koduri 2022], such random forests [Kallus and Mao 2022] and neural networks [Chen ct al. 2022]. Nevertheless, the robustness of the decisions to the epistemic and aleatoric uncertainty rarely considered in these papers.
29


Reviews:
[{"review_id": "lERevZJZM3", "reviewer": "Reviewer_kcWq", "summary": "This paper considers a risk-sensitive version of the contextual LP problem by replacing the original risk-neutral expected cost objective with VaR. The authors propose a new paradiam termed \"predict-then-calibrate\" that first learns a prediction model, and then uses calibration to quantify the uncertainty of the prediction. They present two algorithms that output a box/ellipsoid uncertainty set. The authors then provide a coverage guarantee for both algorithms, and conduct empirical experiments that show favorable properties of the proposed algorithms.", "questions": "- Can the authors provide more guidelines for the modeling choice of $\\hat{h}$? In practice, how to determine which model is better for $\\hat{h}$?\n- In Figure 4 and Table 1, the authors use the Kernel Ridge method with the RBF kernel as the prediction model and the NN model as the preliminary calibration model in both PTC-B and PTC-E (I found this in the appendix; please state it in the main text). Since RBF kernel works the best in Figure 3, this looks like a somewhat unfair comparison, since we are comparing the best among PTC-B/PTC-E with other algorithms. Can the authors elaborate more on this? Also, how does the run time of difference algorithms compare?\n- Is it possible to empirically demonstrate how good the proposed algorithms do in terms of individual-level coverage?\n", "limitations": "The authors discussed the limitations in the conclusion session.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- This paper considers contextual linear optimization problems with a risk-sensitive objective, which is a good complement to existing risk-neutral contextual linear optimization literature. It also complements the conditional robust optimization literature by providing a flexible algorithm in terms of the modeling choices. The idea of adding a calibration step in contextual linear optimization is novel.\n- The two algorithms provided are intuitive and flexible to implement. \n- The paper is overall clearly written and well-structured. The authors use simple intuitive examples to illustrate the value of better prediction and calibration, which I find really helpful.", "weaknesses": "- The modeling choice for $\\hat{h}$ seems vague to me. More elaborations on this subject would be helpful.\n- I have some concerns regarding the comparisons in the empirical session. See \"questions\" for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the comments and feedback, and we hope our response to the raised questions further clarifies the positioning of the predict-then-calibrate framework, and in what way it is connected with the existing results and potential future works. \n\nThe choice of model $\\hat{h}:$\n\nIn short, the vector function $\\hat{h}$ specifies the shape of the confidence set. In other words, the vector function $\\hat{h}$ captures the heteroscedasticity (with respect to the covariates $z$) of the prediction residual. Essentially, the confidence interval reduces to the quantile prediction, which results in the choice of pinball loss here. The optimization/learning problem of (5) aims to fit a quantile model to the residuals $r_{ti}$’s. So $\\hat{h}$ can be chosen as any model that is compatible with the optimization of the pinball loss, including linear models, NNs, and gradient boosting regression. A natural criterion for selecting $\\hat{h}$ would be to select the one with the smallest empirical loss of (5) as this will lead to the most accurate quantile prediction (and hence the confidence set prediction). \n\nMore discussions on Figure 4 and Table 1:\n\nThe reviewer raised a nice point that the implementation of PTC-B/PTC-E uses several different prediction models such as linear models, RBF kernel, and NN. Meanwhile, for the benchmark methods, the method “kNN” is indeed tied to the use of the k-NN as the prediction model, and the methods “DCC” and “IDCC” are tied to the use of the neural network model. They can’t be adapted to other prediction models. This in fact highlights that in handling robust contextual optimization problems, the predict-then-calibrate (PTC) proceeds in two steps, first predict and then quantify the prediction uncertainty, while these existing methods are a one-step procedure. The two-step procedure offers flexibility in choosing the prediction model and thus can best utilize the power of the off-the-shelf ML toolboxes. To some extent, we think this PTC framework is not quite about one new method to outperform the existing benchmarks, but to extend these existing methods to a larger scope -- first, develop the best ML prediction model, and then properly characterize the prediction uncertainty. Importantly and ideally, such disentanglement of prediction and uncertainty quantification provides better empirical performance and theoretical tractability. \n\nRun time:\n\nFor the uncertainty quantification part, the run time of PTC-B and PTC-E algorithms depends on the selected models in prediction and calibration. \n For the downstream robust optimization problem, the runtime depends on the shape of the specified uncertainty set. There are three types/shapes of uncertainty set in the experiments. (1) Box-shaped uncertainty sets for the PTC-B algorithm, which leads to an LP by reformulating the RO problem, so it is the most computationally efficient. (2) Ellipsoid-shaped uncertainty sets for the kNN and PTC-E algorithms in comparison, which leads to a second-order conic programming problem in the reformulation of the RO problem. (3) Specific-shaped uncertainty sets for the DCC and IDCC algorithms proposed in (Chenreddy et al. 2022), where a decomposition-based solving method has been presented in their paper and the termination criterion is defined by the tolerance gap or maximum iteration, so the run time also depends on the self-defined settings. Generally speaking, the run time is (1)<(2)<(3). Considering that the run time of (1) and (2) is not much different in our experiment, while the run time of (3) depends on their own Settings, and the time is not long (each instance is basically no more than half a minute), so we didn’t compare it in the paper. \n\nIndividual coverage:\n\nWe mentioned the limitation of global coverage in our paper. In fact, this is not an intrinsic problem associated with the PTC framework. If one aims for individual coverage, one can choose accordingly an uncertainty quantification method that satisfies such an objective. We invite the reviewer to check our response to Reviewer tVPZ for more details if you are interested and have time.\n\nWe hope the above response addresses the raised questions, and if there are any further questions/confusions, we will respond timely in the following discussion week."}, {"review_id": "fkp7IuKUt7", "reviewer": "Reviewer_1GB8", "summary": "This paper considers the contextual linear optimization problem, where one is given a vector of covariates $z$ that can be used to predict a cost vector $c$, and one wishes to solve the following LP:\n\n$ \\max \\ E[ c \\mid  z]^T x$\n\n$ \\text{subject to}: A x = b, x \\geq 0  $\n\nThis is the risk-neutral version of the contextual LP problem. The risk-sensitive version instead considers the $\\alpha$-value-at-risk with respect to the conditional distribution of $c^T x$ given $z$:\n\n$ \\max \\ VaR_{\\alpha}( c^T x \\mid z )$\n\n$ \\text{subject to}: A x = b, x \\geq 0  $\n\nThe paper proposes an approximate method for solving this problem, where one approximates the VaR with a max over $c$'s in a fixed uncertainty set that depends on the given covariate vector $z$. The uncertainty set itself is obtain from a procedure that in the abstract works like this: take a prediction model $\\hat{f}$ and make predictions of $c$ in a validation set. Calculate the errors/residuals, and build another model, called the calibration model, to predict these residuals. One then constructs an uncertainty set conditional on $z$ where the center comes from the prediction model and the width comes from the calibration model. This approach is shown with high confidence over the validation set to satisfy the $\\alpha$ probability coverage requirement. The paper also tests this approach using synthetic toy instances as well as instances based on the contextual shortest path problem, and shows that it leads to better (lower) VaRs than existing robust-contextual proposals. ", "questions": "_Question/Suggestion 1_: If the goal is to maximize the alpha-VaR conditional on a given covariate vector, could the following simpler strategy not work: in Bertsimas and Kallus (2020), the authors propose solving the contextual problem by using a machine learning model to obtain an estimate of the conditional distribution of $c$ given $z$. (For example, for a CART tree, one would run the given $z$ down the tree to determine the corresponding leaf, look at the historical $(z',c')$ pairs that are in that leaf, and consider the distribution with a weight of $1 / M$ on the $M$ pairs of $(z', c')$ values that are in that leaf, and a weight of zero on all other observations.) Bertsimas and Kallus discusses how this type of strategy can be used in conjunction with other machine learning models, such as random forests and k-nearest neighbors. \n\nMy question here is why could one not take a similar strategy here; specifically, why not output the $x$ that maximizes $\\alpha$-VaR with respect to the estimated conditional distribution? So for example, for CART, this would mean minimizing $\\alpha$-VaR with respect to the same discrete distribution that puts a weight of $1/M$ on the $M$ points that are mapped to the same leaf as the given $z$. (This would likely be some kind of simple MIP problem.)\n\nIn addition to the connection to the existing work of Bertsimas and Kallus, this simpler strategy is also appealing in that one does not need to specify a prediction and a calibration model separately; there is only one machine learning model used that needs to be specified. \n\n\n_Question/Suggestion 2_: Is it possible to say something about how \"optimal\" the proposed predict-then-calibrate approach is? To elaborate, in Bertsimas, Gupta and Kallus (2017), one deals with a robust linear constraint of the form\n\n$\\mathbf{u}^T \\mathbf{x} \\leq b, \\quad \\forall \\ \\textbf{u} \\in \\mathcal{U}$\n\nand one assumes that the actual value of $\\mathbf{u}$ is the random variable $\\mathbf{\\tilde{u}}$. One then seeks to select $\\mathcal{U}$ so that\n\n$ \\text{if} \\ \\mathbf{u}^T \\mathbf{x} \\leq b \\quad \\forall \\mathbf{u} \\in \\mathcal{U}, \\ \\text{then} \\ \\mathbb{P}( \\mathbf{\\tilde{u}} \\mathbf{x} \\leq b ) \\geq 1 - \\epsilon$\n\nBertsimas, Gupta and Kallus (2018) note that this guarantee can be met if $\\mathcal{U}$ is chosen as a $1 - \\epsilon$-confidence region for $\\mathbf{\\tilde{u}}$, i.e., if $\\mathbb{P}( \\mathbf{\\tilde{u}} \\in \\mathcal{U}) \\geq 1 - \\epsilon$, but this is not the only way that the guarantee can be met, and by choosing a smaller $\\mathcal{U}$ one can still have the some probabilistic guarantee and be less conservative. Gupta (2019) shows that a number of uncertainty sets that have been proposed that are based on this confidence region idea are unnecessarily conservative, and that one can obtain much smaller uncertainty sets with the same probabilistic guarantee. The proposed methodology in the paper (replace the intractable problem on lines 106 - 107 with problem (4), and then apply either Algorithm 1 or 2) seems more aligned with this confidence region approach, so it would be great if the authors can discuss more on how tight / optimal this approach is. \n\n_Question/Suggestion 3_: It would be nice to see better motivation for the contextual VaR formulation that the paper studies, both in the introduction and the numerics. \n\n_Other comments/suggestions_:\n\nPage 5, line 143: \"but rather the only two options\" $\\to$ \"but these are not the only two options\". \n\nPage 9, line 264: the word \"better\" is repeated here. \n\nReferences:\nBertsimas, D., Gupta, V., & Kallus, N. (2018). Data-driven robust optimization. Mathematical Programming, 167, 235-292.\nBertsimas, D., & Kallus, N. (2020). From predictive to prescriptive analytics. Management Science, 66(3), 1025-1044.\nGupta, V. (2019). Near-optimal Bayesian ambiguity sets for distributionally robust optimization. Management Science, 65(9), 4242-4260.\n\n", "limitations": "The discussion of limitations seems adequate; as noted in my questions above, it would be nice to have some discussion of how optimal this approach is. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- From a novelty standpoint, I think this paper does present something new; to my knowledge the combination of value-at-risk within contextual optimization has not been done before.\n\n- The method seems reasonably simple and could be implemented easily. It is also nice to see that there is a high-confidence guarantee on the coverage probability of the set $\\mathcal{U}$ produced by Algorithms 1 and 2. Another nice aspect is that the validation data set does not need to be the same data set used to train the predictive model $\\hat{f}$; this goes along nicely with the goal of robustness in the paper.\n\n- I appreciate that the authors provided the simple examples in Section 3.2 to illustrate how the approach works and the difference between having a good prediction model vs. calibration model. ", "weaknesses": "- I think the motivation of the paper is a little weak. While I understand the motivation for predict-then-optimize / contextual optimization, and the motivation for optimizing value-at-risk, it is not clear to me why one would want to couple these two things together. The introduction very quickly brings up the \"risk-sensitive\" aspect of the problem without providing an accompanying problem from the literature or from practice that would need this type of machinery.\n\n- From a practical standpoint, there are a lot of questions that are unanswered, namely how good is the method (can one do better than this method in certain cases? see my suggestion #2 below) and how should one choose the prediction model and the calibration model? \n\n- The numerical evaluation feels incomplete, and the method should be compared to stronger benchmarks; for this type of contextual problem, it feels like there should be lots of ways that one could represent the conditional VaR with respect to a given predictive model (see my suggestion #1 below, on using the conditional distribution outputted by the predictive model). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the comments, and in particular, for the detailed suggestion improving our paper.\n\nMotivation for the robust formulation:\n\nWe thank the reviewer for raising the point. Our problem setup lies at the intersection between robust optimization and contextual optimization, thus it has two positioning from the perspectives of both lines of the literature. The notion of contextual optimization has become popular in the recent decade. Our work is among the earliest efforts in working on the risk-sensitive contextual optimization problem; and compared to [7] and [20], our work emphasizes (i) the flexibility in choosing the prediction model, and (ii) the disentanglement of the prediction and the uncertainty quantification. As for the motivation, we believe it’d be better to take the perspective of robust optimization. The literature and methodology of robust optimization (RO) have been widely applied in various domains such as manufacturing, control system, energy, finance, etc. For all these RO applications, it can also be the application of the robust contextual optimization, and the framework of PTC, as long as there is a presence of covariates, which is more and more commonly available nowadays. Compared to the traditional RO methods, the PTC framework enables contextualized uncertainty set and thus provides more dynamic and less conservative solutions. \n\nPractically, robust contextual optimization has been used across many applications, such as transportation (Guo et al., 2023), portfolio management (Wang et al. 2022), and healthcare (Gupta, Vishal, et al. 2020). Also with a few more applications mentioned in [7,23]. We will include more discussions on motivation in the next version of our paper. \n\nHardness of the problem and MIP formulation:\n\nThe robust optimization, even without the covariates, is generally NP-hard due to joint optimization over the decision variable and the uncertainty set. We adopt an approximation approach that gives up the optimization over the uncertainty set but just sticks to one single uncertainty set. The mixed integer approach in Bertsimas and Kallus (2020) takes another route of reformulating the problem as a mixed integer program (MIP). The MIP reformulation doesn’t change the hardness of the problem but is an exact reformulation, and for small-scale problems, it offers an exact solution. We should have mentioned this in our paper, and we appreciate the reviewer for pointing it out. \n\nCompatibility with other existing results: \n\nIn the paper, we mainly present the PTC framework for approximately solving the robust optimization (RO) problem, and generally, such a route lacks a theoretical guarantee on its optimality (even for the context-free case). Meanwhile, the PTC framework is also compatible with the MIP reformation, and when there is an optimality guarantee for the context-free robust optimization, the PTC framework is capable of migrating the result to the contextual case. \n\n- One-step approach v.s. two-step approach: Both approaches aim for predicting the distribution of $c|z.$ The literature on uncertainty quantification/conformal prediction usually adopts this two-step approach, and this in fact has a theoretical justification. The two-step procedure first predicts the conditional mean with $\\hat{E}[c|z]$ and then tries to predict quantiles/distribution of $c-\\hat{E}[c|z]|z$. To fit the error $c-\\hat{E}[c|z]|z$ can be easier than the original $c|z$ because the error conditional distribution is usually smoother, and ML models can be more sample efficient when fitting smoother functions. To see this, generally, the conditional expectation function $E[c|z]$ is highly related and very likely to wax and wane together with the quantile function $Q_{\\tau}[c|z]$. In this light, subtracting $E[c|z]$ can very likely smooth out the quantile function $Q_{\\tau}[c|z]$. In metaphor, this is quite like the method of controlled variates in Monte Carlo simulation which introduces a controlled random variable that is correlated with the target random variable to reduce the variance of the estimator. Here, the conditional expectation function $E[c|z]$ works as the “controlled variate” for the original “target variate” of $Q_{\\tau}[c|z]$. Between these two approaches, we don’t argue for the superiority of one over the other, and one can follow the training-validation approach to pick the better one for a specific dataset. \n\n- Our algorithms are compatible with the MIP formulation of the RO problem. For example, once we obtain the output of Algorithm 2, we can use it as a generative model to generate samples from the conditional distribution of $c|z$. And then we can plug these samples in the MIP formulation in Bertsimas and Kallus (2020). \n\n- We thank the reviewer for bringing our attention to Gupta (2019). We weren’t aware of the work and read it with great interests. The uncertainty set constructed by Gupta (2019) has an ellipsoid form. For the contextual setting, the PTC framework can also predict the conditional mean and conditional variance of the posterior distribution as the parameters for the ellipsoid for some fixed prior distribution. Then, one can construct the uncertainty set in a similar manner as Gupta (2019). Consequently, under some additional assumptions, one can also prove similar optimality results as in Gupta (2019) for the contextual LP problem. We will include more discussions on this in the next version of our paper.\n\nWe also thank the reviewers for pointing out some typos in our writing. In the coming week, we will get back to you timely for follow-up questions. "}, {"review_id": "lpeDsT1ztJ", "reviewer": "Reviewer_VdM1", "summary": "The authors study a risk-sensitive contextual LP setting. They seek to predict the objective function of the LP from a context vector using a generic machine-learning algorithm, and then use this prediction to achieve a low (good) objective value in the LP. Their insight is this can be done cleverly with calibration—instead of changing the ML prediction as others have done, they calibrate the output. In theory and empirical evidence, they show their method has advantages over competitors.", "questions": "1. Have the authors' investigated the application to conditional value at risk?", "limitations": "Not much discussion, a little bit in Future Directions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- There is substantial interest in the predict-then-optimize setting for LPs (see the citations on Grigas and Elmachtoub). This setting (while not mentioned by the authors) seems to have clear applications in finance.\n- The authors' work is clearly presented and claims are backed up by theory and experiments. The theory and experiments support the claims not only that the approach achieves better objective values, but gives a more detailed view of why (I particularly like 3.2).", "weaknesses": "- The method combines tools that we understand pretty well. In particular, it leverages the detailed picture of robust optimization linear programs that we have. The results are naturally limited to LPs.\n- There isn't much discussion of limitations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for bringing up the finance application. We are not quite experts in the finance domain, so we didn’t mention it in the first place. However, in the next version of our paper, we will include more discussions about it. Generally, this financial application leads to a natural consideration of CVaR objective for its convexity and time consistency. \n\nCVaR objective instead of VaR: \n\nThe framework of predict-then-calibrate (PTC) is more about a generic approach that first predicts the objective vector and then quantifies the uncertainty of the prediction model for the downstream robust task. In particular, PTC specifies a procedure to characterize the conditional distribution $c|z$. For the VaR objective, it outputs box- or ellipsoid- shaped confidence set so as to meet the tractability of the robust task. In comparison, for the CVaR objective, one should replace the calibration part with a finer characterization of the conditional distribution. This indeed can be done with minor modifications of Algorithm 2 or other algorithms of a similar spirit. Note that Algorithm 2 fits a multivariate Gaussian distribution for $c|z$; with the fitted model, for newly observed covariates $z_{new}$, one can generate a number of independent samples\n\n$\\tilde{c}_1,....,\\tilde{c}_k$\n\nfrom the conditional distribution of $c|z_{new}$. Then to optimize the following empirical CVaR objective\n\n$\\min_{x} \\min_{\\gamma} \\gamma+\\frac{1}{k}\\sum_{j=1}^k (\\tilde{c}_j x - \\gamma)^+$\n$s.t. Ax\\le b, x\\ge 0$\n\nThis is a convex program that has an equivalent linear program. We haven’t thought about this in the submitted version of our paper. However, we do find it interesting, so we will include more discussion of the CVaR objective as an extension in the next version of our paper. Moreover, we remark that the method to fit the distribution $c|z$ can be quite flexible and it can be replaced with any generative probabilistic model that outputs a distributional prediction.\n\nGeneral optimization problem beyond LP:\n\nWe presented the PTC framework under the problem of LP for that LP seems to be the most natural playground for studying robust contextual optimization. One key point here is that for the contextual-free (without $z$ or $z=1$ a.s.) case, the robust VaR formulation should have a tractable (approximate) solution; then we can utilize the structure to tailor the uncertainty calibration part. Specifically, for the robust LP problem, the context-free case follows the box- or ellipsoid-shaped uncertainty set, so the PTC algorithms inherit the structure and have the calibration model output (contextual) uncertainty set of corresponding shapes. For more general problems such as the quadratic program or convex program or even multi-stage stochastic program, as long as the context-free robust problem has a tractable solution, we can design the PTC algorithm accordingly. Compared to the context-free case, such PTC design contextualizes the uncertainty set with the context information. To this end, PTC behaves more like a plug-in module that can fit into the existing robust optimization literature. We should have included more discussions on this in our paper; we thank the reviewer for noting the point and we will include it in the next round. "}, {"review_id": "OD6PFldldl", "reviewer": "Reviewer_4BGT", "summary": "The author(s) propose a novel method of robust contextual LP, which extends the conventional contextual LP problem by allowing some uncertainties from the prediction model. It is very well-written, and states very clearly what is the problem setting, and in which direction this work advances. The model properties are discussed in detail and the implication of each theory/statement is explained in a very careful manner. \n", "questions": "1. Proposition 1 provides a coverage guarantee for Algorithm 1 and Algorithm 2. I was a bit confused by the statements. On the left hand side, the inequality goes to 0 and $|\\mathcal{D}_2|$ increases. While on the right handside, the inequality goes to 1 as $|\\mathcal{D}_2|$ increases. Does it mean the more observations in $\\mathcal{D}_2$, the more uncertainty there will be? It would be nice if the author could provide more explanation on it.\n2. As stated above, all theoretical guarantees mentioned in Section 3.1 require $\\mathcal{D}_2\\sim \\mathcal{P}$, e.g. the validation set is correctly specified. For practical application purposes, could the author provide some strategies to make sure this requirement is guaranteed?\n3. In the Experiment Section, Simple LP Visualization paragraph, the author mentions both PTC-B and PTC-E. Maybe I missed it, but it seems in Figure 2, the author only provides visualization for PTC-B. Where is PTC-E?\n", "limitations": "See above for list of areas for improvement.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. Clearly written and well organized\n2. Provides a clear problem statement, and the algorithms are described in good detail\n3.  Strong algorithm analysis with additional detials to provide context for the statements\n4. Good empirical work demonstrates the method\n5. The author proposes two algorithms to construct the contextual uncertainty sets $\\mathcal_{U}$ (which is based on z) for the prediction model. They mention the choice of the prediction model is quite flexible, and there are a couple of advantages by doing so.\n", "weaknesses": "1. It would be nice if the author could provide the audience with some motivations for this work. For example, under what circumstances would it be beneficial to incorporate a risk-sensitive objective into contextual LP.\n2. All theoretical guarantees mentioned in Section 3.1 require $\\mathcal{D}_2\\sim \\mathcal{P}$, e.g. the validation set is correctly specified.  It would be useful to understand how misspecification impacts these results (either empirically or theoretically).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for all the comments and feedback.\n\nTypo in Proposition 1:\n\nThe inequality (8) should be “>=” instead of “<=”. We thank the reviewer for noting this mistake. We agree with the intuitions mentioned by the reviewer and now the inequality becomes aligned with these intuitions. \n\nPTC-E in Figure 2:\n\nWe are sorry for the caused confusion. In the setting of Figure 2, the algorithm of PTC-E will be exactly the same as PTC-B. Specifically, Figure 2 illustrates the benefits of a better prediction or calibration model in a one-dimensional case. In the one-dimensional case, the PTC-B coincides with PTC-E then because both the box-shaped and ellipsoid-shaped uncertainty sets will degenerate into line segments. We will mention the point in the next version of our paper.\n\nValidation set: \n\nThat's a great point. The theoretical results hinge on the fact that the validation set comes from the same distribution as the test data. Practically, just like the standard setup of machine learning, if one has an available training dataset that is from the same distribution as the test set, then one can reserve part of the training data as the validation data. If this is not true, which is known as the out-of-domain problem, where the training data and the test data may be from different distributions, the situation doesn’t become fully pessimistic. Indeed, our algorithms essentially calibrate the uncertainty of c|z. One type of out-of-domain problem is known as the covariates shift, where the distribution of z (covariates) changes between the training data and the test data, but the conditional distribution of the target variable c|z remains the same. In this case, the theoretical guarantee of our algorithms still works. Of course, there are other setups of the out-of-domain problem that may make the algorithms fail. In our opinion, this type of setup studies the potential discrepancy between the training data and the test data, and it deserves more attention from the literature on data-driven robust optimization and contextual optimization, where it often assumes a standard i.i.d. setting. To this end, we will include more discussions about it to call for more awareness of the problem. \n\nWe hope our response addresses the raised questions. We refer to our response to Reviewer 1GB8 for more discussions on the motivation of the formulation. If there are any follow-up questions/concerns, we will get back to you timely in the following discussion week. "}, {"review_id": "StDpZg02P3", "reviewer": "Reviewer_tVPZ", "summary": "The authors study a risk-averse variant of contextual linear optimization, using VaR as the risk measure. The authors develop two heuristic approaches. In both of these approaches, the problem of minimizing the VaR is approximated by a robust optimization problem. The authors propose two different ways of specifying the uncertainty sets, both of which involve building a regression model to predict the conditional mean of the uncertainty, and then calibrating the size of uncertainty with the intent of satisfying a coverage guarantee. The authors provide bounds on the probability that the coverage guarantee will be satisfied, and computational experiments that measure the performance of the proposed method against several baselines. In addition, the authors briefly discuss a distributionally robust variant of contextual linear optimization, and show that there exists a policy that converges to an optimal policy with a specific convergence rate.", "questions": "- In the box uncertainty quantification method, why did the authors choose to perform conditional quantile estimation in two steps, where first the mean is estimated and then quantiles are estimated from the residuals? I would note that in existing works where the mean is estimated and then a density is fit on the residuals, there is usually some assumption that justifies this. For example, if it is assumed that c = f(x) + ε, where the errors ε for different observations are i.i.d., then you can perform unconditional density estimation on the residuals (rather than conditional density estimation). However, I don't see any justification in this work. The authors answered this question in their rebuttal.", "limitations": "- One limitation (mentioned in the \"Weaknesses\" section) is that the coverage guarantees provided by the method are not the ones that would be desired in the stated problem. This is mentioned in passing, but the authors should investigate this limitation further.\n\n- Even in the absence of uncertainty, the proposed method by the authors is a heuristic in the sense that it does not identify the optimal solution nor are any approximation ratios known. It would be worth exploring how close (or far) the solutions are from optimal solutions.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The problem selected by the authors, namely risk-sensitive contextual linear optimization, is an interesting and relevant problem.\n- The design of the experiments provided is reasonable and the proposed methods show good performance.", "weaknesses": "- The exact form of the uncertainty set suggested by the authors seems poorly motivated. It would be helpful if the authors could explain why they chose the approach that they did. In the rebuttal, the authors provided an explanation that helped to motivate the form of the uncertainty set.\n\n- The coverage guarantees provided by the authors' methods are not the relevant coverage guarantees for the contextual problem (4). In particular, the conditional probability P(c ϵ U_α(z) | z) should be equal to α (approximately), but the authors instead have designed the methods to guarantee that P(c ϵ U_α(z)) is equal to α (approximately). I view this as a serious flaw in the method, as someone solving a contextual linear optimization problem is presumably specifying their risk for that context, and the authors' approach could in theory severely underestimate the risk in heteroskedastic settings. The authors should redesign the method to ensure that the correct coverage guarantee is met. In the rebuttal, the authors explained how the method could be adapted to provide a conditional coverage guarantee, and explained their rationale for using a global coverage guarantee rather than a conditional one.\n\n- Even if the goal were to produce an unconditional coverage guarantee rather than a conditional one, the theoretical guarantees in Proposition 1 and Corollary 1 are weak. Some very bad ways of choosing uncertainty sets would satisfy these guarantees. For example, you could specify your uncertainty set as a ball with a center of 0 and with radius chosen so that the proportion of samples from the validation set falling in the ball is equal to α, and it would have the same guarantees. It would be better if the authors could show some stronger properties that their choice of uncertainty set satisfies. The authors address this in their rebuttal by acknowledging that the theoretical guarantees could be satisfied by bad choices of uncertainty sets, there is other evidence in the paper that suggests that their choice of uncertainty set is effective. \n\n- In Proposition 3, the authors should ensure that \"P(c ϵ U_α(z) | z) = α\", not that \"P(c ϵ U_α(z)) = α\" since that is the relevant coverage guarantee for the contextual problem. I considered the possibility that this is a typo, but it can be confirmed that the coverage guarantee for the contextual problem is not satisfied. For example, when z=1, the probability P(c ϵ U_α(z) | z) = 1 - sqrt(2-2α)/2, which is not generally equal to α. This example should be reworked. This was also addressed by the author's discussion of the conditional and global coverage guarantees in the rebuttal.\n\n- Section 4 feels like a summary of a different paper that was inserted into this paper. The proposed method for the contextual DRO problem seems only loosely connected to the methods for the risk-sensitive contextual linear optimization. Furthermore, the authors relegate their proposed method for contextual DRO problems to the appendix and provide no computational results for this method. I recommend removing Section 4. The authors addressed this in their rebuttal by clarifying the connections between the contextual DRO problem and the risk-sensitive problem.\n\n- (A minor point) The authors are inconsistent as to whether the values A and b are random or constant. The methodology seems to assume that these are either fixed or, at the very least, independent of the values of c and z, so I would recommend treating these as constant throughout.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments and the raised questions. We believe the clarification of these questions will make the positioning of our work clearer.\n\nIndividual/conditional coverage guarantee:\n\nWe thank the reviewer for noting the point, and we have also mentioned in our paper this as a limitation of the proposed algorithms. However, we note that the predict-then-calibrate (PTC) framework is more of a general framework to tailor a prediction-aimed ML model for a robust task. The performance guarantee of the current two algorithms only hold for global coverage but not for individual coverage, yet this is NOT caused by the framework, but indeed by the chosen calibration/uncertainty quantification algorithm and the corresponding assumption. If we change the calibration algorithm to one that aims for an individual/conditional objective, the whole framework will be able to fulfill the individual coverage. Now we present such an algorithm and the corresponding theory results:\n\n- Calculate the residual $r_t=c_t-\\hat{f}(z_t)$\n- Perform a nonparametric regression with respect to $r_t$ using $z_t$ and a chosen kernel $k$ (such as simple window kernel or Gaussian kernel). This obtains the following function\n\n$\\hat{Q}(z;\\tau) = Q(\\sum I(r_t) k(z_t,z)/ \\sum k(z_t,z); \\tau)$\n\nwhere  $I(r_t)$ denotes a point mass distribution at $r_t$, and $Q(\\cdot;\\tau)$ outputs the $\\tau$-quantile of a random variable\n- For a new $z_{new}$, output the confidence interval by $[\\hat{Q}(z_{new};(1-\\alpha)/2), \\hat{Q}(z_{new};(1+\\alpha)/2)]$\n\nTheoretical analysis:\nUnder the Lipschitzness condition of the quantile function \n\n$|Q(c|z;\\tau)-\\hat{Q}(c|z’;\\tau)|\\le L\\|z-z’\\|$\n\nfor any $(z,z’)$ and some boundedness assumption, the produced confidence interval ensures a bot finite-sample and asymptotically optimal coverage for each $z_{new}$ almost surely.\n\nThe analysis is built upon the nonparametric theory. Please let us know if you and other reviewers want more details on the analysis. We will respond timely in the following week. \n\nWe note that the existing works on robust contextual optimization [7,20] also fail to achieve the individual coverage guarantee, and more important, these two existing works are restricted to certain prediction model such as k-NN or neural networks. Comparatively, our paper aims to encourage a more flexible choice of the prediction model, and the usage of uncertainty calibration method for robust optimization tasks. It is a secondary goal to achieve individual coverage guarantee, but as it shows above, the PTC framework doesn’t exclude the possibility of achieving this. \n\nTwo-step procedure:\n\nGenerally speaking, an ML prediction problem will become more sample efficient and easier when the conditional expectation/quantile function $E[Y|X]$ or $Q_{\\tau}(Y|X)$ is smoother. In our context, the two-step procedure first predicts the conditional mean with $\\hat{E}[c|z]$ and then try to predict quantiles/distribution of $c-\\hat{E}[c|z]|z$. To fit the error $c-\\hat{E}[c|z]|z$ can be easier than the original $c|z$ because the error’s conditional distribution is usually smoother. To see this, generally, the conditional expectation function $E[c|z]$ is highly related and very likely to wax and wane together with the quantile function $Q_{\\tau}[c|z]$. In this light, subtracting $E[c|z]$ can very likely smooth out the quantile function $Q_{\\tau}[c|z]$. In metaphor, this is quite like the method of controlled variates in Monte Carlo simulation which introduces a controlled random variable that is correlated with the target random variable such to reduce the variance of the estimator. Here, the conditional expectation function $E[c|z]$ works as the “controlled variate” for the original “target variate” of $Q_{\\tau}[c|z]$. Another example is the nonparametric estimator presented in above. The convergence rate of the coverage guarantee scales linearly with the Lipschitz constant $L$. And the corresponding Lipschitz constant for the conditional distribution $c|z$ will be generally much larger that of the error distribution $c-\\hat{f}(z)|z$. \n\nWhile such two-step procedure is commonly adopted in the literature of conformal prediction and ML model calibration, we provide the above explanation to justify such an approach, and we will include this discussion in the next version of our paper. \n\nSection 4:\n\nWe agree that Section 4 has less coherence with other sections of the paper, because the majority of our paper studies the robust optimization problem, while this section concerns the distributionally robust optimization (DRO). Yet, they all share one theme which is to make the choice of the ML model and uncertainty calibration methods more flexible. When we reviewed the related literature, we find that the DRO papers on contextual optimization usually impose very strong assumptions to achieve the performance guarantee. To this end, while Section 4 develops no new algorithm upon the existing literature, we believe it significantly relaxes the realizability assumption and the error distribution assumptions in the existing works. \n\nWe defer more responses to the raised question to Author Rebuttal. We are sorry for the inconvenience and we really appreciate your time in reading our paper and responses. Please let us know if there is any further confusion; we look forward to further discussion with you."}]

Author rebuttal:
We thank the reviewers for spending the time reading our paper, and for all the helpful comments. The raised questions inspire us to think about important aspects that we haven't come across when we write the paper. We look forward to further discussions in the coming week. 

We'd like to take the extra space here to further address a few comments made by Reviewer tVPZ. Our apologies for the confusion and the caused inconvenience.

Scalar adjustment:

One very simple adjustment that appears in both of our algorithms is the scalar adjustment, i.e., the choice of $\eta$. It is a very simple yet effective way to ensure the guarantee. As far as we know, this (surprisingly) seems to be the first such design in robust optimization, while many other works need a complicated procedure to ensure the coverage guarantee.

Motivation for our algorithm design:

As noted above and in our paper, our goal is to advocate for a more flexible choice of the prediction model and the uncertainty calibration method and also to show the value of contextual information in robust optimization. The framework is compatible with many algorithm designs such as the above nonparametric design, our response to reviewer VdM1 on CVaR objective, and our response to reviewer 1GB8 on mixed integer reformulation. We choose Algorithm 1 and Algorithm 2 as exemplifiers for the PTC framework because they naturally inherit the box- and ellipsoid-shaped uncertainty sets in context-free robust optimization. Algorithm 1 fits an ML model to predict the side length of the box while Algorithm 2 predicts the shape of the ellipsoid. We agree with the reviewer that the theoretical guarantees in Proposition 1 and Corollary 1 do not exclude the possibility of having a bad uncertainty set. First, we don’t observe such a phenomenon in our numerical experiments. Second, the PTC framework is generally compatible with other algorithm designs such as parametrized uncertainty sets (Wang et al. 2023, Learning for Robust Optimization). 

Optimality ratio:

The robust optimization problem, even for the context-free case, is an NP-hard problem in general due to the joint optimization over the decision variable and the uncertainty set. We didn’t provide any optimality ratio guarantee in our paper; neither does general robust optimization literature. In other words, the lack of optimality ratio guarantee is not caused by the contextual setup, the PTC framework/algorithms, or our analysis; it is determined by the nature of the robust optimization problem. However, we don’t exclude the possibility of achieving an optimality guarantee or a finer analysis. For example, as our response to reviewer 1GB8, we believe that under the same conditions as Gupta (2019), a similar optimality ratio guarantee can be achieved under the PTC framework and also as per our examples and discussions in Section 3.2. We thank the reviewer for raising the point and will include more discussion on this. 

Again, we appreciate the time spent by the reviewers reading our paper and all the comments. We look forward to further discussions in the coming week. 

Meta-review: The papers consider risk-averse objectives for contextual linear optimization. The reviewers appreciated the paper but raised some concerns. Overall the paper studies a new formulation of an important problem an interesting way and would be valuable addition to the conference. The authors should address the reviewers concerns as outlined in the rebuttal in the text of the paper when preparing a camera ready.
Decision: Accept (poster)