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

Venue: NeurIPS_cc_2024_Conference
Published: 2024-04-24 11:52:19

Abstract: Data-driven decision-making processes increasingly utilize end-to-end learnable deep neural networks to render final decisions. Sometimes, the output of the forward functions in certain layers is determined by the solutions to mathematical optimization problems, leading to the emergence of differentiable optimization layers that permit gradient back-propagation.
However, real-world scenarios often involve large-scale datasets and numerous constraints, presenting significant challenges. Current methods for differentiating optimization problems typically rely on implicit differentiation, which necessitates costly computations on the Jacobian matrices, resulting in low efficiency.
In this paper, we introduce BPQP, a differentiable convex optimization framework designed for efficient end-to-end learning. To enhance efficiency, we reformulate the backward pass as a simplified and decoupled quadratic programming problem by leveraging the structural properties of the Karush–Kuhn–Tucker (KKT) matrix. This reformulation enables the use of first-order optimization algorithms in calculating the backward pass gradients, allowing our framework to potentially utilize any state-of-the-art solver. As solver technologies evolve, BPQP can continuously adapt and improve its efficiency.
Extensive experiments on both simulated and real-world datasets demonstrate that BPQP achieves a significant improvement in efficiency—typically an order of magnitude faster in overall execution time compared to other differentiable optimization layers. Our results not only highlight the efficiency gains of BPQP but also underscore its superiority over differential optimization layer baselines.

Main paper: 
 introduction: 
 Data-driven stochastic optimization often relies on a two-stage solution: first, it reduces uncertainty by predicting key unknown parameters based on available contextual features, then it utilizes these predictions for downstream constrained optimization. The predict-then-optimize paradigm Elmachtoub & Grigas (2022); Wilder et al. (2019) ; Liu & Grigas (2021) integrates these two stages, enabling end-to-end training to directly minimize regret -the difference between the decision made from the prediction and the optimal decision in hindsight Kotary et al. (2021) ; Mandi et al. (2020) . This paradigm, and closely related data-driven optimization methods Agrawal et al. (2019b; a) ; Amos & Kolter (2017) , have proven effective in various applications. Here, we focus on convex optimization because of its wide applications in portfolio optimizationWilder et al. (2019) , control systemsGuo & Wang (2010 ), signal processingMattingley & Boyd (2010) , and more.Training such an end-to-end model necessitates the incorporation of external differentiable convex optimization layers into the training loop of a machine learning (ML) model. Optimization problems typically do not have a general closed-form solution and require more sophisticated solutions. These solutions can be categorized into explicit and implicit methods based on whether an explicit computational graph is constructed. Explicit methods Domke (2012) ; Blondel et al. (2021) ; Foo et al. (2007) ; Sun et al. (2022) unroll the iterations of the optimization process, incurring additional costs. On the other hand, implicit methods utilize the Implicit Function Theorem to derive the gradients. Some of them Amos & Kolter (2017) ; Agrawal et al. (2019a; b) are designed for specific problems, which restrict the options for forward optimization and deteriorates efficiency. On the other hand, Directly solving the Linear system is expensive Backward Pass as QPs (BPQP) 1) Reformulate the linear system as a QP 2) With , convert active inequalities to equalities and remove inactive ones.Employ a first-order solver by default Decision Error (Regret)The forward pass and backward pass are decoupled theoretical equivalencepredicted key parameters customizable customizableFigure 1 : The learning process of BPQP: the machine learning model outputs key parameters ŷ and then generates the optimal decision z ⋆ in the forward pass; the backward pass propagates the decision error to the machine learning model for end-to-end learning; the process is accelerated by reformulating and simplifying the problem first and then adopting efficient solvers. other approaches Gould et al. (2021) ; Blondel et al. (2021) propose more general solutions but are not efficient in the backward pass. There is still plenty of room for improvement in terms of efficiency. To enable rapid, tractable differentiable convex optimization layer and further expand the capabilities of the predict-then-optimize paradigm, we propose a general, first-order differentiable convex framework for large-scale end-to-end learning, namely BPQP. Specifically, we simplify the backward pass by reformulating it into a simpler QP problem, which we refer to as the Backward Pass as a Quadratic Programming (BPQP). This decouples the forward and backward passes and creates a framework that can leverage existing efficient solvers (with the first-order solver, Alternating Direction Method of Multipliers (ADMM) Stellato et al. (2020) , as the default) that do not require differentiability in both passes. Simplifying and decoupling the backward pass significantly reduces the computational cost in both the forward and backward passes. This key idea is summarized in Fig. 1 .Our proposed framework has several theoretical and practical contributions:Efficient Gradients Computation: Empirically, BPQP significantly improves the overall computational time, achieving up to 21.17×, 16.17×, and 1.67× faster performance over existing differentiable layers on 100-dimension Linear Programming, Quadratic Programming, and Second Order Cone Programming, respectively. Furthermore, when applied to large-scale real-world portfolio optimization, BPQP enhances the Sharpe ratio from 0.65(±0.25) to 1.28(±0.43) compared to widely-adopted methods designed for the two-stage approach.Flexible Solver Choice: BPQP accommodates any general-purpose convex solver to integrate the differentiable layer for end-to-end training. In addition, we propose a specialized method for the backward pass: Backward Pass as Quadratic Programming (BPQP). This method leverages structural traits such as sparsity, solution polishing Stellato et al. (2020) , and active-sets Wolfe (1959) for efficient and accurate gradients computation. The method uses Quadratic Programming (QP) to avoid the inversion of the KKT matrix and enables large-scale gradients computation via the Alternating Direction Method of Multipliers (ADMM). This flexibility in solver choice allows for better matching of solver capabilities with specific problem structures, potentially leading to improved efficiency and performance. 
related works: 
 Explicit methods Optimization problems typically do not have a general closed-form solution formula that expresses the decision variable in terms of other parameters. To address this challenge, explicit methods Domke (2012) ; Blondel et al. (2021) ; Foo et al. (2007) unroll the iterations of the optimization process and use the decision variable from the final iteration as a proxy solution for the optimization problem. This constructs an explicit computational graph from the parameters to the proxy parameters. Typically, these methods are designed for unconstrained optimizations. Applying them directly to constrained optimizations is computationally expensive because it requires project-ing decision variables into a feasible region. Alt-Diff Sun et al. (2022) is a novel unrolling solution that decouples constraints from the optimization and significantly reduces the computational cost. While advanced unrolling methods continue to improve their efficiency, they require an additional cost in the unrolled computational graph that increases with the number of optimization iterations.In contrast, implicit methods use the Implicit Function Theorem to relate the decision variable to other parameters. These methods specifically apply the theorem to KKT conditions in convex optimization. Some works are designed for specific problems, which limits the choices of forward optimization and deteriorates efficiency. OptNet Amos & Kolter (2017) presented a differentiable batched-GPU QP solver. diffcp Agrawal et al. (2019a; b) considers computing the derivative of a convex cone program by implicitly differentiating the residual map for its homogeneous selfdual embedding. Open-source convex solver CVXPY Diamond & Boyd (2016) adopts a similar method and computes gradients by SCS O'donoghue et al. (2016) . Another line of work uses more general solutions, which are not efficient enough to handle the backward pass. Gould et al. (2021) decouples the forward and backward pass. JaxOpt Blondel et al. (2021) proposes a simple approach to adding implicit differentiation on top of any existing solver, which significantly lowers the barrier to using implicit differentiation. Our work, BPQP, is based on implicit methods. First, we simplify the backward pass by reformulating it into a simpler decoupled QP problem. Problem simplification and decoupling greatly reduce the computational cost in both the forward and backward passes.Learning-to-optimize Existing work on Learn-to-Optimize trains an approximated solver network (e.g., Donti et al. (2021) ; Cristian et al. (2023) ; Kong et al. (2022) ) . This approach provides solutions as efficient as closed-form solutions. However, these methods either have low accuracy or only perform well in specific scenarios, which is outside the scope of our research. Therefore, the Appendix A.6 includes additional discussions about approximate and scenario-specific methods. 
predict-then-optimize framework: 
 In this section, we formally describe the predict-then-optimize framework for stochastic decision making problems. We assume that the problem of our interest has convex objective and constraints, but the key parameter y ∈ R p is not observable when the decision is made. For each optimization instance, a prediction of y is required to solve the downstream deterministic optimization problem. Specifically, let (x ∈ X , y ∈ Y) ∼ D denote standard input-output pairs drawn from the real and unknown distribution D. Suppose a ML model N , parameterized by θ, with input features x is trained to generate such a prediction ŷ= N (x; θ) = E y∼p θ (y|x) [y], namely ŷ ∈ R p = E[y|x].Let z ŷ ∈ R d denote the decision variable of the corresponding optimization relying on random parameter ŷ. The parameterized convex optimization can be formalized as follows:EQUATIONFor any given ŷ, f ŷ (•) : R d → R the C 2 continuous convex objective function, and h ŷ (•) : R d → R n , g ŷ (•) : R d → R m the n-dimension equality constraints and m-dimension inequality constraints representing the feasible region. h and g are both C 2 continuous convex functions. As we demonstrated, the optimal decision z ⋆ is a random variable depending on ŷ, z ⋆ ŷ∼p θ (y|x) . To implement an end-to-end approach training for N , upon observing the optimal decision z ⋆ y relative to the true instantiation of x and y, we update the parameterized model N (x; θ) correspondingly, minimizing regret. The overall end-to-end training procedure can be viewed as maximizing posterior probability given decision error and prediction error.p(θ|regret, y, x) ∝ p(regret|y, x, θ)EQUATIONIdeally, our goal here is to use supervised learning to predict the unspecified parameter ŷ from empirical data in ways that the decisions made from estimation z ⋆ ŷ match the best decisions taken in hindsight z ⋆ y , i.e., regretEQUATIONGiven the realized parameter y, Chen et al. (2022) found the exact optimization decision error empirically to be a narrow (Dirac-like) target distribution centered at the ground truth regret = 0. The rest of the terms above can be viewed as prior distribution forms the classic prediction error of which we choose simple MSE loss, yielding the simplified end-to-end (predict-then-optimize) loss, weighted by constant β ∈ (0, 1):EQUATION)Comparison to Two-stage Approach The two terms in Eq. ( 4) are concerned with decision error and prediction error. The former is often approximated as surrogate loss due to the complexity of computing regret in previous work Elmachtoub & Grigas (2022); Wilder et al. (2019) . But surrogate loss is sub-optimal and often cannot handle learning feasible solutions of complex constraints over thousands or even hundreds of dimensions. Relatively, the traditional Two-stage approach divides stochastic optimization into two separate stages: first train a prediction model on y and then solve the optimization problems z ⋆ E[y|x] separately. The shortcoming of the Two-stage approach is that it does not take the effect on the optimization task into account. Training to minimize Two-stage loss (prediction loss) is not guaranteed to deliver better performance in terms of the decision problem Mandi et al. (2020) ; Ifrim et al. (2012) . As a special case of end-to-end loss, we conclude that the Two-stage approach minimizes a lower bound of the total end-to-end loss and does not necessarily result in the minimization of regret.L 2stage = E x,y∼D [∥y -ŷ∥ 2 ] ≤ L e2e .(5)One major challenge of adopting the predict-then-optimize approach is to backpropagate losses through the argmin operator, namely the backward pass.EQUATIONWe consider a general convex problem in Eq. (1). To compute the derivative of the solution z ⋆ to parameter y, OptNet Amos & Kolter (2017) differentiates the KKT conditions using techniques from matrix differential calculus. Following this method, the Lagrangian is given by (omitting y),EQUATIONwhere ν ∈ R m and λ ∈ R n , λ ≥ 0 respectively denotes the dual variables on the equality and inequality constraints. The sufficient and necessary conditions for optimality of Eq. ( 1) are KKT conditions. Applying the Implicit Function Theorem (IFT) to the KKT conditions and letP (z ⋆ , ν ⋆ , λ ⋆ ) = ∇ 2 f (z ⋆ ) + ∇ 2 h(z ⋆ )ν ⋆ + ∇ 2 g(z ⋆ )λ ⋆ , A(z ⋆ ) = ∇h(z ⋆ ) and G(z ⋆ ) = ∇g(z ⋆ ). Let q(z ⋆ , ν ⋆ , λ ⋆ ) = ∂(∇f (z ⋆ ) + ∇h(z ⋆ )ν ⋆ + ∇g(z ⋆ )λ ⋆ )/∂y, b(z ⋆ ) = ∂h(z ⋆ )/∂y and c(z ⋆ , λ ⋆ ) = ∂(D(λ ⋆ )g(z ⋆))/∂y. Then the matrix form of the linear system can be written as:EQUATIOND(•) : R m → R m×m represents a diagonal matrix that formed from a vector and z ⋆ , ν ⋆ , λ ⋆ denotes the optimal primal and dual variables. Left-hand side is the KKT matrix of the original optimization problem times the Jacobian matrix of primal and dual variables to the omitted parameter y, e.g., ∂z ⋆ ∂y ∈ R p×d . Right-hand side is the negative partial derivatives of KKT conditions to the y.We can then backpropagate losses by solving the linear system in Eq. ( 8). In practice, however, explicitly computing the actual Jacobian matrices ∂z ⋆ ∂y is not desirable due to space complexity; instead, Amos & Kolter (2017) products previous pass gradient vectors ∂L ∂zEQUATION)And the direct gradients∇ y L ∈ R p = [q(z ⋆ , ν ⋆ , λ ⋆ ), c(z ⋆ , λ ⋆ ), b(z ⋆ )][z, λ, ν] ⊤ . 
backward pass as qps: 
 Our method solves Eq. ( 9) using reformulation method. Consider a general class of QPs that have d decision variables, n equality constraints and m inequality constraints:EQUATIONwhereP ∈ S d + , q ∈ R d , A ∈ R n×d , b ∈ R n , G ∈ R m×d and c ∈ R m .KKT conditions write down in matrix form:EQUATION)We note that Eq. ( 11) is equivalent to Eq. ( 9) if and only if: (i)P = P (z ⋆ , ν ⋆ , λ ⋆ ), A = A(z ⋆ ), D( λ)G = D(λ ⋆ )G(z ⋆ ), [-q, D( λ)c, b] = [-∂L ∂z ⋆ ⊤ , 0, 0] and (ii) P (z ⋆ , ν ⋆ , λ ⋆ ) is pos- itive semi-definite.As the backward pass solves after the forward pass, we can change inequality constraints to an accurate active-set (i.e., a set of binding constraints) of equality conditions, and then condition (i) always holds for the equality-constrained QP. From this, the following theorem can be obtainedTheorem 1 Suppose that the convex optimization 1 is not primal infeasible and the corresponding Jacobian vector ∇ y L exists. It is given by∇ y L = [q(z ⋆ , ν ⋆ , λ ⋆ ), c(z ⋆ , λ ⋆ ), b(z ⋆ )][z, λ, ν]⊤ and z, λ, ν is the optimal solution of following equality constrained Quadratic Problem:EQUATION)WhereP = P (z ⋆ , ν ⋆ , λ ⋆ ), A = A(z ⋆ ), G + = G + (z ⋆ ) and [-q, c + , b] = [-∂L ∂z ⋆ ⊤ , 0, 0].G + , c + has the same row of active-set as original inequality constraints.Though our BPQP procedure described above also applies to Jacobians with forms other than vectors, e.g., matrices, in these cases where each 1-dimension column in [z, λ, ν] ⊤ right multiply the same KKT matrix and can be viewed as QPs packed in multi-dimensions, directly calculating the inverse of the KKT matrix may be more appropriate, especially when it contains a special structure like OptNet Amos & Kolter (2017) and SATNet Wang et al. (2019) .The intuition of BPQP is that the linearity of IFT requires the KKT matrix leftmultiply homogeneous linear partial derivative variables. Theorem 1 highlights a special situation that considers gradients at the optimal point (where KKT conditions are satisfied). Generally, BPQP provides perspective to define gradients in parameter-solution space that preserves KKT norm. Let us consider a series of vectors denoting the kth iteration norm value of KKT conditions:EQUATION)Where r (k) ∈ R d+m+n the KKT conditions in kth iteration andC k ∈ R the norm value. The series {C 0 , C 1 , ..., C k } converges to 0 if the iteration algorithm is a contraction operator. Let Q (k) denote standard QP problem w.r.t. parameter P k , q k , A k , b k , G k , c k and decision variable z k . At each iteration, BPQP yields ∇ y L (k) that preserves ∥r (k) ∥ = C k . (See in Appendix A.3)The time complexity of solving such QP is O(N 3 ) in the number of variables and constraints which is at the same level as directly solving the linear system Eq. ( 9). However, reformulation as QP provides substantial structures that can be exploited for efficiency, such that (we cover them in Section 4.2) sparse matrix, solution polishing Stellato et al. (2020) , active-sets, and first-order methods, etc. Cleverly implement BPQP, experiments at fairly large-scale dimensions in practice highlight BPQP's capacity in comparison to the state-of-art differentiable solver and NNbased optimization layers. Intuitively, BPQP is more efficient than previous methods because it utilizes the convex QP structural trait in the backward pass.The solver we referenced is OSQP Stellato et al. (2020) , which incorporates the sparse matrix method and uses a first-order Alternating Direction Method of Multipliers (ADMM) method to solve QPs. We summarize OSQP here Ichnowski et al. (2021) . On each iteration, it refines a solution from an initialization point for vectors z (0) ∈ R d , λ (0) ∈ R m , and ν (0) ∈ R n . And then iteratively computes the values for the k + 1th iterates by solving the following linear system:EQUATIONAnd then performing the following updates:EQUATION)where σ ∈ R + and ρ ∈ R n + are the step-size parameters, and Π : R m → R m denotes the Euclidean projection onto constraints set. When the primal and dual residual vectors are small enough in norm after kth iterations, z (k+1) , λ (k+1) and ν (k+1) converges to exact solution z ⋆ , λ ⋆ and ν ⋆ .In particular, given a backward pass problem Eq. ( 12) with known active constraints, as stated in OSQP, we form a KKT matrix below1 :EQUATIONAs the original KKT matrix is not always inveritible, e.g., if it has one or more redundant constraints, we modify it to be more robust for QPs of all kinds by adding a small regularization parameter D(P + δI, -δI, -δI) (in Eq. ( 16)) as default δ ≈ 10 -6 . We could then solve it with the aforementioned ADMM procedure to obtain a candidate solution, denoted as t and recover the exact solution t from the perturbed KKT conditions (K + ∆K) t = g by iteratively solving:EQUATION)where tk+1 = tk + ∆ tk and it converges to t very quickly in practice Stellato et al. (2020) for only one backward-and one forward-solve. Thus our BPQP method solves backward pass problems in a general but efficient way.Below we provide examples for differentiable QP and SOCP oracles (i.e. solutions) using BPQP.The general procedure is to first write down KKT matrix of the original decision making problem. And then apply Theorem 1. Assuming the optimal solution z ⋆ is already obtained in forward pass.Differentiable QP With a slight abuse of notation, given the standard QP problem with parameters P, q, A, b, G, c as in Eq. ( 10). The result is exactly the same as OptNet Amos & Kolter (2017) since both approaches are for accurate gradients. But BPQP is capable of efficiently solving large-scale QP forward-backward pass via ADMM Stellato et al. (2020) , as shown in Section 5.1.EQUATIONAnd [z, ν, λ] solvesEQUATION)Differentiable SOCP The second-order cone programming (SOCP) of our interest is the problem of robust linear program Bennett & Mangasarian (1992):EQUATIONwhere q ∈ R d , a i ∈ R d , and b i ∈ R. With m inequality constraints in L2 norm, we give the gradients w.r.t. above parameters.EQUATIONAnd [z, ν, λ] are given by (t1 = i λ ⋆ i+ and t 0 = ∥z ⋆ ∥ 2 ) minimize z 1 2 z⊤ t 1 t 0 I - t 1 t 3 0 z ⋆ z ⋆⊤ z + ∂L ∂z ⋆ z s.t. (a ⊤ i+ + 1 t 0 z ⋆ ) T z = 0, i = 1, 2, ..., m. (22) 
experiments: 
 In this section, we present several experimental results that highlight the capabilities of the BPQP. To be precise, we evaluate for (i) large-scale computational efficiency over existing solvers on randomgenerated constrained optimization problems including QP, LP, and SOCP, and (ii) performance on real-world end-to-end portfolio optimization task that is challenging for existing predict-thenoptimize approaches.We randomly generate three datasets (e.g. simulated constrained optimization) for QPs, LPs, and SOCPs respectively. The datasets cover diverse scales of problems. The problem scale includes 10 × 5, 50 × 10, 100 × 20, 500 × 100 (e.g., 10 × 5 represents the scale of 10 variables, 5 equality constraints, and 5 inequality constraints). Please refer to more experiment details in Appendix A.4.The format of generated QPs follows Eq. ( 12) to which the notations in the following descriptions align. We take q as the learnable parameter to be differentiated and L = 1 ⊤ z ⋆ in Eq. (9). To generate a positive semi-definite matrix P , P ′ ⊤ P ′ + δI is assigned to P where P ′ ∈ R d×d is a randomly generated dense matrix, δI is a small regularization matrix, and δ = 10 -6 . Potentially, we set c = Gz ′ , G ∈ R m×n , z ′ ∈ R n to avoid large slackness values that lead to inaccurate results. All other random variables are drawn i.i.d. from standard normal distribution N (0, 1).The LP problems are generated in the format belowEQUATION)where θ ∈ R d is the learnable parameter to be differentiated,z ∈ R d , A ∈ R n×d , b ∈ R n , G ∈ R m×d , h ∈ R m and ϵ ∈ R + .All random variables are drawn from the same distribution as the QPs dataset. It is noteworthy that it contains an extra item ϵ∥z∥ 2 2 compared with traditional LP. This item is added to make the optimal solution z ⋆ differentiable with respect to θ. Without this item, P (z ⋆ , ν ⋆ , λ ⋆ ) is always zero and thus the left-hand side matrix becomes singular in Eq. ( 8). This is a trick adopted by previous work Wilder et al. (2019) . CVXPY will reformulate the problem to a cone program and can handle this issue internally. So ϵ is set to 0 for CVXPY. For other differentiable optimizers, ϵ = 10 -6 as default.SOCPs Dataset For SOCP in Eq. ( 20), we consider a specific simple case, i.e. a i = 0 ∀i and this relaxations results in m = 1. As in QP and LP, we take q as differentiable parameter and set loss function L = 1 ⊤ z ⋆ , but all variables are drawn i.i.d. from standard Gaussian distribution N (0, 1).To demonstrate the effectiveness of BPQP, we evaluate the efficiency and accuracy of state-of-the-art differentiable convex optimizers, as well as BPQP, on the datasets mentioned above. The following methods are compared: CVXPY 2021). Exact adopts the same algorithm as BPQP for the forward pass, but attempts to calculate exact gradients using direct matrix inversion on the KKT matrix during the backward pass.To evaluate the efficiency of the compared methods, the runtime in seconds is used for each forward pass, backward pass, and total process. To evaluate the accuracy, we first get a target solution z Exact with a high-accuracy method and then calculate the cos similarity with compared methods (CosSim = z Exact • z methodi /(∥z Exact ∥ * ∥z methodi ∥)). We ran each instance 200 times for average and standard deviation (marked in brackets) of the metrics. The results for efficiency evaluation are shown in Table 1 . The evaluation covers three typical optimization problems with different problem scales. The results start from the QP dataset.Compared with state-of-the-art accurate methods, BPQP achieves tens to thousands of times of speedup in total time. When the problem becomes large, such as 5000×2000, previous methods fail to generate results. CVXPY is extremely much slower because it reformulates the QP as a conic program and the reformulation is slow and has to be done repeatedly when the problem parameters change Stellato et al. (2020) . It is worth noting that BPQP is faster even in the backward pass, where CVXPY and qpth/OptNet share information from the forward pass to reduce computational costs. Sharing this information will limit the available forward solvers and result in a coupled design. Exact falls back to a simpler implementation that does not involve sharing information between designs. It solves the KKT matrix (i.e., Eq. ( 9)) in the backward pass via a matrix inverse method without relying on information from the forward pass. Although Exact uses a relatively efficient implementation in the forward pass (i.e., a first-order method, same as BPQP), the fallback backward implementation becomes a bottleneck for efficiency. The results of the LP dataset lead to similar conclusions as those of the QP dataset.In the evaluation of the SOCP dataset, qpth/OptNet and Alt-Diff focus on QP and are excluded from this non-QP setting. Due to the specialty of SOCP, CVXPY does not require problem reformulation into conic programs, giving it an advantage. BPQP still outperforms other options in terms of total time across all problem scales. The accuracy evaluation results are shown in Table 1 . In the forward pass, all solvers give nearly the same results, which are not shown in the table. When evaluating the backward accuracy, we use a matrix inverse method with high precision to solve Eq. ( 9) directly to get a target solution(i.e. z Exact ) and compare solutions from evaluated methods against it. The CosSim. is relatively higher than that in the forward pass due to accumulated computational errors. Among them, the CosSim. of our method BPQP is the highest in QP. The CosSim. of all methods are small enough for SOCP.Portfolio optimization is a fundamental problem for asset allocation in finance. It involves constructing and balancing the investment portfolio periodically to maximize profit and minimize risk. We now show how to apply BPQP to the problem of end-to-end portfolio optimization(more experiment details in Appendix A.5).Mean-Variance Optimization (MVO) Markowitz (1952) is a basic portfolio optimization model that maximizes risk-adjusted returns and requires long only and budget constraints.EQUATION)where variables w ∈ R d represent the portfolio weight, γ ∈ R > 0, the risk aversion coefficient, and µ ∈ R d the expected returns to be predicted. We built an ML predictor to approximate expected returns. The covariance matrix, Σ, of all assets can be learned end-to-end by BPQP. However, it preserves a more stable characteristic than returns in time-series Lux & Marchesi (2000) . Therefore, we set it as a constant.Benchmarks We evaluate BPQP based on the most widely used predictive baseline neural network, MLP. For the learning approach, we compared the separately two-stage(Two-Stage) and end-to-end learning approaches(qpth/OptNet). The optimization problem in the experiment has a variable scale of 500, which cannot be handled by other layers based on CVXPY and JAXOpt. We found the tolerance level for truncation in Alt-Diff hard to satisfy the 500 inequality constraints and yield a relatively longer training time (588 minutes per training epoch) than the above benchmarks. Our implementation substantially lowers the barrier to using convex optimization layers. Results The overall results are shown in Table 4 . As we can see in the prediction metrics, Two-Stage performs best. Instead of minimizing multiple objectives without a non-competing guarantee, Two-Stage only focuses on minimizing the prediction error and thus avoids the trade-off between different objectives. However, achieving the best prediction performance does not equal the best decision performance. BPQP outperforms Two-Stage in all portfolio metrics, although its prediction performance is slightly compromised. qpth/OptNet shows comparable performance with BPQP. But the average training time of BPQP is 2.75x faster than OptNet. These experiments demonstrate the superiority of end-to-end learning, which minimizes the ultimate decision error, over separate twostage learning. 
conclusion: 
 We have introduced a differentiable convex optimization framework for efficient end-to-end learning. Based on whether an explicit computational graph is constructed, previous work on differentiable convex optimization layers methods can be categorized into explicit and implicit methods. Explicit methods unroll the iterations of the optimization process, incurring additional costs. Implicit methods can't achieve overall efficiency on both computing the optimal decision variable during the forward pass and solving the KKT matrix during the backward pass. Our work, BPQP, is based on implicit methods. We simplify the backward pass by reformulating it into a simpler decoupled QP problem, which greatly reduces the computational cost in both the forward and backward passes.Extensive experiments on both simulated and real-world datasets have been conducted, demonstrating a considerable improvement in terms of efficiency. 
 
 Appendix: A.1 MAP PREDICT-THEN-OPTIMIZE LOSS On selecting β for portfolio optimization in section 5.2, mathematically β = σ 2 r σ 2 y ∈ (0, 1) denotes the ratio of variances between the random parameter y and the regret. Since the empirical regret suffers a more severe fluctuation over y (σ r ≫ σ y > 0) in convex optimization Mandi et al. (2020) , prediction error should dominate in the end-to-end loss. However, we use an empiric distribution to approximate the Dirac distribution and set β to a small (β = 0.1 in portfolio optimization experiment) but not zero value.Under normality assumption arg max(p(θ | regret, y, x)) ∝EQUATIONThat isEQUATION)A.2 DIFFERENTIATE THROUGH KKT CONDITIONS USING THE IMPLICIT FUNCTION THEOREMIn this section, we give a detailed discussion on Eq. ( 9). The sufficient and necessary conditions for optimality for Eq. ( 1) are KKT conditions:EQUATIONApplying the Implicit Function Theorem to the KKT conditions and letP (z ⋆ , ν ⋆ , λ ⋆ ) = ∇ 2 f (z ⋆ ) + ∇ 2 h(z ⋆ )ν ⋆ + ∇ 2 g(z ⋆ )λ ⋆ , A(z ⋆ ) = ∇h(z ⋆) and G(z ⋆ ) = ∇g(z ⋆ ) yields to Eq. ( 8). We can then backpropagate losses by solving the linear system. In practice, however, explicitly computing the actual Jacobian matrices ∂z ⋆ ∂y is not desirable due to space complexity; instead, we product some previous pass gradient vectors ∂L ∂z ⋆ ∈ R d , to reform it by noting thatEQUATIONThe first term of left hand side is the transposed solution of Eq. ( 8) and above can be reformulated asEQUATION) A.3 PRESERVE KKT NORM GRADIENTSIn a typical optimization algorithm, each stage of the iteration gives primal-dual conditions r (k) , we follow the procedures of BPQP and solve the corresponding QP problem Q (k) to define general gradients ∇ y L (k) . The key difference here is that instead of using the optimal solution to derive BPQP, we plug in the intermediate points. By IFT,EQUATION)where K (k) is the Hessian matrix (KKT matrix) at points (z k , λ k , ν k ). The general gradients ∇ y L (k) is given by dr (k) = 0 and therefore ∥r (k) ∥ = C k preserves KKT norm.A.4 SIMULATION EXPERIMENTIn Section 5.1, we randomly generate simulated constrained optimization datasets with uniform distributions and varying scales. We use these datasets to evaluate the efficiency and accuracy of stateof-the-art differentiable convex optimizers as well as BPQP. 2020) as the forward pass solver. In the backward pass, it reformulates the backward pass as an equivalent simplified equality-constrained QP. OSQP is also adopted in the backward pass to solve the QP.Exact uses the same forward pass solver as BPQP. The optimization algorithm used for the forward pass is the OSQP Stellato et al. (2020) , which is a first-order optimization algorithm that does not share differential structure information. In the backward pass, without using reformulation via BPQP, the Eq. ( 9) are solved using the matrix inversion method like Gould et al. (2021) . As a result, this approach fails to achieve overall efficiency.JAXOpt Blondel et al. ( 2021) is an open-sourced optimization package that supports hardware accelerated, catchable training and differentiable backward pass. Optimization problem solutions can be differentiated with respect to their inputs either implicitly or via autodiff of unrolled algorithm iterations.Alt-Diff Sun et al. (2022) adopts ADMM in specializing in solving QP problems with exact solutions as well as gradients w.r.t. parameters.All results were obtained on an unloaded 16-core Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz. qpth runs on an NVIDIA GeForce GTX TITAN X.BPQP decoupled the forward and backward pass and provides flexibility of choosing solvers. Normally, the first-order solver is greatly preferred when the problem scale becomes large and is also robust for small problem scale. Therefore, the first-order solver is a good enough default value, which is also employed by our framework and experiments.A.5 PORTFOLIO OPTIMIZATION EXPERIMENT STATISTICAL RISK MODEL (SRM) is used to generate the covariance matrix of MVO in Section 5.2. It takes the first 10 components with the largest eigenvalues by applying PCA on stock returns in the last 240 trading days. SRM shows the best performance of the traditional data-driven approach for learning latent risk factors.This section provides a more detailed introduction to the datasets and metrics used in the experiments described in Section 5.2. The dataset is from Qlib Yang et al. (2020) and consists of 158 sequences, each containing OHLC-based time-series technical features Beyaz et al. (2018) from 2008 to 2020 in daily frequency. Our experiment is conducted on CSI 500 universe which contains at most 500 different stocks each day.For the predictive metrics, we evaluate IC (Information Coefficient) and ICIR (IC Information Ratio) of predictive model baselines. IC measures the correlation coefficient between the predicted stock returns ŷ and the ground truth y. At each timestamp t, IC (t) = corr(ŷ (t) , y (t) ) in whichcorr(x, y) = i (x i -x)(y i -ȳ) i (x i -x) 2 i (y i -ȳ) 2 .We report average IC across instances. ICIR = mean(IC) std(IC) measures both the average and stability of IC. A well-trained predictive model is expected to have higher IC and ICIR. For portfolio metrics, which measure the performance of investment strategies in the real market, we include two key indicators, Ann.Ret. (Annualized Return) and Sharpe (Sharpe Ratio) , which are the ultimate criteria widely used in quantitative investment. Ann.Ret. indicates the return of given portfolios each year. Sharpe = Ann.Ret.Ann.V ol. in which Ann.V ol. indicates the annualized volatility. To achieve higher Sharpe, portfolios are expected to maximize the total return and minimize the volatility of the daily returns. Transaction costs are not considered in our portfolio metrics to align with the regret loss and more stably demonstrate the effectiveness of end-to-end learning without being distracted by unconsidered random factors.Here is a more detailed explanation of the compared methods in this experiment.Two-Stage separately learns a prediction MLP model to predict expected returns (i.e. µ) and then generates decisions based on Eq. ( 24). All other methods below share the same prediction MLP model and only differ in the learning paradigm.qpth/OptNet performs similar to BPQP, but with sightly lower performance in portfolio metrics and regret as it approaches exact gradient with a lower accuracy, shown in Table 3 .BPQP is our proposed method. All the accurate approaches (e.g. CVXPY, JAXOpt) have similar high-quality solutions in both forward and backward passes and are expected to have similar performance. Among them, only BPQP can efficiently handle the problem size of 500 variables(refer to Table 1 ), and thus BPQP are selected. BPQP is trained using the loss function described in Section A.1. To gain a deeper understanding of how end-to-end regret loss works, Figure 2 demonstrates the detailed learning curve of Two-Stage and BPQP. For each subfigure, the x-axis represents the number of epochs during training, and the y-axis represents the training loss of prediction and decision, respectively. Two-Stage aims to minimize the prediction loss, which is ultimately smaller than BPQP. However, the decision loss remains at a high level, resulting in a suboptimal decision. BPQP aims to minimize both prediction loss and decision loss. Both losses decrease initially, and then they start to compete in the later epochs. However, the decision error remains at a much lower value than Two-Stage, resulting in better decisions in the final evaluation. size 10×5 50×10 100×20 500×100 forward + backward time(s) 1.4e-02 1.5e-02 1.7e-02 1.7e-02Table 5 : Efficiency evaluation of the learn-to-optimize method DC3 by runtime in seconds.solver net (i.e. optimizer) with 500 epochs, 10000 samples, and 10 correction Test Max Steps for each type of QP and LP entries.The computational cost scales linearly with the problem size and the number of model parameters. So, it is very efficient, especially when the scale is large. When the problem size is small (10×5 or 50×10), BPQP is still tens of times faster than DC3. However, DC3 becomes 5-10 times faster than BPQP when the problem size becomes large (500×100). Table 5 is the more detailed result of DC3 for both QP & LP (their problem size and number of model parameters are the same, so the time is nearly the same).For large-scale real-world portfolio optimization, approximate methods such as DC3 can be a practical solution in terms of efficiency. The experiment results are shown in Table 6 . Although DC3 is computationally efficient and thus applicable to large-scale real-world datasets, it performs poorly in decision metrics. This is due to the inaccurate gradient that deteriorates the learned model based on DC3. Therefore, accuracy is an important feature in end-to-end learning. G+ = G(z ⋆ + ) has the same row of active-set as g(z ⋆ + ) = 0, z ∈ R m + . m+ is the number of active sets. 


Decision: There is consensus among the expert referees that the submission should be accepted. The issues raised in the initial reviews were addressed in the detailed rebuttal, which should be incorporated in the paper.

Reviews: review: paper_summary: 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.
strength_weakness: strength_weakness: 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: 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?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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: 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?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: The authors have adequately addressed the limitations and I do not see any potential negative societal impacts.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: See above.
limitations: limitations: N/A

Comments: title: Response to rebuttal
Reply to rebuttal
comment: We sincerely thank all the reviewers and Chairs for their time, effort, and insightful feedback during the review process!
Thank you for reviewing our rebuttal! We appreciate your acknowledgment, and if you have any further concerns or suggestions, please feel free to share them with us at any time.
The author addressed some of my concerns. Although I am also inclined to accept this article, I do not intend to give a higher score at the moment.
Thank you for your comprehensive and insightful review. Your feedback has been incredibly helpful in further improving our work.
Thank you for your feedback and encouraging comments. We appreciate your insight and we will continue to refine our strategy for handling infeasible inputs to enhance the robustness and applicability of our framework. 

Thank you once again for your valuable contributions to our work!
Thanks a lot for your comment. I agree with your response and I will change the rate to 7.
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.
Thank you for your thoughtful review and constructive comments. We greatly appreciate your recognition of our discussion on limitations and future work, as well as the ablation studies carried out during the rebuttal. We are encouraged by your decision to raise your score.

We will make sure to explicitly emphasize the dependency of BPQP’s performance on the choice of solver in the limitations and future work section of our manuscript as suggested. Additionally, we are eager to explore and include less well-behaved examples as what you proposed (non-quadratic or linear objectives) in our experiments to further demonstrate the versatility and robustness of BPQP across a broader range of convex optimization scenarios. 

Thank you once again for your valuable feedback which has significantly contributed to improving our work.
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.