Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper provides a method for addressing the "prediction + programming" problem in the case where the programming problem contains a $\max(z,0)$ term in the objective. To do so, the authors rewrite the optimization problem as an unconstrained optimization problem by converting all hard constraints of the optimization problem to soft constraints in the objective. They then pick the coefficients of those soft constraints in a way that is meant to prevent constraint violations, and then relax these soft constraints via a surrogate function. They then embed the resultant approximate optimization problem within a method where some $\theta$ is output by a neural network, the approximate optimization problem is solved for that value of $\theta$, and gradients are updated by differentiating end-to-end through the approximate optimization problem. The authors demonstrate their method on three synthetic settings, and report improved performance over two-stage methods and SPO+.
main_review: The paper addresses an important prediction + programming setting, and provides an interesting surrogate objective framework for addressing it. However, one of the central motivational claims of the paper is flawed, which unfortunately compromises the premise of the paper. In additional, several of the assumptions made throughout are rather strong, and this is not properly flagged.

### Central motivational claim

The central claim on which this work is built is that existing methods cannot handle the setting where there is a $\max(z,0)$ term in the objective function. However, this setting can indeed be handled by existing methods. For instance, the class of programming problems studied can be differentiated through using cvxpylayers (see example code at the end of this review), and KKT differentiation approaches such as those proposed in OptNet [13] can also be used (by obtaining the optimal $z^\star$ via some solver, rewriting $\max(z^\star, 0) = z^\star$ or 0 depending on the value of this optimal solution, and differentiating through the KKT conditions of the resultant problem). These differentiable layers can then be directly used within the end-to-end learning approaches proposed in [9, 11] to address the prediction + programming problem.

Now, the approaches I have described above are certainly far from perfect: For instance, they are likely to be computationally expensive to train (as KKT differentiation-based approaches tend to be). In contrast, the method proposed in the present paper is potentially cheaper to train. However, this is not the axis of improvement that the paper currently aims to demonstrate (i.e., time comparisons to cvxpylayer- or OptNet-based methods are not shown). 

If the authors were to revamp the paper (both the motivation and the experiments) to address the problem of decreasing computational cost (rather than the current motivation of addressing a previously-unaddressed setting), I think this would significantly strengthen the paper (and accordingly, I would potentially be open to increasing my score).

### Assumptions

Some of the assumptions made throughout are also rather strong. While this is okay for the purposes of developing a specialized method, these should be properly flagged and described as limitations rather than being described as common circumstances:
* Line 74: The assumption that all terms in $A$ are non-negative is rather strong, in particular because encoding box constraints on $x$ (that is, $x_l \leq x \leq x_u$ for $x_l, x_u > 0$) would require the presence of negative terms in $A$. Such box constraints are rather common.
* Line 141: The assumption that the l2 norm of $\nabla f$ is bounded is also potentially rather strong, particularly in the quadratic case (Equation 3). This should be flagged and discussed.
* Line 193: It would be helpful if the definition of $P$ could be more clearly described, as it is not immediately clear from the description in the main text why $\lambda_{max}$ would be bounded in practice.

### Other comments

* Line 149: Is "active constraints at $x$" supposed to refer to all constraints that are violated by $x$? (Given that $x \not\in \mathcal{C}$, "active constraints" may not be the correct terminology.)
* Line 201: This statement should be corrected. As described above, Equation 5 can indeed be differentiated through at its optimum since the "max" operation can be replaced by either the linear term or 0 depending on the value of $x^\star$ that is obtained. This rewritten problem can then be differentiated through via the implicit function theorem.

### Sample cvxpylayers code

As mentioned above, here is some sample code for setting up a differentiable layer for Equation 2 via cvxpylayers. 

	import cvxpy as cp
	import torch
	from cvxpylayers.torch import CvxpyLayer
	import numpy as np

	# Random seeds for param generation (picked so the problem is feasible)
	np.random.seed(0)
	torch.random.manual_seed(6)

	# Initialize problem vars and params
	n, m, k = 2, 3, 5
	x = cp.Variable(n)
	theta = np.random.randn(n)
	# pick alpha as the ones vector (see "sum" in the objective)
	A = cp.Parameter((m, n))
	b = cp.Parameter(m)
	B = cp.Parameter((n, n))
	c = cp.Parameter(n)
	C = cp.Parameter((k, n))
	d = cp.Parameter(k)

	# Set up cvxpy problem
	objective = cp.Maximize(theta@x - cp.sum(cp.maximum(C@x + d, 0)))
	constraints = [A@x <= b, B@x == c, x >= 0]
	problem = cp.Problem(objective, constraints)
	assert problem.is_dpp()  # True

	# Create cvxpylayer
	cvxpylayer = CvxpyLayer(problem, parameters=[A, b, B, c, C, d], variables=[x])
	A_tch = torch.randn(m, n, requires_grad=True)
	b_tch = torch.randn(m, requires_grad=True)
	B_tch = torch.eye(n, requires_grad=True)
	c_tch = torch.ones(n, requires_grad=True)
	C_tch = torch.randn(k, n, requires_grad=True)
	d_tch = torch.randn(k, requires_grad=True)

	# Solve the problem
	solution, = cvxpylayer(A_tch, b_tch, B_tch, c_tch, C_tch, d_tch)

	# Compute the gradient of the sum of the solution with respect to problem params
	solution.sum().backward()   # works
limitations_and_societal_impact: As mentioned in my main review, I think the authors could do a better job flagging some of the assumptions they make and describing their significance.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper develops a surrogate function with closed-form solution for objective functions with "soft constraints," here defined as those with the term $\alpha^T \\max\\{0,z(x)\\}$ for affine $z$, component-wise $\\max$, and $\alpha > 0$. The goal is to apply such functions within the context of smart "predict-then-optimize" (SPO) by also relaxing the hard constraints with a sufficiently large penalty $\alpha$. To develop their surrogate, the authors evaluate bounds on the utility gained when violating the soft constraints using primarly a geometric perspective, specifically evaluating the angles or corners of infeasible points with respect to the convex hull of feasible solutions (and related properties). Numerical results compare their approach with the standard SPO+ loss function and a DF metric for portfolio optimization.
main_review: **Originality**

The paper is part of a current stream of papers that investigate different strategies to smooth the underlying loss function within the SPO framework, which is itself a quite challenging problem. Within that context, I found the polyhedral perspective provided by this paper quite interesting and, to the best of my knowledge, original as well. The general ideas are quite relevant given that $\\max\\{0,z\\}$ functions are quite pervasive, e.g., in A.I. and operations.


**Quality**

Overall, I believe the paper is well structured but I do have some few technical concerns. More specifically:

1. When softening hard constraints and calculating their penalty, the terms involve angle, smallest corner calculations, and other complex functions such as $\\sin$. I wonder if there could be challenges associated with numerical stability? Furthermore, how time consuming was calculating such angles and auxiliary parameters for the instances tested?

2. Many of the bounds are defined as within function classes $O(\\cdot)$. From my understanding of the structural results, the actual functions to be used in the penalties could be associated with large constants (e.g., due to $c_1$, l.651, in pg.18, supplemental material), which could make the approximation too weak. Perhaps I misunderstood, but I believe some further discussion on how to prescribe the bounds precisely could be beneficial here, including some intuition on the quality of these bounds.


**Clarity**

The main text is well-written and the supplemental material is comprehensive. My few comments here are as follows.

3. It would be best if the assumptions are more clearly described in the text. In particular, non-negativity of $\alpha$ could not necessarily be always the case (e.g., in Benders or cut-generation linear programs, where similar ideas could be useful). Furthermore, I believe the constant $E$ is an important factor for the development of the results and it could be emphasized further.

4. The proofs were overall rigorously written and are clear to the best of my analysis. The auxiliary figures are extremely helpful. However, Theorems 3 and 5 are relatively more difficult because many statements are posed more vaguely (e.g., in 591-595, how to project the cone to its tip?). I would suggest just to extend them somewhat with more hand-holding and appropriate formalism, if possible.

5. Some statements in the main require references (or at least authors could cite related papers earlier) - for example: "modern solvers ... can already efficiently find optimal for most large scale programming problems," or "it may model overhead of under-provisioning, over-provisioning of goods." 

**Significance**

In my view, this is a paper that provides a clear and useful contribution and may attract a broader interest within the A.I. community. The idea of "softening" constraints by exploiting polyhedral corners/angles is original within the context of SPO, to the best of my knowledge. Nonetheless, the calculation of the softening constraint is more involved and some practical aspects (quality of the bounds, complexity, and numerical stability) requires some more clarification, which I believe can be easily addressed by the authors. 

**Minor Points**

- The references have a few errors. For example, there is no journal information in [10], reverence [7] should be updated with CPLEX v20 (2021) etc. 
- "more loyal" --> "closer?"
- There is often a missing "the" prior to the word "programming" throughout the text.

limitations_and_societal_impact: Not discussed in the text. The paper could greatly benefit from a discussion concerning the limitations and trade-offs of their methodology.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes a new method to integrate soft constraints in the predict+programming paradigm that focuses on mathematical programming models with a prediction component that needs to be considered during optimization/solving.
The new method works by reformulating the problem into piecewise linear constraints and then optimizing a surrogate for the original problem.
A theoretical analysis and motivation is provided as well as an experimental evaluation that underlines the effectiveness of the method.
main_review: As a disclaimer, I'm broadly familiar with predict+optimize, but am not a specialist in this area of mathematical programming and did not follow the theory in detail.
However, the methodological approach seems sound and well supported by the theory.

I was wondering why the methodology was framed as "prediction+programming" rather the, in my view, more established "predict+optimize". Also, even though mathematical programming is an established term, using "programming" might lead to some confusion in regards to software programming.

In general, I think this is solid work and of relevance for this area.
limitations_and_societal_impact: There is no dedicated discussion of societal impacts, but it is also not particularly relevant in this work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper presents an approach for "predict, then optimize" problems that is amenable to derivative-based learning methods. It involves converting hard constraints into soft constraints (i.e. implicitly enforced through objective penalization). The main theoretical contributions are bounds on the magnitude of objective change that can be attributed to infeasibility with respect to the original hard constraints.
main_review: The paper is quite difficult to read. The theoretical results are presented informally in the body of the paper to the point of confusion, and it is difficult to glean what the conclusions from them should be. As such, it is difficult to assess the technical soundness of the work. As one example, the second condition on H (line 137) is written confusingly and informally (what does "increments" mean in this context? How do you formally measure "gain" with respect to violation of the linear constraints?). As a second, the statement of Lemma 1 is also informal--what is the maximin discussed taken with respect to? As a third, Corollary 4 does not formally define what "cardinal constraints" means (should be "cardinality constraints"?) and what their implications are for the structure of the problem data. As a fourth, the theoretical results in Section 3 only seem to indicate asymptotic guidance as to the maximum penalty weights to be considered, not how they should actually be set in practice, let alone to guarantee optimality w.r.t. the true problem. This vagueness continues in Section 4 and the Appendix, where (contra 3(b) in the checklist) the penalty terms gamma are described only in asymptotic notation; the reader is not told how these values are actually set in the experiments.

The approach presented to smooth the max constraints is not particularly surprising, though I have no reason to question its novelty. The computational results seem promising, though the lack of details about the implementation make it difficult to see how readers would glean insight into how to take these results and apply to new problems or extend them.
limitations_and_societal_impact: I do not feel that the authors adequately confront the limitations of their work. Most of the results restrict the problem data to be nonnegative. They claim that "constraint parameters usually represent weights, quantities or their thresholds, and thus are always nonnegative." This is overly broad--there are many, many "realistic" optimization problems that do not satisfy this condition. The wide swath of network optimization problems are just one set of examples. This restriction is a reasonable enough one as many problems _do_ satisfy it, but the paper should be suitably rewritten to soften its claims.

There is no direct negative societal impact of the work.
review_title: null

Meta-review: A majority of reviewers recommend acceptance although, notably, a majority of reviewers also raise clarity concerns with the paper.  For the most part, the reviewers felt that these concerns were satisfactorily addressed in the significant rebuttal discussion.  The reviewers request the authors to revise the paper in light of the reviews and rebuttal discussion, which all reviewers agree would be manageable within the time frame for revision of accepted NeurIPS papers.
Decision: Accept (Poster)