Leveraging augmented-Lagrangian techniques for differentiating over infeasible quadratic programs in machine learning
Authors: Antoine Bambade
Fabian Schramm
Adrien Taylor
Justin Carpentier
Venue: ICLR 2024 spotlight (2024)
Keywords: Machine Learning
Optimization
Differentiable Optimization
Optimization layers
Primary area: optimization
TL;DR: We propose a unified approach to differentiate over the closest feasible quadratic programming (QP) solutions. We show it enables to learn a wider range of QP layers with better performance for some classic learning tasks

Abstract: Optimization layers within neural network architectures have become increasingly popular for their ability to solve a wide range of machine learning tasks and to model domain-specific knowledge. However, designing optimization layers requires careful consideration as the underlying optimization problems might be infeasible during training. 
Motivated by applications in learning, control and robotics, this work focuses on convex quadratic programming (QP) layers. The specific structure of this type of optimization layer can be efficiently exploited for faster computations while still allowing rich modeling capabilities. We leverage primal-dual augmented Lagrangian techniques for computing derivatives of both feasible and infeasible QP solutions. 
More precisely, we propose a unified approach which tackles the differentiability of the closest feasible QP solutions in a classical $\ell_2$ sense. We then harness this approach to enrich the expressive capabilities of existing QP layers. More precisely, we show how differentiating through infeasible QPs during training enables to drive towards feasibility at test time a new range of QP layers. These layers notably demonstrate superior predictive performance in some conventional learning tasks. Additionally, we present alternative formulations that enhance numerical robustness, speed, and accuracy for training such layers. 
Along with these contributions, we provide an open-source C++ software package called QPLayer for differentiating feasible and infeasible convex QPs and which can be interfaced with modern learning frameworks.

Published as a conference paper at ICLR 2024
LEVERAGING LUGMENTED-LAGRANEEE TECHNIQUES FOR G OVER INFEASIBLE QUADRATIC PROGRAMS IN MACHINE LEARNING
Antoine Bambade
Inria Département d'Informatique de I'fcole normale supérieure, PSI. Research University, École des Ponts, Marne-la- Vallée, France. (bambade. antoine @gma com.
Fabian Schramm, Adrien Taylor, Justin Carpentier
Inria Département d' d'Informatique de I l'Ecole normale supérieure, PSL Research University. (fabian. schramm, adrien. taylor, justin.carpentie carpentier) inria. fr
ABSTRACT
Optimization layers within neural network architectures have become increasingly popular for their ability solve a wide range of machine learning tasks and to model domain-specifie knowledge. However, designing optimization layers requires careful consideration as the underlying optimization problems might be infeasible during training. Motivated by applications in learning, control and robotics, this work focuses on convex quadratic programming (QP) layers. The specific structure of this type of optimization layer can be efficiently exploited for faster computations while still allowing rich modeling capabilities. We leverage primal-dual augmented Lagrangian techniques for computing derivatives of both feasible and infeasible QP solutions. More precisely, we propose unified approach that tackles the differentiability of the closest feasible QP solutions in classical l2 sense. We then harness this approach to enrich the expressive capabilities of existing QP layers. More precisely, we show how differentiating through infeasible QPs during training enables to drive towards feasibility at test time new range of QP layers. These layers notably demonstrate superior predictive performance some conventional learning tasks. Additionally, present alternative formulations that enhance numerical robustness, speed, and accuracy for training such layers. Along with these contributions, we provide open-source C++ software package called QPLayer for differentiating feasible and infeasible convex QPs and which can be interfaced with modern learning frameworks.
INTRODUCTION
Incorporating differentiable optimization problems as layers within neural networks has recently become practical and effective for solving certain machine learning tasks, see, for instance (Geng
et al. 2020: Amos & Kolter 2017 Lee et al.
2019
Le Lidec et al., 2021; Donti et al. 2017
de Avila Belbute-Peres al., 2018 Amos al. 2018 Bounou et al. 2021 Donti al. 2222
Such layers allow capturing useful domain sppecic knowledge or priors. Unlike conventional neural networks, where the output of each layer is provided by a simple (explicit) function of input, the input of an optimization layer is the parameter of optimization problem, and its output is solution to this problem. Figure andd Figure 2 provide two illustrative examples of a neural network and QP layer. Both layers have potentially fixed (in blue) and trained (in red) parameters. The main difference is that the output (i.e., y* in Figure I of the forward neural network has a closed-form expression, whereas the output of the QP layer is the solution of constrained QP (i.e., y² in Figure 2). Finally, note that extra parameters (i.e., zf and h² in red in Figure 2) are trained to ensure the quadratic program is always well-posed during training.

---

Published as a conference paper at ICLR 2024
LOSS MINIMIZE
PARAMETER UPDATE
INPUT
Neural network
OUTPUT
=ly)=lly
'''
aL
y' y==tanh(w'x-b)
aL dw
AL ōy dw
ay
Parameters:
trained: w
FORWARD
BACKWARD
fixed: b
Figure 1: Example of feed- forwardd neural network.
LOSS TO MINIMIZE
PARAMETERS UPDATE
INPUT
QP layer
OUTPUT
L(y)=
argmin ||Dy-x|| y s.t., +eyc2++exp(h)
aL
aL dy
C
aL
ay ac
ac
aL
aL ay
="'=z'-0" aL
FORWARD PASS
az
0z
Parameters:
aL aL ay
h -h
aL
C',,'
ah
ah
āh
fixed:
BACKWARD PASS
Figure 2: Example of Quadratic Programming layer (with /) nonsingular).
In this work, we focus on convex Quadratic Programming (QP) layers, a specific type of optimiza- tion layer that offers rich modeling power (Amos & Kolter 2017 Section 3.2). A convex QP parameterized by is defined as follows
f(: 0) = 2" [H(T(((x+ x x 0(0))
x' (0) E argmin #ER"
(QP(0))
s.t. C(0) ([0))==(l) u()).
where (0) E (R) is real symmetric positive semi-definite matrix of R"*=. g(0) E R". C(O) E gnixn and u(0) E R" n is the problem dimension, while is the number of inequality constraints. We will abusively denote H, g. C, and without explicit dependence on 0 when this dependence is clear from the context or does not generate any ambiguity. In order to use (P) as a learning tool that can be trained with standard optimization techniques, we need to be able to differentiate x= (0) w.r.t. 8, which is challenging for few reasons. First, there is usually no practical way to compute a closed-form for x (0), even when QP) is well-defined. Second, even when such x² (9) exists, there is no guarantee for it to be unique nor differentiable w.r.t. 0 (see, e.g., the assumptions of the implicit function theorem (Dontchev & Rockafellar [009 Theorem IB.I)). As consequence, concurrent approaches are generally based on architectures enforcing satisfaction of some strong assumptions. In particular, to the best of our knowledge, previous approaches specialized for differentiating through @P(@eenforee primal feasibility of the layer during training. which generally requires additional learning variables and limits the modeling power of those layers. For instance, as in (Amos & Kolter 2017). learning QP(()) requires imposing its feasible set to be non-empty. For imposing this while learning C, the authors also learn z E R and h E IR and u of the form u = Cz + (h) (similarly to Figure 2), thereby preventing, among others, u from being fixed independently of the learning.
This work makes the following contributions:
We propose unified approach to tackle the differentiability of both feasible and infeasible QPs. The main idea consists extending the definition of x a0)) to be either a solution to QP( when is feasible solution of the closest feasible QP (in the least-square sense) when it is not. By relying on the notion of conservative Jacobian by (Bolte et al. 2021 Bolte & Pauwels 2020), we notably show that the KKT map G of this extended problem
is path differentiable w.r.t. and x* (Section 3.2). In this context, the Jacobian (0) defined as the least-square solution of the linear system formed by applying the implicit function theorem to /Section 3.3] We show that this definition consistently covers the differentiability of feasible QPs with the traditional implicit differentiation (Amos & Kolter 2017) when it is valid and with the least square estimate proposed by (Agrawal et al. 2019 Appendix B) otherwise.
88 is
2

---

Published as a conference paper at ICLR 2024
In Section 3.4 provide efficient ways to compute the Jacobian backward automatic differentiation modes.
(x)(0)
98 in forward and
In Section 4 we demonstrate how the approach enables dealing with possibly infeasi- ble ( during training, while converging for test time feasible layer. We illustrate how it allows to train a broader range of QP layers leanning QPs that are not generically feasible). More precisely. we will show how to drive towards feasibility at test time the QP layer provided in Figure 3 Learning A' (in red) is not obvious since nothing guarantees priori that the fixed equality constraint vector (of ones) lies in the range space of A', We will see that learning such layer notably provides better predictive power for some classic learning tasks.
INPUT
QP layer
OUTPUT y
y = argmin x
y
s.t., A1y=1 and y20.
FORWARD PASS
Parameters: trained: A
Figure 3: A Linear Programming layer. Nothing guarantees during training that the constrained Vector of lies in the range space of the trained matrix A', Our approach enables to train A' such that at test time the LP is feasible.
Based on these developments, we provide QPLayer, an open-source implementation with efficient for- ward and backward passes, freely available at /t/ttts:://iithut
com/ S Simple ee Robot cs/ proxsuite) e It takes advantage, among others, of recent advances in solving of QP problems to output in the forward pass the closest feasible QP solution in Eg-sense as soon as the program primal infeasible (Chiche & Gilbert 2016). [Section 4highlights for different learning tasks the numerical robustness, accuracy, and speed of our approach against other rate-of-theeart methods. Moreover, Appendix C.1 provides different simple experiments with parametric QPs to illustrate the solutions provided by QPLayer in different cases (e.g., LP case, primal infeasible QP case etc.), Appendix C.2 contains additional timing experiments. [Appendix C.3 illustrates through several experiments that QPLayer is numerically more robust and can thereby be trained with large learning rates.
2 RELATED WORK
Differentiation for optimization layers. Under certain regularity conditions, it is possible to implicitly differentiate the optimality conditions of convex optimization problems. (Gould et al. 2016 Gilberi 2021 Fiacco & McCormick) 1968 Robinson 1980) present general conditions and techniques under which it is possible to differentiate through constrained optimization problems using the implicit function theorem. (Bolte et al.] [021]] Bolte & Pauwels 2020) present exten- sions to nonsmooth (not necessarily differentiable) functions for machine learning and optimization applications. (Amos & Kolter 2017) treats the specific case of QPs with dedicated network ar- chitecture, OptNet, and a specialized batched interior-point solver, Qpth, which allows for efficient backpropagation. More recently. (Butler & Kwon (202)) proposed an alternative approach based on the differentiation of ADMM steps. yet dealing only with equality and box inequality constraints For more general convex optimization, (Amos et al. 2018) proposed CvxpyLayer that differentiates through "Disciplined Convex Programs" using an LSQR (Paige & Saunders] 1982) solver to speed up the differentiation procedure. (Sun et al., (002)) has recently proposed an ADMM-type method, called Alt-Diff, to alternatively solving constrained convex optimization program and obtaining approximate Jacobians at the current approximate solutions. caations..Blondee (Blondel et al. 2022) also proposed a generic solver, JaxOpt, based framework. Finally, let us mention the work (Sharma et al. 2022), which provided a Julia library,
implicit automatic differentiation mechanism leveraging the Jax
'The associated solver is yet publicly available.
3

---

Published as a conference paper at ICLR 2024
DiffOpt.jl, for differentiable QP and conic optimization (or any model that can be reformulated into these standard forms).
Unrolling methods. Argmin and Argmax operations can be approximated by first-order methods, which can unrolled (Domke 2012: Monga et al. 202T). These architectures typically introduce an optimization procedure such gradient descent into the inference procedure (Belanger & McCallum 2016, Belanger et al., 2017] Amos et al. 2017 Metz et al., 2019). which is usually truncated to a predefined number of iterations. Recently, (Scieur al. 2022) highlighted the "curse of unrolling" by showing that for unconstrained quadratic optimization, there is a tradeoff between the convergence speed of the iterates and that of the Jacobian. Although unrolling methods are easy to implement, most of their applications are limited to unconstrained problems. Indeed, if constraints are added, the unrolling solutions have to be projected into the feasible region, significantly increasing the computational burdens.
Implicit models. Implicit models replace explicit expressions in neural networks with layers defined by implicit functions (Zhang et al. (2020). As for optimization layers, the backward pass requires equations arising from the implicit function theorem. Recently, there have been growing number of applications using them, such as neural ODE (Chen et al. 2018
solving nonlinear Jacobian-basee
deep equilibrium models (Bai et al. 2019). logical reasoning in deep neural network (using MAXSAT
SDP relaxation) (Wang al. [2019) implicit surface representation (Michalkiewiez et al. 2019).
attention mechanisms (Geng et al. 2021a), graph neural networks (Gu et al. (020). However, this method is not suitable for optimization layers with complicated constraints. Recently, (Fung et al. 2022) proposes matrix-free approach to decrease computational costs, and (Geng et al.) [02] lb) proposes a phantom gradient that relies on fixed-point unrolling and Neumann series for faster computations of approximate update directions.
THE EXTENDED CONSERVATIVE JACOBIAN FOR CONVEX QPs
This section introduces the main contribution of this work: an extended conservative Jacobian for the solutions to QP [ allowing to simultaneously deal with feasible and infeasible QPs, as provided in /ecciin 3.2 and Section 3.3) Seccionn 3.4 proposes efficient algorithms for computing them in forward and backward modes. For exposition purposes, purposes,Appendiis C.T illlstrates the concepts few simple examples.
3.1 PROBLEM FORMULATION
For differentiating QPs, we solve a hierarchic problem QP-H(() which is equivalent to QP when QP(() is primal feasible (i.e., there exists x C(0)z < v())
s" (0) = arg min SER"
(QP-H(O))
s.t. x (0), E arg min max L(x, 8)
#ER" SER,
TT gg() +C u(0) s) (namely the Lagrangian with L(x, 2, 8; 0) - H())x
of QP(() augmented with a slack variable 8). The following assumption is necessary and sufficient for guaranteeing QQ-H(()too have solution. In this situation, Miraaton,[OP-HHUU (QP-H(0) is therefore well-posed and s* is referred to as the optimal shift. It provides a measure of the distance QP to be primal infeasible in sense (hence
iff QP(O feasible).
Assumption 1. (0)) symmetric positive definite in the direction of (()) or g00) is orthogonal to the recession cone of QP(0) i.e., g(0) (0) = {u (²()(( Tyl & u(0) s.1. C(0)x & u(O), 0}.
The existence of a solution (x)()), 20 (0), s()))s(())))))))))))))))))))(s)) is also equivalent to the dual of QP(() having non-empty domain (i.e., being proper), see (Chiche & Gilbert 2016, Assumption 2.6 and Proposition 2.5)). So, the approach proposed here allows differentiating through dual feasible convex QPs.
4

---

Published as a conference paper at ICLR 2024
3.2 THE CLOSEST FEASIBLE QP
In what follows, we deal with QP-H(() via a nonlinear map G:
H (0)x+ + C())
C(0)z u(0) -t
G( 2,t; 0)
(G)
[[t] +2++ 2 -
((O)TELL
where [.]+ and [-]- respectively correspond component-wise projections on the non-negative and
non-pon positive orthants. The following lemma guarantees solutions to QP-H(U) to be zeros of G (see proof Appendix A).
Remark 1. The map G is found via change of variable of the KKT conditions for QP-H(0)
Lemma 1. Let (0) E 84 (RR, g(0) E R" C(O) E R and u(0) E D. be satisfying Assump
tion It holds that (x* 2², s*) solves OP-H(0) iff there exists t" E IR' s.t. G(x", (x= 2;, and
[t*]+.
3.3 THE EXTENDED CONSERVATIVE JACOBIAN
For differentiating through G, we rely on the notion of extended conservative Jacobian (ECJ). As provided by the following lemma, the nonlinear map G(x,, 2, t; 0) is path differentiable (see (Bolte
& Pauwels 2020 Definition 3)) w.r.t. T, 2, t and also w.r.t. 0 under the assumption that (0), g(
C(0) and ul) are differentiable w.r.t. 0. This lemma proved in Appendix B
Lemma 2. G is path differentiable w.r.t. x², 2² and t². Furthermore, if (0). g C(0) and u(0) are differentiable w.r.t 0, then G is path differentiable w.r.t. O.
Definition Let H0)), g(0), C(0) and u(0) be differentiable w.r.t O and satisfying Assumption Let o' = (a",=",1", ,1)) E IR" x R x TR s.t. G(x",=* ;t: 0) O. We refer to the ECJs of x', z
and respectively denoted by 00
de 0= and 0r"
80 as solutions of the following problem
Ox 00
0z*
O
"","",,,,,"" 0)
"C(a",,"'44" 0)
argmmnn
arg min
00
00
Out
00
as Furthermore, we refer to an ECJ of = [1*]+, denoted by 30 any element satisfying with 11 E (()++)(t)) a subgradient of the positive orthant evaluated t*.
0 30
0s*
00
As shown in the next section the ECJs match the definitions of standard Jacobians under standard assumptions guaranteeing differentiability (when the QP is feasible), as provided by (Amos & Kolter 2017. Dontchev & Rockafellar 2009). When the QP is feasible but not differentiable, the ECJ corresponds to a least-square approximation specialized for QPs. similar practical least-square estimate proposed in (Agrawal et al. (2019 Appendix B) for differentiating primal solutions of second-order cones (SOCs Blondel et al. 2022 Section 2.1) proposed a similar estimate.
Remark As introduced in Bolte & Pauwels (2020), conservative Jacobians are generalized forms of Jacobians well suited for automatic difserentiation. A locully Lipschitz, function is called path differentiable if has conservative Jacobian. Importantly, puth differentiability is equivalent to having a chain rule for the Clarke subdifferential.
3.4 DERIVING AN EXTENDED CONSERVATIVE JACOBIAN
This section derives an ECJ and incorporates it in a backpropagation algorithm. also shows how to efficiently compute this ECJ under primal feasibility.
3.4.1
GENERAL CASE: DEALING WITH BOTH FEASIBLE AND INFEASIBLE QPS
In the following, we provide forward and backward pass algorithms to compute ECJs for both feasible and infeasible QPs.
More precisely, (Agrawal et al. [2019] Appendix B) relies on a series of assumptions allowing to simplify the computations. In particular, they assume that 0s* (1 and 0. where slack variable.
5

---

Published as a conference paper at ICLR 2024
Forward pass: Let (0), ( C(0) and u()) be differentiable w.r.t. 0 and satisfying Assump tion 1 and x" 2", "*, t" s.t. G(z², , ,t"; 0) = O. We show in Apppendxx B.2.1.1 that we can efficienlly
derive ECJs of z², 2² and t* by solving the following QP using an augmented Lagrangian -ased
algorithm [Rockafellar 1976)
H
C
OH a0
xx
80
0g
+
8C
20
Ox
0z* 01*
arg min
C
-1
20
8C
30
X
8u
00
00 00
00
0s Bs &s
0
111 -
11
8
0
de
0
0
C (1
(1))
L80
8C
[t"]+
00
(2)
where 11, and Il are binary diagonal matrices respectively corresponding to the subdifferentials [[[]-)([+]] + 2 and (tt)- with the following specific choices in zeros
( 1 when [47] + 2 =0
(Il2); 11 when 17 0.
Furthermore, an ECJ of s* can be obtained via (1 1lg) augmented Lagrangian-bist based algorithm (Chiche & Gilbert 2016), in what follows, we work with s* instead of t*.
0s* 00 As s" is direct output of an
20
Backward pass: Let h R" (R"))² + IR be a differentiable function, and let H()). g()), C(0) and u(0) be differentiable w.r.t. 8 and satisfying Assumption and denote ( := h(x* (0), (0), ) s* (0)). The following assumption is sufficient for ensuring conservative Jacobian Oc can be obtained from the usual chain rule:
Assumption 2. x², 2t and t* are path differentiable w.r.t. 8.
More precisely, under Assumption 2, one can compute:
ØC
OC
Ox OC
02
3C
Ös*
+
(4)
00 dr 00 Oz*
00
Ost
00
Following the methodology provided in (Amos & Kolter
2017
Section 3), also show in
Ap-
pendix B.2.1.2 that conservative Jacobian dn can be obtained via the following expression, which computationally more attractive:
50
OL = (b1)
ÖH
8y
8C x' (x*)
8C 00
OC b (bt)
Ou
00 x²- - (bi)
(b;)
(b:)
bi + (s*)T
(5)
00
d0
00
00
00
where bj. bū. b3 and bj are solutions of the linear system
H CT
0
b
3C
C
0
(T- [h)
0
6
OC
(6)
by
-1
-11
(1)
JL
[b]]
Assumption 3 provides non degeneracy assumptions which ensure equation haas solutions:
Assumption 3. C(0) is full column rank, s" >> O (i.e., all constraints are primal infeasible) and 0c (e.g., the loss L does not depend of 2²)
dz
3.4.2 EXPLOITING PRIMAL FEASIBILITY OF THE QP
In this section, we exploit feasibility of the QP for simplifying the computations. First, for the forward pass, the QP needs only be feasible for the value of 0 under consideration. For the backward pass, exploit the standard assumption (see (Amos & Kolter (017)) of the QP being constructively feasible for all values of 0 (which of course restrictive, but which can be exploited for efficiency).
Forward pass: When QP()) is feasible and H00), g(0), C(0) and u(f) are differentiable w.r.t. and satisfy Assumption | we show in Appendix B.2.2.1 that ECJs can be obtained as solution to the simpler:
Oxt 0z
CT
dz
aH xz
0g
8C
00
00
E aag min de
II CC
I1, -
d=
Ih
3C
00
8u
2s
VI+IT
06
VI+II,
01*
(
0x
ac
Ou
(I -1
x²*
(8)
00
08
08
08

---

Published as a conference paper at ICLR 2024
where II is binary diagonal matrices representing the subdifferential [[]++ + 2*) with the following specific choice:
(11), 1 when Ca u, + 2 0.
(9)
The following lemma (see proof in Appendix B.2.I.2) guarantees that, under standard assumptions,
solutions to equation 7 correspond to standard Jacobians (see, e.g., (Amos & Kolter 2017
Lemma 3. O is feasible and (0), g(0), C()) and u(0) are differentiable w.r.t. and satisfy Assumption and if the KKT matrix of active constraints is nonsingular and x², satisfy strict complementariry, then the ECJs matches the standard Jacobian, i.e., (x'(0)
a6 = Vxx and
0= (0)
(0).
Backward pass: If [0) is by construction primal feasible for any 8, then for any 8, s (0) 0.
We can exploit this result for considering simpler losses not depending anymore of S (0). More
precisely, let h I x (R**) + R be differentiable function, and let (0), g(0), C(0) and n())
be differentiable w.r.t. and satisfying AAssumpiin 1 Then, denoting L()) == (0), (0)).
we show in Appendix B.2.2.2 that when assumptions of Lemma 3) hold the backward pass can be evaluated by solving the following linear system
0c
OC
2
b2
(10)
C2
b-
0z3e
0z.
where J is the set of constraints for which (Il)); 1 and J the one for which (Il)); 0. then retrieved from the chain rule
0C is
30
0c 00 = (b;)
0H
Ög 00
8C + (II))))
T 00 x² (21)
0C b1) 30 by
Ōu
x" + (b2)
(11)
00
00
Note that the assumptions of Lemma 3 are not necessarily met. Such infeasibility be detected easily using iterative refinement (Parikh & Boyd 2014] Section 4.1.2) as it converges to the least- square solution of equation 10 in the infeasible case (see (Güler 1991. Theorem 2.3)).
3.4.3 FUTURE WORK AND POTENTIAL IMPROVEMENTS
Before moving to the experiments, let mention few potential directions for future work and improvements our approach. There remain a few gaps in the theoretical foundations of our methodology, which we believe should be handled in the future. Indeed, we have not proved that we could apply the chain rule to ECJs in the general case in the spirit of CJs (see (Bolte et al., 202I)). Also, it should be confirmed that ECJ indeed reduces to CJ. From what can tell, one major unresolved gap is the scope of applicability of the Implicit function Theorem (IFT). Indeed, standard IFT requires at some point nonsingular matrices, which is not compatible with conditions when (P( is primal infeasible (since primal infeasibility is provoked by degeneracy conditions). Nevertheless, there are known examples (see e.g., the discussion (Krantz & Parks 2002, Section 5.4)) when the IFT can still be applied, even when dealing with degenerate matrices. We leave for future work, extension of these techniques for formulating a IFT adapted for our use-case. While those problems are present in most frameworks (Agrawal et al. 2019 Section B), (Blondel et al. 2022, Section 1),,, using the least- estimate provides good practical results when non-difierentiabiiiy occurs.
EXPERIMENTAL RESULTS
Our backward mode differentiation of convex QP layers has been implemented in C++. We refer to it as QPLayer in what follows. Our code leverages the primal-dual augmented Lagrangian solver ProxQP (Bambade al. 2022). also written in C++ as its internal QP solver. This section illustrates through a classic Sudoku learning tasks that QPLayer allows relaxing primal feasibility constraints, thereby enabling the training of simplified layers.
Benchmark setup. QPLayer is compared to OptNet and CvxpyLayer. The experiments were conducted using all threads of an Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz. The benchmark API is available at atsttps:: http:p:///ttiie htt.tttttttttt////////////.... com/ Btt///Baaaaadeeeeeee qp1 ayer benchmark
7

---

Published as a conference paper at ICLR 2024
Optiet Cothet
Tect ayer
Coapy ayer
Tash OPaayer
Pain Coopylaaper
Tann Optiet
Trai
122
Number of prediction arror
10
20*
10-
10t
10
101
10
100
10.00
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
2.5
5.0
15.0
17.5
20.0
Lpoch
Epoch
(a) Test and training MSE losses of QPLayer. CaxpyLayer and OptNet layers.
(b) Test and training prediction errors of QPLayer, CaypyLayer, and OptNet over 1000 and 9000 puzzles.
Figure 4: Sudoku training and test plots using aPLayer, OptNet, and Cvxpyl Laye can learn LPs (which appear more appropriate), whereas OptNet is restricted to strictly convex QPs.
4.1 LEARNING CAPABILITIES
Differentiable optimization for neural network layers has shown great representational power for learning problems that are fundamentally rooted in optimization. The Sudoku problem is one such problem, which can naturally be cast as mixed integer linear program (MILP). For the Sudoku, OptNet recently showed better robustmess and prediction accuracy results than traditional neural networks (Amos Kolter 2017] Section 4.4). This section shows that QPLayer generalizes even better by exploiting the fact that allows learning LPs (and not only QPs). Further, the ability of QPLayer to deal with possibly primal infeasible problems during the learning process appears to be key.
4.1.1 LEARNING LINEAR PROGRAMS
The Sudoku problem is detailed in (Amos & Kolter 2017 Section 4.4). We reproduce those experiments with OptNet and CvxpyL while letting QPLayer learn linear programs (LPs) instead of strictly convex QPs (the layer model is detailed in Figure of of the appendix). In this experiment, the parameters learned in the layer are the equality constraint matrix and the associated equality constraint vector (through extra variables ensuring the structural feasibility of the layer at training and test time, see Figure 12 of the appendix). OptNet, CvxpyLayer, and QPLayer were trained using Adam with batch of size 150 and learning rate of 0.05 to minimize MSE loss on the dataset created by (Amos & Kolter 2017). The dataset contains 9000 training puzzles and 1000 held-out puzzles for testing. First. Figure 4a shows that QPLayer manages reach better local miniminum for the training and test loss (i.e., about an order of magnitude at the 10th iteration). It ends as well over-fitting the training data, similarly to OptNet and CvxpyLayer Yet. [Figure 4b shows that QPLayer makes at the end of the training process far less prediction errors (i.c., 33 errors for QPLayer over the last 5 epochs, versus 162 for OptNet and 1531 for CvxpyLayer). This advocates that learning a LP instead of a QP enables more accurate and robust training for solving Sudokus.
4.1.2 HANDLING PRIMAL INFEASIBILITY
As outlined in /Section 1.1.1 forcing primal feasibility while learning is a common algorithmic strategy. For the Sudoku problems, those techniques enforeing primal feasibility typically involve neglecting linear cquality constraint Az = 1 (we learn A) which corresponds to Sudoku rules. As shown in Figure 5b] this means that the learning procedures do respect the Sudoku rule constraint (see green and orange dashed Lines-labeled "QPLayer; Ar = 1 violation' and "OptNet; Ar = 1 violation"). In the end, neglecting this constraint ultimately leads learning constraint matrix that is inconsistent with the Sudoku rules. Relaxing the primal feasibility imposed by differentiation procedures of previous solvers thereby appears to key.
By incorporating potential optimal shift s* in its formulation (as exposed in Section 3.1). QPLayer allows dealing with infeasible problems during training. In order to drive towards feasibility the layer at test time (i.e., such that A forms a feasible constraint Ax 1), we consider penalizing the optimal shift s* in the learning loss function (see the layer architecture in Figure 13). The backward pass takes then into account the ECJ derivatives introduced in /Section 3.4.1 Numerical performances
reported in Figure 5 and Figure 5b) It is apparent that the dark green curve labeled "QPLayer-learn A; Ar violation" converges after the end of the first epoch towards model satisfying Sudoku
8

---

Published as a conference paper at ICLR 2024
oveeet veeaden
Number prediction errr
12"
101
orLare:
10
Optlen
wa
OptNet
M55
QPLayer
OptNet-leam
QPLayenleam
12
Oytlie
17.5
8.0
Epoch
Epach
(a) Test MSE loss of Lyyayr OptNet, QPI.ayer-leam A, and OptNet-learn A specialized for learning A. It includes Sudoku Ar violation.
(b) Test prediction errors 1000 puzzles of OptNet, QPLayer, aPeayer-la and OptNet-learn special- ized for learning A.
Figure 5: Sudoku training and test plots using QPLayer and OptNet layers. QPLayer can learn LPs, whereas OptNet is restricted to strictly convex QPs, which limits its representational power. Contrary to OptNer, QPLaayr can be specialized to learn models satisfying specific linear constraints.
rules. The respective yellow prediction and loss curves also converges slightly faster towards regime without any prediction errors. The steeper slope observed in the graph suggests that it might be worthwhile to train a layer that more accurately adheres to the Sudoku rules, this could potentially lead to faster puzzle-solving and more interpretable outcomes.
For comparison with OptNet, we have considered reformulating QP-H(() as convex QP (see Figure 14jin the appendix). The resulting problem considers more variables and constitutes thus potentially harder problem to solve. As OptNet can only learn strictly convex QPs, we have also added small quadratics over the primal variables (similarly to the structural feasible case described in Section 4.1.Ip. The grey curve "OptNet learn A; test loss" shows the result. can be seen that decreases slower and saturates at earlier level, which is consistent with the fact that the problem harder to solve. Furthermore, as expected, it displays a worse prediction error. Indeed, the dark dashed curves "OptNet-learn A; Ax seen that quickly decreases over the first epochs. Yet, at some point does not manage to decrease furthe and saturates at some local minimum around 10-3
violation" outputs the primal feasibility violation. It can be
Finally, let us mention that the formulation developed in [Section 3.4jenables a considerable speed-up over the QP reformulation of equation QP-H(O) Indeed, the forward and backward pass using QPLayer account for about 0.45 = 0.07 seconds per batch, whereas OptNet takes over 8.99 = 0.91 seconds per batch.
4.2 ADDITIONAL EXPERIMENTS
Appendix C.I provides different simple experiments with parametric QPs to illustrate ECJs concept. Appendix C.2 contains additional timing experiments. AAppendix C.3 illustrates through several experiments that QPLayer is numerically more robust and thereby be trained with large learning rates.
5 CONCLUSION
In this work, we introduced an approach for differentiating both feasible and infeasible convex quadratic programs in unified fashion. This approach is particularly relevant for learning with optimization layers through differentiable optimization. In particular, by leveraging augmented Lagrangian techniques for solving QP layers that are potentially infeasible, we propose an extended conservative Jacobian formulation for differentiating convex QPs, covering both feasible and infeasi- ble problems. For feasible problems, and when the solution is differentiable, this reduces to standard Jacobians. We further provide an open-source C++ framework, referred to "QPLayer", which implements the approach. Through a classic learning example we have shown that diffcrentiating over infeasible QP enables more structured learning with better predicting power. We have additionally proposed in the appendix more extensive benchmarks and experiments, to evaluate QPLayer speed and numerical robustness against other alternative state-of-the-an optimization layers. As for future plans, we will extend QPLayer to deal with a broader range of optimization layers that include second-order cones.
'Such behavior could be explained by the fact that the problem is harder to solve, and OptNet fails outputting accurate solutions. Furthermore, as it learss strictly convex QP instead of a I.P. the approximation of the model learned less accurate for solving Sudoku, which are fundamentally formulated MIL.P

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
This work was supported in part by the French government under the management of Agence Nationale de la Recherche through the NIMBLE project (ANR-22-CEE) (ANR-22-CE3--000B) and as part of the "Investissements d' d'avenir" program, reference ANR- SANR-19-P3LE 11--31A--000 (PRAIRIE 31A Institute). This work was also supported by the European Union through the AGIMUS project (GA no. no. 10107016))) Louis Vuitton. This work has also been supported by the Paris [le-de-France Région in the framework of DIM AI4IDF. Views and opinions expressed are those of the author(s) only and do not necessarily reflect those of the European Union the European Commission. Neither the European Union nor the European Commission can be held responsible for them.
BIBLIOGRAPHY
Akshay Agrawal, Brandon Amos, Shane T. Barratt, Stephen P. Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. In NeurIPS, pp. $558-95700 2019. URL
http:://dblp.zzee httppp///lll..ooooeeee//////aaap
Brandon Amos and J. Zico Kolter. Optnet: Differentiable optimization as a layer in neural networks.
In ICML, volume 70 of Proceedings of Machine Learning Research, pp. 136-145. PMLR, 2017. AmosK17
URL https:://aitt dblp.
Brandon Amos, Lei Xu, and J. Zico Kolter. Input convex neural networks. ICML, volume 70 of Proceedings of Machine Learning Research, pp. 146-155, PMLR, 2017. URL https:/ //dblp
org/rec/ con / cm AmosXK17
Brandon Amos, Ivan Dario Jimenez Rodriguez, Jacob Sacks, Byron Boots, and J. Zico Kolter. Differentiable MPC for end-to-end planning and control. NeurlPS, pp. 8299-8310, 2018. URL
https: http//dblppp org/ rec/ conf / n nips/ /ttp//////.//S/SSI/
AmosRSBKI8
C.W. Anderson. Learning to control an inverted pendulum using neural networks. IEEE Control Systems Magazine, 93)):11-37, 1989. doi: 10. N0.1109377.28099 URL
Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In NeurlPS, pp. 688-68886 -886
2019. URL
Antoine Bambade, Sarah El-Kazdadi, Adrien Taylor, and Justin Carpentier. PROX-QP: Yet an- other Quadratic Programming Solver for Robotics and beyond. In RSS 2022 Robotics: Sci- ence and Systems, New York, United States, June 2022. URL https: ihaiainria.fi hal 1a1-03383733
David Belanger and Andrew McCallum. Structured prediction energy networks. In ICML, volume 48 of JMLR Workshop and Conference Proceedings, pp. 983-992. JMLR.org, 2016. URL https 7 7/dblp.a org/ rec/ conf
David Belanger, Bishan Yang, and Andrew McCallum. End-to-end learning for structured prediction energy networks. In ICML, volume 70 of Proceedings of Machine Learning Research, pp. 439. PMLR, 2017. URL BtBpLtttps///bbl.ooe//eeeeeeeee
Mathieu Blondel, Quentin Berthet, Marco Cuturi, Roy Frostig. Stephan Hoyer. Felipe Llinares-López. Fabian Pedregosa, and Jhanlphilippe Vert. Efficient and modular implicit differentiation. In NeurlPS, 2022. URL.ttp::://bbb.roe////eeee htt.://ww...ree..coo/////p////// Bttpss///ooodddddeee HLP222
Jérôme Bolte and Edouard Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient method and deep learning. Mathematical Programming, 188(19-51), April -
2020. doi: 10.1007/s 100070000-0155---5 URL
Jérôme Bolte, Tam Le, Edouard Pauwels, and Antonio Silveti-Falls. Nonsmooth implicit differ- entiation for maahine-learning and optimization. In NeurIPS, pp. 13537-13549, 2021. URL https://dbll p. org/ rec/ http://onnnmmmpp///ttt//////
10

---

Published as a conference paper at ICLR 2024
Oumayma Bounou, Jean Ponce, and Justin Carpentier. Online learning and control of complex dynamical systems from sensory imput. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https:// openreview net/ htt.:eeet/fooeee forum? wtt.ooommmmiotaaooooo V=xtVV8h
Andrew Butler and Roy H. Kwon. Efficient differentiable quadratic programming layers: an ADMM org/
approach. Comput. Optim. Appl. 84(2):449-47,, 2023. URL
Journa ///coapBuut.err22.
Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David Duvenaud. Neural ordinary differential
equations. In NeurlPS, pp. 6572-6583, 2018. URL htttps:///blp..ott http:///rree/ooo////////e/////ee con./ninnff///////
ChenRaD18
Alice Chiche and Jean Charles Gilbert. How the augmented Lagrangian algorithm deal with an
infeasible convex quadratic optimization problem. Journal of Convex Analysis, 23(2), 2016. URL
https: //hal.//haa... inria. fr
Filipe de Avila Belbute-Peres, Kevin A. Smith an Kelsey R. Allen, Josh Tenenbaum, and J. Zico Kolter. End-to-end differenttaable physics for learning and control. In NeurlPS, pp. 7178-7189, 2018.
A. De Marchi. On primal-dual Newton proximal method for convex quadratic programs. Compu- tational Optimization and Applications, 81(2):369 336,39,, 2022. ISSN 0926-6003, 1573-2894. doi: 10.10077s10588--21-000000 010589-021-003422
URL https://ling springer springer.coom/1..0000 com/10.1007..
Justin Domke. Generic methods for optimization-based modeling. A/STA7S, volume 22 of JMLR Proceedings, pp. 318-326. JMLR.org, 2012. (tLLhttps:/ //cblp
jm jmlr/Domee22
Asen L. Dontchev and R. Tyrelll Rockafellar. Implicit functions and solution mappings. 2009.
Priya Donti, Aayushya Agarwal, Neeraj Vijay Bedmutha, Larry Pileggi, and J Zico Kolter. Adversari- ally robust learning for cenurity optimal power flow. Advances in Neural Information Processing Systems, 01-28677728889 2021a.
Priya L. Donti, J. Zico Kolter, and Brandon Amos. Task- end-to-end model learning in stochastic 2017. URL /RL/attps///bbbb...g/e////////
optimization. In NIPS, pp.
Dorti ixA17
Priya L Donti, David Rolnick, and Zico Kolter. De3: A learning method for optimization with hard constraints. arXiv preprint arXiv:2104.12220 2021b.
Anthony V. Fiacco and G. P. McCormick. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley & Sons, New York, NY, USA, 1968. Reprinted by SIAM Publications in 1990.
Samy Wu Fung, Howard Heaton, Qiuwei Li, Daniel McKenzie, Stanley J. Osher, and Wotao Yin. JFB: jacobian-free backpropagation for implicit networks. In AAAI, pp. 6648 166886666..28 AAAI Press, 2022. URL htap://///bbp.oooooeeee/////////
Zhenglin Geng. Daniel Johnson, and Ronald Fedkiw. Coercing machine learning to output physically accurate results. J. Comput. Phys., 406:109099, 2020. URL httpp:://d/b org rec/
journa ls/
Zhengyang Geng, Meng- Hao Guo, Hongxu Chen, Xia Li, Ke Wei, and Zhouchen Lin. Is attention better than matrix decomposition? In ICLR. OpenReview.net, 2021a. URL https:://ddt ://dblp
Zhengyang Geng, Xin- Yu Zhang, Shaojie Bai, Yisen Wang, and Zhouchen Lin. On training implicit models. In NeurlPS, pp. 24247 242600, 2021b. URL hitps: http//bblpppoo http///lpppppppccc/////eeoe f/
n Dpss/enng2BW.211
11

---

Published as a conference paper at ICLR 2024
Jean Charles Gilbert. Fragments d' d'Optimisation Différentiable Théories et Algorithmes. Lecture, March 2021. URL httpps:////.. //ahl.
Stephen Gould, Basura Fernando, Anoop Cherian, Peter Anderson, Rodrigo Santa Cruz, and Edison Guo. On differentiating parameterized argmin and argmax problems with application bi-level
optimization. CoRR, abs/ 607.05547, 2016. URL PRLhttps:// http://bbbb..oooccc/oo/oaaaaaaaa
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent Ghaoui. Implicit graph neural networks. In NeurlPS, 2020. URL hettps///bblp.oogg/eee//oooo
abs 2009-06211
Osman Güler. On the convergence of the proximal point algorithm for convex minimization. SIAM Journal on Control and Optimizatiin, 29(2):403 419, 1991. doi: 10.1137/0329022. URL
https:: http:://doo..rg/////// www.oo/./.............
Diederik P. Kingma and Jimmy Ba.
Adam: A method for stochastic optimization. CoRR,
abs/1412.69800, 2014.
Steven George Krantz and Harold R Parks. The implicit function theorem: history, theory, and applications. Springer Science Business Media, 2002.
Quentin Le Lidec, Igor Kalevatykh, Ivan Laptev, Cordelia Schmid, and Justin Carpentier. Differen- tiable simulation for physical system identification. IEEE Robotics and Automation Letters, 6(2): 3413-3420, 2021.
Kwonjoon Lee, Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. CoRR, abs/1904.03755. 2019. URL http::///ra/.ii.rrrg. abs/ 19049 03758
Quentin Le Lidec, Louis Montaut, Cordelia Schmid, Ivan Laptev, and Justin Carpen- tier. Leveraging randomized smoothing for optimal control of nonsmooth dynamical sys- tems. CoRR, abs/2203.0390 2022. URL (tlthttts:://dt http://///lbpppoorre//e//oo/e/e http://eec/oouraassseeeaaeee
abs 2200-2002222222 03986
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, C. Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers. ICML., volume 97 of Proceedings of Machine Learning Research, pp. 4556-4565. PMLR, 2019. URL https
//dblp.org/ren htth:////ccceee//ceeeeeeeeeeecee /aann//icc///MttMMMM ZMNFS19
Mateusz Michalkiewicz. Jhony Kaesemodel Pontes, Dominic Jack, Mahsa Baktashmotlagh, and Anders Eriksson. Implicit surface represennaations as layers in neural networks. In IC/CCV pp. 4742- 4751. IEEE, 2019. /tt.:t/tpp/.//bbpoo////////////p
Vishal Monga. Yuelong Li, and Yonina C. Eldar. Algorithm unrolling: Interpretable, efficient deep learning for signal and image processing. IEEE Signal Process. Mag., 38(2):18 44, 2021. URL
https: /ttp::///bbppp org/ rec/ www.rauuraaaaaaaa hwtpaaalllls.p/a/aagaaaaaaaaaa LF21
Christopher C. Paige and Michael A. Saunders. LSQR: an algorithm for sparse linear equations and
sparse least squares, ACM Trans. Math. Softw., 8(1):43-71, 1982. URL htllttttp///::poor
ttt.s//ooooooooooooooo.otttttttt Pal ge582
Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends@ in Optimization, (3):127-239, 2014. ISSN 2167-3888. doi: 10.1561/24000000003 URL http::tt:/./. www. 10. 10.1561/2400000000
Stephen M. Robinson. Strongly regular generalized equations. Math. Oper. Res., 5(1):43-62, 1980.
URL htttp:://:/ttt hwtpporg/resoe httt:p/:/.hblll.oo//////////////
R. T. Rockafellar. Augmented Lagrangians and Applications of the Proximal Point Algo- rithm in Convex Programming. Mathematics of Operations Research. 1(2):97-116, 1976. URL lattp:/ 1st psu. httpt:tptt..e.eeeeeee////e/e//ee /tt..///e/eedddooooooaaaaaaaa01.
12

---

Published as a conference paper at ICLR 2024
Damien Scieur, Gauthier Gidel, Quentin Bertrand, and Fabian Pedregosa. The curse of unrolling:
Rate of differentiaaiing through optimization. In NeurlPS, 2022. URL htttps:///blppp: org/
See//cont/aaps///ccerrGG33
Akshay Sharma, Mathieu Besançon, Joaquim Dias Garcia, and Benoît Legat. Flexible differentiable optimization via model transformations. CoRR, abs/2206.06135, 2022. URL httpp://:///
H. Terry Suh, Tao Pang. and Russ Tedrake. Bundled gradients through contact via randomized
smoothing. CoRR, abs/2109.05143, 2021. URL
05143
Defeng Sun and Liqun Qi. On nep-functions. Comput. Optim. Appl, 13(1-3):001-220, 1999. URL https://dblp.cr org rec/ httpo////wwe//////////ee//////// http///naaa/c////uaaaaaa/a/aaaaa http//appp///// Sung99
Haixiang Sun, Ye Shi. Jingya Wang, Hoang Duong Tuan, H. Vincent Poor, and Dacheng Tao.
Alternating differentiation for optimization layers. CoRR, abs/2210.01802, 2022. URL https:
Po-Wei Wang, Priya I.. Donti, Bryan Wilder, and J. Zico Kolter. Satnet: Bridging deep learning and logical reasoning using differentiable satisfiability solver. In JCML, volume 97 of Proceedings of Machine Learning Research, pp. 6545-6554. PMLR, 2019. URL
conf/icml/Ni/ htt.c//////aaan11a5
Qianggong Zhang. Yanyang Gu, Mateusz Michalkiewiez, Mahsa Baktashmotlagh, and Anders P. Eriksson. Implicitly defined layers in neural networks. CoRR, abs/2003.01 2020. URL
2003-01822
13

---

Published as a conference paper at ICLR 2024
ORGANIZATION OF THE APPENDIX
Section
Content
Appendix A
Lemma
solutions to QP-H(())
Lemma 2
path difffrrentiability of G Appendix B.
Forward AD (general case,
A Appendix 1.2.1.1)
Backward AD (general case,
Appendix B.2.1.2).
Appendix ECJs and automatic differentiation.
Forward AD (feasible QPs, Appendix B.2.2.1
Backward AD (structurally feasible QPs, Appendix B.2.2.2
Lemma 3 when do ECJs reduce to Jacobians? Appendix B.3
Strictly convex QP (parameterizeed constraints)
Appendix C.I.1
Appendix C.I Pedagogical examples.
Strictly convex QP (parameterized objective) A Appendix C.1.2)
Parameterized linear program (Appendix C.1.3).
Appendix C.2
Additional benchmarks (timing).
Appendix C.3
Training with large learning rates experiments.
Appendix
Layer architecture for the Sudoku problem (Appendix D.1).
Experimental setups.
Description of the cart-pole problem (Appendix D.2).
Table I: Organization of the appendix. QP stands for "quadratic programming". AD stands for "automatic differentiation", and (E)CJ stands for (extended) conservative Jacobian.
A
PROOF OF LEMMA
For proving Lemma |
we first show that solutions (oQQ-H(() are zeros of the map G:
H(0)=+ + = u + (C(0)= u
G z; 0) =
(12)
Then, suitable change of variable shows that finding zero of is equivalent to finding zero of map G.
Lemma 1. Let (0) E (R), g(0) R". C(0) E x. and u(f) B. be satisfying Assump
tion It holds that (x", 2², s*) solves QP-H(0) iff there exists tx E RR s.t. G(x", 2², ;,; B) and 8 = -1
Proof. We first show that (x*,2*,
2* [Cx* -u] w]+) solves equation QP-H(() if and only if G(** [(=*,,=;; 2²;
The optimal shift s* (that corresponds the closest feasible QP) is equal to [Cx" u]+ and is characterized by the f2 optimality condition (Chiche & Gilbert 2016 Lemma 2.13):
CT [Cr u]+
Furthermore, for feasible problem, the KKT conditions using nonlinear complementarity formula- tion (Sun Qi 1999 reads (De Marchi, 2022
Section 2.1):
-' [Cx* - -u -
Hx* + + 0,
(13)
For showing equivalence, it is thereby sufficient show that the second line of equation 13 corre- sponds to:
[Cxx - u]- +22 2=1+ 2 =0 0.
(14)
14

---

Published as a conference paper at ICLR 2024
This equivalence is straightforward when equation QP(4) is feasible, it therefore follows that only need to handle the infeasible case. When equation (P()) is primal infeasible, then t" = Cx* - u has set of components I [1. [ı] strictly positive, hence s7 [t tt 0. For these components, a solution x² of the closest feasible QP lies on the border Cræ* = uy + 17. The complementarity
condition (De Marchil 2022 Section 2.1) for these components reads:
Cx
ur 17
27 O,
and we thus have [*7]+ 27. For the other set of components, which we denote by 15, we have that s 0, and hence x² follows the complementary conditions in the feasible case
[Cx" u7 21.1+
2j. O.
Therefore, it follows that equation 14 captures the two cases (that both feasible and infeasible QPs), which concludes the first part of the proof.
Finally, introducing the slack variable t* C(0)x* u(0), we have
G(x" ; 0) =
(15)
H(0)x² + g()) + C(0) 2
[[C(0)=* - u(0) + 2" 2
0
(16)
C(O)
(())++
H(())² + +0) C(O) 0(0)x* -u()) -
+
[|t*] + 21
0
(17)
C(0) [t'
G(æ x²,t",; 0) 0.
(18)
Hence G(x", ,*) iff (a* 2", (t*]+) solves QP-H(0) which concludes.
B ECJS AND AUTOMATIC DIFFERENTIATION
This section provides the proofs of the different results used Section 3 In particular, we define ECJs and provide algorithms for computing them (both in forward and backward AD modes).
B. PROOF OF LEMMA
Lemma 2. G is path differentiable w.r.t. x", and Furthermore, if ((). g(0), C(0) and u(0) are differentiable w.r.. 0, then G is path differentiable w.r..
Proof. We start with the first claim of the lemma. The non-negative projector [-]+ is (component-wise) convex, and hence path differentiable (Bolte & Pauwels 2020 Proposition 2()). Thus, it remains to show that the third component of G is path differentiable for reaching the desired conclusion.
To do so, we show that the third component is Lipschitz continuous and real semialgebraic (Bolte & Pauwels 2020 Proposition 2(iv)). Without loss of generality, we restrict ourselves to the case with components (one for the dual variables, and one for the slack variables) using the following function h: 2 + R, s.t. h(2, s) = [[s] + 2]+ z. Then, the following Lipschitzness argument applies component-wise.
15

---

Published as a conference paper at ICLR 2024
Let 21) RR and (82, 22) E R
[h(21, $1) - h(22. s2) < [[[]]]] 21]+ [[s2]] - 22]+1 22l
[[ + [22] - ズ2 + | 22 by monotonicity of [+]+
< [[s]] [s2]-|+ 2|
|81 [si]+ (82 [s2]+)] 2/ 22
[s1
s2l
[[s]++ [ 2 22l
2
82
+ 2/ 22| by monotonicity of [.]+
[1
$2
2
112.
22
Therefore, h is Lipschitz continuous. For showing that the third component G describes a semi- algebraic set, we explicitly formulate the graph of h as finite union of base semi-algebraic sets, as follows:
gph(h)
=[(2,8,) E R'ly== = [s] and [s] + 0}
U ((2,
and
[s] + 2 = 0}
( and
[s] + = < 0)
= <( and > 0 and <0)
((2, and = 0}
U e((,, R and 2 > 0 and s 0}
U ((2,8,8)) R$y = and + = = 0 and 8 < 0}
U ((2,8,8) E R = 2 and
= and = 0}
U ((2,8,8) Ryy = and and > 0}
U (((,8,8) Ryyy = and + 2 < 0 and < 0}
U ((,,8,)) E R
and
and 0}
U ((2,8,)) R
and and 0)-
Hence, gph(h) is real and semi-algebraic as it a finite union of sets defined by polynomial equalities and inequalities. Hence h is Lipschitz continuous and real semi-algebraic, thereby reaching the target conclusion for the first part of Lemma? 2]
As for the second part of Lemma 2 and u()). Furthermore, by assumption (0). g(0). C(0) and u(0) are differentiable w.r.t. B. As diffcrentiability implies nuth-differentiabiiity (Bolte & Pauwels 2020 Remark 3b), arrive at the desired claim by the conservativity of the chain rule for path-differentiable functions (Bolte & Pauwels 2020 Proposition 2).
G is linear, and hence differentiable, w.r.t. H(0), (0), C(O)
B.2
FORWARD AND BACKWARD AD FOR COMPUTING ECJS
This section provides technical details for the computation of ECJs in forward and backward modes for both primal feasible and infeasible problems. We further include the proofs of ?? and Lemma 3
B.2.1 GENERAL CASE
B.2.1.1 Forward pass. Let (0), g(0), C(#) and u(f) be differentiable w.r.t. and satisfying As sumption 1l and x² x²,2" 2*, s.t. G(x=" 2",,"; 8) O.
As G path cath-differentiable w.r.t. n² (x*, 2², ttt) (see Lemma 2). we have
H
C
-1
"G''","",,"; 0)
0
111 -
11
E
Ovt
0
CTI
for some II, 0[]++ ([r) + =*), IT (1)) and IT (1*).
16

---

Published as a conference paper at ICLR 2024
Furthermore, as G' is linear w.r.t H0), g(0), C(0) and u(0) and ( g C(0) and u(0)
differentiable w.r.t. 0, the usual chain rule dictates that
aH 39
80
.68
"0""t"2""tt" 00
ac 00
du
x
86
BC
Finally, as (0) 00]](0) [0, 1], we make the following arbitrary choices in zeros
11 = I when [t*] + 2" 0,
11 = I when t" 0,
(19)
Iī = O when = O,
so that 113 = 112. ECJs are thus retrieved as solutions to:
H
CT
0
Har
TH 80
x² + 0g
00
+ 00
2"
Ox
0z*
Ot
E arg min
C
0
-1
D=
+
aC
00
3:" 30
(20)
00"
00
00
8z
0= 8t
11
-
11
C. - 112)]
8C
[++]+
00
In practice solving this problem can be done via an augmented Lagrangian-based solver for the problem:
Ox
0z
Or
E
arg min
0
00
00
00
17
H
CT
0
30
+ 0g
00
+
0C
30
2'
(21)
s.t.
0
11 -
11
-1
28
20
00
2t
0
0u
00
0
0
CT I2))
39
ac
[t*]
80
when this problem is feasible. When it is not feasible, the augmented Lagrangian naturally converges to the solution the more general equation 20] see (Chiche & Gilbert 2016 Proposition 4.2). In comparison equation 20) a notable advantage of the formulation equation 21 is that is naturally numerically more stable and sparse-by avoiding square matrix products from the objective.
B.2.1.2 Backward pass.
The following lemma formally details the results from Section 3.4.1
Lemma 4. Let h R (R - R be differentiable function, and let H(O), g(f), C(0) and (())
be differentiable w.r.t. and satisfying Assumption 1 Then, denoting L(0) == (xxx(()) , (0),
and under assumptions of Assumption Assumptioo 3 we have that ac can be derived as follows de
ac = (b1)
0H (b;)
T 0g
3C
OC
dC b (b²)
0n.
00 x-
(b2)
x' + (x*)
00 bi + (s*)
00
0e
00
80
00
where bū, bū, b3 and by are the solutions of the linear system
H CT
6C
b
C 0 11)
0 (1 - C12)
0 -1
-11
AC
b2
Ov
Proof. Under the assumption of Assumption 2
it holds that
is CJ
05 29
and (1
30
11 Br E 8s"
36 38 are CJs ( (Bolte & Pauwels, 2020 Proposition 2)). Furthermore, as differentiable
x² 2" and st it is path-ddifeernttable (Bolte & Pauwels 2020 Remark 3b) w.r.t. x so
17

---

Published as a conference paper at ICLR 2024
can apply chain rule (Bolte & Pauwels,
2020
Proposition 2)):
0c
0C
Ox
UC
02
UC
Ös*
+
00
Ox+
00
dzt
00
Ost
00
5C
Ou
--(-
02
0=
80
H
CT
0
D1 SP
ax
20
=
(I-II)
0
-1
11
(1 CC2
200
BH
xx* + 0g
+
8C T
30
30
8C
09
20
30
69
0
aC
[t*1+
HH
0g
00
(61)
x
+
2²
00
00
00
(69) +
00
0u
00
00
OC
(b2)
[t)++
00
OH
00 x² 0C
0g
(61)
0i)T² + (b,)
00
00
8C
Ou
+ (bg)
x-
00 00
00
+ 00
61) [b')+).
To conclude, we show there always exist solution bj, bg, b of the system:
H
CT
0
b
6C
C
0
(1 11)
(22)
b3
0
-1
-11
- CC
82
Under Assumption 3
11, / and 1l, = 0 (since s*
[t*] 0). Furthermore, since dC
0.
32
equation 22 is thus equivalent to solving
и CT
0
6
5C
b
8
C
0
0
0
bg
0
-1
C
5C
6
6x*
The latter system can be reformulated as
8C
8C
C. Cb C
CT
(23)
5x
SC
+ Cbi,
(24)
0st
Cb
(25)
which has always solutions since C is supposed to full row rank.
B.2.2 SIMPLIFICATION OF WHEN QP IS FEASIBLE
B.2.2.1 Simplification of the forward pass When QP(0) is feasible and ( g()), C(#) and
u()) are differentiable w.r.t. 0 and satisfy Assumption then [(*] Further, choices of
18

---

Published as a conference paper at ICLR 2024
subgradients at zero (see equation
19
imply that II, I and hence the following simplifications
H
C
0G(x",²",t", 0)
0
11
11
Ou*
0
8.H 00
x=
0g
9C
8C
80
01
(G 2", ,-,,0;;
0
08
0
Moreover, the optimality conditions of
H
CT
Ba
BH
00
30
8g
8C
30
0r
0z*
C
HC
arg min
+
09
00
00
00
8x 0z Be
0
11
II
20
0
0
write down
Or
HC 0=*
CT Ot
0H
0g
8C T
OC
du
2
C. C)
+ [
x²
+
+
2 +
C
x*
0,
00
00
00
08
00
00
00
00
CH dx
02
0H
0g
0C
+ +C
C 11,
+ C
x²
+
=*) = 0, (26)
00
00
00
06
00
dx
Ot*
8C
du
+ (I + II,)
= 0.
00
08
00
08
Third equation of equation
26 leads
Ot
Or
0C
8u
(C
+ x
00 00)).
00
1+
11,
00
00
Hence, optimality conditions without variable
reduce to
20
I11
C) Ox
dz*
II1
ac
du
0H
0g
0C T
(1I2 CT
+ HCT
CT
H
x*)
0,
I 1+ II
00
00
1+
00
00
00
00
00
(27)
Ox
0z
0H
0g
00 T
CH
+CT
II1)
+
C
0.
00
00
00
Furthermore, the following problem
CT
Oe
8g
ac
min As
II VI+II
C
IT
-
II
0C
x=
0u
De
VI+I
80
have the same KKT conditions as equation 27
thereby allowing to simplify the problem as follows:
da d= X 06
aG(x*, 8"; 0)
OG 0)
min 0x 01
0i*
00
(28)
Gz Bs
min
I1 VI+II
H
C
I1
CT
11-1
0x
20
20
0H
80 x
I1+
11
0C
80
00
8g
80 T
00
0u
86
Hence
Oz
Ox 0z dt
aG(x* ,,"",""""""" 0)
30
aG
(x
,,2, 0)
E arg min
0s
+
00 00 00
20
00
o6 80:00 89
70
01
equivalent to
Oxt 0z
CT
8H DM
+
0g
80
E arg min
70
00
00 00
C
II,
8u
09
VI+II
00
20
8t
6x*
ac
Ou
(I+
(I
[
x²
80
89
00
a0
19

---

Published as a conference paper at ICLR 2024
B.2.2.2 Simplification of the backward pass. This sections details the results from Section 3.4.2
Lemma 5. Let h R x (R*))= - be a differentiable function, and ler ( g(0), C(0) and u(0) be differentiable w.r.t. and satisfving Assumption 1 Then, denoting [(0) == h(2" (0), 2" (0)), we have under assumptions of Lemma 3 that UL can be derived as follows
30
0C 00
0H
0g
8C
80
Ou
(b²)
30 x + (b
+ (1)
00 x" + (2
b/ (II b2)
00
00
00
with by by the solution of the following linear system
- -I-
H
C
bz
-1--
ba
Furthermore, this latter linear system can be solved using iterative refinement.
Proof. Under the assumptions of Lemma it holds that
Jacobian. Furthermore, as C is
differentiable, the chain rule implies that:
ac
00
00
Oc
Ozz"
(-
T
O2
d2*
H1
CT
ba
T
Ozz
as the matrix is nonsingular (see Lemma 3)
[IC
II1 I
b2
DE
bz
BH
30 O0
+
8g
+
8C 2H
2"
bz
IT
( 88
0C
x."
89
0H
0g
ac
(b,)
xx
00
00
00
(b.)
( (II'
du))
=[(b2) 0H x² + 00
OC
0g
bz)
T 2 + (bx)
00
00
aC
x² 0u
+ (bx) (II
)
00
00
where (br, bz) solution to
bz
8
C
b.
62
As detailed in the proof of Lemma (see details in Appendix B.3).
equivalently solve
H
CJ
bz
C
bz
825
S.C
b2g
5z3
with J the index set for which the solution is strictly feasible (i.e., i [1, (I1); = 0), and the set of active constraints (i.e., for which (II)); 1). Such linear systems can be solved e.g., via iterative refinement (as the matrix involved is symmetric positive semi-definite (Parikh & Boyd 2014 Section 4.1 4.1.2)).
20

---

Published as a conference paper at ICLR 2024
B.3 PROOF OF LEMMA
This section details the proof of Lemma 3 ensuring that, under some regularity assumptions, ECJs reduce to standard Jacobians.
Lemma !)(P(() is feasible and H()), g()), C(O) and ul0) are differentiable w.r.t. and and if the KKT matrix of active constraints is nonsingular and x² z² satisfy
satisfy Assumption I
strict complementarity then the ECJs matches the standard Jacobian, i.e., 0z"(0) Vx (0) and
(0) 36
(8).
Proof. If equation QP(0) is feasible, then the ECJs of x² and 2" w.r.t. A are provided by
Ox 0z"
CT
de
8g
8C
00
00
E arg min
88-88
VI+III
C 11
29
29
d2
38
I1
09
29
x
88
au
80
(29)
where TT, corresponds binary diagonal matrix of the complementarity conditions Ca" - O. Denoting by J the index set for which the solution is strictly feasible (i.e., i E [1, n.). (1I = 0). and by J the index set of active constraints (i.e., for which (II1); 1) then A can be reformulated as follows (by strict complementary)
H
C
C
A
L
CJ
0
0
V2
with / being the identity matrix of appropriate dimension. Furthermore, the right-hand side of linear system within the & norm becomes
80
x
+
80
0g
20
T
2
8C
V2
80
x
30
0
Н CJ
] corresponds to the KKT matrix of active constraints, and is nonsingular by assumption.
H
CJ
As it implies nonsingularity of
it follows that:
C,
0
V2
θzy 0,
00
and the solution to equation
29 is uniquely determined the solution of the following linear system
(as in (Amos & Kolter 2017 Appendix A), after multiplying second row block by v2):
C 0
a0
AH 700
x² +
70
0g
8C
700
2"
C,
8C
80
x 00
Hence, we arrive at the desired conclusion that ECJ coincides with the usual Jacobian this case.
C ADDITIONAL EXPERIMENTAL RESULTS
Appendix C.I provides few simple experiments with parametric QPs illustrate the concept of ECJs. AAppendix C.2 contains additional benchmarks. [Appendix C.3 illustrates through several experiments that QPLayer can be trained with large learning rates.
21

---

Published as a conference paper at ICLR 2024
C.1 PEDAGOGICAL EXAMPLES OF PARAMETRIC QPs
A few numerical examples illustrate the concept of ECJ in different simple scenarios. The first example corresponds to a strictly convex parametric QP which can be either feasible infeasible. In this example, linear constraint depends on parameter 0. Depending on the value of this parameter, the QP can either be feasible or infeasible.
The second example is strictly convex QP with parameterized linear cost. This problem is always feasible.
The last example is a parametric LP with possibly multiple solutions. For appropriate values of the parameters, the LP feasible but not differentiable.
C.I.1 STRICTLY CONVEX QP (PARAMETERIZED CONSTRAINTS)
Consider the following strictly convex QP parameterized by scalar value
x (0) arg min - (a7 +z²)
1
21,2 2
(30)
s.t. 1 + 22 < 1.55,
1.5 <2n Ta & 1.55
Notice that for 0umi 1.55, the QP becomes primal infeasible. We use gradient descent to minimize two scalar losses (0) (0) and (0) 20). starting from predefined value 0g More precisely we have launched gradient descent for steps with a learning rate 5 x 10-4 starting from 8 1.54. Figure 6a illustrates the results by showing the iterates of gradient descent for minimizing z (as well as the search direction minus the ECJs). By doing so O increases and eventually becomes larger than Ojiiit
Figure 6b reports a similar experiment for when minimizing x2(
COAA
1.4
-008
114
1200
1200
1.20
133
1,00
2200
1302
130
(a) 40 steps of gradient descent for minimizing (0) starting from O 1.54. When 0 1.55, equation 30 differentiated though infcasible.
(b) 40 steps of gradient descent for minimizing =0) starting from Ou 1.54. The QPs remain feasible.
C.1.2 STRICTLY CONVEX QP (PARAMETERIZED OBJECTIVE)
Consider the following strictly convex QP parametrized by a scalar value 0
1
0
x² (0) = arg min
21 2R, 2
Ø2
-2
(31)
s.t. 300 <
22
400,
200
< 2z
+
x2
< 500
40 iterations of gradient descent with learning rate x 10 10 starting from 6 = 1.54. as reported by Figure 7 As expected, see that (0) -0, hence increasing / decreases x (0).
We gradient descent to minimize the loss (1)
More precisely,
22

---

Published as a conference paper at ICLR 2024
1,5000
X010
1.4925
1.4900
1.4825
1,4800
-1.5000
-1.4975
-1.4950
-1.4925
-1.4900
-1.4875
-1.4850
-1.4825
-1.4800
Figure 7: Gradient descent for minimizing 2 (0) (solution to equation 31 starting from 6, = -15.
C.1.3 PARAMETERIZED LINEAR PROGRAM
Consider the following LP parameterized by a scalar parameter
(0) arg min 21 + 22 ER
s.t. < 01 + T2,
(32)
0 σ x 1
0 < 12 1.
Note that this LP is always well-defined for any 9 since the linear cost is orthogonal to the recession (which empty), thereby satisfying the technical requirements from Assumption We gradient descent for minimizing two scalar losses Li (0) (0) and C2 xz(0).
C.1.3.1 Feasible case (0 < 2). For any EJO, 2). there are infinitely many solutions to equation 32 which are defined by the segment equation
+ = 0 0 0 . < 1,
0 < 1
We can see in Figure and Figure 8b that the forward pass chooses as solution x; xi = Hence,
only the constraint S 32 active. Following the formalism from Section 3.1 we have
0
c
- 0
0
-1
23

---

Published as a conference paper at ICLR 2024
The ECJs of L1 and Le w.r.t are the solutions
(b
0
(62)
(6 )2
arg min by b,
0
-1
(b )2
+
b
-1
[d 11 (d 2
0
-1
[d )1
0
0
E arg min dx dz
(d )2
d=
-1
d=
As the corresponding linear systems involved within the lg norm are infeasible, the least square estimates do not correspond to solutions to the linear system. That is, the corresponding least-square solutions are respectively the solutions of the following projected linear systems:
[b
1
0
0
(b))
0
[
1
07
[dd)
(d 12
2
d²
which leads to 30 ae
ac OC.
= bن
d
Figure 8a and Figure 8b show that those directions allow
minimizing L1 and L2 through gradient descent.
128
0.80
0.81
0.81
0.81
3.50
648
4.00
6.6
(a) 40 iterations of gradient descent for minimizing xi (0) for the problem equation 32
(b) 40 iterations of gradient descent for minimizing (0) for the problem equation
32
C.1.3.2 Infeasible case (0 2). the least-square solutions to
For any 0 > the LP is infeasible. The corresponding ECJs
CT
b1
éC,
b2
8x
arg min
||
C
0
(I
II,
+
0
1 for i E {1,2),
bg
by bo..b.. bb.
I
1T,
C2
b1_
0
0
0
07
0
0
0
0
0
0
with
1
0
and P3
0
The linear system within the & norm
0
0
0
0
0
0
0
feasible and QPLayer outputs as ECJs following such directions allows using gradient descent for minmizing E and L22
ac
30
DC
38
3.
Figure 9a and Figure 9b show that
24

---

Published as a conference paper at ICLR 2024
10080
1.010
1440
12412
(a) 40 steps of gradient descent applied to minimize (0) starting from Op = 2.2. when
(b) 40 steps of gradient descent applied to minimize z (0) starting from Op = 2.2, when
considering the infeasible LP defined by equation 32
considering the infeasible LP defined by equation 32
C.2 TIMING BENCHMARKS
In this section, we report our numerical results and compare them against state-of- ofaee-of-the-art frameworks on of standard experiments. We outline detailed timings for differentiating solutions on set of different QPs. First, Table 2 shows the results for a few randomly generated QPs. Second, Table 3 reports the average time spent in the differentiation procedure on four different learning tasks.
Additional experiments are provided in (Appendix C.2
In the first of experiments (see Appendix C.2.I). QPLayer is compared to OptNet, CvxpyLayer, JaxOpt, and Alt-Diff. For all the other experiments, QPLayer is benchmarked only against approaches available within the PyTorch framework (i.e., OptNet and CvxpyLaye
C.2.1 RANDOM QPs
In this first set of experiments, we generated random QPs with 100 variables, 50 equality, and 50 inequality constraints. We solve and backpropagate through all those QPs for different forward pass accuracies, We then average the results over trails and report the timings in the spirit of (Sun et al. 2022).
For a batch size of 100, Table 2 shows that QPLayer is almost times faster than OptNet (the second fastest approach). We can see similar performance for a batch size of 1 (see Table 4, QPLayer is about 4 times faster than OptNet (the second fastest approach) for all target accuracies). We observe that the speed gain is mostly due the forward pass speed-up. enabled by the use of ProxQP and thread parallelization. It is also confirmed by Table 5) which reproduces in Table 5he serial forward timing benchmark proposed (Amos & Kolter 2017] Section 4.1). exhibits from times faster computation times.
C.2.2 LEARNING TASKS
For this second of experiments, report the numerical results obtained traditional learning tasks (namely MNIST classification, signal denoising, Sudoku solving and cart-pole experiment). For all experiments, we report the average (over all epochs) time spent in the forward and backward passes. TTalle 3) reports that QPLayer is 3 to 10 times faster than the second fastest approach (i.e., 3 times faster on the classification task, times faster on the Sudoku, about 10 times faster for the denoising and 7 times faster for the cart-pole experiments). In all cases, the test loss incurred using QPLayer either similar (for the denoising and cart-pole tasks) or far better than competitor layers (about 2 to times smaller for the classification and Sudoku experiments).
More precisely, the first three experiments reproduce the ones originally described in (Amos & Kolter 2017 Sections 4.2 to 4.4). A complete description of the cart-pole swing-up task is detailed
AAtfDiff' exhibited too slow performances for fair and reasonable comparison. Note that (Sun et al. 2022 have not yet proposed an Alt-Diff layer deriving all QP Jacobians. Therefore, we have included in our benchmark open-source implementation of Alt-Diff based their work.
25

---

Published as a conference paper at ICLR 2024
in Appendix D.2 These tasks involve learning convex feasible QPs using Adam optimizer (Kingma & Ba 2014). The first three experiments are run with the default batch sizes and the number of epochs fixed by the original authors (i.c., batch size equals 64 for classification, 150 for denoising and Sudoku tasks; 30 epochs for classification, and 20 for denoising and Sudoku tasks). We run the cart-pole example with batch size 1 for 800 epochs. For the first three experiments, same QP layer models as (Amos & Kolter 2017). except that we have changed the backends for executing the forward and backward passes (using either Qpth, QPLaye or CvxpyLayer), Finally, we have used the following learning rates for running the benchmarks: 10 for classification, 10-5 for denoising, 5 10-2 for Sudoku, and 10-1 for cart-pole tasks.
the
Forward tolerance
10-1
10-2
10-3
Forward (ms)
72.43 (17.288)
71.89 (#3.0)
72.12 (#:4.21)
Backward (ms)
18.14 14 (=1.01)
18.03 (#0.17)
18.12 (#0.37)
QPLayer total (ms)
90.57
89.92
90.24
Forward (ms)
340.62 (17.06)
348.68 (#3.51)
349.44 (#2.44)
Backward (ms)
6.39 (+00.16
6.61 (+0.41)
6.66 (++038)
OptNet total (ms)
347.01
355.29
356.10
Forward (ms)
123.35 (=13.70)
196.75 (+:8.13)
281.54 (#.64.1)
Backward (ms)
546.91 (+:55.58)
622.45 (+66.63)
723.34 (+-66.26
JaxOpt total (ms)
670.16
819.20
1004.88
Forward (ms)
1.16(10.038)x00'
1.19 (10.015)x10*
1.24 (10.0017xx10*
Backward (ms)
187.52(+8.59)
187.74 (#11.54)
197.18 (+7.99)
CvxpyLayer total (ms)
1.35x103
1.38x103
1.43x 103
Forward (ms)
Time limit
Time limit
Time limit
Backward (ms)
Time limit
Time limit
Time limit
Alt-Diff total (ms)
Time limit
Time limit
Time limit
Table 2: Timings for deriving all Jacobians of random QPs with different forward pass accuracies and batch size 100.
'Yet two differences should be noted: QPLayer learns LP for the Sudoku experiment. We have not imposed zero Hessian for the Cvxpyl Layer even if it could leam it, it would display worse results. Furthermore, for the denoising experiment, QPI Layer learns the lower and upper bounds simultancously.
26

---

Published as a conference paper at ICLR 2024
Learning Tasks
QPLayer
OptNet
CvxpyLayer
cart-pole
Forward (ms)
55.20 (#6693)
615.84 (#16.15)
629.70 (#330.42)
Backward (ms)
39.27 (=2.17)
61.26 (#2.84)
101.88 (#1.11)
Final test loss
0.02556
0.02604
0.02566
Sudoku
Forward (ms)
87.39 (#16.69)
454.48 (+:22.22)
772.77 (#33.89)
Backward (ms)
20.80 (=1.70)
8.07 (+00.42)
192.99 (19.81)
Final test loss
6.19x x 10
0.0017
0.389
denoising
Forward (ms)
247.89 (#17.03)
2827.48 (=618.78)
Error
Backward (ms)
52.99 (#2.75)
40.57 (+2.98)
Error
Final test loss
3281.84
3529.2029
Error
classification
Forward (ms)
26.77(#3.63)
102.62 (=18.23)
Error
Backward (ms)
11.12 (#3.01)
16.58 (+12.0
Error
Final test loss
0.1363
0.3264
Error
Table 3: Timings and final loss of learning tasks. CvxpyLayer errors arise due failures in filling the disciplined parametrized programming (DPP) form of quadratic cost.
Forward tolerance
10-1
10-2
10-3
Forward (ms)
1.30 (+0017)
1.42 (=0.19)
1.55 (+0.20)
Backward (ms)
0.77 (+0001)
0.70 (+0.02)
0.71 (+0.02)
QPLayer total (ms)
2.07
2.12
2.26
Forward (ms)
6.93 (#00.22
6.85 (=0.05)
7,49 (#0.04)
Backward (ms)
0.75 (+1
0.70 (+0.01)
0.70 (#0.01)
OptNet total (ms)
7.68
7.55
8.19
Forward (ms)
7.99 (1:0.93)
12.82 (1:2.67)
18.82 (+:4311
Backward (ms)
24.71 (12253)
30.47 (12.71)
36.43 (13.93)
JaxOpt total (ms)
32.70
43.29
55.25
Forward (ms)
411.20 (#3.90)
415.94 (#2.63)
422.28 (+2.65)
Backward (ms)
6.13 (+00.02
6.34 (+.0333
6.26 (+0.06)
CvxpyLayer total (ms)
417.33
422.24
428.54
Forward (ms)
6.00 (++0.85) 1
38.66 (+7.1 10
114.20 (4:31.48)x 10
Backward (ms)
0.99 (+.0211)
0.98 (+0.13)
1.05 (+0.14)
Alt-Diff total (ms)
6.00 3
36.66x 103
114.20x 103
Table 4: Averaged timings for the forward and backward passes when computing all Jacobians of randomly generated feasible QPs (with 100 primal variables, 50 equality constraints and inequality constraints) considering different forward pass accuracies. The batch size is 1. QPLayer has the best total timings for all accuracies.
27

---

Published as a conference paper at ICLR 2024
QP and Batch sizes
QPLayer (ms)
OptNet (ms)
CvxpyLayer (ms)
Batch = 1, n = 100, n, = 0, n2 50
0.88 (+00066
8.01 (=0.89)
334.06 (#7.83
Batch = 1. n = 100, fh = 50, n4 = 50
1.09 (10.10)
8.35 (-0.67)
406.18 (11..4)
Batch = 1. 100. = O. 100
1.22 (1.0.08)
7.62 (=0.32)
422.59 (114.44)
Batch 1, 100, The 50, 100
1.75 (#0.17)
13.95 (+2.03)
522.80 (#3,96)
Batch 1. 100, f2 100, n4 50
1.26 (10..4))
16.77 (#3.41)
521.18 (=16.15)
Batch 1. n 100, n2 100, n1 100
1.45 (1:0.88)
18.33 (#53355
621.25 (19.67)
Batch 64, 100, nh O, 50
30.16 (+5.511)
173.95 (+ 12.82)
771.49 (+59.74)
Batch 64, 100, ne 50, n4 50
48.60 (+9.19)
183.84 (+9.99)
818.75 (+5.42)
Batch 64, 100, nh n2
44.68 (#:5955)
176.88 (=2.30)
820.85 (=13.8
Batch = 64, n = 100, ne = 50, 74 = 100
55.77 (#:)38)
243.15 (#27.86)
1126.99 (#34.33)
Batch = 64, = 100, ne = 100, 74 = 50
51.66 (1:8.51)
231.11 (3:73)55)
1177.89 (+132.99)
Batch = 64, 100, = 100, = 100
62.52 (#7.84)
276.18 18 (#31.29)
1314.47 (=69.60)
Batch = 128, n = 100, n. = O, n, 50
62.94 (+9.52)
620.91 (#3.52)
1202.61 (=88.32)
Batch = 128, n = 100, ne = 50, = 50
78.01 (+4.06)
667.55 (=5.86)
1295.50 (+24.63)
Batch = 128, 100, fee 0, n4 100
89.48 (17.09)
653.32 (15.54)
1267.83 (130.85)
Batch 128, 100, n2 50, 100
111.01 (+8.21)
774.08 (+20.90)
1739.41 (#70.53)
Batch 128, 7 100, The 100, n4 50
96.23 (+9.47)
811.44 (+25.299
1896.52 (+284.89)
Batch 128, n 100, n. 100, n1 100
119.13 (1100177
934.26 (187.79)
2059.44 (=147.77)
Table 5:
Timing benchmarks of different backends used for solving a forward pass for different batch sizes. ne stands for the number of equality constraints.
C.3 TRAINING WITH LARGE LEARNING RATES
In this section, assess the numerical robustness of QPLayer traditional learning tasks by demonstrating that it can be trained with larger learning rates than other approaches, potentially resulting in improved attraction pools.
More precisely, we ran the MNIST classification and denoising tasks described in ?? with SGD and larger learning rates and reported the corresponding results. We measured the final test loss and error reached after 30 epochs and the standard deviation over the last 10 epochs of the test loss and test error. The results are averaged over 10 seeds and the experiment is performed for different learning rates.
As described in Appendix C.2.2 for those tasks, the QP layers need to learn all the model parameters (i.e.. H. g. C, and u). We observe that it generates potentially very ill-conditioned problems when the forward the backward passes are not solved accurately enough. This phenomenon appears to be amplified with larger learning rates. In those situations, it appears that robust solution methods (e.g., allowing for temporary infeasible, or ill-conditioned problems) are critical.
Figure 10a 10a and Figure show that for too high learning rates (i.e., 10-4 or 10-5 for denoising task and 10 10 for the classification task) the OptNet layer generate errors, whereas is never the case for QPLayer. Furthermore, for low learning rale levels (i.e.. 10 or 10-7 for the denoising task and 10 and 10 for the classification task), the final loss reached is similar but with a less important noise amplitude level when using QPLayer (Figure 11 provides robustness statistics of the classification task using the prediction error rate of the two layers). Finally, QPLayer is capable of being trained with larger learning rate (i.e., 10-1 for the denoising task and 10-2 for the classification task). Also,
28

---

Published as a conference paper at ICLR 2024
note that LvxpyLayer fails to be run in all these robustness experiments because the Hessian part of the quadratic model fails to fit the required DPP form (Amos et al. 2018 Section 4.1).
10a
102
OptNet erners GPlayer
final
107
102
Opt meen GPLayer std mear
30*
101
Robustress
10*
30
Optitel
10-1
Layyy mean
OptNict mean
Layye std meae
Eroor
0001
1e-05
1e:00
1e-07
0.003
(a) Robustness statistics for denoising task.
(b) Robustness statistics for MNIST classification task.
Figure 10: Robustness statistics for denoising and MNIST classification tasks: number of errors (i.e., NaNs), averaged final loss reached after 30 epochs (with 95% confidence intervals). and averaged standard deviations over the last 10 epochs (with 95% confidence intervals). Results are averaged over 10 seeds. CvxpyLayer fails to be trained for all these tasks.
10a
OptNet errors
104
QPLayer
OptNet final error mean
10a
QPLayer final
OptNet std mean
Robustness statistics
102
QPLayer std mean
10
10
10
10-2
10-3
0.01
0.001 Learning rates
0.0001
Figure 11: Robustness statistics for MNIST classification: number of errors (i.e., NaNs), averaged final prediction error reached after 30 epochs (with 95% confidence intervals), and averaged standard deviations over the last 10 epochs (with 95% confidence intervals). Results are averaged over 10 seeds.
Remark 3 (Numerical differences with OptNet). Our approach offers a few numerical advantages compared to (Amos & Kolter 2017). In particular, a numerical matrix factorization at the center of most popular techniques for differentiating through OPs. This factorization procedure represents one of the main bottlenecks in the computational costs. In our approach, we need to factorize smaller and better-conditioned symmetric matrices.
29

---

Published as a conference paper at ICLR 2024
The formulation exploited by OptNet consists of larger linear system compute its Jacobians. More precisely, they factorize a matrix of the form:
H 0
C
== 0 D
D(t*)
C
0
where 1* u and D(z*) corresponds a diagonal matrix whose diagonal entries correspond to 2", For obtaining symmetrized version that can be factorized with efficient methods, the second row block scaled by D(1jt*) (Amos & Kolter 2017 Section 3.1). Yet. symmetrization comes the price of being more sensitive to the localization of the solution w.rl the constraints. Indeed, x² lies on the boundary, i.e,, Cya* U1 for some component index I, the conditioning of the matrix degraded, OptNet needs to divide by zeros (or small clamped numbers in practice).
On our side, the formulation feasible QPs relies on smaller matrix, which is symmetric and better- conditioned (it does not require scaling rows by values that are potentially zeros, see equation 70
D EXPERIMENTAL SETUP
This section details the optimization architectures used for the Sudoku tasks described in Section 4.1 The cart-pole task mentioned in Appendix C.2.2 detailed Appendix D.2.
D.1 LAYER ARCHITECTURE FOR THE SUDOKU PROBLEM
& Kolter 2017) for the Sudoku problem is described in Figure 12 In contrast, the QPLayer architecture (which does not require structural feasibility of the QPs) described in Figure 13 The QPLayer architecture allows learning more structured constraints, such as the Sudoku constraint "Ar 1", which cannot be done, as is, with OptNet (which requires the QPs be structurally feasible).
The layer architecture used by OptNet
Amos Amos
QP LAYER
MEAN SQUARED ERROR
argmin alxx||"-x'y stt, A O
Li(x,, E. ||4" "11
over LPs,
Y
150, spochs
Parameters trained: At, h²
A A'- d,
}
0,L O,,00, 0,L 0,.10_,
MODEL TRAINED WITH OPTNET
ht* 0,L
sG0 based update
Chain rule
Figure 12: Strictly convex QP layer trained using OptNet in Section 4.1.1 (as in Amos & Kolter
(2017). The constraint matrix and an extra variable are learned in order to be sure that the QP always primal feasible (structural feasibility).
3
LP LAYER
argmin -xyy x 1+5, O.
L[(x* }}=E> |xx" - FF ||5"||
9000 wich mini
V
epachs
Parameter trained: A"
A A A'-1=A Iro,t } 0,L 0,1=0,10,w+-,,u 0,s*
MODEL TRAINED WITH QPLAYER
update
Figure 13: An LP layer trained allowed by QPLayer in Section 4.1.2) It enables for more flexibility in the problem to be learned (only the constraint matrix A is learned). The optimal shift s* is a new output variable minimized in the loss, in order to learn test time feasible LP layer.
30

---

Published as a conference paper at ICLR 2024
3
QP LAYER
She argmin [||||44|||4|
L(Ox*, s - | - IF + ||s:||
9000 wich mini
size
Parameter trained: A
MODEL TRAINED WITH OPTNET
= A Ir
} 0₂L 0,L_ O,s
update
Chainrule
Figure 14: A QP layer formulating equation ((-H(8) as a convex QP problem. The optimal shift s* output variable minimized in the loss, in order to learn at test time a feasible QP layer. The resulting forward pass considers a larger and potentially harder problem to solve. InfSection 4.1.2 this
layer is trained using OptNet after adding a small strictly convex quadratic (i.e., 5 x 10 10
x 113)
D.2 DESCRIPTION OF THE CART-POLE PROBLEM
The cart-pole system (Anderson) 1989 is classic control problem used for benchmarking control algorithms. The system we consider consists of an extended model with dry friction on the joints of the cart-pole, namely on the prismatic cart joint and the revolute joint of the pole. It makes the dynamics non-smooth. It is described by a set of differential equations relating the position, velocity, acceleration, angle, and angular velocity of the cart and pole plus the additional friction forces. The static friction forces on each joint can be obtained by solving QP problem, see equation 33
and (Le Lidec et al. 2021).
The initial position of the cart-pole system consists of the pole hanging down vertically. The objective of the task is to move the cart in such way as to swing the pole up and keep it balanced in the upright position. To swing the pole up, the control inputs may involve moving the cart back and forth a particular pattern that generates the necessary forces to overcome the friction and accelerate the pole in the desired direction.
Task:
The forward dynamics with friction
Ma = T X,
can be re- re-written in terms of velocity and impulses with timestep Al as
uy + -- >AV = uy
were M is the inertia matrix of the system, E "h- is the joint acceleration, E RT the joint torque, vy the free velocity of the system without friction and Rhv the dry friction force on every joint. To obtain the friction impulse A corresponding to the friction coefficient the following quadratic problem can solved:
1
min ATM A A
2
(33)
s.t. A En
Its Lagrangian L can written as follows
L(A, = 1 3 N (IA) 17),
which leads to the KKT system:
M- A + + diag(sign( (a))gn(A))y = O.
(34)
|A| & n
(35)
y >>> O,
(36)
y ||A| 7)
(37)
31

---

Published as a conference paper at ICLR 2024
where stands for the standard Hadamard product. Considering the case where the friction force within the friction cone for a specific joint j. i.c. [Ayl < M/j the joint is then not moving. We see from equation 37 that yj 0 satisfies equation 36 and we get from equation 34
M A
Vz.
Consequently, the friction impulse is acting in the opposite direction than the joint torque тy and with a magnitude that is canceling out the free velocity. If |Ay] 72 the joint will no longer be blocked by the friction forces and will thus start moving. We see from equation 34
M M A, 2.j U diag(sign(AA))e)
(38)
As 2 0, equation 38 shows that A is opposed to the velocity of the joint.
Optimal control algorithms such as Differential Dynamic Programming (DDP) can be used to compute the optimal trajectory that minimizes a cost function over finite time horizon, subject to dynamics of the cart-pole system and control input constraints.
These methods take advantage of the derivatives of the dynamics to efficiently control physical systems. In the presence of non-smooth dynamics, such class of algorithms is likely to fail due, for instance, to the presence of discontinuities in the dynamics derivatives or because of the non- informative gradient (Lidec et al. 2022). In the cart-pole benchmark, randomized smoothing, as proposed by (Lidec et al.) 2022; Suh al. (021) is used to cope with the non-smooth dynamical system. For the optimal swing-ur up trajectory with 20 timesteps, 5 random samples with a uniform Gaussian noise are generated. The random noise is applied to the input controls, and the dynamics are calcul ated for each of them and afterward averaged in the forward pass, resulting in informative gradients in the backward pass. equation 33 has be solved for every random sample in every timestep.
32


Reviews:
[{"review_id": "EU8XZPqb5Y", "reviewer": "Reviewer_sv98", "summary": "The authors study the problem of calculating the gradient of optimal solutiosn to the input in the convex quadratic programming problem. One limitation of existing convex QP layers is that they assume the QP problem is always feasible during training. The main contribution of the paper is developing an augmented Lagrangian-based approch to calculate the gradient when the QP problem is not feasible.", "questions": "1. The paper is not easy to follow. In some key sections or proofs, the authors suggests to read some other referecens to undertand the concepts. This makes reading the paper difficult for readers that are not working on this specific area of extended conservative Jacobian. To make the paper easier to read, the authors are suggested to add the basic concepts and ideas in the paper instead of requesting the audience to read a number of other reading materials.  \n\n2. To address the infeasibility issue for the QP layers, one straightfoward way is to introducing slack variables and add penalties about the constraint violation in the objective function. The authors are suggested to show the advantage of the proposed approach as compared to this straightforward approach.\n\n3. One application of the QP layers is to use it as a building block for existing iterative algorithms (similar to the approach in [R1] and [R2]). The authors are suggested to analyze the convergence performance of the iterative algoritms when using the propsoed conservative Jacobian as a building block.\n\n\n[R1] Donti, P.L., Rolnick, D. and Kolter, J.Z., 2021. DC3: A learning method for optimization with hard constraints. arXiv preprint arXiv:2104.12225.\n[R2] Donti, P., Agarwal, A., Bedmutha, N.V., Pileggi, L. and Kolter, J.Z., 2021. Adversarially robust learning for security-constrained optimal power flow. Advances in Neural Information Processing Systems, 34, pp.28677-28689.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper studies an important problem.\n2. The paper proposes a new approach to calculate gradients in convex QP layers.", "weaknesses": "1. The paper is not easy to follow. See the comments below.\n\n2. The analysis in the paper is not sufficient. See the comments below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wkV2aDsoYs", "reviewer": "Reviewer_7UKP", "summary": "The paper proposes an approach for differentiating through quadratic programs (QP)s that might be primal infeasible. It provides all the necessary mathematical derivation and extensive numerical experiments including comparisons to state-of-the-art approaches like CvxpyLayers and OptNet. The paper provides a clear approach for this task (basically introducing primal slack variables and hence, considering the extended conservative Jacobian. Forward and backward mode autodiff rules are also provided.", "questions": "The approach behind CvxpyLayers seems to use a similar least-squares relaxation (as also stated in the paper). How does the presented approach differ from this?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Solving (constrained) QPs as a layer within a neural network can be a useful task. Hence, the topic of differentiating QPs that might be primal infeasible is very important. The mathematical derivation seems sound (though I did not fully check it), the presentation is very clear, and the experiments are also very convincing.", "weaknesses": "The approach behind CvxpyLayers seems to use a similar least-squares relaxation (as also stated in the paper). How does the presented approach differ from this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5dG2UbR81D", "reviewer": "Reviewer_vnSN", "summary": "This paper considers the problem of training neural network with quadratic program (QP) layers. In order to differentiate the quadratic program, previous work has to enforce the feasibility by ignoring some constraints. In contrast, this work improves the QP layer and allows directly differentiating through infeasible QP layers. The this end, the authors introduce a slack variable (which measures the \"degree\" of infeasibility) and minimize the the Euclidean of the slack variable in a hierarchical quadratic program. To differentiate through the hierarchical, the author propose using the extended conservative Jacobian.\n\nThey show the improve QP layer enables learning linear programs and quadratic programs without neglecting any constraints. In addition, the proposed method stabilizes training and leads to better performance.", "questions": "How is the hierarchical quadratic program (QP-H) solved numerically? Is it similar to phase-I method in interior point methods?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The idea is well-motivated and experiments are convincing. This paper solves an important problem in learning QP layers. The proposed method could greatly improve the robustness of QP layer training and handle all QP layers (including the infeasible ones) in a principle manner.\n- The technique in this paper could be potentially generalized to all differentiable convex layers.", "weaknesses": "- This paper is very technical and the presentation should be improved. For example, the non-linear map (G) is introduced without any background information. The authors should add more text to motivate this non-linear map and explain how it is derived.\n- Limited scope of applications. The experiment only shows training QP layers solving Sudoku problems. However, I am interested to see if the improved QP layer enables new applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aRulQYh0QY", "reviewer": "Reviewer_uDj8", "summary": "The paper studies the problem of differentiating through quadratic programming layers. These are layers whose output is the solution to some quadratic programming problem, whose problem data depends on the input to the layer.\n\nThe main contribution of the paper is to provide a more efficient way to compute the Jacobian of the solution mapping which maps inputs to the layer to the solution of the quadratic programming problem. Besides this, there are also a number of experiments demonstrating the efficacy of this proposed method on the sudoku problem, comparing to alternative methods like optnet and cvxpylayer.\n\nA major obstacle in quadratic programming layers has been maintaining feasibility of the quadratic program; previous works have always parametrized or constrained the layers in a way to ensure feasibility but this limits expressiveness. A key advantage of the method proposed by the paper is that it can handle both feasible and infeasible quadratic programs by extending the definition of a solution to account for infeasibility. In the case of infeasibility, the solution is considered to be a solution of the closest feasible quadratic program in a least-squares sense. This is accomplished using an augmented Lagrangian approach to representing the quadratic program that is more flexible and allows to better treat this infeasibility, at least empirically.\n\nThe paper also introduces a notion of extended conservatve Jacobian as a way to make sense of the nonsmooth \"Jacobian\" like objects computed by automatic differentiation in the case of infeasibility. There are some results showing that, under very strict hypotheses, the extended conservative Jacobians correspond to ordinary conservative Jacobians or ordinary Jacobians.\n\nSmall comment: in section 3.1 \"hierarchic\" is not a word.", "questions": "Is there any hope to handle the gaps that you outline in 3.4.3? Even for feasible programs, it's not always guaranteed that x\\* is a function since there can be many solutions, so how would it be possible to pursue path differentiability?\n\nSince the augmented Lagrangian approach for possibly infeasible QPs already existed, is the contribution here just to combine it with deep learning?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is very rigorous and mathematically precise in its statements and proofs. Furthermore, the method is very practical in the sense that it allows for a much broader class of quadratic programming layers than previous works did while at the same time offering computational advantages in terms of accuracy, time for the forward pass, and total time for the forward+backward passes. These advantages are shown to hold for many different problem settings, not only the sudoku problem but also the cart-pole problem (optimal control), and denoising and classification tasks coming from computer vision. The experiments are very comprehensive and convincing in terms of the empirical performance of this method vs prior works on quadratic programming layers.", "weaknesses": "The theoretical claims in the paper are correct but they are basic and unsatisfying. While it's shown that G, a sort of KKT mapping, is path differentiable with respect to its arguments x,z, and t, this is insufficient for rigorously differentiating through the quadratic program layer. It must also be shown that the solution mappings themselves, x\\*, z\\*, and t\\* are path differentiable with respect to the theta. Otherwise, knowing that G alone is path differentiable is not useful. The path differentiability of x\\*, z\\*, and t\\* is rigorously proved in Lemma 3 but the assumptions of this lemma are so strong that it is no longer applicable to quadratic programming layers. It requires that the objective function in the quadratic program is no longer quadratic (indeed, it must be linear in the lemma) and that it does not depend on theta anymore (g is constant).\n\nThis does not appear to be a trivial problem; proving that the solution maps are path differentiable will require assumptions that negate some of the proposed contributions of the paper, i.e., we will no longer be able to treat such a broad class of problems and this might even exclude infeasible problems, which is a supposed motivation of this work. To be fair, this is a problem of other frameworks as well (as the authors themselves point out) and this paper should not be singled out for this shortcoming, but it is indeed a **major** shortcoming in terms of the theoretical contributions of this work.\n\nBecause of this drawback with respect to the theory, I find the claims that this method handles infeasible problems a bit unsatisfactory - it seem to be based entirely on the experimental observations that it works but there is no rigorous justification that I can find.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)