BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning

Summary

The authors introduce BPQP, a differentiable convex optimization framework designed for efficient end-to-end learning. The core of this work lies in simplifying and decoupling the KKT matrix for the backward pass and solving it with a first-order solver to improve the overall efficiency of the module.

Strengths

1. The paper is well-organized and well-written, making it relatively easy to read. 2. The proposed strategy performs well in the experiments.

Weaknesses

1. The differences between BPQP and OptNet seem to be only reflected between Equation 3 and Equation 5. The rationale, necessity, and justification for this change may need more explanation. 2. For Equation 3, OptNet uses the interior-point method, while for Equation 5, BPQP uses ADMM. What is the motivation for using ADMM? The impact of using the interior-point method or various first-order/second-order optimization algorithms on performance (convergence, accuracy, time cost) also needs to be reflected in the experiments. 3. It is a good practice to learn from OptNet and conduct experiments on richer tasks such as Total Variation Denoising and Sudoku.

Questions

See above.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

N/A

Summary

This paper develops a technique to use deep learning models to solve convex optimization problems that offers speedups and space benefits over the current state of the art. Rather than using conventional implicit layers to predict optimal solutions, the authors consider the Karush-Kuhn Tucker (KKT) conditions for optimality in a different light in order to avoid costly and large Jacobian matrix computations. Here, they formulate this backward pass as a quadratic program (QP), which can be efficiently solved using first derivatives and requires less space and time than differentiating through the system of equations resulting from the KKT conditions. The KKT conditions are still used to form the backward pass as a QP, but solving the large system of equations is avoided.

Strengths

The BPQP framework, due to avoiding solving the linear system of equations introduced by the KKT optimality conditions, offers significant speedups versus existing differentiable layers for LP, QP, and SOC problems. This is a very relevant area of research as NN-based end-to-end optimization solutions are gaining a lot of attention for the extreme speed-ups over using conventional optimization solvers for convex programs. The comparisons show very promising results against a wide variety of other solutions, both conventional (CVXPY) and NN-based (OptNet). The reformulation of the backward pass into a format which has efficient solution algorithms rather than naively solving the linear system of equations introduced by the optimality conditions is simple but quite clever, and the results speak for themselves.

Weaknesses

I would prefer if BPQP was defined in the abstract (also, shouldn't it either be "as a Quadratic Program" or "as Quadratic Programming" to be grammatically correct?) There are quite a few grammatical errors in the paper. Not to the level of affecting readability, but the authors may want to go through and polish this. A bit nitpicky, but ADMM is not a "solver", it is an algorithm (page 2). The text in Figure 1 in the forward and backward pass is very small.

Questions

During inference, if the input to the model is actually infeasible (no solution exists that satisfies the corresponding KKT conditions), is there any indication of infeasibility produced by the model? Do the authors have an idea of how this would extend to nonconvex problems? The KKT conditions would provide local minima, but perhaps the same reformulation of the backward pass as a QP would be more complicated.

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

The authors have adequately addressed the limitations and I do not see any potential negative societal impacts.

Summary

The paper provides a novel approach for handling differentiable optimization layers when their forward corresponds to the solution to a convex constrained optimization problem. The authors show that the gradient of such a layer corresponds to the solution of a QP, thus enabling a tractable backward through the use of QP solvers (in contrast to previous approaches which require solving a linear system). The authors evaluate their proposed algorithm on synthetic data tasks and a portfolio optimization problem. The results show a significant improvement in efficiency with respect to baselines.

Strengths

The high-level story of the paper is easy to follow. The proposed idea is simple and neat. Unlike existing approaches for implicit layers, it allows for the forward and backward passes to be decoupled algorithmically, thus allowing for extra flexibility since off-the-shelf solvers can be used for solving both the forward and backward problems. The results show a significant improvement in efficiency with respect to baselines.

Weaknesses

* Although the proposed method applies when the forward passes correspond to general convex constrained optimization problems, only QPs are considered in the experiments section. Does the proposed algorithm provide as significant a speedup when the considered problem is less well-behaved? * The paper does not include any comments on the limitations of the proposed method or potential future works. Note that there is a difference between scoping (e.g. saying that the problem applies only to the convex setting) and identifying a limitation (e.g. saying that the gains of an approach are less significant as the dimension of the problem increases). * Tables 1 and 2 should include performance measures instead of just the computational time. Even if these synthetic problems are relatively trivial to solve with high precision, it is important to report the quality of the solution to ensure a fair comparison across approaches. * The paper does not include any ablation experiments. See Question 1 for a potential ablation. Minor points * The authors could do a better job at motivating the field in the introduction: in which practical context have differentiable optimization layers been used and how (concretely) have they proven more effective than alternative approaches? * Figure 1 is too small. * The main paper results are only presented through tables. Plots help illustrate the results much better. Moreover, they make it easier to identify trends (e.g. as the size of the problem changes) and make it more evident if confidence intervals overlap across methods.

Questions

1. Would the proposed method work if the forward problem is solved approximately, thus yielding an imprecise estimate of the optimal solution and Lagrange multipliers? Note that this often happens in practice due to computational cost considerations (which are the main motivation of the submission). Did the authors consider a sensitivity analysis of the precision of the solution to the forward problem? 2. Can the proposed algorithm be extended to non-convex problems?

Rating

7

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

* The authors do not mention any limitations of their work. * There is no discussion on future work. * No broader impact statement is provided in the paper.

Summary

This paper proposes BPQP, a differentiable convex optimization framework to perform efficient end-to-end learning on convex problems using KKT condition. Compared with existing OptNet baselines, BPQP achieves similar performance but much faster speed.

Strengths

1. This paper proposed BPQP, which utilizes the linearity of IFT to speed up the differential layers in an end-to-end framework. The intuition is good, and the performance of BPQP is good (2.75x faster than OptNet). 2. The paper is clearly written, and the theory part is well-explained with detailed proofs.

Weaknesses

1. The BPQP framework proposed in this paper is solely built on KKT conditions, which means BPQP can only be applied to convex end-to-end problems. However, most real-world decision-making problems are more complex and non-convex, making BPQP less applicable. 2. In the experiment section, the author only performed two experiments: one is synthetic, and the other one is the portfolio optimization problem. However, I am a little worried if only the portfolio problem is enough to showcase the effectiveness of the proposed method. Besides, the author only compared with OptNet and two-stage, ignoring the other baselines in this area. 3. Despite the clear mathematical theorem and proof of BPQP, many of the mathematical aspects are actually similar to the OptNet work, which makes the paper less novel.

Questions

My main question is: Is the portfolio experiment shown in section 5.2 enough to showcase the performance of the proposed method, or do we need more experiments? For the baseline, are the two-stage and OptNet enough, or do we still need more baselines?

Rating

7

Confidence

5

Soundness

2

Presentation

2

Contribution

3

Limitations

1. More experiments, or at least, more datasets should be included in the results section to showcase the performance of BPQP. 2. In the experiments, the author should also add more baselines to compare with.

Reply to rebuttal

Overall, I am satisfied with the author's responses. In particular, I appreciate the discussion on limitations/future work and the ablation carried out during the rebuttal. I am thus raising my score to a 7. Some minor follow-ups: --- > we have also explored Linear Programming (LP) and Second Order Cone Programming (SOCP) in our Simulated Constrained Optimization experiments. The setting I have in mind is problems where the objective function is not quadratic (or linear), but still convex. --- > Thank you for highlighting this oversight. The performance and limitations of BPQP largely depend on the choice of solver, as the framework completely decouples the forward and backward pass processes. As indicated in Table 1, while the forward pass time dominates the total computing duration for large-scale problems, the backward pass—formulated as a straightforward QP problem—is relatively quick to solve, showcasing our method's strength. However, both the efficiency and accuracy of BPQP are still contingent on the solver's capabilities. This point makes sense. The authors might want to emphasize this explicitly in the paper.

Response to rebuttal

Thank you to the authors for responding to my comments. I'm glad to hear they have thought of these issues arising, and even if infeasible inputs are unlikely, future frameworks should consider all possible inputs to be the most robust. I don't have any further questions or comments.