A Discretization Framework for Robust Contextual Stochastic Optimization
Authors: Rares C Cristian
Georgia Perakis
Venue: ICLR 2024 poster (2024)
Keywords: Robust Optimization
Stochastic Optimization
End-to-End learning
Primary area: optimization

Abstract: We study contextual stochastic optimization problems. Optimization problems have uncertain parameters stemming from unknown, context-dependent, distributions. Due to the inherent uncertainty in these problems, one is often interested not only in minimizing expected cost, but also to be robust and protect against worst case scenarios. We propose a novel method that combines the learning stage with knowledge of the downstream optimization task. The method prescribes decisions which aim to maximize the likelihood that the cost is below a (user-controlled) threshold. The key idea is (1) to discretize the feasible region into subsets so that the uncertain objective function can be well approximated deterministically within each subset, and (2) devise a secondary optimization problem to prescribe decisions by integrating the individual approximations determined in step (1). We provide theoretical guarantees bounding the underlying regret of decisions proposed by our method. In addition, experimental results demonstrate that our approach is competitive in terms of average regret and yields more robust solutions than other methods proposed in the literature, including up to 20 times lower worst-case cost on a real-world electricity generation problem.

Published as a conference paper at ICLR 2024
A DISCRETIZATION FRAMEWORK FOR ROBUST CON- TEXTUAL STOCHASTIC OPTIMIZATION
Rares Cristian, Georgia Perakis
Operations Research Center Massachusetts Institute of Technology, Cambridge, MA, USA (raresc georgi i ap) @mi mimm..... t........ edu
ABSTRACT
We study contextual stochastic optimization problems. Optimization problems have uncertain parameters stemming from unknown, conlext-dependent, distribu- tions. Due to the inherent uncertainty in these problems, one often interested not only in minimizing expected cost, but also to be robust and protect against worst case scenarios. We propose a novel method that combines the learning stage with knowledge of the downstream optimization task. The method prescribes decisions which aim to maximize the likelihood that the cost below (user-controlled) threshold. The key idea is (1) to discretize the feasible region into subsets that the uncertain objective function can be well approximated deterministically within each subset, and (2) devise secondary optimization problem prescribe deci- sions by integrating the individual approximations determined in step (1). We pro- vide theoretical guarantees bounding the underlying regret of decisions proposed by our method. In addition, experimental results demonstrate that our approach is competitive in terms of average regret and yields more robust solutions than other methods proposed in the literature, including up to 20 times lower worst-case cost on a real-world electricity generation problem.
INTRODUCTION
In recent years, the field of machine learning (MI. has made remarkable strides in developing pow- erful algorithms that can automatically extract patterns and insights from data. While prediction is often the primary focus in many MI. applications, the ultimate goal is to make optimal decisions based on these predictions. For example, may predict the hourly electricity demand of power plant for the next day. But more importantly, based off of this forecast, the operator must decide how much electricity generate in order to minimize cost while staying within the operational con- straints of the plant. Another key factor is the possible distribution of the uncertain parameters and being able protect against worst-case scenarios. In the previous example, the decision-make may have the goal to maximize the probability that their operational cost is below a certain threshold. Robustness is crucial property in real-world decision-making since single significantly poor de- cision may have separate damaging effects. For instance, it could damage a company's 's reputation and trust with its customers.
Traditionally, a rredict-then-optmiie approach has been used in practice: the learning stage is per- formed separately from the optimization task. First one trains a model predict the uncertain parameters (such as the electricity demand), then independently solve the corresponding optimiza- tion problem. Recent work in end-to-end learning has focused on how to train a model with a loss function that is meant to explicitly approximate the true decision cost prediction would produce. However these approaches only target minimizing the average cost, and do not, in general, take ro- bustness into account. In this work, propose different paradigm for combining the learning and optimization tasks. In particular our paper makes the following contributions.
1) Novel approach to contextual stochastic optimization problems that is robust and data driven: We propose a novel data-driven method to tackle contextual stochastic optimization problems. The proposed method is directly applicable to any class of optimization problems,

---

Published as a conference paper at ICLR 2024
including linear, nonlinear and discrete optimization problems. Furthermore, it gives rise lutions that are robust against uncertainty in the objective function using a single user-defined parameter to control the degree of robustness. In contrast to more traditional robust optimiza- tion methods, our proposed approach does not rely on constructing uncertainty sets. It is data driven and does not need to make any assumptions about the structure of the data itself and its distribution.
2) Analytical guarantees the regret and the stability of the proposed approach: We prove analytical guarantees on the regrer of the proposed method. For instance, we show that the difference between the in-sample cost and the out-of-sample cost decreases on the order of 1f ////n, for n datapoints. Furthermore, we prove the proposed method is stable against noise, showing that the decisions prescribed do not change significantly if the dataset is perturbed by noise.
3) Computational experiments on a variety of applications: We show with computational exper- iments that the proposed method is competitive in terms of the average error relative to existing approaches the literature. In addition to testing our approach for linear optimization appli- cations such portfolio optimization using historical stock data, we also consider nonlinear optimization problem applications such as inventory allocation and electricity generation using real-world data. Finally, through these xperiments, we show significant improvement in lerms of robusiness. We obtain as much as 20 times lowers cost in the worst case when compared to other end-to-end learning methods and 5 times lower than other robust approaches.
2 RELATED WORK
Due to space limitations will keep this section short.
End-to-End Learning:
Traditionally, the simplest way to learn the uncertain parameters is to do so independently of the op- timization problem by minimizing a loss function such as mean-squared error between predictions and observed realizations. However, it has been shown that solving the predictive and decision- making problems independently, can produce significantly suboptimal decisions Cameron et al. 2021I. As such, large stream of the literature includes end-to-end methods where the goal is to propose predictions whose corresponding optimal decisions minimize the downstream task loss (e.g.. the objective function). One of the earlier works related to end-to-end learning Kao et al. (2009) which trains a model to minimize task loss of an unconstrained quadratic optimization prob- lem. In general, the primary difficulty end-to-end learning approaches the differentiability of the constrained optimization task. Amos & Kolter (2017) extends the setting in Kao et al.) (2009) to constrained quadratic optimization, computing the gradient by differentiating through the KKT system of equations at the optimal solution. Unfortunately, for linear optimization, the problem becomes more complex since the gradient of the output of a linear problem with respect to its objec- tive coefficients is either zero everywhere taking a similar approach to Amos & Kolter (2017) for linear optimization problems but also adding quadratic regularization term to the objective function. Other approaches have focused other methods of altering the loss function or the objective function to compute more useful gradients end-to-end. For instance, for linear optimization problems, [Elmachtou & Grigas 2022) constructs a surrogate loss function that is a convex and differentiable approximation of the objective function. Elmachtoub et al. (2020) takes this approach and proposes a method to train decision trees with this
undefined. Wilder et al. (2019) addresses the issue by
surrogate loss. Mandi & Guns| (2020). Vlastelica et al. (2020). Berthet et al. (2020) take different approaches to address this issue. Kotary et al. (2021) and the references therein provide a general survey for end-to-end combinatorial learning problems.
The approach we propose is applicable directly to any class of optimization problems, while individ- ual end-to-end methods are usually restricted certain sub-classes of problems. Morcover, major difference in the approach proposed in this paper, that it is non -arammemiiticc and proposes decisions directly from data without requiring an intermediate forecast.
Prescriptive Analytics and Robust Optimization: To solve a stochastic optimization problem one apply well-known methods such as contextual Sample Average Approximation (SAA) (see for example, Kleywegt et al.] (2002)). The work of Bertsimas Kallus (2020) extends SAA to take advantage of the contextual nature of the problem by using covariates and weighing samples in
2

---

Published as a conference paper at ICLR 2024
non-uniform way (unlike SAA) using ML methods such as k-nearest neighbors or decision trees. For instance, for an out-of-sample set of features æ, use the k-nearest observations in the training data to make decision. Alternatively, [Bertsimas & Koduri (202I) generates weights using global methods, not only by using data around neighborhood of out-of-sample æ. |Bertsimas et al. (2019a) extends the general methodology by introducing optimal prescriptive tree framework to produce weights that are directly dependent on the optimization problem and minimize task loss, Furthermore, Kallus & MMo (2022) considers similar framework using random forest. Finally, Bertsimas & McCord (2019) applies these prescriptive ideas to the multi-period setting.
There has been significant work within the robust optimization literature over the years (see for example, the books by Ben- Tal et al. (2009), |Brtssimas & den Hertog (2021) as well as the survey paper by |Bertsimas et al. (2010) and the references within). In robust optimization, careful construc- tion of the underlying uncertainty sets is required to ensure the models are not overly conservative. Various formulations have been proposed, starting for example, with Soyster (1973). [Ben-Tal Ne- mirovski (2000), and Bertsimas & Sim (2004). Nevertheless, uncertainty sets can be learnt as gain information from data. Earlier papers uses estimates of the mean and standard deviation from the available data such as for example, |Bertsimas et al. (2013) who takes data-driven robust opti- mization view. Uncertainty sets could vary as a function of the features, as for example in [Bertsimas) & Van Parys 2002T) Kannan al. (2020) and Bertsimas et al. (0099)).
3 THE FRAMEWORK
In this section, we first formally describe the problem and the data-driven setting we study in this paper. Given a feasible region P and decision variables w E P. the goal is minimize an ob- jective function (ww) parameterized by uncertain parameters v. If we have exact knowledge of the realized uncertainty v values, the optimal decision could be determined through the following problem
w" (v) = arg min gu (w)). wEP
(I)
If the problem above does not a unique solution, we can instead assume that w ww(v) is an oracle pro- viding any optimal solution. For example, 9u (w) can correspond to linear optimization problem objective, (w) = n" "w or a quadratic optimization problem objective, gu(w) = q" w + w Qu, where (q. Q) corresponds to the linear and quadratic objective cocfficients respectively. In shortest path example, the uncertainty parameters v would correspond to the unknown travel times along each edge while the decision would be vector determining which path to take. Naturally set P constrains w to properly satisfy the path related constraints. Finally, we formally define the notion of regret of decision:
The regret Rp (w) of a decision w with respect to a parameterization v is given by the difference between its objective value and the optimal one correpsonding
Definition
(ww = (w gu(w" (n=ww(()) (p))
(2)
We make the following assumptions regarding the optimization problem:
Assumption 3.1 We assume that the maximum regret (x) = (w(w) (w (v)) is bounded and at most M1 > 0 for any v, w.
In the data-driven setting, we assume that the objective's uncertain parameters are distributed ac- cording to an unknown distribution Dr which depends on features æ. Given some vector of features x, we need to compute decision ((x). Only afterwards can we observe the realization of V/ Da and incur cost of gu- (w(x)). We take data driven approach and do not assume know the distribution Dr of the cost vector for any given feature vector æ. Rather we assume we are given N N) consisting of observed covariates x' and observed realizations v' ~ Dg. One objective is to minimize the expected regret of the decision:
data points (x x )....... (x
min Eu,- D= [Ru., (w)
(3)
WEP
while another would be provide solution that is more robust to uncertainty. One may wish to minimize the probability that the regret is above a certain threshold:
min P. PuanDe (Rig (w) 2 Φ).
(4)
WEP
3

---

Published as a conference paper at ICLR 2024
However, this formulation, even given perfect knowledge of the distribution of w= (v²)) is not tractable. For instance, for discrete Da, it may be solved only by a mixed integer optimization problem (see Appendix E We propose
approximation to this objective: minimize the pected regret that is larger than Φ, which we denote as the minimum violation solution. If the regret of is below for given Vas treat it as having regret. Otherwise,
assign it regret of Rv, (w) Ø, the amount by which its regret surpasses ø. This is the same as in formulation (4) except the cost of having regret greater than 6 is simply a constant of in Moreover, this is now a convex problem whenever (x)x) is convex.
Definition (minimum-vvoolation The minimum violation optimization problem is given by
min
BD [max{[Br (w) - Φ. 0,
WEP
To gain additional intuition into the choice of this formulation, we can also rewrite this objective as min PP Via (Ra (w) 2 Φ) EvarDD [Re (w) @ Rv_ (w) 2 Φ)
(6)
WEP
Notice that for = O, the above formulation reduces simply minimizing the expected regret. In addition, for ø large enough (so that regret is always bounded by Φ). the problem becomes fully robust and produces the same solution as 4 In between, this is combination of two objectives. The left term is the original one in 44) to minimize the probability that regret is larger than é. The second term is similar to conditional value at risk (CVaR) Rockafellar & Uryasev (2002). The CVaR objective minimizes Ex, [Rn (w)] (w) 2 qa (w) where qo (w)) is the a quantile of the regret distribution of taking decision w. To contrast this approach with ours, note that ga (w) change for each while the term remains constant throughout. We see in the computational experiments (section [.I and Figure 2 that the CVaR approach produces decisions that change discretely as the robustness parameter changes (the quantile being targeted), whereas the minimum- violation objective produces more continuously changing decisions.
Overview The key idea is to coarsen the problem and discretize the feasible region P into K subsets Hj...., H4 and determine the probabilities P(w" E H₂) that the optimal solution w" (vz) belongs to each H3, k 1..... .. K. We can use these discrete Hş as building blocks to approximate the expectations in (3) and (5). Intuitively,
would like construct Hş that, if w" (vz) ) belongs to Hy. then Rv, (w) can be well approximated by some deterministic function of w. Then, we minimize the expected regret based off of these individual approximations.
Discretization Consider constructing HE for each datapoint (w U*) corresponding to the set of points whose regret at most e:
H = {w E P 9o (w) - S (w S S (w EP : S {e}
(7)
Now remains to approximate the probability that w" (vx) belongs to each Hi- We approximate P(w* E KG} by leveraging the data we already have for training. For the training data, we compute point estimates of this probability since we have access to the realized cost parameters. That is, for every feature point x", we can determine whether the optimal decision w (v²) either belongs to set Hí or not. For each pair (x" (z") and Hi we generate the following labels:
[1. f
if un (x*) H
p - {0. otherwise
(8)
This creates multi-label data set (a", (PE))=,,....) We can then learn mapping (x(x)) which approximates ((w"(P)) E HG). We accomplish this using any classification method such as for example, logistic regression, decision trees, k-nearest neighbors, and neural networks among others. Figure proviides an illustration and the corresponding labels we create.
Algorithm
We summarize the algorithm as the following steps:
Define subsets Hi (w E P Ryd (w) S }) for each datapoint.
(ii) Construct labels P indicate whether w (U*) E H
4

---

Published as a conference paper at ICLR 2024
W (1b))
H5
W (v')
pf =
w (wx))
x
Figure I: w" (z") and wn (x²) belong Hi. but w* (x²) does not. Thus, points x! x² are labeled with 1, and 2 is labeled as 0.
(ii) Train ML model (xx) on multi-label dataset (a", (=E))==.....)))
(iv) For out-of-sample æ, take decision
N
we o (x) = arg min w EPP Σ (x) max Roy (w)) 0,03
(9)
This optimization problem in (9) combines the individual predictions of which sets Hí the solution should belong to. To gain some intuition this last step, consider the case that the sets H& form partition of the feasible region P. Note that we will relax this to the general case in Theorem 4.1 Then, conditioning the events w² (vx) H the minimum-violation problem in 5 can be rewritten as
D. [max{ Rv, (w) 0,0]] EP(w (vo) H |max Ru, (w) 0, | w=" (v&) Hgl
(10)
In Theorem 4.1 we will show that the term max (w) - o, 0} approximates the value of max Ri (w) o, 0}. whenever w" (vx) E Hi. Moreover, these terms are weighted by Pf (æ),
the approximations P("" (Vz) E H3).
Alternative interpretation for e === We would also like to present an alternative viewpoint of our proposed method which connects the choice of objective [[[ma (R, Φb 0}] to the rest of the method and how the weights (x) are generated. This interpretation is unique to proposed method, and differs from that of Bertsimas Kallus (2020) and related literature. We alternatively view the problem follows. For out-of-sample features æ, the goal is find feasible solution w that best matches the predictions P (z) in terms of which sets HE the optimal solution w' w"(va, (va) should belong to. For example, if we predict that w" (u²) belongs Hi and H, with high probability (meaning weights pi (x), 15 are high), then the solution we propose should belong the intersection of sets Hi and H5. The formulation 9 performs this by implicitly scoring each feasible solution: if feasible solution w does not belong to Нÿ we penalize it by our approximation pf (z) that should have belonged to it multiplied by the distance from Hí. However, if w does belong to Hí. then there is no penalty. This score exactly corresponds to each term PL. (x) max Ry* (w) - c, O). We choose the feasible solution that minimizes overall penalty.
THEORETICAL REGRET BOUND AND PRACTICAL APPLICATION
Theorem 4.1 Under Assumption 3.1
the expected regret decision w E P can be bounded (9) with probability 1 1 - as follows:
above by the approximate problem in
log 1/8
E [max [max(Rus (w) 0,03] < c. a (BB(ww)+MM) MIE+
(11)
2N
for = a(B. + Φ) and where OBJ(w)= = I EN Px( max max(Ryr (w) - -. 0} is the approxima-
tion optimize over in 99 E is the mean prediction error
N/ EN (x) Plww" (vx)
5

---

Published as a conference paper at ICLR 2024
HG) and constants a, 3g depending the optimization problem. In particular, for the following classes of objectives we have
bi-lipschitz objectives: for any bi-lipschitz objective, with constants L, ps such that 1 || w0 w I (gw(ww)) gu(w²)) I T. / As an example, this holds for any quadratic optimization problem with bounded feasible region having positive definite quadratic term.
T.|l=* - w²)] [[ we have a = L/ and Be = c.
2. quantile loss function: given a prediction un and outcome Vn. the regression loss for quan- tile is given by Sva (w) = max (q(v= w), (1 q)(w - Un}}- Then a = and max/g/(1 q). q)/q}E. For example, this is also applicable to the inventory
stock problem in section 5.1
Furthermore, C. is constant factor describing for any x. how often w" (V=) will have regret at most with respect to a random other cost vector. In particular, ce 1/ ming a MiiiaPPRRRar (Rey (w" (v=)) S c).
The full proof can be found in Appendix A Moreover, we prove stability of the output of our proposed model under perturbations in the data. This can be found in the appendix (see Appendix B). In short, the stability result describes the change in the decision (0,)(²)) when the dataset is perturbed by noise. If each of the learning algorithms used to train (x have hypothesis stability (defined in the appendix, see definition B). then the output ( also changes by small amount when the dataset is perturbed. Before the computational section, we discuss some of the main practical issues and take-aways from Theorem 4.1. In particular, we discuss how to practically choose and how this affects each term in the bound in theorem 4.1
Discussion on choosing e. By definition, determines the size of sets H This in turn affects the resulting multi-labelling pp 1,..., N. If for example, the sets Hi do not intersect, then each vector p* (Pā)==1,.... has single non-zero entry. This would make pa (x) impossible to learn.
As such, we propose the following method of choosing e: choose e large enough so that for each vector p", "r at least some fraction, which we denote by To of ils entries are non-zero. Then, from Theorem 4.1 we argue that given N datapoints, one should choose e large enough so that Ye Z 1/vN. We can see this as follows by viewing the impact of on each term of the bound:
Effect c.. Recall that if pp this is equivalent to Ry (w" (v")) S Therefore, % chosen in this way implies that
(R (w" (v²)) S <6)= 7e-
(12)
Moreover, this results in G. 1/7c-
Effect on &. % also affects the error of the ML. models, namely E. For instance, labelling everything with a zero will have an error of E Ye. In general, any ML model that improves beyond this baseline will have & < Te-
Effect on (w). We can bound (B) by
N Σ
OBJ(w) =
p (x)
max Rot (w) -,,0
(13)
N
k=1
1 N
< M
(m(x)) < Mi E+
Σ
(ww E Hz)
(14)
kk=l (((((()) E Hi) concentrates around its expectation which is % R Py (R,,,, (w))) I <). It follows that (BJ(w) & 2M given that E S %e as argued previously.
Finally, the term &V EN
Overall, this implies that the right hand side of the bound theorem 4.1 has c, on the order of 1/ while OBJ and are both on the order of Ye. Putting these together, we see that these cancel out to be overall on the order of ((M1). The only remaining term is /log(1/6)/2N Hence, we need enough data so that this term also becomes on the order (1). Therefore, we need on the order 1/>2 datapoints or that y 2 L/VN. We present results in the computational experiments section about the effect of the quality of decisions produced.

---

Published as a conference paper at ICLR 2024
The remaining question is now, how small can be that Y 2 1/VN? In practice, this can be determined on case-by-case basis for each dataset, for instance by using binary search. Of course, "e 2 1/V/N is only a rough guide to understand the magnitude needed. A process like cross- validation can ultimately be used to choose c. Theoretically, in the worst case either (1) such needs to be a constant fraction of the diameter of the feasible region or (2) c is kept small but we need an amount of data that is exponential in the dimension of the decisions. However, this is often not the case in practice when presented with real-world data. Ultimately this largely depends on the distribution of the decisions w' (v) and P itself. In real-world data, the distribution of w" (v) would not pathologically uniformly cover the feasible region. but rather be more clustered around smaller regions. Moreover, the feasible region itself plays crucial role. Consider the case that decisions u E Rd are constrained to feasible region P that is an s-dimensional subspace of the ambient space Rdd For instance, P = (w Aw b, w 2 0} where the null space of Á has dimension 8.
COMPUTATIONAL RESULTS
We consider four applications of the proposed approach. Two applications come from Donti et al. 2017): synthetic inventory stock problem and a real-world energy scheduling task. We show that this discretization approach is competitive with other methods in terms of expected cost, and has significant improvement in terms of robustness with up to 20 times lower cost in worst-case scenarios. Moreover, we also compare against other non-contextual robust optimization methods. Due to space limitations, we present this last experiment in appendix C.I We also put into practice the earlier discussion regarding the choice of and how its value affects the quality of the decisions ranging from performing better at minimizing the expected cost or being robust.
5.1 INVENTORY STOCK PROBLEM
Consider the classical newsvendor problem in which a given product has uncertain demand d as well as observed covariates æ. Each day we observe the new features æ and must make a decision w for the amount of product to supply. Afterwards. the true demand is realized. For each unit of supply above the demand, there is a unit cost of ch (for holding an item overnight in the store) and for each unit of supply below the demand, we incur backorder or lost sales unit cost es (for example, cost of expedited shipping to ensure the product arrives the next day). has been shown that the optimal order quantity is the cb/(cs + ca) quantile of the demand distribution (see Arrow et al. (1951) )) In principle, one could apply the quantile loss function to predict this quantity and solve the problem in two-stage manner. However, to consider the identical problem also presented in DDnti et al. (2017), we consider a version with additional quadratic costs to over or under-stocking as well as an ordering cost. The objective is given
1
ga(w)= = Cow + Cg w2+ + c max w. 0} + 2 2% max w. 0
(15)
ch max(w 0,03 + 99h max w d, 0)2
(16)
Experimental setup: We use the same unit cost parameters as well as data, and compare against the same models as in Donti al. (2017). However, we present not only the average cost incurred on the testing data but also on various quantiles of the cost distribution. We plot on the x-axis the mean cost incurred by each method, and on the y-axis the cost at the gt quantile.
The problem of mingee E (max(Rp (w) Φ 0}} can also be solved by existing methods such as Bertsiimas & Kallus (2020) by thinking of the objective function not as (x) but rather as max Ry. (w) - Φ. Of directly. In this approach, weights are generated by K-nearest neighbors (or other ML models like linear or tree models). However, these methods do not generate these weights based on the optimization problem itself. In contrast our proposed method generates weights explic- itly depending on the optimization task. We denote this approach as KNN + minimum-violation in the experiments. We also compare against the method Bertsimas & Kallus (2020) where we use CVaR as the objective, namely E E[R2, (w) [Rys (w) 2 (Rp, (w)),, where qa. (Z) is the a-quantile of random variable Z. We consider range of values for the quantile in the experiments. In ad- dition, we also compare against another data-driven contextual robust optimization methods where one solves the following problem. For an out-of-sample æ., find the K nearest neighbors in the data,
7

---

Published as a conference paper at ICLR 2024
85th quantle
50th quantle
95th quantle
380
400
400
350
225
730
7.00
232
263
700
7.0
Coo
Nount
Moan Cost
99th
100th quantii
400
450
1384 eierarsaaie Otorgetcc
300
Riky
220
2.3
272
123
272
Mean
Comparison of average cost of each method vs. 85th 90th 95th 99th and 100th quantile cost. We vary the degree of robustness for each method. As this robustness parameter increases, the mean cost increases, but the quantile cost (generally) decreases for all methods.
Figure 2:
namely, (xx K). Unlike Bertsimas & Kallus (2020) which minimizes the average cost, we weight the remaining K datapoints adversarially according to distribution π that is, within a Kullback- Leibler divergence distance of at most from a uniform distribution, assigning weights 1/K each datapoint (so that ( (m|| <. r). Due to space limitations, details and formulations for each of these approaches can be found in appendix C.I Morcover, we compare against the method in Donti et al. (2017). This is end-to-end method which trains neural network predict discrete probability distribution for the possible values of demand. We refer to this as the kask-based method in Figure 2 This work makes use of the OptNet framework in Amos & Kolter (2017) to compute gradients of the loss function with respect to the predicted demand d. Furthermore, we also compare against a policy optimizer approach. Here, one does not make a forecast for demand, but rather the neural network model directly outputs the policy/decision to take.
Each of these methods use a linear model make predictions (or decisions, as in the case of the policy optimizer). For the other weight-based methods (KNN + KL divergence and those based on Bertsimas Kallus (2200) we use KNN method to generate weights (with K 10). For con- sistency, our approach also uses KNN model to predict the Pı also using K 10 neighbors. Each pa (ar) predicts a value between 0 and based on the average label assigned to the K-nearest neighbors of æ in the training data. This is done independently for each k. In contrast, for the fol- lowing experiment in section 5.2 the models (x(-) are trained simultancously by a neural network.
Results: In Figure we report the mean and the 85th 90th 95th 99 and 1h0th quantile (out- vary the level of robustness for each approach (6 for the iunimum-violation objective and a in for CVaR). The KNN + minimum- violation method and our proposed method have the same objective, but different methods of solving it. We see that both approaches produce similarly shaped mean vs. quantile cost curves but the discretization method consistently has lower 9th quantile cost for the same average cost for all 85 to 100. As this quantile approaches 100, the gap between the two decreases but of note, at q = 100, all approaches, other than the discretization method performs poorly, worse than even the policy method in terms of robustness. The CVaR and traditional robust methods also deteriorate in performance as the quantile increases.
of-sample) cost of each decision made by the approaches
5.2 LOAD FORECASTING AND GENERATOR SCHEDULING
Next, we consider a real-world problem for generator scheduling using years of real electrical grid data from PJM, electricity routing company coordinating the movement of electricity throughout
8

---

Published as a conference paper at ICLR 2024
average cost
Hourly 98th quanble cost
Houry cost
Hourly 100th quantile
0.0
4-
010
dlscredtatinn 215
Decrdtiancnn apard.025
Dacretion assodas
Dacrebaacen a.a-d.00
Hour 35
Hour
Hour of
day
Figure 3: Reporting for each hour of the day the mean, 99th quantile, and maximum cost of each method. A fixed ø = 0.5 value for the discretization method was used for all results.
13 states. We use the same range of data as also used in Donti al. (2017). Here, we must make decisions w E I² for the amount of electricity generation for each hour of the following day. Similar to the inventory problem, the operator incurs a cost Ye for excess generation and cost % for a shortage in generation. In addition, power plants have physical limitations prohibiting large changes in generation from one hour to the next. The objective and constraints are given as:
ga(w) Σ 7o max ww; 0} +7e max d:, 0},
|w:41 - wi| S 1, 23 (17)
Experimental setup: We use the same setup used in Donti et al. 2017). using the same param- eters for the problem as well data. We make use of the same data preprocessing and feature engineering. They use a two-layer (each layer of width 200) network with an additional residual connection from the inputs to the outputs. We use the same architecture learn the labeling Pî (a:). In addition, we compare against a cost wost-weighted model minimizing weean-suaared error which peri- odically reweights training samples based on their fask-based cost. Finally, we also compare against the method described in the previous section with objective to minimize CVaR.
We compare the average cost as well as the 98 100 quantiles of the cost distribution for each method. In particular, we also present results for different choices of c. Following the discussion of theorem 4.1 a starting point would be to choose so that the average number of posi- tive labels. %e. is around 1/VN. We choose different epsilon so that % = 0.015, 0.025, 0.04, 0.05 where 1/vN x 0.02 (here we have N = 2, 553 training points). As and %. decrease, we find that the solutions better target minimizing the expected cost, while increasing e will improve per- formance on higher quantiles of the cost distribution. In particular, when % 0.025, the method outperforms even the
Results:
method on average cost at peak demand hours of the day (hours 0.05, we find that the worst case cost across the entire day is
15-22). At the other extreme nearly constant and up to more than 20 times lower than the CVaR and other methods. However, setting = 0.01 to be too small does not introduce enough robustness. While it performs best in terms of average cost, its worst-case cost spikes suddenly.
CONCLUSIONS
We proposed novel method for contextual stochastic optimization based off of discretizing the feasible region into subsets and learning how the optimal solution maps to each subset. We proved analytical guarantees on the bound between the expected out-of-sample cost compared to the ap- proximate objective proposed in Finally, we present computational experiments on three datasets, including a real-world electricity generation problem, and show our proposed method competitive against other end-to-end approaches and provides significantly more robust solutions, even when compared to other robust optimization methods. Future directions of research may include devising different constructions of the subsets HE and consider uncertainty in constraints well.

---

Published as a conference paper at ICLR 2024
REFERENCES
Brandon Amos and Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks. In International Conference on Machine Learning, pp. 136-145. PMLR, 2017.
Kenneth Arrow, Theodore Harris, and Jacob Marschak. Optimal inventory policy, Econometrica: Journal of the Econometric Society, pp. 250-272, 1951.
A. Ben-Tai Tal, L.E. Ghaoui, and A. Nemirovski. Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, 2009, ISBN 9781400831050
Aharon Ben-Tal and Arkadi Neminovski. Robust solutions of linear programming problems taminated with uncertain data. Mathematical Programming, 88(3):411 1514)24114224, 2000.
Aharon Ben-Tal Dick den Hertog, Anja De Waegenaere, Bertrand Melenberg, and Gijs Rennen, Ro- bust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2)3341-35, 2013. ISSN 00251909, 15265501.
Quentin Berthet, Mathieu Blondel, Olivier Teboul, Marco Cuturi, Jean-Philippe Vert, and Francis Bach. Learning with differentiable perturbed optimizers. ArXiv, abs/2002.08676, 2020.
Dimitris Bertsimas and Dick den Hertog. Robust and Adaptive Optimization. Dynamic Ideas LLC, 2021.
Dimitris Bertsimas and Nathan Kallus. From predictive to prescriptive analytics. Management Science, (6(3):1025-1044 2020.
Dimitris Bertsimas and Nihal Koduri. Data-driven optimization: A reproducing kernel hilbert space approach. Oper. Res., 70:4544471, 2021.
Dimitris Bertsimas and Christopher McCord. From predictions to prescriptions in multistage opti- mization problems, ArXiv, abs/1904.11637, 2019.
Dimitris Bertsimas and Melvyn Sim. The price of robustness. Operations Research, 52:35-53, 02 2004. doi: 10. 10. 1030.0065.
Dimitris Bertsimas and Bart Van Parys. Bootstrap robust prescriptive analytics. Mathematical Programming, pp. 1-40, 2021.
Dimitris Bertsimas, David Brown, and Constantine Caramanis. Theory and applications of robust optimization. SIAM Review, 53, 10 2010. doi: 10.1137/080334500
Dimitris Bertsimas, Vishal Gupta, and Nathan Kallus. Data-driven robust optimization. Mathemat- ical Programming, 167, 12 2013. doi: 10.10077/10107--17-113
Dimitris Bertsimas, Jack Dunn, and Nishanth Mundru. Optimal prescriptive trees. INFORMS Jour- nal on Optimization, 1(2)164--188 2019a.
Dimitris Bertsimas, Christopher McCord, and Bradley Sturt. Dynamic optimization with side infor- 2019b.
mation. arXiv preprint
Olivier Bousquet and André Elisseeff. Algorithmic stability and generalization performance. In Advances in Neural Information Processing Systems, volume 13. MIT Press, 2000.
Chris Cameron, Jason Hartford, Taylor Lundy, and Kevin Leyton- Brown. The perils of learning before optimizing. arXiv preprini arXiv:2106. 10.339906./034, 2021.
Lucian Coroianu. Best lipschitz constants of solutions of quadratic programs. Journal of Opti- mization Theory and Applications, 170(3):853 875, sep 2016. ISSN 0022-3239. doi: 10.1007/ 210957-016-0966-.
Lue Devroye and Terry Wagner. Distribution-free performance bounds for potential function rules. IEEE Transactions on Information Theory, 25(5):601-604, 1979.
Priya Donti, Zico Kolter, and Brandon Amos. Task-based end-to-end model learning in stochastic optimization. In NIPS, 2017.
10

---

Published as a conference paper at ICLR 2024
Adam Elmachtoub, Jason Cheuk Nam Liang, and Ryan McNellis. Decision trees for decision- making under the predict-then-optmizz framework. In International Conference on Machine Learning. pp. 2858 2867. PMLR, 2020.
Adam N Elmachtoub and Paul Grigas. Smart predict, then optimize'. Management Science, 68(1): 9-26, 2022.
Nathan Kallus and Xiaojie Mao. Stochastic optimization forests. Management Science, 2022.
Rohit Kamnan, Güizin Bayraksan, and James R Lucdtke. Residuals-based distributionally robust optimization with covariate information. arXiv preprint arXiv:2012.01088, 2020.
Yi-Hao Kao, Benjamin Roy, and Xiang Yan. Directed regression. In Y. Bengio, D. Schuurmans, Lafferty, C. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Sys- tems, volume 22. Curran Associates, Inc., 2009.
Anton J. Kleywegt, Alexander Shapiro, and Tito Homem-de Mello. The sample average approxima- tion method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2):49-502, 2002.
James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-end con- strained optimization learning: A survey. CoRR, abs/2103.16378, 2021.
Jayanta Mandi and Tias Guns. Interior point solving for Ip-based prediction-oppimisation. ArXiv, abs/2010. 13943, 2020.
Tyrrell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distributions. Journal of banking & finance, 26(7):1443-144 2002.
Lorenzo Roscasco and Tomasso Poggio. Stability of tikhonov regularization, 2009.
https://
Allen L. Soyster. Technical note-convex programming with set-inclusive constraints constrrnnn and applica-
tions to inexact linear programming. Operations Research, 2145):114-11157, 1973.
Marin Vlastelica, Anselm Paulus, Vít Musil, G. Martius, and Michal Rolinek. Differentiation of blackbox combinatorial solvers. ArXiv, abs/ abs/1912.00215, 2020.
Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: Decision- focused learning for combinatorial optimization. The Thirty-Third AAAI Conference on Artifi- cial Intelligence, AAAI, pp. 1658 1668..66..0 AAAI Press, 2019.

---

and Published as a conference paper at ICLR 2024
A
PROOF OF THEOREM
Theorem 1:
Under basic boundedness assumptions on the optimization problem (see Assump- tion B.1), the expected regret of decision P can be bounded above by the approximate problem
in 9 with probability "y as follows:
E [ (w) - 8) 1 (Rpp (w) 2 cc . (OBJ(w) + M18+
log 1/7 2N
(18)
for 0 = aBe + ar and where OBJ(ww)= = Em (x) max Ryt Φ 0) is the approxima-
tion we optimize over in the mean prediction error & N Σx= i (a:) PPw" (vn) E H&)l
and constants a, 3gg depending on the optimization problem. In particular, for the following classes of objectives we have
1. bi-lipschitz objectives: for any bi-lipschitz objective, with constants I, such that 1 I|'' wi|l S (9w" gr (w"2 S L w will, we have a = L/p and Be = As an example, this holds for any quadratic optimization problem with bounded feasible region having positive definite quadratic term.
|||
2. quantile loss function: given a prediction w and outcome Va, the regression loss for quan- tile q is given by 9vs (w) max w), (1 q)(w v=)). Then
3. max (1/(1 (1 - 4), - (1-4)//e
Furthermore, c₂ constant factor describing for any æ, how often w² (Vz) will have regret at most with respect to a random other cost vector. In particular, = 1/ min P (Rzy (w=(zx)) (vz)) S c).
Proof: We prove this statement for broader class of objectives, In particular, for functions having the following condition: whenever Rw, (w* (v=)) (where is feature vector like æ), then we must have that Ryg (w) I a.R,, (w) Be. We will then show this holds for instance for bi-lipschitz and quantile loss functions. We proceed prove this follows. We first consider our formulation in 9 when the approximations (x( are exact. Let
N
OBJ((w)
P(w E Hf) max - 6,03
(19)
N
k=
We will show that
c-a (OBS(W)) +
log 1/8
2 Ee [max Rug (w) al)
(20)
2N
Then, we prove the general statement for OBJ(w) by showing that (OBJ(w) OBJ((w) s Mi/N (x) PPw" Hx)].
First, we show 20 We have
N
1
OBJ((w)=
=
Σ (Mw E HB) max(gx 6.0)
(21)
N
Ex
I(By (w*) S E)) maxigu (w) 0,
(22)
Next, we can treat the k as realizations of random variable as well. The inner term in the expec- tation, Ex EN 1 (R,, (w" (v,) I <)) max(gu> (w) o, 0}}. concentrated around its mean, μ. The = are identically distributed and independent. Therefore, so a function of these random variables. Let y be random variable from the same distribution all the wt Then, by Hoeffding's inequality,
N Σ P(w" (Va) E HG) max you (w) 0,0) - # 22)) S eexp (-2Nt²)
Py N
(23)
k=1
12

---

Published as a conference paper at ICLR 2024
Therefore, with probability 1 - 5,
OBJ Er EB [IP(Rr, (v=(vo)) S E) max (w) o, 0}]] log 1/ō 2N
(24)
with y a random variable identically distributed like the v². Rewriting the expectation over y by conditioning over the event Re, (vx) S f), we have
log 1/8
OBJ*(w) 2 Ex [P (w (vx) & E)IEy [max( Lnn, (w) - 0, Ry, (w (uz) S -
2.V
(25)
By assumption, we simply bound the term Fy (Re, (w, (Ux) S c) 2 1/c. And again by assumption on the structure of the objective function, we can bound
-
By max (9,, Φ,
0} Ru, (w" (vx) S c max
Rp (w) - 2.0}
(26)
a
Combining this with 25 and rearranging, shows that with probability 1 --6 8,
a (BB((w) +V
log 1/6
Ex [max Ruv (w) aB.. - -a0, 0H1
(27)
2NN
Next, we show that (OBJ(w) - -OBJ(ww) (w)) S & = M1 IN (1)(()) - IP(w" (uz) E Hs)). We have
1
[OBJ(w) OBJ S
N Σ (x) P(w" (V))(va) E Hae)
(28)
By assumption 3.1 Ry((w)) < M1 and hence the claim follows. Finally, it remains to show the initial conditions hold.
1. bi bi-lipschitz objectives: For any æ, y. we have
gus (w)(w) - 9un (w (vz)) s L w w (v=)
(29)
19,, (w) gu, gv,( (v=)))
(30)
a
L
19r, (w) Iu, (w" (vy)) + gv, (w" (vy) Iu, (w (vx)) ))
(31)
19v, (w) guy (w" (My))) +
(32)
The last inequality follows by noting that by definition guy (w) Ry (w" (vx)) I So indeed,
(2) - Jr (w (My))
=
L Re, (w) S Rw, (w) +
(33)
2. quantile loss function: First, note that Rv, (w) = (w) and w= wv())) U for any x. w.
Further, note that the condition Re, (w" (V=)) S c then implies that
max(glvy va), (1 (V= vy)} Se
(34)
1 1
1/2 Uyl S min
q 1-qJe
(35)
Moreover, Reg (w) = (v- = Ir- -ve-ryte, (w)) So.
Rvs (w) maxig(u, Vy + Uy w) (1 q)(w w (V Uy vy))
(36)
I gey (w) + max q, - q/10 U2 - nyy
(37)
S Juy (w) + max q - / min
(38)
9 1
S (w) + max
1 -
g
6
(39)
q
13

---

Published as a conference paper at ICLR 2024
B STABILITY OF DECISIONS UNDER DATA UNCERTAINTY
In this section we consider the change in output (,))(())) when the training dataset changes under noise. In particular, we define stability as follows. Let = (v" [D"]N N.N and let 2 {v" + 8") ) be a perturbation of the dataset Z by noise 8 with bounded norm | Il2 I a. We wish to bound the difference in decisions when training under Z and any noisy perturbation 2. We first make the following assumption regarding the algorithm used learn the labelling p:
Definition (Hypothesis Stability) Let p2 (a) E [0,1] be the prediction output of a learning algo- rithm trained dataset Z size stability By if
size N for a binary classification problem. We say p² has hypothesis
Vi vi= N, Ex (x" 3N.
-p
(40)
where 7 is the same data set as Z, but with the ith point removed. If 8N decreases at a rate of O(1NN) with data size N, the algorithm is called stable.
Note that this is a significantly different notion of stability - it only accounts for the addition of single new datapoint, whereas in our setting every datapoint is perturbed by noise. Moreover, many learning algorithms have this stability property. For example, support vector machines and regularized least squares (Bousquet& & Elisseeff (2000)), K-NN classifiers with a {0, 13 loss function (Devroye& & Wagner (1979)), and all learning algorithms (such as neural networks) with Tikhonov regularization (Roscasco Poggio (2009)).
Assumption B.1 The learning algorithu to train and generate each predictor px(+) has hypothesis stability with rate fN. Ol1/N) where N is the size of the dataset.
We also make the following assumptions about the optimization problem itself:
Assumption B.2 The function gu is linear with respect the uncertain parameters v, although it may be nonlinear with respect to Moreover, (uw) is L -Lpishiit with respect to wo for any v. So, for wi, W2:
Ig gr (w2)) S L1 |101 w2ll
(41)
and w² (v) Lppliihehi with respect to v. That is, for vz u
||w"((")) w² (v²) S L2 v² u²
(42)
For example, any convex unconstrained minimization problem with Lipschitz objective function. Additionally, quadratic optimization problems with any linear constraints also satisfy these assump- tions (see for instance Coroianu 2016)).
Theorem B.1
Let á² (x)(x) be the decision w. (2) as defined in (9) when given training a dataset
Z. Under the stability Assumption B.l and Assumption B.2 for dataset Z = (() )) and perturbed dataset Ž = {(x', nd + 8"IN I==1 with any, including potentially adversary, noise || <
a,
Ex ( u6 (1>)
cua(()
(43)
for some constant Co Additionally, M(a) is an increasing function of the noise level a and X(0) = defined explicitly by
X(a) max P. (w"(vz) E HetaL Hg-o)).
(44)
k
Moreover, this change is concentrated around its mean:
Pe (1))2(x)) - w² xx) - E 1 (x:) "² (x))
-2t
eexp
(45)
(N)
14

---

Published as a conference paper at ICLR 2024
(v)
w (V+
La
La
Figure 4: Any point w"(v) (v) belonging to the cap of size e La or outside of the cap of size + Lo will never change its label after noise is added. In the figure, this is any point outside of the strip defined by the dotted lines. Otherwise, points within the strip may change their label.
Proof:
First, we show that the labelling P& as defined in does not change for constant fraction
of the data even under noisy perturbations. In particular, note that for any such that w ("(") e
Hr -b-L-a we also have w" (w" + 8") E Hig. Indeed, if 9ex (w (w"(w" (n") gut (w* (w²)) S E La,
then by the Lipschitz property B.2 we have Iu (uww"("" + 8n)) Ius (w"
Therefore,
labeling of w" (v) and w" (w" + a) would both be equal to for any noise [8|]" I a. Similarly, if w" (D²)
Hi and the labels would both be 0. On the other hand, if w" (D") E H H Hf-Lo then it possible for the label to change. See Figure However, this can only be true for at most a constant fraction of the data, independent of the size of the data. Let this fraction be X(a). That is,
HE+aL then also w"(v" (v" + 8")
X(a) max IP (w) HetLa (15
(46)
Clearly, this is an increasing function with X(0) -
Notice that the learners P& (x: are trained only on these labels. Let p (a: be the model learned when training with data from Z and similarly let p (x) be the model when trained on labels resulting from Z. Note that from the argument above, the number of labels that are different in each case is bounded in expectation by A(a). Now, we bound [0((x) (x) - w² (x) By definition and linearity from Assumption B.2
N max Ry (w), 0}
(.)((x) arg min
Σ (x)
(47)
WEP
i=1
N
arg min
Pe (w)
(48)
WEP
N
1=1
arg min wEP
-+ EV, Prteoue (w)
(49)
w²
(50)
15

---

Published as a conference paper at ICLR 2024
Then,
w¹ (N 2s [ -w w¹ (
(x) - v0 (x) -x)
N E pe (()))))
(51)
N 11 (1
(x:))
s12 1
Σ 1x) - fz(())
|01
N
(52)
Now, noting that | < by assumption,
2 (x) ع (z)
1 L2 N
Σ Elp (x) xx))
(53)
Given that A(a) N labels change in expectation, using lemma A.I gives that (ar) p? (x)) & N follows that
B (x) w² (xx)
< 2L N
Σ (a)N -0
(54)
Moreover, the final tail bound follows directly from Hoeffding's inequality.
Lemma B.1 Given that labels change in the training data, the difference in prediction for any fixed j is bounded as E 1e -x(()) S 2jBN & for stable algorithm used to learn each Pz.
Z be a sequence of datasets where Z1 Z and Z' = Z and where there is exactly one label changed from dataset Z to Zi+1, Then applying the lemma for the case j = 1 to each pair of consecutive datasets Z', 2 will prove the result.
We now prove Lemma B.1 by induction. Let 71 ZI. ......,Z?
We now prove the result for j = 1. Here we have exactly one label that is changed from Z to Z. Let be the index of the datapoint which has its label changed. Consider an intermediate dataset 2 which equal to Z but which has datapoint 8 removed. Note that 2 is also equal to 2 but with datapoint removed as well. We now apply the definition of hypothesis stability to find that
Exp pk
(z)
2 (z)) s Ex pt (xx pk (xx)
+ EE
p (x)
p (x)
(55)
I BNN + BNN 2,3N
(56)
which proves the claim for 1 and hence the lemma.
C FORMULATIONS AND EXPERIMENTS
C.I INVENTORY STOCK PROBLEM
Recall the objective is given as
1
ga(w) cote oww c max(d- w. +
2 Tb max w. 2
(57)
Ch max - d, 0} +
2 9h maxfw d, 0)2
(58)
where d is the uncertain demand and w is the allocation decision for product. We provide some details on the approaches we compare against:
Minimum-violation objective with Bertsimas & Kallus (020). Here aim to solve the prob-
lem of min E. [max Rv, (w) o. 0}] by the method of Bertsimas & Kallus (2020) by thinking of the objective function not as gu (x) but rather as max Ru, (w) Φ, 0J directly. The formulation is given as
N
min WEP
x (x) max Ry, (w) - 6.0}
(59)
16

---

Published as a conference paper at ICLR 2024
where the (x) weights are generated by K-nearest neighbors (or other ML models like linear or tree models as described Bertsimas & Kallus (2020)). However, these methods not generate this weighting based on the optimization problem itself. In contrast proposed methods generates weights explicitly depending on the optimization task.
CVaR objective. We also compare against the CVaR objective, which is very similar to ours. Specifically, the objective is given E[ (w) RR, (w) 2 (a(Rr, (w) where (a(2) is the quantile of a random variable According to Rockatellar & Uryasev (2002) the problem can be reformulated to have objective
+ max RR, max (w) - 8,0}
(60)
where 3 is newly introduced auxiliary variable. Using the method of Bertsimas & Kallus 2020 we solve the following formulation:
1 3 max (Rx -,,0)
min WEP,
Σ
('))
(61)
where again (x) are determined by the 10 nearest training neighbors of the out-of-sample point
Traditional robust optimization. We also compare against a more traditional robust optimiza- tion approach. Specifically, for out-of-sample æ, find the K nearest neighbors the data, namely (x, K). Unlike [Bertsimas & Kallus (2020) which simply minimizes the average cost, we weight the remaining K datapoints adversarially according to a distribution æ that within a Kullback- Leibler divergence distance of at most from uniform distribution assigning weights 1/K to each datapoint (so (TI(T]/)/K) S r). The formulation is
arg min WEP T.DKL(GIL//KS (eN(o,
max
E
a ('))
(62)
This Kullback-Leibbe uncertainty set was introduced Ben-Tal et al. (2013) in the feature-less setting. We use the methods in this paper to solve the proposed method in (62).
C.2 LOAD FORECASTING
ga(w) = Ts max wi, 0} + Ta max(w:: di, 03 + (w: d.)²
(63)
with additional ramping constraints w,+1 wi < r, limiting the change in electricity generation from one hour to the next, The optimization problem, given a forecast of v is given by
w" w"(d)=
arg min subject to
Ei= i' max w. 0} %a max d; + {w, d,)2 W wal Sr, == L..... 23
(64)
We can rewrite the terms max (d; w; 0}. max (w. d; 0} by variables h; and b, with constraints h; 2 d; w;, h, 2 0 and similar for b. Since the objective is to minimize the overall cost, the variable h, will take the minimum possible value while satisfying the constraints. So, it would equal The problem can be reformulated as
the maximum of 0 and d,
w" (d) = arg min subject to
E Yoh + beb, ; + (w, d
W w. Σ r, i=
23
h; 2 d, wi:
i = 1,...,24 24
(65)
b, w, d,
1,... 24
w, h, b > 0
17

---

Published as a conference paper at ICLR 2024
The method of Donti al. (2017) views the problem stochastic optimization problem where they predict a distribution for the demand and solves the corresponding stochastic problem:
min subject to
Ei= Ed (dlp) 1% max wi, 0} + Y max w. d;,0} 0} + (w,; d;)²1
w; 2 0
wi ST, i 1,...,,2 23
(66) where p(d(z) is the prediction made (end-to-end) of the demand distribution. The paper predicts the mean and variance the distribution, then assume follows the corresponding gaussian distri- bution. They solve the stochastic problem by sequential quadratic programming (SQP) iteratively approximate the problem. This is computationally much more expensive to do than the simple de- terministic quadratic problem one must solve using the discretization method proposed.
C.3 PORTFOLIO OPTIMIZATION
We are given d investment options whose random returns are denoted by ri, 1,... d. Let D be the joint distribution of the r;. As data, we use historical stock prices companies starting from January 2021, until August 2023. Denote by r()).... ......,())) r(") the returns observed on the train data ........"
We wish to make decisions for the fraction of portfolio to invest in option i. In this robust setting, we wish to make a decision that maximizes the probability that the return is above threshold In particular, take decision given by
max; subject
ProD xx22t) Σ -== 11=1 =1
677
24 120 0
which we solve approximately by minimizing the expected violation across the data:
minz.j
ビ==10 9j 9j 2 (rl))T==
subject
(68)
Σ 82 =1
0,920
Budget Uncertainty: We additionally compare against existing robust optimization approaches. constructs an budget uncertainty set. They solve the problem
max, minrew subject to
Σ
== (14 +
orrr)a;
2 =1
Σ
(69)
24 2020
where the uncertainty set is given by
4 = (r: ||1|bo 2 1, ST}
(70)
and I is the co-called budget of uncertainty which needs to be tuned.
Data driven, KL-divergence and variation distance: Furthermore, we also compare against data-driven method, in Here, one treats the dataset uncertainty set all probability distributions (on the same support) that has KL-divergence at most some e. In particular, let म, 1/n, Vj 1,...,,' n be the uniform empirical distribution for the datapoints. Then, define 4k as the set of all probability whose KL-divergence is at most from f:
empirical distribution and construct an
{
O,
- Σ
My LoggTT,)) $c $c}
(71)
j=1
Then, the robust decision is given by solving the following:
max, min subject to
Σ 15
(r())
-=
(72)
222
18

---

Published as a conference paper at ICLR 2024
However, this is computationally expensive problem as it requires exponential constraints. We see this in the increased running time required to solve the problem. Therefore, we also compare with the same data-driven approach but using simpler uncertainty set. In, particular consider the set of probability distributions я that within 1-norm distance from the empirical ř = 1 1/n. We denote this the variation distance uncertainty set LVD:
u = {
π
T20,
Tj = 1,
[ Rg 5c
(73)
==1
==1
C.4 INVENTORY ALLOCATION WITH NO FEATURES
We now consider an inventory allocation problem with K products from a store and must decide on a number 24 items of type k. k = 1..... .,. K to order. Let d . d(M) denote the demand vectors on each of the M days of data, d(:)) denotes the demand of product k on day m. We assume a uniform holding cost of H for each unit of product that is not sold and lost opportunity cost C for each unit of demand is left unmet. The cost of allocating units when the true demand is d is given by
K
max 2k, 0} + H. max (ax - da, 0}.
(74)
k=1
Furthermore, there is a capacity on the total supply of products allowed in the store. So, Ek= Fa < S. We wish to make decision æ which maximizes the probability that its cost is below a certain threshold with demand d coming from some unknown distribution D:
P EK C. max(dd Ik, 0} + H max - dx. 0} st)
max
(75)
subject to Ek=1 S
24 20
Using the framework of minimizing the expected violation, we reformulate the problem
ΣM
maxy,ge Ne..
9m
subject
Im
k=
K
H
hm
+ +C Ck
h
2 23
h 2 0 dg
(m)
(76)
d ml
Tk.
C 20
Σ 2* <
Σ
S,
04
where we introduce variables hy and cx. to indicate the number of units that contribute to holding and opportunity costs, respectively.
Adaptive robust optimization: We also compare against an adaptive robust optimization ap- proach. Note that this is inherently two-stage problem: after demand realization is made, one must fulfil the demand. So, 23 are the first stage allocation decision, and (d), c (d) are the second stage variables that describe the fulfilment of demand d. Let U denote the uncertainty set for the uncertain demand Then, the adaptive robust optimization problem is given as
Σk hx(d) + C. (x(d)
min, maxdeu subject to
(d) 2 σx de. he(d) 2 0
Ck (d) 2 dç - de, hy (d) 2 0
(77)
Σ 1-11 Z3 =1
However, as written this is an infinite dimensional problem, requiring different variable by (d) for each E U. As is commonly done, we use linear decision rules for the second stage variables. Hence, (d),), (d) now linear functions of d:
K
hx(d) = h
+
h
dj
(78)
==1
K
(d) = ch + Σ
ck
(79)
j=1
19

---

Published as a conference paper at ICLR 2024
for new variables gg..... h Cx: ........ of 1...., K to define the linear functions of d. As an uncertainty set, we use again a budget uncertainty set:
dx
u
d
<
(80)
Ok
where μ4g, are the empirical mean and variance of the demand of the kth product. Again, I is the budget of uncertainty that must be tuned.
Data driven, KL-divergence and variation distance. As in the previous section, we consider the data-driven method, robust against all empirical distributions that are within fixed distance from the observed empirical distribution. Again, let Rm denote the uniform distribution over the data d(t) d(M)) We consider the two uncertainty sets of KL-diveregence 4K and Variation Distance unD in and 73 The problem can then be formulated
min yb. TE/KL//D subject to
Mh
Em mm (EE h
k=
H hT
C..
2
d%
hg 2
(81)
(m)
Ck
Tk.
Ck 2 0
k= TA S S,
T2
0
For each decision made by all four approaches described above we calculate all costs test data and report the worst case costs incurred. In figures 5 we see the costs of the worst 5% examples for each decision various different supply capacities. We see that overall our proposed approach the minimum of the other approaches at almost every quantile. Furthermore, as the capacity increases, and the more freedom have in the decisions we make, the larger the gaps become. At the very highest quantiles 199%-,00)) we see our approach performing up to 15-20% better than the other approaches. Moreover, in the 95%-97% quantiles, our approach and the adaptive approach have cost lower by up to 18% compared to the KL and VD approaches when the capacity is 800. At a capacity of 1100, they have cost up to 25% lower.
Results:
6
Capacity 800
Capacity 1000
4000
divergence
divergence
VD divergence
divergence
3500
Adaptive
3000
Adaptive
3000
Minimum Violation
2500
Minimum Violation
25.00
2000
1500
1500
1000
500
1.00
1.00
quantile
quantile
Figure 5: Worst-case costs at 800 capacity.
Figure 6: Worst-case costs at 1000 capacity.
D IMPLEMENTATION AND TRACTABILITY
We now discuss some details of implementation and improving the running time of the method. There are two parts the approach, first to learn the labelling P and second solve the optimiza- tion problem to determine (x)..
E MAXIMIZING PROBABILITY OF Low REGRET
Finally, we have a brief discussion on the difficulty of the original robust problem proposed in 4
max Pug-DD (Rw_(w) Φ).
WEP
In general, if the distribution D' is discrete, having point masses v....., De with probabilities Pl,---3 - Pk. the problem can be formulated as mixed integer optimization problem:
20

---

Published as a conference paper at ICLR 2024
Σj=1 qj
maxw. 4
subject to
Ryz((V) (w) Set + M 93)
(83)
w E P q E (0, 13
If Reg (w) e, the constraint forces that q whether B2g (w) S or not. indeed the regret less than e, then qi can take either the value 0 or But the objective is to maximize the weighted sum of the Zj. therefore at optimality, will take the value of whenever the regret of w with respect Da is most
Therefore, qj is a binary variable that reflects
21


Reviews:
[{"review_id": "WFGIjXjAuV", "reviewer": "Reviewer_XXVR", "summary": "This paper explores robust contextual stochastic optimization. In this problem setting, we have a feasible set $\\mathcal{P}$ and an objective function $g_{\\bm{v}}(\\bm{\\omega})$, where $\\bm{v}$ is a random variable. The distribution of $\\bm{v}$ depends on a contextual variable $\\bm{x}$, denoted as $\\bm{v} \\sim \\mathcal{D}_{\\bm{x}} $, and this distribution is unknown. Unlike other contextual stochastic optimization problems, the primary focus of this paper is the following problem:\n$\n\\min_{\\bm{\\omega} \\in \\mathcal{P}} \\mathbb{E}_{\\bm{v}_{\\bm{x}} \\sim \\mathcal{D}_{\\bm{x}}} \\left[\\max\\{R_{\\bm{v}_{\\bm{x}}}(\\omega)-\\phi, 0 \\}\\right]\n$\nThis problem aims to minimize the expected violation, where $\\phi$ represents a user-defined cost threshold. Here, $R_{\\bm{v}}(\\omega) = g_{\\bm{v}}(\\bm{\\omega}) - g_{\\bm{v}}(\\bm{\\omega^*(\\bm{v})})$ denotes the regret of decision $\\bm{\\omega}$ when the objective function parameter is $\\bm{v}$.\n\n\\section*{Methodology}\n\nGiven a historical dataset of observations $\\{(\\bm{x}^i, v^i)\\}_{i=1}^n$, the authors propose to define two key components:\n$\nH_k^\\epsilon = \\{\\bm{\\omega}\\in \\mathcal{P}: R_{\\bm{v}^k}(\\omega) \\leq \\epsilon\\},\n$\nand\n$\np^n_k = \\begin{cases}\n    1, & \\text{ if } \\bm{\\omega}^*(\\bm{v}^n) \\in H_k^\\epsilon\n    \\\\\\\\\n    0, & \\text{ otherwise}. \n\\end{cases}\n$\n\nTo harness this information, the authors propose training a machine learning model $\\hat{p}_k^\\epsilon(\\bm{x})$ to predict $\\mathbb{P}(\\bm{\\omega}^*(\\bm{v}_{\\bm{x}}) \\in H_k^\\epsilon)$. Consequently, the contextual stochastic optimization problem transforms into:\n$\n\\min_{\\bm{\\omega}} \\sum_{k=1}^N \\hat{p}_k^\\epsilon(\\bm{x}) \\max\\{R_{\\bm{v}_{\\bm{x}}}(\\omega)-\\phi, 0\\}.\n$\n\n\\section*{Questions and Comments}\n\nIn reviewing this work, several questions and comments have emerged:\n\n\\begin{itemize}\n    \\item First, regarding the definition of $H_k^\\epsilon$, it seems unnecessary to have that $\\cup_{k=1}^n H_k^\\epsilon = \\mathcal{P}$. If this is the case, it is unclear how the authors intend to bound the regret when $\\bm{x}$ is observed and $\\mathbb{P}\\left(\\bm{\\omega}(\\bm{v_x}) \\in \\mathcal{P}\\setminus (\\cup_{k=1}^n H_k^\\epsilon)\\right) > 0$.\n    \n    \\item Additionally, the paper would benefit from a discussion of how the machine learning model $\\hat{p}_k^\\epsilon(\\bm{x})$ is trained based on the provided data. Are the models trained jointly or separately on $(p_k^n)_{k=1, \\cdots, n}$? If trained separately, there may be cases where $\\sum_{k=1}^N \\hat{p}_k^\\epsilon(\\bm{x}) \\neq 1$, making it challenging to interpret $\\min_{\\bm{\\omega}} \\sum_{k=1}^N \\hat{p}_k^\\epsilon(\\bm{x}) \\max\\{R_{\\bm{v}_{\\bm{x}}}(\\omega)-\\phi, 0\\}$ as an approximation of $\\min_{\\bm{\\omega}} \\mathbb{E}_{\\bm{v}_{\\bm{x}} \\sim \\mathcal{D}_{\\bm{x}}} \\left[\\max\\{R_{\\bm{v}_{\\bm{x}}}(\\omega)-\\phi, 0 \\}\\right]$. In cases of joint training, how do the authors handle models when the possible outcomes $(p_k^n)_{k=1, \\cdots, n}$ outnumber the training data size? Regrettably, these details are not addressed in the numerical study neither.\n    \n    \\item Furthermore, when examining the final problem:\n$\n    \\min_{\\bm{\\omega}} \\sum_{k=1}^n \\hat{p}_k^\\epsilon(\\bm{x}) \\max\\{R_{\\bm{v}_{\\bm{x}}}(\\omega)-\\phi, 0\\}\n$\n    it becomes apparent that, although it is linear in $n$, when $n$ is very large, this problem may become computationally challenging. Do the authors have any insights or strategies for addressing this issue?\n    \n    \\item Finally, the overall framework resembles a weighted average optimization problem. It would be meaningful to discuss how this framework fundamentally differs from Bertsimas and Kallus (2020) and related literature.\n    \n    \\item A recommendation is made to move Section 5 entirely to an appendix, allowing more space for a deeper discussion of the framework, algorithm, and implementation details.\n\\end{itemize}\n\n\\section*{Minor Comments}\n\nSome minor comments for consideration:\n\n\\begin{itemize}\n    \\item In Equation (10), $H_\\epsilon^k$ should be corrected to $H_k^\\epsilon$.\n    \n    \\item In the beginning of the sixth line in Theorem 4.1, $H_k$ should be corrected to $H_k^\\epsilon$.\n    \n    \\item In the penultimate line of the same theorem, $x \\to \\bm{x}$ and $\\bm{v}_x \\to \\bm{v_x}$ for consistency.\n\\end{itemize}", "questions": "Please see my comments in Summary for details.", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Proposed a new framework to solve robust contextual stochastic optimization problem. Please see my comments in Summary for details.", "weaknesses": "Not fully clear presentation/discussion of their algorithm. Please see my comments in Summary for details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ctsAJAtJ8t", "reviewer": "Reviewer_67NA", "summary": "This paper proposes and studies a novel robust optimization framework that is based on discretization of the domain with respect to the data set. The framework proceeds as follows. For each data sample about the problem uncertainty, it constructs the set of near-optimal solutions to the optimization problem whose parameters are specified by the data sample. These sets basically give rise to the \"discretization\" of the solution space. Then the framework builds an ML model to learn the probability that the optimal solution to the problem whose parameter is given by a particular data sample is near-optimal with respect to other data samples. Here, the framework is flexible in terms of choosing which ML models to use, e.g., k-nearest neighbor. The paper provides some theoretical performance guarantees of the proposed framework and promising numerical results.\n\nHowever, it seems that the paper could be further improved by investigating further the connections between the proposed framework and the existing data-driven robust optimization methods. Moreover, the paper needs to refine and better present its theoretical performance guarantees. Lastly, the reader would appreciate if the paper provided more intuitions about the proposed framework for robust optimization problems particularly.", "questions": "* On page 4, the algorithm is described. Should each data be given by $(x^n, (p_k^n)_{k=1,\\ldots, N})$ instead of $k=1,\\ldots, n$?\n* Typically, the notion of regret is defined for iterative learning processes. Is it possible to extend the current framework to the online setting for which we allow updating the model with a new set of data samples.\n* In the introduction, it is stated that the difference between the in-sample cost and the out-of-sample cost decreases on the order of $1/\\sqrt{n}$. Perhaps, it would be a better strategy to decompose the current statement of Theorem 4.1 into two where one explains the statement and the other presents the regret bound. \n* Could you provide more computational results on a broad set of tolerance levels? For example, 50%, 75%, 90%, 95% quantiles.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The robust optimization framework of solving minimizing $E[[R(w)-\\phi ]_+]$ is novel while it is related to many of the existing robust optimization frameworks.\n* The data-driven learning-and-optimization method studied in this paper is novel, and the method is flexible in that it can take any ML models to learn the uncertain parameters of the problem.\n* The paper provides both theoretical performance analysis and promising numerical results.", "weaknesses": "* It is difficult to appreciate the main theoretical performance guarantee on the proposed framework  (given in Theorem 4.1) due to its dependence on the parameters $c$ and $\\alpha$. Here, $c$ would increase as the accuracy parameter $\\epsilon$ as well as the size of each subset decrease, in which case the bound gets weak. We may try to decrease the parameter $\\epsilon$ to make $c$ close to 1, but this would make the mean prediction error $\\mathcal{E}$ large. At the same time, no explicit dependence of $c\\mathcal{E}$ on $\\epsilon$ is studied. Lastly, $\\alpha$ could be arbitrarily large when the objective function is not bi-Lipschitz. \n* The framework is almost equivalent to minimizing the conditional value-at-risk (CVaR), except that there is an additional probability term being multiplied. The paper would be stronger if it discussed the relationship between the existing CVaR minimization setting and the framework of this paper. No numerical results were done with the CVaR framework. \n* There are many typos in the mathematical proofs in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VToPlDX2Zg", "reviewer": "Reviewer_VbmN", "summary": "The paper proposed a new data-driven approach for the contextual optimization problem. It also provides a new loss function to allow users to balance the robustness and the expected performance. To illustrate the performance, the authors provide a theoretical analysis of the regret and algorithm stability as well as the numerical results for many applications.", "questions": "1. Corresponding to Part 1 in the weaknesses, I wonder whether one can learn the probability efficiently. Or, equivalently, I wonder whether the authors could elaborate more on the sample complexity for learning and reducing $\\Epsilon$ in (11) for Theorem 1. Please correct me if I am wrong. For me, I am not sure whether it is possible to learn $\\Epsilon$ efficiently, especially when the dimension of the feasible set is large. In other words, one may require the size of training data to be exponentially large as the dimension of the feasible set to have a low $\\Epsilon$. Particularly, based on the algorithm, H_k^{\\epsilon} may only cover a small region, the volume of which can decrease exponentially when the dimension is high. Then, if the size of the training samples is only polynomially large as the dimension, it is very likely that $H_k$'s are disjointed or rarely have non-empty intersections. In this case, the multi-label data set for each training sample might be a vector with only one non-zero entry.\n\n2. Can the algorithm still be useful when the feasible region also depends on the contextual data?\n\n3. In practice, I wonder how one should choose $\\phi$ and $\\epsilon$.\n\n4. Corresponding to part 4 in the weaknesses, I wonder whether the authors would like to change Theorem 4.1 to a uniform generalization bound.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The idea is new and interesting, which is to discretize the decision set to do the robust optimization looks interesting.\n\n2. The new loss function can balance the worst-case regret and the expected regret.\n\n2. the numerical performance looks good.\n\n3. the paper has theories corresponding to the algorithm.", "weaknesses": "1. My main concern is the efficiency of the given algorithm. For me, it might be impossible to efficiently learn $\\hat{p}$ in Step 3 of the algorithm unless the size of the training sample is exponentially large as the dimension of the feasible set. Please see question 1 for more details.\n\n2. It seems that the feasible set must be fixed for different contextual information.\n\n3. It would be better to have more discussion about the choice of $\\phi$ in the loss function.\n\nSome minor points:\n\n4. In addition, It looks like the bound in Theorem 4.1 is established for any fixed decision $w$. It would be better to have a uniform generalization bound instead since the output of the algorithm is not a fixed action.\n\n5. Assumption 5.2 looks strong for many optimization problems. For example, linear programming does not satisfy (14).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q0DI8f9qOh", "reviewer": "Reviewer_9FbH", "summary": "The authors propose a new approach to contextual stochastic optimization. This approach first divides the feasible region into subregions, and then builds a prediction model that predicts the probability that the optimal solution for a given context will fall in a given subregion. These predicted probabilities are incorporated into an optimization problem that can be used to select a decision for a given context. The authors provide asymptotic bounds regarding the generalization error of the method as well as a type of stability of the method. The authors provide computational results demonstrating the results of the method for a newvendor problem and a generator scheduling problem.", "questions": "Why did you choose this particular form of objective function, rather than using more established notions of risk, such as CVaR?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The author's approach to contextual stochastic optimization problems is overall quite novel. The paper is well-organized and clearly written. Contextual optimization problems are an important topic of recent interest, so novel methods for this class of problems are a welcome contribution.", "weaknesses": "There is a significant issue with the framing of the paper. In particular, the authors frame their contribution as an approach for robust contextual stochastic optimization problems. However, I do not think that this an accurate presentation. Consider the central optimization problem (equation 5, page 4): \n$$\\min_{w \\in \\mathcal{P}} \\mathbb{E}_{\\nu_x \\sim D_x}[\\max\\\\{R\\_{\\nu\\_x}(w)-\\phi,0\\\\}]$$\nNote that this problem can be rephrased as the problem of minimizing the expectation of a function $f\\_{\\nu\\_x}$, specifically: \n$$f\\_{\\nu\\_x}(w) = \\max\\\\{R\\_{\\nu_x}(w)-\\phi,0\\\\}$$\nSo, this problem is just a special type of a contextual stochastic optimization problem, and techniques for contextual stochastic optimization problems, such as that in Bertsimas and Kallus (2020) or Donti et al. (2017), could be applied here. Note that robust, distributionally robust, or risk-averse optimization problems cannot typically be easily reduced to a standard stochastic problems. \n\nThe authors do not provide a proof of Lemma A.1 in the appendix, which seems like a fairly critical step in the proof of Theorem 5.1. In addition, I suspect that Lemma A.1 is not actually true. In particular, the Hypothesis Stability provides a convergence rate $\\beta_N$ on the change in predicted probability by omitting a point for a single binary classification problem. However, it seems to me for this lemma to work, the authors would need a uniform convergence rate $\\beta_N$ that applies to all $N$ binary classification problems (note here that the number of binary classification problems appearing in the authors' method increases with sample size). This seems to me to be a much stronger property.\n\nThe computational experiments compare the authors' methods to methods that solve a completely different problem. In particular, three of the four comparison methods seem to be designed to solve the problem $\\min\\_{w}\\mathbb{E}\\_{\\nu\\_x \\sim D\\_x}[R\\_{\\nu\\_x}(w)]$ , while the remaining method (KNN+KL Robust) is designed to solve a robust variant of this problem that is not clearly connected to the problem that the authors are solving. Notably, the authors claim that the method of Bertsimas and Kallus (2020) does not apply to this problem. However, this method can be applied as follows. First, fit a prediction model that predicts the parameter $\\nu$ from the context $x$. Then, given some fixed context $x$, derive weights $\\hat{p}\\_n(x)$ for each training points $\\{x^N,\\nu^N\\}$ (as described in Bertsimas and Kallus 2020).  Then, solve the problem: \n$$\\min_{w \\in \\mathcal{P}} \\sum_{n=1}^N \\hat{p}\\_n(x)\\max\\\\{R\\_{\\nu^n}(w)-\\phi,0\\\\}$$\n\nSimilarly, the method of Donti et al. (2017), the \"policy optimizer method\" and the \"MLE method\" could also be applied to the problem $\\min_{w \\in \\mathcal{P}} \\mathbb{E}_{\\nu_x \\sim D_x}[\\max\\\\{R\\_{\\nu\\_x}(w)-\\phi,0\\\\}]$, rather than to the problem of $\\min\\_{w}\\mathbb{E}\\_{\\nu\\_x \\sim D\\_x}[R\\_{\\nu\\_x}(w)]$ by making relatively straightforward modifications to these methods.\n\nMinor comments:\n\nThe authors state that $\\mathbb{E}\\_{\\nu\\_x \\sim D\\_x}[R\\_{\\nu\\_x}(w)-\\phi \\mid R\\_{\\nu\\_x}(w) \\geq \\phi]$ is the CVar (discussion following equation 6 in page 4). However, this is not accurate. The CVaR in this setting would be given by something like: $ \\mathbb{E}_{\\nu_x \\sim D_x}[R\\_{\\nu\\_x}(w) \\mid R\\_{\\nu\\_x}(w) \\geq q\\_{\\alpha}(R\\_{\\nu\\_x}(w))]$ where $q\\_{\\alpha}(Z)$ gives the $\\alpha$ quantile of the variable $Z$. Minimizing the latter is not equivalent to minimizing the former. \n\nThe authors frequently refer to expressions involving $w^*$ that are only well-defined if the problem has a unique solution. This could easily be fixed, for example by stating that $w^*$ is an oracle that chooses one solution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)