Risk Bounds and Calibration for a Smart Predict-then-Optimize Method
Authors: Heyuan Liu
Paul Grigas
Venue: NeurIPS 2021 Poster (2021)
Keywords: contextual stochastic optimization
predict-then-optimize
learning theory
risk bounds

Abstract: The predict-then-optimize framework is fundamental in practical stochastic decision-making problems:  first predict unknown parameters of an optimization model, then solve the problem using the predicted values. A natural loss function in this setting is defined by measuring the decision error induced by the predicted parameters, which was named the Smart Predict-then-Optimize (SPO) loss by Elmachtoub and Grigas [2021]. Since the SPO loss is typically nonconvex and possibly discontinuous, Elmachtoub and Grigas [2021] introduced a convex surrogate, called the SPO+ loss, that importantly accounts for the underlying structure of the optimization model. In this paper, we greatly expand upon the consistency results for the SPO+ loss provided by Elmachtoub and Grigas [2021]. We develop risk bounds and uniform calibration results for the SPO+ loss relative to the SPO loss, which provide a quantitative way to transfer the excess surrogate risk to excess true risk. By combining our risk bounds with generalization bounds, we show that the empirical minimizer of the SPO+ loss achieves low excess true risk with high probability. We first demonstrate these results in the case when the feasible region of the underlying optimization problem is a polyhedron, and then we show that the results can be strengthened substantially when the feasible region is a level set of a strongly convex function. We perform experiments to empirically demonstrate the strength of the SPO+ surrogate, as compared to standard $\ell_1$ and squared $\ell_2$ prediction error losses, on portfolio allocation and cost-sensitive multi-class classification problems.

Risk Bounds and Calibration for a Smart Predict-then-Optimize Method
Heyuan Liu University of California, Berkeley
Paul Grigas
University of California, Berkeley Berkeley, CA 94720
Berkeley, CA 94720 heyuan_ leweeerkeleyeeeeeeeee..... edu edu
pgrigas@berkelley edu
Abstract
The predict-then-optimize framework is fundamental in practical stochastic decision-makinn problems: first predict unknown parameters of an optimization model, then solve the problem using the predicted values. A natural loss function in this setting is defined by measuring the decision error induced by the predicted parameters, which was named the Smart Fredict-then-Optimiz (SPO) loss by Elmachtoub and Grigas [2021]. Since the SPO loss typically nonconvex and pos- sibly discontinuous, Elmachtoub and Grigas 2021] introduced convex surrogate, called the SPO+ loss, that importantly accounts for the underlying structure of the optimization model. In this paper, greatly expand upon the consistency results for the SPO+ loss provided by Elmachtoub and Grigas [001]] We develop risk bounds and uniform calibration results for the SPO+ loss relative to the SPO loss, which provide quantitative way to transfer the excess surrogate risk to excess risk. By combining our risk bounds with generalization bounds, we show that the empirical minimizer of the SPO+ loss achieves low excess true risk with high probability. We first demonstrate these results the case when the feasible region of the underlying optimization problem is polyhedron, and then we show that the results can be strengthened substantially when the feasible region is level of a strongly convex function. We perform experiments to empirically demonstrate the strength the SPO+ surrogate, as compared to standard & and squared &a predic- tion error losses, on portfolio allocation and cost-sensitive multi-class classification problems.
1 Introduction
The predict-hhen-ppimmizz framework, where one predicts the unknown parameters of an optimization model and then plugs in the predictions before solving, is prevalent in applications of machine learning. Some typical examples include predicting future asset returns in portfolio allocation problems and predicting the travel time each edge of network in navigation problems. In most cases, there many contextual features available, such as time day, weather information, financial and business news headlines, and many others, that can be leveraged predict the unknown parameters and reduce uncertainty in the decision making problem. Ultimately, the goal to produce a high quality prediction model that leads to good decisions when implemented, such position that leads to large return or a route that induces a small realized travel time. There has been fair amount of recent work examining this paradigm and other closely related problems in data-driven decision making, such as the works of Bertsimas and Kallus [2020]. Donti et al. [2017) [Elmachtoub and Grigas 2021
Kao al. [2009] Estes and Richard [2019] Ho and Hanasusanto (2019] Notz and Pibernik
2019
Kotary et al. 202 the references therein, and others.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In this work, we focus on the particular and important case where the optimization problem of interest has linear objective with a known convex feasible region and where the contextual features are related to the coefficients of the linear objective. This case includes the aforementioned shortest path and portfolio allocation problems. In this context, |Elmachtuub and Grigas [20TT] developed the Smart Peedict-then-Opiimie (SPO) loss function, which directly measures the regret of prediction against the best decision in hindsight (rather than just prediction error, such as squared error). After the introduction of the SPO loss, recent work has studied its statistical properties, including generalization bounds of the SPO loss function in El Balghiti et al. [2019] and generalization and regret convergence rates in Hu et al. [020]_ Moreover, since the SPO loss is not continuous nor convex in general [Elmachtoub and Grigas 2021]. which makes the training of a prediction model computationally intractable, Elmachtoub and Grigas (202T] introduced a novel convex surrogate loss, referred to as the SPO+ loss. Ellacctoub and Grigas
2021] highlight and prove several advantages of the SPO+ surrogate loss: (i) it still accounts for the downstream optimization problem when evaluating the quality of a prediction model (unlike prediction losses such as the squared Eg loss), (ii) it has desirable Fisher consisteney property with respect to the SPO loss under mild conditions, and (iii) it often performs better than commonly considered prediction losses in experimental results. Unfortunately, although desirable property of any surrogate loss in this context, Fisher consistency is not directly applicable when one only has available a finite dataset, which is always the case in practice, because it relies on full knowledge of the underlying distribution. Motivated thusly, is desirable to develop risk bounds that allow one to translate an approximate guarantee on the risk of a surrogate loss function to a corresponding guarantee on the SPO risk. That is, risk bounds (and the related notion of calibration functions) answer the question: to what tolerance ō should the surrogate excess risk be reduced to in order to ensure that the excess SPO risk is at most e? Note that, with enough data, it is possible in practice to ensure (high probability) bound on the excess surrogate risk through generalization and optimization guarantees.
The main goal of this work is to provide risk bounds for the SPO+ surrogate loss function. Our results, to the best of our knowledge, are the first risk bounds of the SPO+ loss, besides the analysis of the 1 1-dimensional scenario in Ho-Neu and Kilin-- Karzn-KKazaanaaaa 2020). Our results consider two cases for the structure of the feasible region of the optimization problem: (i) the case of bounded polyhedron. and (ii) the case of a level set of a smooth and strongly convex function. In the polyhedral case, we prove that the risk bound of the SPO+ surrogate is O(²)) where E is the desired accuracy for the excess SPO risk. Our results hold under mild distributional assumptions that extend those considered in Elmachtoub and Grigas (202T). In the strongly convex level set case, we improve the risk bound of the SPO+ surrogate to O(c) by utilizing novel properties of such sets that we develop, namely stronger optimality guarantees and continuity properties. As a consequence of our analysis, we can leverage generalization guarantees for the SPO+ loss to obtain the first sample complexity bounds, with respect to the SPO risk, for the SPO+ surrogate under the two cases we consider. In Section [] we present computational results that validate our theoretical findings. In particular we present results on entropy constrained portfolio allocation problems which, to the best of our knowledge, is the first computational study of predict-then-eee then-optimize problems for a strongly convex feasible region. Our results on portfolio allocation problems demonstrate the effectiveness of the SPO+ surrogate. We also present results for cost-sensitive multi-class classification that illustrate the benefits of faster convergence of the SPO risk in the case of strongly convex sets as compared to polyhedral ones.
Starting with binary classification, risk bounds and calibration have been previously studied in other machine learning settings. Pioneer works studying the properties of convex surrogate loss functions for the 0-1 loss include Zhang et al. [2004], Bartlett et al. 2006). Massart et al. (0066] and Steinwart (0077). Works including Zhang] [2004), Tewari and Bartlett| [2077] and Osokin et al. [2017] have studied the consistency and calibration properties of multi-class classification problems, which can be considered as a special case of the prrdict-then-optinee related to the results presented herein is the work of Houuueen and Kiling-Kazan Karzan [2020]. J. who study the uniform calibration properties of the squared &g loss, and the related work of Hu et al. (2020). complexit complexity results for the SPO loss when using squared lg surrogate.
framework [E) Balghiti et al., 2019]. Most
who also develop fast sample
Notation. Let @ represent element- multiplication between two vectors. For any positive integer m, let [m]] denote the set (1, : m). Let T denote the by p identity matrix for any positive integer p. For ē E Rdd and a positive semi- matrix Σ E Raxd let Net Σ) denote the normal distribution (cc) e 3 (o-n)) x: (c-)))
We will make use of a generic given norm || - || on w E Rd
(22r) det(T)
2

---

as well as its dual norm || ||~ which is defined by ||e||= m| c'w.
w. For positive definite matrix A, we define the A-norm by ||æ]|| == / Aw. Also, we denote the diameter of the set S S Rdd by Ds == w's |||u (1lo-wu w2112
2
Predict-then-optine
framework and preliminaries
We now formally describe the predict- predict-then-opine then-optimize framework, which is widely prevalent in stochas- tic decision making problems. We assume that the problem of interest has linear objective. but the cost vector of the objective, E C C IRd. is not observed when the decision is made. Instead, we observe feature vector x X C TRP, which provides contextual information associated with c. Let IP denote the underlying joint distribution of the pair (z, c). Let w denote the decision variable and assume that we have full knowledge of the feasible region S C Rd, which is assumed to be non-empty, compact, and convex. When feature vector x is provided, the goal of the decision maker is to solve the contextual stochastic optimization problem:
min P- [e" w] = min Pe)) WES
(1)
WES
As demonstrated by [ for linear optimization problems the predict-then-opiin on a prediction of the conditional expectation the cost vector, namely [[[[[=] = [=)) [c]]] Let à denote a prediction of the conditional expectation, then the next step in the predict-then-optimizz setting is to solve the deterministic optimization problem with the cost vector č, namely
framework relies
P(() min c" W. WES
Depending on the structure of the feasible region S, the optimization problem P(-) can represent linear programming, conic programming, and even (mixed) integer programming, for example. In any case, we assume that we can solve P-)) to any desired accuracy via either a closed-form solution or a solver. Let w-): T2d -> S denote a particular optimization oracle for problem 2 whereby w" ("(( (?) is an optimal solution of P(č). (We assume that the oracle is deterministic and ties are broken in an arbitrary pre-specified manner.)
In order to obtain a model for predicting cost vectors, namely a cost vector predictor function g : X + Rd, we may leverage machine learning methods learn the underlying distribution P from observed data ((11,
(In, G,),, which are assumed to be independent samples from P. Most importantly, following [ we would like to learn the conditional expectation and thus g(x) can be thought of as an estimate of B[c/z]. We follow standard recipe for learning a predictor function g where we specify a loss function to measure the quality of predictions relative to the observed realized cost vectors. In particular, for loss function f, the value f(é, c) represents the loss or error incurred when the cost vector prediction is è (i.e., = g(r)) and the realized cost vector is c. Let (g: P) == B((,,))p(((g(()) c)] denote the the risk of given loss function é and let (P) = inf Re(g': (P) denote the optimal é-risk over all measurable functions g'. Also, let (g) = 1 Σn i= c() denote the empirical f-risk. Most commonly used loss functions are based on directly measuring the prediction error, including the (squared) &z and the & losses. However, these losses do not take the downstream optimization task nor the structure of the feasible region S into consideration. Motivated thusly, one may consider a loss function that directly measures the decision error with respect the optimization problem 2). Elmachtoub and Grigas) (0021) formalize this notion in our context of linear optimization problems with their introduction of the SPO (Smart Predict-then-OOe thet--ptiizzeee loss function, which is defined by
(é c) == cT w" (c) cT w (c))..
where é E Rd is the predicted cost vector and E C is the realized cost vector. Due to the possible non-convexity and possible discontinuities of the SPO loss, Ellacchoub and Grigas (021 also propose a convex surrogate loss function, the SPO+ loss, which is defined
Esro+ (č, c) := max ( (c- 20) w) + 26" wn(c)= c² """ (c).
WES
Importantly, the SPO+ loss still accounts for the downstream optimization problem 2 and the structure of the feasible region S, in contrast to losses that focus only on prediction error. As discussed by [llachhoub and Grigas 2021 the SPO+ loss can be efficiently optimized via linear/conic
3

---

optimization reformulations and with (stochastic) gradient methods for large datasets. Elmachtoub and Grigas 202T provide theoretical and empirical justification for the use of the SPO+ loss function. including derivation through duality theory, promising experimental results on shortest path and portfolio optimization instances, and the following theorem which provides the Fisher consistency of the SPO+ loss.
Theorem 2.1 (Elmachtoub and Grigas [ Theorem 1). Suppose that the feasible region S has non-empty interior. For fixed a &, suppose that the conditional distribution PP ([-(z) is continuous
on all of RR, is centrally symmetric around its mean == [[,-(())) and that there is a unique
optimal solution of P(e). Then. for all A IP it holds that
(- [esPo- + c) (e, c)] (ewF(-la)) [[c +2)+22)//) (w" (c) w wc(c+ (c(cc)A) 2 O.
Moreover, if A # O, then E--P(-lle) [(Spo) (i + A) - ESpO+ (c) > 0.
Notice that Theorem 2. holds for arbitrary x E X. i.e., employs a nonparametric analysis as is standard in consistency and calibration results, whereby there are constraints the predicted cost vector associated with æ. Under the conditions of Theorem 2.1 given any z E X, we know that the conditional expectation ē [e-p(- [c] is the unique minimizer of the SPO+ risk. Furthermore, since č is also a minimizer of the SPO risk, it holds that the SPO+ loss function is Fisher consistent with respect the SPO loss function, i.e., minimizing the SPO+ risk also minimizes the SPO risk. However, in practice, due to the fact that we have available only a finite dataset and not complete knowledge of the distribution P. cannot directly minimize the true SPO+ risk. Instead, by employing the use of optimization and generalization guarantees, we are able to approximately minimize the SPO+ risk. A natural question is then: does low excess SPO+ risk guarantee low excess SPO risk? More formally, we are primarily interested in the following questions: (i) for any E > 0, does there exist d(e) 0 such that RSpo IP) Rspo- (IP) < ô(e) implies that Aspo IP) (PP) < e?, and (ii) what is the largest such value of ō(E) that guarantees the above?
Excess risk bounds via calibration. The notions of calibration and calibration functions provide useful set of tools answer the previous questions. We now review basic concepts concerning calibration when using a generic surrogate loss function f, although we are primarily interested in the aforementioned SPO+ surrogate. An excess risk bound allows one transfer the conditional excess f-risk, E (((2,c))z - in E [&(c', c)]22 to the conditional excess frsok EE [fsro c]| inf E [Espo (c', [x] Calibration, which we now briefly review, a central tool in developing excess risk bounds. We adopt the definition of calibration presented by [Steinwart [007 and Ho-Nguyen and Balinç-Karzan 2020). which is reviewed in Definition 2. below.
Definition 2.1. For a given surrogate loss function f, we say is Espo-calibrater with respect to P there exists function de(-): I E4 such that for all E X, ê e C, and >> 0, it holds that
E [e((,, e)l=] in [e(c', , c) Se(e) + E [f e>|
inf E [éspo c)(a]
(3)
Additionally, if 3 holds for all PP E P, where P is class of distributions on X' C, then we say that é is uniformly calibrated with respect to the class of distributions P.
direct approach to finding a feasible 6e(-) function and checking for uniform calibration is by computing the infimum of the excess surrogate loss subject to a constraint that the excess SPO loss is least e. This idea leads the definition of the calibration function, which we review in Definition 2.2 below.
Definition 2.2. For given surrogate loss function l and true cost vector distribution Pe,, the condi- tional calibration function (=:PP..) is defined, for > 0, by
6e(s; = inf BER4
[E( e) - inf E [e(() E [Espo (2, c)) inf
inf ((spo .c)] c))22) 20]
o
o'
Moreover, given a class of joint distributions P, with a slight abuse of notation, the calibration function (r(:;P) P) is defined, for e > 0, by
de(e; = inf 8c(e;
FEP

---

If the calibration function Pp satisfies Pe(e; > 0 for all > O, then the loss function E' is uniformly (spo-calibratee with respect to the class of distributions P. To obtain an excess risk bound, we let 07 denote the biconjugate, the largest convex lower semi-continuous envelope, of 5t. Jensen's 's inequality then readily yields (fspRs (g. P) - ((so((P)) I Re(g. IP) - (T()) which implies that the excess surrogate risk Rg P) Rg (P)) of predictor can be translated into upper bound of the excess SPO risk Ag P) RSro(P) (P). For example, the uniform calibration of the least squares (squared E2) loss, namely (2,(C, = l|ē cll2. was examined by Ho-Nguyen and Kilin-KKazan 20200. They proved that the calibration function is d8g (f) = = D which implies an upper bound of the excess SPO risk by [sro(g. P) - (1P) S Ds (DL(( - Ris (IP)) In this paper, we derive the calibration function of the SPO+ loss and thus reveal the quantitative relationship between the excess SPO risk and the excess surrogate SPO+ risk under different circumstances.
(Rspo
3 Risk bounds and calibration for polyhedral sets
In this section, we consider the case when the feasible region S is a bounded polyhedron and derive the calibration function of the SPO+ loss function. As shown in Theorem 2.1 the SPO+ loss Fisher consistent when the conditional distribution PP(-j2)) is continuous on all of Rd and is centrally symmet- ric about its mean č. More formally, the joint distribution I' lies in the distribution class Peont symm == (P-(z) is continuous on all of Id and is centrally symmetric about its mean, for all E X3. In Example we later show that this distribution class is not restrictive enough to obtain meaningful calibration function. Instead, we consider a more specific distribution class consisting of distributions whose density functions can be lower bounded by normal distribution. More formally, for given parameters M 2 and O; B >> O, define Par..,8 == (P E Pount symm for all x E X with ē = Efc|z]], there exists a E [0, M] satisfying || S B0 and P(c(x) 2 a NNe, I²I) 1) for all c E Rd). Intuitively, the assumptions on the distribution class PMr ensure that avoid situation where the density of the cost vector concentrates around some "badly behaved points." ! This intuition is further highlighted in Example Theorem 3.1 is our main result in the polyhedral case and demonstrates that the previously defined distribution class is a sufficient class to obtain a positive calibration function. Recall that Ds denotes the diameter of S and define "width constant" associated with S by ds := min {maxwes v² min v" w Notice that ds >> 0 whenever S has a non-empty interior.
Theorem 3.1. Suppose that the feasible region S is a bounded polyhedron and define Es = (1 +
2v3Ds )1-d. Then the calibration function of the SPO+ loss satisfies
ds
oEs
min { () for all > 0.
22
8 8 (c; (c;PM,,,3) 2
(4)
Theorem 3.1 yields an ((22) uniform calibration result for the distribution class PM. The dependence on the constants is also natural as it matches the upper bound given by the cases with fi-like unit ball feasible region S' and standard multivariate normal distribution as the conditional probability F(-1z)) Please refer Example 2 in the Appendix for detailed discussion. Let us now provide some more intuition on the parameters involved in the definition of the distribution class Pa....9 and their roles in Theorem 3.1 In the definition of P PM. a is a lower bound on the ratio of the density of the distribution of the cost vector relative to "reference" standard normal distribution. When a is larger, the distribution is behaved more like normal distribution and it leads to better lower bound on the calibration function (4) in Theorem 3.1 The parameter M is an upper bound on the standard deviation of the aforementioned reference normal distribution, and the lower bound 4 naturally becomes worse as M increases. The parameter 3 measures how the conditional mean deviates from zero relative to the standard deviation of the reference normal distribution. If this distance is larger then the predictions are larger on average and 4 becomes worse. The width constant dg measures the near-degeneracy of the polyhedron (ds = 0 is degenerate) and the bound becomes meaningless as ds - 0. When the feasible region S is near-degenerate, i.e., the ratio Ds close to zero, we tend to have a weaker lower bound on the calibration function, which is also natural.
da is
We now state a remark concerning an extension of Theorem 3.1 and we describe the example that demonstrates that it is not sufficient to consider the more general distribution class Paom synm- Remark. In Theorem 3.1 assume that the conditional distribution P(. is lower bounded by normal density the entire space Rdd We can extend the result of Theorem 3.1 I to the case when
5

---

P(-[z) is lower bounded by normal density on a bounded set but the constant is more involved. For details, please refer Theorem in the Appendix.
Example 1. Let the feasible region be the l ball S {w R² / w|l < 1} and consider the distribution class Poent, symm. For fixed scalar > 0, let (9c, 0)2 and c2 (-7e, 0) Let the conditional distribution Po (elxz) be mixture of Gaussians defined by P. (c]z) := (e(ee,o"1)
(c2, o² D)) for any
O, and we have (c|z)) E Poont. symm. Let the predicted cost vector be è = (0, e)", then the excess conditional SPO risk is E[fsro((,, c) (e,
c. Then it holds that the excess conditional SPO+ risk E [Espo+ (2. c) - ESPO+ (c, [z) + 0 when o + 0, and hence
we have (e: Poont. symm) = 0.
The intuition of Example D is that the existence of a non-zero calibration function requires the conditional distribution of c given x to be "uniform" on the space R4, but not concentrate near certain points. Example | highlights a situation that considers one such "badly behaved" case where a limiting distribution of mixture of two Gaussians leads to a zero calibration function.
By combining Theorem 3.1 with a generalization bound for the SPO+ loss, we can develop a sample complexity bound with respect to the SPO loss. Corollary [.1 presents such result for the SPO+ method with a polyhedral feasible region. The derivation of Corollary 3.1 relies on the notion of multivariite Rademacher complexity well the vector contraction inequality of Maurer [2016) in the l noooo.. In particular, for a hypothesis class H. of cost vector predictor functions (functions from X' to IRd), the multivariate Rademacher complexity is defined as 9t 22 -= of 9(z;)] where a, E {-1,+1} are Rademacher random vectors for i = I,...,n.. n. Please refer to Appendix [A] for a detailed discussion of multivariate Rademacher
E0,0 . JSupgE 1
complexity and the derivation of Corollary 3.1
Corollary 3.1. Suppose that the feasible region S is bounded polyhedron, the optimal predictor g"(x) E[c|xr] is in the hypothesis class H. and there exists constant C' such that RA (H) S C² vii
Let SSPo+ denote the predictor which minimizes the empirical SPO+ risk (. over H. Then there exists a constant C such that for any P E PMM,,, and 8 E (0, }), with probability at least 1 - 5, holds that
RsPo (pSO i P)- 185r (IP) Cvlog(1/0)
1/4
Notice that the rate in Corollary 3.1 is O(1/n//4). However, the bound with respect the SPO loss which is generally non-convex and is the first such bound for the SPO+ surrogate. Huu et al. (2020) present a similar result for the squared & surrogate with rate of O(1/ and an interesting open question concerns whether the rate can also be improved for the SPO+ surrogate.
4 Risk bounds and calibration for strongly convex level sets
In this section, we develop improved risk bounds for the SPO+ loss function under the assumption that the feasible region is the level set of a strongly convex and smooth function, formalized in Assumption below.
Assumption 4.1. For given norm -1 let Rd + R be p-strongly convex and L-smooth function for some L μ O. Assume that the feasible region S is defined by S {w Rd f(w) S T} for some constant r > fmin := min, f(w).
The results in this section actually hold in more general situations than Assumption 4.1 In Appendix C we extend the results of this section to allow the domain of the strongly convex and smooth function Assumption 4. to be any set defined by linear equalities and convex inequalities (Assumption
C. Herein, we consider the simplified case where the domain is IR for ease of exposition and conciseness. The results of this section and the extension developed in Appendix Saarnddixaaalooo Callow for broad choice of feasible regions, for instance, any bounded fg ball for any g E (1,2) and the probability simplex with entropy constraint. The latter example, which can also be thought of portfolio allocation with an entropy constraint, is considered in the experiments in Section
As in the polyhedral case, the distribution class Peont, symm is not restrictive enough to derive meaningful lower bound on the calibration function of the SPO+ loss. We instead consider two related classes of rotationally symmetric distributions with bounded conditional coefficient of variation.

---

These distribution classes are formally defined in Definition [.1 below, and include the multi variate Gaussian, Laplace, and Cauchy distributions as special cases.
Definition 4.1. Let A be given positive definite matrix. We define Pio symm, the class of distributions with conditional rotational symmetry in the norm || ll-1, namely
P symm, A {P: Vx X, 3q(+) [0, oo] [0, such that P(c)a:) g(lle dlA--))--
Let è denote the conditional expectation = B[e[z]. For constants E (0, 1] and 3 > 0, define
PBA:= = {P E Prxx symm,, Fagxelle ||c - c| 2 S 3 | Vo E }
and
PaBBA = {P P s (lc - - B ||||||-111 2 a, Vo E x
Under the above assumptions, Theorem 4.1 demonstrates that the calibration function of the SPO+ loss is O()), significantly strengthening our result in the polyhedral case. Theorem C.I in Appendix Gextends the result of Theorem to the aforementioned case where the domain (-) may be
subset of Rd which includes the entropy constrained portfolio allocation problem for example.
Theorem 4.1. Suppose that Assumption
4.1 holds with respect to the norm
ll for some pos- 2/2
itive definite matrix A. Then, for any 0, it holds that 8t (c; (3.A) 2 4(14,332213 c and
Segr (e; Pa.8.A)2 2 4(1+82)2973
o/2/2
Let us now provide some more intuition on the parameters involved in the definitions the distribution classes PA.A and Pa.e,A and their roles in Theorem 4.1 In both cases, 33 controls the concentration of the distribution of cost vector around the conditional mean. The more concentrated the distribution is, the better the bounds in Theorem 4. are. In the case of Pa, a relates the probability that the cost vector is "relatively close" to the conditional mean. When or is larger, the cost vector is more likely to be close the conditional mean and the bound will be better.
Our analysis for the calibration function (the proof of Theorem 4.1) relies on the following two lemmas. which utilize the special structure of strongly convex level sets strengthen the first-order optimality guarantees and derive a "Lipschitz-like like"" continuity property of the optimization oracle w" (-). The first such lemma strengthens the optimality guarantees of and provides both upper and lower bounds of the SPO loss.
Lemma 4.1. Suppose that Assumption 4.1 holds with respect to a generic norm || ||. Then, for any C1 C2 Rdd it holds that
cF w² (c()c 2T Smin)
Ve E E, |all--1w w² (c:)ll?
and
L
of (c2) - w= (ci)) 5 22/2u(r fmia)
lealla1lu=(css) w=
The following lemma builds on Lemma 4.1 to develop upper and lower bounds on the difference between optimal decisions based on the difference between the two normalized cost vectors.
Lemma 4.2. Suppose that Assumption 4.1 holds with respect to generic norm || be such that C1, 02 # O, then holds that
Let c1, 02 Rd
[l="(ci)) - - (c2))l 2p - fmin)
C2
L
||l
|| |02
and
(cz) w0 (02)l 2L - Smin)
C2
|elll
|eell
in Lemma 4.1 and the upper bound of | (c; (c:)-w') - (c2) in Lemma 4.2 match bounds developed by El Balghiti et al. (2019]. Indeed, although El Balghiti al. 2019 study the more general case of strongly convex sets, the constants are the same since M -strongly convex Theorem 12 of Journé et al. [210]] demonstrates that our set S is /2L(r-Jmia)
Note that the lower bound of of (w-w"
7

---

set. However, the upper bounds in Lemmas 4.1 and uppear to be novel and rely on the special properties of strongly convex level sets. It is important to emphasize that we generally do not expect all of the bounds in Lemmas 4.1 and 4.2 to holds for polyhedral sets. Indeed, for polyhedron the optimization oracle w" (.) is generally discontinuous at cost vectors that have multiple optimal solutions. The properties in Lemmas 4.1 4.2 drive the proof of Theorem and hence lead to the improvement from (e²²) in the polyhedral case to O(e) in the strongly convex level set case.
By following similar arguments as in the derivation of Corlloary 3.1 Corollary 4.1 presents the sample complexity of the SPO+ method when the feasible region is a strongly convex level set.
Corollary 4.1. Suppose that Assumption holds with respect to the norm || l for some positive definite matrix A. Suppose further that the optimal predictor g" (x) E[c[z]] is the hypothesis class H. and there exists a constant C' such that RDhh R*HH) (H) S C² Let 0SPO+ denote the predictor which
VT
minimizes the empirical SPO+ risk R)po-()) over H. Then there exists a constant C such that for any P E Po, UP3 and ó E (0, f), with probability at least -Ō,
6, it holds that
C Cvlog(L/d)
Rspo R P) 185ro (IP) S
n//
Notice that Corollary 4.1 improves the rate of convergence to O(1/vn) as compared to the O(1/n1/4 rate of Corollary 3.1 This matches the rate for the squared &g surrogate developed by Hu et al. [2020] (though their result is in the polyhedral case).
5 Computational experiments
In this section, we present computational results of synthetic dataset experiments wherein we empirically examine the performance of the SPO+ loss function for training prediction models, using portfolio allocation and cost-sensitive multi-class classification problems as our problem classes. We focus on two classes of prediction models: (i) linear models, and (ü) two-layer neural networks with 256 neurons in the hidden layer. We compare the performance of the empirical minimizer of the following four different loss function: (i) the previously described SPO loss function (when applicable), (ii) the previously described SPO+ loss function, (iii) the least squares (squared E2) loss function {(2, c) ||ē cl2 and (iv) the absolute (l₂) loss function ((2,c) l|è cll2 For all loss functions, we use the Adam method of Kingma and Ba (015) to train the parameters of the prediction models. Note that the loss functions (ii) and (fv) do not utilize the structure of the feasible
region and can be viewed as purely learning the relationship between cost and feature vectors.
Entropy constrained portfolio allocation. First, we consider the portfolio allocation [Markowitz] 1952] problem with entropy constraint, where the goal is to pick an allocation of assets in order to maximize the expected return while enforcing certain level of diversity through the use of an entropy constraint (see, e.g., Bera and Park (008)). This application is an instance of our more general theory for strongly convex level sets constrained domains, developed in Appendix C Alternative formulations of portfolio allocation, including when S' is a polyhedron or a polyhedron intersected with an ellipsoid, have been empirically studied in previous works (see, for example example|Elmachtoul Elmachtoub and Grigas (2021) Hu et al. (2020]). The objective is to minimize e" w where is the negative of the expected returns of d different assets, and the feasible region is S = {w E Rd 2 0, Σ W0 1, 1 w, log w; S <r} where r user-specified threshold of the entropy of portfolio w. Note that, due to the differentiability properties of of the optimization oracle w-(() in this case (see Lemma D. in the Appendix), it is possible to (at least locally) optimize the SPO loss using gradient method even though SPO loss is not convex.
In our simulations, the relationship between the true cost vector and its auxiliary feature vector x is given by e= d (Bx)) @ where does is a polynomial kernel mapping of degree deg, B is a fixed weight matrix, and is multiplicative noise term. The features are generated from a standard multivariate normal distribution, we consider d = 50 assets, and further details of the synthetic data generation process are provided in Appendix D. To account for the differing distributions of the magnitude of the cost vectors, in order to evaluate the performance of each method we compute a "normalized" SPO loss on the test set. Specifically, let 9 denote a trained prediction model and let
>m (.)(8(E.).8))
{ (ū,, T denote the test set, then the normalized SPO loss is defined as 2im1 (8.)
where
8

---

Normalized SPO Loss v.s. Polynomial Degree
Method
Absolute Loss = Least Least Squares
SPO + SPO+
No Noise
Noise Training Set Size = 1000
Moderate Noise
Moderate Noise
Training Set Size 100
Training Set SitSize Size 100
Training Set Set 1000
Predictor: Linear
0.2
0.1
5PO Loss
0.0
Predictor: NN
0.2
0.1
0.0
1
2
6
2
B
1
Polynomial Degree
Figure 1: Normalized test set SPO loss for the SPO, SPO+, least squares, and absolute loss methods on portfolio allocation instances.
(2) mintee of is the optimal cost in hindsight. We set the size of the test set to 10000. In all of our experiments, we run 50 independent trials for each setting of parameters.
Figure displays the empirical performance of each method. We observe that with linear hypothesis class, for smaller values of the degree parameters, i.c., deg E {1,2), all four methods perform comparably, while the SPO and SPO+ methods dominate in cases with larger values of the degree parameters. With a neural net hypothesis class, we observe similar pattern but, due to the added degree of flexibility, the SPO method dominates the cases with larger values of degree and SPO+ method is the best among all surrogate loss functions. The better results of the l loss as compared to the squared lg loss might be explained by robustness against outliers. Appendix D also contains results showing the observed convergence of the excess SPO risk, the case of poly polynomial degree one, for both this experiment and the cost-sensitive multi-class classification
Cost-sensitive multi-class classification. Here we consider the cost-sensitive multi-class classi- fication problem. Since this is multi-class classification problem, the feasible region is simply the unit simplex S = {w E Rd w 2 0, E. W; 1} We consider an alternative model for generating the data, whereby the relationship between the true cost vector and its auxiliary feature vector is follows: first generate score a (ddez x)) @ c). where d is degree-deg polynomial kernel, 5 is a fixed weight vector, is a multiplicative noise term, and a--) is the logistic function. Then the true label is given by lab [10s] {1,,... 10} and the
vector is given by G = lab] for i ...... 10. The features are generated from a standard multivariate normal distribution, and further details of the synthetic data generation process are provided in Appendix D Since the scale of the cost vectors do not change as we change different parameters, we simply compare the test SPO loss for each method. We still the size of the test set 10000 and run 50 independent trials for each setting of parameters. In addition to the regular SPO+, least squares, and absolute losses, we consider an alternative surrogate loss constructed by considering the SPO+ loss using log barrier (strongly convex) approximation to the unit simplex. That is, we consider the SPO+ surrogate that arises from the set 5 ;= {w Ed
0, Dd Di=!
W; 1, Σd log w; S r}
for some r 0. Details about how we chose the value r are provided in Appendix D
Herein we focus on the comparison between the standard SPO+ loss and the "SPO+ w/ Barrier" surrogate loss. (We include more complete comparison of all the method akin to Figure [ Appendix DD) Figure[ishow shows a detailed comparison between these alternative SPO+ surrogates we vary the training set size. Note that the SPO loss always measured with respect to the standard unit simplex and not the log barrier approximation. Interestingly, we observe that the "SPO+ w/ Barrier" surrogate tends to perform better than the regular SPO+ surrogate when the training set size is small, whereas the regular SPO+ surrogate gradually performs better the training set size increases. These

---

SPO Loss V.S. Training Set S Size = SPO+ E
Method
SPO+ w/ Barrier
Predictor: Linear
Predictor: Linear
Predictor: Neural Nets
Predictor: Neural Nets
No Noise
Moderate Noise
No Noise
Moderate Noise
SPO Logs
0.6
0.4
0.2
0.0
100
200
500
2000
100
200 500
1000 2000
100 200
500 1000 2000
100
200 500 1000 2000
Training Size
Figure 2: Test set SPO loss for the SPO+ methods with different feasible regions the cost-sensitive multi-class classification instances.
results suggest that adding barrier constraint the feasible region has type of regularization effect, which may also be explained by our theoretical results. Indeed, adding the barrier constraint makes the feasible region strongly convex, which improves the rate of convergence of the SPO risk. On the other hand, this results in an approximation to the actual feasible region of interest and, eventually for large enough training set sizes, the regularizing benefit of the barrier constraint outweighed by the cost of this approximation.
6 Conclusions and future directions
Our work develops risk bounds and uniform calibration results for the SPO+ loss relative to the SPO loss, and our results provide a quantitative way transfer the excess surrogate risk to excess true risk. We analyze the case with a polyhedral feasible region the underlying optimization problem, and we strengthen the results when the feasible region is level set of strongly convex function. There are several intriguing future directions. In this work, we mainly focus on the worst case risk bounds of the SPO+ method under different types of feasible regions, and consider the minimal possible conditions to guarantee the risk bounds. In many practical problems, it is reasonable to assume the true joint distribution of (ar, satisfies certain "low-noise" conditions (see, for example, Bartlett et al. (006). Massart et al.) (2006), Hu et al. [2020]. In such conditions, one might be able to obtain improved risk bounds and sample complexities. Also, developing tractable surrogates and corresponding calibration theory for non-linear objectives is very worthwhile.
Acknowledgments
The authors grateful Othman El Balghiti, Adam N. Elmachtoub, and Ambuj Tewari for early discussions related to this work. PG acknowledges the support of NSF Awards CCF-1755705 and CMMI-1762744.
10

---

References
L.. Bartlett and S. Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
L.. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 1413)))::38-156 2006.
A. K. Bera and S. Y. Park. Optimal portfolio diversification using the maximum entropy principle. Econometric Reviews, 27(4-6):484557) 512, 2008.
D. Bertsimas and N. Kallus, From predictive to prescriptive analytics. Management Science, 66(3): 1044-1044, 2020.
P. Donti, B. Amos, and J. Kolter. Task-based end-to-end model learning in stochastic optimization. In Advances Neural Information Processing Systems, volume 30, 2017.
O. El Balghiti, A. N. Elmachtoub, P. Grigas, and A. Tewari. Generalization bounds in the predict- then-optimize framework. In Advances in Neural Information Processing Systems, volume 32, 2019.
A. N. Elmachtoub and P. Grigas. Smart "predict, then optimize". Management Science, 2021.
A. Estes and J.-P. Richard. Objective-aligned regression for two-stage linear programs. Available SSRN 3469897, 2019.
C. P. Ho and G. A. Hanasusanto. On data-driven prescriptive analytics with side informa- tion: A regularized nadaraya-watson approach. URL: http://www. optimization-online org/DB FILE/201/01/7043. pdf. 2019.
N. Ho-Nguyen and F. Kılmę- Karzan. Risk guarantees for end-to-end prediction and optimization processes. arXiv preprint arXiv:2012.15046. 2020.
Y. Hu, N. Kallus, and X. Mao. Fast rates for contextual linear optimization. arXiv preprint arXiv:2011.030300 2020.
M. Journée, Y. Nesterov, P. Richtárik, and R. Sepulchre. Generalized power method for sparse principal component analysis. Journal of Machine Learning Research, 11(Feb):517555, 2010.
Y.-h. Kao, B. Roy, and X. Yan. Directed regression. Advances in Neural Information Processing Systems, 22:889 897, 2009.
D. Kingma and J. L. Ba. Adam: method for stochastic gradient descent. ICLR: International Conference Learning Representations, pages 1-15, 2015.
J. Kotary, F. Fioretto, P. Van Hentenryck, and B. Wilder. End-to-end constrained optimization learning: A survey. arXiv preprint arXiv:2103. 16378, 2021.
H. Markowitz. Portfolio selection. The Journal of Finance, 7(1):77-91, 1952. ISSN 00221082, 15406261. /ttp:://://ww/ w/st///sww.ssoorrr/r/ooo.o jstor. org/ sttg////9////
P. Massart, É. Nédélec, et al. Risk bounds for statistical learning. The Annals of Statistics, 34(5): 2326-2366, 2006.
A. Maurer. vector-contraction inequality for rademacher complexities. International Conference on Algorithmic Learning Theory, pages 3-17. Springer, 2016.
P. M. Notz and R. Pibernik. Prescriptive analytics for flexible capacity management. Available at SSRN 3387866, 2019.
A. Osokin, F. Bach, and S. Lacoste-Julien. On structured prediction theory with calibrated convex surrogate losses. arXiv preprint arXiv: /00.00277002233 2017.
Steinwart. How to compare different loss functions and their risks. Constructive Approximation, 26(2):225-287, 2007.

---

A. Tewari and P. L. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(5), 2007.
Zhang. Statistical analysis some multi-category large margin classification methods. Journal of Machine Learning Research, 5(Oct): 1225-1251, 2004.
T. Zhang et al. Statistical behavior and consistency of classification methods based on convex risk minimization. The Annals of Statistics, 32(1):56-88) 2004.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Please refer Section and
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Please refer Appendix [ C
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] Please refer Appendix [
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] Please refer Section
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] Please refer Section
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [Yes] Please refer Appendix [
4. If you using existing assets (e.g., code, data, models) or curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "wLC7RjI-RNO", "reviewer": "Reviewer_7rEw", "summary": "The paper develops the risk bounds and uniform calibration results for the surrogate SPO+ loss relative to the SPO loss in the predict-then-optimize framework under the assumption of a linear loss function. The results are first obtained for a polyhedron feasible region of the optimization problem and further improved when the feasible region is a level set of a strongly convex function. Then, they are used to establish a sample complexity (with respect to the SPO loss) of the algorithm that minimizes the empirical SPO+ risk. The empirical performance of the SPO+ surrogate is demonstrated in portfolio optimization and cost-sensitive multi-class classification problems.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I believe that the paper presents an important extension of the existing Fisher consistency property of SPO+ w.r.t SPO with the risk bounds and uniform calibration results. This is because the Fisher consistency is not applicable when only finite datasets are available as explained in the paper. The assumption of linear loss function is also reasonable according to the presented literature of the predict-then-optimize framework. Overall, the paper is well-written and well-structured. \n\nI only have minor questions related to the experiments and the fact that the conclusion section is missing. In figure 1, when the predictor is a neural network and the polynomial degree is 6 or 8, the performance of SPO+ is only on par with l1 loss and is outperformed significantly by SPO. This is different from the case when the predictor is a linear model. What could be the reason for this? I think that the assumption $g^*(x) = \\mathbb{E}[c|x]$ (in Corollaries 3.1 and 4.1) is violated more severely for simple predictors (e.g., linear models), so what does this imply?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "umwHRYCcM4S", "reviewer": "Reviewer_FdGF", "summary": "This paper derives uniform calibration bounds for the SPO+ loss relative to the SPO loss, when the feasible region is polyhedral or a level set of strongly convex functions. This enables us to translate excessive risk bound in terms of SPO+ loss, ie, the convex surrogate loss,  into bounds for the SPO loss. Notably, the authors show that the class of symmetric distributions considered in Elmachtoub and Grigas is not restrictive enough to derive calibration bounds, and instead stronger restrictions must be incorporated.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper looks very solid. It studies a very important question about the SPO method that attracts a lot of attention recently, ie, whether small risks for the computationally tractable surrogate loss imply small risks for the loss of interest. \n\nAlthough that this paper can derive some calibration results is really nice, I am not sure how relevant the results are for explaining the use of SPO+ loss. \n\t1. In particular, the calibration results in this paper are all based on some restrictions on the true data distributions. But this paper has very little discussions about these assumptions. For example, how strong are these assumptions? What do some parameters (eg, alpha, beta..) mean? How do they influence the final bounds? What is the intuition? What if the assumptions are violated?\n\t2. The Experiments in this paper are very disconnected from the theory. I don't see how the experiments even try to support any of the theoretical findings. It seems that the current experiments largely just shows that SPO works better, especially when models are misspecified, which is similar to the original SPO paper. But what's new?  Actually, experiments might be a very good way to assess the those distributional assumptions. \n-------------------\nConsidering the authors' response, I decide to change my score from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't think that this work will have negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 "}, "extra_text": {}}, {"review_id": "ofi2DwWjT33", "reviewer": "Reviewer_cSZd", "summary": "The paper studies the excess SPO risk of the empirical SPO+ risk minimizers. When the feasible region of the downstream planning task is a bounded polyhedron, the excess risk is on the order of O(n^{-1/4}). When the feasible region is the level set of a strongly convex and smooth function, the excess risk is on the order of O(n^{-1/2}). Empirically, the authors show that the empirical minimizers of SPO+ perform better than the ones for \\ell_1, \\ell_2 for more complex hypothesis class. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is very clearly written with a detailed background on smart Predict-then-Optimize and the SPO+ surrogate loss. In general, the current manuscript could be improved in the following ways:\n\n- The distributional assumptions for Theorem 3.1/Corollary 3.1: It is a bit unnatural to see that the assumption of the distribution requires P(c|x) to be heavy-tailed (in the sense that the tails are thicker than the ones for sub-Gaussians) to obtain the excess-risk guarantees. Intuitively, when P(c|x) is sub-Gaussian, the learning problem becomes much simpler and one would expect the excess risk of any proposed learning-planning scheme to be lower. Does this result suggest that when the data is nicely distributed (e.g., when P(c|x) is sub-Gaussian), one should use other losses instead of SPO+ loss or maybe just directly perform the traditional two-stage process: first learning then planning? \n- For the experiment section, since the theoretical results are on excess risk---it would be nice/necessary to have an experiment that shows the excessive risk of empirical SPO+ minimizers against the number of samples and see whether the rate is on the order of O(n^{-1/4}) or O(n^{-1/2}).\n\n*Update after author response* I have read the author response and I am satsfied with the answers. Hence, I maintain my score for acceptance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper builds upon a prior work on Smart Predict-Then-Optimize (SPO) framework. Many practical problems can be described as 2 step procedures: 1. predict some quantity 2. solve optimization problem with predictions from step 1 being inputs. Elmachtoub and Grigas earlier proposed SPO where we take into account step 2 during step 1 by setting up an appropriate surrogate loss. Prior work has only established asymptotic guarantees for this learning problem and this paper presents first finite sample guarantees. The reviewers agree that this paper is well written and presents an important contribution that is of interest to a broader Neurips community.
Decision: Accept (Poster)