Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
Authors: Omar Bennouna
Jiawei Zhang
Saurabh Amin
Asuman E. Ozdaglar
Venue: ICML 2025 poster (2025)
Keywords: Contextual Optimization
Machine Learning
Constrained Optimization
Primary area: optimization->nonconvex

Abstract: Contextual optimization problems are prevalent in decision-making applications where historical data and contextual features are used to learn predictive models that inform optimal actions. However, practical applications often suffer from model misspecification due to incomplete knowledge of the underlying data-generating process, leading to suboptimal decisions. Existing approaches primarily address the well-specified case, leaving a critical gap in handling misspecified models. In this paper, we propose a novel Integrated Learning and Optimization (ILO) framework that explicitly accounts for model misspecification by introducing a tractable surrogate loss function with strong theoretical guarantees on generalizability, tractability, and optimality. Our surrogate loss aligns with the true decision performance objective, ensuring robustness to misspecification without imposing restrictive assumptions. The proposed approach effectively mitigates the challenges of non-convexity and non-smoothness in the target loss function, leading to efficient optimization procedures. We provide rigorous theoretical analysis and experimental validation, demonstrating superior performance compared to state-of-the-art methods. Our work offers a principled solution to the practically relevant challenge of model misspecification in contextual optimization.

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
Omar Bennouna" *1
Jiawei Zhang 12
Saurabh Amin
Asuman Ozdaglar'
Abstract
be estimated using contextual information. A canonical example is traffic routing, where the costs of traversing net- work edges-initially unknown-depend on observable fea- tures such as weather, time of day, and construction activity. Given historical data, the goal of contextual optimization to learn policy that maps observed contexts near-optimal decisions (Sadana et al., 2024).
Contextual optimization problems are prevalent in decision-making applications where historical data and contextual features are used to learn predictive models that inform optimal actions. However, practical applications often suffer from model misspecification due to incomplete knowl- edge of the underlying data- tata-gennrating process, leading to suboptimal decisions. Existing ap- proaches primarily address the well-specified case, leaving a critical gap in handling misspeci- fied models. In this paper, we propose a novel In- tegrated Learning and Optimization (ILO) frame- work that explicitly accounts for model misspeci- fication by introducing& a tractable surrogate loss function with strong theoretical guarantees on generalizability. tractability, and optimality. Our surrogate loss aligns with the true decision perfor- mance objective, ensuring robustness to misspeci- fication without imposing restrictive assumptions. The proposed approach effectively mitigates the challenges of non-convexity and non-smoots in the target loss function, leading efficient optimization procedures. We provide rigorous theoretical analysis and experimental validation, demonstrating superior performance compared to state-of-the -he--rr- methods. Our work offers a princi- pled solution to the practically relevant challenge of model misspecification in contextual optimiza- tion.
A standard framework for contextual optimization assumes that the unknown cost vector E IR is correlated with an observed context & E R2 and the objective is to minimize expected decision cost:
min Bee,c)~ (cTTx)))
sell
Here, P is the joint distribution of (x, c), and IT is set of feasible policies that map contexts to decisions in a bounded convex set W C. Rd. Since the true cost function is un- known in practice, must be approximated using a predic- tion model from hypothesis class H.
The widely used predict-then-optimie approach first learns predictor ē(z) from H. and then selects a decision by solving:
f +xx) arg min c(z) w..
wEW
Prior works mainly adopt two approaches: Sequential Learn- ing and Optimization (SLO) (Bertsimas and Kallus, 2020; Hu et al., 2022) and Integrated Learning and Optimization (ILO) (Donti et al., 2017: Elmachtoub and Grigas, 2022: Sun et al., 2023). SL.O focuses solely minimizing predic- tion error for c, ignoring the downstream optimization task, while ILO prioritizes decision performance over accurate cost prediction. Recent research in Integrated Learning and Optimization (II.O) refines cost prediction to improve down- stream decisions, under the assumption that 7 contains the true cost function. In other words, previous ILO approaches assume that H. well-specified.
1. Introduction
Many real-world decision- Decision-making problems require opti- mizing decisions based on uncertain parameters that can
'Equal contribution 'Department of EECS, Massachusetts Insti- tute of Technology 'Department of Computer Sciences, University of Wisconsin Madison. Correspondence to: Omar Bennouna <omarben mii. Jiawei Zhang <jzhang2924@# eis..
However, real-world settings often violate the above assump- tion. We say that H. is misspecified when it does not contain predictor that perfectly captures the true cost function. In real-world applications, this situation can arise due to incomplete feature sets, unmodeled dependencies, or distri- bution shifts. Despite its practical significance, contextual
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
optimization under model misspecification remains under- explored in the literature. Most existing research in ILO assumes H is well-specified and focuses on design of surro- gate loss functions and algorithms to maximally reduce the decision error. While some recent empirical works (Donti et al., 2017; McKenzie et al., 2023; Kotary et al., 2023; Huang and Gupta, 2024) explore decision-aware learning under misspecification. they lack theoretical guarantees for global optimality and generalization. Additional literature review is available in Appendix A.3.
To illustrate why traditional approaches such SLO and (SPO+) fail to handle misspecified H. consider a simple binary classification example: suppose the decision space is W = [-1/2, and the cost vector c takes values in {-1,1}, and the minimization in (3) is replaced by maxi- mization. The optimization problem then reduces to mini- mizing:
( = + ((r,))> (L)ign(((a)))ee)
(6)
We argue that the key challenge lies in distinguishing be- tween two forms of misspecification (see Appendix A.4 for further details):
This formulation is closely related to minimizing classifica- tion error in binary classification. We can observe that SL.O and SPO+ lead to suboptimal solutions in such a setting.
Example 1. Consider the following hypothesis class: H {a1, and the context takes only values and 2 equally likely, and always takes the value 1. Assume that (1 = 5. (1( = a. (1)== L, and (2 = - Although è leads to optimal decision-making, both SPO+ and SLO select č2, a suboptimal predictor (refer to Appendix A.
1. Prediction Misspecification: The inability of model ((x)) accurately estimate c(x);
2. Decision Misspecification:
The inability of model a(xr) to produce the same decisions as those derived from the true cost function.
Thus, in contextual optimization, the challenge is to design tractable approaches to tackle decision misspecification. In- deed, a model can yield poor predictions yet still make optimal decisions-and vice versa. Yet, standard methods such as Sequential Learning and Optimization (SLO) and Smart Predict-then-Optimee gas, 2022) fail to guarantee optimal decision-make making in the presence of misspecification, leading to suboptimal policies.
This example demonstrates that SPO+ and SLO do not nec- essarily yield optimal decisions. Similar conclusions can be drawn for more practical traffic routing problem, where the goal is to allocate traffic across roads to minimize travel time based on contextual factors like weather, time of day, and road construction. Suppose the true travel cost depends on all three factors, but due to model limitations, only weather and time of day are considered, ignoring road construction effects. This model misspecification leads both SLO and SPO+ to learn systematically biased cost estimates, which fail to anticipate congestion caused by construction. As a result, traffic is misallocated, leading to longer travel times during construction periods. SLO fails because it prioritizes prediction accuracy over decision performance. while SPO+ fails because its decision-aware learning is constrained by incomplete hypothesis class. This demonstrates how standard methods can yield suboptimal decisions, even if predictions appear reasonable, highlighting the need for a method that directly optimizes decision quality despite misspecification.
(SPO+) (Elmachtoub and Gri-
1.1. Problem setup
For simplicity, we consider that unknown parameters appear linearly in the objective function of the stochastic optimiza- tion problem:
min E (( (c w|z) wEW
min p(r.))=(((x=) w. (3)
WEW
Since c is unknown, we approximate it using a predictor è E H. where č(x) is learned using historical data. Impor- tantly, H can be misspecified. The decision-making process as follows: first, observe the context x and predict the cost vector ē(æ). Next, compute decision w(((x)) that minimizes the predicted cost:
1.2. Our contribution
w(((=)) E arg min 6(x) wEW
(4)
To address these limitations, we propose a novel decision- aware surrogate loss function that explicitly minimizes de- cision error regardless of whether or not H. is misspecified. Our approach ensures optimal decision performance un- der model misspecification and provides strong theoretical guarantees, ensuring both optimality and generalization per- formance. Importantly, our tractable surrogate loss function matches the optimal solutions of the true objective (5), has favorable optimization properties, avoiding bad local min- ima, and generalizes well to new distributions. We prove
We consider that the hypothesis set H. is parametric, i.e. it can be written as H. = (čo, O E }. Our goal is to find predictor èg that minimizes decision error, defined as:
( = P
max c_ cTw) WEW (ca(x))
(5)
where (Z) := arg min Z w represents the set of optimal solutions given a predicted cost vector č.
2

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
that our surrogate loss:
Our task now becomes to solve the optimization problem (7). Since known approaches cannot be directly applied to solve (7), we develop an approach based on surrogate loss function that enjoys two properties:
Yields globally optimal decision policies (Theorem 1).
Exhibits strong generalization properties (Theorem 2).
1. Consistency: The optimal solutions for the surrogate loss are also optimal for the target loss;
Is computationally tractable, enabling efficient opti- mization via first-order methods (Theorem 4).
2. Tractability: The surrogate loss is tractable opti- mize.
We also evaluate our approach against SPO+ and SLO, showing superior performance under varying degrees of misspecification.
2.2. Introducing our surrogate loss function
The remainder of the paper is structured as follows. Section 2 formalizes the problem and introduces our surrogate loss function. Section 3 establishes theoretical guarantees. Sec- tion 4 presents empirical results comparing our approach to existing methods. Section 5 concludes with future research directions.
We introduce a new surrogate loss function referred as Consistent Integrated Learning and Optimization (CIL.)) loss for contextual optimization under misspecification.
Definition 1. (CILO loss) For 3 E R. we define the function f
Y0 E RT, eg(0) = min B(ao)) (Bo(#) w((()) weewy
2. Our approach
B())) (ca(x) up(x)), (co(x)]up(())
2.1. Rewriting E under a generic assumption
min wPEWp
Recall from (5) that the generic form of the target loss func- tion in our contextual optimization problem involves the worst case value of c w when arg win (a(x)" Tw because the solution to minwew èo (x) w is not nec- essarily unique in theory.
where W Up E Wp. B(r,)) (c wp(x)) s $}.
In (Elmachtoub and Grigas, 2022), authors show that in the binary classification setting, the SPO+ loss is equal the hinge loss, i.c.
In practice, however, arg win w čo (z:) w is likely to be unique. For example, in the common case where č (z) is a continuous random variable and W is a polyhedron (or more generally when the set of directions ē for which the solution minwew è" w not unique is of Lebesgue measure equal to zero), unique- ness holds with probability 1. Hence, due to practical rea- sons and theoretical convenience, we make the following assumption henceforth:
Vc, č E Rd, (2, c) max(0, 1 2cē).
We introduce the following notation, for every B E R and measurable function è
(g(()) min
B(ee)~ (c(x) T wf w..W, min wpEWp
Assumption 1. For any O E Ih" such that Co(x:) * 0 almost surely, min (0(x) w has a unique solution with probability 1 when (I, c) ~ P.
B( (6(x) T wr(x))
We denote 3h.P E(z,e)~ (max c cTw). The following proposition shows that the CILO loss also has an interesting expres- sion in the binary classification setting when the hypothesis set is decision- well spll-specfffed.
(y(e))e((() and faax,
We denote Wp the set of measurable mappings from the support of the joint probability P of (I,c) to the set of feasible decisions W. Under Assumption 1, we can see that the problem of minimizing target loss can be written as follows:
In the binary classification setting, when 3 BH. and is deterministic function of x. for every measurable function è, when H. is decisson-well--peecffeld we have
Proposition 2.1.
min (P( min min E( (c wp(x))
BERm
BER" wrEWr
s.t. Vr E RR wr(x) E arg min (z) T w.
NEW
(8)
(g(() = E(z,e)) Asig((((=))
(9)
We formulate a proposition that provides a sufficient condi- tion for Assumption to hold when W is a polyhedron in Appendix A.5.
The proof of this proposition is in Appendix A.6. We can see in Proposition 2.1 that the CILO loss nearly matches the expression of the target loss when the hypothesis set
3

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
decision-well well-specified (and not necessarily prediction-well- specified) and is deterministic in s.. Furthermore, when à does not take the value zero, the consistency or the CILO loss is clear from its expression.
ture: existing surrogate losses, though tractable, guarantee optimality only under well-speciffed settings. While some perform well experimentally in misspecified cases, no exist- ing approach ensures global optimality across all levels of misspecification. We close this gap in Section 3.
The following example shows that whereas SLO and SPO+ fail to provide a minimizer for Ep, this new surrogate suc- cessfully does so.
3. Technical approach
Example 2. We revisit Example I. We have seen that SPO+ and S1.O do not favor the best element of the hypothesis set H. Since H is decision-well-spetee
In this section, we formalize our technical approach based the CILO loss function and the consistency result. We first mention three key issues that our approach seeks to address. In the remainder of the paper, we denote by ||-|| the 2 norm.
by choosing 3 = P = = 2. from proposition 2.1, equality (9) is satisfied. Consequently, we have (G)( = O and (62) = 12 > e (fp())) We see that indeed here, the global minimum of this new loss is optimal for the target loss.
Firstly, we do not have access to the joint distribution P of random variables (z, e): instead we assume that we have access a historical dataset S =
(Iin Gn)). where is the number of samples and each sample (I,, ct), E [n] is sampled from P. Thus, we seek to optimize the empirical version of CILO, denoted e where P, is the uniform distribution over the dataset S. The question we need to address is whether by minimizing empirical CILO, we can obtain good generalization performance (i.e., guarantees on out-of-sample CILO loss). Theorem 2 shows that this is indeed the case.
It is important to keep in mind that in the example above, the model is prediction misspecified, but decision well-specified. Hence, even when there exists a cost predictor that yields the same decisions as c, SPO+ and SLO may fail to favor the best cost predictor in term of decisions. Decision-wed specification is not necessary for the CILO loss' consistency to hold in the example. To see that, it suffices to add third point in the distribution of P which is labeled the same way by è1 and 8 This example will yield the same results.
Secondly, the CILO loss di is a non-convex and non- smooth function, and we need a technique to optimize it in tractable manner. We provide one way to address this issue by leveraging the Moreau envelope smoothing technique (Sun and Sun, 2021) to transform the problem of minimizing tp into another optimization problem whose objective func- tion enjoys good landscape; in particular it is smooth and has no "bad" first-order stationary points or local minima (see Theorem 4). Consequently, this smoothed optimization problem is conducive to gradient descent.
We will now prove that the consistency observed in example 2 holds in general. The lemma below will be useful when proving our main consistency theorem.
Lemma 1. For every B E R such that Bi.P S B, Ep is non-negative.
We now formulate our main consistency theorem.
Theorem 1. Let 3 E I such that SH.p S B < Smar, P. Under Assumption 1, for every 0 E R. with ca(x)) # 0 almost surely, (p))) S 8 if and only 0 is a minimizer of pp- In particular, when 3 = BH. 0 is a minimizer of e if and only if it is a minimizer of tpp
Thirdly, to guarantee consistency, we must ensure that the optimization procedure is able to find minimizer f that veri- fies èn (xx A almost surely (see Theorem 1). We address this issue by refining our smoothing procedure so that gradi- ent descent on smoothed CILO loss results in minimizer that verifies (x) + 0 almost surely (see Theorem 6).
The proof of this thcorem is in Appendix A.7.
This result suggests a natural approach to minimizing pp: first, find tractable method to minimize the CILO loss eg for a suitable choice of auxiliary parameter B, ensuring the candidate minimizer 0 satisfies (z) # 0 almost surely. While $4.r is unknown, achieving a sufficiently small value of t% during optimization likely ensures that the target loss Ep remains below B. To select _., one can perform line search over a suitable interval [8, [3] and choose the value that minimizes the CILO loss. We now develop tractable (in the sense that it runs in polynomial time in theory and is efficient in practice) procedure to optimize eg makinn the line search feasible- and formalize the relationship be- tween near- optimal el values and the target loss Ep. This addresses a key limitation in contextual optimization litera-
These three steps together ensure that we have tractable approach to minimizing empirical CILO loss, resulting in a solution that has good generalization perform optimality guarantee.
3.1. Generalization performance
We study the generalization performance of the empirical version of CILO loss and show that by optimizing the em-
pirical CILO loss f... we can ensure a nearly optimal value for its out of sample counterpart eg. We first make the following boundedness assumptions.
4

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
Assumption 2.
W is closed and bounded and there exists K 2 0 such that for all x RR, ||e[=:]]| S K. We denote
Assumption 4. For 0 + O, (o(x)) # 0 almost surely.
Bw = su |l|]-
Assumption 4 holds when for every 0 E I \ {0]. Eg is a nonzero analytic function and has continuous distribu- tion. In this case, the set of zeroes of éq is of measure equal to zero (see (Mityagin, 2015)) and consequently z does not belong to this set almost surely. This assumption, coupled with Assumption 1, implies that for any 0 E IR" \ {0), the problem min Co(xr) w has a unique solution almost surely.
Assumption 3. When 0 0. (x(x) = O. Furthermore, there exists B+ 2 0 such that the gradient with respect to 0, (eo(ar), is piecewise continuous and bounded by Bo for every 0 E I=m' and x E I²*
The first part of Assumption 3 is natural when we as- sume that there exists Og E TR such that Co. = 0. By reparametrizing the hypothesis set as H' = co+a. 0 E RT,
We give more concrete optimality guarantee obtained by minimizing ey. which sharpens Theorem 1. We first make an assumption similar to the assumption in (Hu et al., 2022) which enables the authors to get good generalization guar- antees for SLO in the well-specified case. However, our assumption add conditions on the hypothesis set rather than the ground truth cost.
we obtain ég- = 0. Furthermore, a direct consequence this assumption is that for every x E R and R.
[6o(z)]| = 11.0 Vēto(x)Todd)) eatl
! VVzo(x) dt s Bx |011
Assumption 5. Assume that W is a polyhedron. We denote W- the set of extreme points of W. For a given context x R$t we denote for every 0 E TRm.
We now present our main generalization result.
Theorem 2. Let B 2 Pi.P. Let l E Imm such that
min wWW NEW>WWW WW (Ra(1))
(0(x)) min dx(x) w
ep (0*) S E. Assume that there exists D 2 0 such that
wEWL
|10*| S D. Under ussumptions 2, and 3, and assuming
AO(I)
if (co(t)) # W else.
H..P* P,, with probability at least 1 8, we have
Assume that for some a >> 0 and y 2 0, for every 0 E RM
1
log A
(000) B B
7
Vt 0, P(O Do (x) S ||]| S
Bw
Notice here that when the hypothesis set H. is decision- misspecified, we have $4. >> Pmin,,. and consequently the term 1 P is bounded. If 7 is (nearly) well vell-specified, choose larger 33 guarantee the generalization bound to be good. This theorem implies that our surrogate loss can generalize when n is large and hence minimizing the empirical version of the surrogate loss fP, yields small optimality gap for its out-of-sample counterpart 6% Using Theorem 1 and Theorem 2. we can deduce that finding 0 such that (x) # O almost surely and minimizing e yields optimal value for (()
The assumption above ensures the stability of the target loss tp. Specifically, it strengthens the uniqueness guar- antee provided by Assumption 1. Besides ensuring that min 6ه(x)) T w has a unique solution almost surely, it offers sharper measure for how sensitive the mapping w - + (xx) w is deviations from w(C((x)) with high probability. Assumption 5 is reasonable when (x(x) has continuous distribution, since it is equivalent to say that co(x) is likely to have a direction that is not too close to being perpendicular to one of the faces of the polyhedron W-that is, the probability of this direction to be falling within one of the red cones shown in Figures and decays to 0 as the cones get more narrow. More details about this assumption are provided in Appendix A.8.
Theorem 1 ensures that the closer 0 is to optimality for es for well-chosen B E R. the closer it is to optimality for p. When 0 is nearly optimal for Ey. we aim to quantify how close it is to optimality for pp By adopting a stability as- sumption regarding the linear optimization problem, we can establish a more concrete accuracy bound for the solution obtained from the empirical version 08
The following theorem provides a relationship between op- timality gaps of ed (0) and ( when f is bounded away from 0, f.e. there exists u > O such that ||0|| 2 u.
Theorem 3. Under assumptions 2, 3 and 5, there exists a > 0 such that for all 0 E T.' bounded away from 0 and 3 BH.
3.2. Stronger consistency result
For ease of presentation, we make the following assumption from now on:
Ep(0) S 3 + 0080 (
5

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
Landscape properties and smoothing. We take closer look at the structure of our surrogate. We make the following mild assumption.
Assumption 6. The function 0 - čo (2)) is differentiable for every x E RR, and there exists Bt, such that for all 0, 0' E 1 and E R
w00,a)
če (x)
W
[VoCo(z) Vocgr (x)]l - Bz 110 6'11-
(8,
This assumption is sufficient for eg be written as a difference of two convex functions. Specifically, we have the following result:
(x))
Figure 1. Less likely directions for (x) relative to when is polyhedron in I²
Proposition 1. Under assumptions and 6, &p. is a DC (difference of two convex functions) functioon))
The proof of this theorem can be found in Appendix A.12. Assuming that 0 is bounded away from 0 is crucial here, be- cause when 0 = 0, the uniqueness property in Assumption 1 is not guaranteed, and the consistency in Theorem is not satisfied. Similarly, when 0 is close to 0, e exhibits poor behavior, as it approaches the scenario where consistency breaks down. Although Assumption 5 requires W to be a polyhedron, it is possible to consider similar yet reason- able assumption that does not impose this requirement. This alternative leads to stronger consistency inequality (see Appendix A.
The proof of the proposition above (see Appendix 1.1 relies on the fact that under assumptions and 2. gp. and fe are both weakly convex functions, and consequently their difference a difference of convex functions.
We aim find 0 E R \ {0} that minimizes & A natural approach is to identify stationary point of Pp. (i.e., a where the subgradient of Ep, contains O). Despite eg. having a DC structure, it may still be non-smooth, making the task of finding a stationary point challenging. To address this, we introduce smoothed version of pr.
Remark 1. This theorem suggests that to minimize Ep, one should seek an approximate minimizer of Eg for a well-chosen 3 E with |[0]| kept away from zero. By ap- plying Theorem it follows that it suffices to find some 0 E R. such that E (0) is small while ensuring ||0|| re- mains bounded away from zero.
Definition 2. (s-CILO loss) For all X E RT and B z Su.p. we denote gb., gp., and gř. (1,2), let
3 For Pp.
1
M3, (A) == min (o), (0) + || 0113),
deRm
2
1
3.3. Optimizing our surrogate
0 (A) arg min (op, (0) + 2 210 211
BER"
Based theorems 1, 2, and 3, it is sufficient to find 0 E T such that exx is small and 0 is kept bounded away from zero to minimize εp. The empirical surrogate loss ef can be written as:
We define a smooth surrogate to the CILO loss, which we call the S-CILO loss rf. (A) == A,, (A) M3, (A). When there is an ambiguity about the value of B, we denote Op,- =
0%., 8%. = Mp. == MM. M : M
v0 R", (0) = gp. SP. (0),
Following (Sun and Sun, 2021) (proposition 1, page 10), the smooth surrogate above has the following property: for (10jevery stationary point À of r., 07, (A) and 0p,, (A) are 3
where
gr., (0) := -E -EC,
min 60(x)
equal and are stationary points of f7.- Similar to 6% s- (1 (11)CIO satisfies the positivity property and the fact that its Pr. (0) : min B(o,))),,, (co(z) w. (x) ew
NEW
min ar,, eWr,
B(C,Y)P,, (Co(x) Wp,. (x))
minimum value is equal to 0 from C
(12)
We now have way to find stationary point of eg. A practical way to ensure that the iterates of an optimiza- tion algorithm for 4. do not converge to 0 = 0 is to add a constraint ||||| 2 2 where 2 > 0. Since the function - 2 ||@]| can be written as a difference of two con- vex functions, we can find a constrained stationary point to
WP,
P.
The equality in (11) is satisfied because choosing a policy up minimizing E( (z)( T T (z) is equivalent
to choosing (p(x) minimizing (x) (I((x) for every x in k
6

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
8 Pr. (see (Pang et al., 2017) for tractability results for DC constrained minimization).
Definition 3. For a set V in Ikm and element u
R denote -V = {-v, min.ev |/u -|| the L distance between and V.
E Vj and d(u, V)
The DC structure of our surrogate enables us to find sta- tionary point of P, thus allowing us to approximately min- imize the target loss pp. Moreover, as we will demonstrate (see Theorem 4 below), for specific choices of the hypoth- esis set (e.g., a linear hypothesis set), our surrogate has a favorable landscape, meaning that every stationary point of Pp. is a global minimum. Consequently, first-order opti- mization algorithms can effectively find a global minimum of our surrogate.
Proposition 2. Let X E 12 and 3 2 Ph. we denote
Vr. = { (B(re) (QT(x)wp, (I)) Wp. E W V Pr == [REE ( (x)wr, (x)) wp. E W Pa
Pr can be rewritten as
r (2)
(2) = 2
2 (d(A,
d(2, VVr.)))
From now on, we assume that our hypothesis set H is lin- ear, meaning there exists a mapping Φ : IR* - R.xxd such that for all f R co(x)) (x))0. In this see- nario, Assumption 4 is satisfied if (xx) is full rank almost surely. Additionally, Assumption 6 is inherently satisfied, and Assumption 3 can be replaced with the following:
The proof of this proposition can be found in Appendix 1.
We observe that rr. exhibits an interesting property: re- covering candidate solution 0 R that is equal to zero is equivalent to finding À E RT such that a(A,-V%% P..) -VA.)V = O, and hence, we would like to find a near sta- tionary point for rpp such that these distances are non zero In order to do that, we introduce the following log-barrier surrogate.
Assumption 7. For any x, the largest singular value of (x) is bounded above by Bą.
With this special choice of hypothesis set, our surrogate loss and its smoothed version enjoy good landscape proper- ties. In particular, every stationary point of e is a global minimum. We formulate our main landscape result.
Definition 4. (log-CILO loss) Let B 2 37.P we define for every E R
8 is everywhere differentiable. If X is a sta- Theorem 4. Tpp tionary point of r'. such that Cor, (2) (x)(2) + 0 almost surely,
-V SP. (A) log d(>, -V p..) - -lo d(A, - Vv,)). (13)
We call this function the log-CIL.O loss.
then oy,, (A) is a global minimum of e In particular, un- der assumptions 2 and 3, we have for every 0 E 1.mh and E 220 0,
The function fP, inherits the properties we previously observed in r... Specifically, since d(A,-V
d(A, Vv,,) for every À E R (due to the fact that V C Vy.,), and because the logarithm is non-decraasing func- tion, we have fP. (A) 2 for every 1R Furthermore. to 9 similar to r'p if X is a minimizer of fp. then the distances d(A, d(A,-VPP)) p.) and d(>, vv,,) are equal. Additionally, can be shown that any stationary point of fi, is also stationary point of r?, (see Theorem 6).
Vr === P. (0) < 8Bw B&E
A more complete version of this theorem along with its proof is provided in Appendix A.13. Assuming a priori that running gradient descent to optimize our smooth surrogate, do not fall into the case (1) 0 almost surely, our practical procedure optimize E simply consists of finding a suitable 3 using line search and run gradient descent P..
If gradient descent is used to optimize rf, and subse- quence of the iterates converges outside the set Vv. (and hence outside - -V P. as well), we can recover from the limit of this sequence a e R that is bounded away from zero and serves as a minimizer of e² As a result, by Theorems and 3, we successfully obtain a desirable approximate minimizer of Ep. However, if every limit point of the gra- dient descent iterates converges within the sets -Vp, and -V,, the function fp. can be used instead. Gradient de- scent applied to fPP will not yield iterates converging inside the sets -Vp, and- -Vž. due to the presence of log barriers. The following proposition outlines the possible outcomes when running gradient descent on fP..-
Now, the only remaining problem to address is the case where the algorithm gives O.
Avoiding zero solutions. Even if we successfully mini- mize 6 we could encounter the pathological case where 0 0, which would fail to ensure that ca(x) # 0 almost surely. In this situation, the conditions for Theorems 1 and 3 would not be satisfied. To prevent this, we leverage the linear structure of the hypothesis set. We begin by stating a proposition that highlights key properties of our surrogate when the hypothesis set is linear.
7

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
approach
SPD+
A
1000
VP
P
Out sample regret
600
Figure 2. Construction of X: when À is close to the sets Vi,, and Vr., we construct new approximately stationary point by moving away from Vp, orthogonally to its boundary.
400
200
Proposition 3. Consider the backtracking line search gra- dient descent method applied to the function J'..- ensuring sufficient decrease at each iteration (refer to Algorithm 3. in (Nocedal and Wright, 1999)). Suppose the gradient de- scent sequence has least one limit point. There are two possible cases:
5-5
s=31
5-63
s=127
s-255
s-511
dimbx)-5
dimix--5
dim(x)-6
dim(x)-
dimix--8
dim(x-9
the ground dim(k): context
Figure 3. Comparison of SPO+, SLO, and our approach compari- son for different levels of misspecification
1. The limit point lies strictly outside the interior of - Vp. or
-VP Pa
compare our method with SPO+ and SLO in misspecified setting.
2. The limit point lies on the common boundary of Vp..
and V.. P..
We write the ground truth cost c(x) 6* (xx) for some matrix 8* 20xx and for all R where Φ(xx) R Furthermore, the predictors in the hypothesis set take the form co(x:) = (z)(z) for any 0 E R220x and for all ar E R where Φ(x) E IR$ is equal to 6(x) truncated to its first 5 co- ordinates. When
The proof of this proposition is provided in Appendix A.17. If the gradient sequence {>x } converges to the common boundary of Vv, and -V the corresponding sequence (0 (A,,)} approaches zero, which is not a desirable so- lution. Fortunately, this issue can addressed. Since the sequence converges
5, the hypothesis set is well-specified, and when 8 grows, the misspecification level of the hypoth- esis set grows as well. In this setting, the hypothesis set is linear (see Appendix A.18 for more details). To optimize P., we ran gradient descent its surrogate loss rp, (we did not need to optimize the surrogate / because the it- erates did not converge to 0). We chose ,3 by line search. We used Bmin, = ((a,,))=P (c" w(()) as a lower bound to B, and ASPO+ = [..,c)),, (c (Cugpor (sr)) where OSPO+ is the solution obtained by optimizing the SPO+ loss. For every value of s, we tested 96 evenly spaced values of in the interval [Smin,P; Sspo+] and picked yielding the solution with the best decision performance. The optimal 3 is likely to fall into (or near) the interval [Sminn BsPo.). and hence for at least one of the values of 3 that we test, & enjoys good optimality guarantees, which ensures that the solution obtain yields small value for lp. For every value of 8, we run 96 experiments to get the distribution of the testing loss P for every method, and get results in the box plots in Figure 3. We also include the same plot with relative regret instead of absolute regret in Appendix D.
limit point on the boundary of Vvr, and -VP. p. which is also stationary point of r/., there must exist some λi, such that is an e-stationary point of 8 rp. We then move Ao orthogonally away from the boundary of Vvp (see Figure 5). This yields new approx- imate stationary point that is sufficiently distant from both VV. and -VP. As a result, the corresponding 0 is an approximate global minimizer of ef that is bounded away from zero.
Theorem 6 in Appendix A. 16 provides an overview of this procedure, as well as a relationship between the optimality for f and rr.-
4. Computational experiments
We make similar comparison to the one performed by (Hu et al., 2022). In their work, SLO is compared to SPO+, showing that when the hypothesis set is well-specifted, SLO achieves a smaller value lp than SPO+. Conversely, when the model is misspecified, SPO+ performs better. Here, we
In Figure 3, we plot the regret yielded by SLO, SPO+ and our approach, i.c. the value of (7( = (p()) - 8mmn.P 2 0. We observe that in the well-specified setting (s = 5), SL.
8

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
performs best among the other methods, whereas in the misspecified setting (s 5), the more the misspecification level grows, the more method performs better than SLO and SPO+, and SLO performs the worst. This is coherent with results in (Hu et al., 2022) and (Elmachtoub et al., 2023) in one hand, but also with our consistency and generalization results in the other hand (Theorems and 2).
5. Conclusion
This paper presents novel approach to addressing model misspecification in contextual optimization. State-of-the-ar methods optimize the decision cost effectively only when the hypothesis set well-specified, leaving the misspecified case largely unresolved. Our surrogate loss function success- fully optimizes the decision cost and retrieves good cost predictor in terms of decision performance from the hypoth- esis set in reasonable time. Despite its non-convexity and non-smoothness, we exploit its structure as a difference of convex functions, enabling optimization through smoothing. We theoretically and experimentally demonstrate that our ap- proach outperforms state-of-tt of-the-art methods in misspecified settings. To our knowledge, this is the first approach to prov- ably optimize the decision cost Ep under misspecification. While almost all of our results only require generic bound- edness and smoothness assumptions, global optimality for our surrogate loss holds for linear hypothesis sets, although we believe extends to broader class of predictors and contextual optimization problems beyond the case where the objective optimize is linear. We have validated our method synthetic data and plan further experiments real-world datasets for comparison with existing methods.
Impact Statement
This paper introduces a tractable method for contextual op- timization under model misspecification, with theoretical guarantees and improved decision performance. The con- tribution is purely methodological; do not anticipate any broader societal or ethical impact beyond this technical advance.
Acknowledgements
This work has been partly funded by AFOSR grant FA9550- 19-1-0263. The author Jiawei Zhang is supported by MIT postdoe fellowship for engineering excellences. All com- putational experiments were run on the MIT SuperCloud (Reuther et al., 2018).

---

Contextual Optimization Under Model Misspccification: A Tractable and Generalizable Approach
References
Nocedal, and Wright, S. J. (1999). Numerical optimization. Springer.
Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z. (2019). Differentiable convex optimization layers. Advances in neural information processing systems, 32.
Pang. J.S.,, Razaviyayn, M., and Alvarado, A. (2017). Computing b-stationary points of nonsmooth de programs. Mathematics of Operations Research, 42(1):95-113 118.
Amos, and Kolter. J. Z. (2017). Optnet: Differentiable opti- mization as layer in neural networks. In International Conference on Machine Learning, pages 136-145. PMLR.
Reuther, A., Kepner, J., Byun, C., Samsi, S., Areand, W., Bestor,
D., Bergeron, B., Gadepally, V., Houle, M., Hubbell, M., Jones, M., Klein, A., Milechin, L., Mullen, J., Prout, A.. Rosa, A., Yee, C., and Michaleas, P. (2018). Interactive supercomputing 40,000 cores for machine learning and data analysis. In 2018 IEEE High Performance extreme Computing Conference (HPEC), page 1 1-6, IEEE
Bertsimas. D. and Kallus, N. (2020). From predictive to prescrip- tive analyties. Management Science, 66(3):1025-104:
Domke, J. (2012). Generic methods for optimization- based model- ing. In Artificial Intelligence and Statistics, pages 318-326.
Sadana, U., Chenreddy, A.. Delage, E.,, Forel, A., Frejinger, E., and Vidal, T. (2024). A survey of contextual optimization methods for decision dccision-making under uncertainty. European Journal of Operational Research.
PMLR.
Donti, P., Amos, B., and Kolter, J. Z. 20. Task-based end-to-
end model learning in stochastic optimization. Advances in neural information processing systems, 30.
Sun, C., Liu, S., and Li, X. (2023). Maximum optimality margin: A unified approach for contextual linear programaming and inverse linear programming. In International Conference on Machine Learning, pages 22886-32912 PMLR.
Elmachtoub, A. N. and Grigas, P. (2022). Smart "predict, then optimize". Management Science, 68( 1):9-26.
Elmachtoub. A. N., Lam, H., Zhang, H., and Zhao, Y. (2023). Estimate-then-oopiinzz versus integrated- cetimation-otimmizaiin A stochastic dominance perspee- tive. arXiv preprint arXiv:2304.06: 06833.
Sun, H., Shi, Y., Wang, J., Tuan, H. D., Poor, H. V., and Tao, (2022). Alternating diffcrentiation for optimization layers. arXiv preprint arXiv:2210.018022
Foster, D. J., Gentile, C., Mohri, M., and Zimmert, J. (2020). Adapting to misspecification in contextual ban- dits. Advances Neural Information Processing Systems, 13:81478-1
Sun, K. and Sun, X. A. (2021). Algorithms for difference- of-convex (dc) programs based on difference-of-monn mo-morauu-- envelopes smoothing. arXiv e-prints, pages arXiv-2144 2104.
Tang, B. and Khalil, F. B. (2024). Pyepo: A pytorch-based end- to-end prenpiittee library for linear and integer programming. Mathematical Programming Computation, 16(3):297-335.
Hu, Y., Kallus, N., and Mao, X. (2022). Fast rates for contextual lin- ear optimization. Management Science, (8(6):4436-42453
Huang. M. and Gupta, V. (2024). Learning best-in-class policies for the
framework. arXiv preprint
Wainwright, M. J. (2019). High- digh-ddimensioal statistics: A non- asymptotic viewpoint, volume 48. Cambridge university press.
arXiv:2402.03256.
Jeong. J., Jaggi. P., Butler, A., and Sanner, S. (2022), An exact sym- bolic reduction of linear smart predict+ optimize to mixed integer linear programming. In International Conference on Machine Learning, pages 10053-10067. PMLR.
Kallus, N. and Mao. X. (2023). Stochastic optimization forests. Management Science, 69(4):1975 19944.
Kotary, J. Dinh, M. H., and Fioretto, F. (2023). Backpropagation of unrolled solvers with folded optimization. arXiv preprint aiv: /2047.
Krishnamurthy, S. K.. Hadad, V., and Athey, S. (2021). Adapt- ing to misspecification in contextual bandits with offline regression oracles. In International Conference on Machine Learning, pages 5805 5814. PMLR.
Liu, M., Qi, M., and Shen, Z.-J. M. (2021). End-to-end deep lcarning for automatic inventory management with fixed ordering cost. Available at SSRN 3888897.
Loke, G. G., Tang, Q. and Xiao, Y. (2022). Decision-driven regularization: A blended model for mredicttthen-opinng Available at SSRN 3623006.
McKenzie, D., Fung, S. W., and Hcaton, H. (2023). Faster predict- and-optimize with three-operator splitting. arXiv preprint arXiv:2301. 13395.
Mityagin, B. (2015). The zero set a real analytic function. arXiv preprint arXiv:1512.07277
Monga, V., Li, Y., and Eldar, Y. C. (2021). Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Processing Magazine, 38(2):18- 44.
10

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
A. Appendix
A.1. More details about Example
For any predictor é, we use the following abuse notation
(p(c) (a..))>P
max C (WEW"((x))
espo= B(z,o)a
max - w((c)))
WEW
(c) = V Blaoo (le-((x))())
Notice that whereas (x( = - and (((2)) = 0 (r(t), we have (G) = 20 (P)) = <
(CPO+(C)), (()) = 7 (()) 12 (c)) Although 82 leads to suboptimal decisions while é results in optimal decisions, both SLO and SPO+ appear favor è2.
A.2. Equivalence of the target loss in binary classification
Proof. For every è R - Rd, we denote
(p(C) ((ze))
min (EW"(((a))
cTw)
We have for every è: R - Rd. for every x E R if sign(((z)) = c, then (é(x)) W*(c) = {c/2). Consequently. we have win (d(o)) c w 2- If sign((())) # c, then mat)) e Consequently, we have for any
x E R
( if sign(c(x))
min =E(*()(s)
0 else.
This directly gives
((( (a (Li)g((((=))= 1
A.3. Previous approaches to Integrated Learning and Optimization
A more comprehensive review of contextual optimization approaches can be found in the survey by (Sadana al., 2024).
Directly optimizing the target loss. One of the first instances of the ILO method can be traced back to (Donti et al., 2017) who provide a practical way to differentiate the target loss Ep under some regularity conditions. Similarly, others have attempted to directly minimize f using some estimation of its gradient, such as unrolling (Domke, 2012; Monga et al., 2021), which consists of keeping track of operations while rumning gradient descent in order to differentiate the final gradient descent iterate as function of the model parameters, and implicit differentiation (Amos and Kolter, 2017; Agrawal al., 2019; Sun et al., 2022: McKenzie al., 2023). However, tp non-differentiable in general, and even if it were, there guarantee that it would be convex. This implies that gradient- gradient-based algorithms mentioned above do not guarantee convergence to optimum of the target loss. In contrast, our approach consists of minimizing tractable smooth surrogate that has the same set of minimizers as εp. This allows us to avoid the challenge coming from the lack of regularity properties for tp.
Optimizing a surrogate loss. Another increasingly popular approach, which is most relevant to ours, is optimizing the target loss using a smooth convex surrogate loss. In (Elmachtoub and Grigas, 2022), a new convex surrogate function, named SPO+. Minimizing SPO+ proven to also minimize the target loss when the hypothesis set is well-specified, but no

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
consistency results are provided when the chosen predictor class is misspecified. Furthermore, SPO+ seems to outperform SLO (i.e. yield better decision performance) when H. is misspecified,, since SLO only focuses the accuracy of the prediction step, but completely disregards the performance in the optimization step, whereas ILO specifically focuses on the decision performance, and when the hypothesis set is misspecified, maximizing the prediction accuracy of the underlying cost will not necessarily result in good decision performance. Moreover, when H. is well-specified, SI.O methods outperform ILO (Hu et al., 2022; Elmachtoub and Grigas, 2022). (Hu et al., 2022) give theoretical and experimental evidence showing that classical SLO methods generalize better than SPO+ when the hypothesis set well-specified. In fact, evidence in (Elmachtoub al., 2023) suggests that in the well-specified case, SLO might likely have better performance than ILO approaches, and such a behavior is inverted in the misspecified case. Most previous works have not theoretically considered the misspecified case. In (Huang and Gupta, 2024), new surrogate is introduced based an approximation of the directional derivative of Ep, and is shown to be theoretically consistent with tp. However, only local optimality results are provided for this surrogate, whereas in our work, we provide global optimality guarantees.
Another alternative is the surrogate introduced by (Sun et al., 2023), which attempts to maximize the nonbasic reduced costs (when the cost taken equal to the predicted cost) of past realizations of ground truth optimal decisions. Such a method does not require the knowledge of historical costs, but only solutions of previously seen linear programs. In order for this surrogate to be consistent, authors assume that the chosen hypothesis set is well-specified in the sense of our definition, i.e. Tax (7)) = 0. On one hand, this assumption is weaker than the usual definition of well-specification, which requires that the hypothesis set contains the ground truth predictor. On the other hand, this surrogate is only designed for linear objectives with linear constraints. Our surrogate only requires the set of feasible decisions W to be convex and bounded. In a related paper, (Liu et al., 2021) use a neural network structure in an inventory management problem to learn a mapping which provides the optimal merchandise order quantity and order time, and give theoretical guarantees in the well-specified setting. Other surrogates have been considered in the literature (Loke et al., 2022; Jeong et al., 2022; Kallus and Mao, 2023), which despite having good practical performance benefits, do not seem to theoretically tackle the misspecified case opposed to our work, though practical toolkits such as PyEPO (Tang and Khalil, 2024) provide implementations of some of these approaches.
A.4. Predicition misspecification and decision misspecification
In the litterature, classical metric to quantify the level of prediction misspecification of given hypothesis set H. is the L or 2 norm of the distance between the parameter (or the function) one seeks to estimate and the chosen hypothesis set. In our setting, it can be written as
Vireed (H)
min GER
(( (((()) ((()))
This metric has been previously adopted in statistics and contextual bandits (Foster et al., 2020), (Krishnamurthy et al., 2021). We argue that (H) can be a good metric for evaluating the effect of misspecification for prediction problems, but not for contextual optimization problems in which parameter estimates enter in downstream optimization problem. This can be seen by noting that in our setting, the best achievable cost should not change when multiplying the elements of H by positive constant, whereas "/ped (H) is not invariant to such transformation. To address this, we introduce new metric to quantify misspecification in contextual optimization.
Definition 5. We define the decision misspecification gap as
Yeeeo ( (H) = -min ((r,))~
max (WW-(((x))
cxx) w) -B
(Eminn
min c(x) T w wEW
GEH
The function class H is decission-well-pperifeel if (Pde)(() = 0, and decisson-misspeccifed otherwise.
First, note that the first term is the smallest possible value of the target loss when choosing a cost predictor from H. and the second term is the smallest possible value of the target loss in the case where H contains the ground truth cost predictor. Hence, it follows to conclude that (H)) captures the optimality gap (in terms of decision performance) caused by model misspecification. Second, notice that if H is decision-misspeciffee
i.e. (Pt) > O, then necessarily it is i.c. (H) > O. Third, 7 (H) is clearly invariant when multiplying the cost predictors by a constant. In Example 1, that we have Ypred (7{) > O but (P)) = O. This means that while SPO+ and SLO are consistent when the hypothesis set is prediction-welle -pecifee,,,,,d, their consistency property no longer holds even when the hypothesis set is well-speeifiedd in general.
12

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
For given cost predictor é, denoting " (c) P ((e(x) c² w) E (min c w) and Ypred (c)
v B( ((θ(z) )( we can see that SLO focuses on bringing (pe)(() as close as possible to Tipred (H), whereas more natural to focus on bringing "Itee (c) as close to (aa)(H) as possible, since small prediction error does not necessarily
mean good decision performance in the misspecified case. In the other hand, even current ILO methods such as SPO+ aim
to bring (c) as close to "idec (H), it is unclear whether they can do so in the misspecified case, whereas surrogate loss's optimality gap dominates Tiee (c) (see Theorem 3).
A.5. Sufficient condition for uniqueness assumption to hold when W is polyhedron
Proposition 4. If the context variable has continuous probability distribution and the mapping - (x(x)) is nonzero analytic function for any 0 + O, then Assumption 1 holds for any polyhedron W that satisfies čy (a(x)) + 0 for any {0} and any nonzero E W.
0 E II
Proof. Let {Si)ier be all the faces of W, where is a finite index set. Let or an arbitrary tangent direction of St and let V
her be a finite set. Let U be the set containing all such that the solution to the linear program
min u w, u E U is not unique, Then any U satisfies 02 0 for some Therefore, čœ cœ(x) E U if (x()) T2, = O (o 2, 0}. We have Xu S Usez X,. By the assumption in the Proposition, (x(x) U is nonzero analytic function and then by (Mityagin, 2015). X; is a zero- sero-measure set. Therefore, Xo = User X, is zero-measure set since I is finite. Finally, since Xo is of measure zero and is continuous random variable, x lies outside of Xo almost surely, i.c. the solution min 0g(x)) w is unique almost surely.
for some i. Let Xa {i E R (o(x)) U} and X; == {i R* c)(x))
A.6. Proof of Proposition 2.1
In the binary classification setting, when H. is decision- wesoon-welllsype seel-spe,,fied, we have 34. =-3 PH.
-1. For any é: R² Rd, when
(G()) = max E (a (o(x) wz((a) + max whEW?
wPEWr E(x,)) (6(x) . wp(x))
max Bere (ow))())))) BleeN (((x) wf((o)) B (l((z)))
SnEWp
- B (0(z).c) 2 ((
1
1
1
2 Blroo (l((z) (1- sign(((x)) -ignnlt))))) ) c))
E (l0(x) L=ign(((=))
A.7. Proof of Theorem 1
p Proof. We denote 3h.P min EP))), Smax, p P( (max c_ cTw), and Smin, E(z (min c_ w). Let 3 E R. We first study the property (0) < 3 when 3 satisfies Pi. B < Amax, and (x) # 0 almost surely. The inequality 3H, I B ensures that the condition (0) < B is feasible, and the inequality / < Smmss P ensures that the condition (0( S 3 is not trivial. Notice that if we take 3 = Bi, p. any E RdM satisfying ( < 3 is a minimizer of (P))). When Assumption holds, and when (x) * almost surely, W (c)((x) contains only one element for almost every x. Hence, we denote (x)( to be the unique solution in W (c)())) when W (&p())) contains only one element. The condition (() < 33 can be rewritten as p(z,))p(cc (x)((x))) S when (x( A almost surely. For given 0 E m and wp Wp. p, if wp satisfies
((p()))))()))(())) Wp E Erg min ((r,)))((((()) wr(x)), wpEWp
(14)
then we have, w>((x)= = w((n(z) (x)) almost surely, as for each x, the unique minimizer of co(x) w over w E W is given by w (x)), according to Assumption 1.
If E R satisfies éP(0) < B, and wp is the measurable mapping satisfying condition (14) (and hence wp(x) = wo( (()())) almost surely), then we have [( (c wp (x)) S B. This suggests that adding the linear constraint
13

---

Contextual Optimization Under Model Misspecification; A Tractable and Generalizable Approach
(e,c) (cTwp up (z)) 3 (14) does not change the of minimizers of wp - ((x.e)<((((()) up(x)) when
Ep(0) S 3. Defining W.. (wp E Wp. (r,,) (c"wp(x)) - 8). our latter statement means that if ( S 5, the two optimization problems
min wpEWp
(( (co(1) T wx(x))
(15)
and
min B( (ca(x) xp(x)) MPEWe
(16)
would result in identical values of the objective function.
Let 3 E I such that $ S B < P and 0 E Ih" satisfying (x) * 0 almost surely. Assume that 0 is optimal for ey.
ie.. (0) = Let Wp(x) be the solution of (16). Then ()) = 0 implies
(x,e)~~ ((o(2)]wp((a) wp(() - (x(2)) w (Co(x))) = 0.
Since the random variable éo (2: Tr(x) - (o(x)) T w (R)(x)) is positive almost surely, the equality above implies that éø (x) T> (2:) (c)( = 0 almost surely, i.e. Wp is also minimizer of wp + B(a.)) (Co(x) ((o(x))T<(())) wp(x)), and hence under Assumption 1, we have wr(z)= w((o(())) almost surely. This finally gives
(p) B(z.)prcc (cx(x))) = E( ((mp))(((((()))) Tp(x)) s 8.
A.8. More details about Assumption
We first mention the assumption in (Hu et al., 2022) which enables the authors to get good generalization guarantees for SLO in the well-specified case. Note that we will not be making this assumption, but mention it just for reference.
Assumption Assume that W a polyhedron. We denote W 4 the set of extreme points of W. For given context R
we denote
min c(x)Tw w min dx)TT w ((()(( # w
Axx)
0
else.
Assume that for some a, 7 2 O.
Vt > 0, P(O < A(x)
<t) <
Bw
We provide further justification of the remarks following Assumption 5. When W is a polyhedron, denoting for 0 + 0. w00,x)) x)) arg min ( (=)(((=))) (x) T ww, and
(w(())((( w(Co(x)
cos (w) [(((x)] |m000, 2x)
Assumption 5 can be rewritten as
7 Bw
P (I1és(x)) [[((0, (w(((==))rll (O, x)) < 10]1 <
(17)
We do not need focus the term [lw(0, w((o(z)) it is both upper bounded and bounded away from zero Therefore, inequality (17) is equivalent to (a) having norm that is bounded away from zero with high probability, and an angle (0, .r) that is bounded away from when 0 is bounded away from 0. In other words, (o(x) is likely to have a direction that is not too close to being perpendicular to one of the faces of the polyhedron W. other words, the probability of this direction to be falling within one the red cones shown Figure and 4 decays to as the cones get more narrow. When do (x) follows a continuous distribution, such a property on the direction of (x(x)) is reasonable.
14

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
The key idea of the proof of Theorem 3 relies on the following sensitivity inequality resulting from Assumption 5 which holds for every t 2 0 and mapping w Wp:
E PP (1ox(x) T w(Co(z)) - (x) (()))) 2 t.A1 ||@]| [(.,)) (I)w((o(()) - w(=)ll) A2 [[0]] to;
where A1, A2 are positive constants. The left-hand side equals (0) for well-chosen w E Wr, while the right-hand side is directly related to (0( B. Optimizing over ł in the right-hand side yields the desired inequality. By omitting the term Ag f0 and the dependence of the right-hand side on t, it is possible to obtain a stronger bound that does not require W to a polyhderon. Specifically, we assume the existence of Bg > such that for every E R and every mapping w E Wp.
PP (1oo(x) T (x(((())) (x)x) wx())) 2 B. |10|| (a (l)x((o(()) w(z)ll),
(18)
the bound Ep( S 8 +-+0 0 e
(%)))) holds when ||0|| is bounded away from O. This bound is stronger since 1 - I+x
< 1 for
every a and does not require W to be a polyhedron. This assumption is also reasonable when P is continuous.
A.9. Proof of Theorem 2
Proef. We proceed in two steps.
Step 1. We first prove the Lipschitz continuity of the generalization, i.e. that there exists constant A 2 such that for every 0, 0' E R
(0) (0) (7( -0) s Al10 0'1
(19)
For every 0 E IR",, using Lagrangian duality,
P. (0) (0)= min B(e,))~PP (co(0) T w/ (2r) wP, EWA.
min
B( (2o(2)) T "r,, (x))
(20)
Wr, eW
pn
min max (aa,))PP (co())TTT,,) (x) + y (Bea.Owe (ctx) wx,, (x)) - 3)
(21)
wp, EWn, V2U
min "lp, "P,,We, EWP,
B, (6o(x) (o((=)Tpp,,(') (x))
(22)
max min P (106(z) + ((6o(z)+ vc(x)) T w. (1t) yB min wp, EWP. B(s.o)~P, (colx)] wp, wp,(x))
(z))
(23)
920 wr EWr,
In (23), we have switched the min and the max because of strong duality, since the objective function we are optimizing is linear. For a given 0 E RT, we denote y (0) to be the optimal dual variable corresponding to 0 in the minimization problem
above. Let 0, 8' E R. and D 2 max([10]] (1). We have
(0) (0) (e (0') (0')
e((0)) -(0)))(((0))))
()) (r, (0') +
+
(
We now bound the two terms above on the right side of the inequality. We have
(G. (0)
69 (0')
max min y20 wat EWP,
B(e,e)~P (100(x)) + yc(x)) T w (1)) - y
min
B(e,o) (co(1) T wp, (2))
wp,, EWP
max min 220 wi EWP,
BLECNNP (() yc(x)) T T (x)) -13-
min
Eiec (cw(x) T wp, (x))
wp, EWP.
Biz,,)yP ((o((z) + y" (0)c(z)) TP (x)) (0)
min T.p EWP.
min up, EWP
B(,,)) (co(x) wr, (x))
Fl (())(z)) + (0 (())) w (x))
min
wh, EWP,
Bia.ere (x) up, (x))
(0')8
min wp, EWr,
15

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
In the left hand side of the inequality above, we can that if Cg (0) 2 &pp (0)), then replacing y" (0") by y (0) gives larger term than the one above, and when ér, (0) < p. (0'), replacing y (0) by y" (0") gives larger term than the one above as well. Let ÿ E (0), y" } such that replacing (d) and y0") by ū makes the expression above larger. We
have, by replacing y" (0) and y" (0") by y in the inequality above, we get
2r (0) Eg (0))
min
B(ere)pP (16o(z)) (c(x)) T wP (o)
min B(xe) (0o(1) wr, (x))
w eWn,
wP, EWp,
min
Bix,) (c)) jj(())) + jc(x)) w) min (+o(x))(((x))
Tp. (0)
min EWr,
B( (Cor (x) up, (x))
ppp EWPn
((r,))
E (((se)
min co(z) T
NEW
NEW
B(
min (Co (x) + 5e(x)) (c))) w wEW
+ (a
min Ger (xx w NEW
1fg.Pr. (0) So.P.. (f')
where for every 0 E Rm
(0..0))))) (co(1) + 5e(x))
h2(0,
(0) Beacerp
min wEW
w) Bie,eee
min (0(r)) w wEW
W is a convex bounded set, and for all E R and the two functions E Rd 0 + h1 w. 0 + h2 x) are both differentiable with respect to 0. Moreover, 8h1 - Vêo(1) w and 0h2 + (co(z) w (where (éo(z) is the jacobian of 0 - (a))) at 0) are both continuous with respect to w for all 0 E Ih" and E R*. Hence, using Danskin's 's theorem, we can say that for all x E IR h (0, x) min / w.æ) and (2) = min h2 (0, r) are both subdifferentiable, and that for all 0 E R", (0, x) = conv[Véo(a (02(0, x)- = conv (V)v(V)g( T w, w E arg min ho20,, w.x)) ))). These two sets are bounded by Bw Bg because of Assumption 3. This means that the two functions in the equality above are both Bw B& lipschitz, which makes fg. BB B& lipschitz.
80
w. w E arg min hz(0, w. x)},
We can also easily prove that the inequality above is also true when replace Pa. by P. Hence, we can deduce that
( (0) - (e2, (0') (0%)(0)) - ((((0)
S e (0) er, (0) +0) - {
< fp (0) - fy (0))++1fa.P(0 fv.)(0))
< 4B Bo ||0 811,
which yields the desired result of step 1.
Step 2. We will now prove the desired generalization bound by bounding the generalization gap locally in balls covering the set which represents the possible values of 0*_ Let B be set of balls of radius 7 > 0 (for the norm [|-I]) such that UBES B =
Bj|,I( (0, D). According to (Wainwright, 2019), it is possible to choose B such that log [B] S dllo (1+ 2D For every
B E 18, let On be an element of B. For a given e >> 0 we would like to bound the probability PP ((ef.
cr (0) e,,00) > 5)
16

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
using Hoeffding's 's inequality. In order to do that, first notice that using Lagrangian duality, we get (0) p.p (0) v20 TpeWp max min B(z,c)ur ((6)(z) + yo(x)) up(x)) yB + yc(x))
min wrEWr B(x,))rr (co(x) (co(x)]pp(x)) wp(x))
max min B(x,o)ur, ((oolz)+
10,, E.P, wpe (x)) y8
min B(r,)),, (Co(x) wr, (x))
v2o Ty EWo,
min B(E,)) + ( T vp((t)) 12(()8 min wrEWr
B(,,))~ (Co(x) w
BPEWP
EWp, min B( (60o(2)+ + up. (0)c(z)) Tp. (1) UPP (0)
Bi (co( wp,, (z)) (z))
min "P, eWp,
where (0) and yp,, (0) are respectively optimal dual variables in the bottom and top line above. As we have seen before, replacing vi. (0) by (0) makes the above term larger. Hence, we have
(e( ctt (0) s
min [(r,))~ ((6)(() + vb((0c(x)) T)(())-
min wnEWn
Eix,c)< (Bo(#)]wp(xt) wp(x))
min
Bi ((0((z)+ + (00())(()) TP (x))
min EWP.
B(,,)) (co(x) T wp, (x))
pr EWPn
(a.c)~p
min (Co(x) + (}=())(())) w
min (x) w NEW
NEW
min (co(x) (²)(((())) w WEW
min 80(x)) Tww weW
F (6)
Hence, we have P (0)
e the term on the right given that we bound the random variable
(0) E) < IP
(1) P. (0) > e). This enables us to apply Hoeffding's 's inequality to
m(a, 0) = min (c)(x) + (0)c(z) min
c0(x)) T w. wEW
weW
is easy to see that using Cauchy-Sehwarre inequality, we have
|m(x, 0)1 S (1()(())) + (0) Bw + ( Bw
In order to upper bound the right-hand side, we need to upper bound (f). order to do this, we prove that the Lagrange multiplier (f) bounded for any 0 E R. Indeed, we have
min E(x.c))((G(()) ((p()) < min max ((.)))(((((() (p(())) + (E (<(p)) wp(x)) - 3) (24)
()(x))
wpWWp
wPEWe 920 = min ((n,)))((G(())) (()(((()TT(())))))) uPEWe
wp(x)) (0) (O) T wr(x)) - B) (25)
< ((r.e))((((( (w(c(=))) + (00 w(c(x))) - 3).
(26)
Inequality (24) holds because the left-hand side is the evaluation of the right-hand side at O. Hence,
min ((xx))(((((x)) wP(()) wpEWp
< ((a.c))((s(()) (wp()) w(c(x))) + (0) (E..)))) w(c(x))) - 33)
= -Ger w(c(x))) + (0) 3).
This yields
(0) ((z,)))(((((z)) (w((xx)) - ((ao)) ((((())) 2DBw B
3 - Boin.
3 - Bmin,
17

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
Hence, we get the following upper bound for the random variables we working with
2DBw B$ = U
[m(2, 0)l < 2DBw B& + K KBw
B Pmin,
we can apply Hoeffding's inequality, and say that
P (Ep(0) - (0)
(0) > E 2e
=i 20
This yields
IP
sup BEB
T (p(0))
Ep. (0n) = S | 2e
20
By denoting 8 = [ 2e. 202, we can say that with probability at least
we have
log [B]
+
log
YB E B, 1g(8g) E.p. (0B) S SU2
n
which gives
VB B, (g)))) eg_ (0B) s LU2 log [ + log x
dlog 1 2D
log
S SU22
Now we have for every 8 E B (0, D) denoting B E such that E B,
( e (0) S (0g)) - ep. (0B) + P. (0) - ef( (e) (0z) (00)) eZ
(27)
dlog 1 + 2D
+ log
S SUV2
+ 4Bw Ba 110 0
(28)
(1
dlog
+ +lg
7
SUV2
+ 4B Bay.
(29)
Incquality (29) is resulting from the Lipschitz inequality (19). Taking 7 =0
(v (Voes
log
get
log
- (0) 50 (U (U+ +7+4BB 4Bw B&)
n
Since we have ef (0*) S e, we can replace in the inequality above 0 by 0* and get
log 1
log 1 8
(0(00) pp (0') +0 (U (U+4BwBo)
< 5
3
Buin,
A0 Proof of Lemma
Proof. Since the only difference between the right and left optimization problems in ep. is an additional constraint added to the right problem, is clear that it will yield higher value than the right one for any E IR",, and consequently we have that indeed &e is positive.
18

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
A.11. Proof of Proposition 1
Proof. We denote for every w E W and 0 E IR",, f00
-c)(())) w. We want prove that for every E W. f(0; w) is weakly convex. More precisely, want to prove that there exists 2 such that for every w W, f(0;w) w) + a |10] convex. We have for every 01, B2 E I using assumptions and 2,
0
[V((1: - (0)0;;10) = (Véo, (x) - Vćo, (1)) w
I Bw || Vêe, (4) Vêe, (z)
I Bw BL |10 - 0221-
We denote for every 0 R and w E W, h(0:w) = f(0; w) + 2Bw By |101 We have for every 0,, 82 E R",
(Vh(O);w) vh(02;w))T(01
02) (Vf(Oi;w) V (02; 02) 2Bw Br, |2 y11
2 [Vf(01: - vf(02; w|ll ||0 8211 - 2Bw BL 1|0 0-l
2 Bw BL |0: 02ll + 2BW By ||0 021
Bw B2 110 02l1² 2 0.
Hence, for every w E W, 0 + h(0; w) convex. This implies that for any measurable mapping w R W. A > ((,,))P,, (h(0; wx))) convex. Consequently, 0 m max eWr, (w.,))>, (h(O; w(x))) and 0 max EW", (x,,))>,,, (1(0; (x))) are both maximums of family of convex functions, and hence are also convex functions. Finally we have for every 0 R"
max WP, EWP, ((,,)) (h(0: (h(0: w(x))) (P, 2B ||011
max [(r,,)-P,, ((()) = Jr. (0) + 2B, 1101?
eW Pm
Finally, write for every E R
eg (0) - (0) 2B,
-
(0% (0) 100/2(000000 2Br 1101²)
which is indeed a difference of convex functions.
A.12. Proof of Theorem
Proof. Let I and /. 0. Assumption gives
76
P(O < Ao(z) - t1 <
B
where
min mw TT(x)T w min we (Z) w
if W (co(x)) # W
A)(x)=
0
else.
19

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
We have for 0 + O, denoting W-= W.N.
(02 - (0(x)) (oo))w(err w(Co(x)) > ||01| t (0(x) > |10|| t = Vwzz E W< \ foo(Eo)), Ro(x) w2
Vwz W- (vo(Co)) (x(x) wz - -o()) w((((=)) 11011 [lw((((x))) - w
2Bw
VAi,..... An 2 0ss. A1 + +... + 1, 1,
N
de (Bo(x) wi -o(2) T (((o(z)))
1
|10| t
Σ
[lo(C((=)) will
2Bw
VAI...., An 2 O.s ................................ + An 1,
N
(0)
Xwu; - co(z) [](c(=)))= > 2Bw
| w((o(z))
Σ
X
==1
1
Vw E W, co(x) w c0(2) (()((x))
|10| [()(
wll
2Bw
Hence, we have
|0|| [[((((())) - w|l t) 2 P(Ao(r)>>N)) 1011 1- -11) (30)
IP Ve E W, Co(x) T w (a( T (c(a(x))) >
2Bw
We denote for w E W, t 2 0, and 0 E R² \ {0}.
1
G = (z) w - (((=))=(((()))
|18|| [[((Co())) -wllt
2Bw
and the event A(x, 0) defined by Hence, we have for every mapping w R² - w and E Rm {0).
A(x, 0, = (tw W, G(x, 0, w(x), 0}.
E(,,))r(G(zz 0, w(x), t)) = EEz,)) 0, w(x), 6) () + (axo
2 P()x)) ((r),, A(.,..0))
Furthermore, we have for every w E W
|G(z, w. t)1 = [o(()) ( (o(x)=)((((x))) 1
2Bw ||||| [(((((())) wll
< Bw |10| + Bo Bw ||0|| + ||0|| L = ||0|| (2Bw Bo + ()-
Notice that (30) can be rewritten PP (A(z, 0 t)) 1 - ( a Hence, have
E B(z,,)> uz)) 1)) 2 -22B B4 + 1) P(Ax, 0, ()9
78
2 -2BB B& + 1) |10||
B
In conclusion, we have for every t 2 0 and every 0 E RT, and mapping w R W,
1
7t
B( (Bo(x) w(x) - cx) T (()((()))) 2
|||| P (alp:r/((wwweeee ([ - wx))ll) t- (2Bw BB + t) ||@||
2Bw
B
the inequality above is trivially verified when 0. Also, when taking w arg min wEW;, B(x,) (co(x)) (((())(w(())) w(x)), we get
e,(10) 2 2Bw
1 |10|| P (I)((é(())) - w(x) (2 Ba + +1) |1011
7t a
B
||0|| (Cr(0) - 3) - (2Bw Bs + +011
7t)
> 2K Bw
B
20

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
Let > Assume that 0 is bounded away from O. We have
2K 2KBw Bw
(2(00) |0]|
78
s so ((((+++))
- 3
+ (2Bw +1)
B
To optimize the right hand side and ignoring the constant, we take Eg. (0) 1.., This gives
(p(0) 88+ (g (0) +
A.13. A more complete version of Theorem 4
Theorem 5.
1. For all 0 E Rm, Jr. and gp, have non-empty subgradient at 0, and Epp (0) (v)=0)((0) for some v(0) E de 0g (0) - 0gr. (0) == {uz (us, u) E 0grr (0) x Ögr, (0)), where 0g (0) and Øgr, (0) are respectively the 8 subgradients of pr. and gr. at 0:
2. For all 0 E 12m v0) = 0 for some v(0) E de,, (0), then Ep (0)= = 0, hence 0 is a minimizer.
3. r',, everywhere difserentiable. If x is a stationary point of rr, such that izg, (2)(2) (2) o almost surely, then 0g (A)
is global minimum of P..- In particular, under assumptions and 3, we have for every @ E IR. and & 2 0.
Vr == e.p (0) 8Bw BaE.
Proof.
1. We denote for all (0, v) E R x Vp, 60, = =0 u. and for all (0) E Rm x Vp, 6(0, = 0T Ug. In this case, for all 0 E IR",, the loss writes as
( = g0) -0) min o(0, Ug) min Φ(0, v).
"VEV
VEVp
Let (0) and (0) be the set minimizers of respectively U2 + +(0 vp) over V/ and v + (00,)) v) over Vp. Given that Vy and V are compact sets, and -- ((00,) v) for all v E V. is differentiable, and & is continuous, we can say by Danskin's 's theorem that for all 0 E IRm
@p((,,) v)
U ve0(8) conv Vy(()) VP(0),
(fr conv
00
(+)
( conv
(0((0,0)) vB)
ug v²(00) conv 1)) (.+)
(0).
00
The two inequalities (+) and (**) are due to the fact that Vp(0) and (0) are convex sets. Furthermore, we have for all E m
(²)(0)= min 6(0, min
s(0, v) AT 0/3 00 0T (vg 0.
DEVp
where (
E Dp x Vp((). All of the above clearly yields
(0) E v) - (r( = 0g - 0gr
which the result we were seeking to prove.
21

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
2. From the above, it is clear that for given 0 IRm if x(0) O, then (0) 0. Furthermore, using the very first definition of ég. since W p C Wp, we have for all 0 R""
(0)= min Blc,))o ((Co(z) wp(x))) wpEWp
min
B(c,))>P (Co(x) wp(x)) 2 0.
"PEw?
In conclusion, O is a lower bound of ep. and if for given 0, v(0) = 0, then ( 0, i.c. 0 is a minimizer of eg.
3. rp is the difference of the Moreau envelope of two convex functions, hence is the difference between two differentiable convex functions. this yields that r is differentiable. Furthermore, if À is a stationary point of rf then using proposition from (Sun and Sun, 2021), 0f (A) is indeed a stationary point of eg. Furthermore, we have for every 2 0, We consider À E Rn e-stationary point of r i.e. Vr (\))
S E. Using Danskin's 's theorem, we get
Vr 8 P. (A) VMp. (1) VM P.
= - pr, (A) - (A - 0r (1))
= (x) (A) - 0p, (2),
Where 8P. (A) arg minger" gp. (0) 1 a^ 0| and tp. (A) arg minger"" gP. (0) +
2 1| 01 By Up, (Or, (A)) where
2
looking at the proof of Lemma 2, we can easily see that also have Or, (2)
8 up, (0p.. (A)) E arg min 0p, (A) Ogp, (0p, (A)) and 0g. (A) A up, (0 (A)) where upp (0p, (A))
0r (A)T 00p, p. (1)). Letup (0p, (A)) E Earg min, 0% (A)Tr= 0gp. (8P, (A)). We have
arg min V
A P. P. (A)) 0r, (A) T A
(0
uPp p. (A)) - 0p (A)EP, CPP (A)) (A))
(31)
0% (A) 8
Up. To, (A)) -b (A) UP. (0p,()))
(32)
Op,, (A) up, (0p, (A)) 0g (A) UP. OOp. (A))
(33)
(A) up, (0p, (A)) 87, (A) T Up. (Or, (A))
(34)
S 02 (2) bgg Spp, (A)) ur. (Op, (A)) + |=(0f, (2)) k(0r, (2))
(35)
Up, (0p, (1)) 0p, (A) - 6 (A)
(36)
$ (2Bw B& + 5B B&) + l<(02, (A)) - k(0p, (2))
(37)
$ (3Bw B& + 5B BB) e = 8Bw B&e
(38)
Here, is defined for any 0 T as x<)) min T The last equality 38 is due the fact that the subgradient of at some 0 E R" is in Vp, (which can be proven thanks Danskin's theorem) and is hence bounded by Bw Ba. We can see that inequality 38 is indeed the inequality were seeking to obtain. Taking 0 gives that stationarity S for rr, implies global optimality for E
A.14. Key lemma to prove Proposition 2
Lemma For every X E I and 3 2 Bi... we denote V1. Vp, and V2,
V
We have for E (1,2).
P..
1
1
8/ (A) = x v2 with v; arg min
||A + u1l2 and Mip (A) ||a1
min ||^ + e1l?. VEV P. 2
eV P. 2
Proof. The main idea of the proof is to switch min and max in the definitions of Mp. and M
22

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
1. We have for all À E RD
Mp(A) min (7( + 2
|| - 011
(39)
BER
(- min
1
min #ER"
E(Co (x) wr(())
2 a 012
(40)
wyeWr
max @ERm WpEWp
min
-B(Cx(x) wp(x)) + | - 01
(41)
2
min max
0 ((((x) (p((x) (x) + || 01
(42)
dERm wp WPWWp
min max -0 v -vv+
|| 01
(43)
PER vEVp
2
1 || 012
min
-0 V -
(44)
VEVp fER
2
The equality between 44 and 43 holds because of Sion's minimax theorem: since R and Vp are convex sets, v + 00 & is upper semi-continuous and concave for any 0 IRm", and m -0 + 2 || - 0| is lower semicontinuous and convex for any v E Vp, we can switch min and max. In 44, the minimum reached when the gradient with respect to / is zero, i.e. - + 0 - X = O, which gives A + X. In this case, get
Mp(A) = max -w0 + A)
1 ++
||u11
VEVr
2
max -A |0/12 vEVP
1
||al2
1
1A ell
max "EVP
2
= 2
||a|
min "EVp
|| + 011?
2
The calculations above also give us immediately that 0p(A) X where arg min a u11.
2. The proof of the second property is almost identical to the previous one. It suffices to replace Vp by Vp and Wp by 9 p.
A.15. Proof of Proposition 2
This proposition immediately follows from Lemma
A.16. More details on avoiding 0 =
Theorem 6. We define Eve, (A) := arg minxe- || XII and Fro. (A) = arg min
ve-Va || - X to be respec-
tively the projection of X on - Vp, and on -VP. Suppose that X is an e-solution of fP. i.e. and X v1. We have Vr.. B7 Ble. Furthermore, if d(A, -Vp.) By Ba, letting Ā = X + a Fvp, (A]l
| (A) < E for some > 0. \ Fve, (2)
with [3Bw Bo, 8Bw B+] and e' Byy Bic, we have
The value of 3 P. (*) is dominated by e. In particular, we have r (A) < 11Bw Bas' and |[ (30 S VIIBw Bys!
The norm of the resulting candidate solution for eg is bounded from above and below. In particular, Bw Ba. S 110%, (A)]l S 11 Ba B
23

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
Figure summarizes the construction of X.
The theorem above provides us with algorithm to optimize pp
1. Run gradient descent on rpp
2. If we obtain a solution reasonably far from Vr,,, we simply return that iterate as an output. Else, we run gradient descent on Jr.
3. If the gradient descent iterates do not converge to a common boundary to -Vr. and -V P., we return the final iterate as an output. Else, we use the procedure in Theorem 6 to obtain near stationary point which far from the boundary, and return it as an output.
Proof. We will sequentially prove the two points. We assume that À E I is a stationary point of pú In this case, we have
A
F P
(A)
A Fve, (A)
0 (A)
(A)
||
Vp. (1)
2
a Fvon, (2)1
Pro
This yields
A - Ppa (A)
X A-Frr, (A) (A)
1 P (A)
||^ Fvr. (A)l
Ph
Taking the norm in both sides, we get 1 - Ppe. (2)
|| Fvr. (A]] and finally, replugging this in the equality above,
we directly get PP (A) = Fve, i.) Vrp, (A) 0. Let us now prove the second result. We denote D = A Fig. (A)
and Dn A Fvr. (A). We assume now that
f/. (A)
S E. This inequality gives two inequalities
1
Dn
D
S e and
S
E.
|DaIll
|
||
D
2
Hence, we have
Vr P.
Pra Pm
(A) -Fvm (2)
= =1IDA -ull
Dn
-11
||D,,|?
||D,,|1?
< 1|
Dr
D
+
||
1
||Dmn|?
|DA
||D.!1?
D
(1+
| |1
1
< 19Bry + 9BBy
1+
D
|
Do
< B7 Bze.
Let R. such that (V/ (A)l S Se,
Fve. (A) - Fvr, (2) Se.
(45)
24

---

Contextual Optimization Under Model Misspccification: A Tractable and Generalizable Approach
We have
- PF2. (2)
- A Are. (2)
(46)
Pa
- j Fvr. (2)
+
Fven (2) (A)- FVR (a)l
(47)
$ | Firr (2)
+E.
(48)
The last inequality is due to inequality 45 and Eve. (²) Pro (2). every U. E -Vp..
We finish by proving this last equality. We have for
- 1
2 =
X Fve, (2) A +
- 0
(49)
1 Fvrn (1)ll
A EVe. (A) Fvr. (A)
= || u11 + n² + 2r
A-
(50)
11
2 | - w|| + ,2
(51)
Notice that when the left-hand side in 51 is minimized (i.e. == Fvr, (A), the right-hand side takes the same value. Hence, v = Fven (A) is also a minimizer of the left-hand side, i.e. Fve. (1) FFa. (A). Finally, inequality 48 yields
j
(1)l - || Evr. (2// Se,
VA
Which gives
9 rr. (²)
F vg [3/
2
1
- Fven (2/
2
2 (/) Î Poz (3)
` Fren (1)1)) (1)5- - Poz. (2)]l + 1ا Pve. (8/l))
< 2 (1) Î 17g (²)
+ - - Aive (i) (1
$ 2 (6Bw BB + 2r)= S 11B BoE.
Using this, we also prove the bound on the gradient of r.. Using the properties of the projection Pve, (7), we have
Vrg. [1)|| = /|| F P.
(²) - Evon
(F)-FVon.() (ă)
2
= -V (5) 180-x/1- ->1] - | (3) - x||2 - -F
-
Frr Pr (②) - Fvr, (2), Fven (2) - )
S P. (N) S VIIBW BBE.
We finish by proving the bound on 8rr (2). Using Lemma 2, we have 0p. (2) = - Frg. (1), hence,
Bs s 10 ( 11B Ba.
A.17. Proof of Proposition 3
Proof. Let { be the sequence of iterates generated by applying gradient descent to fb. Suppose a subsequence
} of this sequence converges to a limit point A+. If X is not on the boundary of Vp, or -V -V² then by (Nocedal and Wright, 1999). X is a stationary point of f&. We now show that if the limit point x lies on the boundary of -V., then it must also lie on the boundary of -VPp. Indeed, on the one hand, the objective function (A,) is non-increasing, f8, (Ar)) S S (2o) for all t. On the other hand, -
P..
co, which implies that
(d -V v) - oc. Therefore, d(2'; - P..) + 0, yielding the desired result.
25

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
A.18. Experimental setting
We set (d.j) (20, 5) and W to be polyhedron and written W {w R2 Aw 10 10 w 0} where E Rixd (j I d) and b R/. W is closed and bounded, Assumption holds. In every experiment, sample z ~ I) while all of its coordinates are conditioned to be between 0 and 10. and the coefficients of A from standard normal Gaussian distribution, and b to be equal to A |uw, where w has standard normal random coefficients and |w|] is the vector whose coordinates are equal to the absolute value of the coordinates of w.
To create a framework where we can enforce misspecification and progressively analyze how the performance of different methods varies with the level of misspecification (H)) we need to define model that allows for easy adjustment of the misspecification level while still yielding meaningful results. In order to do so, define for R$ c(x) to be linear combination of polynomial functions of æ. This could be written in compact way c(x) M Mo(r) where M is real valued matrix, and (xx) is vector whose coordinates are polynomial in defined by
Vor RR x(x) (I)
21 TR)
T
II
3122
BE (E(0,1)).55t
Furthermore, we define (x) for a E RR and R" as Co(2) = M²(0))(z) where ē(x) is equal to 6(x) truncated to its first coordinates, and (0) a matrix representation
increase the level of misspecification, increase the size of and consequently the gap between 6(x) and ((x) in terms of number of features. To show that this experimental setting that both the elements of the hypothesis set and the ground truth can be written for all x E R& as (x( (xx) 0 and c(x) 4(x)0' 0 Rmm where
indeed corresponds to the theoretical setting studied in this paper,
TT(x)
(((x)
((x)=
E 20x1000 ((x)=
IR 20x00
T(x)T) T
0
d(x)
Furthermore, for any matrix M, we denote (MM the r-th row of M. this case, we have 0* (LM L2)(M)) 20 and f (In(M((B)) [2o()((0)) R 100
B. Additional Figures
Figure Less likely directions for (z):: (e(xr) is less likely to have a direction included red cones, which represent nearly perpendicular directions to one of the faces of the polyhedron (see Assumption 5).
C. Notation table
Symbol R
Meaning
Context or input features
E Rdd
True cost vector
26

---

Contextual Optimization Under Model Misspecification: A Tractable and Generalizable Approach
Wa RR
Feasible of decisions (convex and bounded) Optimal decision under true cost: arg min c w.w Feature transformation (e.g., polynomial basis) applied to context Parameters of the predictive model
w"(c) (c)
((x)
0 e R""
(x(x)
Predicted cost vector, typically ((x) Decision minimizing è w over W Hypothesis class for cost prediction Empirical distribution over i.i.d. samples True decision loss under distribution CILO surrogate loss with cost threshold
w(C)
H
Pn
(p())
(0)
PP.
Piecewise linear surrogate components of CILO loss
TP
3.
Smoothed CILO (s-CIL.O) via Moreau envelope
fP.
bog-barrier surrogate (log-CILO)
Vp.
Set expected feiture-weighted decisions under Pn Subset of Vp,, with expected cost < 3
V
B
Threshold defining near-optimal decision region
Smoothing parameter used in the Moreau envelope
D. Plot with relative regret
Distribution relative performance of different aiteerenttppprerree and their means
Burasspwah
1.50
1.00
0.75
0.50
0.25
5-255
1nd hoollpechhc
Figure 5. Experiment with relative regret results
27


Reviews:
[{"review_id": "gXVq7dIKTe", "reviewer": "Reviewer_cgak", "summary": "In contextual optimization, real-world settings often suffer from model misspecification, meaning the chosen predictor family does not include the true cost function. While existing contextual optimization literature largely focused on well-specified models, this paper tackles that gap by introducing a surrogate loss (“CILO”) that explicitly accounts for model misspecification. The authors show that 1) this surrogate loss is consistent, 2) minimizing the empirical version of this loss has good generalization guarantees, and 3) there exists computationally efficient ways to optimize the proposed surrogate loss. Improvements compared to existing methods are shown in the experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for there insightful questions. Here are our answers in order.\n\n1. We thank the reviewer for this thoughtful question. While we focus on a linear hypothesis class $\\mathcal{H}$ in the later part of Section~3.3 for clarity and analytical tractability, the core ideas and surrogate loss formulation extend well beyond the linear setting.\n\nIn particular, suppose $ \\Phi : \\mathbb{R}^r \\times \\mathbb{R}^k \\rightarrow \\mathbb{R}^{d \\times m} $ is a smooth, parameterized feature map—for example, a neural network with parameters $u \\in \\mathbb{R}^r$. We can define a generalized cost predictor as\n\n$$\\hat{c}_{u,\\theta}(x) = \\Phi(x, u)^\\top \\theta,$$\n\nwhich retains the structure of a linear combination over learned features while allowing $ \\Phi(x, u) $ to be highly expressive. \n\nThis setting captures a broad class of nonlinear models such as neural networks where $\\theta$ is the weights for the output layer and $u$ is the hidden weight. Under mild regularity conditions (e.g., smoothness of $\\Phi$, well-behaved optimization landscapes), the surrogate loss retains the same optimality properties, i.e. every stationary point of our surrogate is a global minimizer. To see why this is true, consider the resulting CILO loss when using this new class of predictors $\\ell_{P}^\\beta(u,\\theta)$ and its Moreau envelope $h_{P}^\\beta(\\lambda_u,\\lambda_\\theta)$.  From Theorem 5 page 19, we can say that for any $\\lambda_u$ and $\\lambda_\\theta$, if $u$ and $\\theta$ are solutions of the minimization problems resulting from the computation of $h_P^\\beta(\\lambda_u,\\lambda_\\beta)$, then if $\\frac{\\partial h_P^\\beta} {\\partial \\lambda_\\theta}(\\lambda_u,\\lambda_\\theta)=0$, then we have $\\ell_P^\\beta(u,\\theta)=0$, i.e. $(u,\\theta)$ is a global minimizer of $\\ell_P^\\beta$. Hence, if $(\\lambda_u,\\lambda_\\theta)$ is a stationary point of $h_P^\\beta$, then we have $\\frac{\\partial h_P^\\beta}{\\partial \\lambda_\\theta}(\\lambda_u,\\lambda_\\theta)=0$ and consequently $(u,\\theta)$ is a global minimizer of $\\ell_P^\\beta$.\n\n2.(i). More details (including what the function phi is) are available in appendix A.18 in page 24.\n\n2.(ii). An updated version of our experiment figure with the relative regret is available here: https://imgur.com/a/0rqF2iE\nThe boxplots show the distribution of the performance of each method, and the curve shows the mean performance of each method.\n\n2.(iii) When checking the mean and the median of the absolute difference between the performance of SPO+ and SLO, they range respectively between 9% and 15% and between 7% and 10% even though the median of the difference between the performance of the two methods appears to be small. We believe that such a difference does not suggest that there is some link between SLO and SPO+.\n\n3.  We thank the reviewer for highlighting the connection to Hu et al. (2024), “Contextual Linear Optimization with Bandit Feedback.” While our assumption is similar in spirit to theirs—both aim to rule out degenerate cases—there is a key conceptual difference.\n\nIn Hu et al., the non-degeneracy condition is imposed on the ground-truth cost function, which is unknown and problem-dependent. In contrast, our assumption is placed on the hypothesis class, which is fully under the control of the decision maker. This makes our assumption both practical and easier to verify in real-world applications, since the designer can ensure it holds through appropriate model selection. In Hu et al., by contrast, the assumption may or may not hold depending on the unknown environment.\n\nThis distinction also highlights a difference in perspective: our framework is designed to be robust under misspecification, where the true cost function may not lie within the hypothesis class. We will clarify this distinction in the revised manuscript, particularly in the discussion surrounding Theorem~2.\n\n4. In the revised version, we will include a dedicated table of notations in the appendix summarizing all key symbols and their meanings. This will help improve clarity and ease of reference. Meanwhile, we provide a table of notations in the following link: https://imgur.com/a/73fBZcT", "claims_and_evidence": "The claims in the paper are supported by evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation make sense for the problem.", "theoretical_claims": "There's no proof in the main text, and I only very briefly checked some in the appendix. The conclusions in the theoretical claims make intuitive sense. One reservation I have for the theory is that, starting from the later part in section 3.3, the authors assume the hypothesis set H is linear, which is somewhat restrictive.", "experimental_designs_or_analyses": "The experiments make sense overall. I have a few questions that I want to authors to clarify:\n- Some design choices in the experiments are unclear, e.g., what the phi function is. \n- A lot of the existing literature use a normalized loss when reporting the results (e.g., Elmachtoub and Grigas), which makes it clear how much worse the methods are compared to the ground truth. The currect paper reports absolute regret, making it hard to observe the relative improvement.\n- The difference between SPO+ and SLO seem to be smaller than I expected in the misspecified setting.", "relation_to_broader_scientific_literature": "The key contribution of the current paper is to design a computationally-efficient surrogate loss for contextual linear optimization under model misspecification. In comparison, existing literature largely focused on well-specified models.", "essential_references_not_discussed": "Since a key contribution in sections 3.1 and 3.2 is proving generalization bound under misspecification for contextual optimization under misspecification, the authors should compare to Theorem 2 in \"Contextual Linear Optimization with Bandit Feedback\" by Hu at al (2024) published in NeurIPS 2024. Theorem 2 therein also considers a generalization bound under misspecification, and they seem to use a similar assumption as Assumption 5 in the current paper.", "other_strengths_and_weaknesses": "I think the contribution of the currect paper is nice. It highlights the under-explored issue of model misspecification in the contextual optimization literature, and the proposed surrogate loss makes sense. I have a few questions that I want to authors to answer, which I listed in the Questions section.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "I want to briefly summarize my questions in the previous sections:\n1. Regarding the theory, please explain what makes optimizing surrogate loss hard if the hypothesis class is non-linear. \n2. Regarding the experiments, please (i) specify the phi functions; (ii) consider changing the absolute regret to normalized regret so it's easier to see the relative improvement compared to baseline; (iii) provide an explanation why the performance of SPO+ and SLO are rather similar.\n3. Regarding literature, please compare the currect result to Hu et al (2024) \"Contextual Linear Optimization with Bandit Feedback\". There seems to be some similarities between the generalization bound in the currect paper and Theorem 2 in the referenced paper, and I think the authors should clarify the difference.\n4. Regarding presentation, it would be better if the authors were able to make a list of the notations in the appendix, since there are many of them and sometimes it's hard for the reader to keep track of things.", "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": "UgnDTNHa55", "reviewer": "Reviewer_WSCt", "summary": "The paper proposes a new optimization surrogate for contextual linear optimization which is a hard problem due to the nonconvexity of the loss function. The newly proposed surrogate is also non convex but is a difference of convex functions. They prove generalization bounds for their surrogate relative to the original/target loss. While the surrogate has good generalization bounds, it potentially does not converge to a stationary point. Thus, the authors propose applying a Moreau envelope smoothing technique to the surrogate. The smoothed surrogate is then shown to have no \"bad\" first-order stationary points or local minima. The paper also provide strategies for avoiding zero solutions. Finally, the paper concludes with a shortest path experiment and compares their approach against SPO+ and sequential learning and optimization approaches.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Replies to initial remarks: we thank the reviewer for their remarks.\n\n- About Proposition 2.1: In binary classification, we aim to maximize the cost. Hence, if we make a cost prediction $\\hat{c}$, then we solve  $\\min -\\hat{c}^\\top w $ to make a decision. Consequently, in the minimization setting, we are making the prediction $-\\hat{c}$ and the CILO loss can be written as the same as defined but replacing $\\hat{c}$ by $-\\hat{c}$. Hence, we believe our proof is correct. A more detailed proof of line 623 page 12 is available here: https://imgur.com/a/NBVRRp4\n\n- About the approach in Jeong et al.: We appreciate the reviewer’s insight. Jeong et al. formulate the SPO loss minimization as an MILP for linear hypothesis sets, whereas our approach is computationally tractable and scalable. It avoids MILP-based optimization, which can be impractical in high dimensions or when fast gradient-based training is needed (e.g., with deep models or large datasets). Our surrogate is differentiable, smoothly approximated via the Moreau envelope, and compatible with standard first-order methods. Our key point is that our approach is the first to tractably minimize decision cost under misspecification with theoretical guarantees.\n\n- Additional details about the experiments: each experiment was conducted using a training dataset of 20 samples and a testing dataset of 20 samples. The optimization was performed using GDA/gradient descent with a constant step size applied to the least squares loss, SPO+, and our smoothed CILO loss. We will make sure to highlight this more clearly in the final submission.\n\n- We agree that broader benchmarks would enhance the practical relevance of our method. Our minimalistic, controlled design follows Hu et al. (https://arxiv.org/abs/2011.03030), enabling systematic analysis of decision quality under misspecification and direct links to theory. While we did not include PyEPO methods, we see PyEPO as a valuable benchmark and appreciate the suggestion. Expanding comparisons to PyEPO and larger benchmarks is a promising future direction once our core theoretical contributions are validated. \n\n- While our goal is not optimal complexity, our primary aim is demonstrating that contextual optimization under misspecification is tractable using a surrogate loss optimized with first-order methods. For clarity, we use Gradient Descent-Ascent (GDA-max) in our experiments, though advanced min-max algorithms could improve the complexity. Our surrogate’s Moreau envelope minimization can be reformulated as a min-max problem (https://imgur.com/a/fYxXQAk), enabling efficient optimization via the single-loop smoothed gradient descent-ascent algorithm (https://arxiv.org/abs/2010.15768). Since $w_P(x_1),\\dots,w_P(x_n)$ have independent constraints, parallelization is possible. While we prioritized conceptual clarity, integrating accelerated methods is a promising direction for future work, which we will clarify and support with relevant citations.\n\n- About the PG loss in Huang et al.: The approach in Huang et al. can be seen as the penalty method to solve the bilevel optimization problem $\\min_{\\hat{c}^\\top w\\leq \\min_{w'\\in W}\\hat{c}^\\top w'}c^\\top w$. In our approach, we flip the upper and lower level, which is why our loss when langragified appears similar (proof: https://imgur.com/a/h0KbcjC). Our approach has global optimiality guarantees, and also differs by the fact that the lagrange multiplier in our surrogate is bounded (see Appendix A.9) and the \"lagrange multiplier\" $\\frac{1}{h}$ in the PG loss has to be large enough when the sample size is large which can cause numerical issues.\n\nReplies to the questions:\n1. The realizations of $w_P(x)$ in equaltions (10) and (11) are independently constrained, whereas in equation (12), the realizations of $w_P^\\beta(x)$ are linked by the constraint $\\mathbb E(c^\\top w_P^\\beta (x))\\leq \\beta$ and hence the same inequality does not hold. \n\n2. It seems that in most practical settings, this phenomenon does not happen. However, since we do not have a theoretical characterization of when this happens, we introduced the log-CILO loss, which helps to address this issue.\n\n3. In reality, the good landscape properties of the CILO loss remain even before considering its Moreau envelope. Indeed, in Appendix A.13, a more complete version of theorem 4 is provided, where we show that any stationary point of the non-smooth version of the CILO loss is a global minimizer. The Moreau envelope is used only as a tool to tractably minimize the CILO loss.\n\n4. Theoretically, we can prove that line search with precision $\\epsilon$ provides an global minimizer with precision $\\epsilon$. Proof:https://imgur.com/a/LHxvfkk\n\n5. The shortest path problems are within our problem setting--their decision-making problems are linear programs. So we can directly apply our approach to solve them, but we agree that testing our algorithms in practical settings can be interesting and important future directions.", "claims_and_evidence": "Some of the claims in the paper are hard to verify like Proposition 2.1. In the proof, the authors seem to convert the minimization problems into maximization problems. They seem to claim that $\\min c^{\\top}x$ is $-\\max c^{\\top}x$ which seems incorrect. My belief is that the authors used a CILO form for maximization problems but mixed up their steps with the version of the proof using minimization problems. \n\nThe authors also claim that existing works lack generalization bounds as they are empirical, however, [1] provides the same type of generalization bounds as this paper and only does not provide global optimality results. \n\nThe paper also seems to claim that most surrogates do not consider the misspecified setting. However, the main surrogate that requires well-specified hypothesis classes is just SPO+. Methods like [2] directly optimize SPO loss which would practically also cover misspecified settings. \n\n___ \n[1] Huang, Michael, and Vishal Gupta. \"Decision-focused learning with directional gradients.\" Advances in Neural Information Processing Systems 37 (2024): 79194-79220.\n[2] Jeong, Jihwan, et al. \"An exact symbolic reduction of linear smart predict+ optimize to mixed integer linear programming.\" International Conference on Machine Learning. PMLR, 2022.", "methods_and_evaluation_criteria": "The proposed theoretical tools leverage theory for solving non-convex losses which is a key challenge for this class of problems. The numerical evaluation criteria is somewhat limited as there are existing surrogate losses that solve the same problems, however, the paper does not compare against these approaches. This would be helpful for understanding when the proposed surrogate's global optimality guarantees are practically useful. Related, the paper also does not highlight the computational cost of their approach. Optimizing a function with Moreau envelope smoothing does not seem computationally cheap. In contrast existing approaches do not leverage such smoothing and are potentially more computationally efficient. Thus, identifying settings where global optimality is hard to achieve would be made the proposed surrogate approach more practically compelling.", "theoretical_claims": "As discussed above, Proposition 2.1 proof seems incorrect. Restated: \"In the proof, the authors seem to convert the minimization problems into maximization problems. They seem to claim that $\\min c^{\\top}x$ is $-\\max c^{\\top}x$ which seems incorrect. My belief is that the authors used a CILO form for maximization problems but mixed up their steps with the version of the proof using minimization problems. \"\n\nI checked the theoretical results up Propostion 1, which seemed correct.", "experimental_designs_or_analyses": "The design of the main numerical experiment seems valid, but lacks many details such as the number of samples generated or a main body description of the optimization problem solved. It is also limited due to the lack of problem settings as well as lack of benchmark methods. The PyEPO package [1] is fairly standard benchmark that was not considered by the authors.\n____\n[1] Tang, Bo, and Elias Boutros Khalil. \"Pyepo: A pytorch-based end-to-end predict-then-optimize library with linear objective function.\" OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop). 2022.", "relation_to_broader_scientific_literature": "This work broadly contributes to the area of decision-focused learning [1]. A key challenge in the literature is constructing computationally tractable surrogates to optimize over as the direct decision-focused loss is non-convex. This paper provides the first results highlighting that there exists surrogates that when optimized over converge to a \"good\" stationary point. \n\n____\n[1] Mandi, Jayanta, et al. \"Decision-focused learning: Foundations, state of the art, benchmark and future opportunities.\" Journal of Artificial Intelligence Research 80 (2024): 1623-1701.", "essential_references_not_discussed": "The paper doesn't seem to mention PyEPO [1] which provide standard numeric benchmarks and methods to evaluate. Many existing surrogates in the PyEPO seem to argue that their surrogates enjoy good landscape. With global optimality guarantees, this paper should be able to verify if such claims are true for existing benchmarks and give insight about what settings are \"easy\" or \"hard\" to solve to global optimality for existing surrogates.  \n____\n[1] Tang, Bo, and Elias Boutros Khalil. \"Pyepo: A pytorch-based end-to-end predict-then-optimize library with linear objective function.\" OPT 2022: Optimization for Machine Learning (NeurIPS 2022 Workshop). 2022.", "other_strengths_and_weaknesses": "Strengths\n1) The paper constructs a surrogate and shows optimizing the surrogate returns a stationary point that correspond with global optimality. It breaks down the key challenges towards showing such a stationary point can be achieved and addresses each challenge in an organized and clear manner. \n2) The paper provides helpful examples for understanding the challenges of misspecification. \n\nWeaknesses\n1) The paper lacks details and analysis on the computational components of their approach. First, they do not provide details on how to solve the minimization problems in Definition 2. They also do not highlight the computation cost of their approach in the numerics compared to existing benchmarks.\n2) The notation in the paper is confusing. A key definition is $\\beta^{\\star}\\_{\\mathcal{H},P} := \\min\\_{\\hat{c}\\in\\mathcal{H}}\\ell\\_{P}(\\hat{c})$, however, $\\ell_P$ seems to only take the input $\\theta$. This notation makes it hard to distinguish between $\\beta_{\\min, P}$ and $\\beta^{\\star}\\_{\\mathcal{H},P}$.", "other_comments_or_suggestions": "1) In the proof of Theorem 2, it seems that the CILO loss when lagrangified resembles the PG Loss of [1] with step size $h$ set as the optimal dual variable. It may be worth making the connection.\n2) The decision-well-specified definition is hidden in the appendix and not defined in the body even though it is an assumption for Proposition 2.1. It would be helpful to reference it so readers can find it.", "questions_for_authors": "1) Does an equality similar to the equality between equations (10) and (11) hold for equation (12)?\n2) In what settings do $\\theta$ converge to 0 if one does not use the log-CILO loss? \n3) What properties of the CILO loss allow the Moreau envelope smoothing approach to produce a surrogate with \"good\" stationary points?\n4) It was not clear to me, but is there a way to verify if your choice of $\\beta$ returns the global optimal solution for the empirical loss? Another similar question would be, does line search guarantee you obtain the global minimizer for $\\theta$ in polynomial time? \n5) Does your surrogate practically work for combinatorial problems like shortest path? My main concern is solving the problem with the $\\beta$ constraint and the minimization problem in the Moreau envelope smoothing.", "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": "BCqLVXhXRw", "reviewer": "Reviewer_modT", "summary": "This paper considers misspecification in the contextual optimization problem, or the predict-then-optimize problem. The authors use a toy example to illustrate the failure of some existing approaches, such as SPO+ and SLO, when the hypothesis class for the prediction part is misspecified. Then, to address this issue, this paper proposes a new traceable surrogate loss function to learn the predictor, and shows the performance of this new method with both theoretical guarantee and numerical performance.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer bringing up the work of Sun et al. [2023], which proposes a novel approach for learning a cost predictor by maximizing the optimality margin—ensuring that the reduced cost of the predicted solution is positive in the ground-truth optimal basis.\n\nThis method can lead to robust decisions under certain conditions. However, we would like to highlight a key assumption made in their analysis (see page 7 of their paper), which implies the existence of a cost predictor in the hypothesis class that yields the same decision as the ground-truth cost. This is equivalent to assuming the hypothesis class is decision well-specified, which we formally define in our paper (Definition 5, page 11). Our framework is explicitly designed to relax this assumption; thus, we address a more general (and practically relevant) setting where no cost predictor in the hypothesis class can yield optimal decisions. To the best of our knowledge, this is the first approach that can minimize the decision cost in a tractable manner under misspecification.\n\nNote that the optimality margin in Sun et al. [2023] focuses on the magnitude of optimality violations (e.g., positivity of reduced costs)– this is still an inconsistent metric with decision cost, since decision quality is ultimately determined by whether the optimal decision under the predicted cost function aligns with that of the true cost.  \n\nIn contrast, our method directly minimizes the decision error of the optimal decision-making policy under the predicted cost, and we provide guarantees that hold even without decision well-specification (see Theorem 1, page 4).\n\nAlthough our first toy example (Example 1, page 2) assumes decision well-specification, we clarify after Example 2 (line 170, page 4) that our method continues to perform well even when this assumption fails, while other methods, including SPO+, SLO, and by extension Sun et al., can fail. \nTo further support this point, we are including an updated version of Example 2 where the method in Sun et al. [2023] does not yield the optimal cost predictor, while ours does. The core intuition of our example is that a predictor that classifies nearly all points correctly but has extreme optimality constraint violation for one point will not be favored by their approach over a predictor that makes poor decisions consistently but mildly violates the optimality margin, whereas the optimal predictor in terms of decision performance is the one that classifies correctly the most amount of points. Our approach provides the optimal classifier in this setting as well.\n\nRegarding the mention of “KKT-based” methods: if the reviewer was referring to the use of KKT conditions to characterize predictive performance (as in Sun et al. [2023]), we believe the limitations noted above apply. If a different method was intended, we would be happy to provide further clarification upon request.\n\nConsider a refinement of example 2 where we expand the support of the distribution of the context to $\\\\{1,2,3\\\\}$. We consider the two cost predictors $\\hat{c}_1$ and $\\hat{c}_2$ to satisfy $\\hat{c}_1(1)=\\frac{1}{8}, \\hat{c}_1(2)=\\frac{1}{8},\\hat{c}_1(3)=-100000,\\hat{c}_2(1)=1,\\hat{c}_2(2)=-\\frac{1}{6},\\hat{c}_2(3)=-1.$\n\nRecall that in example 1, the ground truth cost is always equal to $1$. The problem we solve to make a decision given a prediction $\\hat{c}$ is the following $\\max_{w\\in[-1/2,1/2]} \\hat{c}w.$ In order to apply the approach in Sun et al. [2023], we write the maximization problem above in its standard form. \n\\\\begin{align*}\n\\min_{w_+,w_-,s_u,s_\\ell\\geq 0}&\\\\;\\begin{pmatrix}\n-\\hat{c} \\\\\\\\ \\hat{c} \\\\\\\\ 0 \\\\\\\\ 0\n\\end{pmatrix}^\\top \\cdot\\begin{pmatrix}\nw_+ \\\\\\\\ w_- \\\\\\\\ s_u \\\\\\\\ s_\\ell\n\\end{pmatrix}\\\\\\\\\n\\text{s.t. }&\\begin{pmatrix}\n1 & -1 & 1 & 0 \\\\\\\\ -1 & 1 & 0 & 1\n\\end{pmatrix}\\begin{pmatrix}\n w_+ \\\\\\\\ w_- \\\\\\\\ s_u \\\\\\\\ s_\\ell\n\\end{pmatrix}=\\begin{pmatrix}\n1/2 \\\\\\\\ 1/2\n\\end{pmatrix}.\n\\\\end{align*}\nRecall that in Sun et al., the optimization problem they solve in order to solve the optimal predictor is in equation 3 page 4 of their paper. We drop the term $\\frac{\\lambda}{2}\\|\\|\\Theta\\|\\|_2^2$, although it is possible to keep it and construct a model that gives the same result while keeping this term. This optimization problem in our setting becomes the following\n\n\\\\begin{align*}\n\\min_{\\hat{c}\\in \\\\{\\hat{c}_1,\\hat{c}_2\\\\}}& \\frac{1}{3}(||v_1||_1+||v_2||_1+||v_3||_1)\\\\\\\\\n\\text{s.t.} &\\\\; \\forall t\\in \\\\{1,2,3\\\\}, \\begin{pmatrix}\n0 \\\\\\\\ \\hat{c}(i)\n\\end{pmatrix}\\geq \\begin{pmatrix}\n1 \\\\\\\\ 1\n\\end{pmatrix} -v_i\n\\\\end{align*}\n\nThe value of the minimum above for $\\hat{c}_1$ is equal to $\\sim 33334.66$ and for $\\hat{c}_2$ is equal to $\\sim 2$, which means that the approach in Sun et al. favors $\\hat{c}_2$ even though it is suboptimal, whereas our method favors $\\hat{c}_1$.\n\nFinally, we aim to include further comparison with other approaches in our full submission, and are open to compare with any further approaches the reviewer has in mind.", "claims_and_evidence": "Yes. The authors use a counter-example to show the weakness of some existing methods and also provide proof to show the strength of their new approach.", "methods_and_evaluation_criteria": "Yes. Hypothesis class misspecification is an important setup in learning with optimization.", "theoretical_claims": "I checked the proof for the toy example, and roughly checked the proof for the main theorem.", "experimental_designs_or_analyses": "I roughly went through the numerical part.", "relation_to_broader_scientific_literature": "This work considers the misspecification issues for the PTO or contextual optimization problem, while to my best knowledge, the existing work needs to assume a well-specified hypotheis class.", "essential_references_not_discussed": "I would not say the work is essential for the predict-then-optimize or the contextual optimization problem. However, potentially [1] can still also address the misspecification issues for the given example. More specifically, it seems that the issues in the toy example come from the misalignment between prediction accuracy in parameter prediction and the accuracy in optimality prediction. Consequently, it is possible that a KKT-based method can address this misspecification issue.\n\nIf my statement is corrected, could the authors illustrate more on the necessity of their new approach? I am happy to change my rating based on the authors' answer to this one.\n\n[1] Maximum Optimality Margin: A Unified Approach for Contextual Linear Programming and Inverse Linear Programming", "other_strengths_and_weaknesses": "The strengths have been discussed in the summary. When talking about weaknesses, I wonder whether the authors could elaborate more on the necessity of this new approach. More details can be found in the Essential References part. This is also my major concern.", "other_comments_or_suggestions": "It would be better to include more comparisons between the new approach and other methods for the PTO or contextual optimization problem.", "questions_for_authors": "Please see the Essential References part.", "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": {"ethical_review_concerns": "NA"}}, {"review_id": "ksYVD6Udfa", "reviewer": "Reviewer_e7We", "summary": "The paper addresses the case of hypothesis class misspecification and proposes a new contextual optimization framework that ensures both tractability (via regularizing) and generalizability.\n\npost-rebuttal: I thank the authors for their response and explanation on generalizability of their ideas. I am keeping my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for this thoughtful question. While we focus on a linear hypothesis class $\\mathcal{H}$ in the later part of Section~3.3 for clarity and analytical tractability, the core ideas and surrogate loss formulation extend well beyond the linear setting.\n\nIn particular, suppose $ \\Phi : \\mathbb{R}^r \\times \\mathbb{R}^k \\rightarrow \\mathbb{R}^{d \\times m} $ is a smooth, parameterized feature map—for example, a neural network with parameters $u \\in \\mathbb{R}^r$. We can define a generalized cost predictor as\n\n$$\\hat{c}_{u,\\theta}(x) = \\Phi(x, u)^\\top \\theta,$$\n\nwhich retains the structure of a linear combination over learned features while allowing $ \\Phi(x, u) $ to be highly expressive. \n\nThis setting captures a broad class of nonlinear models such as neural networks where $\\theta$ is the weights for the output layer and $u$ is the hidden weight. Under mild regularity conditions (e.g., smoothness of $\\Phi$, well-behaved optimization landscapes), the surrogate loss retains the same optimality properties, i.e. every stationary point of our surrogate is a global minimizer. To see why this is true, consider the resulting CILO loss when using this new class of predictors $\\ell_{P}^\\beta(u,\\theta)$ and its Moreau envelope $h_{P}^\\beta(\\lambda_u,\\lambda_\\theta)$.  From Theorem 5 page 19, we can say that for any $\\lambda_u$ and $\\lambda_\\theta$, if $u$ and $\\theta$ are solutions of the minimization problems resulting from the computation of $h_P^\\beta(\\lambda_u,\\lambda_\\beta)$, then if $\\frac{\\partial h_P^\\beta} {\\partial \\lambda_\\theta}(\\lambda_u,\\lambda_\\theta)=0$, then we have $\\ell_P^\\beta(u,\\theta)=0$, i.e. $(u,\\theta)$ is a global minimizer of $\\ell_P^\\beta$. Hence, if $(\\lambda_u,\\lambda_\\theta)$ is a stationary point of $h_P^\\beta$, then we have $\\frac{\\partial h_P^\\beta}{\\partial \\lambda_\\theta}(\\lambda_u,\\lambda_\\theta)=0$ and consequently $(u,\\theta)$ is a global minimizer of $\\ell_P^\\beta$.", "claims_and_evidence": "Claims made in the submission are supported by clear and convincing evidence", "methods_and_evaluation_criteria": "The methods and evaluation criteria make sense.", "theoretical_claims": "I haven't checked the proofs; though they look highly plausible.", "experimental_designs_or_analyses": "I checked the soundness of the experimental setup and they stand valid.", "relation_to_broader_scientific_literature": "It complements the prior predict-then-optimize literature e.g. Elmachtoub, A. N. and Grigas, P. (2022). Smart “predict, then optimize”. Management Science, 68(1):9–26. and Elmachtoub, A. N., Lam, H., Zhang, H., and Zhao, Y. (2023). Estimate-then-optimize versus integrated-estimationoptimization: A stochastic dominance perspective. arXiv preprint arXiv:2304.06833. by considering specifically model misspecification.", "essential_references_not_discussed": "I am not aware of such cases.", "other_strengths_and_weaknesses": "I think the method is original to the field of data-driven decision-making community.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "How would the analysis of global optimality generalize to non-linear hypothesis classes?", "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": "rpl31g8xsf", "reviewer": "Reviewer_Mq1a", "summary": "This paper presents a new framework for contextual optimization problems where predictive models may not perfectly capture the true underlying relationships. Unlike traditional methods that assume the model is well-specified, this approach introduces a new surrogate loss function designed to ensure that even when predictions are inaccurate, the chosen decisions remain close to optimal. The authors provide theoretical guarantees, including global optimality, generalization performance, and computational efficiency. To handle challenges like non-convexity, they apply smoothing techniques that enable stable gradient-based optimization. Through empirical comparisons, they show that while standard approaches like Sequential Learning and Optimization and Smart Predict-then-Optimize perform well in well-specified cases, their method outperforms them when models are misspecified.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for these thoughtful questions. First, we believe that the paper the reviewer mentioned (Adam N Elmachtoub, Henry Lam, Haixiang Lan, and Haofeng Zhang. Dissecting the impact of model misspecification in data-driven optimization) is indeed relevant to our work, and aim to mention it in our final submission.\n\nHere are the answers for each of the two questions.\n\n1. This is indeed a valid point. We aim to run more extensive experiments in our future work to validate further the performance of our method, and in particular in real world datasets. We believe that such experiments can strengthen the evidence that shows our approach's empirical performance.\n\n2. While we focus on a linear hypothesis class $\\mathcal{H}$ in the later part of Section~3.3 for clarity and analytical tractability, the core ideas and surrogate loss formulation extend well beyond the linear setting. In particular, suppose $ \\Phi : \\mathbb{R}^r \\times \\mathbb{R}^k \\rightarrow \\mathbb{R}^{d \\times m} $ is a smooth, parameterized feature map—for example, a neural network with parameters $u \\in \\mathbb{R}^r$. We can define a generalized cost predictor as\n\n$$\\hat{c}_{u,\\theta}(x) = \\Phi(x, u)^\\top \\theta,$$\n\nwhich retains the structure of a linear combination over learned features while allowing $ \\Phi(x, u) $ to be highly expressive. \n\nThis setting captures a broad class of nonlinear models such as neural networks where $\\theta$ is the weights for the output layer and $u$ is the hidden weight. Under mild regularity conditions (e.g., smoothness of $\\Phi$, well-behaved optimization landscapes), the surrogate loss retains the same optimality properties, i.e. every stationary point of our surrogate is a global minimizer. To see why this is true, consider the resulting CILO loss when using this new class of predictors $\\ell_{P}^\\beta(u,\\theta)$ and its Moreau envelope $h_{P}^\\beta(\\lambda_u,\\lambda_\\theta)$.  From Theorem 5 page 19, we can say that for any $\\lambda_u$ and $\\lambda_\\theta$, if $u$ and $\\theta$ are solutions of the minimization problems resulting from the computation of $h_P^\\beta(\\lambda_u,\\lambda_\\beta)$, then if $\\frac{\\partial h_P^\\beta} {\\partial \\lambda_\\theta}(\\lambda_u,\\lambda_\\theta)=0$, then we have $\\ell_P^\\beta(u,\\theta)=0$, i.e. $(u,\\theta)$ is a global minimizer of $\\ell_P^\\beta$. Hence, if $(\\lambda_u,\\lambda_\\theta)$ is a stationary point of $h_P^\\beta$, then we have $\\frac{\\partial h_P^\\beta}{\\partial \\lambda_\\theta}(\\lambda_u,\\lambda_\\theta)=0$ and consequently $(u,\\theta)$ is a global minimizer of $\\ell_P^\\beta$.", "claims_and_evidence": "The paper's claims are generally well-supported by theoretical analysis and empirical results. The authors provide formal proofs showing that their surrogate loss function aligns with the true decision objective (Theorem 1) and that minimizing the empirical surrogate loss results in a small out-of-sample decision error (Theorem 2). Additionally, they demonstrate that the method remains tractable for gradient-based optimization through Moreau envelope smoothing (Theorem 4). Overall, the core contributions are justified and well-grounded.\n\nHere are some minor points that could be strengthened:\n1. The paper evaluates its method primarily on synthetic data. Expanding the experiments to include real-world datasets from diverse domains would enhance empirical validation. Some theoretical conditions may require verification in practical settings. Providing concrete examples of how these conditions hold in real-world scenarios would strengthen the paper’s contributions.\n\n2. In Theorem 4, global optimality for the proposed surrogate loss is established only for linear hypothesis sets. Extending this result to more general hypothesis classes would improve its applicability.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are generally well-aligned with the problem of contextual optimization under model misspecification.", "theoretical_claims": "I reviewed the theoretical claims and proofs, such as Theorems 1, 2, 4. Theorem 1 establishes that minimizing the proposed surrogate loss leads to optimal decision policies, and the proof appears mathematically sound. Theorem 2 provides a generalization bound, demonstrating that minimizing empirical loss results in small out-of-sample decision errors, and the proof appears fine. Theorem 4 (and Theorem 5) ensures computational traceability and optimization efficiency, and the proof is well-structured.", "experimental_designs_or_analyses": "I reviewed the validity of the experimental design and analyses. The paper effectively compares its method against Sequential Learning and Optimization (SLO) and Smart Predict-then-Optimize (SPO+), which are the most relevant baselines for decision-focused learning. The evaluation uses synthetic datasets to control for model misspecification. The chosen metrics, particularly decision error, are well-suited to the problem.", "relation_to_broader_scientific_literature": "The key contributions of this paper extend existing research in the area of contextual optimization (Sadana et al., 2024). It builds on prior work, such as Smart Predict-then-Optimize (SPO+) (Elmachtoub & Grigas, 2021), which integrates optimization constraints into the learning process to improve decision quality. However, unlike SPO+, which assumes a well-specified prediction model, this paper explicitly accounts for model misspecification. Additionally, the paper connects to research on sequential learning and optimization (SLO) (Donti et al., 2021). The considerations of well-specified and misspecified models also align with findings from Hu et al. (2022) and Elmachtoub et al. (2023), which explore the impact of misspecification on decision-making performance. This work may also relate to advances in robust decision-making under uncertainty, such as distributionally robust optimization (DRO) (Rahimian & Mehrotra, 2019) and end-to-end decision learning (Wilder et al., 2019).", "essential_references_not_discussed": "The paper appropriately cites and discusses the most relevant prior works necessary to contextualize its key contributions. \n\nA recent paper that might have some relevance is:\nAdam N Elmachtoub, Henry Lam, Haixiang Lan, and Haofeng Zhang. Dissecting the impact of model misspecification in data-driven optimization. In International Conference on Artificial Intelligence and Statistics. PMLR, 2025.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "See Claims And Evidence.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: I enjoyed the paper and concur with the overall positive response from the reviewers and happily recommend acceptance. There are a few points, however, that I think are necessary to address in a camera ready. One is an expanded discussion of statistical guarantees in the misspecified setting (e.g. Hu et al 2024 as mentioned by Reviewer cgak) as well as a clearer explanation of the use of a margin condition and its relation to statistical guarantees. Another is a clarification and better discussion of the claimed tractability and its meaning as "practical tractability" vs "theoretical tractability," given that, while well motivated, the reduction is still to a technically "hard" problem in the general setting. These are only what I think are the most crucial points, but the authors should also address all other concerns and certainly incorporate elements from the discussion into the final paper.
Decision: Accept (poster)