Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 
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:

- 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? 
- 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}).

*Update after author response* I have read the author response and I am satsfied with the answers. Hence, I maintain my score for acceptance.
limitations_and_societal_impact: The authors have adequately addressed the limitations of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

I 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?

limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.  
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. 

Although 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. 
	1. 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?
	2. 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. 
-------------------
Considering the authors' response, I decide to change my score from 5 to 6.
limitations_and_societal_impact: I don't think that this work will have negative societal impact.
review_title: null

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)