Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: ### quality
Good

### clarity
Good

### originality 
Carefully combines a number of non-trivial methods from recent related work. Clever new idea for how to guarantee constraint satisfaction of the output of the network.

### significance
Concrete contribution to the field of learnable 'optimizers.' The applications are well-motivated and it appears that deploying the method for the ACOPF could have immediate impact.

### Pros 
Well executed + motivated. Careful ablation analysis.

### Cons 
The results may be more impactful and interesting in an operations research venue. The gap between the learned optimizer and the exact QP solver is non-trivial for some problems. This may be a deal-breaker for deployment.

## Comments
### Satisfying inequality constraints = 

It was unclear to me why the gradient descent procedure is guaranteed to converge. Is this assuming that the constraint set is convex?

I was confused as to why the equality and inequality constraints are treated so differently. Why have a black box solver with implicit function theorem differentiation for equality constraints vs. back-propping through unrolled gradient descent for the inequality constraints?


FYI, in principle, the optimization in 3.2 doesn't need to be in z space. It could be in hidden space of the neural network that outputs z. In future work this might allow local search to move better when seeking to enforce the inequality constraints.

### Benchmarking 
4.1: Does making Q diagonal change the difficulty of the optimization problem? Is this a realistic setting?


### The 'Optimizer' Baseline=
Table 2: The gap between the exact QP optimizer and DC3 is non-trivial, with a scale that is often bigger than the gap between DC3 and some of the other deep net baselines. The claim "we find that DC3 achieves comparable objective" may be over-stated. Perhaps you should do a paired analysis across optimization problems. When comparing method X to method Y, on how what fraction of problems does X outperform Y?

Can the 'Optimizer' baseline be warm-started? If so, how fast would it be to warm start using DC3. This might help close the speed gap between 'Optimizer' and DC3 while achieving higher quality solutions.

## Minor Comments

I initially found (1) confusing because I thought that part of the learning problem was to learn the dependence of the optimization problem on x. This occurs, for example, in the field of structured prediction, where we have a labeled dataset of (x, y) pairs. You should update to emphasize that this is not the case.

In algorithm 1, line 10, aren't you doing gradient descent, not stochastic gradient descent? It should be GD.

In Table 3, DC3, \leq train matches DC3. Why do you expect this is true?


Page 5: I would have preferred to see the discussion of the very relevant related work in the main text and not relegated to an appendix.

review_title: Interesting, well-motivated method

final_score: rating: 4: Ok but not good enough - rejection
review_content: Strength:
+ The paper proposes a general framework to deal with constraints in optimization problems using neural networks. In my opinion this is an important problem since there exists no standard method in many existing deep neural network frameworks to deal with constraints, which are also inapplicable even if the constraints are only slightly nontrivial. The paper proposes to deal with equality and inequality constraints differently which may be often easier in large scale settings.
+ Comparison with CVXPY indicates that the algorithm can indeed be practically useful, and applicable for a broad spectrum of problems (this is not discussed in the paper).

Weakness:
- While the related work from the recent years has been discussed to some extent, the paper fails to show how the technique proposed is better than them. The main idea of the paper has a rich history in optimization literature and is referred to as "elimination" of constraints. See Chapter 15 in Numerical Optimization by Nocedal & Wright (2006), and references within for more details. From my understanding, the discussion in Amos & Kolter (and their implementation) makes it clear that a reduced/partial Cholesky factorization is sufficient. This is equivalent to the completion procedure suggested here. Moreover, the correction procedure simply reduces a penalized form of constraints, and is not a projection operation. To this end, the paper does not have any discussion regarding the convergence aspects of the framework which is a crucial subject for this paper.
- For a generic optimization framework (proposed), the paper only provides experiments on well studied optimization problems - all the experiments provided in the paper are with quadratic programming problems which are known to be easy both in theory and practice. It will be interesting to see how the framework performs in different problems. Also, it is not clear whether the experimental benefits will carry to other networks that are used in practice. Indeed, running experiments on all known network architectures is feasible but showing experiments on a few more relevant architectures can add a lot of value to the paper and readers.
After response: While some of my concerns were cleared after the response, the experimental evaluations presented do not sufficiently support the claim that the method can handle nonlinear constraints. 

review_title: The paper proposes a learning based framework for the solving optimization problems with fixed equality and inequality constraints in the formulation. Experiments on quadratic programming instantiated with synthetic data and on AC optimal power flow problems are presented for the proposed framework.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper proposes a method to strictly enforce hard constraints during a neural network, without compromising differentiability. The method has two stages 1) From a smaller set of predicted variables, compute the remaining ones so that equality constraints are satisfied; 2) Take a few gradient steps (w.r.t soft constraint) in case inequality constraints are violated. They perform experiments on synthetic and also somewhat applied instances of quadratic programs. The results look very promising.

While most of this review will focus on the negative aspect, I want to begin by stating that I like the paper very much.

I think it solves an important problem (from a fundamental standpoint but with potentially large impact), it solves it with a method that is non-trivial, yet quite simple (both of which are positives) and shows performance clearly better than that of naive -- but popular -- baselines. The writeup is very nice and the experiments are sufficient.

Having said all of that, I cannot recommend acceptance of the paper in its current stage. In several places, the paper claims to have orders-of-magnitude faster runtimes than standard solvers. It is even the only claim of the paper appearing in boldface. Since the time measurement methodology is not described in the paper, I went into the code attached to the submission. Below is a list of reasons why I believe the current methodology is flawed and does not permit making strong claims from the paper.

- CVXPy was never developed to be a fast solver. I checked this with the CVXPy authors and often times the solver is not even the computational bottleneck.
- Even if other bottlenecks are factored out of CVXPy, there is an option to use an almost-SOTA QP solver on the backend with prob.solve(solver=cp.OSQP), which the authors **do not use**. For these two reasons, it would probably be better to compare against the freely available OSQP directly, without incorporating CVXPy -- (I feel, CVXPy, in general, shouldn't be promoted as a baseline for runtimes)
- I didn't go through all the code but the time measurements I found were around large blocks of code, not the pure runtime of the solvers. This leaves a lot of room for inaccuracies.
- The baselines optimizers do not enjoy any parallelization over the instances. On the other hand, the authors write (in a footnote on page 11) that their method was timed with *full parallelization* (all instances in one batch). **This is massively unfair to the baseline** and **may fully explain the orders of magnitude difference in runtimes**.
- Runtime of its own is a bit of a compromised quantity due to hardware (cpu/gpu) differences, maybe FLOPS would be fairer (but I understand it might not be feasible)

There are two ways forward:

a) The authors remove/strongly-tone-down all claims about runtimes. In this case, I am ready to dramatically improve my evaluation as I believe the paper is safely above the acceptance threshold even without them.

b) The authors insist on claims about runtime. If this is the case, the authors need to address the points made above, update the results, and add a section that demonstrates the soundness of the methodology (possibly into supplementary). In such a case, I am happy to reevaluate but I will still insist on a proper justification of the claims made in boldface.
review_title: Strong paper but the central claim is compromised

final_score: rating: 7: Good paper, accept
review_content: There has been an increase of works using deep neural networks to heuristically predict solutions to constrained optimization problems. However, these methods cannot generalize to arbitrary constraints.  In this paper, the authors propose a method to build neural networks that output vectors that satisfy hard equality and inequality constraints. They do this by first having the network predict the underdetermined part of the system defined by the equalities, then doing a series of gradient steps to project the solution onto the space delineated by the inequalities. They evaluate on synthetic quadratic programs and problems derived from a AC power flow application.

Prior to this work I could see two ways of doing what they propose. 

A) If the constraints are linear, then Frerix et al. (2020) propose to compute the Minkowski-Weyl decomposition of the polyhedron of constraints, and to have the neural net output the coefficients in the resulting basis. Computing the MW decomposition is very expensive (both in theory and in practice), but once it is computed, enforcing the constraints is automatic.

B) Alternatively, if the constraints are (disciplined) convex, one could use a differentiable convex layer as last layer, e.g. using the method of Agrawal et al. (2019) with a somewhat arbitrary choice of objective function. For example, it could be a quadratic program layer (as in the preceding work of Amos and Kolter (2017), where a neural net with a final QP layer is used to output soft solutions to Sudokus, which the authors do cite). In fact when constraints are convex something very similar to this paper can be done with this approach, where a neural net would predict a solution, and a final QP layer would find the point that satisfies the constraints that is the closest in L2 distance with the initial neural net guess.

The current paper discusses briefly works related to method B in the "Implicit layers" paragraph of Section 2, without discussing how it can accomplish what they aim to do, nor compare against it. It is a direct competitor when constraints are convex. As for method A, it is neither cited nor compared against. Against, this is a direct competitor when constraints are linear.

So in what way does the current approach compare to these previous ones? The main advantage I see is that the method can be applied to nonconvex problems. Of course, this doesn't mean it will necessarily do well - the Newton's method step for the equality constraints or the first-order projection for the inequality constraints might not converge. There is no miracle and probably this method won't be workable on nonlinear constraints that are too wild. But at least, it seems it does converge for the nonconvex "ACOPF" problem of the experiments, so there seems to be some use-case. I think this advantage (the method can be applied to arbitrary nonlinear constraints) should be emphasized more, and a discussion of the probable limitations should be included as well. In particular, when more assumptions are put on the constraints (e.g. linearity), there are probably better options than first-order methods.

Regarding the timings in the experiments: all the machine learning methods use a GPU, so it would be interesting to compare against a baseline solver that can use a GPU when possible as well. For example, for the QP, the qpth library of Amos and Kolter (2017) has the entire QP solver implemented on CUDA - this might make a difference in speed.

Overall, my opinion is that the paper does nothing groundbreaking, but has the quality of being the first method (as far as I know) to propose enforcing hard equality-inequality constraints on the output of a neural net, which is an obstacle right now in extending recent work on learning heuristics for optimization problems. The literature review definitely has to be expanded however, to explain that when constraints are linear and convex respectively, the works of Frerix et al. (2020) [method A] and Agrawal et al. (2019) [method B] are competitors. Moreover, more discussion on the advantages and inconvenients of the approach is necessary (i.e. that the method is very general, but probably inefficient on more structured problems, and yet probably can't work on constraints that are too wild). But otherwise, the core concept of the paper sounds sound to me, and the experiments, although minimal, are I think correctly made (several seeds, etc.) I also appreciate that code was provided. So I tend towards weak acceptance of the paper.

In case this paper is rejected, my recommendation to the authors would be strengthen the experimental section. First, since comparisons on QPs are presented, I would have liked to see comparisons against these methods. I think comparisons on another nonconvex problem would be a must as well. Also comparisons in a "predict-then-optimize" setup (e.g. see Elmachtoub and Grigas 2017, Donti et al. 2017, Wilder et al. 2019, Vlastelica et al. 2019) would be very welcome, since this is a setup where neural networks have tremendous potential. This would make for a much stronger paper.


References

[1] Frerix, T., Nießner, M., & Cremers, D. (2020). Homogeneous linear inequality constraints for neural network activations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (pp. 748-749).

[2] Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., & Kolter, J. Z. (2019). Differentiable convex optimization layers. In Advances in neural information processing systems (pp. 9562-9574).

[3] Amos, B., & Kolter, J. Z. (2017). Optnet: Differentiable optimization as a layer in neural networks. arXiv preprint arXiv:1703.00443.

[4] Elmachtoub, A. N., & Grigas, P. (2017). Smart" predict, then optimize". arXiv preprint arXiv:1710.08005.

[5] Donti, P., Amos, B., & Kolter, J. Z. (2017). Task-based end-to-end model learning in stochastic optimization. In Advances in Neural Information Processing Systems (pp. 5484-5494).

[6] Wilder, B., Ewing, E., Dilkina, B., & Tambe, M. (2019). End to end learning and optimization on graphs. In Advances in Neural Information Processing Systems (pp. 4672-4683).

[7] Vlastelica, M., Paulus, A., Musil, V., Martius, G., & Rolínek, M. (2019). Differentiation of blackbox combinatorial solvers. arXiv preprint arXiv:1912.02175.

---

Edit after rebuttal: I am satisfied with the changes to the paper and increase my score to an accept.
review_title: Not very pretty, but (to my knowledge) first method to deal with arbitrary nonlinear constraints

Meta-review: The paper proposes an approach for solving constrained optimization problems using deep learning. The key idea is to separate equality and inequality constraints and "solve" for the equality constraints separately. Empirical results are given for convex QPs and for a non-convex problem that arises in AC optimal power flow.
There was much discussion of this paper between the reviewers and the area chair. THe key question was whether the empirical evaluation is sufficient to convince that the method is more effective than existing solvers. The current experiments do not show that the method achieves better solutions than existing solvers. For the convex case this is to be expected since solvers are optimal. But in the non-convex case, it would have been nice to see that the method indeed can find better solutions.
This leaves the advantage of the method in its speedup over existing methods. However, as the authors acknowledge, it is possible that this speedup is due to better use of parallelization than the methods they compare to. It is true that deep learning is particularly easy to parallelize, but this is not impossible for other methods (e.g., for linear algebra operations etc).
Thus, taken together the empirical support for the current method is somewhat limited. The method itself does make sense, and this was indeed appreciated by the reviewers. 


Decision: Accept (Poster)