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.

Here are the answers for each of the two questions.

1. 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.

2. 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

$\hat{c}_{u,\theta}(x) = \Phi(x, u)^\top \theta,$

which retains the structure of a linear combination over learned features while allowing $\Phi(x, u)$ to be highly expressive.

This 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$.

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.

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

$\hat{c}_{u,\theta}(x) = \Phi(x, u)^\top \theta,$

which retains the structure of a linear combination over learned features while allowing $\Phi(x, u)$ to be highly expressive.

This 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$.

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.

This 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.

Note 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.

In 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).

Although 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. To 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.

Regarding 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.

Consider 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.$

Recall 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.
$

\min_{w_+,w_-,s_u,s_\ell\geq 0}&\;\begin{pmatrix} -\hat{c} \\ \hat{c} \\ 0 \\ 0 \end{pmatrix}^\top \cdot\begin{pmatrix} w_+ \\ w_- \\ s_u \\ s_\ell \end{pmatrix}\\ \text{s.t. }&\begin{pmatrix} 1 & -1 & 1 & 0 \\ -1 & 1 & 0 & 1 \end{pmatrix}\begin{pmatrix} w_+ \\ w_- \\ s_u \\ s_\ell \end{pmatrix}=\begin{pmatrix} 1/2 \\ 1/2 \end{pmatrix}.
$

Recall 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

$

\min_{\hat{c}\in \{\hat{c}_1,\hat{c}_2\}}& \frac{1}{3}(||v_1||_1+||v_2||_1+||v_3||_1)\\ \text{s.t.} &\; \forall t\in \{1,2,3\}, \begin{pmatrix} 0 \\ \hat{c}(i) \end{pmatrix}\geq \begin{pmatrix} 1 \\ 1 \end{pmatrix} -v_i
$

The 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$.

Finally, 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.

Replies to initial remarks: we thank the reviewer for their remarks.

• 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

• 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.

• 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.

• 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.

• 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.

• 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.

Replies to the questions:

1. 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.

2. 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.

3. 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.

4. Theoretically, we can prove that line search with precision $\epsilon$ provides an global minimizer with precision $\epsilon$. Proof:https://imgur.com/a/LHxvfkk

5. 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.

Thank you for there insightful questions. Here are our answers in order.

1. 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.

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

$\hat{c}_{u,\theta}(x) = \Phi(x, u)^\top \theta,$

which retains the structure of a linear combination over learned features while allowing $\Phi(x, u)$ to be highly expressive.

This 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$.

2.(i). More details (including what the function phi is) are available in appendix A.18 in page 24.

2.(ii). An updated version of our experiment figure with the relative regret is available here: https://imgur.com/a/0rqF2iE The boxplots show the distribution of the performance of each method, and the curve shows the mean performance of each method.

2.(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+.

3. 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.

In 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.

This 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.

4. 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